Surface reconstruction of freeform objects based on multiresolution volumetric method

ABSTRACT

3D scanners developed over the past several decades have facilitated the reconstruction of complicated engineering parts. Typically the boundary representation of a part is reconstructed from its scanned cloud of points. This approach, however, is still limited and cannot be applied to a family of objects such as thin parts. Recently, new 3D scanning devices have been developed. These devices capture additional information, such as normals and texture, as well as conventional information, including clouds of sampled points.This paper describes a new and fast reverse engineering method for creating a 3D computerized model from data captured by contemporary 3D scanning devices. The proposed method aggregates large-scale 3D scanned data into an extended Hierarchical Space Decomposition Model (HSDM) based on Octree data structure. This model can represent both an object's boundary surface and its interior volume. Based on the proposed volumetric model, the surface reconstruction process becomes more robust and stable with respect to sampling noise. The hierarchical structure of the proposed volumetric model enables data reduction, while preserving sharp geometrical features and object topology. As a result of data reduction, the execution time of the reconstruction process is significantly reduced. Moreover, the proposed model naturally allows multiresolution surface reconstruction, represented by a mesh with regular properties. The proposed surface reconstruction approach is based on extracting a Connectivity Graph from the extended HSDM and reconstructing facets based on normals data. The feasibility of the method will be demonstrated on a number of complex objects, including thin parts.

REFERENCES

• 1: Nina Amenta , Marshall Bern, Surface reconstruction by Voronoi filtering, Proceedings of the fourteenth annual symposium on Computational geometry, p.39-48, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276889]
• 2: Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376986]
• 3: F. Bernardini, C. L. Bajaj, J. Chen, and D. R. Schikore. Automatic reconstruction of 3D CAD models from digital scans. International Journal of Computational Geometry and Applications (IJCGA), 9(4&5):327--370, Aug. & Oct. 1999.
• 4: 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 ]
• 5: J. D. Boissonat. Representing 2D and 3D shapes with the delaunay triangulation. In Seventh International Conference on Pattern Recognition (Montreal, Canada, July 30-August 2, 1984), pages 745--748. IEEE, 1984.
• 6: Pere Brunet , Dolores Ayala, Extended octtree representation of free form surfaces, Computer Aided Geometric Design, v.4 n.1-2, p.141-154, July 1987 [doi>10.1016/0167-8396(87)90031-8 ]
• 7: CATIA. Cloud to geometry. User's Guide, April 1997.
• 8: 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]
• 9: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: Tamal K. Dey , Joachim Giesen , James Hudson, Delaunay based shape reconstruction from large data, Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, October 22-23, 2001, San Diego, California
• 11: A. Doi, S. Fujiwara, K. Matsuda, and M. Kameda. 3d volume extraction and mesh generation using energy minimization techniques. In 1st International Symposium on 3D Data Processign Visualization and Transmission, pages 83--86. IEEE, June 2002.
• 12: 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]
• 13: C. A. Gran. Octree-based Simplification of Polyhedral Solids. PhD thesis, University of Catalunya, 1999.
• 14: H. Hoppe. "http://research.microsoft.com/~hoppe/".
• 15: Hugues Hoppe, Surface reconstruction from unorganized points, University of Washington, Seattle, WA, 1995
• 16: 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
• 17: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 18: M. Kass, A. Witkin, and D. Terzopoulos. Snakes: Active contour models. International Journal on Computer Vision, 1:321--331, 1988.
• 19: 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]
• 20: Large Geometric Models Archive. "http://www.cc.gatech.edu/projects/large_models/".
• 21: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 22: R. Mencl , H. Müller, Graph-Based Surface Reconstruction Using Structures in Scattered Point Sets, Proceedings of the Computer Graphics International 1998, p.298, June 22-26, 1998
• 23: Yutaka Ohtake , Alexander G. Belyaev, Dual/Primal mesh optimization for polygonized implicit surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566308]
• 24: P. Perona , J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.629-639, July 1990 [doi>10.1109/34.56205 ]
• 25: J. Rossignac and P. Borrel. Multi-resolution 3D approximation for rendering complex scenes. In Second Conference on Geometric Modelling in Computer Graphics, pages 453--465, June 1993. Genova, Italy.
• 26: T. Várady, R. R. Martin, and J. Cox. Reverse engineering of geometric models - an introduction. Computer Aided Design, 29(4):255--268, 1997.
• 27: Hong-Kai Zhao , Stanley Osher , Ronald Fedkiw, Fast Surface Reconstruction Using the Level Set Method, Proceedings of the IEEE Workshop on Variational and Level Set Methods (VLSM'01), p.194, July 13-13, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms

Keywords:
multiresolution, octree, reverse engineering, surface reconstruction