[{"doi":"10.1111/j.1467-8659.2009.01609.x","title":"Exact and Robust (Self‐)Intersections for Polygonal Meshes","date_created":"2025-06-30T08:24:08Z","author":[{"orcid":"0000-0003-2340-3462","last_name":"Campen","full_name":"Campen, Marcel","id":"114904","first_name":"Marcel"},{"first_name":"Leif","last_name":"Kobbelt","full_name":"Kobbelt, Leif"}],"volume":29,"publisher":"Wiley","date_updated":"2025-07-14T12:35:44Z","citation":{"chicago":"Campen, Marcel, and Leif Kobbelt. “Exact and Robust (Self‐)Intersections for Polygonal Meshes.” <i>Computer Graphics Forum</i> 29, no. 2 (2010): 397–406. <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01609.x\">https://doi.org/10.1111/j.1467-8659.2009.01609.x</a>.","ieee":"M. Campen and L. Kobbelt, “Exact and Robust (Self‐)Intersections for Polygonal Meshes,” <i>Computer Graphics Forum</i>, vol. 29, no. 2, pp. 397–406, 2010, doi: <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01609.x\">10.1111/j.1467-8659.2009.01609.x</a>.","ama":"Campen M, Kobbelt L. Exact and Robust (Self‐)Intersections for Polygonal Meshes. <i>Computer Graphics Forum</i>. 2010;29(2):397-406. doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01609.x\">10.1111/j.1467-8659.2009.01609.x</a>","apa":"Campen, M., &#38; Kobbelt, L. (2010). Exact and Robust (Self‐)Intersections for Polygonal Meshes. <i>Computer Graphics Forum</i>, <i>29</i>(2), 397–406. <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01609.x\">https://doi.org/10.1111/j.1467-8659.2009.01609.x</a>","bibtex":"@article{Campen_Kobbelt_2010, title={Exact and Robust (Self‐)Intersections for Polygonal Meshes}, volume={29}, DOI={<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01609.x\">10.1111/j.1467-8659.2009.01609.x</a>}, number={2}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Campen, Marcel and Kobbelt, Leif}, year={2010}, pages={397–406} }","short":"M. Campen, L. Kobbelt, Computer Graphics Forum 29 (2010) 397–406.","mla":"Campen, Marcel, and Leif Kobbelt. “Exact and Robust (Self‐)Intersections for Polygonal Meshes.” <i>Computer Graphics Forum</i>, vol. 29, no. 2, Wiley, 2010, pp. 397–406, doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01609.x\">10.1111/j.1467-8659.2009.01609.x</a>."},"page":"397-406","intvolume":"        29","year":"2010","issue":"2","publication_status":"published","publication_identifier":{"issn":["0167-7055","1467-8659"]},"extern":"1","language":[{"iso":"eng"}],"user_id":"117512","department":[{"_id":"969"}],"_id":"60463","status":"public","abstract":[{"text":"<jats:title>Abstract</jats:title><jats:p>We present a new technique to implement operators that modify the topology of polygonal meshes at intersections and self‐intersections. Depending on the modification strategy, this effectively results in operators for Boolean combinations or for the construction of outer hulls that are suited for mesh repair tasks and accurate mesh‐based front tracking of deformable materials that split and merge. By combining an adaptive octree with nested binary space partitions (BSP), we can guarantee exactness (= correctness) and robustness (= completeness) of the algorithm while still achieving higher performance and less memory consumption than previous approaches. The efficiency and scalability in terms of runtime and memory is obtained by an operation localization scheme. We restrict the essential computations to those cells in the adaptive octree where intersections actually occur. Within those critical cells, we convert the input geometry into a plane‐based BSP‐representation which allows us to perform all computations exactly even with fixed precision arithmetics. We carefully analyze the precision requirements of the involved geometric data and predicates in order to guarantee correctness and show how minimal input mesh quantization can be used to safely rely on computations with standard floating point numbers. We properly evaluate our method with respect to precision, robustness, and efficiency.</jats:p>","lang":"eng"}],"type":"journal_article","publication":"Computer Graphics Forum"},{"extern":"1","language":[{"iso":"eng"}],"_id":"60464","department":[{"_id":"969"}],"user_id":"117512","abstract":[{"text":"<jats:title>Abstract</jats:title><jats:p>We present a novel technique for the efficient boundary evaluation of sweep operations applied to objects in polygonal boundary representation. These sweep operations include Minkowski addition, offsetting, and sweeping along a discrete rigid motion trajectory. Many previous methods focus on the construction of a polygonal superset (containing self‐intersections and spurious internal geometry) of the boundary of the volumes which are swept. Only few are able to determine a clean representation of the actual boundary, most of them in a discrete volumetric setting. We unify such superset constructions into a succinct common formulation and present a technique for the robust extraction of a polygonal mesh representing the outer boundary, i.e. it makes no general position assumptions and always yields a manifold, watertight mesh. It is exact for Minkowski sums and approximates swept volumes polygonally. By using plane‐based geometry in conjunction with hierarchical arrangement computations we avoid the necessity of arbitrary precision arithmetics and extensive special case handling. By restricting operations to regions containing pieces of the boundary, we significantly enhance the performance of the algorithm.</jats:p>","lang":"eng"}],"status":"public","publication":"Computer Graphics Forum","type":"journal_article","title":"Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes","doi":"10.1111/j.1467-8659.2010.01770.x","date_updated":"2025-07-14T12:35:40Z","publisher":"Wiley","volume":29,"author":[{"full_name":"Campen, Marcel","id":"114904","last_name":"Campen","orcid":"0000-0003-2340-3462","first_name":"Marcel"},{"first_name":"Leif","last_name":"Kobbelt","full_name":"Kobbelt, Leif"}],"date_created":"2025-06-30T08:34:20Z","year":"2010","intvolume":"        29","page":"1613-1622","citation":{"chicago":"Campen, Marcel, and Leif Kobbelt. “Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes.” <i>Computer Graphics Forum</i> 29, no. 5 (2010): 1613–22. <a href=\"https://doi.org/10.1111/j.1467-8659.2010.01770.x\">https://doi.org/10.1111/j.1467-8659.2010.01770.x</a>.","ieee":"M. Campen and L. Kobbelt, “Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes,” <i>Computer Graphics Forum</i>, vol. 29, no. 5, pp. 1613–1622, 2010, doi: <a href=\"https://doi.org/10.1111/j.1467-8659.2010.01770.x\">10.1111/j.1467-8659.2010.01770.x</a>.","ama":"Campen M, Kobbelt L. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. <i>Computer Graphics Forum</i>. 2010;29(5):1613-1622. doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2010.01770.x\">10.1111/j.1467-8659.2010.01770.x</a>","apa":"Campen, M., &#38; Kobbelt, L. (2010). Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. <i>Computer Graphics Forum</i>, <i>29</i>(5), 1613–1622. <a href=\"https://doi.org/10.1111/j.1467-8659.2010.01770.x\">https://doi.org/10.1111/j.1467-8659.2010.01770.x</a>","bibtex":"@article{Campen_Kobbelt_2010, title={Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes}, volume={29}, DOI={<a href=\"https://doi.org/10.1111/j.1467-8659.2010.01770.x\">10.1111/j.1467-8659.2010.01770.x</a>}, number={5}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Campen, Marcel and Kobbelt, Leif}, year={2010}, pages={1613–1622} }","short":"M. Campen, L. Kobbelt, Computer Graphics Forum 29 (2010) 1613–1622.","mla":"Campen, Marcel, and Leif Kobbelt. “Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes.” <i>Computer Graphics Forum</i>, vol. 29, no. 5, Wiley, 2010, pp. 1613–22, doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2010.01770.x\">10.1111/j.1467-8659.2010.01770.x</a>."},"publication_identifier":{"issn":["0167-7055","1467-8659"]},"publication_status":"published","issue":"5"},{"abstract":[{"lang":"eng","text":"<jats:title>Abstract</jats:title><jats:p> <jats:italic>In this paper, we present a novel method to compute Boolean operations on polygonal meshes. Given a Boolean expression over an arbitrary number of input meshes we reliably and efficiently compute an output mesh which faithfully preserves the existing sharp features and precisely reconstructs the new features appearing along the intersections of the input meshes. The term “hybrid” applies to our method in two ways: First, our algorithm operates on a hybrid data structure which stores the original input polygons (surface data) in an adaptively refined octree (volume data). By this we combine the robustness of volumetric techniques with the accuracy of surface‐oriented techniques. Second, we generate a new triangulation only in a close vicinity around the intersections of the input meshes and thus preserve as much of the original mesh structure as possible (hybrid mesh). Since the actual processing of the Boolean operation is confined to a very small region around the intersections of the input meshes, we can achieve very high adaptive refinement resolutions and hence very high precision. We demonstrate our method on a number of challenging examples.</jats:italic> </jats:p>"}],"status":"public","publication":"Computer Graphics Forum","type":"journal_article","extern":"1","language":[{"iso":"eng"}],"_id":"60462","department":[{"_id":"969"}],"user_id":"117512","year":"2010","page":"75-87","intvolume":"        29","citation":{"ama":"Pavić D, Campen M, Kobbelt L. Hybrid Booleans. <i>Computer Graphics Forum</i>. 2010;29(1):75-87. doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01545.x\">10.1111/j.1467-8659.2009.01545.x</a>","ieee":"D. Pavić, M. Campen, and L. Kobbelt, “Hybrid Booleans,” <i>Computer Graphics Forum</i>, vol. 29, no. 1, pp. 75–87, 2010, doi: <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01545.x\">10.1111/j.1467-8659.2009.01545.x</a>.","chicago":"Pavić, Darko, Marcel Campen, and Leif Kobbelt. “Hybrid Booleans.” <i>Computer Graphics Forum</i> 29, no. 1 (2010): 75–87. <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01545.x\">https://doi.org/10.1111/j.1467-8659.2009.01545.x</a>.","apa":"Pavić, D., Campen, M., &#38; Kobbelt, L. (2010). Hybrid Booleans. <i>Computer Graphics Forum</i>, <i>29</i>(1), 75–87. <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01545.x\">https://doi.org/10.1111/j.1467-8659.2009.01545.x</a>","bibtex":"@article{Pavić_Campen_Kobbelt_2010, title={Hybrid Booleans}, volume={29}, DOI={<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01545.x\">10.1111/j.1467-8659.2009.01545.x</a>}, number={1}, journal={Computer Graphics Forum}, publisher={Wiley}, author={Pavić, Darko and Campen, Marcel and Kobbelt, Leif}, year={2010}, pages={75–87} }","mla":"Pavić, Darko, et al. “Hybrid Booleans.” <i>Computer Graphics Forum</i>, vol. 29, no. 1, Wiley, 2010, pp. 75–87, doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01545.x\">10.1111/j.1467-8659.2009.01545.x</a>.","short":"D. Pavić, M. Campen, L. Kobbelt, Computer Graphics Forum 29 (2010) 75–87."},"publication_identifier":{"issn":["0167-7055","1467-8659"]},"publication_status":"published","issue":"1","title":"Hybrid Booleans","doi":"10.1111/j.1467-8659.2009.01545.x","date_updated":"2025-07-14T12:35:48Z","publisher":"Wiley","volume":29,"author":[{"first_name":"Darko","last_name":"Pavić","full_name":"Pavić, Darko"},{"first_name":"Marcel","orcid":"0000-0003-2340-3462","last_name":"Campen","id":"114904","full_name":"Campen, Marcel"},{"first_name":"Leif","full_name":"Kobbelt, Leif","last_name":"Kobbelt"}],"date_created":"2025-06-30T08:22:33Z"},{"department":[{"_id":"65"}],"user_id":"14955","_id":"21773","language":[{"iso":"eng"}],"publication":"Computer Graphics Forum","type":"conference","status":"public","volume":28,"author":[{"id":"90","full_name":"Domik, Gitta","last_name":"Domik","first_name":"Gitta"},{"first_name":"Riccardo","last_name":"Scateni","full_name":"Scateni, Riccardo"}],"date_created":"2021-04-25T17:06:54Z","date_updated":"2022-01-06T06:55:13Z","doi":"10.1111/j.1467-8659.2009.01433.x","title":"Education Programme at Eurographics 2009","publication_identifier":{"issn":["1467-8659"]},"intvolume":"        28","page":"1723–1724","citation":{"apa":"Domik, G., &#38; Scateni, R. (2009). Education Programme at Eurographics 2009. In <i>Computer Graphics Forum</i> (Vol. 28, pp. 1723–1724). <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01433.x\">https://doi.org/10.1111/j.1467-8659.2009.01433.x</a>","short":"G. Domik, R. Scateni, in: Computer Graphics Forum, 2009, pp. 1723–1724.","mla":"Domik, Gitta, and Riccardo Scateni. “Education Programme at Eurographics 2009.” <i>Computer Graphics Forum</i>, vol. 28, 2009, pp. 1723–1724, doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01433.x\">10.1111/j.1467-8659.2009.01433.x</a>.","bibtex":"@inproceedings{Domik_Scateni_2009, title={Education Programme at Eurographics 2009}, volume={28}, DOI={<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01433.x\">10.1111/j.1467-8659.2009.01433.x</a>}, booktitle={Computer Graphics Forum}, author={Domik, Gitta and Scateni, Riccardo}, year={2009}, pages={1723–1724} }","ama":"Domik G, Scateni R. Education Programme at Eurographics 2009. In: <i>Computer Graphics Forum</i>. Vol 28. ; 2009:1723–1724. doi:<a href=\"https://doi.org/10.1111/j.1467-8659.2009.01433.x\">10.1111/j.1467-8659.2009.01433.x</a>","ieee":"G. Domik and R. Scateni, “Education Programme at Eurographics 2009,” in <i>Computer Graphics Forum</i>, 2009, vol. 28, pp. 1723–1724.","chicago":"Domik, Gitta, and Riccardo Scateni. “Education Programme at Eurographics 2009.” In <i>Computer Graphics Forum</i>, 28:1723–1724, 2009. <a href=\"https://doi.org/10.1111/j.1467-8659.2009.01433.x\">https://doi.org/10.1111/j.1467-8659.2009.01433.x</a>."},"year":"2009"}]