{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:12:41Z","timestamp":1750219961851,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T00:00:00Z","timestamp":1669766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>We port Boolean set operations between 2D shapes to surfaces of any genus, with any number of open boundaries. We combine shapes bounded by sets of freely intersecting loops, consisting of geodesic lines and cubic B\u00e9zier splines lying on a surface. We compute the arrangement of shapes directly on the surface and assign integer labels to the cells of such arrangement. Differently from the Euclidean case, some arrangements on a manifold may be inconsistent. We detect inconsistent arrangements and help the user to resolve them. Also, we extend to the manifold setting recent work on Boundary-Sampled Halfspaces, thus supporting operations more general than standard Booleans, which are well defined on inconsistent arrangements, too. Our implementation discretizes the input shapes into polylines at an arbitrary resolution, independent of the level of resolution of the underlying mesh. We resolve the arrangement inside each triangle of the mesh independently and combine the results to reconstruct both the boundaries and the interior of each cell in the arrangement. We reconstruct the control points of curves bounding cells, in order to free the result from discretization and provide an output in vector format. We support interactive usage, editing shapes consisting up to 100k line segments on meshes of up to 1M triangles.<\/jats:p>","DOI":"10.1145\/3550454.3555466","type":"journal-article","created":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T21:19:07Z","timestamp":1669843147000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["BoolSurf"],"prefix":"10.1145","volume":"41","author":[{"given":"Marzia","family":"Riso","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Italy"}]},{"given":"Giacomo","family":"Nazzaro","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}]},{"given":"Enrico","family":"Puppo","sequence":"additional","affiliation":[{"name":"University of Genoa, Italy"}]},{"given":"Alec","family":"Jacobson","sequence":"additional","affiliation":[{"name":"University of Toronto, Adobe Research, Canada"}]},{"given":"Qingnan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Fabio","family":"Pellacini","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}]}],"member":"320","published-online":{"date-parts":[[2022,11,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Adobe inc. 2021. Adobe Illustrator. Adobe inc. https:\/\/adobe.com\/products\/illustrator"},{"key":"e_1_2_2_2_1","volume-title":"CDT: Constrained Delaunay Triangulation. https:\/\/github.com\/artem-ogre\/CDT","author":"Amirkhanov A.","year":"2022","unstructured":"A. Amirkhanov. 2022. CDT: Constrained Delaunay Triangulation. https:\/\/github.com\/artem-ogre\/CDT"},{"key":"e_1_2_2_3_1","volume-title":"Indirect Predicates for Geometric Constructions. Computer-Aided Design 126","author":"Attene M.","year":"2020","unstructured":"M. Attene. 2020. Indirect Predicates for Geometric Constructions. Computer-Aided Design 126 (2020), 102856:1--102856:9."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201337"},{"volume-title":"Linear Booleans. In Proc. of the Symp. on Geom. Proc. 1269--1278","author":"Bernstein G.","key":"e_1_2_2_5_1","unstructured":"G. Bernstein and D. Fussell. 2009. Fast, Exact, Linear Booleans. In Proc. of the Symp. on Geom. Proc. 1269--1278."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01609.x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925880"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570697"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459870"},{"key":"e_1_2_2_11_1","first-page":"1038","article-title":"Greedy optimal homotopy and homology generators. In Proc. 16th ACM-SIAM Symp","volume":"5","author":"Erickson J.","year":"2005","unstructured":"J. Erickson and K. Whittlesey. 2005. Greedy optimal homotopy and homology generators. In Proc. 16th ACM-SIAM Symp. Disc. Alg., Vol. 5. 1038--1046.","journal-title":"Disc. Alg."},{"volume-title":"SCG '93","author":"Fortune Steven","key":"e_1_2_2_12_1","unstructured":"Steven Fortune and Christopher J. Van Wyk. 1993. Efficient exact arithmetic for computational geometry. In SCG '93."},{"volume-title":"Algebraic Topology: A First Course","author":"Fulton W.","key":"e_1_2_2_13_1","unstructured":"W. Fulton. 1995. Algebraic Topology: A First Course. Springer, New York, USA."},{"key":"e_1_2_2_14_1","volume-title":"Proc. 11th Europ. Symp. on Alg. LNCS","volume":"2832","author":"Granados M.","unstructured":"M. Granados, P. Hachenberger, L. Hert, S. adn Kettner, K. Mehlhorn, and M. Seel. 2003. Boolean operations on 3d selective NEF complexes: Data structure, algorithms, and implementation. In Proc. 11th Europ. Symp. on Alg. LNCS, Vol. 2832. Springer, 174--186."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1990-1024774-2"},{"key":"e_1_2_2_16_1","unstructured":"A Hatcher. 2002. Algebraic Topology. Cambridge UK."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323011"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_2_20_1","unstructured":"A. Johnson. 2014. Clipper - an open source freeware library for clipping and offsetting lines and polygons. http:\/\/www.angusj.com\/delphi\/clipper.php"},{"volume-title":"Metafont: the Program","author":"Knuth D.","key":"e_1_2_2_21_1","unstructured":"D. Knuth. 1986. Metafont: the Program. Addison-Wesley."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.10.004"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","unstructured":"C. Mancinelli G. Nazzaro F. Pellacini and E. Puppo. 2022. B\/Surf: Interactive B\u00e9zier Splines on Surfaces. IEEE Trans. VIs. Comp. Graph (2022). to appear. 10.1109\/TVCG.2022.3171179","DOI":"10.1109\/TVCG.2022.3171179"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2022.04.007"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01264913"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/97880.97892"},{"key":"e_1_2_2_27_1","article-title":"geoTangle: Interactive Design of Geodesic Tangle Patterns on Surfaces","volume":"41","author":"Nazzaro G.","year":"2021","unstructured":"G. Nazzaro, E. Puppo, and F. Pellacini. 2021. geoTangle: Interactive Design of Geodesic Tangle Patterns on Surfaces. ACM Trans. Graph. 41, 2 (2021), 12:1--12:17.","journal-title":"ACM Trans. Graph."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409060.1409088"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.5802\/aif.100"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417839"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/129902.129906"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460775"},{"key":"e_1_2_2_34_1","unstructured":"R. Wein E. Berberich E. Fogel D. Halperin M. Hemmer O. Salzman and Zukerman B. 2021. CGAL 5.3.1 - 2D Arrangements. https:\/\/doc.cgal.org\/latest\/Arrangement_on_surface_2\/index.html"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.119"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925901"},{"key":"e_1_2_2_37_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Q.","year":"2016","unstructured":"Q. Zhou and A. Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv:1605.04797","journal-title":"A Dataset of"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3550454.3555466","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3550454.3555466","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:11Z","timestamp":1750182551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3550454.3555466"}},"subtitle":["Boolean Operations on Surfaces"],"short-title":[],"issued":{"date-parts":[[2022,11,30]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1145\/3550454.3555466"],"URL":"https:\/\/doi.org\/10.1145\/3550454.3555466","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2022,11,30]]},"assertion":[{"value":"2022-11-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}