Split a cubic Bézier curve at a point

user_405017 0
Viewed 1739

This question and this question both show how to split a cubic Bézier curve at a particular parameterized value 0 ≤ t ≤ 1 along the curve, composing the original curve shape from two new segments. I need to split my Bézier curve at a point along the curve whose coordinate I know, but not the parameterized value t for the point.

For example, consider Adobe Illustrator, where the user can click on a curve to add a point into the path, without affecting the shape of the path.

Assuming I find the point on the curve closest to where the user clicks, how do I calculate the control points from this? Is there a formula to split a Bézier curve given a point on the curve?

Alternatively (and less desirably), given a point on the curve, is there a way to determine the parameterized value t corresponding to that point (other than using De Casteljau's algorithm in a binary search)?

My Bézier curve happens to only be in 2D, but a great answer would include the vector math needed to apply in arbitrary dimensions.

cubic-bezier bezier computational-geometry math geometry
1 Answers

It is possible, and perhaps simpler, to determine the parametric value of a point on the curve without using De Casteljau's algorithm, but you will have to use heuristics to find a good starting value and similarly approximate the result.

One possible, and fairly simple way is to use Newton's method such that:

tn+1 = tn - ( bx(tn) - cx ) / bx'(tn)

Where bx(t) refers to the x component of some Bezier curve in polynomial form with the control points x0, x1, x2 and x3, bx'(t) is the first derivative and cx is a point on the curve such that:

cx = bx(t) | 0 < t < 1

the coefficients of bx(t) are:

A = -x0 + 3x1 - 3x2 + x3
B = 3x0 - 6x1 + 3x2
C = -3x0 + 3x1
D = x0

and:

bx(t) = At3 + Bt2 + Ct + D,
bx'(t) = 3At2 + 2Bt + C

Now finding a good starting value to plug into Newton's method is the tricky part. For most curves which do not contain loops or cusps, you can simply use the formula:

tn = ( cx - x0 ) / ( x3 - x0 ) | x0 < x1 < x2 < x3

Now you already have:

bx(tn) ≈ cx

So applying one or more iterations of Newton's method will give a better approximation of t for cx.

Note that the Newton Raphson algorithm has quadratic convergence. In most cases a good starting value will result in negligible improvement after two iterations, i.e. less than half a pixel.

Finally it's worth noting that cubic Bezier curves have exact solutions for finding extrema via finding roots of the first derivative. So curves which are problematic can simply be subdivided at their extrema to remove loops or cusps, then better results can be obtained by analyzing the resulting section in question. Subdividing cubics in this way will satisfy the above constraint.

user_13219440
Related