Ohrhallinger, Stefan, Mudur, Sudhir and Wimmer, Michael (2013) Minimizing edge length to connect sparsely sampled unstructured point sets. Computers & Graphics, 37 (6). pp. 645658. ISSN 00978493

Text (application/pdf)
8MBmudur2013.pdf  Accepted Version 
Official URL: http://dx.doi.org/10.1016/j.cag.2013.05.016
Abstract
Most methods for interpolating unstructured point clouds handle densely sampled point sets quite well but get into trouble when the point set contains regions with much sparser sampling, a situation often encountered in practice. In this paper, we present a new method that provides a better interpolation of sparsely sampled features.
We pose the surface construction problem as finding the triangle mesh which minimizes the sum of all triangles’ longest edge. Since searching for matching umbrellas among sparsely sampled points to yield a closed manifold shape is a difficult problem, we introduce suitable heuristics. Our algorithm first connects the points by triangles chosen in order of their longest edge and with the requirement that all edges must have at least two incident triangles. This yields a closed nonmanifold shape which we call the Boundary Complex. Then we transform it into a manifold triangulation using topological operations. We show that in practice, runtime is linear to that of the Delaunay triangulation of the points. Source code is available online.
Divisions:  Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering 

Item Type:  Article 
Refereed:  Yes 
Authors:  Ohrhallinger, Stefan and Mudur, Sudhir and Wimmer, Michael 
Journal or Publication:  Computers & Graphics 
Date:  2013 
Digital Object Identifier (DOI):  10.1016/j.cag.2013.05.016 
Keywords:  Surface reconstruction; Point cloud; Boundary complex; Sharp features; Sparse sampling; Energy minimization 
ID Code:  977887 
Deposited By:  DANIELLE DENNIE 
Deposited On:  01 Oct 2013 18:13 
Last Modified:  18 Jan 2018 17:45 
References:
1. H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle Surface reconstruction from unorganized points Comput Graph, 26 (2) (1992), pp. 71–78[2]
Ohrhallinger S, Mudur S. An efficient algorithm for determining an aesthetic shape connecting unorganized 2d points. Comput Graph Forum, 10.1111/cgf.12162, in press.
[3]
N. Amenta, M. Bern Surface reconstruction by voronoi filtering Discrete Comput Geom, 22 (1998), pp. 481–504
[4]
Edelsbrunner H, Mücke EP. Threedimensional alpha shapes. In: VVS '92: Proceedings of the 1992 workshop on volume visualization. New York, NY, USA: ACM; 1992. p. 75–82.
[5]
R.C. Veltkamp Boundaries through scattered points of unknown density Graph Model Im Proc, 57 (6) (1995), pp. 441–452
[6]
F. Bernardini, J. Mittleman, H. Rushmeier, C. Silva, G. Taubin The ballpivoting algorithm for surface reconstruction IEEE Trans Vis Comput Graph, 5 (4) (1999), pp. 349–359
[7]
D. CohenSteiner, F. Da A greedy Delaunaybased surface reconstruction algorithm Vis Comput, 20 (1) (2004), pp. 4–16
[8]
J.D. Boissonnat Geometric structures for threedimensional shape representation ACM Trans Graph, 3 (4) (1984), pp. 266–286
[9]
M. Gopi, S. Krishnan, C. Silva Surface reconstruction based on lower dimensional localized delaunay triangulation Comput Graph Forum, 19 (3) (2000), pp. 467–478
[10]
Dumitriu D, Funke S, Kutz M, Milosavljevic N. How much geometry it takes to reconstruct a 2manifold in r3. In: Proceedings of the 10th workshop on algorithm engineering and experiments, ALENEX 2008, San Francisco, USA, ACMSIAM. San Francisco, USA; 2008. p. 65–74.
[11]
Funke S, Ramos EA. Smoothsurface reconstruction in nearlinear time. In: SODA '02: proceedings of the 13th annual ACMSIAM symposium on discrete algorithms. Philadelphia, PA, USA: SIAM; 2002. p. 781–90.
[12]
U. Adamy, J. Giesen, M. John Surface reconstruction using umbrella filters Comput Geom: Theory Appl, 21 (1) (2002), pp. 63–86
[13]
Kós G. An algorithm to triangulate surfaces in 3d using unorganised point clouds. In: Geometric modelling. London, UK: SpringerVerlag; 2001. p. 219–32.
[14]
M. Attene, M. Spagnuolo Automatic surface reconstruction from point sets in space Comput Graph Forum, 19 (3) (2000), pp. 457–465
[15]
Chaine R. A geometric convection approach of 3d reconstruction. In: SGP '03: proceedings of the 2003 eurographics/ACM SIGGRAPH symposium on geometry processing. AirelaVille, Switzerland: Eurographics Association; 2003. p. 218–29.
[16]
N. Amenta, S. Choi, R. Kolluri The power crust, unions of balls, and the medial axis transform Comput Geom, 19 (27) (2001), pp. 127–153
[17]
Amenta N, Choi S, Dey TK, Leekha N. A simple algorithm for homeomorphic surface reconstruction. In: SCG '00: proceedings of the 16th annual symposium on computational geometry. New York, NY, USA: ACM; 2000. p. 213–22.
[18]
Dey TK, Goswami S. Tight cocone: a watertight surface reconstructor. In: SM '03: proceedings of the eighth ACM symposium on solid modeling and applications. New York, NY, USA: ACM; 2003. p. 127–34.
[19]
Dey TK, Goswami S. Provable surface reconstruction from noisy samples. In: Proceedings of the 20th annual symposium on computational geometry, SCG '04. New York, NY, USA: ACM; 2004. p. 330–9.
[20]
Giesen J, John M. The flow complex: a data structure for geometric modeling. In: Proceedings of the fourteenth annual ACMSIAM symposium on discrete algorithms, SODA '03. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics; 2003. p. 285–94.
[21]
H. Edelsbrunner Surface reconstruction by wrapping finite sets in space Discrete Comput Geom—‘The GoodmanPollack Festschrift’, 25 (1) (2003), pp. 379–404
[22]
Dey TK, Giesen J, Ramos EA, Sadri B. Critical points of the distance to an epsilonsampling of a surface and flowcomplexbased surface reconstruction. In: Proceedings of the 21st annual symposium on computational geometry, SCG '05. New York, NY, USA: ACM; 2005. p. 218–27.
[23]
Ramos EA, Sadri B. Geometric and topological guarantees for the wrap reconstruction algorithm. In: Proceedings of the 18th annual ACMSIAM symposium on discrete algorithms, SODA '07. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics; 2007. p. 1086–95.
[24]
B. Sadri Manifold homotopy via the flow complex Comput Graph Forum, 28 (5) (2009), pp. 1361–1370
[25]
L. Guibas, S. Oudot Reconstruction using witness complexes Discrete Comput Geom, 40 (2008), pp. 325–356
[26]
S. Petitjean, E. Boyer Regular and nonregular point setsproperties and reconstruction Comput Geom Theory Appl, 19 (2001), pp. 101–126
[27]
P. Labatut, J.P. Pons, R. Keriven Robust and efficient surface reconstruction from range data Comput Graph Forum, 28 (8) (2009), pp. 2275–2290
[28]
H. Hiyoshi Optimizationbased approach for curve and surface reconstruction Comput Aided Des, 41 (2009), pp. 366–374
[29]
S. Ohrhallinger, S.P. Mudur Interpolating an unorganized 2d point cloud with a single closed shape Comput Aided Des, 43 (12) (2011), pp. 1629–1638
[30]
Ruppert J. A new and simple algorithm for quality 2dimensional mesh generation. In: Proceedings of the fourth annual ACMSIAM symposium on discrete algorithms, SODA '93. Philadelphia, PA, USA: SIAM; 1993. p. 83–92.
[31]
H. Blum A transformation for extracting new descriptors of shape W. WathenDunn (Ed.), Models for the perception of speech and visual form, MIT Press, Cambridge (1967), pp. 362–380
[32]
Hert S, Seel M. dD convex hulls and Delaunay triangulations. In: CGAL User/Ref. Manual, 3.8 edition, CGAL Ed. Board; 2011.
[33]
Stefanov E, Disjoint sets data structure implementation. 〈http://www.emilstefanov.net/Projects/DisjointSets.aspx〉; 2011 [accessed May 13, 2011].
[34]
Ohrhallinger S, Prieler D. Sourcecode of algorithm in this paper. 〈https://sourceforge.net/p/connect3d/〉; May 2013.
[35]
Kazhdan M, Bolitho M, Hoppe H. Poisson surface reconstruction. In: Proceedings of the fourth eurographics symposium on geometry processing, SGP '06. AirelaVille, Switzerland: Eurographics Association; 2006. p. 61–70.
[36]
T.K. Dey, S. Goswami Provable surface reconstruction from noisy samples Comput GeomTheory Appl, 35 (1) (2006), pp. 124–141
Repository Staff Only: item control page