{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T04:27:49Z","timestamp":1765254469730,"version":"3.46.0"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>Cellular patterns, from planar ornaments to architectural surfaces and mechanical metamaterials, blend aesthetics with functionality. Homogeneous patterns like isohedral tilings offer simplicity and symmetry but lack flexibility, particularly for heterogeneous designs. They cannot smoothly interpolate between tilings or adapt to double-curved surfaces without distortion. Voronoi diagrams provide a more adaptable patterning solution. They can be generalized to star-shaped metrics, enabling diverse cell shapes and continuous grading by interpolating metric parameters. Mart\u00ednez et al. [2019] explored this idea in 2D using a rasterization-based algorithm to create compelling patterns. However, this discrete approach precludes gradient-based optimization, limiting control over pattern quality. We introduce a novel, closed-form, fully differentiable formulation for Voronoi diagrams with piecewise linear star-shaped metrics, enabling optimization of site positions and metric parameters to meet aesthetic and functional goals. It naturally extends to arbitrary dimensions, including curved 3D surfaces. For improved on-surface patterning, we propose a per-sector parameterization of star-shaped metrics, ensuring uniform cell shapes in non-regular neighborhoods. We demonstrate our approach by generating diverse patterns, from homogeneous to continuously graded designs, with applications in decorative surfaces and metamaterials.<\/jats:p>","DOI":"10.1145\/3763296","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Closed-Form Construction of Voronoi Diagrams with Star-Shaped Metrics"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9663-5016","authenticated-orcid":false,"given":"Haoyang","family":"Zhou","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-1431-7370","authenticated-orcid":false,"given":"Logan","family":"Numerow","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6604-4784","authenticated-orcid":false,"given":"Stelian","family":"Coros","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8086-7664","authenticated-orcid":false,"given":"Bernhard","family":"Thomaszewski","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Olivier Devillers, and Martin Isenburg.","author":"Alliez Pierre","year":"2005","unstructured":"Pierre Alliez, \u00c9ric Colin De Verdi\u00e8re, Olivier Devillers, and Martin Isenburg. 2005. Centroidal Voronoi diagrams for isotropic surface remeshing. Graphical models 67, 3 (2005), 204\u2013231."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2008.169"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778853"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399504.1360662"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/natrevmats.2017.66"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057437"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2007.70408"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185559"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130817"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925911"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323264"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766901"},{"key":"e_1_2_2_14_1","first-page":"1","article-title":"Tile patterning on free-form surfaces that reduces tile cutting","volume":"2023","author":"Du Chaoyu","year":"2023","unstructured":"Chaoyu Du, Tom Van Mele, and Philippe Block. 2023. Tile patterning on free-form surfaces that reduces tile cutting. Proceedings of IASS Annual Symposia 2023, 21 (2023), 1\u201310. https:\/\/www.ingentaconnect.com\/content\/iass\/piass\/2023\/00002023\/00000021\/art00001","journal-title":"Proceedings of IASS Annual Symposia"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-0309-8_4"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3502802"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.7121"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2383654.2383668"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.674976"},{"volume-title":"Tilings and patterns: An introduction","author":"Grunbaum Branko","key":"e_1_2_2_20_1","unstructured":"Branko Grunbaum and Geoffrey Colin Shephard. 1989. Tilings and patterns: An introduction. WH Freeman and Company."},{"key":"e_1_2_2_21_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_2_22_1","unstructured":"Gurobi Optimization LLC. 2024. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360647"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2498620"},{"key":"e_1_2_2_25_1","unstructured":"Steven G. Johnson. 2007. The NLopt nonlinear-optimization package. https:\/\/github.com\/stevengj\/nlopt."},{"key":"e_1_2_2_26_1","volume-title":"Introductory Tiling Theory for Computer Graphics","author":"Kaplan Craig","unstructured":"Craig Kaplan. 2009. Introductory Tiling Theory for Computer Graphics (1st ed.). Morgan and Claypool Publishers.","edition":"1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462005"},{"key":"e_1_2_2_28_1","volume-title":"Stripe Patterns on Surfaces. ACM Trans. Graph. 34","author":"Kn\u00f6ppel Felix","year":"2015","unstructured":"Felix Kn\u00f6ppel, Keenan Crane, Ulrich Pinkall, and Peter Schr\u00f6der. 2015. Stripe Patterns on Surfaces. ACM Trans. Graph. 34 (2015). Issue 4."},{"volume-title":"Computer Graphics Forum","author":"Landreneau Eric","key":"e_1_2_2_29_1","unstructured":"Eric Landreneau and Scott Schaefer. 2010. Scales and scale-like structures. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1653\u20131660."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141921"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424630.3425411"},{"key":"e_1_2_2_32_1","unstructured":"Bruno L\u00e9vy. 2015. Geogram. https:\/\/github.com\/BrunoLevy\/geogram."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778856"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618325"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658122"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102853"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559758"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","first-page":"1502","DOI":"10.1109\/TPAMI.2010.221","article-title":"Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces","volume":"33","author":"Liu Yong-Jin","year":"2010","unstructured":"Yong-Jin Liu, Zhanqing Chen, and Kai Tang. 2010. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 8 (2010), 1502\u20131517.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1088\/1361-665X\/aca5d6"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925922"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818101"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322989"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073638"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588432.3591496"},{"key":"e_1_2_2_46_1","volume-title":"Differentiable Stripe Patterns for Inverse Design of Structured Surfaces. ACM Transactions on Graphics (TOG)","author":"Montes Juan","year":"2023","unstructured":"Juan Montes, Yinwei Du, Ronan Hinchet, Stelian Coros, and Bernhard Thomaszewski. 2023. Differentiable Stripe Patterns for Inverse Design of Structured Surfaces. ACM Transactions on Graphics (TOG) (2023)."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658175"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311561"},{"key":"e_1_2_2_49_1","volume-title":"SIGGRAPH Asia 2025 Conference Papers","author":"Numerow Logan","year":"2025","unstructured":"Logan Numerow, Stelian Coros, and Bernhard Thomaszewski. 2025. Star-Shaped Distance Voronoi Diagrams for 3D Metamaterial Design. In SIGGRAPH Asia 2025 Conference Papers (Hong Kong, Hong Kong) (SA '25). Association for Computing Machinery, New York, NY, USA."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658152"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459789"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073649"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766937"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073239"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658125"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766926"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275085"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12967"},{"key":"e_1_2_2_59_1","unstructured":"Nicholas Sharp et al. 2019b. Polyscope. www.polyscope.run."},{"key":"e_1_2_2_60_1","unstructured":"Nicholas Sharp Keenan Crane et al. 2019a. GeometryCentral: A modern C++ library of data structures and algorithms for geometry processing. https:\/\/geometry-central.net\/. (2019)."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.2312\/SGP\/SGP03\/020-030"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499362822"},{"key":"e_1_2_2_63_1","unstructured":"The CGAL Project. 2024. CGAL User and Reference Manual (6.0.1 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/6.0.1\/Manual\/packages.html"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392451"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417790"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383297"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2014.08.023"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01521.x"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01521.x"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.09.004"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925888"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126594.3126600"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618396"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141942"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3095815"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:12:36Z","timestamp":1764969156000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":75,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3763296"],"URL":"https:\/\/doi.org\/10.1145\/3763296","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-05-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}