How to determine curvature of a cubic bezier path

问题:

I've been working on a project where I use Bezier paths to draw the curves I need. Each basic shape in my project consists of three cubic Bezier curves arranged end to end so that the slopes match where they meet.

The basic problem I need to solve is whether the compound curve made of the three Bezier curves intersects with itself. After thinking about it for a while, I've figured out that given the constraints of the curves, I can simplify the task to something else:

The curvature of each of the three Bezier paths should be opposite in curvature direction relative to the curve it's abutted to. In other words, there should be an inflection point where one bezier curve abuts to another one. If that is not the case, I want to reject the parameter set that generated the curves and select a different set.

In any case, my basic question is how to detect whether there is an inflection point where the curves abut each other.

In the illustration, each of the three Bezier curves is shown using a different color. The left black curve curves in the opposite direction from the red curve at the point where they meet, but the right black curve curves in the same direction. There is an inflection point where the red and left black curve meet but not where the red and right black curve meet.

Edit: Below, I've added another image, showing the polygon enclosing the Bezier path. The crossing lines of the polygon, shown in the black curve, tests for an inflection point, not a loop. I'm guessing that one curve intersecting another can be tested by checking whether the enclosing polygons intersect, as illustrated by the red and blue curves.

P.S. Since there has been some question about the constraints, I will list some of them here:

• The left most point and the rightmost point have the same y value.
• The x value of the control point of the leftmost point is less than
  the x value of the control point of the rightmost point. This keeps
  the black and blue curves from intersecting each other.
• The slope at the leftmost and rightmost points is within about +/- 10 degrees of horizontal.
• The intersection of the black and red curves, and the intersection of the red and blue curves divide the full curve in approximately thirds. I don't have exact numbers, but a sample bound would be that the x value of the left end of the red curve is somewhere between 25% and 40% of the x value of the rightmost point.
• The y value of the points of intersection are +/- some small fraction of the overall width.
• The slope at the intersections is > 0.6 and < 3.0 (positive or negative).

回答1:

The equation for curvature is moderately simple. You only need the sign of the curvature, so you can skip a little math. You are basically interested in the sign of the cross product of the first and second derivatives.

This simplification only works because the curves join smoothly. Without equal tangents a more complex test would be needed.

The sign of curvature of curve P:

ax = P[1].x - P[0].x;               //  a = P1 - P0
ay = P[1].y - P[0].y;
bx = P[2].x - P[1].x - ax;          //  b = P2 - P1 - a
by = P[2].y - P[1].y - ay;
cx = P[3].x - P[2].x - bx*2 - ax;   //  c = P3 - P2 - 2b - a
cy = P[3].y - P[2].y - by*2 - ay;

bc = bx*cy - cx*by;
ac = ax*cy - cx*ay;
ab = ax*by - bx*ay;

r = ab + ac*t + bc*t*t;

Note that r is the cross product of the first and second derivative and the sign indicate the direction of curvature. Calculate r at t=1 on the left curve and at t=0 on the right curve. If the product is negative, then there is an inflection point.

If you have curves U, V and W where U is the left black, V is the middle red, and W is the right black, then calculate bc, ac, and ab above for each. The following test will be true if both joins are inflection points:

(Uab+Uac+Ubc)*(Vab) < 0 && (Vab+Vac+Vbc)*(Wab) < 0

The equation for curvature has a denominator that I have ignored. It does not affect the sign of curvature and would only be zero if the curve was a line.

Math summary:

// start with the classic bezier curve equation
P = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
// convert to polynomial
P = P0 + 3*t*(P1 - P0) + 3*t^2*(P2 - 2*P1 + P0) + t^3*(P3 - 3*P2 + 3*P1 - P0)
// rename the terms to a,b,c
P = P0 + 3at + 3btt + cttt
// find the first and second derivatives
P' = 3a + 6bt + 3ctt
P" =      6b  + 6ct
// and the cross product after some reduction 
P' x P" = ab + act + bctt

回答2:

One of the deterministic ways to check if a bezier curve has a double-point or self-intersection is to calculate the inverse equation and evaluate the root, since the inversion equation of a bezier curve is always zero at the point of self-intersection. As detailed in this example by T.W.Sederberg –course notes. Then for detecting whether two bezier curves (red and black in the question) intersect with each other, there are a few methods, binary subdivision (easier to implement) and bezier clipping (very good balance of efficiency and code complexity), implicitization (not worth it).

But a more efficient way to do it probably is to subdivide the curves into small line-segments and find the intersection. Here is one way to do it. Especially when you are interested in knowing whether the path self-intersect, but not in an accurate point of intersection.

If you have well defined assumptions about the locations of the CVs of the piece-wise bezier curves (or poly-bezier as @Pomax mentioned above), you can try out the curvature based method as you have mentioned in your question.

Here is a plot of the curvature on a similar path as in the question. Under similar circumstances, it seems this could give you the solution you are looking for. Also, in case of a cusp, it seems this quick and dirty method still works!

回答3:

Suppose you have 4 points: P0, P1, P2 and P3, which describes a cubic Bezier's curve (cBc for short) . P0 and P3 are starting and ending points, P1 and P2 are directional points.

When P0, P1 and P2 are collinear, then cBc has an inflection point at P0.

When P1, P2 and P3 are collinear, then cBC has an inflection point at P3.

Remarks.

1) Use the vector product ( P0P1 x P1P2 and P1P2 x P2P3 respectively) to check the collinearity. The result should be a zero-lenght vector.

2) Avoid the situation where P0, P1, P2 and P3 are all collinear, the cBc they create aren't curves in the common sense.

Corollary.

When P1=P2, cBc has inflection points at both sides.

回答4:

@ Victor Engel : Thank you for the clarification. Now the solution is even easier.

In short, look at torques of both curves. If they pull together, the "inflexion" occurs, if they are opposed, the "curvature" continues.

Remark: Words "inflexion" and "curvature" have here a more intuitive nature, than a strict mathematical meaning, therefore apostrophes are used.

As before, a set of points P0,P1,P2,P3 defines the first cubic Bezier curve, and Q0,Q1,Q2 and Q3 the second. Moreover, 4 vectors: a,b,u,w will be useful.

a = P2P3
b = P1P2
u = Q0Q1
v = Q1Q2

I will omit a C1-continuity checking, it's already done by you. ( This means P3=Q0 and a x u=0)

Finally, Tp and Tq torques will appear.

Tp = b x a 

( "x" means a vector product, but Tp on the planar is treated like a simple number, not a vector. }

if Tp=0            {very rarely vectors a, b can be parallel.}
    b = P0P1
    Tp = b x a 
    if Tp=0 
        No! It's can't be! Who straightened the curve???
        STOP
    endif
endif

Tq = u x v 
if Tq=0            {also  vectors u, v can be parallel.}
    v = Q2Q3
    Tq = u x v 
    if Tq=0 
        Oh no! What happened to my curve???
        STOP
    endif
endif

Now the final test:

if Tp*Tq < 0  then    Houston! We have AN "INFLEXION"!
              else    WE CONTINUE THE TURN!