Re: [help] fast intersection calculation between bezier & rectangle
- From: Mark VandeWettering <wettering@xxxxxxxxx>
- Date: Mon, 21 May 2007 11:55:28 -0500
On 2007-05-19, Dave Eberly <dNOSPAMeberly@xxxxxxxxxxxxxxx> wrote:
<Ylem.GL@xxxxxxxxx> wrote in message
news:1179564418.999716.61620@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I'm currently working on a 2D drawing app which allows users to
drag their mouses in the canvas to select from a lot of bezier curves.
To figure out which bezier curves are selected seems a bit difficult
to me.
I tried to sample the bezier into dozens of line segments and
calculate the intersection between the line segments and the selection
rectangle, but it seems not very efficient (especially when the number
of curves grows to 50+)
Can anyone give me some suggestions on how to figure out the
intersect set much more efficiently, please?
Using your approach, preprocess the line segments of the polylines
that approximate the curves. Compute the axis-aligned bounding boxes
of the segments. Sort the projections of these relative to the x-axis.
Now when a user creates a tracking rectangle, you can quickly locate
which segments the rectangle edges potentially intersect by locating
those axis-aligned boxes that the rectangle edges intersect. The idea
is effectively that of http://www.cs.cmu.edu/~baraff/sigcourse/notesd2.pdf .
Also look at the recent thread in this newsgroup; the subject is
"Intersection of bezier and straight line". You can compute the
intersection of rectangle edge and Bézier curve directly by converting
the problem to computing the roots of a polynomial. Finding roots can
also be computationally expensive. As a quick "no intersection", you
can use Sturm sequences for the polynomial and test whether the
polynomial has no real-valued roots, in which case the edge does not
intersect the curve. These tests involve only basic arithmetic operations.
When all you have is a hammer, everything looks like a nail. My
particular hammer is interval arithemetic, so everything looks like
interval arithmetic to me. I'd note that the Bezier curve should
definitely be selected if any vertex lies within the rectangle, which is
trivial to check. If it isn't, then check to see whether the bounding
box of the control points overlaps with your target rectangle. If it
does not, then it doesn't overlap. If it does, then it might, so do
a Bezier subdivide and try again with the two subcurves, with some
termination criteria (the above solutions also have a termination
criteria for linearization, you can adopt the same here). Note that you
only need to fine ONE subcurve which overlaps, there is no reason to continue
searching once you find one.
Because no actual data structures are computed here, I doubt it will perform
as well as David's proposed method, but on the other hand, no actual data
structures are involved, so I suspect the code will be rather smaller and
easier to debug. YMMV.
Mark
--.
Dave Eberly
http://www.geometrictools.com
- References:
- [help] fast intersection calculation between bezier & rectangle
- From: Ylem.GL@xxxxxxxxx
- Re: [help] fast intersection calculation between bezier & rectangle
- From: Dave Eberly
- [help] fast intersection calculation between bezier & rectangle
- Prev by Date: Raytracing and modern Render Engines
- Next by Date: Line Line intersection in 3D
- Previous by thread: Re: fast intersection calculation between bezier & rectangle
- Next by thread: Newbie question on how to crop images depending on pixel color
- Index(es):
Relevant Pages
|
