Moving at a constant speed along a Bézier Curve

Game Mechanics
#1

I’ve been playing with quadratic bezier curves recently, its easy enough to draw and get the points along it using something like:

float x = (1 - t) * (1 - t) * startX + 2 * (1 - t) * t * cx + t * t * endX;
float y = (1 - t) * (1 - t) * startY + 2 * (1 - t) * t * cy + t * t * endY;

Where start/end is the beginning/end point on the curve and c being the control point.

t is a value between 0 and 1 which can be used to move along the curve, 0 being the start and 1 being the end, however the problem is that this value can’t be used to move along the curve at a constant speed since t=0.5 is not necessarily at the middle of the curve or t=0.25 the first quarter.

I’ve got an approximation of the length of the curve using

public float getApproxLength() {
		float t = 0;
		length = 0; // reset length
		
		float oldX = startX;
		float oldY = startY;
		
		// scroll through curve and update length
		for (int i = 0; i < 100; i++) {
			t += 0.01f;
			
			float x = (1 - t) * (1 - t) * startX + 2 * (1 - t) * t * cx1 + t * t * endX;
			float y = (1 - t) * (1 - t) * startY + 2 * (1 - t) * t * cy1 + t * t * endY;
			
			length += getLineLength(x, y, oldX, oldY);
			
			oldX = x;
			oldY = y;
		}
		
		return length;
	}

Are there any easy solutions to achieve this other than to use a whole ton of look up tables and memory? doesn’t need to be super accurate just something good enough to get a decent constant looking movement along the curve.

#2

You used my code, about 6 years ago, which used a whole ton of lookup tables and memory. There are no shortcuts, as far as I know.

#3

Interesting problem!

This may be computationally too intensive, but perhaps use some sort of binary search algorithm to test the distance travelled for a given fraction of t? In other words, measure the distance for a given t-fraction. If too large (or too small) vary and try again to hit the target distance within a given tolerance.

There may be optimizations to help this algorithm, like only using the squares not the square roots in the distance calculation (which will make overshooting a bit less accurate than undershooting [do I have that backwards?], but maybe still good enough), and starting the search with the previous t-fraction or a t-fraction with the increment or decrement previously successful.

[EDIT: maybe I didn’t fully grasp the question. I was looking at it via having a set distance you wish to travel per frame, and thus was not worried about the problem of computing the total distance of the curve.]

[EDIT2: Roquen’s article looks like a bullseye. But I had another thought that maybe is worthless, but here goes: convert the bezier curve into a GeneralPath for transversal purposes?]

#4
#5

Yup remember that super awesome spline class well (still have it in my workspace), used it many times and would probably use it again here if I could, however limited to working with quadratic bezier curves directly in this case.

Cool, that looks like pretty much what I need, some pretty dense math representation of the formula’s there though, will see if I can write some code from it.

#6

What’s the use case of these curves? Presumably simply:

[quote]move along the curve at a constant speed
[/quote]
Especially when travelling along the curve (not requiring random access) it seems that making something stateful, that remembers its last t and distance, is ‘good enough’ (as in: fast and accurate)


traveller = new CurveTraveller(curve);
Vec2 pos = traveller.advance(1.2);

There would be no lookup tables involed.

#7

I have done this accurately enough and fairly fast with just short 3rd order Gaussian quadrature integration, and doing a stepwise pre integration when the curve is created for a “global scale”. Its plenty accurate enough for games. I use Hermite splines.

There is no short cut, there are proofs of this out there that there is no simple formula.

#8

just curious, why Hermite curves over Bézier curves? Noticed a lot of people using them, is there some extra advantage in using them?

#9

This. Very much this. I’d go so far as to say if you’re thinking about a problem and “spline?” pops in your head then the next thought is hopefully “cubic hermite?”

Dead simple to design on-the-fly. Cubic is end-points and end-point tangents (or direction & speed…not saying velocity because of parameterization). The down side of cubic hermite is that they are only first order continuous. Not a big deal in most situations. The basis of cubic hermite is what Perlin’s original ease function was and the quintic for improved noise.

#10

On line 224 of this procedural map generator I wrote, there is the math for a carefully incremented Bezier if you’d like to check it out.

http://pastebin.com/1Jb6dHTk

It draws beziers paths across a grid, which was kinda hard to figure out for me.
Here is the approximate end result: