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

Preview |
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 non-manifold 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. Three-dimensional 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 ball-pivoting algorithm for surface reconstruction IEEE Trans Vis Comput Graph, 5 (4) (1999), pp. 349–359

[7]

D. Cohen-Steiner, F. Da A greedy Delaunay-based surface reconstruction algorithm Vis Comput, 20 (1) (2004), pp. 4–16

[8]

J.-D. Boissonnat Geometric structures for three-dimensional 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 2-manifold in r3. In: Proceedings of the 10th workshop on algorithm engineering and experiments, ALENEX 2008, San Francisco, USA, ACM-SIAM. San Francisco, USA; 2008. p. 65–74.

[11]

Funke S, Ramos EA. Smooth-surface reconstruction in near-linear time. In: SODA '02: proceedings of the 13th annual ACM-SIAM 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: Springer-Verlag; 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 3-d reconstruction. In: SGP '03: proceedings of the 2003 eurographics/ACM SIGGRAPH symposium on geometry processing. Aire-la-Ville, 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 water-tight 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 ACM-SIAM 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 Goodman-Pollack Festschrift’, 25 (1) (2003), pp. 379–404

[22]

Dey TK, Giesen J, Ramos EA, Sadri B. Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based 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 ACM-SIAM 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 non-regular 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 Optimization-based 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 2-dimensional mesh generation. In: Proceedings of the fourth annual ACM-SIAM 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. Wathen-Dunn (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. Source-code 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. Aire-la-Ville, 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