Bezier Spline - want to expand <sub> and <sup>

[dedndave]

the following is part of an article from codeproject.com
the original article uses <sub> and <sup> bulletin board codes
the codeproject website changed the way they handle these bbc's
so, now, they don't display correctly   :P
i wanted to be able to understand the math, so i put it here to read it
i also separated lines where he has multiple equations on a line

this is the full article by Oleg V. Polikarpotchkin and Peter Lee:
http://www.codeproject.com/Articles/31859/Draw-a-Smooth-Curve-through-a-Set-of-2D-Points-wit

A Bezier curve on a single interval is expressed as:

B(t)=(1-t)³P₀+3(1-t)²tP₁+3(1-t)t²P₂+t³P₃ (1)

where t is in [0,1], and

    P0 – first knot point
    P1 – first control point (close to P0)
    P2 – second control point (close to P3)
    P3 – second knot point

The first derivative of (1) is:

B'(t)=-3(1-t)²P₀+3(3t²–4t+1)P₁+3(2t–3t²)P₂+3t²P₃

The second derivative of (1) is:

B''(t)=6(1 - t)P₀+3(6t-4)P₁+3(2–6t)P₂+6tP₃

Single Segment

If we have just two knot points, our "smooth" Bezier curve should be a straight line, i.e. in (1) the coefficients in the members with the power 2 and 3 should be zero. It's easy to deduce that its control points should be calculated as:

3P₁ = 2P₀ + P₃
P₂ = 2P₁ – P₀

Multiple Segments

This is the case where we have more than two points. One more time: to make a sequence of individual Bezier curves to be a spline, we should calculate Bezier control points so that the spline curve has two continuous derivatives at knot points.

Considering a set of piecewise Bezier curves with n+1 points and n subintervals, the (i-1)-th curve should connect to the i-th one. Now we will denote the points as follows:

    Pi – ith knot point (i=1,..,n)
    P1i – first control point close to Pi
    P2i – second control point close to Pi

At the ith subinterval, the Bezier curve will be:

B_i(t)=(1-t)³P_i-1+3(1-t)²tP1_i+3(1-t)t²P2_i+t³P_i; (i=1,..,n)

The first derivative at the ith subinterval is:

B'_i(t)=-3(1-t)²P_i-1+3(3t²-4t+1)P1_i+3(2t-3t²)P2_i+3t²P_i; (i=1,..,n)

The first derivative continuity condition B'i-1(1)=B'i(0) gives:

P1_i+P2_i-1 = 2P_i-1; (i=2,..,n) (2)

The second derivative at the ith subinterval is:

B''_i(t)=6(1-t)P_i-1+6(3t-2)P1_i+6(1-3t)P2_i+6tP_i; (i=1,..,n)

The second derivative continuity condition B''i-1(1)=B''i(0) gives:

P1_i-1+2P1_i=P2_i+2P2_i-1; (i=2,..,n) (3)

Then, as always with splines, we'll add two more conditions at the ends of the total interval. These will be the "natural conditions" B''1(0) = 0 and B''n(1) = 0.

2P1₁-P2₁ = P₀ (4)
2P2_n-P1_n = P_n (5)

Now, we have 2n conditions (2-5) for n control points P1 and n control points P2. Excluding P2, we'll have n equations for n control points P1:

2P1₁ + P1₂ = P₀ + 2P₁
P1₁ + 4P1₂ + P1₃ = 4P₁ + 2P₂ ....
P1_i-1 + 4P1_i + P1_i+1 = 4P_i-1 + 2P_i (6) ....
P1_n-2 + 4P1_n-1 + P1_n = 4P_n-2 + 2P_n-1
2P1_n-1 + 7P1_n = 8P_n-1 + P_n

System (6) is the tridiagonal one with the diagonal dominance, hence we can solve it by simple variable elimination without any tricks.

When P1 is found, P2 could be calculated from (2) and (5).

[Gunther]

Hi Dave,

yes, Bezier splines are very interesting and powerful. They are often used by automobile or aircraft designers.

Gunther

[dedndave]

i just wanna make some lines from data points - lol

[avcaballero]

If you need help I can post a qbasic example.... ;)

[dedndave]

that would be very helpful, Alfonso   :t
i have a hard time with C   :P

[dedndave]

here is a test bed program
i use 2 arrays with 36 points each, and switch between them
that demonstrates draw/undraw

for now, the 2 control points are just filled in by a "dummy" proc named SynthesizeBezierControlPoints

i am trying to do something like Oleg and Peter, except i am trying to do it with extended integer math   :P

[dedndave]

i am having a hard time understanding part of this code
the first part, i think i understand
i don't expect anyone to translate it to asm
but, if you could give a simple description of what is going on, that would be great   

