Minimising Longest Edge for Closed Surface Construction from Unorganised 3D Point Sets

Stefan Ohrhallinger, Sudhir Mudur
Minimising Longest Edge for Closed Surface Construction from Unorganised 3D Point Sets
Poster shown at Eurographics 2012 (Best Poster Award) (2012-05-13-2012-05-18) In Poster Proceedings, pages 25-26. May 2012.
[paper] [poster]

Information

Abstract

Given an unorganised 3D point set with just coordinate data, we formulate the problem of closed surface construction as one requiring minimisation of longest edge in triangles, a criterion derivable from Gestalt laws for shape perception. Next we define the Minimum Boundary Complex (BCmin ), which resembles the desired surface Bmin considerably, by slightly relaxing the topological constraint to make it at least two triangles per edge instead of exactly two required by Bmin . A close approximation of BCmin can be computed fast using a greedy algorithm. This provides a very good starting shape which can be transformed by a few steps into the desired shape, close to Bmin. Our method runs in O(n log n) time, with Delaunay Graph construction as largest run-time factor. We show considerable improvement over previous methods, especially for sparse, non-uniform point spacing.

Additional Files and Images

Additional images and videos

: 3D Reconstruction : 3D Reconstruction

Additional files

paper: Paper paper: Paper
poster: Poster poster: Poster

Weblinks

No further information available.

BibTeX

@misc{ohrhallinger_stefan-2012-mle,
  title =      "Minimising Longest Edge for Closed Surface Construction from
               Unorganised 3D Point Sets",
  author =     "Stefan Ohrhallinger and Sudhir Mudur",
  year =       "2012",
  abstract =   "Given an unorganised 3D point set with just coordinate data,
               we formulate the problem of closed surface construction as
               one requiring minimisation of longest edge in triangles, a
               criterion derivable from Gestalt laws for shape perception.
               Next we define the Minimum Boundary Complex (BCmin ), which
               resembles the desired surface Bmin considerably, by slightly
               relaxing the topological constraint to make it at least two
               triangles per edge instead of exactly two required by Bmin .
               A close approximation of BCmin can be computed fast using a
               greedy algorithm. This provides a very good starting shape
               which can be transformed by a few steps into the desired
               shape, close to Bmin. Our method runs in O(n log n) time,
               with Delaunay Graph construction as largest run-time factor.
               We show considerable improvement over previous methods,
               especially for sparse, non-uniform point spacing. ",
  month =      may,
  booktitle =  "Poster Proceedings",
  event =      "Eurographics 2012 (Best Poster Award)",
  location =   "Cagliari, Italy",
  publisher =  "Eurographics Association",
  note =       "Poster presented at Eurographics 2012 (Best Poster Award)
               (2012-05-13--2012-05-18)",
  pages =      "25--26",
  keywords =   "Point Cloud, Point Set, Reconstruction, Surface Construction",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2012/ohrhallinger_stefan-2012-mle/",
}