compression of Sparse Voxel Octrees

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Mar 18, 2011 at 04:24

So you can store a 3d world in a sparse voxel octree, but youve taken up huge amounts of ram in doing so.
Jon Olick says you can get it down to a bit and a half per voxel utilizing some compression techniques… any ideas to how this could be possible?

10 Replies

Please log in or register to post a reply.

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Mar 18, 2011 at 13:35

Why not ask Olick himself?

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Mar 18, 2011 at 14:11

How do I get a message to him? I wonder if he even has the time…

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Mar 18, 2011 at 15:01

I guess I was implying he’s online and you may be able to find a way to reach him. For example, a comment on his blog on a voxel post may get an answer.

6837d514b487de395be51432d9cdd078
0
TheNut 179 Mar 18, 2011 at 15:35

Tell him to make time :lol:

According to his paper, his storage is 8 bytes per voxel. He only mentions positional data is 1.15 bits in comparison to triangle storage. According to his storage structure, 1 byte is allocated for the children mask. A byte has 8 bits and a voxel has 6 possible children (sides of the cube), plus itself so 7 bits in total. 8 / 7 = 1.142 positional bits per voxel. He probably just rounded that up to 1.15. His encoding is similar to how PNG files are encoded before they are compressed with deflate. Stochastic data doesn’t compress very well, so if you filter the data to minimize entropy, compression algorithms like deflate will do a much better job. In his case, he stores the relative values instead of absolute values (exactly what PNG does).

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Mar 18, 2011 at 16:42

thanks for that info, so it is similar to png, i cant really do voxels tho, cause i know how to save a png file, but i dont know how to code it myself.

Ive actually moved to displacement mapping (see my other post http://www.devmaster.net/forums/showthread.php?p=82256#post82256) and its going quite well, and with that yes all i do is literally save the png file and displacement map is compressed.

So far I got my voxel model to be about 1.45 bytes positional data and not sure at all how I would compress colours in the state they are in, so I think im much better off with displacement maps, and then I would get pretty nice compression, even without knowing much about compression.

what do you think nut… would displacement map models compress detail better than a voxel model?

6837d514b487de395be51432d9cdd078
0
TheNut 179 Mar 18, 2011 at 18:34

It would work fine for simple terrain, but anything with interior would be problematic. It offers the best compression for what it does, but without interior it’s not much of a voxel format ;) With my limited knowledge, I would stick with the classical approach of storing and loading spatial trees. You also get the added bonus of storing and loading LOD levels, which will be important for dealing with memory intensive voxel data.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Apr 19, 2011 at 13:24

This is a revival on the old post.

So I finally read what you said TheNut and I finally understand!! (sort of) :)

So you store the voxels as neighbouring bits from each other, and it comes to about 8 bits a voxel… how do you compress further than that?

I sorta gather entropy is when the data turns to complete noise.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Apr 19, 2011 at 16:39

Oh I get it! Entropy encoding is just huffman encoding, can I ask another question? could you use entropy encoding for the colours as well as the neighbour bits? and how well would it do… theres no way youd get 8:1 compression like Jon Olick says… or can you?!?

and by filter, do you mean make all the similar colours the same colour, that would be a good image filter to go into huffman code, is that what you mean?

6eaf0e08fe36b2c23ca096562dd7a8b7
0
__________Smile_ 101 Apr 20, 2011 at 18:46

You must use entropy encoding for anything, because colors and normals eats much more space, than child bits (not neighbour). Also, I suggest using some type of arithmetic coding instead of Huffman (Huffman can compress down to integer number of bits, while arithmetic coding compress further to fractions).

As Olick wrote, store colors as difference to parent with some quantization. Process of quantization is essentially lossy filtering.

Fd80f81596aa1cf809ceb1c2077e190b
0
rouncer 103 Apr 21, 2011 at 04:06

everyone seems to know more than me!!! ahhhh!!!