Voxel mesh optimization

Hi!

Alright, simplifying box meshes. There is a very famous command line tool by Hang Si, called Tetgen. It is usually used to build tetrahedralizations from polygonal meshes. You could simply throw in your high quality meshes and this tool would merge coplanar faces and would produce Delaunay triangularizations of the rest. Among other things it can write out the new generated faces. Probably you can specify to only output boundary faces. If not, you can do something similar to the classical stencil shadow stuff to extract the boundary faces. You know, the part where you compute the silhouette of an object. Let’s have a look at some pseudocode.

list<cubeface> hull; // list of potential boundary faces
for each Tetrahedron do
for each Face f do
if ( !hull.contains(f) ) hull.add(f); else hull.remove(f);

This would give you all faces of the hull, since the hull faces are touched once and all other faces (inside the tetmesh) are touched twice. The second touch removes them from the hull candidate list.
You would have less to code for yourself to get this working and it would be one possible solution for dynamic updates of your world mesh.

If your world is static you can do this stuff with 3ds max or cinema 4D etc. They have mesh simplification algorithms included.

Your only problem is that you have to remove the internal faces. If you would only have the hull (which you could also extract with the aforementioned pseudocode stuff) and some neighborhood information, you could use standard stuff, like edge collapse, to update dynamic scenes. There are many mesh simplification algorithms out there and I would highly recommend to use a library for that.

Well, Tetgen is pretty easy to use. The source is available as well, so you wouldn’t even have to write your geometry to file, run Tetgen and read in the files containing the results.

Whether to go in this direction or not pretty much depends on your requirements. Can you give use more detail on how many boxes will end up in your scene? Which resolution (number of tiny boxes) will your meshes have? Makes a hierarchical approach for the representation of the geometry sense in your case? (Can they locally deform, does the color change, etc.)