Crawling Cubes Algorithm

November 26, 2010 General News 0 Comments

Huge breakthrough today!

I've written a new algorithm that I called the "Crawling Cubes Algorithm" that works extremely well and is ultra-efficient. Right now, it's looking about 4-5 times faster than my most heavily-optimized Marching Cubes, and roughly 20x faster than the vanilla Marching Cubes. Crawling Cubes is almost algorithmically optimal, meaning that it makes almost no unnecessary evaluations of the density field.

Crawling Cubes is specifically designed for metaball fields. It takes advantage of the fact that it can gain access to the positions of the metaballs. Using this information, Crawling Cubes is able to find a "starting point" cell on every disjoint isosurface. The algorithm then propagates over the surface until all cells containing the surface have been polygonized. Since any given cube that intersects an isosurface has perfect information about whether or not each of its neighbors intersects the isosurface, Crawling Cubes can propagate over the entire surface without wasting any evaluations on cells that don't intersect the surface.

To be fair, I didn't come up with this idea on my own. I found the idea on this page and quickly realized how brilliant it was and how perfectly it would work for metaball meshes.

The algorithm can now handle that 60k mesh of 30 metaballs that I mentioned in my last post in well under a single second. Furthermore, Crawling Cubes never causes topological artifacts. Unlike my previous hacky optimizations, this optimization preserves all topology (at the expense of generality, since it works only for metaball meshes).

I'm really, really excited about the development of this new algorithm and can't wait to put it to good use with ultra-high-quality procedural models!