Aha! I see that now. This is close to how I calculate things in animations, but I'm
not
familiar with this form. Now that I get it, it's probably easier than what I normally
do. My
formula would look like

S double prime of x = [ [ ( x - x sub i ) * ( z sub i +1 - z sub i ) ] / (x sub i +1 -
x sub
1)  ] + z sub i

which is probably harder to integrate.

Thanks for the tip. I'm getting closer. I understand what you're acheiving here, which
is a
plus on my side.

Josh

Serge LAROCQUE wrote:

> > I don't quite follow the linear relationship for S double prime sub i that you
list on
> > the top of page two.
>
> Ok. S'' is the second derivative of the spline. It is shown in Figure 1. I know,
it's not
> much to look at :-). Perhaps I should have made the graph a bit bigger with more
points.
> But basically, we want second derivative continuity from segment to segment, and for
a
> cubic, that means that it must change linearly from point to point. The equation can
be
> easily derived by applying the algorithm for finding the equation of a line based on
2
> pairs of (x,y) coordinates [with (x sub i,z sub i) and (x sub i+1,z sub i+1]. After,
you do
> a bit of algebraic manipulation to get it in the form of S'' = A*(x-x sub i) + B*(x
sub i+1
> - x), [rather than S'' = K*x + M ] and you get the equation. I have done this check
myself
> to make sure it was correct :-).
>
> One thing to note is that at this point you don't even know what S'' is equal to at
each
> point. You assume they are z sub i. You find their value when you solve the system
of
> equations. Once that is solved, you're in business and you can form your
polynomials, one
> for each interval.

--
Josh English
eng### [at] spiritonecom
"May your hopes, dreams, and plans not be destroyed by a few zeros."

Post a reply to this message

Actually, I have succeeded.

I couldn't follow everything you had, and the system of equations was a bit beyond
what I'm capable
of. Once I figured out what you were doing and I followed your logic, I applied it to
what I already
know, bezier curves.

I took an array of position vectors, and came up with a method of generating the
control points for
the bezier curves, and then I create an array of bezier curves, and voila, I have a
series of
predefined points being connected by a single path.

I couldn't have done it without that document, tho. When it comes down to it, a bezier
curve is a
third degree polynomial, so I can easily calculate the first and second derivative. I
know I have
first derivative continuity, but I am not convinced that my method guarentees second
derivative
continuity yet, so if I tried to animate a point through this series of curves it
would have a speed
different that what I'd expect. That's assuming that it crosses every point at equal
intervals. I am
now working on calculating "timestops" along the points, which should allow for a
continuous speed
along the spline.

Thanks for the document. I am keeping the goal to understand it enough on my list, so
someday it will
make sence for me.

Josh

Serge LAROCQUE wrote:

> I was just thinking, since this cubic spline algorithm requires solving a set of
linear
> equations, I don't know if you could use it directly in a POV-Ray scene file, you
might need to
> get a spreadsheet to calculate and export the points...... not the greatest if
you're going to
> change it a lot, or animate. I suppose you could use the VB macros in an Excel
spreadsheet to
> export a set of points that would change over time, but again you would have to
ensure you export
> one for each clock value................... :-/ Depends on what you want to do with
the algorithm
> I guess :-) BTW did you look at the spreadsheet I included? You can change the
y-values, not the
> x-values though.

--
Josh English
eng### [at] spiritonecom
"May your hopes, dreams, and plans not be destroyed by a few zeros."

Post a reply to this message

Get ready for another long-winded pendantic post ; )

My bezier.inc file can be found here:
 http://www.spiritone.com/~english/cyclopedia/include/bezier.inc

but it is not well documented yet.