Code Select Expand

// Calculate first Bezier control points
// Right hand side vector
double[] rhs = new double[n];

// Set right hand side X values
for (int i = 1; i < n - 1; ++i)
rhs[i] = 4 * knots[i].X + 2 * knots[i + 1].X;
rhs[0] = knots[0].X + 2 * knots[1].X;
rhs[n - 1] = (8 * knots[n - 1].X + knots[n].X) / 2.0;
// Get first control points X-values
double[] x = GetFirstControlPoints(rhs);

// Set right hand side Y values
for (int i = 1; i < n - 1; ++i)
rhs[i] = 4 * knots[i].Y + 2 * knots[i + 1].Y;
rhs[0] = knots[0].Y + 2 * knots[1].Y;
rhs[n - 1] = (8 * knots[n - 1].Y + knots[n].Y) / 2.0;
// Get first control points Y-values
double[] y = GetFirstControlPoints(rhs);

// Fill output arrays.
firstControlPoints = new Point[n];
secondControlPoints = new Point[n];
for (int i = 0; i < n; ++i)
{
// First control point
firstControlPoints[i] = new Point(x[i], y[i]);
// Second control point
if (i < n - 1)
secondControlPoints[i] = new Point(2 * knots[i + 1].X - x[i + 1], 2 * knots[i + 1].Y - y[i + 1]);
else
secondControlPoints[i] = new Point((knots[n].X + x[n - 1]) / 2, (knots[n].Y + y[n - 1]) / 2);
}
}

/// <summary>
/// Solves a tridiagonal system for one of coordinates (x or y) of first Bezier control points.
/// </summary>
/// <param name="rhs">Right hand side vector.</param>
/// <returns>Solution vector.</returns>
private static double[] GetFirstControlPoints(double[] rhs)
{
int n = rhs.Length;
double[] x = new double[n]; // Solution vector.
double[] tmp = new double[n]; // Temp workspace.

double b = 2.0;
x[0] = rhs[0] / b;
for (int i = 1; i < n; i++) // Decomposition and forward substitution.
{
tmp[i] = 1 / b;
b = (i < n - 1 ? 4.0 : 3.5) - tmp[i];
x[i] = (rhs[i] - x[i - 1]) / b;
}

for (int i = 1; i < n; i++)
x[n - i - 1] -= tmp[n - i] * x[n - i]; // Backsubstitution.

return x;
}
}
}
the part that is really throwing me is this part

Code Select Expand

b = (i < n - 1 ? 4.0 : 3.5) - tmp[i];
x[i] = (rhs[i] - x[i - 1]) / b;
}

for (int i = 1; i < n; i++)
x[n - i - 1] -= tmp[n - i] * x[n - i]; // Backsubstitution.
the "b = (i < n - 1 ? 4.0 : 3.5) - tmp[ i ];" line is tossing me for a loop - lol
i kind of get the rest, i think

[dedndave]

Code Select Expand

b = (i < n - 1 ? 4.0 : 3.5) - tmp[i]

ok - let me see if i got this right

Code Select Expand

    .if i < n-1
        b=4.0 - tmp[i]
    .else
        b=3.5 - tmp[i]
    .endif

or, do i have it backwards ?

[Dubby]

yup that's right...  :t

Code Select Expand

(condition) ? true-clause : false-clause
and by the way the code is in C#...

the first part of code is set up the array in order to calculate the points.. the '[]' is indicating an array..
it goes like this

Code Select Expand

(NameOfArray)[index]
where the index is zero based..

hope this helps...

[dedndave]

thanks Dubby
i think i have it figured, now   :P

[avcaballero]

Here it is the example in quick basic... though if you have started already with c, maybe it were better for you to keep on going with that... Anyway, I hope that helps :)

[dedndave]

thanks, Alfonso   :t

[FORTRANS]

Hi,

   Hey, thanks for starting this.  Maybe a bit advanced, but I looked
at my copy of "Numerical Recipes", and implemented something
simpler.  So, now I have a curve fit / interpolation program to play
with.  Maybe I'll work up to a Bezier interpolation.

   I did write a Bezier curve for a paint type program a long time ago.
Only took three or four tries to get it to look okay.  Never got the
optimization part though.  Nice that computers don't mind using brute
force.

Cheers,

Steve N.

[dedndave]

hi Steve

yah - there are 2 different approaches
1) calculate "de Boor" control points if you want to use the PolyBezier API
2) calculate all the points

i am trying method 1, simply because that's where i started - lol
i think method 2 might be better, overall
i will get there, eventually

[dedndave]

well, it's trying to work - lol
at least it doesn't crash