Thursday, March 7, 2013

Marching Cubes tricks-semi-advanced Info

Some speed optimisation and accuracy considerations for marching cubes:

it's amazing how brief and effective a simple implementation of marching cubes is. only about 100 lines apart from the tables, so easy to read! It just calculates an equation on points, checks the values between points, for all edges of a cube, and the data table returns what triangles that corresponds to. it's literally 2 or 3 loops and some lists of points and lines and a data table.

If you have a basic implementation of marching cubes, you will find that each triangle is separate from each other and has its own vertices, so any mesh with 10,000 triangles will represent 30,000 vertices. a slightly optimised code would produce about 11,000 vertices instead.

Another consideration is that the simple versions calculate 12 edges for each cube, and when you add all the cubes together, it's about 4 times more edges than you really need to process.

So- to divide that part of the code processing by a factor of 4, you should use only the 3 edges of the cube on the front lower left corner, March through all the cubes and store all their values in an array, and then you will have all the edges by doing only 3 edges  instead of 12.

to read edges from the new array, every time you have the cube and need to send 12 of them to the triangles data table,you simply get the right array values for the cubes adjacent.

to calculate the points in the 1st place, from which the edge-ISOsurface intersection values are assessed, most marching cubes just walk through all the points and put them in an array.

Some marching cubes also do octree segmentation divisions of the space and only check the points and edges inside quadrants of the space which clearly contain the surface., and areas that are far from the ISO level are thrown out.

You can also just not bother to do any edges and cubes and marching, for any cubes of which 1 point is really far from the ISO value. get the 1st cube corner, check it's value, and leave it out if it's far away from the surface. you can even rewrite all the points , as they are calculated at 1st, that are far from the ISO, to a specific value so that all the cubes to be left out have that specific value on any of their points.


Here's a little trick about snapping very small triangles and throwing them out. At the linear interpolation stage of the edges, just make points are very close to cube corners equals to keep corners like as explained in the Snap MC implementation-this literally took 2 lines to change the triangles, and another 3 lines to omit triangles that are flattened.


Another consideration is