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

Information

• Publication Type: Poster
• Workgroup(s)/Project(s):
  • Rendering and Modeling
• Date: May 2012
• Publisher: Eurographics Association
• Location: Cagliari, Italy
• Event: Eurographics 2012 (Best Poster Award)
• Booktitle: Poster Proceedings
• Conference date: 13. May 2012 – 18. May 2012
• Pages: 25 – 26
• Keywords: Point Cloud, Point Set, Reconstruction, Surface Construction

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

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,
  publisher =  "Eurographics Association",
  location =   "Cagliari, Italy",
  event =      "Eurographics 2012 (Best Poster Award)",
  booktitle =  "Poster Proceedings",
  Conference date = "Poster presented at Eurographics 2012 (Best Poster Award)
               (2012-05-13--2012-05-18)",
  note =       "25--26",
  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/",
}