3

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Phrogz
  • 296,393
  • 112
  • 651
  • 745
  • IIRC and a [Bezier curve can be represented as a matrix](http://www.idav.ucdavis.edu/education/CAGDNotes/Matrix-Cubic-Bezier-Curve/Matrix-Cubic-Bezier-Curve.html) where you plug in the parameter value and get the coordinates, you could (in theory) calculate the inverse matrix and use it, maybe. – Will Ness Jul 08 '17 at 23:48
  • Finding the closest point on the curve assumes determining t value. – MBo Jul 09 '17 at 03:30
  • Finding the closest point accurately is not so simple because it requires solving a 6th-order polynomial in 2D. But you can also do it in screen space. When you draw the curve, draw the corresponding t-values to a separate buffer. Then, you only need to do a screen-space closest point search and you immediately know the parameter. Btw, binary search on the parameter does not work either because the coordinates in a cubic curve are not monotone. – Nico Schertler Jul 09 '17 at 07:32
  • @NicoSchertler I suspected the binary search would fail, [but I had to try](https://stackoverflow.com/a/44993719/405017). Yup. Not perfect in many spots. In my case someone else (web browser SVG) is drawing the curve, so I'll have to plot it myself to find the closest. Trouble is, SVG coordinates are not always pixels, so I must choose my marching size carefully to balance performance and precision. Thanks for your input. Good news: once I find the spot using this method, I'll also have the _t_ value to split using. – Phrogz Jul 09 '17 at 14:39
  • I suggest you read Pomax' comprehensive book on Bézier curves, probably Intersections and Root Finding will help you up to quartic curves: https://pomax.github.io/bezierinfo/#intersections. However I think you're probably better off with de Casteljau and binary search, that works on Bézier curves of any degree. – karatedog Jul 11 '17 at 11:12

1 Answers1

1

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.

Nolo
  • 846
  • 9
  • 19