Re: [boost] [geometry] robustness approaches

Subject: Re: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-19 11:48:09

Hi Thomas,

Sorry for the late response.

> Hi Fernando,
> 
> The clear position of Lucanus Simonson with respect to the "allowed" output
> of a line segments intersection algorithm and your reactions to his position
> makes me wonder which output you consider "allowed".
> 
> The figures 1a), 1b), 2) and 3b) of John Hobby's publication 
> http://cutebugs.net/files/curve/2-27.ps clearly illustrate the discussed
> issue.
> 

3b) would be a reasonable result.
1b) could also depending on the application: in rendering for example it could 
be totally acceptable.

> I considered 2) as non-acceptable output and Lucanus Simonson considered 1b)
> as non-acceptable. (The output 3b) seems to be the most attractive one for
> this example.) Your position that geometric algorithms should use exactly
> evaluated "predicates" called explicitly on the input (and never ever on an
> intermediate result) to drive the topological construction doesn't seem to
> settle this question.
> 
Put like that, no it doesn't :) But notice that I carefully said "unless you 
really have to use intermediate results, and if you do, use them very very 
carefully"

> Why not? Because the output 1b) would not be allowed as input to your
> algorithm, it's hard to see why you should allow it as output from your
> algorithm. The output 2) and 3b) on the other hand clearly fall into the
> category "modification of input" (because a straight segment was replaced by
> a bent segment), which you explicit call "hacking". And it clearly is hacking
> in the sense that it doesn't generalize to other problems (like the straight
> skeleton for example). I somehow got the impression that 1b) is indeed the
> output that you consider "allowable", but I would like you to confirm or
> correct this impression.
> 
Yes, (1b) could be considered allowed as well, depending on what you need to do 
with the result.

These questions are excelent to put what I've said before in a much better 
persective:

What I outlined are general guidelines for all types of geometric computation 
problems. As such, it has particular cases where something case-specific must be 
done, as in this case.

OTOH the very fact that the guidelines don't directly apply calls for 
reconsidering the inmediate solution a bit further. In the case of booleans, for 
instance, one could notice the following:

Let's label the points in the figures, in topological order, for the sake of 
discussion: P, Q, R, S such that the segments are PQ, QR, RS and segments PQ and 
RS intersect at point I

Given exact predicates operating exclusively in the input, it is possible to 
know that segments PQ and RS intersect at I, but there is no other intersection, 
specially NOT with QR.

That indicates that all the problems stated in the cited paper comes from 
approximating the intersection point embeeding it into a finite space, which is 
a problem that can be considered separated from the boolean operation  algorithm 
(which a researcher could express in tems of a RealRAM).

Therefore, a boolean operations algorithm could be designed in a such a way that 
it just doesn't attempt to ouput ANY approximation for intersections points at 
all. Instead, it could merely return the Planar Directed Graph (PDG) that 
corresponds to the result, with all intersection points given "expressively": 
i.e. using a representation that actually stores the four points that define the 
two intersecting segments.

Such an algorithm would have the luxury of totally ignoring the potential side 
effect of introducing "unreported intersections" as you call it. It is extremely 
useful to be able to implement a geometric algorithm with such a freedom.

Then a second, separate and composable "embeeding" algorithm could take on the 
job of approximating intersection points fullfilling certain output requirements.

Given a DAG, such an algorithm can produce (3b) since it can know using the 
exact predicates that point I is to one side of segment QR but the best 
approximation it can generate is (as reported by the predicate but this time 
called on the potential result) to the other side, so it MUST modify the 
idealized result splitting and snapping QR.  Granted, this is using the 
predicate with an intermediate result, but in a place specifically designed to 
carefully consider the effect of rounding and with the "ideally correct" result 
already in hand (the DAG).

Notice how the general exact computation paradigm lead us to decompose an 
algorithm into concerns that could not have been obviously separated. As a 
consequence, one can now consider the possibility of providing a toolbox of 
distinct "embeeding" steps that, for instance produce (1b), which could be more 
than acceptable, for example, for rendering. Users would choosen the one they need.

Even more, the entire geometric computing framework could follow a similar 
design by pushing the actual computation of intermediate results as far ahead as 
possible. That is, there could be several algorithms taking the DAG produced by 
the "error-free" boolean operation and go from there. Only in the very end of 
the processing pipeline the results would have to be embeeded, but now in a 
context where approximation erros have little, if any, impact.

Best

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