This week I reached a major milestone in my implementation of the new general meshing tech for our game in production, NOWHERE (alpha available for download), which is going to replace the previous implementation we used for sculpting and will do a better job at covering the different procedural modelling approaches the game requires. To commemorate the occasion, I did a little write-up. Beware: from here on it gets quite technical. I interspersed the article with a few screenshots from the work on the prototype. These are not screenshots of the game.
The mesh representation is mostly done, only smaller augmentations and performance optimizations remain, so I thought this would be a good moment to do a little summary of the new tech. I think I ended up with a little more than I initially hoped I could realistically get.
The result is surprisingly close to the crazy idea that I had in the beginning. I wanted a kind of hybrid that would combine the simplicity of dealing with volumes with the performance and precision of meshes, versatile enough to easily describe simple primitives, surfaces with low triangle count but also huge terrains of any genus. The topology should at all times implicitly form a clean closed surface without self intersections. It should be easily possible to generate different level of detail meshes from the same representation, and the entire structure must support interactive editing and lend itself well to tooling.
The work is almost completely based on the papers by Schaefer & Warren [1] (for the original marching cubes on a dual grid idea) and Lewiner et al [2] (for an efficient implementation of the dual grid). My original contribution would be a radical simplification of the meshing process aiming for both a finer level of control to facilitate manual editing and cleaner meshes without slivers.
Breakdown
The implementation consists of populating a data structure and generating a mesh from it.
You need only a simple hashtable-based sparse octree implementation; Each cell stores (at minimum) the relative coordinate of a vertex that will or will not become a defining point on the surface. There are no leaves outside the volume, so every leaf is implicitly inside or on the boundary of a volume. You can easily add more attributes to the cells such as normals or material information, that will be used in the meshing process.
As the octree cell implicitly already defines an origin and scale through its morton encoded location, the coordinate can be of low precision; three signed 8-bit components would suffice. I'm using 16-bit precision at the moment.
These vertices form a dual grid, on which the actual mesh will be generated.
The mesh generator then uses a simple binary marching cube process to decide whether triangles need to be generated for each dual grid of eight adjacent vertices (If neighboring leaves aren't present, that's no problem; since those points are outside anyway, the MC doesn't need them for building the triangles). The endpoints of the triangles will always be at the vertex locations, so you have explicit control over surface features.
The simplest structures you can build with this in a single branch (keeping all vertices at their default center positions) are a flat triangle with two sides (tag three adjacent cells as inside), a 2-sided quad (tag four adjacent cells), a tetrahedron (tag four adjacent cells in the pattern 0b000,0b110,0b101,0b011), and a 12-sided cube (tag eight adjacent cells).
To build a perfect sphere, you can tag all cells within a desired radius as inside, and push the vertices of cells enclosing a piece of the surface to the surface of the sphere ("shrinkwrapping").
For very complex surfaces, you can also fill the octree using a CSG tree describing a signed distance field, and push the vertices along the distance fields gradient to the surface for a smooth regular surface.
Drawbacks & Yet Unexplored Avenues
I don't have a good scheme for UV mapping yet. Using trilinear texturing and weights at the vertices to control the blending, it should be possible to describe most terrains. One could also store mapping information at the axes (see implementation notes). There's also an interesting paper on TileTree texturing by Lefebvre & Dachsbacher [3] which offers a fine grade of control but needs to be adapted to volumetric meshes; a single tree should be enough, and we have enough information to not need ray casting as the paper suggests.
Normals aren't smoothed, and vertices aren't merged into index buffers. This could all be done as a third step; But smooth normals could also be saved with the cell vertices, and would have to be re-calculated for the cell and adjacent cells on change, which is not particularly difficult (see implementation notes).
Level of detail (LOD) isn't done yet. Sparse octrees support LOD easily, as branches can always sum up what's going on in the leaves, and this tree is no different. If the mesher does not traverse deeper than a preset LOD level, the mesh will be more coarse, but still regular. If the tree is to be partially LOD'ed, the dual cells connecting the 1-ring neighbors of zones would have to be handled separately, but this is also easy to figure out.
Partial mesh updates are not done yet. The latest plan is to split up large trees into zones with separate vertex buffers, and to recalculate a complete zone on change, as per-cell updates cause all kinds of logical fragmentation problems.
Threading & GPU support: both tree population and the binary MC meshing can be neatly parallelized if desired, as work can be discretely split up along the branches' octants.
Implementation Notes
To speed up the meshing and allow the enumeration of each dual grid body, the octree needs a second set of values for the hashtable, which represent the axes or corners of the octree cells. An octree axis conveniently always maps to a single dual grid cell, and is used to efficiently retrieve the edges connecting neighboring cell vertices. To achieve this, an axis stores the level of the deepest octree cell that supplies a vertex to the grid volume.
The basic implementation is very much the same as in Lewiner et al [2], you can follow that one to the letter, and Lewiner has source code on his website for comparison (there's a typo in the paper so you'll need it).
Thanks
Thanks to my wife and co-designer Sylvia Ritter for her endurance, patience and trust.
Thanks to Fabian Giesen for his magnificient blog, exhaustive rubberducking and hours of unpaid
consulting.
Thanks to Alex Evans, Doug Binks, Tenebrous, Nick Porcino, Sean Barrett, Jon Olick, Nathan Reed and many other Twitteristas for advice, hints, positive responses and oh so many favs.
Lastly, thanks to Tom Forsyth who told me not to cross the streams, because I totally did, and it worked!
Sources
[1] Schaefer & Warren, Dual Marching Cubes (2004), slides:
http://www.cs.berkeley.edu/~jrs/meshs08/present/Andrews.pdf
[2] Lewiner et al, Fast generation of pointerless octree duals (2010)
http://www.matmidia.mat.puc-rio.br/tomlew/pdfs/fastdualoctree_sgp.pdf
[3] Lefebvre & Dachsbacher, TileTrees (2007)
http://www-sop.inria.fr/reves/Basilic/2007/LD07/LD07.pdf
