Surface-Based Polygonization

August 2, 2011 General News 0 Comments

I've set aside the physics engine for a while to undertake another huge project - one that lies at the core of everything I do. My new goal: eliminate marching cubes. It's slow, it's memory intensive, it has no respect for surface topology, and it's not easy to make adaptive.

Instead, I'm building an algorithm that will polygonize a surface using....the surface! Just like my adapted version of marching cubes ('crawling cubes') crawls along the surface, so will my new algorithm. But, unlike MC, my algorithm will orient triangles such that they actually approximate the surface.

This is definitely going to be the most challenging algorithm I've ever designed, and I'm sure edge cases and slight things that I haven't considered yet are going to turn this into an absolute nightmare...but the reward for success is huge: polygonization quality and speed are absolutely essential to my entire engine, since all meshes will be converted at some point. MC is currently responsible for many of the annoyances that I see on a daily basis: poorly-calculated normals (due to sliver triangles), high poly count (due to the lack of adaptiveness), meshes with holes (due to lack of a bulletproof method for determining the isosurface bounds). A good surface-based algorithm will fix all of the above.

At any rate, I'm excited to have some initial results to share! It's not much, but you can see the formation of something that loosely resembles a surface! There's no adaptability yet, and the surface doesn't handle self-intersection (which I anticipate will be the most difficult part of the algorithm). Still, it's an encouraging start, and the surface quality clearly beats out anything MC could produce.