14

I'm looking for an algorithm to insert a new control point on a Bézier curve, without deforming.

Does anybody know a library or reference for Bézier algorithms (insertion, optimize, de Casteljau ...)?

Michael Litvin
  • 3,976
  • 1
  • 34
  • 40
sorush-r
  • 10,490
  • 17
  • 89
  • 173
  • 2
    comp.graphics.algorithms FAQ, questions 4.02 and 4.03. In what language are you looking for a library? – bobince Apr 10 '10 at 15:48

3 Answers3

23

This is called the "knot insertion problem". For Bézier curves, the de Casteljau algorithm will give you the right answer. Here is the simple algorithm for a degree 3 Bézier.

Say you want to insert a knot at a fraction t of the parameter space inside the Bézier curve defined by P0, P1, P2, P3. Here's what you do:

P0_1 = (1-t)*P0 + t*P1
P1_2 = (1-t)*P1 + t*P2
P2_3 = (1-t)*P2 + t*P3

P01_12 = (1-t)*P0_1 + t*P1_2
P12_23 = (1-t)*P1_2 + t*P2_3

P0112_1223 = (1-t)*P01_12 + t*P12_23

Then your first Bézier will be defined by: P_0, P0_1, P01_12, P0112_1223; your second Bézier is defined by: P0112_1223, P12_23, P2_3, P3.

The geometrical interpretation is simple: you split each segment of the Bézier polygon at fraction t, then connect these split points in a new polygon and iterate. When you're left with 1 point, this point lies on the curve and the previous/next split points form the previous/next Bézier polygon. The same algorithm also works for higher degree Bézier curves.

Now it can get trickier if you want to insert the control point not at a specific value of t but at a specific location in space. Personally, what I would do here is simply a binary search for a value of t that falls close to the desired split point... But if performance is critical, you can probably find a faster analytic solution.

Philippe Beaudoin
  • 3,290
  • 1
  • 22
  • 25
  • 3
    For a more efficient way to find the value t closest to a specific location in space, take a look at the paper referenced in my reply to this question: http://stackoverflow.com/questions/2742610/closest-point-on-a-cubic-bezier-curve – Adrian Lopez May 01 '10 at 18:13
2

You could also take the mathematical approach.

A qubic Bézier curve with control points p_1,p_2,p_3,p_4 can be written as:

b(t)=(1-t)^3 p_1+3t(1-t)^2 p_2+3t^2 (1-t) p_3+t^3 p_4

Its derivative w.r.t. t is

\frac{\partial b}{\partial t} = 3(1-t)^2 (p_2-p_1 )+6t(1-t)(p_3-p_2 )+3t^2 (p_4-p_3 )

To limit the curve from t0 to t1, you get new control points q_1,q_2,q_3,q_4:

q_1=b(t_0),q_4=b(t_1)

q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}

q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}

Proof

Substituting

s=\frac{t-t_0}{t_1-t_0}

t=t_0+s(t_1-t_0 )

We get

\frac{\partial b}{\partial s} = \frac{\partial b}{\partial t} \frac{\partial t}{\partial s} = (t_1-t_0) \frac{\partial b}{\partial t}

The first and last points of the sub-curve are the first and last new control points

q_1=b(t_0),q_4=b(t_1)

And the tangent at those points is

\frac{\partial{b}}{\partial{s}}_{(s=0)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}=3(q_2-q_1)

\frac{\partial{b}}{\partial{s}}_{(s=1)}=(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}=3(q_4-q_3)

So

q_2=q_1+\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_0)}

q_3=q_4-\frac{1}{3}(t_1-t_0)\frac{\partial{b}}{\partial{t}}_{(t=t_1)}

Michael Litvin
  • 3,976
  • 1
  • 34
  • 40
1

Adding this for completeness.

An open-source implementation of many Bézier path operations can be found inside GIMP source code, in gimpbezierstroke.c. For reference on inserting a new anchor, search for gimp_bezier_stroke_anchor_insert.

Michael Litvin
  • 3,976
  • 1
  • 34
  • 40