Qixing Huang, Leonidas Guibas, and Niloy Mitra. Near-Regular Structure Extraction Using Linear Programming. ACM Transactions on Graphics (SIGGRAPH 2014), 2014.


Near-regular structures are common in man-made and natural objects. Algorithmic detection of such regularity greatly facilitates our understanding of shape geometries, leads to compact encoding of input geometries, and enables efficient generation and manipulation of complex patterns on both acquired and synthesized objects. Regularity manifests itself both in the repetition of certain geometric elements, as well as in the structured placement of the elements. We cast the regularity detection problem as an optimization and efficiently solve it using linear programming techniques. Our optimization has a discrete aspect, the connectivity relationships among the elements, as well as a continuous aspect, the locations of the elements of interest. Both of these are captured by our near-regular mesh extraction framework, which alternates between discrete and continuous optimizations. We demonstrate the effectiveness of our framework on a variety of problems including manifold near-regular structure extraction, structure-preserving pattern manipulation, and markerless correspondence detection. Robustness results with respect to geometric and topological noise are also presented on synthesized and benchmark datasets.


 author = {Qixing Huang and Leonidas Guibas and Niloy Mitra},
 title = {Near-Regular Structure Extraction Using Linear Programming},
 journal = {ACM Transactions on Graphics},