We're covering Arc length next week in Calculus 3.
I've looked at this problem for my own bezier macro. The original formula I used
for calculating a Bezier curve in 3 space is as follows:

A, B,C, and D are position vectors in space
t is a scalar value that goes from 0 to 1

The position on the spline is:
A*(1-t)^3 + 3*B*t*(1-t)^2 + 3*C*t^2*(1-t) + D*t^3

There is an easier way to calculate this, with several lines of algabraic
playing aroud:

E = -A + 3*D + 3*C + D
F = 3*A - 6*B + 3*C
G = -3*A + 3*B

and then the position is:
E*t^3 + F*t^2 + G*t + A

According to the textbook, the arclength is the integral of the derivitave taken
from 0 to 1. (In this case)
The derivative of the curve can be found with 3*E*t^2 + 2*F*t + G

The problems I am having is that the text deals with vector functions
differently than I have here. It uses a parametric form, so there are separate
formulas for x,y, and z. I have to expand A,B,C,D (and then E,F, and G) into
component forms to see how easily this will simplify. I suspect that after
Tuesday I will be able to figure this out. The book isn't too hot on explaining
itself, but my instructor loves this stuff.

I'll report back when I know more

Josh

Chris Colefax wrote:

> Edward Coffey <e.c### [at] ugradunimelbeduau> wrote:
> > A while back there were a couple of posts about splines and how to measure
> > the length of bezier splines, find points at particular distances along
> > them, and move along them at constant speed without resorting to
> > approximation - was that problem solved?  How is it done for UV mapping in
> > MegaPOV, approximation?
> > I've found a related bit of calculus which shouldn't take too long to
> adapt
> > and convert to simple formula if no-one has done this yet.
>
> Are you suggesting a formula that returns the distance of a cubic spline at
> a particular point?  If so, it's my understanding (after a lot of research
> and many attempts while developing my Spline Macro File -
> http://www.geocities.com/ccolefax/spline) that there is no known analytical
> solution to this problem.  If you have indeed found one, I for one would be
> very interested!
>
> For my macro file I settled on sampling points along the spline and using
> the linear distances between them (both for length and constant speed
> calculations).  In some areas I've also used an approximation of the segment
> lengths based on the linear distance between the end points and the length
> of the segment's constraining hull.  Of course, it would be far more
> preferable to use an exact and neat solution, if calculus can offer one...

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

Post a reply to this message

> Are you suggesting a formula that returns the distance of a cubic spline
at
> a particular point?  If so, it's my understanding (after a lot of research
> and many attempts while developing my Spline Macro File -
> http://www.geocities.com/ccolefax/spline) that there is no known
analytical
> solution to this problem.  If you have indeed found one, I for one would
be
> very interested!

I should have read ahead in the arc-length section of my calculus text - the
bit where it says there is often no way of solving the integral required
because of the difficulty in finding the appropriate antiderivative.

Having got stuck into the maths I've found that the problem boils down to
finding the antiderivative of the square-root of a polynomial of degree
(n-2)^2, where n is the number of control points in the spline.  In the most
common case (for me anyway) of 4 points, the polynomial is a 4th degree.  I
can't think of how to do that, but I'll ask someone in the maths department
at uni if I can't nut it out over the weekend.

Post a reply to this message

Edward Coffey <e.c### [at] ugradunimelbeduau> wrote:
> I should have read ahead in the arc-length section of my calculus text -
the
> bit where it says there is often no way of solving the integral required
> because of the difficulty in finding the appropriate antiderivative.
>
> Having got stuck into the maths I've found that the problem boils down to
> finding the antiderivative of the square-root of a polynomial of degree
> (n-2)^2, where n is the number of control points in the spline.  In the
most
> common case (for me anyway) of 4 points, the polynomial is a 4th degree.
I
> can't think of how to do that, but I'll ask someone in the maths
department
> at uni if I can't nut it out over the weekend.

When I said there was no known solution, I meant quite literally that no-one
has been able to solve this problem since the first invention/discovery of
the various cubic spline functions!  I'd certainly applaud your efforts to
be the first, but it seems that approximation works well for just about
everyone who's had a need for finding the length of a cubic spline segment -
so don't lose any sleep over it...

Post a reply to this message

Edward Coffey <e.c### [at] ugradunimelbeduau> wrote in message
news:39262485@news.povray.org...
> ... the problem boils down to
> finding the antiderivative of the square-root of a polynomial of degree
> (n-2)^2, where n is the number of control points in the spline.

By which I mean 2(n-2) of course.

Post a reply to this message

