Discovering structural regularity in 3D geometry
Top Cited Papers
- 1 August 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 27 (3), 1-11
- https://doi.org/10.1145/1360612.1360642
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 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.Funding Information
- Defense Advanced Research Projects Agency (HR0011-05-1-0007)
- National Institutes of Health (GM-072970)
- National Science Foundation (FRG-0354543)
- Division of Mathematical Sciences (FRG-0354543)
This publication has 24 references indexed in Scilit:
- SymmetrizationACM Transactions on Graphics, 2007
- A planar-reflective symmetry transform for 3D shapesACM Transactions on Graphics, 2006
- Partial and approximate symmetry detection for 3D geometryACM Transactions on Graphics, 2006
- Accurate detection of symmetries in 3D shapesACM Transactions on Graphics, 2006
- A computational model for periodic pattern perception based on frieze and wallpaper groupsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Noncombinatorial detection of regular repetitions under perspective skewIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Mean shift: a robust approach toward feature space analysisIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Calculation of a constant Q spectral transformThe Journal of the Acoustical Society of America, 1991
- Closed-form solution of absolute orientation using unit quaternionsJournal of the Optical Society of America A, 1987
- Random sample consensusCommunications of the ACM, 1981