Constant length bezier curve

[peterbone]

hello

I'm writing a program that uses a quadratic bezier curve and I want it to stay the same length as the curve bends - as the difference in angle between the first and second line segments changes. Here is a program that demonstrates what I'm trying to do:
http://www.geocities.com/peter_bone_uk/bezier.zip
Drag the red dots to bend the curve. Select/deselect the checkbox to see what the curve looks like with constant length and with the normal bezier curve.
To make it constant length I'm recalculating the control point of the bezier curve by offsetting it from it's normal position. The green dot in the program shows the repositioned control point. The direction of offset is directly between the 2 line segments joining the 2 end points 2 the control point. The offset amount is currently calculated using an iterative method by calculating the length of the curve (also an iterative method) and adjusting the offset of the control point until the length is within the desired error limits. This works fine but it's slow because of the iteration and I was wondering if it's possible to calculate the offset analytically.
I have an analytical approximation method that works well, but only if the 2 line segments are equal length. This equation is a polynomial approximation that I found using the polynomial curve fitting function in MATLAB. The equation is:

OffsetDistance = (-0.002993458 * A^4 + 0.00862333 * A^3 - 0.00551 * A^2 + 0.18482917 * A) * (L1+L2)
where
A is the difference in polar angle between the 2 line segments (ie if the curve is straight the angle difference is 0)
L1, L2 are the lengths of the line segments from the end points to the control point.
This equation only works if L1 = L2.

So anyway, this is a rather complex problem and I don't see much hope of finding an analytical solution but I thought I'd ask you anyway.

Any help would be greatly appreciated

Peter Bone

http://www.geocities.com/peter_bone_uk

 

[rachmaninoff]

I've never done anything with Bezier curves before, but I'm looking at your problem. Simply stated, is it this:

L1 and L2 are fixed lenghts, and you're looking at the set of
{P,Q,R} points in R^2, where P and Q are fixed,
|PQ| = L1, and the choice of R is constrained by
|QR| = L2

(giving one degree of freedom, the rotation of QR about Q)

and if L' is the length of the corresponding unweighted Bezier curve where PQR is a stright line,

for each R, you want to find a point S, such that the angles of PQS and RQS are equal (restricting it to a straight line, 1 deg. of freedom)
and also such that the three-point (quadratic) Bezier curve corresponding to {P,S,R} (no Q) is equal to L'...

is this correct?

 

[rachmaninoff]

(edited several times):

I'll start:

Fix
$$\vec{P}= P_x \hat{i}+P_y \hat{j}$$
$$\vec{Q}= \vec{0}$$ (without loss of generality), and
$$L = \| QR \| = \sqrt{R_x^2 + R_y^2}$$ (for variable R)

And we define, for arbitrary 'theta',
$$\vec{R}= L \cos \theta \hat{i} + L \sin \theta \hat{j}$$
So that the PQR has a principal angle of 'theta' plus a constant angle. (edited)

Fix 'theta'. Thus we have a fixed R.

We restrict our choice of S to the line of points {S'} such that the angles of PQS' and RQS' are equal. With some basic vector algebra (helps to draw a picture here), this line {S'} is
$$\begin{align*} \{ S' : S' &= \vec{Q} + a \left( \hat{P} + \hat{R} \right) \\ &= a \left( \hat{P} + \hat{R} \right) \} \end{align}$$

with normalized vectors
$$\hat{P}=\frac{\vec{P}}{\| P \|}=\frac{p_x \hat{i} + p_y \hat{j} }{\sqrt{p_x^2+p_y^2}}$$
$$\hat{R}=\frac{\vec{R}}{\| R\|}=\frac{r_x \hat{i} + r_y \hat{j} }{\sqrt{r_x^2+r_y^2}}$$

and with 'a' as a real scalar multiplier.

Then, as I learned from these definitions from wolram's mathworld,
http://mathworld.wolfram.com/BezierCurve.html
http://mathworld.wolfram.com/BernsteinPolynomial.html

The parameteric form of the quadratic Bezier curve looks like this:
$$\begin{align*} \vec{C} (t) &= B_{0,2} \vec{P} + B_{1,2} \vec{S'} + B_{2,2} \vec{R} \\ &=(1-t)^2 \vec{P} + 2t(1-t) \vec{S'} + t^2 \vec{R} \\ &=(1-t)^2 (p_x \hat{i} + p_y \hat{j} )+ 2t(1-t) a \left( \left( \frac{p_x}{ \sqrt{ p_x^2+p_y^2} } + \frac{r_x}{ \sqrt{ r_x^2+r_y^2}} \right) \hat{i} + \left( \frac{p_y}{ \sqrt{ p_x^2+p_y^2}} + \frac{r_y}{ \sqrt{ r_x^2+r_y^2}} \right) \hat{j} \right) + t^2 (r_x \hat{i} + r_y \hat{j} ) \\ &= \hat{i} \left[ (1-t)^2 p_x + a t (1-t) \left( \frac{p_x}{ \sqrt{ p_x^2+p_y^2}} + \frac{r_x}{ \sqrt{ r_x^2+r_y^2}}\right) + t^2 r_x \right] + \hat{j} \left[ (1-t)^2 p_y + a t (1-t) \left( \frac{p_y}{ \sqrt{ p_x^2+p_y^2}} + \frac{r_y}{ \sqrt{ r_x^2+r_y^2}}\right) + t^2 r_y \right] \end{align}$$