Chris Colefax <chr### [at] tagpovrayorg> wrote in message
news:39262b8b@news.povray.org...
> When I said there was no known solution, I meant quite literally that
no-one
> has been able to solve this problem since the first invention/discovery of
> the various cubic spline functions!  I'd certainly applaud your efforts to
> be the first, but it seems that approximation works well for just about
> everyone who's had a need for finding the length of a cubic spline
segment -
> so don't lose any sleep over it...

Indeed, the solution can be found, but it is enormous, complex and uses
functions that can only be calculated by approximation!
I suspect that your method actually gives the best accuracy : cpu-time
ratio.

Post a reply to this message

I'm sorry I haven't responded yet. I finally got it through my thick skull on the
first
page. So I understand your restrictions. The next part is still giving me trouble, but
I'll keep plugging away at it.

I don't quite follow the linear relationship for S double prime sub i that you list on
the top of page two.
Josh

Serge LAROCQUE wrote:

> Josh, I was wondering if you ever got my little 'report' on cubic splines and if you
> found it useful?

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

Post a reply to this message

Oops. I tried this code from home and it didn't work. It should look like:

E = -A + 3*D -3*C + D
F = 3*A - 6*B + 3*C
G = -3*A + 3*B

The position vector is E*t^3 + F*t^2 + G*t  A
The first derivative is 3*E*t^2 + 2*F*t * G
The second derivative is 6*E*t + 2*F

The unit tangent vector is the normalized first derivative and shows the "forward"
vector at t
The "right" vector can be found by the cross product of the "up" vector and the unit
tangent vector. This is where curvature comes into play. I'm guessing that I can
alter the "up" vector based on the curvature, but the mechanics are past me right
now.

As for the issue of arc length, it should suffice to integrate the magnitude of the
second derivate from 0 to 1. Again, the specific method of taking my formulas and
converting them to a set of parametric equations is a lot of sratch work.

Josh

Josh English wrote:

> We're covering Arc length next week in Calculus 3.
> I've looked at this problem for my own bezier macro. The original formula I used
> for calculating a Bezier curve in 3 space is as follows:
>
> A, B,C, and D are position vectors in space
> t is a scalar value that goes from 0 to 1
>
> The position on the spline is:
> A*(1-t)^3 + 3*B*t*(1-t)^2 + 3*C*t^2*(1-t) + D*t^3
>
> There is an easier way to calculate this, with several lines of algabraic
> playing aroud:
>
> E = -A + 3*D + 3*C + D
> F = 3*A - 6*B + 3*C
> G = -3*A + 3*B
>
> and then the position is:
> E*t^3 + F*t^2 + G*t + A
>
> According to the textbook, the arclength is the integral of the derivitave taken
> from 0 to 1. (In this case)
> The derivative of the curve can be found with 3*E*t^2 + 2*F*t + G
>
> The problems I am having is that the text deals with vector functions
> differently than I have here. It uses a parametric form, so there are separate
> formulas for x,y, and z. I have to expand A,B,C,D (and then E,F, and G) into
> component forms to see how easily this will simplify. I suspect that after
> Tuesday I will be able to figure this out. The book isn't too hot on explaining
> itself, but my instructor loves this stuff.
>
> I'll report back when I know more
>
> Josh
>
> Chris Colefax wrote:
>
> > Edward Coffey <e.c### [at] ugradunimelbeduau> wrote:
> > > A while back there were a couple of posts about splines and how to measure
> > > the length of bezier splines, find points at particular distances along
> > > them, and move along them at constant speed without resorting to
> > > approximation - was that problem solved?  How is it done for UV mapping in
> > > MegaPOV, approximation?
> > > I've found a related bit of calculus which shouldn't take too long to
> > adapt
> > > and convert to simple formula if no-one has done this yet.
> >
> > Are you suggesting a formula that returns the distance of a cubic spline at
> > a particular point?  If so, it's my understanding (after a lot of research
> > and many attempts while developing my Spline Macro File -
> > http://www.geocities.com/ccolefax/spline) that there is no known analytical
> > solution to this problem.  If you have indeed found one, I for one would be
> > very interested!
> >
> > For my macro file I settled on sampling points along the spline and using
> > the linear distances between them (both for length and constant speed
> > calculations).  In some areas I've also used an approximation of the segment
> > lengths based on the linear distance between the end points and the length
> > of the segment's constraining hull.  Of course, it would be far more
> > preferable to use an exact and neat solution, if calculus can offer one...
>
> --
> Josh English
> eng### [at] spiritonecom
> "May your hopes, dreams, and plans not be destroyed by a few zeros."

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

Post a reply to this message

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