On 5/27/06, Justin Wikinator <touchmewithsynchronicpulses@...400...> wrote:

I'm guessing instead of plotting a huge amount of points I can just do a rougher plot and then increase the resolution in the area before the target to optimize.

I've been thinking about ways to improve accuracy since yesterday, and I have some better math for you. :)

Dividing the curve into line segments and finding their lengths will always give you an answer that is too low, since line segments will always take a short-cut around any curved portions. It would be more efficient to use the Calculus definition, since it takes curvature into account:

Integral( sqrt( dx/dt ^ 2 + dy/dt ^ 2 ), t )

If you have a point traveling along your spline, the dx/dt and dy/dt functions tell you the point's x and y velocity with respect to t. The formula for dx/dt is:

dx/dt = x0 * (-3*(1-t)^2) + x1 * (+3*(1-t)^2 - 6*(1-t)*t) + x2 * (-3*t^2 + 6*(1-t)*t) x3 * (+3*t^2)

Here, x0 and x3 are the endpoints, and x1 and x2 are the control points. The formula for dy/dt is the same. Combining these two functions using the Pythagorean theorem gives the absolute speed of a point traveling along the spline:

s(t) = sqrt( dx/dt ^ 2 + dy/dt ^ 2 )

In other words, the definition of arc length is just speed integrated by time, giving distance traveled. Since an integration just divides a function into infinitely small chunks and adds them up, it can be approximated with a sum:

double s = 0; //Result double dt = 0.01; //Step size for (double t = 0; t < 1; t += dt) { s += s(t) * dt; }

Using an infinitely small dt would give you exact integration, but computers can't do that. :) Using something called Simpson's rule, however, can improve the results dramatically with almost no extra work:

int n = 100; //Steps; must be even double t0 = 0; //Start value for t double t1 = 1; //End value for t double dt = (t1 - t0) / n; //Step size double s = s(t0) + s(t1); //Result for (int i = 1; i < n; i += 2) { s += 4*s(t0 + i*dt) + 2*s(t0 + i*dt + dt); } s *= dt/3;

You can Google Simpson's rule for more info on the algorithm, but the accuracy improvements are substantial. Plus, this algorithm is actually faster than summing lengths of line segments.

-William Swanson