“Zippered polygon meshes from range images” by Turk and Levoy

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.

1. Bern, Marshall and David Eppstein, “Mesh Generation and Optimal Triangulation,” Technical Report P92-00047, Xerox Palo Alto Research Center, March 1992.
2. Besl, Paul J. and Neil D. McKay, “A Method of Registra-tion of 3-D Shapes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, No. 2 (February 1992), pp. 239-256.
3. Boissonnat, Jean-Daniel, “Geometric Structures for Three-Dimensional Shape Representation,” ACM Transactions on Graphics, Vol. 3, No. 4 (October 1984), pp. 266-286.
4. 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.
5. 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.
6. Chen, Yang and Gerard Medioni, “Object Modelling by Registration of Multiple Range Images,” Image and Vision Comput-ing, Vol. 10, No. 3 (April 1992), pp. 145-155.
7. Edelsbrunner, Herbert and Ernst P. M~cke, “Three-dimensional Alpha Shapes,” Proceedings of the 1992 Work-shop on Volume Visualization, Boston, October 19-20, 1992, pp. 75- 82.
8. Hoppe, Hugues, Tony DeRose, Tom Duchamp, John McDonald and Werner Stuetzle, “Surface Reconstruction from Unorganized Points,” Computer Graphics, Vol. 26, No. 2 (SIGGRAPH ’92), pp. 71-78.
9. Hoppe, Hugues, Tony DeRose, Tom Duchamp, John McDonald and Werner Stuetzle, “Mesh Optimization,” Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH ’93), pp. 19-26.
10. 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.
11. Schroeder, William J., Jonathan A. Zarge and William E. Lorensen, “Decimation of Triangle Meshes,” Computer Graphics, Vol. 26, No. 2 (SIGGRAPH ’92), pp. 65-70.
12. 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.
13. Turk, Greg, “Re-Tiling Polygonal Surfaces,” Computer Graphics, Vol. 26, No. 2 (SIGGRAPH ’92), pp. 55-64.
14. 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.