The power crust

ABSTRACT

The power crust is a construction which takes a sample of points from the surface of a three-dimensional object and produces a surface mesh and an approximate medial axis. The approach is to first approximate the medial axis transform (MAT) of the object. We then use an inverse transform to produce the surface representation from the MAT.

This idea leads to a simple algorithm with theoretical guarantees comparable to those of other surface reconstruction and medial axis approximation algorithms. It also comes with a guarantee that does not depend in any way on the quality of the input point sample. Any input gives an output surface which is the `watertight' boundary of a three-dimensional polyhedral solid: the solid described by the approximate MAT. This unconditional guarantee makes the algorithm quite robust and eliminates the polygonalization, hole-filling or manifold extraction post-processing steps required in previous surface reconstruction algorithms.

In this paper, we use the theory to develop a power crust implementation which is indeed robust for realistic and even difficult samples. We describe the careful design of a key subroutine which labels parts of the MAT as inside or outside of the object, easy in theory but non-trivial in practice. We find that we can handle areas in which the input sampling is scanty or noisy by simply discarding the unreliable parts of the MAT approximation. We demonstrate good empirical results on inputs including models with sharp corners, sparse and unevenly distributed point samples, holes, and noise, both natural and synthetic.

We also demonstrate some simple extensions: intentionally leaving holes where there is no data, producing approximate offset surfaces, and simplifying the approximate MAT in a principled way to preserve stable features.

REFERENCES

• 1: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete and Computational Geometry 22, pp. 481- 504, (1999).
• 2: Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
• 3: N. Amenta, S. Choi and R. Kolluri. The power crust, unions of balls and the medial axis transform, Int. J. Computational Geometry and its" Applications, to appear.
• 4: N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336207]
• 5: Dominique Attali , Annick Montanvert, Computing and simplifying 2D and 3D continuous skeletons, Computer Vision and Image Understanding, v.67 n.3, p.261-273, Sept. 1997 [doi>10.1006/cviu.1997.0536]
• 6: D. Attali and J-O. Lachaud. Delaunay constrained iso-surface, skeleton extraction and noise removal, Int. J.Computational Geometry and its" Applications, to appear.
• 7: J. August, A. Tannenbaum, and S.W. Zucker. On the evolution of the skeleton, International Conference on Computer Vision (1999).
• 8: Fausto Bernardini , Joshua Mittleman , Holly Rushmeier , Cláudio Silva , Gabriel Taubin, The Ball-Pivoting Algorithm for Surface Reconstruction, IEEE Transactions on Visualization and Computer Graphics, v.5 n.4, p.349-359, October 1999 [doi>10.1109/2945.817351]
• 9: F. Bernardini, H. Rushmeier. Strategies for registering range images from unknown camera positions. Proc. of SPIE Three- Dimensional Image Capture and Applications II1, 2000.
• 10: Robert Blanding , Cole Brooking , Mark Ganter , Duane Storti, A skeletal-based solid editor, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.141-150, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304026]
• 11: Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984 [doi>10.1145/357346.357349]
• 12: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 13: J. W. Bran&. Describing a solid with the three-dimensional skeleton, Proc. the International Society for Optical Engineering, vol. 1830, Curves and Surfaces in Computer Vision and Graphics III, SPIE, Boston Mass, 1992.
• 14: H.I. Choi, S.W. Choi and H.P. Moon. Mathematical theory of medial axis transform, Pacific Journal of Mathematics 181( 1 ), pp. 57-88, (1997).
• 15: Howie Choset, Sensor based motion planning: the hierarchical generalized Voronoi graph, California Institute of Technology, Pasadena, CA, 1996
• 16: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 17: Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304030]
• 18: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 19: T. Dey, personal communication.
• 20: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 21: Herbert Edelsbrunner, The union of balls and its dual shape, Proceedings of the ninth annual symposium on Computational geometry, p.218-231, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161139]
• 22: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 23: M. Etzion and A. Rappoport. Computing the Voronoi diagram of a 3-D polyhedron by separate computation of its symbolic and geometric parts. Solid Modeling '99
• 24: M. Etzion and A. Rappoport. Computing Voronoi skeletons of a 3D polyhedron by space subdivision, Technical Report, Hebrew University, 1999.
• 25: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 26: Christopher Gold, Crust and anti-crust: a one-step boundary and skeleton extraction algorithm, Proceedings of the fifteenth annual symposium on Computational geometry, p.189-196, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304971]
• 27: M. Gopi and S. Krishnma. A fast and efficient projection based approach for surface reconstruction. International Journal of High Performance Computer Graphics', Multimedia and Visualization, to appear.
• 28: L. Guibas, R. Holleman and L. E. Kavraki. A probabilistic roadmap planner tbr flexible objects with a workspace medialaxis-based sampling approach, in IEEE/RSJ Proc. of the Int. Conf. on Intelligent Robots" and Systems (1999).
• 29: L. Guibas, D. Knuth and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica 7 (1992), pp. 381-413.
• 30: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 31: C. Hoffman, How to construct the skeleton of CSG objects, in The Mathematics of Surfaces. IVA. Bowyer and J. Davenport, Eds., Oxford University Press, 1990.
• 32: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 33: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 34: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 35: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 36: VJ. Milenkovic. Robust construction of the Voronoi diagram of a polyhedron, 5th Canadian Conference on Computational Geometry (1993) pp. 473--478.
• 37: R.L. Ogniewicz. Skeleton-space: A multiscale shape description combining region and boundary information, Proceedings of Computer I,version and Pattern Recognition (1994) pp. 746-751.
• 38: S.M. Pizer, C.A. Burbeck, J.M. Coggins, D.S. Fritsch and B.S Morse. Object shape before boundary shape: Scale-space medial axes, Journal of Mathematics Imaging and I, qsion, 4:3, (1994), pp. 303-313.
• 39: George D. Stetten , Stephen M. Pizer, Automated Identification and Measurement of Objects via Populations of Medial Primitives, with Application to Real Time 3D Echocardiography, Proceedings of the 16th International Conference on Information Processing in Medical Imaging, p.84-97, June 28-July 02, 1999
• 40: V. Ranjan and A. Fournier. Matching and interpolation of shapes using unions of circles, Computer Graphics" Forum, 15(3), pp. 129---142, (1996).
• 41: Damian J. Sheehy , Cecil G. Armstrong , Desmond J. Robinson, Shape Description By Medial Surface Construction, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.62-72, March 1996 [doi>10.1109/2945.489387]
• 42: A. Sheffer, M. Etzion, A. Rappoport and M. Bercovier. Hexahedral mesh generation using the embedded Voronoi graph, Technical Report, Hebrew University (1999).
• 43: Evan C. Sherbrooke , Nicholas M. Patrikalakis , Erik Brisson, An Algorithm for the Medial Axis Transform of 3D Polyhedral Solids, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.44-61, March 1996 [doi>10.1109/2945.489386]
• 44: J.R. Shewchuk, personal communication.
• 45: Duane W. Storti , George M. Turkiyyah , Mark A. Ganter , Chek T. Lim , Derek M. Stal, Skeleton-based modeling operations on solids, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.141-154, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267771]
• 46: M. Teichman and S. Teller. Assisted articulation of closed polygonal models, Proc. 9th Eurographics Workshop on Animation and Simulation, (1998).
• 47: G.M. Turkiyyah, D.W.Storti, M. Ganter, H. Chen and M. Vimawala. An accelerated triangulation method for computing the skeletons of free-form solid models, Computer Aided Design, 29:1 (1997) pp. 5-19.
• 48: S.P. Uselton. Three dimensional surface descriptions from sensed data, Proc. of the 16th Hawaii International Conference on System Sciences', vol. 2, (1983) pp. 387-385.
• 49: Pamela Jean Vermeer, Medial axis transform to boundary representation conversion, Purdue University, West Lafayette, IN, 1994
• 50: J. Vleugels and M. Overmars. Approximating generalized Voronoi diagrams in any dimension, Int. Jour Computational Geometry and its Applications, (1998).
• 51: Steven A. Wilmarth , Nancy M. Amato , Peter F. Stiller, Motion planning for a rigid body using random networks on the medial axis of the free space, Proceedings of the fifteenth annual symposium on Computational geometry, p.173-180, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304967]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  J. Computer Applications
  J.1 ADMINISTRATIVE DATA PROCESSING
      Subjects: Manufacturing

General Terms:
Algorithms, Design, Management, Performance, Theory