Bézier curve - higher order - detect "sharpness" (serpentine or cusp) in curve

Question

I have high order Bézier curve (n > 5). I would like to detect points of self intersection or too pointy ones. In lower degrees, I could use derivative of curve equation and solve roots for valeu = 0, but in higher dimensions, that would take too long.

Is there any other way? I am not looking for precise solution, just a closest possible. I dont even need the point value itself, just detection.

I was thinking of converting curve to lines and check angle, but that is not very accurate and can miss points if I choose lines too big (miss intresection) or too small (miss cusp via angle criteria)

Answer 1

For self-intersecting, you can refine Bezier curve's control polygon (by knot insertion) to a level that the sum of control polygon length converges (i.e., does not change within a certain tolerance) then use the control polygon to check if the curve self-intersect. This is better than sampling points on the curve and using line segments from these sampled points to check for self-intersection.

You can also use control polygon to detect cusps. Try to do degree elevation of the Bezier curve and the control points will start to form a loop around where the cusp is. The only problem with this approach is that the control polygon converges slowly with degree elevation.

The following pictures show an example of using degree elevation to narrow down the cusp. The first picture shows a degree 3 Bezier curve with a cusp at t=0.5. The 2nd and the 3rd picture show the result with degree being elevated to 7 and 15 respectively. As we can see that the control points start to loop around the cusp.

Answer 2

Let's suppose we have a Bézier curve $\mathbf{C}(t)$ of degree $m$, and denote is its control points by $\mathbf{P}_0, \ldots, \mathbf{P}_m$.

A cusp can occur only at a point where $\mathbf{C}'(t)=0$.

But we can also consider $\mathbf{C}'(t)$ to be a Bézier curve; it has degree $m-1$ and its "control points" are $\mathbf{P}_1 - \mathbf{P}_0, \ldots, \mathbf{P}_m - \mathbf{P}_{m-1}$. Pedantic detail: I put the term "control points" in quotes because these things aren't really points, of course, they are vectors. You can identify them with points by locating them at some common origin. The "derivative curve" constructed this way is often called the hodograph of the original curve.

So the original curve can have a cusp only if its hodograph curve passes through the origin. In the answer provided by @Fang, you can see that the hodograph curve is a quadratic that passes through the origin at $t=\tfrac12$.

As you remarked, finding places where $\mathbf{C}'(t)=0$ is a nasty root-finding problem that can only be solved by numerical methods. But if $\mathbf{C}'(t)$ is expressed in Bézier form (the hodograph), as above, then there's an obvious useful fact available to us: the curve $\mathbf{C}'(t)$ can not pass through the origin if the origin is not contained within the convex hull of its control points.

This suggests the following algorithm: construct the hodograph curve and then repeatedly refine it in such a way that the control polygon gets closer to the curve. There are two refinement methods that will work: either subdivision or degree elevation. Subdivision is probably easier, numerically, and converges faster. Continue the refinement until you get a control polygon that doesn't contain the origin, or you run out of patience. If you refine a great many times, and your control polygon still contains the origin, then the hodograph must pass very close to the origin, and this means that the original curve has something very close to being a cusp.