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.

How can I find the distance traveled by a Bezier curve?

For example, the distance traveled by a Linear Bezier Curve is:

distance = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));

But what about Quadratic, Cubic or really Nth-Degree Bezier Curves?

I want to estimate a sampling resolution beforehand, so I don't have to waste time checking if the next point is touching the previous point.

share|improve this question
1  
You should reword the question to refer to the length of the curve, that is a much more straightforward (and searchable) term. –  Sparr Nov 28 '10 at 11:34
    
i suggest posting this on math, i'm sure some clever face over there will give you the answer in one of them clever web fonts :p –  Tor Valamo Nov 28 '10 at 17:27
1  
@Tor I did (yesterday), but I've been told it's very complicated, and hence unpractical. [ math.stackexchange.com/q/12186/2736 ] –  muntoo Nov 28 '10 at 21:08
    
Supposedly clothoid curves/splines are an alternative to beziers, and have closed-form arclength expressions, but I don't know much about this yet. (Trying to generate equal-distance points along a curve.) Catenaries also have closed-form arc length expressions? –  endolith Feb 21 at 16:43

2 Answers 2

up vote 6 down vote accepted

A simple way for cubic Beziers is to split the curve into N segments and sum the segments' lengths.

However, as soon as you need the length of only part of the curve (e.g. up to a point 30% of the length along), arc-length parameterization will come into play. I posted a fairly long answer on one of my own questions about Béziers, with simple sample code.

share|improve this answer
    
I'm doing this for the LEGO Mindstorms NXT, which has a really weak processor (48Mhz), so I need as much speed as possible. I'll take the dividing approach to conserve some speed, and get it accurate enough (for "non-realtime" rendering). I also have a option in which you can set the value of 1.0/t (called resolution), so that's for "realtime" (which is at best 10fps on the slow NXT). Every iteration, t += resolution, and a new point/line is drawn. Anyways, thanks for the idea. –  muntoo Nov 29 '10 at 0:58

While I am d'accord with the answers you got already, I want to add a simple but powerful approximation mechanism which you can use for any degree Bézier curves: You continually subdivide the curve using de Casteljau subdivision until the maximum distance of the control points of a sub-curve to the sub-curve's baseline is below some constant epsilon. In that case the sub-curve can be approximated by its baseline.

In fact, I believe this is the approach usually taken when a graphics subsystem has to draw a Bézier curve. But do not quote me on this, I do not have references at hand at the moment.

In practice it will look like this: (except the language is irrelevant)

public static Line[] toLineStrip(BezierCurve bezierCurve, double epsilon) {
    ArrayList<Line> lines = new ArrayList<Line>();

    Stack<BezierCurve> parts = new Stack<BezierCurve>();
    parts.push(bezierCurve);

    while (!parts.isEmpty()) {
        BezierCurve curve = parts.pop();
        if (distanceToBaseline(curve) < epsilon) {
            lines.add(new Line(curve.get(0), curve.get(1)));
        } else {
            parts.addAll(curve.split(0.5));
        }
    }

    return lines.toArray(new Line[0]);
}
share|improve this answer

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.