Discovering Structural Regularity in 3D Geometry

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

450 citations recorded by the source corpus.

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 meshbased 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.

Subfields: Computational Mechanics, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

Citations in the corpus

Shape Completion Using 3D-Encoder-Predictor CNNs and Shape Synthesis (2016, background): “For instance, many works detect symmetries in meshes or point clouds, and use them to ﬁll in missing data [41, 23, 30, 36, 39].”
PCN: Point Completion Network (2018, methodology): “Symmetry-driven methods [29, 30, 35, 36, 46, 52, 55] identify symmetry axes and repeating regular structures in the partial input in order to copy parts from observed regions to unobserved regions.”
Data-driven structural priors for shape completion (2015, background): “Although symmetric objects can be completed by copying observed regions to occluded counter-parts, existing symmetry detection algorithms (e.g., [Pauly et al. 2008; Mitra et al. 2006]) infer symmetry from the input shape, which means that they need to observe at least some fraction of the occluded…”
ScanComplete: Large-Scale Scene Completion and Semantic Segmentation for 3D Scans (2017, methodology): “Other shape completion methods have been developed, including approaches that leverage symmetries in meshes or point clouds [40, 19, 26, 34, 37] or part-based structural priors derived from a database [38].”
Voronoi-Based Curvature and Feature Estimation from Point Clouds (2011, background): “…are rotation-invariant local descriptors, which together with principal curvature directions have proven useful in detecting structural regularity [PMW + 08], global matching [AMCO08], modeling and rendering of point-based surfaces [GTE + 06], and anisotropic smoothing [LP05] to name just a few.”
3D Object Dense Reconstruction from a Single Depth View (2018, methodology): “[25] uses plane fitting to complete small missing regions, while [26] [27] [28] [29] [30] apply shape symmetry to fill in holes.”
Object detection and classification from large‐scale cluttered indoor scans (2014, methodology): “In scenes where symmetries or structure repetitions are dominant, such methods can compress and complete scans [PMW ∗ 08], which is especially effective for facades [CML ∗ 12].”
Style-content separation by anisotropic part scales (2010, methodology): “Basic Books.”
Segmentation and Unsupervised Part-based Discovery of Repetitive Objects (2010, background): “In 3D, discovery and utilization of repetition has been adressed in computer aided design and other synthetic models [7, 8, 9].”
A Survey of Surface Reconstruction from Point Clouds (2017, unknown): “The method of [PMW ∗ 08] ﬁnds repeating elements (small subsets of the point cloud) that can be mapped onto one another by local similarity transformations.”
3D Object Reconstruction from a Single Depth View with Adversarial Learning (2017, unknown): “[35] uses plane fitting to complete small missing regions, while [32] [34] [40] [48] [52] [56] applies shape symmetry to fill in holes.”
Part-based modelling of compound scenes from images (2015, methodology): “Parametrized sets of transformations have also been used to identify the building blocks of building facades [13] and 3D structures [14, 2].”
High-Resolution Shape Completion Using Deep Neural Networks for Global Structure and Local Geometry Inference (2017, unknown): “Based on the observation that urban objects are usually made of non-local repetitions, many methods ( [20] [32]) attempt to discover symmetries from input data and use them to complete the unknown geometry.”
Learning 3D Shape Completion from Laser Scan Data with Weak Supervision (2018, background): “The former leverage observed symmetry to complete shapes; representative works include [27, 29, 34, 46, 51].”