Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-15 20:17:09

Hi Luke,

> 
> You are right that I introduce intersections on segments in order to
> assure that the computed result doesn't have more intersections than
> actually reported.  I'm surprised, however, that unreported
> intersections are commonly considered allowable in floating point if
> they are below a threshold.

Tolerance-based decisions in floating point computatioms are the very 
source of robustness issues.

>  Wouldn't mismatches between thresholds
> in different floating point modules lead to such unreported
> intersections in the output causing an invariant to be violated in
> someone else's input and their code to fail?  Isn't it equally
> possible to introduce intersections on floating point segments if
> they were "close enough" to intersecting to assure that the computed
> result in floating point doesn't have more intersections than
> actually reported.  I was working on devising a way to compute x and
> y epsilon values from the bounding box of the floating point input
> such that I could bound the lateral movement of segments due to
> floating point grid snapping to those epsilons and assure that the c 
> omputed result doesn't contain unreported intersections.

NO. Please don't go that route. Epsilon-geometry is just NOT the right 
way, even if it might appear to be in some particular algorithm where 
the effect of arbitrary snapping within an uncertainity disk is less 
catastrophic.

This would be a non-robust implementation just like any other one.

>  It is
> basically trying to apply my integer methodology to floating point.
> Is this the opposite of the normal approach to floating point, which
> you suggest is to ignore the potential to creat such intersections as
> artifacts of floating point grid snapping since they should be below
> some threshold and can be ignored?
>
FWIW, the "normal approach" is the wrong one.

> I know the commercial, floating-point-based, 3D modeling, meshing and
> physical simulation tools we use are frequently failing due to
> numerical robustness issues.  They place very tight restrictions on
> the cleanlyness of their inputs, and meeting those kinds of tight
> restrictions should be the goal of a geometry library,

Not even.. those restrictions exist to begin with because of the 
incorrect handling of robustness.

 > or it precludes its interoperability with quite a few applications.
> Working around these numerical issues in commercial software consumes
> significant engineering effort inside Intel.

How you ever tried CGAL?

I have a customer of my polygon offsetting implementation (the one in 
CGAL) in the VLSI verification industry. They perform offseting of 
polygons whose vertices might very well be separated less than 1e-5, for 
instance. And of course there isn't any threshold adjusted for that.

 > It also keeps the
> software vendors busy providing us with support and software updates.

Each time I had to provide support for that code it turned out to be a 
plain old bug. Never a numerical issue.

> By this evidence, floating point robustness doesn't appear to be a
> solved problem. 

The general purpose floating-point filtering technique I outlined in my 
previous post involves an overhead ranging from 20% to 50%, compared to 
"naive" epsilon-based implementations.
If having to pay that overhead is unacceptable, then it is not solved, 
but if it is, then it is definitely a solved problem.

> There is no way that a boost library can provide
> that kind of labor intensive support.

Indeed

 > In order to be both free and
> use ful, it has to be absolutely reliable and generate no support
> load for the maintainer due to robustness issues and not need such
> support to be used for real world applications. 

Right

> I would reco mmend
> against accepting a geometry library to boost if I thought it would
> result in an avalanche of robustness issues being reported by unhappy
> users.  Nor would I want to be responsible for supporting such a
> boost library.  I am only proposing my library because I'm confident
> in the reliability of what I've done for integer coordinates.

Great

>  Do you
> think employing my fixed point scheme for floating point coordinates
> would result in issues when using it in applications? 

Would it use any sort of epsilon to decide on the snapping? if so, then 
it will result in issues, so, don't do it :)

Best

--
Fernando Cacciola
SciSoft Consulting, Founder
http://www.scisoft-consulting.com