Geometric predicates are a basic ingredient to implement a vast range of algorithms in computational geometry . Modern implementations employ floatingpoint filtering techniques to combine efficiency and robustness . If the input to these predicates is an intermediate construction, its floating point representation may be affected by anapproximation error, and correctness is no longer guaranteed . Instead of taking the intermediate construction as an explicit input, an indirect predicate considersthe primitive geometric elements which are combined to produce such aconstruction . This makes it possible to exploit efficient filters and expansion arithmeticto resolve the predicate with minimal overhead with respect to a naive floating point implementation . We show how toextend standard predicates to the case of points of intersection of linearelements (i.e. lines and planes) and show that, on classical problems, this approach outperforms state-of-the-

Author(s) : Marco Attene

Links : PDF - Abstract

Code :

Keywords : predicates - geometric - indirect - input - construction -

Leave a Reply

Your email address will not be published. Required fields are marked *