{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T02:13:31Z","timestamp":1774059211128,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["RI-1618685"],"award-info":[{"award-number":["RI-1618685"]}]},{"DOI":"10.13039\/100004344","name":"Adobe Systems","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100004344","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2021,8,31]]},"abstract":"<jats:p>We present a novel representation of solid models for shape design. Like Constructive Solid Geometry (CSG), the solid shape is constructed from a set of halfspaces without the need for an explicit boundary structure. Instead of using Boolean expressions as in CSG, the shape is defined by sparsely placed samples on the boundary of each halfspace. This representation, called Boundary-Sampled Halfspaces (BSH), affords greater agility and expressiveness than CSG while simplifying the reverse engineering process. We discuss theoretical properties of the representation and present practical algorithms for boundary extraction and conversion from other representations. Our algorithms are demonstrated on both 2D and 3D examples.<\/jats:p>","DOI":"10.1145\/3450626.3459870","type":"journal-article","created":{"date-parts":[[2021,7,20]],"date-time":"2021-07-20T00:04:26Z","timestamp":1626739466000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Boundary-sampled halfspaces"],"prefix":"10.1145","volume":"40","author":[{"given":"Xingyi","family":"Du","sequence":"first","affiliation":[{"name":"Washington University in St. Louis"}]},{"given":"Qingnan","family":"Zhou","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Nathan","family":"Carr","sequence":"additional","affiliation":[{"name":"Adobe Research"}]},{"given":"Tao","family":"Ju","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis"}]}],"member":"320","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Handbook of computational geometry","author":"Agarwal Pankaj K","unstructured":"Pankaj K Agarwal and Micha Sharir . 2000. Arrangements and their applications . In Handbook of computational geometry . Elsevier , 49--119. Pankaj K Agarwal and Micha Sharir. 2000. Arrangements and their applications. In Handbook of computational geometry. Elsevier, 49--119."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2008.06.009"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3376918"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2331684.2331698"},{"key":"e_1_2_2_5_1","volume-title":"Computer Graphics Forum","author":"Berger Matthew","unstructured":"Matthew Berger , Andrea Tagliasacchi , Lee M Seversky , Pierre Alliez , Gael Guennebaud , Joshua A Levine , Andrei Sharf , and Claudio T Silva . 2017. A survey of surface reconstruction from point clouds . In Computer Graphics Forum , Vol. 36 . Wiley Online Library , 301--329. Matthew Berger, Andrea Tagliasacchi, Lee M Seversky, Pierre Alliez, Gael Guennebaud, Joshua A Levine, Andrei Sharf, and Claudio T Silva. 2017. A survey of surface reconstruction from point clouds. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 301--329."},{"key":"e_1_2_2_6_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--1278. Gilbert Bernstein and Don Fussell. 2009. Fast, exact, linear booleans. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1269--1278."},{"key":"e_1_2_2_7_1","volume-title":"Martin de La Gorce, and Renaud Marlet","author":"Boulch Alexandre","year":"2014","unstructured":"Alexandre Boulch , Martin de La Gorce, and Renaud Marlet . 2014 . Piecewise-planar 3D reconstruction with edge and corner regularization. In Computer Graphics Forum, Vol. 33 . Wiley Online Library , 55--64. Alexandre Boulch, Martin de La Gorce, and Renaud Marlet. 2014. Piecewise-planar 3D reconstruction with edge and corner regularization. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 55--64."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/781606.781629"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383266"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(89)90026-5"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5539824"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR42600.2020.00012"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_2_14_1","volume-title":"QuickCSG: Fast Arbitrary Boolean Combinations of N Solids. arXiv preprint arXiv:1706.01558","author":"Douze Matthijs","year":"2017","unstructured":"Matthijs Douze , Jean-S\u00e9bastien Franco , and Bruno Raffin . 2017. QuickCSG: Fast Arbitrary Boolean Combinations of N Solids. arXiv preprint arXiv:1706.01558 ( 2017 ). Matthijs Douze, Jean-S\u00e9bastien Franco, and Bruno Raffin. 2017. QuickCSG: Fast Arbitrary Boolean Combinations of N Solids. arXiv preprint arXiv:1706.01558 (2017)."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275006"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_56"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2016.01.001"},{"key":"e_1_2_2_19_1","volume-title":"Heterogeneous objects modelling and applications","author":"Fayolle Pierre-Alain","unstructured":"Pierre-Alain Fayolle , Alexander Pasko , Elena Kartasheva , Christophe Rosenberger , and Christian Toinard . 2008. Automation of the volumetric models construction . In Heterogeneous objects modelling and applications . Springer , 214--238. Pierre-Alain Fayolle, Alexander Pasko, Elena Kartasheva, Christophe Rosenberger, and Christian Toinard. 2008. Automation of the volumetric models construction. In Heterogeneous objects modelling and applications. Springer, 214--238."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.11.004"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24855-2_110"},{"key":"e_1_2_2_22_1","unstructured":"Christoph Martin Hoffmann. 1989. Geometric and solid modeling. (1989).  Christoph Martin Hoffmann. 1989. Geometric and solid modeling. (1989)."},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3306346.3322994","article-title":"Variational implicit point set surfaces","volume":"38","author":"Huang Zhiyang","year":"2019","unstructured":"Zhiyang Huang , Nathan Carr , and Tao Ju . 2019 . Variational implicit point set surfaces . ACM Transactions on Graphics (TOG) 38 , 4 (2019), 1 -- 13 . Zhiyang Huang, Nathan Carr, and Tao Ju. 2019. Variational implicit point set surfaces. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1--13.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_24_1","volume-title":"Jose Alonso Ybanez Zepeda, and Tamy Boubekeur","author":"Kaiser Adrien","year":"2019","unstructured":"Adrien Kaiser , Jose Alonso Ybanez Zepeda, and Tamy Boubekeur . 2019 . A survey of simple geometric primitives detection methods for captured 3D data. In Computer Graphics Forum, Vol. 38 . Wiley Online Library , 167--196. Adrien Kaiser, Jose Alonso Ybanez Zepeda, and Tamy Boubekeur. 2019. A survey of simple geometric primitives detection methods for captured 3D data. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 167--196."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(03)00060-5"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/3DV.2019.00067"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44199-2_43"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0055697"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1055715.1646512"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2004.87"},{"key":"e_1_2_2_31_1","volume-title":"Indoor scene reconstruction using feature sensitive primitive extraction and graph-cut. ISPRS journal of photogrammetry and remote sensing 90","author":"Oesau Sven","year":"2014","unstructured":"Sven Oesau , Florent Lafarge , and Pierre Alliez . 2014. Indoor scene reconstruction using feature sensitive primitive extraction and graph-cut. ISPRS journal of photogrammetry and remote sensing 90 ( 2014 ), 68--82. Sven Oesau, Florent Lafarge, and Pierre Alliez. 2014. Indoor scene reconstruction using feature sensitive primitive extraction and graph-cut. ISPRS journal of photogrammetry and remote sensing 90 (2014), 68--82."},{"key":"e_1_2_2_32_1","volume-title":"Function representation in geometric modeling: concepts, implementation and applications. The visual computer 11, 8","author":"Pasko Alexander","year":"1995","unstructured":"Alexander Pasko , Valery Adzhiev , Alexei Sourin , and Vladimir Savchenko . 1995. Function representation in geometric modeling: concepts, implementation and applications. The visual computer 11, 8 ( 1995 ), 429--446. Alexander Pasko, Valery Adzhiev, Alexei Sourin, and Vladimir Savchenko. 1995. Function representation in geometric modeling: concepts, implementation and applications. The visual computer 11, 8 (1995), 429--446."},{"key":"e_1_2_2_33_1","volume-title":"Computer Graphics Forum","author":"Pavi\u0107 Darko","unstructured":"Darko Pavi\u0107 , Marcel Campen , and Leif Kobbelt . 2010. Hybrid booleans . In Computer Graphics Forum , Vol. 29 . Wiley Online Library , 75--87. Darko Pavi\u0107, Marcel Campen, and Leif Kobbelt. 2010. Hybrid booleans. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 75--87."},{"key":"e_1_2_2_34_1","unstructured":"Aristides AG Requicha and Herbert B Voelcker. 1977. Constructive solid geometry. (1977).  Aristides AG Requicha and Herbert B Voelcker. 1977. Constructive solid geometry. (1977)."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/356827.356833"},{"key":"e_1_2_2_36_1","unstructured":"Jaroslaw Rossignac and Aristides Requicha. 1984. Constant-radius blending in solid modelling. (1984).  Jaroslaw Rossignac and Aristides Requicha. 1984. Constant-radius blending in solid modelling. (1984)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(86)90017-8"},{"key":"e_1_2_2_39_1","volume-title":"Computer graphics forum","author":"Schnabel Ruwen","unstructured":"Ruwen Schnabel , Roland Wahl , and Reinhard Klein . 2007. Efficient RANSAC for point-cloud shape detection . In Computer graphics forum , Vol. 26 . Wiley Online Library , 214--226. Ruwen Schnabel, Roland Wahl, and Reinhard Klein. 2007. Efficient RANSAC for point-cloud shape detection. In Computer graphics forum, Vol. 26. Wiley Online Library, 214--226."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.02.007"},{"key":"e_1_2_2_41_1","volume-title":"Computer graphics forum","author":"Shamir Ariel","unstructured":"Ariel Shamir . 2008. A survey on mesh segmentation techniques . In Computer graphics forum , Vol. 27 . Wiley Online Library , 1539--1556. Ariel Shamir. 2008. A survey on mesh segmentation techniques. In Computer graphics forum, Vol. 27. Wiley Online Library, 1539--1556."},{"key":"e_1_2_2_42_1","volume-title":"Solid Modeling. Handbook of computer aided geometric design 20","author":"Shapiro Vadim","year":"2002","unstructured":"Vadim Shapiro . 2002. Solid Modeling. Handbook of computer aided geometric design 20 ( 2002 ), 473--518. Vadim Shapiro. 2002. Solid Modeling. Handbook of computer aided geometric design 20 (2002), 473--518."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(91)90077-A"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/169728.169723"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/11595014_15"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2006.11.003"},{"key":"e_1_2_2_47_1","volume-title":"ARTICLE","author":"Verdie Yannick","year":"2015","unstructured":"Yannick Verdie , Florent Lafarge , and Pierre Alliez . 2015. LOD generation for urban scenes. ACM Transactions on Graphics 34 , ARTICLE ( 2015 ), 30. Yannick Verdie, Florent Lafarge, and Pierre Alliez. 2015. LOD generation for urban scenes. ACM Transactions on Graphics 34, ARTICLE (2015), 30."},{"key":"e_1_2_2_48_1","volume-title":"Approximate boolean operations on large polyhedral solids with partial mesh reconstruction","author":"Wang Charlie CL","year":"2010","unstructured":"Charlie CL Wang . 2010. Approximate boolean operations on large polyhedral solids with partial mesh reconstruction . IEEE transactions on visualization and computer graphics 17, 6 ( 2010 ), 836--849. Charlie CL Wang. 2010. Approximate boolean operations on large polyhedral solids with partial mesh reconstruction. IEEE transactions on visualization and computer graphics 17, 6 (2010), 836--849."},{"key":"e_1_2_2_49_1","volume-title":"Computer Graphics Forum","author":"Wu Qiaoyun","unstructured":"Qiaoyun Wu , Kai Xu , and Jun Wang . 2018. Constructing 3D CSG models from 3D raw point clouds . In Computer Graphics Forum , Vol. 37 . Wiley Online Library , 221--232. Qiaoyun Wu, Kai Xu, and Jun Wang. 2018. Constructing 3D CSG models from 3D raw point clouds. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 221--232."},{"key":"e_1_2_2_50_1","volume-title":"Computer Graphics Forum","author":"Wyvill Brian","unstructured":"Brian Wyvill , Andrew Guy , and Eric Galin . 1999. Extending the csg tree. warping, blending and boolean operations in an implicit surface modeling system . In Computer Graphics Forum , Vol. 18 . Wiley Online Library , 149--158. Brian Wyvill, Andrew Guy, and Eric Galin. 1999. Extending the csg tree. warping, blending and boolean operations in an implicit surface modeling system. In Computer Graphics Forum, Vol. 18. Wiley Online Library, 149--158."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.10.036"},{"key":"e_1_2_2_52_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2897824.2925901","article-title":"Mesh arrangements for solid geometry","volume":"35","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou , Eitan Grinspun , Denis Zorin , and Alec Jacobson . 2016 . Mesh arrangements for solid geometry . ACM Transactions on Graphics (TOG) 35 , 4 (2016), 1 -- 15 . Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1--15.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41095-016-0071-3"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450626.3459870","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450626.3459870","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3450626.3459870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:21Z","timestamp":1750191441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3450626.3459870"}},"subtitle":["a new representation for constructive solid modeling"],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":52,"aliases":["10.1145\/3476576.3476601"],"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8,31]]}},"alternative-id":["10.1145\/3450626.3459870"],"URL":"https:\/\/doi.org\/10.1145\/3450626.3459870","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,19]]},"assertion":[{"value":"2021-07-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}