{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T09:23:42Z","timestamp":1768728222653,"version":"3.49.0"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T00:00:00Z","timestamp":1597190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN2017-05235, RGPAS-2017-507938"],"award-info":[{"award-number":["RGPIN2017-05235, RGPAS-2017-507938"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"name":"New Frontiers of Research Fund","award":["NFRFE-201"],"award-info":[{"award-number":["NFRFE-201"]}]},{"DOI":"10.13039\/100004675","name":"Autodesk","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004675","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fields Center for Quantitative Analysis and Modelling"},{"DOI":"10.13039\/501100002784","name":"Canada Research Chairs","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002784","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ontario Early Research Award"},{"name":"MESH Inc."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>This work concerns the computation and approximation of developable surfaces --- surfaces that are locally isometric to the two-dimensional plane. These surfaces are heavily studied in differential geometry, and are also of great interest to fabrication, architecture and fashion. We focus specifically on developability of heightfields. Our main observation is that developability can be cast as a rank constraint, which can then be plugged into theoretically-grounded rank-minimization techniques from the field of compressed sensing. This leads to a convex semidefinite optimization problem, which receives an input heightfield and recovers a similar heightfield which is developable. Due to the sparsifying nature of compressed sensing, the recovered surface is piecewise developable, with creases emerging between connected developable pieces. The convex program includes one user-specified parameter, balancing adherence to the original surface with developability and number of patches. We moreover show, that in contrast to previous techniques, our discretization does not introduce a bias and the same results are achieved across resolutions and orientations, and with no limit on the number of creases and patches. We solve this convex semidefinite optimization problem efficiently, by devising a tailor-made ADMM solver which leverages matrix-projection observations unique to our problem. We employ our method on a plethora of experiments, from denoising 3D scans of developable geometry such as documents and buildings, through approximating general heightfields with developable ones, and up to interpolating sparse annotations with a developable heightfield.<\/jats:p>","DOI":"10.1145\/3386569.3392419","type":"journal-article","created":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T11:44:27Z","timestamp":1597232667000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Developability of heightfields via rank minimization"],"prefix":"10.1145","volume":"39","author":[{"given":"Silvia","family":"Sell\u00e1n","sequence":"first","affiliation":[{"name":"University of Toronto"}]},{"given":"Noam","family":"Aigerman","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Alec","family":"Jacobson","sequence":"additional","affiliation":[{"name":"University of Toronto"}]}],"member":"320","published-online":{"date-parts":[[2020,8,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Jascha Achenbach Eduard Zell and Mario Botsch. 2015. Accurate face reconstruction through anisotropic fitting and eye correction. (2015)."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461931"},{"key":"e_1_2_2_3_1","volume-title":"Denoising of dynamic 3D meshes via low-rank spectral analysis. Computers & Graphics","author":"Arvanitis Gerasimos","year":"2019","unstructured":"Gerasimos Arvanitis, Aris S Lalos, and Konstantinos Moustakas. 2019. Denoising of dynamic 3D meshes via low-rank spectral analysis. Computers & Graphics (2019)."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2007.01059.x"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12178"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Stephen Boyd Neal Parikh Eric Chu Borja Peleato Jonathan Eckstein et al. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends\u00ae in Machine learning 3 1 (2011) 1--122.","DOI":"10.1561\/2200000016"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex optimization.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_2_8_1","unstructured":"Derek Bradley. 2006. Deforming Developable Surfaces."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2017.03.004"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970395"},{"key":"e_1_2_2_11_1","volume-title":"An introduction to compressive sampling [a sensing\/sampling paradigm that goes against the common knowledge in data acquisition]","author":"Cand\u00e8s Emmanuel J","year":"2008","unstructured":"Emmanuel J Cand\u00e8s and Michael B Wakin. 2008. An introduction to compressive sampling [a sensing\/sampling paradigm that goes against the common knowledge in data acquisition]. IEEE signal processing magazine 25, 2 (2008), 21--30."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/gmip.1999.0487"},{"key":"e_1_2_2_13_1","volume-title":"Methods of Mathematical Physics: Partial Differential Equations","author":"Courant Richard","unstructured":"Richard Courant and David Hilbert. 2008. Methods of Mathematical Physics: Partial Differential Equations. John Wiley & Sons."},{"key":"e_1_2_2_14_1","volume-title":"de Lima and Helton Hideraldo B\u00edscaro","author":"Jos\u00e9 Paulo","year":"2015","unstructured":"Jos\u00e9 Paulo R. de Lima and Helton Hideraldo B\u00edscaro. 2015. Compressive Representation of Three-dimensional Models. SBC Journal on Interactive Systems (2015)."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2006.00982.x"},{"key":"e_1_2_2_16_1","volume-title":"Saarland Universitesi","author":"Didas Stephan","year":"2004","unstructured":"Stephan Didas and Joachim Weickert. 2004. Higher order variational methods for noise removal in signals and images. Saarbr\u00fccken, Saarland Universitesi (2004)."},{"key":"e_1_2_2_17_1","volume-title":"Programming curvature using origami tessellations. Nature Materials 15 (01","author":"Dudte Levi","year":"2016","unstructured":"Levi Dudte, Etienne Vouga, Tomohiro Tachi, and Lakshminarayanan Mahadevan. 2016. Programming curvature using origami tessellations. Nature Materials 15 (01 2016)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2001.945730"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(03)00105-2"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461965"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2005.2"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Jin Huang Tengfei Jiang Zeyun Shi Yiying Tong Hujun Bao and Mathieu Desbrun. 2014. L1-Based Construction of Polycube Maps from Complex Shapes. ACM Trans. Graph. (2014).","DOI":"10.1145\/2602141"},{"key":"e_1_2_2_23_1","unstructured":"Alec Jacobson et al. 2016. gptoolbox: Geometry Processing Toolbox. http:\/\/github.com\/alecjacobson\/gptoolbox."},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo et al. 2018. libigl: A simple C++ geometry processing library. http:\/\/libigl.github.io\/libigl\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_25_1","volume-title":"D-charts: Quasi-developable mesh segmentation. In Computer Graphics Forum","author":"Julius Dan","year":"2005","unstructured":"Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-charts: Quasi-developable mesh segmentation. In Computer Graphics Forum, Vol. 24. Wiley Online Library, 581--590."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2749458"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.250917"},{"key":"e_1_2_2_28_1","volume-title":"ACM transactions on graphics (TOG)","author":"Kilian Martin","unstructured":"Martin Kilian, Simon Fl\u00f6ry, Zhonggui Chen, Niloy J Mitra, Alla Sheffer, and Helmut Pottmann. 2008. Curved folding. In ACM transactions on graphics (TOG), Vol. 27. ACM, 75."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcde.2015.07.001"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(98)00015-3"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276405"},{"key":"e_1_2_2_32_1","unstructured":"Hsueh-Ti Derek Liu and Alec Jacobson. 2019. Cubic Stylization. ACM Trans. Graph. (2019)."},{"key":"e_1_2_2_33_1","volume-title":"Computer Graphics Forum","author":"Liu Ligang","unstructured":"Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J Gortler. 2008. A local\/global approach to mesh parameterization. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1495--1504."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141941"},{"key":"e_1_2_2_35_1","volume-title":"Low Rank Matrix Approximation for Geometry Filtering. CoRR abs\/1803.06783","author":"Lu Xuequan","year":"2018","unstructured":"Xuequan Lu, Scott Schaefer, Jun Luo, Lizhuang Ma, and Ying He. 2018. Low Rank Matrix Approximation for Geometry Filtering. CoRR abs\/1803.06783 (2018). arXiv:1803.06783 http:\/\/arxiv.org\/abs\/1803.06783"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Tomohiko Mukai and Shigeru Kuriyama. 2016. Efficient dynamic skinning with low-rank helper bone controllers. ACM Trans. Graph. (2016).","DOI":"10.1145\/2897824.2925905"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2462010"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Barrett O'Neill. 1966. Elementary differential geometry.","DOI":"10.1016\/B978-1-4832-3170-9.50011-7"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2016.05.007"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.1478"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1648394.1648502"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(94)00031-M"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360675"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(99)00012-6"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180494"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Michael Rabinovich Tim Hoffmann and Olga Sorkine-Hornung. 2018b. The shape space of discrete orthogonal geodesic nets. In SIGGRAPH Asia 2018 Technical Papers. ACM 228.","DOI":"10.1145\/3272127.3275088"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356531"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(89)90111-5"},{"key":"e_1_2_2_49_1","volume-title":"SGP'07-5th Eurographics Symposium on Geometry Processing. Eurographics Association, 163--172","author":"Rose Kenneth","year":"2007","unstructured":"Kenneth Rose, Alla Sheffer, Jamie Wither, Marie-Paule Cani, and Boris Thibert. 2007. Developable surfaces from arbitrary sketched boundaries. In SGP'07-5th Eurographics Symposium on Geometry Processing. Eurographics Association, 163--172."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-2789(92)90242-F"},{"key":"e_1_2_2_51_1","volume-title":"Multiscale Biharmonic Kernels. Comput. Graph. Forum 30, 5","author":"Rustamov Raif M.","year":"2011","unstructured":"Raif M. Rustamov. 2011. Multiscale Biharmonic Kernels. Comput. Graph. Forum 30, 5 (2011)."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2829948"},{"key":"e_1_2_2_53_1","volume-title":"Computer Graphics Forum","author":"Solomon Justin","unstructured":"Justin Solomon, Etienne Vouga, Max Wardetzky, and Eitan Grinspun. 2012. Flexible developable surfaces. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1567--1576."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201303"},{"key":"e_1_2_2_55_1","doi-asserted-by":"crossref","unstructured":"Oded Stein Eitan Grinspun Max Wardetzky and Alec Jacobson. 2018b. Natural Boundary Conditions for Smoothing in Geometry Processing. ACM Trans. Graph. (2018).","DOI":"10.1145\/3186564"},{"key":"e_1_2_2_56_1","volume-title":"OSQP: An Operator Splitting Solver for Quadratic Programs. ArXiv e-prints (Nov.","author":"Stellato B.","year":"2017","unstructured":"B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd. 2017. OSQP: An Operator Splitting Solver for Quadratic Programs. ArXiv e-prints (Nov. 2017). arXiv:math.OC\/1711.08013"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/11802914_11"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2832906"},{"key":"e_1_2_2_59_1","doi-asserted-by":"crossref","unstructured":"Etienne Vouga Mathias H\u00f6binger Johannes Wallner and Helmut Pottmann. 2012. Design of Self-supporting Surfaces. ACM Trans. Graph. (2012).","DOI":"10.1145\/2185520.2335438"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356541"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2018.2865363"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2013.05.008"},{"key":"e_1_2_2_63_1","doi-asserted-by":"crossref","unstructured":"Juyong Zhang Bailin Deng Yang Hong Yue Peng Wenjie Qin and Ligang Liu. 2019. Static\/Dynamic Filtering for Mesh Geometry. IEEE TVCG (2019).","DOI":"10.1109\/TVCG.2018.2816926"},{"key":"e_1_2_2_64_1","volume-title":"Local Barycentric Coordinates. ACM Trans. Graph. 33","author":"Zhang Juyong","year":"2014","unstructured":"Juyong Zhang, Bailin Deng, Zishun Liu, Giuseppe Patan\u00e8, Sofien Bouaziz, Kai Hormann, and Ligang Liu. 2014. Local Barycentric Coordinates. ACM Trans. Graph. 33 (2014)."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392419","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386569.3392419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T05:36:21Z","timestamp":1750829781000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,12]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3386569.3392419"],"URL":"https:\/\/doi.org\/10.1145\/3386569.3392419","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,12]]},"assertion":[{"value":"2020-08-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}