Subject: Re: [boost] [geometry] robustness approaches
From: Fernando Cacciola (fernando.cacciola_at_[hidden])
Date: 2009-03-19 11:48:09
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
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
> 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
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.
-- Fernando Cacciola SciSoft Consulting, Founder http://www.scisoft-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk