Exact and Robust (Self-)Intersections for Polygonal Meshes

dc.contributor.authorCampen, Marcelen_US
dc.contributor.authorKobbelt, Leifen_US
dc.date.accessioned2015-02-23T16:40:35Z
dc.date.available2015-02-23T16:40:35Z
dc.date.issued2010en_US
dc.description.abstractWe 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.en_US
dc.description.number2en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume29en_US
dc.identifier.doi10.1111/j.1467-8659.2009.01609.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages397-406en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2009.01609.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleExact and Robust (Self-)Intersections for Polygonal Meshesen_US
Files