defined on $$0 \leq t \leq 1$$

Having separated the x- and y- components of the parametric Bezier curve, we are in position to take its derivative and thus find it's arc-length, which is defined as
$$\begin{align*} A &= \int_a^b \| \frac{d}{dt} \vec{C} (t) \| dt \\ &= \int_a^b \frac{\hat{i}\frac{d}{dt} C_x(t) + \hat{j} \frac{d}{dt} C_y(t)}{\sqrt{ \left( \frac{d}{dt} C_x(t) \right) ^2+ \left( \frac{d}{dt} C_y(t) \right) ^2}} dt \\ &= \int_0^1 \frac{\hat{i} \left[ 2(1-t) p_x + a (1-2t) \left( \frac{p_x}{ \sqrt{ p_x^2+p_y^2}} + \frac{r_x}{ \sqrt{ r_x^2+r_y^2}}\right) + 2t r_x \right] + \hat{j} \left[ 2(1-t) p_y + a (1-2t) \left( \frac{p_y}{ \sqrt{ p_x^2+p_y^2}} + \frac{r_y}{ \sqrt{ r_x^2+r_y^2}}\right) + 2t r_y \right] }{ \sqrt{ stuff }} dt \end{align}$$

 

[rachmaninoff]

To clear things up, I'll define an arbitrary notation,

$$\bar{p_x} \equiv \frac{p_x}{ \sqrt{ p_x^2+p_y^2}}$$
And likewise for $$p_y, r_x, r_y$$.

Continuing on with the arclength:

$$\begin{align*} A &= \int_0^1 \frac{\hat{i} \left[ 2(1-t) p_x + a (1-2t) \left( \bar{p_x} + \bar{r_x} \right) + 2t r_x \right] + \hat{j} \left[ 2(1-t) p_y + a (1-2t) \left( \bar{p_y} + \bar{r_y} \right) + 2t r_y \right] }{ \sqrt{ \left[ 2(1-t) p_x + a (1-2t) \left( \bar{p_x} + \bar{r_x} \right) + 2t r_x \right]^2+\left[ 2(1-t) p_y + a (1-2t) \left( \bar{p_y} + \bar{r_y} \right) + 2t r_y \right]^2}} dt \end{align}$$

What we want to do, as I figure, is isolate 'a' as a function of everything else (meaning, a function of P and R, as well as the arclength A);

