Discovering structural regularity in 3D geometry

Mark Pauly*, Niloy Mitra, Johannes Wallner, Helmut Pottmann, Leonidas J. Guibas

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

48 Scopus citations

Abstract

We introduce a computational framework for discovering regular or repeated geometric structures in 3D shapes. We describe and classify possible regular structures and present an effective algorithm for detecting such repeated geometric patterns in point- or mesh-based models. Our method assumes no prior knowledge of the geometry or spatial location of the individual elements that define the pattern. Structure discovery is made possible by a careful analysis of pairwise similarity transformations that reveals prominent lattice structures in a suitable model of transformation space. We introduce an optimization method for detecting such uniform grids specifically designed to deal with outliers and missing elements. This yields a robust algorithm that successfully discovers complex regular structures amidst clutter, noise, and missing geometry. The accuracy of the extracted generating transformations is further improved using a novel simultaneous registration method in the spatial domain. We demonstrate the effectiveness of our algorithm on a variety of examples and show applications to compression, model repair, and geometry synthesis.

Original languageEnglish (US)
StatePublished - Dec 18 2008
EventACM SIGGRAPH 2008 Papers 2008, SIGGRAPH'08 - Los Angeles, CA, United States
Duration: Aug 11 2008Aug 15 2008

Other

OtherACM SIGGRAPH 2008 Papers 2008, SIGGRAPH'08
CountryUnited States
CityLos Angeles, CA
Period08/11/0808/15/08

Keywords

  • Regular structure
  • Repetitive pattern
  • Shape analysis
  • Similarity transformation
  • Transformation group

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design
  • Human-Computer Interaction

Fingerprint

Dive into the research topics of 'Discovering structural regularity in 3D geometry'. Together they form a unique fingerprint.

Cite this