Cubical Marching Squares: On Adaptively Preserving Consistent Topology and Sharp Features for Realtime Isosurfacing

This dissertation presents a new method for surface extraction from volume data which generates surface adaptively without crack patch- ing, maintains consistent topology, preserves sharp features, and pre- serves the property of inter-cell independency. The presented ap- proach is based on the marching cubes algorithm, a popular method to convert volumetric data to polygonal meshes. The original march- ing cubes algorithm suffers from problems of cracks in adaptive reso- lution, inability to preserve sharp features, and topological inconsis- tency. Most of marching cubes variants only focus on one or some of these problems. Although these techniques could be combined to solve these problems altogether, such a combination might not be straightforward. Moreover, some feature-preserving variants intro- duce an additional problem, inter-cell dependency. The presented method provides a relatively simple and easy-to-implement solution to all these problems by converting 3D marching cubes into 2D cubical marching squares, resolving topology ambiguity with sharp features and eliminating inter-cell dependency by sampling additional sharp features on faces. Comparisons of our algorithm with other marching cubes variants demonstrate the effectiveness of presented method on various applications.1 Introduction 1 2 Background 7 2.1 Marching Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Marching Cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Related Work 13 3.1 Adaptive resolution . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Sharp features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4 Inter-cell independence . . . . . . . . . . . . . . . . . . . . . . . . 16 3.5 Other related work . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.6 Comparison with marching cubes variations . . . . . . . . . . . . 21 4 Preliminary results 23 4.1 Acquisition of samples from polygonal mesh . . . . . . . . . . . . 23 4.2 Adaptive Extended Marching Cubes . . . . . . . . . . . . . . . . 25 4.3 Sampling sharp features on faces . . . . . . . . . . . . . . . . . . 29 4.4 Topology determination . . . . . . . . . . . . . . . . . . . . . . . 31 5 Solving Problems in 2D 39 5.1 Handling Sharp Features . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Handling Topology Correctness . . . . . . . . . . . . . . . . . . . 42 5.3 Adaptive Resolution . . . . . . . . . . . . . . . . . . . . . . . . . 46 6 Cubical Marching Squares: Isosurfacing in 3D 51 6.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.2 Algorithm overview . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.3 Segment generation for faces in 2D . . . . . . . . . . . . . . . . . 55 6.4 Surface extraction for cells in 3D . . . . . . . . . . . . . . . . . . 59 7 Sculpting: Boolean Operations 61 7.1 Storing Volume Data . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.2 Boolean Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.3 Rendering Volume Data . . . . . . . . . . . . . . . . . . . . . . . 67 7.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 8 Results 73 8.1 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8.2 CSG and LOD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 8.3 Remeshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 9 Conclusion and Future Work 79 A Feature Refinement 81 A.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 A.2 Feature-Sensitive volumetric sculpting on adaptive isosurface . . . 83 A.2.1 Problems of editing sharp features . . . . . . . . . . . . . . 83 A.2.2 Feature refinement strategy . . . . . . . . . . . . . . . . . 84 A.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 A.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 B Additional simulation results 89 B.1 Single object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 B.2 Multiple objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 C Publications 99 C.1 Journal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 C.2 Conference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 References 10