Bezier Curve Intersection?

This topic is 4668 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Does anyone have a function that determines whether two Bezier curves intersect? Both of my curves are on the same two dimensional plane. Here is an example I have fro drawing one of my curves.
    protected override void OnPaint(PaintEventArgs e)
{
base.OnPaint(e);

using (Pen myPen = new Pen(Color.Black))
{
//Draw a curved line between two points.
//DrawBezier() was easier use than DrawArc()
Point start = new Point(label1.Right, label1.Bottom);
Point stop = new Point(label2.Right, label2.Top);
Point control1 = new Point(label1.Right + 30, (label1.Bottom + label2.Top) / 2);
Point control2 = new Point(label2.Right + 30, (label1.Bottom + label2.Top) / 2);

e.Graphics.DrawBezier(myPen, start, control1, control2, stop);
}
}


I would like to also have a function that returns true if I pass in the parameters for two curves that intersect.
public bool IntersectingCurves(start1, control1, control2, stop1, start2, control2_1, control2_2, stop2);


If anyone has a formula or some tips about how to do this, I would really appreciate it.

Share on other sites
Three methods that I'm aware of:

1. Recursively (DeCasteljua) subdivide and evaluate the curve and create a poly line (list of connected line segments). Next, compare the line segments for overlap (brute force or create a spatial partition to speed it up).
2. Use Bezier Clipping (see google).
3. Evaluate a degree 9 polynomial (per Dave Eberly), will have numerical issues though.

Dave's Geometric Tools site may be helpful.

Share on other sites
Er....to really find intersection points between two Bezier's is a rather tricky problem that in the general case requires either the use of calculus or a faceted line segment approximation to the curves. Both approaches have robustness "issues" of various sorts to deal with that would drive you mad.

That said, do you really need to know that they actually intersect, or will an approximation do? All you need to know is "do they intersect", right? Not "where do they intersect"?

One approximation I have in mind is to compute a bounding box around the control nets for each curve, and if the bounding boxes overlap assume that they intersect.

A slightly better approximation would be to compute the intersection points between the line segments in the two control nets. If the control net segments intersect between the two curves, changes are good that the curves themselves intersect (though they still might not).

Share on other sites
Quote:
 Original post by John SchultzThree methods that I'm aware of:1. Recursively (DeCasteljua) subdivide and evaluate the curve and create a poly line (list of connected line segments). Next, compare the line segments for overlap (brute force or create a spatial partition to speed it up).2. Use Bezier Clipping (see google).3. Evaluate a degree 9 polynomial (per Dave Eberly), will have numerical issues though.Dave's Geometric Tools site may be helpful.

Good summary, John. And good to link to Eberly's page. I would comment that the polynomial formulation is for Bezier curves of a specific order (cubic ones?). Could be sufficient for Brad's case, I would imagine. I haven't seen the treatment, but I would assume it involves finding the roots to that polynomial? In itself nontrivial for 9th order, which is where calculus begins to come into play.

As for speeding up approach #1, the Bentley-Ottmann plane sweep approach is damned fast, and doesn't require building a spatial partition.

The following page offers some additional insight:

Finding All Intersections of Two Bezier Curves

There is also a way cool Java applet that uses approach #1, available here:

Finding Intersections...(I got tired of typing the whole web page title)

Share on other sites
Quote:
 Original post by John SchultzGraham- have you tried Bezier Clipping? Seems to work pretty well:Demo 1Demo 2Nishita's PaperPaper 2

No, I haven't tried that myself. I just found one of the same demos. Very cool! For cubic and lower order, this would seem to maybe be fast enough. Not sure what application this is intended for, though.

Share on other sites
Thank you all so much for your help. I really appreciate it, and will likely be able to implement this function with all these great suggestions.

Thanks again.

Share on other sites
Quote:
 Original post by grhodes_at_workI would comment that the polynomial formulation is for Bezier curves of a specific order (cubic ones?). Could be sufficient for Brad's case, I would imagine. I haven't seen the treatment, but I would assume it involves finding the roots to that polynomial? In itself nontrivial for 9th order, which is where calculus begins to come into play.

To test only if there is an intersection, you do not need to compute the roots of the 9th degree polynomial. You can use Sturm sequences to count how many roots are in the domain [0,1] of the polynomial. Constructing the polynomial in the first place, constructing the Sturm sequence, and applying the root-counting test involves only addition and multiplication. If robustness is important, you can implement the Sturm sequence approach using exact arithmetic, converting the floating-point coefficients of the 9th degree polynomial to rational numbers.

To read an interesting post on the topic, there is a *closed form* solution for testing. Search comp.graphics.algorithms for:
From: "Przemyslaw Koprowski" <org@siggraph.pkoprowski>
Subject: Closed-form of Bezier intersection test
Date: Sunday, February 12, 2006 3:17 PM

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 15
• 14
• 46
• 22
• Forum Statistics

• Total Topics
634054
• Total Posts
3015274
×