On Sun, Mar 15, 2009 at 11:01:06PM -0200, Fernando Cacciola wrote:
Hi Steve,
On Sat, Mar 14, 2009 at 04:26:35PM -0200, Fernando Cacciola wrote:
IMO, any geometric library should provide a toolbox of exact predicates (which shoud be exact independetly of the input type)
I agree.
I've always thought that the adaptive floating-point arithmetic of Douglas Priest [1] and Jonathan Shewchuk [2] would be a good way to do this for floats and doubles.
These techniques are excelent tools for providing (adaptive) extended precision number types. OTOH, it would hurt performance unneccesarily too much if these are not coupled with interval arithmentic to detect the need for the extra precision in the first place. I know that as a fact because I've implemented Priest's expansions once, many years ago.
IOW, following the simple foating-point filter I sketeched before, Priest's expasions would be the exact number type in there.
Yes. Roughly speaking, that's what Shewchuk's predicates do: a floating point filter that, if the filter fails, is followed by an exact calculation using Priest's expansions. It's been a while since I read the papers but IIRC, the filter computations provide the initial expansions so you don't have to re-start the exact computation from scratch. This could be an additional speed benefit. -Steve