Here's a brief rundown.  I don't have a link handy (I'm sure Ken does) for the graphic
portion of the
process, but it's easy to describe.

Declare four points in space, and label them A,B,C, and D. A is the starting point of
the spline, and D is
the end point. B and C are your control points.
Graphically:
find the midpoint between A and B and call it E,
find the midpoint between B and C and call it F,
find the midpoint between C and D and call it G.
find the midpoint between E and F and call it H,
find the midpoint betweenF and G, call it I.
The last point is J, which is directly inbetween H and I.

Out of all these points, only A,J, and D are on the line, but if you have drawn this
all out you will see
that you can apply the process recursively, using A,E,H, and J as one set, and J,I,G
and D as the other. This
process repeats until the full curve is drawn.

Mathematically, the formua for a bezier curve is a parameatric equation. We'll use t,
and it will go from 0
to 1. At t=0 we are at A, and at t=1 we are at D.
Find where you are along the curve with
position = A*(1-t)^3 + 3*B*t*(1-t)^2 + 3*C*t^2*(1-t) + D*t^3

After a whole lot of algebra we find an easier equation.
Find three constants based on A,B,C, and D:
E = -A + 3B -3C +D
F = 3A - 6B + 3C
G = -3A + 3B
position = E*t^3 + F*t^2 + G*t + A

This is a faster calculation and easier to differentiate:

Velocity = 3*E*t^2 + 2*F*t + G

Now, this means you have to specify the control points of each segment of the spline.
You only know that the
curve will pass through the starting point A and the end point D.

The problem your documents solves is to find a curve that passes through a series of
points.
Given an array of position vectors, find a smooth curve between them.

Lets work with a series of points A,B,C,D, and E. We want our curve to touch them in
that order.

It is easier to start with the second point B. B is the endpoint of the first bezier
spline and the start
point of the second bezier spline. The two conrol points associated with this point
need to lie on the same
vector (so their second derivatives are the same, or at least scalar multipliers of
eachother) and to make
things easer, assume that this vector is parallel to the vector AC. Then it is a
simple matter of finding the
lengths of these vectors to the control points.

This is a slightly different way of talking about control points than before. The two
control points
associated with B are for two different splines, since B is part of two different
splines. When you look at
the calculations for point C, it's control points being parallel to BD, you will have
the four points
necessary to draw a bezier curve between B and C

Back to the lengths of these control vectors. They need to be on the same line to
avoid a sharp corner, but
if they are of equal length the entire curve will look strange and go needlessly too
far. If A and B are far
apart, but B and C are close together, having control vectors ofthe same lenght makes
an undesirable curve.
So, to counter act this, I find the length of the vector between A and B, multiply it
by a constant value
(usally around 0.1) and use that to alter the length of vector CA, which I add to B,
to get the position of
the control vector. I then repeat the process using the length of B to C multiplied by
the same constant to
change the length of  vector AC(notice the reverse direction) and add it to B to get
the second control
points position.

It's a bit glib, and I keep kicking myself for not having a nice version of this
available yet.
Do the same thing for B,C, and D and you will have all of the necessary control points
except for two. The
control point next to point A, andthe control point for point E.

The easy solution is to declare the control point for A is A, and the control point
for E is E. I use this
and find it has the nicest results. You can label the control point for A to be B,
meaning the curve will
mover directly towards point B, move away from it and come at it "from the side".
The third method I've found is to find the vector from C to B and make the control
vector for point A
parallel to that. This looks nice as well, but it can make the curve move away from
the other points in the
sequence which might look strange animating it.

You can look at the poorly documented files I made that do most of this at:

 http://www.spiritone.com/~english/cyclopedia/include/SplineList.inc
 http://www.spiritone.com/~english/cyclopedia/include/list.pov
(list.pov is the main file. It includes SplineList.inc, which includes bezier.inc)

Please ask clarifying questions. I will answer them all.

Josh

Serge LAROCQUE wrote:

> > I couldn't follow everything you had, and the system of equations was a bit beyond
what I'm capable of.
>
> Ah I see. Well, basically, if you have a set of linear equations such as
>
> x + 2y + 3z = 4
> 2x + 3y - z = 3
> -x - 4y + 2z = 5
>
> where the number of equations must be equal to the number of unknows.
> You can form here a 3x3 matrix with just the coefficients of the unknows, in this
case:
>       | 1  2  3 |
> [A] = | 2  3  -1|
>       |-1  -4  2|
> View the equation in matrix form:
> [A]{x} = {c}
> where {x} is {x y z} and {c} is the constants on the RHS {4 3 5}
> you can solve this by calculating the inverse of [A] and multiplying both sides of
the equation (
> [A]^(-1) represents the inverse of [A])(Excel can calculate this for you, or you can
implement an
> algorithm from an algebra textbook)
> [A]^(-1)*[A]*{x}=[A]^(-1)*{c}
>
> obviously, this reduces to {x}=[A]^(-1)*{c}
> this approach is what I have used in that Excel spreadsheet.
>
> There is another method, Cramer's rule. This one involves calculating determinants
> So we have matrix [A]. calculate its determinant: |A|
> then, replace the first column by the constants column, and calculate the
determinant of this matrix,
> call it |Ax|, do the same thing with the second and third columns, call them |Ay|
and |Az|.
>
> then solve: x = |Ax|/|A|
>             y = |Ay|/|A|
>             z = |Az|/|A|  (I haven't done this in years so I'm not 100% sure it's
|Ax|/|A| or the other
> way around ;) )
>
> Of course, this is easy to do when the matrix [A] isn't too big (say 2x2 or 3x3), so
it's usually easier
> to just go with the inverse matrix approach.
>
> BTW, I am interested in these Bezier splines... do you have some URLs where I could
go and take a peak? I
> was wondering how the relationship between control points and curve points worked, I
am working on
> something which might use these. I figured it would be easy to form a curve when the
control points are
> known, but not the other way? I'd like to find more about this.
>
> Whew long post :)

--
Josh English
eng### [at] spiritonecom
"May your hopes, dreams, and plans not be destroyed by a few zeros."

Post a reply to this message