{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T07:21:14Z","timestamp":1783063274737,"version":"3.54.6"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T00:00:00Z","timestamp":1783036800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2212290"],"award-info":[{"award-number":["2212290"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2504890"],"award-info":[{"award-number":["2504890"]}],"id":[{"id":"10.13039\/100000001","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":[[2026,7,3]]},"abstract":"<jats:p>\n                    This paper describes a strategy for vectorizing 3D scenes with proper occlusion. Given a collection of curves derived from 3D geometry (silhouettes, isolines, material boundaries, etc.), we produce a 2D vector image that partitions the image plane into a\n                    <jats:italic toggle=\"yes\">planar map<\/jats:italic>\n                    of solid shaded regions. The method is agnostic to surface representation, handling for instance curves obtained from polygonal, NURBS or subdivision surfaces. The output likewise supports curve segments of arbitrary parametric type. Our key observation is that the spatial hierarchy used to accelerate curve-curve intersections provides the fundamental representation of the planar map itself. This approach provides geometric flexibility, since general curve-curve intersection problems are replaced with simpler curve-line intersection. Simultaneously, it provides robustness since cells of the spatial hierarchy define a well-defined planar map, even in the presence of numerical errors. For instance, it automatically handles \"curve soup\" where segment endpoints are not explicitly connected in the input file. The method scales to a large number of primitives, and is output sensitive: it resolves intersections only up to a user-defined precision\u2014while still providing topologically valid output. We evaluate the method on a collection of challenging tests, showing that it is both more robust and orders of magnitude more efficient than existing curve arrangement techniques, such as those found in CGAL.\n                  <\/jats:p>","DOI":"10.1145\/3811357","type":"journal-article","created":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T07:05:51Z","timestamp":1783062351000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Robust Planar Maps for 3D Vectorization"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-3607-9883","authenticated-orcid":false,"given":"Robert","family":"Fuchs","sequence":"first","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2772-7034","authenticated-orcid":false,"given":"Keenan","family":"Crane","sequence":"additional","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA"},{"name":"Roblox, San Mateo, California, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,3]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"129","article-title":"Analytical Forward Projection for Axial Non-central Dioptric and Catadioptric Cameras","volume":"2010","author":"Agrawal Amit","year":"2010","unstructured":"Amit Agrawal, Yuichi Taguchi, and Srikumar Ramalingam. 2010. Analytical Forward Projection for Axial Non-central Dioptric and Catadioptric Cameras. In Computer Vision - ECCV 2010. 129\u2013143.","journal-title":"Computer Vision - ECCV"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800196.806007"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276415"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/67449.67511"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1561\/0600000075"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","article-title":"Algorithms for reporting and counting geometric intersections","volume":"100","author":"Ottmann Bentley","year":"1979","unstructured":"Bentley and Ottmann. 1979. Algorithms for reporting and counting geometric intersections. IEEE Transactions on computers 100, 9 (1979), 643\u2013647.","journal-title":"IEEE Transactions on computers"},{"key":"e_1_2_2_7_1","volume-title":"Computer Graphics Forum","author":"Bernstein Gilbert","unstructured":"Gilbert Bernstein and Don Fussell. 2009. Fast, exact, linear booleans. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1269\u20131278."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588432.3591547"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_2_10_1","unstructured":"Keenan Crane. 2013. Illustrating Geometry. https:\/\/www.cs.cmu.edu\/~kmcrane\/IllustratingGeometry.pdf. Lecture slides."},{"key":"e_1_2_2_11_1","volume-title":"Shadow algorithms for computer graphics. Acm siggraph computer graphics 11, 2","author":"Crow Franklin C","year":"1977","unstructured":"Franklin C Crow. 1977. Shadow algorithms for computer graphics. Acm siggraph computer graphics 11, 2 (1977), 242\u2013248."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601169"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13622"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576246.1531389"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2008.01258.x"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1201\/b14581"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653865"},{"key":"e_1_2_2_19_1","volume-title":"An outsider's inside view of the Challenger inquiry. Physics today 41, 2","author":"Feynman Richard P","year":"1988","unstructured":"Richard P Feynman. 1988. An outsider's inside view of the Challenger inquiry. Physics today 41, 2 (1988), 26\u201337."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48318-7_14"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661274"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/74334.74369"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.11396894"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658201"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-336156-1.50013-6"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236246.1236282"},{"key":"e_1_2_2_27_1","unstructured":"Angus Johnson. 2025. Clipper2. https:\/\/github.com\/AngusJohnson\/Clipper2"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658215"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/15922.15904"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3544778"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576246.1531390"},{"key":"e_1_2_2_32_1","first-page":"2","article-title":"Soft Stacking","volume":"31","author":"Mccann James","year":"2012","unstructured":"James Mccann and Nancy Pollard. 2012. Soft Stacking. Proceedings of Computer Graphics Forum 31, 2 (May 2012), 469 \u2013 478.","journal-title":"Proceedings of Computer Graphics Forum"},{"key":"e_1_2_2_33_1","volume-title":"Graphics Interface","author":"Naylor Bruce","unstructured":"Bruce Naylor and Lois Rogers. 1995. Constructing Partitioning Trees from Bezier-Curves for Efficient Intersections & Visibility. In Graphics Interface. Canadian Information Processing Society, 44\u201344."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409088"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.15042"},{"key":"e_1_2_2_36_1","unstructured":"Peter Selinger. 2003. Potrace: a polygon-based tracing algorithm."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37421"},{"key":"e_1_2_2_38_1","volume-title":"Requicha","author":"Voelcker Herbert B.","year":"1977","unstructured":"Herbert B. Voelcker and Aristides A. G. Requicha. 1977. Constructive Solid Geometry. Technical Report Technical Memorandum 25. University of Rochester, Production Automation Project, Rochester, N.Y. http:\/\/hdl.handle.net\/1802\/26358"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192184"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237287"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925901"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/abs\/10.1145\/3811357","content-type":"text\/html","content-version":"vor","intended-application":"syndication"}],"deposited":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T07:11:36Z","timestamp":1783062696000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3811357"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,3]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,7,3]]}},"alternative-id":["10.1145\/3811357"],"URL":"https:\/\/doi.org\/10.1145\/3811357","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,3]]},"assertion":[{"value":"2026-01-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-07-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}