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

	/** 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;
	}

	/** 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);
		return gaussianQuadrature(0f, tMax);
	}

	/** 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);
		}
		
		fResult *= fRadius;
		return fResult;
	}

	public float length()
	{
		return gaussianQuadrature(0f, 1f);
	}

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.

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

// 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)