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.

Post a reply to this message

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...

Post a reply to this message

"Edward Coffey" 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?

Well, not really. I found a solution, but the solution *was* approximation.
It's quite precise though.

> How is it done for UV mapping in MegaPOV,
> approximation?

I don't know...

> 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.

I'm interested in this!

Greetings,

Rune

---
Updated April 25: http://rsj.mobilixnet.dk
Containing 3D images, stereograms, tutorials,
The POV Desktop Theme, 350+ raytracing jokes,
miscellaneous other things, and a lot of fun!

Post a reply to this message

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