Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Fast Floating-Point Filters for Robust Predicates

  • Geometric predicates are at the core of many algorithms, such as the construction of Delaunay triangulations, mesh processing and spatial relation tests. These algorithms have applications in scientific computing, geographic information systems and computer-aided design. With floating-point arithmetic, these geometric predicates can incur round-off errors that may lead to incorrect results and inconsistencies, causing computations to fail. This issue has been addressed using a combination of exact arithmetic for robustness and floating-point filters to mitigate the computational cost of exact computations. The implementation of exact computations and floating-point filters can be a difficult task, and code generation tools have been proposed to address this. We present a new C++ meta-programming framework for the generation of fast, robust predicates for arbitrary geometric predicates based on polynomial expressions. We combine and extend different approaches to filtering, branch reduction, and overflow avoidance that have previously been proposed. We show examples of how this approach produces correct results for data sets that could lead to incorrect predicate results with naive implementations. Our benchmark results demonstrate that our implementation surpasses state-of-the-art implementations.
Metadaten
Author:Tinko Bartels, Vissarion FisikopoulosORCiD, Martin WeiserORCiD
Document Type:Article
Parent Title (English):BIT Numerical Mathematics
Volume:63
Date of first Publication:2023/05/17
ArXiv Id:http://arxiv.org/abs/2208.00497
DOI:https://doi.org/10.1007/s10543-023-00975-x
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.