Unconstrained isosurface extraction on arbitrary octrees

ABSTRACT

This paper presents a novel algorithm for generating a watertight level-set from an octree. We show that the levelset can be efficiently extracted regardless of the topology of the octree or the values assigned to the vertices. The key idea behind our approach is the definition of a set of binary edge-trees derived from the octree's topology. We show that the edge-trees can be used define the positions of the isovalue-crossings in a consistent fashion and to resolve inconsistencies that may arise when a single edge has multiple isovalue-crossings. Using the edge-trees, we show that a provably watertight mesh can be extracted from the octree without necessitating the refinement of nodes or modification of their values.

REFERENCES

• 1: Gill Barequet , Matthew Dickerson , David Eppstein, On triangulating three-dimensional polygons, Computational Geometry: Theory and Applications, v.10 n.3, p.155-170, June 1, 1998 [doi>10.1016/S0925-7721(98)00005-4 ]
• 2: Adam W. Bargteil , Tolga G. Goktekin , James F. O'brien , John A. Strain, A semi-Lagrangian contouring method for fluid simulation, ACM Transactions on Graphics (TOG), v.25 n.1, p.19-38, January 2006 [doi>10.1145/1122501.1122503]
• 3: J. Bloomenthal, Polygonization of implicit surfaces, Computer Aided Geometric Design, v.5 n.4, p.341-355, Nov. 1988 [doi>10.1016/0167-8396(88)90013-1 ]
• 4: Gill Barequet , Micha Sharir, Filling gaps in the boundary of a polyhedron, Computer Aided Geometric Design, v.12 n.2, p.207-229, March 1995 [doi>10.1016/0167-8396(94)00011-G ]
• 5: {HWC*05} Ho C., Wu F., Chen B., Chuang Y., Ouhyoung M.: Cubical marching squares: Adaptive feature preserving surface extraction from volume data. In Proceedings of EUROGRAPHICS 2005 (2005), pp. 537--545.
• 6: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 7: {JU06} Ju T., Udeshi T.: Intersection-free contouring of an octree grid. In Proceedings of Pacific Graphics (2006).
• 8: Michael Kazhdan , Matthew Bolitho , Hugues Hoppe, Poisson surface reconstruction, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 9: Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001 [doi>10.1145/383259.383265]
• 10: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 11: Frank Losasso , Frédéric Gibou , Ron Fedkiw, Simulating water and smoke with an octree data structure, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 12: Heinrich Müller , Michael Stark, Adaptive generation of surfaces in volume data, The Visual Computer: International Journal of Computer Graphics, v.9 n.4, p.182-199, Jan. 1993 [doi>10.1007/BF01901723]
• 13: {MY80} Meeks W., Yau S.: Topology of three dimensional manifolds and the embedding problems in minimal surface theory. The Annals of Mathematics 112, 3 (November 1980), 441--484.
• 14: {MY82} Meeks W., Yau S.: The existence of embedded minimal surfaces and the problem of uniqueness. Mathematische Zeitschrift 179, 2 (June 1982), 151--168.
• 15: Gregory M. Nielson , Bernd Hamann, The asymptotic decider: resolving the ambiguity in marching cubes, Proceedings of the 2nd conference on Visualization '91, October 22-25, 1991, San Diego, California
• 16: Yutaka Ohtake , Alexander Belyaev , Marc Alexa , Greg Turk , Hans-Peter Seidel, Multi-level partition of unity implicits, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 17: M. Ohlberger , M. Rumpf, Hierarchical and adaptive visualization on nested grids, Computing, v.59 n.4, p.365-385, 1997 [doi>10.1007/BF02684418]
• 18: Raj Shekhar , Elias Fayyad , Roni Yagel , J. Fredrick Cornhill, Octree-based decimation of marching cubes surfaces, Proceedings of the 7th conference on Visualization '96, p.335-ff., October 28-29, 1996, San Francisco, California, United States
• 19: Scott Schaefer , Tao Ju , Joe Warren, Manifold Dual Contouring, IEEE Transactions on Visualization and Computer Graphics, v.13 n.3, p.610-619, May 2007 [doi>10.1109/TVCG.2007.1012]
• 20: Scott Schaefer , Joe Warren, Dual Marching Cubes: Primal Contouring of Dual Grids, Proceedings of the Computer Graphics and Applications, 12th Pacific Conference, p.70-76, October 06-08, 2004
• 21: {SZK95} Shu R., Zhou C., Kankanhalli M.: Adaptive marching cubes. The Visual Computer 11 (1995), 202--217.
• 22: Gokul Varadhan , Shankar Krishnan , TVN Sriram , Dinesh Manocha, Topology preserving surface extraction using adaptive subdivision, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057464]
• 23: Gokul Varadhan , Shankar Krishnan , Liangjun Zhang , Dinesh Manocha, Reliable implicit surface polygonization using visibility mapping, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 24: Jane Wilhelms , Allen Van Gelder, Octrees for faster isosurface generation, ACM Transactions on Graphics (TOG), v.11 n.3, p.201-227, July 1992 [doi>10.1145/130881.130882]
• 25: {WKE99} Westermann R., Kobbelt L., Ertl T.: Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces. The Visual Computer 15 (1999), 100--111.
• 26: {WMW86} Wyvill G., McPheeters C., Wyvill B.: Data structures for soft objects. The Visual Computer 2 (1986), 227--234.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling