Bezier Curve Intersection?

Math and Physics Programming

Started by BradSnobar April 06, 2006 02:38 PM

6 comments, last by Wasting Time 18 years ago

232

Author

April 06, 2006 02:38 PM

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.

John Schultz

811

April 06, 2006 04:30 PM

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.

Amazing Curves Racing

grhodes_at_work

1,385

April 06, 2006 04:37 PM

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

John Schultz

811

April 06, 2006 04:53 PM

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

Amazing Curves Racing

grhodes_at_work

1,385

April 06, 2006 04:53 PM

Quote:Original post by John Schultz
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.

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

grhodes_at_work

1,385

April 06, 2006 04:56 PM

Quote:Original post by John Schultz
Graham- have you tried Bezier Clipping? Seems to work pretty well:

Demo 1
Demo 2

Nishita's Paper
Paper 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

BradSnobar

232

Author

April 06, 2006 05:47 PM

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.

Wasting Time

411

April 06, 2006 09:38 PM

Quote:Original post by grhodes_at_work
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.

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

Bezier Curve Intersection?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Bezier Curve Intersection?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines