{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T15:16:40Z","timestamp":1778080600125,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR0011-05-1-0007"],"award-info":[{"award-number":["HR0011-05-1-0007"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["GM-072970"],"award-info":[{"award-number":["GM-072970"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["FRG-0354543"],"award-info":[{"award-number":["FRG-0354543"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["FRG-0354543"],"award-info":[{"award-number":["FRG-0354543"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1360612.1360642","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":230,"title":["Discovering structural regularity in 3D geometry"],"prefix":"10.1145","volume":"27","author":[{"given":"Mark","family":"Pauly","sequence":"first","affiliation":[{"name":"ETH Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niloy J.","family":"Mitra","sequence":"additional","affiliation":[{"name":"IIT Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Wallner","sequence":"additional","affiliation":[{"name":"TU Graz"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Helmut","family":"Pottmann","sequence":"additional","affiliation":[{"name":"TU Vienna"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas J.","family":"Guibas","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1113\/jphysiol.1969.sp008862"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1121\/1.400476"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0052-1"},{"key":"e_1_2_2_4_1","volume-title":"Proc. Symp. Geometry Processing. 177--187","author":"Cazals F."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.1000236"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/358669.358692"},{"key":"e_1_2_2_7_1","volume-title":"Tech. Rep. 782--07","author":"Golovinskiy A.","year":"2007"},{"key":"e_1_2_2_8_1","unstructured":"Gr\u00fcnbaum B. and Shephard G. C. 1987. Tilings and Patterns. W. H. Freeman.  Gr\u00fcnbaum B. and Shephard G. C. 1987. Tilings and Patterns . W. H. Freeman."},{"key":"e_1_2_2_9_1","volume-title":"Lie algebras, and representations. An Elementary Introduction","author":"Hall B. C."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2005.2"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1364\/JOSAA.4.000629"},{"key":"e_1_2_2_12_1","volume-title":"Int. Conference on Image Processing, 166--169","author":"Hsu J. T."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/83.128028"},{"key":"e_1_2_2_14_1","volume-title":"Int. Conference on Image Processing, 61--64","author":"Korah T."},{"key":"e_1_2_2_15_1","volume-title":"European Conference on Computer Vision, 546--555","author":"Leung T. K."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11802914_19"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1262332"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Liu S. Martin R. R. Langbein F. C. and Rosin P. L. 2007. Segmenting periodic reliefs on triangle meshes. In Math. of Surfaces XII. Springer 290--306.   Liu S. Martin R. R. Langbein F. C. and Rosin P. L. 2007. Segmenting periodic reliefs on triangle meshes. In Math. of Surfaces XII . Springer 290--306.","DOI":"10.1007\/978-3-540-73843-5_18"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","volume-title":"The Fractal Geometry of Nature","author":"Mandelbrot B.","DOI":"10.1119\/1.13295"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1138450.1138462"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141924"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276456"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276484"},{"key":"e_1_2_2_24_1","volume-title":"Proc. Symp. Geometry Processing, 23--32","author":"Pauly M."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141923"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-006-5167-2"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SMI.2007.6"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Schaffalitzky F. and Zisserman A. 1999. Geometric grouping of repeated elements within images. In Shape Contour and Grouping in Computer Vision 165--181.   Schaffalitzky F. and Zisserman A. 1999. Geometric grouping of repeated elements within images. In Shape Contour and Grouping in Computer Vision 165--181.","DOI":"10.1007\/3-540-46805-6_10"},{"key":"e_1_2_2_29_1","unstructured":"Shikhare D. Bhakar S. and Mudur S. P. 2001. Compression of large 3D engineering models using automatic discovery of repeating geometric features. In Vision Modeling and Visualization 233--240.   Shikhare D. Bhakar S. and Mudur S. P. 2001. Compression of large 3D engineering models using automatic discovery of repeating geometric features. In Vision Modeling and Visualization 233--240."},{"key":"e_1_2_2_30_1","volume-title":"Proc. Symp. Geometry Processing. 111--119","author":"Simari P."},{"key":"e_1_2_2_31_1","volume-title":"On Growth and Form","author":"Thompson D. W."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1190569"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1360612.1360642","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1360612.1360642","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1360612.1360642","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:10Z","timestamp":1750254970000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1360612.1360642"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1360612.1360642"],"URL":"https:\/\/doi.org\/10.1145\/1360612.1360642","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2008-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}