Interval arithmetic for the geometric predicates
|
| Interval arithmetic for the geometric predicates |
|
Interval arithmetic allows to speed up the exact computations, at low cost, it's an arithmetic filter. This concerns most of the geometric tests, that need to be computed exactly.
The principle of interval computation is to represent a number by an interval that contains its value. The following operations (the 4 basic operations, and the square root), preserve this inclusion. So, to determine the sign of a variable, you only have to test whether the interval contains zero or not.
It is known that there is a high probability that the floating point filter succeeds, that is, in nearly all non degenerate cases.
There exists different filter types. Static, semi-static, and dynamic. The static filters suppose some bounds on the entries, and do not support all operations, but are the fastest (nearly as fast as floating point code), because the error bound computation is done at compile time.. The semi-static filters compute the error bounds at compile time, so it's more precise, which increases the probability of success, but slightly slower. Then, dynamic filters maintain the error bound dynamicaly for each variable, that's what interval arithmetic does. The method is simpler to use and more general that other filter types. Moreover, efforts have been made to obtain an implementation as fast as possible (factor 3 to 8 compared to floating point code on a predicate), so the cost compared to floating point computation is barable at the application level.
Concerning the implementation, the source code (1998-09-29 version) is freely available, for any use. It contains two C++ interfaces, one C interface, and one with macros. The timings are, either comparable, either better than those of traditionnal implementation such as the Profil/BIAS library.
The implementation is based on the FPU rounding modes. The particularity of this implementation is that it doesn't constantly need to change the rounding mode, because of the representation chosen, which stores the opposite of the lower bound of the interval. So, the code is faster, and gives more possibilities to the compiler to optimize.
See my bibliography for more details.