{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T02:57:42Z","timestamp":1794279462003,"version":"4.9.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T00:00:00Z","timestamp":1721347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2024,7,19]]},"abstract":"<jats:p>Point containment queries for regions bound by watertight geometric surfaces, i.e., closed and without self-intersections, can be evaluated straightforwardly with a number of well-studied algorithms. When this assumption on domain geometry is not met, such methods are either unusable, or prone to misclassifications that can lead to cascading errors in downstream applications. More robust point classification schemes based on generalized winding numbers have been proposed, as they are indifferent to these imperfections. However, existing algorithms are limited to point clouds and collections of linear elements. We extend this methodology to encompass more general curved shapes with an algorithm that evaluates the winding number scalar field over unstructured collections of rational parametric curves. In particular, we evaluate the winding number for each curve independently, making the derived containment query robust to how the curves are arranged. We ensure geometric fidelity in our queries by treating each curve as equivalent to an adaptively constructed polyline that provably has the same generalized winding number at the point of interest. Our algorithm is numerically stable for points that are arbitrarily close to the model, and explicitly treats points that are coincident with curves. We demonstrate the improvements in computational performance granted by this method over conventional techniques as well as the robustness induced by its application.<\/jats:p>","DOI":"10.1145\/3658228","type":"journal-article","created":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T10:47:57Z","timestamp":1721386077000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Robust Containment Queries over Collections of Rational Parametric Curves via Generalized Winding Numbers"],"prefix":"10.1145","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8219-4360","authenticated-orcid":false,"given":"Jacob","family":"Spainhour","sequence":"first","affiliation":[{"name":"University of Colorado Boulder, Boulder, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4154-0911","authenticated-orcid":false,"given":"David","family":"Gunderman","sequence":"additional","affiliation":[{"name":"Indiana University School of Medicine, West Lafayette, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6649-8022","authenticated-orcid":false,"given":"Kenneth","family":"Weiss","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory, Livermore, United States of America"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,7,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276415"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2022.115742"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201337"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2016.07.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095878.1095883"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","unstructured":"A. Capps R. Carson B. Corbett N. Elliott J. Essman B. Gunney B. Han C. Harrison R. Hornung M. Larsen A. Moody E. Pauli R. Settgast L. Taylor K. Weiss C. White B. Whitlock M. Yang and G. Zagaris. 2017--2024. Axom: CS infrastructure components for HPC applications. https:\/\/github.com\/llnl\/axom. 10.11578\/dc.20210915.2","DOI":"10.11578\/dc.20210915.2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","unstructured":"P. C. P. Carvalho and P. R. Cavalcanti. 1995. II.2 - Point in Polyhedron Testing Using Spherical Polygons. In Graphics Gems V A. W. Paeth (Ed.). Academic Press Boston 42--49. 10.1016\/B978-0-12-543457-7.50015-2","DOI":"10.1016\/B978-0-12-543457-7.50015-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090122.1090144"},{"key":"e_1_2_1_10_1","unstructured":"G. E. Farin. 2001. Curves and surfaces for CAGD: A practical guide. Morgan Kaufmann."},{"key":"e_1_2_1_11_1","volume-title":"High-Order Spatial Discretization and Numerical Integration Schemes for Curved Geometries. Ph. D. Dissertation. Department of Applied Mathematics","author":"Gunderman D.","unstructured":"D. Gunderman. 2021. High-Order Spatial Discretization and Numerical Integration Schemes for Curved Geometries. Ph. D. Dissertation. Department of Applied Mathematics, University of Colorado Boulder."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102944"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-336156-1.50013-6"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9991(74)90051-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00012-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392458"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","unstructured":"L. Klinteberg and A. H. Barnett. 2020. Accurate quadrature of nearly singular line integrals in two and three dimensions by singularity swapping. BIT Numerical Mathematics 61 (07 2020) 1--36. 10.1007\/s10543-020-00820-5","DOI":"10.1007\/s10543-020-00820-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(03)00021-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11831-017-9220-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964932"},{"key":"e_1_2_1_22_1","unstructured":"A. A. Mezentsev and T. Woehler. 1999. Methods and Algorithms of Automated CAD Repair for Incremental Surface Meshing. In IMR. Citeseer 299--309."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/97880.97916"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2003.1196006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399504.1360691"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2514\/6.2021-2992"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","unstructured":"N. Patrikalakis and T. Maekawa. 2010. Shape Interrogation for Computer Aided Design and Manufacturing. 10.1007\/978-3-642-04074-0","DOI":"10.1007\/978-3-642-04074-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"L. Piegl and W. Tiller. 1996. The NURBS book. Springer Science & Business Media.","DOI":"10.1007\/978-3-642-97385-7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392374"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360678"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(90)90039-F"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555441"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1002\/fld.1711"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.3164"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/368637.368653"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2022.108026"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2014.07.014"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530181"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings 25th International Meshing Roundtable (IMR '16)","author":"Weiss K.","unstructured":"K. Weiss, G. Zagaris, R. Rieben, and A. Cook. 2016. Spatially accelerated shape embedding in multimaterial simulations. In Proceedings 25th International Meshing Roundtable (IMR '16), S. Canann (Ed.). Washington, D.C."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2022.3153677"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:04:16Z","timestamp":1750277056000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,19]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,7,19]]}},"alternative-id":["10.1145\/3658228"],"URL":"https:\/\/doi.org\/10.1145\/3658228","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,19]]},"assertion":[{"value":"2024-07-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}