(if we do that then we're essentially done.)

 

[rachmaninoff]

Got an answer from THE INTEGRATOR , typing it up...

edit: it's a huge, multline expression, I'll come back to this after coffee...

-rachmaninoff, @GMT 21:31

 

[rachmaninoff]

Earlier I obtained the antiderivative from The Integrator; five pages of algebra later, everything "simplifies" to:

$$\left( k_0 + k_1 a + \sqrt{h_0+h_1 a + h_2a^2} \right)^{\left( 2-\frac{p_x}{\sqrt{p_x^2+p_y^2}} - \frac{r_x}{\sqrt{r_x^2+r_y^2}} \right) } \left( c_0+ c_1a + \sqrt{j_0+j_1 a+ j_2 a^2} \right)^{\left( \frac{p_x}{\sqrt{p_x^2+p_y^2}} + \frac{r_x}{\sqrt{r_x^2+r_y^2}}-\frac{1}{a}2r_x \right)}=e^A$$

where the (constant) coefficients are:

$$\begin{align*}&k_0=-2p_y\\ &c_0=2r_y \\ &k_1=c_1=\left( \frac{p_y}{\sqrt{p_x^2+p_y^2}} + \frac{r_y}{\sqrt{r_x^2+r_y^2}} \right) \\ &h_0=4 \| P \| ^2 = 4p_x^2+4p_y^2 \\ &h_1=4p_x \left( \frac{p_x}{\sqrt{p_x^2+p_y^2}} + \frac{r_x}{\sqrt{r_x^2+r_y^2}} \right) - 2 p_y \left( \frac{p_y}{\sqrt{p_x^2+p_y^2}} + \frac{r_y}{\sqrt{r_x^2+r_y^2}} \right) \\ & \\ &h_2 = \left( \frac{p_x}{\sqrt{p_x^2+p_y^2}} + \frac{r_x}{\sqrt{r_x^2+r_y^2}} \right)^2+\left( \frac{p_y}{\sqrt{p_x^2+p_y^2}} + \frac{r_y}{\sqrt{r_x^2+r_y^2}} \right)^2 \\ &j_0= 4 \| R \| ^2= 4r_x^2+r_y^2 \\ &j_1= - 4 r_x \left( \frac{p_x}{\sqrt{p_x^2+p_y^2}} + \frac{r_x}{\sqrt{r_x^2+r_y^2}} \right) + 2 r_y \left( \frac{p_y}{\sqrt{p_x^2+p_y^2}} + \frac{r_y}{\sqrt{r_x^2+r_y^2}} \right) \end{align}$$

$$\begin{align*} &j_2 = h_2=\left( \frac{p_x}{\sqrt{p_x^2+p_y^2}} + \frac{r_x}{\sqrt{r_x^2+r_y^2}} \right)^2+\left( \frac{p_y}{\sqrt{p_x^2+p_y^2}} + \frac{r_y}{\sqrt{r_x^2+r_y^2}} \right)^2 \end{align}$$

This gives an implcit equation relating the arclength of the Bezier curve, A, and a scalar 'a' which uniquely determines the point "S" we were looking for. Ideally, we would solve this equation to yield a as dependent on everything else, in particular, a=f(A).

 

[rachmaninoff]

Short answer, as far as I can tell there is no closed form explicit formula for the offset distance for S.

 

[peterbone]

Wow, I really appreciate all the effort you put into this. I wasn't sure anyone was going to reply. I understand some of what you've written but having learned mathematics in an engineering degree my knowledge of pure maths and standard notation is limited. The short answer at the end was very helpful though. I should have known there would be no explicit formula for the offset since there is no explicit formula for the length of a bezier curve.
I guess I'll just have to use my numerical method for calculating the offset. If I store the offset in memory every time the curve is changed then I don't need to calculate it every time I draw the lines.

Thanks again for all the effort you put in. I'll carry on trying to understand what you wrote after 'L1 and L2 are fixed lenghts, and you're looking at the set of' and before 'Short answer, as far as I can tell there is no closed form explicit formula for the offset distance for S'!

Peter

 

[rachmaninoff]

I should have known there would be no explicit formula for the offset since there is no explicit formula for the length of a bezier curve.

Oh, if you want the arclength, I can give you that:

$$\begin{align*} \mbox{Arclength}&=\int_a^b \| \frac{d}{dt} \vec{C} (t) \| dt \\ &={\left( 2-\frac{p_x}{\sqrt{p_x^2+p_y^2}} - \frac{r_x}{\sqrt{r_x^2+r_y^2}} \right) } \log \left( k_0 + k_1 a + \sqrt{h_0+h_1 a + h_2a^2} \right) \\ &+ {\left( \frac{p_x}{\sqrt{p_x^2+p_y^2}} + \frac{r_x}{\sqrt{r_x^2+r_y^2}}-\frac{1}{a}2r_x \right)} \log \left( c_0+ c_1a + \sqrt{j_0+j_1 a+ j_2 a^2} \right) \end{align}$$

Which is explicit (the coefficients are defined in my last post). The geometry I used transpoes Q to (0, 0); P=(px, py) and R=(rx,ry) are anywhere. You can get R from your 'theta' by
$$R=(r_x, r_y) = \left( R \cos \left( \theta - \theta_0 \right), R \sin \left( \theta - \theta_0 \right) \right)$$
Where $\theta$ is the angle between PQ and QR, and $\theta _0$ is the constant angle of PQ with the x-axis.

edit: it'll look much simpler in polar notation (if you make the theta-substitution that makes it useful).

 

[rachmaninoff]

Or, in your notation,

$$\mbox{Arclength} &=\left( 3 + \cos \theta \right) \log \left( \frac{ \| S \| }{\sqrt{ 2+2 \cos \theta }} \sin \theta + \sqrt{4 L_1^2- 4 L_1 \left( 1- \cos \theta \right) \frac{ \| S \| }{\sqrt{ 2+2 \cos \theta }} + \left( 2 + 2 \cos \theta \sin \theta \right) \frac{ \| S \|^2 }{ 2+2 \cos \theta }} } \right)$$
$$\begin{align*} &+ \left(\cos \theta - 1 +L_2 \frac{\sqrt{ 2+2 \cos \theta }} { \| S \| }2 \cos \theta \right) \log \left( \frac{ \| S \| }{\sqrt{ 2+2 \cos \theta }} \sin \theta + \\ & \sqrt{4L_2^2+\left( -4 L_2 \cos \theta \left( -1 + \cos \theta + 2 L_2 \sin^2 \theta \right) \right) \frac{ \| S \| }{\sqrt{ 2+2 \cos \theta }} \sin \theta + \left(2 + 2 \cos \theta \sin \theta \right) \frac{ \| S \|^2 }{ 2+2 \cos \theta }} \end{align}$$

(read as one multiline expression)

 

[peterbone]

Thanks, using that equation for the length should speed it up a bit but what is ||S|| ?

 

[rachmaninoff]

what is ||S|| ?

The length of your line QS, where S is the offset control point you're looking for.

Actually, the expicit arclength would take a lot more cpu time than any approximation - you're better off with numerical methods.

 

[peterbone]

oh right, it's just the offset then.
Yeah, I was thinking that that equation has got a lot of slow routines in it like sins, cosines and square roots. I may try it though.