Checking if two cubic Bézier curves intersect

Question

Hello guys,

For a personal project, I'd need to find out if two cubic Bézier curves intersect. I don't need to know where: I just need to know if they do. However, I'd need to do it fast.

I've been scavenging the place and I found several resources. Mostly, there's this question here that had a promising answer.

So after I figured what is a Sylvester matrix, what is a determinant, what is a resultant and why it's useful, I thought I figured how the solution works. However, reality begs to differ, and it doesn't work so well.

---

Messing Around

I've used my graphing calculator to draw two Bézier splines (that we'll call B₀ and B₁) that intersect. Their coordinates are as follow (P₀, P₁, P₂, P₃):

(1, 1) (2, 4) (3, 4) (4, 3)
(3, 5) (3, 6) (0, 1) (3, 1)

The result is the following, B₀ being the "horizontal" curve and B₁ the other one:

Following directions from the aforementioned question's top-voted answer, I've subtracted B₀ to B₁. It left me with two equations (the X and the Y axes) that, according to my calculator, are:

x = 9t^3 - 9t^2 - 3t + 2
y = 9t^3 - 9t^2 - 6t + 4

---

The Sylvester Matrix

And from that I've built the following Sylvester matrix:

9  -9  -3   2   0   0
0   9  -9  -3   2   0
0   0   9  -9  -3   2
9  -9  -6   4   0   0
0   9  -9  -6   4   0
0   0   9  -9  -6   4

After that, I've made a C++ function to calculate determinants of matrices using Laplace expansion:

template<int size>
float determinant(float* matrix)
{
    float total = 0;
    float sign = 1;
    float temporaryMatrix[(size - 1) * (size - 1)];
    for (int i = 0; i < size; i++)
    {
        if (matrix[i] != 0)
        {
            for (int j = 1; j < size; j++)
            {
                float* targetOffset = temporaryMatrix + (j - 1) * (size - 1);
                float* sourceOffset = matrix + j * size;
                int firstCopySize = i * sizeof *matrix;
                int secondCopySize = (size - i - 1) * sizeof *matrix;
                memcpy(targetOffset, sourceOffset, firstCopySize);
                memcpy(targetOffset + i, sourceOffset + i + 1, secondCopySize);
            }
            float subdeterminant = determinant<size - 1>(temporaryMatrix);
            total += matrix[i] * subdeterminant * sign;
        }
        sign *= -1;
    }
    return total;
}

template<>
float determinant<1>(float* matrix)
{
    return matrix[0];
}

It seems to work pretty well on relatively small matrices (2x2, 3x3 and 4x4), so I'd expect it to work on 6x6 matrices too. I didn't conduct extensive tests however, and there's a possibility that it's broken.

---

The Problem

If I understood correctly the answer from the other question, the determinant should be 0 since the curves intersect. However, feeding my program the Sylvester matrix I made above, it's -2916.

Is it a mistake on my end or on their end? What's the correct way to find out if two cubic Bézier curves intersect?

Answer 1

I'm by no way an expert on this kind of thing, but I follow a nice blog that talks a lot about curves. He has link to two nice articles talking about your problem (the second link has an interactive demonstration and some source code). Other people may have much better insight into the problem but I hope this helps!

http://cagd.cs.byu.edu/~557/text/ch7.pdf

http://xtyler.com/code/104

Answer 2

Is it a mistake on my end or on their end?

Are you basing your interpretation of the determinant on the 4th comment attached to this answer? If so, I believe that's where the mistake lies. Reproducing the comment here:

If the determinant is zero there is is a root in X and Y at *exactly the same value of t, so there is an intersection of the two curves. (the t may not be in the interval 0..1 though).

I don't see any problems with this part, but the author goes on to say:

If the determinant is <> zero you can be sure that the curves don't intersect anywhere.

I don't think that's correct. It's perfectly possible for the two curves to intersect in a location where the t values differ, and in that case, there will be an intersection even though the matrix has a non-zero determinant. I believe this is what's happening in your case.

Answer 3

I don't know how fast it will be, but if you have two curves C1(t) and C2(k) they intersect if C1(t) == C2(k). So you have two equations (per x and per y) for two variables (t, k). You can solve the system using numerical methods with enough for you accuracy. When you've found t,k parameters you should check if there is a parameter on [0, 1]. If it is they intersects on [0, 1].

Answer 4

Intersection of Bezier curves is done by the (very cool) Asymptote vector graphics language: look for intersect() here.

Although they don't explain the algorithm they actually use there, except to say that it's from p. 137 of "The Metafont Book", it appears that the key to it is two important properties of Bezier curves (which are explained elsewhere on that site though I can't find the page right now):

• A Bezier curve is always contained within the bounding box defined by its 4 control points
• A Bezier curve can always be subdivided at an arbitrary t value into 2 sub-Bezier curves

With these two properties and an algorithm for intersecting polygons, you can recurse to arbitrary precision:

bezInt(B₁, B₂):

1. Does bbox(B₁) intersect bbox(B₂)?
   • No: Return false.
   • Yes: Continue.
2. Is area(bbox(B₁)) + area(bbox(B₂)) < threshold?
   • Yes: Return true.
   • No: Continue.
3. Split B₁ into B_1a and B_1b at t = 0.5
4. Split B₂ into B_2a and B_2b at t = 0.5
5. Return bezInt(B_1a, B_2a) || bezInt(B_1a, B_2b) || bezInt(B_1b, B_2a) || bezInt(B_1b, B_2b).

This will be fast if the curves don't intersect -- is that the usual case?

[EDIT] It looks like the algorithm for splitting a Bezier curve in two is called de Casteljau's algorithm.