Calculate evenly distributed points along a curve

Question

I'm using this equation to calculate a series of points along a quadratic curve:

// Returns a point on a quadratic bezier curve with Robert Penner's optimization of the standard equation
result.x = sx + t * (2 * (1 - t) * (cx - sx) + t * (ex - sx));
result.y = sy + t * (2 * (1 - t) * (cy - sy) + t * (ey - sy));

Sadly the points are unevenly distributed, as you can see in the dashed-line rendering below. The points are denser in the middle of the curve, and are further spaced apart near the edges. How can I calculate a evenly distributed set of points along a quadratic bezier curve?

Please note that I'm using this for rendering a dashed line, so a slow solution in MATLAB or something will not do. I need a fast solution that will fit inside a renderer. This is not for research or a one-off calculation!

Edit: I'm not asking how to accomplish the above. The above is MY RENDERING! I already know how to estimate the length of a bezier, calculate the number of points, etc, etc. What I need is a better bezier point interpolation algorithm since the one I have calculates points unevenly distributed along the curve!

Edit: Code in any language will do! My game runs in JS but I can port anything.

Answer 1

I don't think there's a closed form for a point a certain fraction of the distance along a quadratic curve.

A solution that's often good enough for rendering is to traverse the curve at a fixed rate, keeping track of the distance traveled. When the distance to the current point becomes greater than the desired distance between points, use linear interpolation to choose a point between the previous and current points.

If you want the points to exactly fill the curve (that is, not have the last segment possibly be shorter than the rest), you first will have to find the length of the curve by traversing it a second time.

In code-like form (obviously not tested):

total_distance = 0

previous_point = start_point
t = 0
while t < 1
    t = t + STEP_SIZE
    current_point = bezier(t)
    total_distance = total_distance + length(current_point - previous_point)
    previous_point = current_point

ideal_distance = total_distance / NUM_POINTS

previous_distance = 0;
previous_point = start_point
t = STEP_SIZE
while t < 1
    current_point = bezier(t)
    current_distance = previous_distance + length(current_point - previous_point)

    if current_distance >= ideal_distance
        distance_interp = (ideal_distance - previous_distance) /
                          (current_distance - previous_distance)
        t_interp = t - STEP_SIZE + distance_interp * STEP_SIZE
        output_point(bezier(t_interp)
        current_distance = current_distance - ideal_distance

    previous_distance = current_distance
    previous_point = current_point
    t = t + STEP_SIZE

output_point(bezier(1))

I recommend starting with STEP_SIZE = 1 / NUM_POINTS. If the result isn't accurate enough, cut STEP_SIZE in half.

If you don't require the final segment to be the same length as the others, you can simply set ideal_distance to a length that you like, then run the second loop. In this case, STEP_SIZE should be set quite small to ensure that one iteration of the loop doesn't step past two of the desired points. Alternately, in the condition where current_distance >= ideal_distance you could check and output multiple points.