# Spline parameterisation

This topic is 3641 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Say I have a list of N points in 3D space, each with an orientation matrix/quaternion. I have these requirements: 1)To generate a curve which passes through all points 2)Based on a single parameter 0<=T<=100, I can get the position/orientation at T% along the total curve (in theory based on absolute curve length but some approximation is considered likely/acceptable). So basically, it's similar to having a camera travelling along some path in space. In reality, I hope that only 3 or 4 points will be needed so if there is a special case which is much simpler than trying to solve for any N, that would certainly be of interest.

##### Share on other sites
Quote:
 Original post by JDXSolutions LtdSay I have a list of N points in 3D space, each with an orientation matrix/quaternion. I have these requirements:1)To generate a curve which passes through all points

Then use a Bezier spline (not NURBS). You will define one control vertex for each point, and another one for each tangent -- which you can compute by rotating using your matrix/quaternion.

Quote:
 2)Based on a single parameter 0<=T<=100, I can get the position/orientation at T% along the total curve (in theory based on absolute curve length but some approximation is considered likely/acceptable).

As Bezier curves are naturally parameterized by arc length, this is not problem.

##### Share on other sites
Quote:
 As Bezier curves are naturally parameterized by arc length...
Are you sure about that? I'm pretty sure that's incorrect. (Or maybe I'm misunderstanding what you mean...)

##### Share on other sites
Quote:
Original post by jyk
Quote:
 As Bezier curves are naturally parameterized by arc length...
Are you sure about that? I'm pretty sure that's incorrect. (Or maybe I'm misunderstanding what you mean...)

No, you are actually correct. It is parameterized by time.

However the problem is still not too difficult. You have a couple options.

1) If the curve is not too wild, you may find that taking steps in the time parameter looks good enough for your purposes. (in fact, you may even prefer the way this looks)

2) I do not think there is a closed form solution for the Bezier curve reparamaterized by arc length. However the derivative is easy to calculate:

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-der.html

One approach would therefore be to take steps in the direction of the derivative, and then reproject back onto the Bezier curve. In order to re-project, you will probably need to linearize the curve into smaller segments.

I'm also thinking that there might be a more clever way to do this, by doing something like...taking steps in "t" divided by the magnitude of the derivative. I'm not sure if that will work exactly but it might be possible to finnagle the mathematics so that it does, if it doesn't.

##### Share on other sites
That's a good explanation of some of the basic principles of differential geometry, and explains how to reparameterize a curve by arc length. Unfortunately this requires integrating the derivative of the curve, which you can't do in closed form for a Bezier curve -- or any other curve based on your own specified control vertices, really. While it is possible to integrate it numerically, that's probably not a very efficient solution. David Eberly does describe a way to improve performance using a polynomial approximation, which may be another pretty good, albeit complicated, solution.

##### Share on other sites

The numerical integration might still work out if the curve is rather static in the OP's scenario. In a pre-processing step, the reparameterization could be used to come up with a set of points spaced evenly across the curve. You could generate enough of these points so that the speedups/slowdowns due to interpolation between them are barely noticable or even linear interpolation produces acceptable results.

Even with my lowly math skills, I realize that's not very elegant though, nor particularly efficient or correct [smile]

##### Share on other sites
To my knowledge, this curve is entirely static, so precomputing some data is entirely feasible.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634052
• Total Posts
3015262
×