• entries
743
1924
• views
581091

# Curves 2

438 views

Man, the problems of moving at a constant speed over a quadratic Bezier curve are more of an issue than I thought. The camera movement sucks.

I understand the problem - sampling for a value of t over a curve between 0 and 1 does not necessarily give you an even spatial distance over the curve, which is a natural consequence of the way the curve formula works.

I've been researching some other alternatives. Catmull Rom is supposed to give a constant speed but requires some really weird control points that would be counter-intuitive in the editor. Trigonometric splines are of interest, but again I can't quite work out how well that's going to work in terms of UI.

Bugger. Thought that quadratic splines would work - they provide the nicest concept from a UI point of view.

I have a ridiculous idea that I could have some kind of mapping between 0 and 1 onto a section of the curve that took into account the linear distance between the last point and the desired new point, binary chopping between different values of t until a point on the curve was found that satisfied a tolerance of the actual distance the point moved, but that's probably just mental. Hard to tell.

Blibble blibble. Is it actually that important to be able to sweep the camera in smooth curves around the level at the start? Probably not.

I have thought about this problem before too, and I always thought that if you could develop an integral that determines the length of the curve, then you could properly determine which part of the curve you wanted based on a [0,1] range of values. It would be non-trivial to figure out, but I think a closed form expression should exist for the integral - it just needs to be calculated.

With the integral in hand, you could then evaluate the integral over different ranges of the input parameter and see how long it was. This makes it simple to create a mapping between linear [0,1] range and a distance based [0,1] range that is distorted to the appropriate distance metric.

Its worth a shot if you don't find any other alternatives...

Quote:
 Original post by Jason Z Its worth a shot if you don't find any other alternatives...

Sorry? What is? Blibble [smile].

Unless it wasn't otherwise plain, I'm a fumbling idiot, not a maths guy.

The brain-dead approach is to evaluate stepping along the curve in "tiny" increments, where tiny is some arbitrarily derived amount. Evaluate a whole bunch of tiny steps and accumulate distances until the total distance is roughly equal (to within a margin of error) of the actual distance the entity can travel in the given timestep. It's not the most elegant solution, but it sure beats trying to integrate the thing numerically.

I fought with this a while ago - and was surprised to find that a proper analytical solution is actually impossible.

Here's the best solution I could find. Basically you'll animate over your curve's length, then use the below function to convert the length to a T value (0-1), and then use that to actually find the 2d point on the curve.

	/** Takes a position (length) along the curve and finds the corresponding time (t) value.
*  Position is always in the range of [0, curveLength]
*  Time is always in the range of [0, 1]
*/
public float getTimeFromPosition(float position)
{
assert (position >= 0-epsilon);
assert (position <= length()+epsilon);

if (position <= 0)
return 0.0f;

if (position >= length())
return 1.0f;

// Newton's method makes an initial guess and progressivly refines it

final int maxIterations = 128;
final float tolerance = 0.5f;

// Initial guess
float l = length();
float time = position / l;
float difference = 0f;

for (int i=0; i<maxIterations; i++)
{
difference = lengthTo(time) - position;

if (Math.abs(difference) < tolerance)
return time;

float s = speed(time);
time -= (difference / s);

// Clamp time to [0,1] range
time = Math.max(time, 0f);
time = Math.min(time, 1f);
}

// Newton's method failed to converge.
// If this happens, increase iterations, tolerance or integration accuracy.
//	assert (false) : "Failed to converge, closest position is "+difference+" out.";

// Return current best guess
return time;
}

Hopefully the code makes sense. It basically takes a guess (on the assumption that T is linear across the length) and refines it in several increments.

Almost forgot, you'll need this semi-voodoo code as well:

	/** Length of a subsection of the curve, from the start (t=0) to the tMax specified.
*/
private float lengthTo(float tMax)
{
assert (tMax >= 0f && tMax <= 1f);
}

/** Get the speed at any given point on the curve.
*  Caution: Requires a square root operation.
*/
public float speed(float t)
{
// Speed is the magnitude of the velocity vector at point t
Vector2f vel = velocity(t);

return (float)Math.sqrt(vel.x*vel.x + vel.y*vel.y);
}

/** Find the velocity at a given point on the curve
*/
public Vector2f velocity(float t)
{
return velocity(t, new Vector2f());
}

public Vector2f velocity(float t, Vector2f dest)
{
assert (t >= 0f && t <= 1f);
assert (dest != null);

// Calculate the first derivative of the curve, which is the velocity at that point

// Cubic equation is:
//		(1-t)^3*p  +  3t(1-t)^2*q  +  3t^2(1-t)*r  +  t^3*s

// Expanded is:
//		(-t^3 + 3t^2 - 3t + 1)p  +  (3t^3 - 6t^2 + 3t)q  +  (3t^2 - 3t^3)r  +  (t^3)s

// So First Derivative is:
//		(-3t^2 + 6t - 3)p  +  (9t^2 - 12t + 3)q  +  (6t - 9t^2)r  +  (3t^2)s

float t2	= t*t;

// Find weights
float w0 = -3*t2 + 6*t - 3;
float w1 = 9*t2 - 12*t + 3;
float w2 = 6*t - 9*t2;
float w3 = 3*t2;

float vx = startPoint.x*w0 + controlPoint1.x*w1 + controlPoint2.x*w2 + endPoint.x*w3;
float vy = startPoint.y*w0 + controlPoint1.y*w1 + controlPoint2.y*w2 + endPoint.y*w3;

dest.set(vx, vy);
return dest;
}

