Robust mesh reconstruction from unoriented noisy points

ABSTRACT

We present a robust method to generate mesh surfaces from unoriented noisy points in this paper. The whole procedure consists of three steps. Firstly, the normal vectors at points are evaluated by a highly robust estimator which can fit surface corresponding to less than half of the data points and fit data with multi-structures. This benefits us with the ability to well reconstruct the normal vectors around sharp edges and corners. Meanwhile, clean point cloud equipped with piecewise normal is obtained by projecting points according to the robust fitting. Secondly, an error-minimized subsampling is applied to generate a well-sampled point cloud. Thirdly, a combinatorial approach is employed to reconstruct a triangular mesh connecting the down-sampled points, and a polygonal mesh which preserves sharp features is constructed by the dual-graph of triangular mesh. Parallelization method of the algorithm on a consumer PC using the architecture of GPU is also given.

REFERENCES

• 1: M. Alexa, J. Behr, D. Cohen-Or, S. Fleishman, D. Levin, and C. T. Silva. Computing and rendering point set surfaces. IEEE Transactions on Visualization and Computer Graphics, 9(1):3--15, January 2003.
• 2: P. Alliez, D. Cohen-Steiner, Y. Tong, and M. Desbrun. Voronoi-based variational reconstruction of unoriented point sets. In SGP '07, pages 39--48, 2007.
• 3: N. Amenta, M. Bern, and M. Kamvysselis. A new voronoi-based surface reconstruction algorithm. In SIGGRAPH '98, pages 415--421, 1998.
• 4: N. Amenta, S. Choi, T. K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. In SCG '00: Proceedings of the sixteenth annual symposium on Computational geometry, pages 213--222, 2000.
• 5: N. Amenta, S. Choi, and R. K. Kolluri. The power crust. In SMA '01: Proceedings of the sixth ACM symposium on Solid modeling and applications, pages 249--266, 2001.
• 6: C. L. Bajaj, F. Bernardini, and G. Xu. Automatic reconstruction of surfaces and scalar fields from 3d scans. In SIGGRAPH '95, pages 109--118, 1995.
• 7: M. Bolitho, M. Kazhdan, R. Burns, and H. Hoppe. Multilevel streaming for out-of-core surface reconstruction. In SGP '07, pages 69--78, 2007.
• 8: C. Buchart, D. Borro, and A. Amundarain. A gpu interpolating reconstruction from unorganized points. In SIGGRAPH '07: ACM SIGGRAPH 2007 posters, page 8, 2007.
• 9: J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and T. R. Evans. Reconstruction and representation of 3d objects with radial basis functions. In SIGGRAPH '01, pages 67--76, 2001.
• 10: P. Cignoni, C. Rocchini, and R. Scopigno. Metro: measuring error on simplified surfaces. Computer Graphics Forum, 17(2):167--174, 1998.
• 11: D. Cohen-Steiner, P. Alliez, and M. Desbrun. Variational shape approximation. In SIGGRAPH '04, pages 905--914, 2004.
• 12: T. K. Dey, J. Giesen, and J. Hudson. Delaunay based shape reconstruction from large data. In PVG '01: Proceedings of the IEEE 2001 symposium on parallel and large-data visualization and graphics, pages 19--27, 2001.
• 13: T. K. Dey and S. Goswami. Tight cocone: a water-tight surface reconstructor. In SM '03: Proceedings of the eighth ACM symposium on Solid modeling and applications, pages 127--134, 2003.
• 14: J. R. Diebel, S. Thrun, and M. Brünig. A bayesian method for probable surface reconstruction and decimation. ACM Trans. Graph., 25(1):39--59, 2006.
• 15: S. Fleishman, D. Cohen-Or, and C. T. Silva. Robust moving least-squares fitting with sharp features. In SIGGRAPH '05, pages 544--552, 2005.
• 16: H. Hoppe, T. DeRose, T. Duchamp, M. Halstead, H. Jin, J. McDonald, J. Schweitzer, and W. Stuetzle. Piecewise smooth surface reconstruction. In SIGGRAPH '94, pages 295--302, 1994.
• 17: H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstruction from unorganized points. In SIGGRAPH '92, pages 71--78, 1992.
• 18: A. Hornung and L. Kobbelt. Robust reconstruction of watertight 3d models from non-uniformly sampled point clouds without normal information. In SGP '06, pages 41--50, 2006.
• 19: I. P. Ivrissimtzis, W.-K. Jeong, and H.-P. Seidel. Using growing cell structures for surface reconstruction. In SMI '03: Proceedings of the Shape Modeling International 2003, page 78, Washington, DC, USA, 2003.
• 20: P. Jenke, M. Wand, M. Bokeloh, A. Schilling, and W. Straßer. Bayesian point cloud reconstruction. Comput. Graph. Forum, 25(3), 2006.
• 21: A. Kalaiah and A. Varshney. Modeling and rendering of points with local geometry. IEEE Transactions on Visualization and Computer Graphics, 9(1):30--42, 2003.
• 22: M. Kazhdan. Reconstruction of solid models from oriented point sets. In SGP '05, page 73, 2005.
• 23: M. Kazhdan, M. Bolitho, and H. Hoppe. Poisson surface reconstruction. In SGP '06, pages 61--70, 2006.
• 24: C.-C. Kuo and H.-T. Yau. A new combinatorial approach to surface reconstruction with sharp features. IEEE Trans. Vis. Comput. Graph., 12(1):73--82, 2006.
• 25: D. Levin. Mesh-independent surface interpolation. In Geometric Modeling for Scientific Visualization, pages 37--49, 2003.
• 26: Y. Lipman, D. Cohen-Or, D. Levin, and H. Tal-Ezer. Parameterization-free projection for geometry reconstruction. In SIGGRAPH '07: ACM SIGGRAPH 2007 papers, page 22, New York, NY, USA, 2007. ACM.
• 27: S. P. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28:129--136, 1982.
• 28: W. E. Lorensen and H. E. Cline. Marching cubes: A high resolution 3d surface construction algorithm. SIGGRAPH Comput. Graph., 21(4):163--169, 1987.
• 29: L. G. Mark Pauly, Niloy Mitra. Uncertainty and variability in point cloud surface data. In Symposium on Point-Based Graphics 2004, 2004.
• 30: B. Mederos, N. Amenta, L. Velho, and L. H. de Figueiredo. Surface reconstruction from noisy point clouds. In SGP '05: Proceedings of the third Eurographics symposium on Geometry processing, page 53, 2005.
• 31: J. V. Miller and C. V. Stewart. Muse: Robust surface fitting using unbiased scale estimates. In CVPR, pages 300--, 1996.
• 32: D. M. Mount and S. Arya. Ann: A library for approximate nearest neighbor searching. Aug. 2006. http://www.cs.umd.edu/mount/ANN/.
• 33: Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P. Seidel. Multi-level partition of unity implicits. ACM Trans. Graph., 22(3):463--470, 2003.
• 34: Y. Ohtake, A. Belyaev, and H.-P. Seidel. 3d scattered data interpolation and approximation with multilevel compactly supported rbfs. Graph. Models, 67(3):150--165, 2005.
• 35: S. Petitjean. A survey of methods for recovering quadrics in triangle meshes. ACM Comput. Surv., 34(2):211--262, 2002.
• 36: M. Samozino, M. Alexa, P. Alliez, and M. Yvinec. Reconstruction with voronoi centered radial basis functions. In SGP '06, pages 51--60, 2006.
• 37: O. Schall, A. Belyaev, and H.-P. Seidel. Robust filtering of noisy scattered point data. In M. Pauly and M. Zwicker, editors, IEEE/Eurographics Symposium on Point-Based Graphics, pages 71--77, Stony Brook, New York, USA, 2005.
• 38: A. Sharf, T. Lewiner, A. Shamir, L. Kobbelt, and D. Cohen-Or. Competing fronts for coarse-to-fine surface reconstruction. Computer Graphics Forum, 25(3):389--398, 2006.
• 39: J. Shen, D. Yoon, D. Shehu, and S.-Y. Chang. Spectral moving removal of non-isolated surface outlier clusters. Computer-Aided Design, In Press, Corrected Proof:--, 2008.
• 40: S. Silva, J. Madeira, and B. S. Santos. Polymeco "a polygonal mesh comparison tool. In IV '05: Proceedings of the Ninth International Conference on Information Visualisation, pages 842--847, Washington, DC, USA, 2005. IEEE Computer Society.
• 41: H. Song and H.-Y. Feng. A global clustering approach to point cloud simplification with a specified data reduction ratio. Computer Aided Design, 40(3):281--292, 2008.
• 42: F. Steinke, B. Schölkopf, and V. Blanz. Support vector machines for 3d shape processing. Comput. Graph. Forum, 24(3):285--294, 2005.
• 43: B. Tordoff and D. W. Murray. Guided sampling and consensus for motion estimation. In ECCV '02: Proceedings of the 7th European Conference on Computer Vision -- Part I, pages 82--98, London, UK, 2002. Springer-Verlag.
• 44: G. Turk and J. F. O'Brien. Shape transformation using variational implicit functions. In SIGGRAPH '99, pages 335--342, 1999.
• 45: S. Valette, J. M. Chassery, and R. Prost. Generic remeshing of 3d triangular meshes with metric-dependent discrete voronoi diagrams. IEEE Transactions on Visualization and Computer Graphics, 14(2):369--381, 2008.
• 46: H. Wang and D. Suter. MDPE: A very robust estimator for model fitting and range image segmentation. Int. J. Comput. Vision, 59(2):139--166, 2004.
• 47: H. Xie, K. T. McDonnell, and H. Qin. Surface reconstruction of noisy and defective data sets. In VIS '04: Proceedings of the conference on Visualization '04, pages 259--266, 2004.
• 48: K. Zhou, M. Gong, X. Huang, and B. Guo. Highly parallel surface reconstruction. 2008. Microsoft Technical Report, MSR-TR-2008-53 http://www.kunzhou.net/2008/MSR-TR-2008-53.pdf.

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

Keywords:
GPU, noisy points, parallel computing, robust approach, surface reconstruction