Zippered polygon meshes from range images

ABSTRACT

Range imaging offers an inexpensive and accurate means for digitizing the shape of three-dimensional objects. Because most objects self occlude, no single range image suffices to describe the entire object. We present a method for combining a collection of range images into a single polygonal mesh that completely describes an object to the extent that it is visible from the outside.The steps in our method are: 1) align the meshes with each other using a modified iterated closest-point algorithm, 2) zipper together adjacent meshes to form a continuous surface that correctly captures the topology of the object, and 3) compute local weighted averages of surface positions on all meshes to form a consensus surface geometry.Our system differs from previous approaches in that it is incremental; scans are acquired and combined one at a time. This approach allows us to acquire and combine large numbers of scans with minimal storage overhead. Our largest models contain up to 360,000 triangles. All the steps needed to digitize an object that requires up to 10 range scans can be performed using our system with five minutes of user interaction and a few hours of compute time. We show two models created using our method with range data from a commercial rangefinder that employs laser stripe technology.

REFERENCES

• Bern 92: Bern, Marshall and David Eppstein, "Mesh Generation and Optimal Triangulation," Technical Report P92-00047, Xerox Palo Alto Research Center, March 1992.
• Besl 92: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791]
• Boissonnat 84: 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]
• Businski 92: Businski, M., A. Levine and W. H. Stevenson, "Performance Characteristics of Range Sensors Utilizing Optical Triangulation," IEEE National Aerospace and Electronics Confer-ence, Vol. 3 (1992), pp. 1230-1236.
• Champleboux 92: Champleboux, Guillaume, Stephane Lavallee, Richard Szeliski and Lionel Brunie, "From Accurate Range Imaging Sensor Calibration to Accurate Model-Based 3-D Object Localiza-tion," Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Champaign, Illinois, June 15-20, 1992, pp. 83-89.
• Chen 92: Yang Chen , Gérard Medioni, Object modelling by registration of multiple range images, Image and Vision Computing, v.10 n.3, p.145-155, April 1992 [doi>10.1016/0262-8856(92)90066-C]
• Edelsbrunner 92: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, Proceedings of the 1992 workshop on Volume visualization, p.75-82, October 19-20, 1992, Boston, Massachusetts, United States [doi>10.1145/147130.147153]
• Hoppe 92: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.71-78, July 1992
• Hoppe 93: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
• Horn 87: Horn, Berthold K. P., "Closed-Form Solution of Absolute Orientation Using Unit Quaternions," Journal of the Optical Society of America. A, Vol. 4, No. 4 (April 1987), pp. 629-642.
• Schroeder 92: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• Soucy 92: Soucy, Marc and Denis Laurendeau, "Multi-Resolution Surface Modeling from Multiple Range Views," Proceedings of the IEEE Computer Society Conference on Computer Vision and Pat-tern Recognition, Champaign, Illinois, June 15-20, 1992, pp. 348- 353.
• Turk 92: Greg Turk, Re-tiling polygonal surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.55-64, July 1992
• Wada 93: Wada, Nobuhiko, Hiroshi Toriyama, Hiromi T. Tanaka and Fumio Kishino, "Reconstruction of an Object Shape from Multiple Incomplete Range Data Sets Using Convex Hulls," Com-puter Graphics International '93, Lausanne, Switzerland, June 21-25, 1993, pp. 193-203.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Range data

General Terms:
Algorithms, Theory

Keywords:
polygon mesh, range images, structured light range scanner, surface fitting, surface reconstruction