After the recent refinements, it's time for another short write-up, as the work has reached a stable state and is nearly ripe for release as part of the next Alpha later this month. Beware: from here on it gets technical.
In this article I'm going to walk you through the construction of a complete voxel mesh hybrid structure including level of detail using an analog quadtree structure and an exemplary shape.
|A voxel mesh hybrid octree with leafs and branches visualized.|
|An oriented concave shape with a hole that we're going to store in the grid.|
|The grid resulting from rasterizing the shape. All vertices are at their default locations.|
Each cell acts both as voxel and point, holding a vertex with coordinates relative to the extents of the cell, so that -1 -1 -1 is the lower left front, 1 1 1 is the upper right back, and 0 0 0 is right in the center of the cell. Note how all vertices here are still at their default locations. This isn't strictly necessary, but helps to understand the implicit connectivity step that comes next.
Using a simple set of 16 binary marching cube connectivity rules (in 3D, it's 256 different combinations), we now build a dual mesh, connecting 4 adjacent cells at a time. Thanks to the connectivity rules, the mesh is guaranteed to be watertight, non-intersecting and two-manifold.
|The 16 connectivity rules for 2D grids. Orange spots are marked as inside the mesh.|
Furthermore, the marching cube has been extended with a bitmask marking inside cells, which helps to discern if a vertex is visible, and allows to easily find degenerate vertices. A degenerate vertex is any vertex with a valence < 2 (3D: degenerate if valence < 3 or ring loop hops counted != valence), unless that vertex is marked as inside.
|The resulting traced mesh|
As a next step (which can be done independent of connectivity), we move vertices closer to the surface. In this case, the vertices were hand-edited, but this could also be automated using a distance fields gradient data; if the data source is already a mesh, the vertices would copy representative positions.
|Vertices on the surface have been moved to the boundary, reconstructing the surface. Note the oversampling at four locations caused by the coarse resolution.|
Since the parent cells are of the same structure as the leaf nodes, we can mesh the tree at lower levels and get coarser meshes with can be used for level of detail and building collision meshes for physics simulation. Therefore, we now adjust the vertices at level 3 so that their edges resemble boundaries around the vertices of level 4:
|The level 4 cell structure and its implicit mesh|
|Level 3 cells superimposed over level 4, with outer vertices forming an implicit boundary mesh. The coarse resolution causes the concave sections to disappear early.|
|The resulting implicit mesh of level 3 cells.|
|The mesh at level 2.|
|The mesh at the lowest level.|
Voxel meshes can be edited with classical techniques available both to voxel and mesh editing, with differences in any task involving changes in edge connectivity, as with voxel mesh hybrids, connectivity is implicit: new triangles are only created when cells are removed or added. Variety in detail magnitude on a single level is possible up to a certain degree. Edge lengths may range from 0 to 2*sqrt(3)*(cell width).
Extrusion must be performed on the voxel level, with edge lengths dependent on how close vertices are to cell boundaries.
Subdivision must be performed uniformly, subdividing all cells to a higher level, testing against the vertex ring to decide where cells need to be created (only add new voxels whose boundaries collide with the lower level mesh volume), then projecting the new vertices to the surface.
So much for now. More to come.