[Bf-committers] Boolean tool precision

[Ed Halley]

Anyone who is interested in the best practices for comparing floating
point numbers should take a reading of the following page.

http://www.cygnus-software.com/papers/comparingfloats/ 
comparingfloats.htm

The page describes several stages of evolution, from simple to best,  
that
look at the mantissa and exponent components of an IEEE value, and then
makes a determination about whether they are within proper tolerances.

Any stock standard "abs(a-b) < EPSILON" kind of test is sadly out-of- 
date
in the computer engineering world, as the more effective and adaptive
techniques like this page have been around for decades.

- --

On Jul 3, 2007, at 11:26 AM, Ken Hughes wrote:

Before I head out of town for a few days, thought I'd throw this at the
list and see what people's thoughts were:

Chris and I have been working on some of the bugs in the boolean tools:

http://projects.blender.org/tracker/? 
func=detail&atid=125&aid=6847&group_id=9

I've fixed a few problems, but the one I'm running up against now is
numeric precision.  Tests for "equal to zero" are causing some resulting
meshes to have holes (i.e., non-manifold).  Scaling up the sizes of the
objects prior to applying the boolean operations can fix this.

I've experimented with making the "equal to zero" tests scale based on
the size of the values being compared, using the floating point numbers
exponent and mantissa (see frexp() in math.h).  This gives much better
results, but at the cost of speed: as much as 20% slower in some of my
tests.

I'm open to other suggestions how to handle this, or just live with one
of these two options:  fast but possibly non-manifold, slower but almost
always manifold.

Ken
_______________________________________________
Bf-committers mailing list
Bf-committers at blender.org
http://lists.blender.org/mailman/listinfo/bf-committers

--
[ e d @ h a l l e y . c c ]