Sign in to follow this  
dawberj3

Travelling along a curve

Recommended Posts

I have a collection of bezier curves (each has 2 end points and 2 control points) in which I need to travel along them at a constant speed but some curves are shorter and longer than others hence they speed up/slow down when using 0 < t < 1. Ive read sumwhere that I need to turn the curves into degree 2 of linear pieces. Linear one seem easier so can someone point me in the right direction in how to start this? Thx

Share this post


Link to post
Share on other sites
I think I need to do something with this: http://www.geometrictools.com/Documentation/MovingAtConstantSpeed.pdf but its obviously written by someone with a Maths degree.

The puesdo code at the end is kind of useful but can anyone translate what I need on that document to something more understandable?

Thx

Share this post


Link to post
Share on other sites
@ury
The specific pdf deals with arc length parametrizations of parametric curves. Bezier curves are not parametric curves, in a fashion that you would simply plug the desired "t" value, and evaluate its respective position vector...
In order to reparametrize a curve, one has to have a parametric expression of the length of its derivative, expressed via its initial parameter.
Bezier curves are defined with recursive bases polynomials, it's not just a symbolic expression that can you simply differentiate.
I really think that the only practical solution to this problem cam be obtained with numeric methods...
I only have basic experience with them myself, so if I'm missing something big, please let me know.

edit: I'm sorry, I had read this quite long ago, and didn't remember there was a numerical solution section too.

@dawberj3
Quote:

Ive read sumwhere that I need to turn the curves into degree 2 of linear pieces.

Now that you mention this, this could turn out to be a good hack...
Evaluate a sufficient number of points of the curve, and create the line segments that connect them. This can be done using DeCasteljau's algorithm. Notice that you will need to remember which subinterval of [0,1] was used to create each segment.
These points will have arbitrary distances both on the curve, and in the "euclidean" sense. (this is the original problem)
The length of the specific line segment though, approximates the length of the curve between the values (t1, t2) that where used to create it.
So, when your object/camera moves on the curve within the interval (t1, t2), use the length of the respective segment to adjust the time it will take you to interpolate from the parameter t1 to t2.
For a sufficient number of points, the approximation will be quite good.
Of course, this is the big idea... You don't have to apply it verbatim. E.g. you don't need to calculate all that info; you can calculate the next segment on the fly.

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
@ury
The specific pdf deals with arc length parametrizations of parametric curves. Bezier curves are not parametric curves, in a fashion that you would simply plug the desired "t" value, and evaluate its respective position vector...
In order to reparametrize a curve, one has to have a parametric expression of the length of its derivative, expressed via its initial parameter.
Bezier curves are defined with recursive bases polynomials, it's not just a symbolic expression that can you simply differentiate.

nope. beziers are parametric curves, and obtaining their parametric representation is very easy.
Quote:

I really think that the only practical solution to this problem cam be obtained with numeric methods...


this is true. this problem asks for a numerical solution. it has been discussed numerous times on these boards: a search here should turn up something.

Share this post


Link to post
Share on other sites
Don't let all the math confuse you. The basic idea is that to find the length of a curve you integrate the length of its derivative. In other words, to find the total distance traveled by a particle between t0 and t1, you integrate its speed between those times.

With arclength parameterization, you know what you want the total distance to be, but you don't know the time values. Actually, you know that t0 is 0 (since you start from the beginning of the curve), but you don't know what t1 is. However using Newton's method you can approximate t1. When you then go back and plug in t1 into the Bezier curve, you get back the arclength you want. In essence, you can control the motion of the particle using travel distance (arclength), which allows you to establish constant speed.

Quote:
Original post by dawberj3
The puesdo code at the end is kind of useful but can anyone translate what I need on that document to something more understandable?

The pseudocode is basically Newton's method, however it does a lot of hand-waving with regard to the Integral, Speed, and ArcLength functions. You can use a numerical integration method for Integral such as Simpson's rule or the 3/8 rule. Speed is simply a matter of finding the first derivative of the Bezier curve function with respect to time for each axis, i.e. (dx/dt), (dy/dt), and (dz/dt). From that point you can find the speed using sqrt( (dx/dt)2 + (dy/dt)2 + (dz/dt)2 ) at any time.

Share this post


Link to post
Share on other sites
My specific words were that they're not parametric curves in a fashion that you would simply plug the desired "t" value, and evaluate its respective position vector....
My only experience with such splines is that I've merely drawn some 3d nurbs, but I remember that there were recursive expressions that had to be evaluated. I don't know if it is feasible to differentiate such quantities directly.

Unless -of course- you agree to fix them at a certain order (e.g. cubic) and expand their expressions. It may look ugly, but it would work. This is probably what you're talking about... (?)

Share this post


Link to post
Share on other sites
Quote:
Original post by someusername
My specific words were that they're not parametric curves in a fashion that you would simply plug the desired "t" value, and evaluate its respective position vector....
My only experience with such splines is that I've merely drawn some 3d nurbs, but I remember that there were recursive expressions that had to be evaluated. I don't know if it is feasible to differentiate such quantities directly.

Unless -of course- you agree to fix them at a certain order (e.g. cubic) and expand their expressions. It may look ugly, but it would work. This is probably what you're talking about... (?)

You're thinking of a B-Spline, which is a generalization of a Bezier curve and defined using recursive basis functions. But an n-order Bezier curve has exactly n+1 control points, and is expressed as an explicit polynomial (and hence easily differentiable). You can also differentiate the basis functions of a B-Spline without too much difficulty, but since it can be a mind bender differentiating a recurrence relation it's probably easier just to look for the definition online. But it isn't ugly at all.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this