Volumetric methods in mesh processing

Tao Ju, 2007

Polygonal models (or meshes) are one of the most popular computer representations of 3D objects, and have been widely used in design, visualization, animation and interaction. However, direct operations on meshes are often time and space consuming, and often introduce geometric or topological errors. On the other hand, voxel-based volumes allow efficient operations with geometric and topological guarantees. Here we explore the use of voxels in performing fast and robust mesh construction and processing.

Our work is focused on the use of multi-resolution voxel grids (i.e., octree) for fast and robust mesh operations. We are particularly interested in mesh construction from volumes and volume-based mesh repair.

Iso-surfacing methods

Convex contouring [Visual Computer 2003]: A key step in volume-based mesh processing is to be able to create a closed polygonal mesh from a volume grid. One of the most popular methods for this purpose is the Marching Cubes [Lorensen and Clein 1987], which creates triangles within each uniform grid cell that intersects the iso-surface. We proposed an extension to Marching Cubes to further guarantee that the triangles generated within each cube always forms a convex space . The new method, called Convex Contouring, allows fast collision detection with the iso-surface that is essential in applications such as games.

Dual Contouring [SIGGRAPH 2002]: A common drawback of primal contouring methods, including Marching Cubes and Convex Contouring, is that they tend to produce blobby shapes and extension of these methods onto non-uniform, octree grid is difficult and problematic. We proposed a new method, Dual Contouring, which used a simple concept of forming surfaces that lie dual to edges on the grid exhibiting a sign change. DC was able to create closed surfaces for arbitrary octree grids and even with multiple material types. In addition, DC is capable of reproducing sharp edges and corners from Hermite volumes. Since its introduction, the DC method has been widely used and studied. A number of extensions have been proposed, including our own work on eliminating geometric intersections [PG 2005] and maintaining topological manifoldness during octree-based simplification [TVCG 2007].

Robust Mesh Repair

Fixing geometric errors [SIGGRAPH 2004]: Polygonal models obtained from different means, such as 3D scanning or commercial design softwares, typically have errors in the forms of holes, self-intersections and hanging pieces. However, applications such as finite element analysis and fast proto-typing all require a closed mesh as input. Combining memory-less mesh-to-octree conversion and octree-based repair with Dual Contouring for reconstruction, we are able to efficiently repair an arbitrary polygonal model (e.g., a bag of triangles), maybe gigantic in size, so that the repaired model is guaranteed to be closed. The repair operation would also preserve surface features such as sharp edges and corners.

Fixing topological errors [SIGGRAPH 2007]: While a mesh can be free of geometric errors, it can still contain noisy features such as handles, tunnels, cavities or islands. The existence of these topological errors can significantly hinder mesh processing tasks such as parameterization and simplification, as well as computations using meshes such as finite element analysis. To remove such errors, we proposed a user-guided framework that allows the user to provide the desired topology of a model through sketching and automatically modifies the input model to be consistent with the provided topology. This method is based on our previous skeleton-based handle-removal method [TVCG 2007], and permits accurate removal of topological noise while preservation of both topological and geometric features.

  • Dual contouring of hermite data
    Paper presentation at ACM SIGGRAPH (by Scott Schaefer), San Antonio, August 2002 (Download PPT 7MB)

  • Robust repair of polygonal models
    Paper presentation at ACM SIGGRAPH, Los Angeles, August 2004 (Download PPT 8MB)

Comments or suggestions: taoju at cs.wustl.edu