• FEATURED

View more

View more

View more

\$5

### Image of the Day Submit

IOTD | Top Screenshots

## Bezier Curve Intersection?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

7 replies to this topic

Posted 06 April 2006 - 08:38 AM

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.

### #2John Schultz  Members

Posted 06 April 2006 - 10:30 AM

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.

### #3grhodes_at_work  Members

Posted 06 April 2006 - 10:37 AM

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).
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

### #4John Schultz  Members

Posted 06 April 2006 - 10:53 AM

Graham- have you tried Bezier Clipping? Seems to work pretty well:

Demo 1
Demo 2 (may just be recursive DeCasteljau; nice demo)

Nishita's Paper
Paper 2

### #5grhodes_at_work  Members

Posted 06 April 2006 - 10:53 AM

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)
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

### #6grhodes_at_work  Members

Posted 06 April 2006 - 10:56 AM

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.
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Posted 06 April 2006 - 11:47 AM

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.

### #8Wasting Time  Members

Posted 06 April 2006 - 03:38 PM

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

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.