Symmetry Detection and Structure Discovery

"Symmetry is a complexity-reducing concept [...]; seek it everywhere."
Alan J. Perlis

Short Summary

Symmetry and structural regularity are essential concepts in many natural and man-made objects and play a crucial role in visual perception, biology and physics, design, engineering, and art. This project investigates computational methods to detect and enhance symmetries and regular structures in geometric models.

 

Project Description

Symmetry detection and structure recovery have applications in shape matching and retrieval, compression, geometric modeling and shape design, and scientific data exploration. We introduce a novel approach for detecting partial and approximate symmetries in 3D shapes. The method employs a clustering algorithm that aggregates local symmetry information in an appropriately defined transformation space. We prove that this algorithm finds the relevant symmetries of a given model with high probability, given a suitably dense sampling. This work is complemented by an optimization procedure that enhances imperfect symmetries by deforming a shape towards a symmetric configuration. Currently we are investigating a formal model of symmetry and a new methodology based on compact generative models that allows a concise and semantically meaningful way of representing digital geometry. Such a framework will enable the analysis of the underlying design principles of geometric shapes and facilitate novel geometry synthesis algorithms based on procedural models derived from the extracted design rules.

 

Results

Regular structures discovered by our algorithm involve combinations of rotation, translation, and scaling of the repetitive elements.

Different 3D objects symmetrized with our algorithm. The transparent shapes indicate the original models. The example in the center shows a fully automatic correspondence computation that can be formulated as a symmetrization of the two poses of a scanned human.

Perfectly symmetric meshes can be obtained using symmetrizing deformations, symmetric sampling, and symmetry-aware meshing.

Symmetry Detection in an architectural model. The images in the center show the two most prominent symmetries. The image on the right shows the global symmetry structure.

 

 

Publications

 

Symmetry in 3D Geometry: Extraction and Applications

Niloy J. Mitra, Mark Pauly, Michael Wand, Duygu Ceylan
State-of-the-art Report (STAR). Computer Graphics Forum (Proceedings of Eurographics) 2012

Paper Slides


Discovering Structural Regularity in 3D Geometry

Mark Pauly, Niloy J. Mitra, Johannes Wallner, Helmut Pottmann, Leonidas J. Guibas
ACM Transactions on Graphics (Proceedings of SIGGRAPH) 2008

Paper


Symmetrization

Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly
ACM Transactions on Graphics (Proceedings of SIGGRAPH) 2007

Paper Movie


Partial and Approximate Symmetry Detection for 3D Geometry

Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly ACM Transactions on Graphics (Proceedings of SIGGRAPH) 2006

Paper


 

Participating Researchers

Mark Pauly, Niloy Mitra, Leonidas Guibas, Johannes Wallner, Helmut Pottmann