an interesting Voxel Compression scheme..

[leopardpm]

One of the problems with voxel models is that they take up vast amounts of space. For instance, the MagicaVoxel (.VOX) and Ken Silvermans file formats are basically 3 dimensional arrays of either 4 byte RGBA colors, or palettized of the same. This means that the maximum sized .VOX file is (127 x 127 x 127 =) 2,048,383 pixels, meaning 2 mb if palettized for ONE frame of a voxel animation... I have thought of different ways to compress this, one being with the Voxel List Method which can reduce the file size by quite a bit. But, still much larger than a 2D sprite file with 8 rotations.

I like to think of voxel models as 'layer' of 2D images, 127 layers of 127 x 127 pix images in the case of the above magicaVoxel file size. This lends itself to using PNG compression, etc, on each of those layers. But I don't like that method because you need to use a library to access the PNG encode/decode routines. I was thinking today that there is another thing about these layers which might make an entirely different compression scheme to be used.

Each layer essential has a 'slice' of the model in question, an 'empty' slice that looks like something like a circle or some other fully enclosed shape. Here are some example slices:
feet or legs
torso
torso with arms
head

so, my idea is... for each slice, start off at any pixel, save its x/y location and palette color, then OFFSET from that location around each shape. The offset would be a 3 bit variable which covers the 8 possible directions of the next pixel (n,w,s,e,nw,sw,ne,se). So, all the empty space is automatically ignored, and each pixel only takes up (3 bits for direction, 8 bits for palette index) 11 bits! I haven't written any code yet, but I think this compression method will probably be the smallest that I could come up with (of course, the directions and colors could be in separate blocks and then both could be easily further compressed with RLE...). Just wanted to throw this out there for anyone who might be interested... I have not yet delved into what the routine would look like to 'encode' a layer... it might be very hard.. but as long as the 'outline' is only 1 voxel thick and all voxels in a shape are touching either a corner or side.

[sean_vn]

Hash tables are usually the answer to this sort of thing. It's not difficult to make a hash table that accepts 3 input parameters. hash3D(x,y,z)=hash1D(hash1D(hash1D(x)+y)+z) or whatever. Or a Bloom filter based on 3D hashes for space saving.

[leopardpm]

Hash tables are usually the answer to this sort of thing. It's not difficult to make a hash table that accepts 3 input parameters. hash3D(x,y,z)=hash1D(hash1D(hash1D(x)+y)+z) or whatever. Or a Bloom filter based on 3D hashes for space saving.

you are way beyond me... I understand a 'hashcode' for error checking, but i have no idea what a hash table is or how it could be used for compression... i will google now...

[Aethelstan]

each pixel only takes up (3 bits for direction, 8 bits for palette index) 11 bits!

I don't know much about hashtables, too, but I like your idea. It's like saving path (assuming that it has no branches/leafs - otherwise it would be more complicated to represent the drawing). Moreover, if the freestyle drawing is made with just one, selected color, you can save it only once with the 'path' you create (not with every pixel). Of course this method will have many disadvantages and may not be good enough to compress data of pictures with many colors and/or small areas. It should work best for pictures created by-hand. Still I think it has a good potential.

[leopardpm]

each pixel only takes up (3 bits for direction, 8 bits for palette index) 11 bits!

I don't know much about hashtables, too, but I like your idea. It's like saving path (assuming that it has no branches/leafs - otherwise it would be more complicated to represent the drawing).

Exactly! It saves a 'path' of how to draw an enclosed shape with one go. I always seem to have problems describing what I am thinking and your vision is much more succinct... a path!

Moreover, if the freestyle drawing is made with just one, selected color, you can save it only once with the 'path' you create (not with every pixel). Of course this method will have many disadvantages and may not be good enough to compress data of pictures with many colors and/or small areas. It should work best for pictures created by-hand. Still I think it has a good potential.

yes, too limiting to just use one color - but what you describe can be used with multiple colors as well - it is RLE compression: storing a string of same colors or patterns of colors and the 'run-length' of the path that is that color. It works great for images which have limited colors (not pictures) and which has parts of the image which are the same color. Next to palettizing an image, it is probably the easiest compression scheme to incorporate and gives great results.

After reading about hash tables, I am still confused as to how they work and how they would be put to use in a compression scheme... too complicated for my brain!

[counting_pine]

I'd be surprised if Ken Silverman hadn't put a lot of thought into his file format. I thought I remembered reading that it used RLE compression in one axis..
Either way, not every set of voxels can be compressed, and there will always be configurations where the size cannot be reduced.

Using a stack of 2D cross-sections sounds quite inefficient - I presume that with a 3D object you usually only want to store the surface colours, so each 2D image will basically be storing a contour, which most image formats aren't designed to do. Also, it won't be easy to gain any compression from the similarities between adjacent cross-sections.

Octrees might be an efficient way to store voxel position data. Split up your model into eight subcubes (2x2x2), and record whether all the voxels in each subcube are set, or all of them are unset, or some of them are set. A subcube with all or no voxels set needs no further data stored, and a subcube with some voxels set is split up recursively into smaller subcubes.
Once you have the positions of each voxel, you'd need to store colour information separately. Only colours for set voxels need to be stored, and additional compression could probably be used there.

[leopardpm]

I'd be surprised if Ken Silverman hadn't put a lot of thought into his file format. I thought I remembered reading that it used RLE compression in one axis..

yes, Ken is/was brilliant... but I import his files with no RLE going on, at least the files created by is voxelap program which voxelizes a 3D mesh (.OBJ i think)

Using a stack of 2D cross-sections sounds quite inefficient - I presume that with a 3D object you usually only want to store the surface colours, so each 2D image will basically be storing a contour, which most image formats aren't designed to do. Also, it won't be easy to gain any compression from the similarities between adjacent cross-sections.

yes, it isn't very efficient altogether - mostly because of what you mention regarding having no ability to compress based on similarities between layers (cross-sections). The 'Voxel List' method just stores the x,y,z,clr value for each voxel (excluding clear ones), and then this can be further refined by grouping all the voxels on the same axis (usually z) which groups them by layer. Then group them by either same x or y and you end up with rows or columns of voxels with only 2 bytes - 1 for x position and 1 for color index. Still that is 16 bits compared to my proposed 11 bits for the same information... but both of these are 'simple' compression schemes (which is what I am capable of...).

Octrees might be an efficient way to store voxel position data.

yup, I looked into octrees early on as they are a very efficient method of storing voxel data, in fact they are used alot in medical voxel image storage... but my attempts at programming the octree creation and transversing routines were failures, recursion kills me... I did manage to do a 2D version of an octree - the quadtree for 2d images, and it was impressive. Both octrees and quadtrees essentially manage to store the position of a pixel/voxel without storing the empty space inbetween and provide a relatively fast method of retrieving any particular pixel/voxel... the encoding takes much longer, of course...[/quote]