Re: [Lib2geom-devel] Boolean operations on adjacent cases

[jf b. <jf....@gm...>]

Hi all.

About topology versus precision issues in boolean operations, I think
topology is manageable. I used a "Morse theoretic" flavoured approach
(don't pay attention, no one else would ever call it this way!) and I think
it can solve things pretty well. I certainly left this at an too early
stage, and I guess it's not easy to catch (but just ask if interested ---
the last time I looked at this, which was yeeaaaars ago, there were several
parallel attempt at boolops/intersections, making things pretty confusing;
I dont even remember if I moved mine from toys to trunc... I certainly did
partially :-(  ).

>From my point of view, the hard part in this stuff is the intersection
finder, that should be precision aware (and return time intervals and space
boxes that contain the intersection) . Once you have a bullet (well, say
atomic) proof intersection finder, you have bullet (well, say bow) proof
boolops.

Coincidental segments are already an issue at the root finder level. I
don't think they can be a major issue once you are sure they are exactly
the same. If one is a piece of another, and you still want to detect this,
then it's more delicate, since when you subdivide, every thing moves, and
we are lost (unless you have a horizontal or vertical line).

Strictly speaking, you can have a bunch of epsilon-precise intersections
without the two curves to be exactly the same (think of a very flat
parabola and a tangent). The strategy would be to clean the problem first:
if you can detect that one piece of a curve is in the epsilon neighborhood
of another, then you replace one with the other and do some suitable
adaptation near the ends to keep connectedness; this way, you only have to
handle exact coincidental segments.
I don't think we have such a cleaning process for pairs of paths (at least
we hadn't... years ago). It would be nice to.


I'm not sure my thoughts about boolops are of any help since they might be
too outdated or straight forward, but my main point in writing this is that
I want to convince you that I would be very happy if someone could bring
boolops to live in lib2geom!!

Sincerly, JF.


2012/6/28 Nathan Hurst <nj...@nj...>

> On Wed, Jun 27, 2012 at 09:16:34PM +0200, Vincent Barrielle wrote:
> > Hello,
> >
> > I'm considering using lib2geom in my vector graphics tool to implement
> > boolean operations. But before I try that I'd like to know how it
> > handles hard cases such as computing intersections between two bezier
> > segments that overlap, ie that have (mathematically) an infinite
> > number of intersections. This case happens quite often in my project,
> > so it's really important.
> >
> > For what I've read of lib2geom's code, I haven't seen code dedicated
> > to handling such cases, but perhaps I'm missing something?
> >
> > If lib2geom does not handle this case, I'd be glad to try and
> > contribute so that it is handled (I'm already trying to tackle this
> > issue in my own boolops framework right now, but integrating lib2geom
> > would be a great thing for my project).
>
> The existing boolops code is in a some what disappointing state as it
> turned out harder than anyone thought.
>
> The specific case of coincident polynomial curves is actually quite
> easy to detect - you just have to find more than m*n common points for
> a degree m and degree n curve.  In practice you probably need far
> fewer of these for a non equal curve because a randomly selected point
> has a low probability of being on both curves.  This includes conic
> sections (such as eliptical arcs).  To find partial overlaping bezier
> segments you can start with the existing intersector and when it finds
> sufficient matched points consider it equal.  (Note that
> mathematically equal curves can not share points due to rounding; in
> general floating point makes everything three times harder)
>
> The hardest problem to solve is correctly dealing with the imprecision
> around intersection points (determining the topology of the
> intersections).  We have not found a good answer to this problem,
> though we have many yet untried ideas.
>
> If you want to try boolops we are all very happy to help, but be
> warned, it's one of the hardest problems in 2d geometry processing we
> know of :)
>
> njh
>
>
> ------------------------------------------------------------------------------
> Live Security Virtual Conference
> Exclusive live event will cover all the ways today's security and
> threat landscape has changed and how IT managers can respond. Discussions
> will include endpoint security, mobile security and the latest in malware
> threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
> _______________________________________________
> Lib2geom-devel mailing list
> Lib...@li...
> https://lists.sourceforge.net/lists/listinfo/lib2geom-devel
>