Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a game that requires each player to move along one specified path. I draw the path using Bézier curves. How can I determine the total real (not linear) length of the path and the distance that each player had made? (The distance between the start point and a specified point on the path.)

UPDATE:

The path is represented in a Cartesian plane (2D).

share|improve this question
    
Your question is answered near the bottom of this answer –  BlueRaja - Danny Pflughoeft Oct 2 '11 at 11:04
add comment

5 Answers

up vote 7 down vote accepted

As the previous answers said, computing the length of a Bezier curve it's hard (impossible?). I would say that 100% of the games use an approximation of the length, which is pretty much always accurate enough.

A few month ago I implemented it using the proposed approach of breaking the curve into "small" segments and adding their length. There's an example of a C++ implementation here.

share|improve this answer
add comment

Measuring the length of a Bezier curve is hard. If you don't mind a slight inaccuracy, a simple solution would be to approximate the Bezier curves with straight lines and calculate the sum of the line lengths. The more segments you create, the better the approximation.

share|improve this answer
    
I might consider that, but how can I determine how many segments should I have and how can I map the segments to have their start point and end point on my path? Does this technique has a name? (so I search it up on Google) –  Valentin Radu Oct 1 '11 at 9:52
    
A simple approach would be to just use a linear distribution of points from B(0) to B(1)... much like something you would use to actually plot the curve. Look at the source code in Dan's answer. –  bummzack Oct 1 '11 at 12:37
    
I'd appreciate an explanation of the down-vote, just to know what I could improve in my answer... –  bummzack Oct 1 '11 at 12:39
add comment

Higher order (i.e. greater than 1st order) spline length parameterization has to be approximated; it cannot be represented directly, hence the fact that it's not easy to find direct solutions to this.

Some extant implementations (copy-paste code):

Using Chebyshev approximations, according to the authors, accuracy grows as curve size increases. Look at pp. 7-8 pseudocode, the rest is a description of other algorithms on which they based their approach which you can ignore. A number of references online refer to this method as a good one.

See also these concise approaches.

share|improve this answer
add comment

This started out as a comment on the comment on @bummzack's answer, but grew too long.

how can I determine how many segments should I have

There are two approaches. The first is just the standard algorithm for rendering a Bézier curve: the control points form a bounding box of the curve, so if all of the control points are within epsilon of the line segment from start point to end point you approximate as a line; otherwise you subdivide using de Casteljau's algorithm. Epsilon is chosen according to the error you wish in the final result. (For rendering it's usually 0.5 pixels).

The other approach is a refinement of that using interval arithmetic. Take the length of the line from start to end as the lower bound, and the sum of the lengths of the lines through the control points as the upper bound. Again, subdivide as required by your final error requirements.

One normally subdivides at t=0.5, but de Casteljau's algorithm allows splitting at any point, so if you have a cubic Bézier with control points C_0 to C_3 and C_2 is much nearer the line segment between the endpoints than C_1 you might find that splitting at one of 1/3 or 2/3 gives tighter bounds. I haven't worked through the algebra to justify which would be better, but you can experiment and report back if you want. If nothing else, I wanted to point out that the option is there.

share|improve this answer
add comment

Calculating the length of a parametrized curve can be done by taking the integral of sqrt((dx/dt)² + (dy/dt)²), where dx/dt is the derivative of the x-component of the curve, and dy/dt is the derivative of the y-component of the curve. In the case of a Bézier-spline, these two are the same, as the equation can be extended to any dimension.

The formula for a cubic Bézier-spline is the following one: B(t) = (1 - t³) * P0 + 3(1 - t)²t * P1 + 3(1 - t)t² * P2 + t³ P3 where P0 through P3 are the control points.

According to Wolfram|Alpha, the derivative of this formula is: d(B(t))/dt = 3(t(t(P3 - P0) + P2(2 - 3t) + P1(3t² - 4t + 1))

Now you can put this back into the equation for the length of a curve, and calculate the integral from t = 0 to t = 1. Unfortunately, Wolfram|Alpha times out when I try to do this. You can do numerical integration, however.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.