// Holy crap! Magical voodoo code!
// Performs some kind of numerical intergration, which we use here on the speed, giving us the length
// of the curve
private float gaussianQuadrature(float fA, float fB)
{
// Legendre polynomials
// P_0(x) = 1
// P_1(x) = x
// P_2(x) = (3x^2-1)/2
// P_3(x) = x(5x^2-3)/2
// P_4(x) = (35x^4-30x^2+3)/8
// P_5(x) = x(63x^4-70x^2+15)/8

// Generation of polynomials
//   d/dx[ (1-x^2) dP_n(x)/dx ] + n(n+1) P_n(x) = 0
//   P_n(x) = sum_{k=0}^{floor(n/2)} c_k x^{n-2k}
//     c_k = (-1)^k (2n-2k)! / [ 2^n k! (n-k)! (n-2k)! ]
//   P_n(x) = ((-1)^n/(2^n n!)) d^n/dx^n[ (1-x^2)^n ]
//   (n+1)P_{n+1}(x) = (2n+1) x P_n(x) - n P_{n-1}(x)
//   (1-x^2) dP_n(x)/dx = -n x P_n(x) + n P_{n-1}(x)

// Roots of the Legendre polynomial of specified degree
final int iDegree = 5;
final float s_afRoot[] =
{
-0.9061798459f,
-0.5384693101f,
0.0f,
+0.5384693101f,
+0.9061798459f
};
final float s_afCoeff[] =
{
0.2369268850f,
0.4786286705f,
0.5688888889f,
0.4786286705f,
0.2369268850f
};

// Need to transform domain [a,b] to [-1,1].
// If a <= x <= b and -1 <= t <= 1, then x = ((b-a)*t+(b+a))/2.
float fRadius = 0.5f * (fB - fA);
float fCenter = 0.5f * (fB + fA);

float fResult = 0.0f;
for (int i=0; i<iDegree; i++)
{
fResult += s_afCoeff[i] * speed(fRadius * s_afRoot[i] + fCenter);
}

return fResult;
}

public float length()
{
}



Quote:
 Original post by JTippetts The brain-dead approach is to evaluate stepping along the curve in "tiny" increments, where tiny is some arbitrarily derived amount. Evaluate a whole bunch of tiny steps and accumulate distances until the total distance is roughly equal (to within a margin of error) of the actual distance the entity can travel in the given timestep. It's not the most elegant solution, but it sure beats trying to integrate the thing numerically.

That's kind of what I was thinking when I woke up this morning. I guess that if you make the size of the small increment a function of the length of the subsection of the curve, that could work reasonably well.

Thanks.

Quote:
 Original post by OrangyTang Here's the best solution I could find. Basically you'll animate over your curve's length, then use the below function to convert the length to a T value (0-1), and then use that to actually find the 2d point on the curve...

I appreciate the effort in posting all that but it looks like it is based on cubic splines rather than quadratic. I'm going to experiment with JTippet's approach before I try to get my head round yours.

// Generation of polynomials
//   d/dx[ (1-x^2) dP_n(x)/dx ] + n(n+1) P_n(x) = 0
//   P_n(x) = sum_{k=0}^{floor(n/2)} c_k x^{n-2k}
//     c_k = (-1)^k (2n-2k)! / [ 2^n k! (n-k)! (n-2k)! ]
//   P_n(x) = ((-1)^n/(2^n n!)) d^n/dx^n[ (1-x^2)^n ]
//   (n+1)P_{n+1}(x) = (2n+1) x P_n(x) - n P_{n-1}(x)
//   (1-x^2) dP_n(x)/dx = -n x P_n(x) + n P_{n-1}(x)


That looks like one of the failed attempts by an infinite number of monkeys to type the complete works of Shakespeare to me. [smile]

How smooth do you really need it to be? Surely you could just convert the curve to a series of line segments and move along that? You could sample in a simple fashion to begin with, then go through and find pairs of line segments with too great an angle between them and subdivide if it is necessary for the desired quality.

Once you have your "smooth enough" line strip it's very straightforward to move along it at constant speed, and if you like you can determine your speed based on the length of the whole strip.

It seems to me you could create a "sampling function" for t that approximates equal distance. The dependent variables would be the dot products of the control points for the B?zier/Hermite spline, I'd think. Just a guess, though, haven't been able to find a simple approximation dealing specifically with cubic Bez splines online. If you do, please share :) Bnd perhaps you'd prefer it to be as exact as possible anyway. Yeah, otherwise Casteljau, or Euler with segment arc-length threshold (and correction), I'd say. What an annoying problem :)