Indirect Predicates for Geometric Constructions
| Autor: | Marco Attene |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Computational Geometry (cs.CG)
FOS: Computer and information sciences Floating point Correctness Exploit Computer science 020207 software engineering 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Graphics and Computer-Aided Design Industrial and Manufacturing Engineering Predicate (grammar) Computer Science Applications 010201 computation theory & mathematics Robustness (computer science) Approximation error 0202 electrical engineering electronic engineering information engineering Computer Science - Computational Geometry Geometric predicates Exact arithmetic Filtering Implementation Algorithm |
| Zdroj: | Computer Aided Design 126 (2020). doi:10.1016/j.cad.2020.102856 info:cnr-pdr/source/autori:M. Attene/titolo:Indirect Predicates for Geometric Constructions/doi:10.1016%2Fj.cad.2020.102856/rivista:Computer Aided Design/anno:2020/pagina_da:/pagina_a:/intervallo_pagine:/volume:126 |
| ISSN: | 0010-4485 |
| DOI: | 10.1016/j.cad.2020.102856 |
| Popis: | Geometric predicates are a basic ingredient to implement a vast range of algorithms in computational geometry. Modern implementations employ floating point filtering techniques to combine efficiency and robustness, and state-of-the-art predicates are guaranteed to be always exact while being only slightly slower than corresponding (inexact) floating point implementations. Unfortunately, if the input to these predicates is an intermediate construction of an algorithm, its floating point representation may be affected by an approximation error, and correctness is no longer guaranteed. This paper introduces the concept of indirect geometric predicate: instead of taking the intermediate construction as an explicit input, an indirect predicate considers the primitive geometric elements which are combined to produce such a construction. This makes it possible to keep track of the floating point approximation, and thus to exploit efficient filters and expansion arithmetic to exactly resolve the predicate with minimal overhead with respect to a naive floating point implementation. As a representative example, we show how to extend standard predicates to the case of points of intersection of linear elements (i.e. lines and planes) and show that, on classical problems, this approach outperforms state-of-the-art solutions based on lazy exact intermediate representations. Comment: In Computer-Aided Design, 2020 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect