Midpoint Algorithm Fast Direction I've been exploring the Midpoint algorithm for drawing lines and curves, and I have a quick question: How should you determine the fast direction for a curve? I've seen that if the shape is simple, you can draw one section and repeat the rest, but what if the shape does not have this property?

Right now I'm just using the derivative(slope), so I wonder if this is correct or cheaty? :P
I have never done this so this is just my best guess. I think you are on the track with the slope but I'm going to expand it little with some calculus. If you parameterize your curve by some variable t:

x(t) = ...

y(t) = ...

Then you can compute dx/dt and dy/dt which is how much x or y changes as you change t. This runs into some problems on a general purpose curve though. For example dx/dt might be a function of t. This means that the rate of change of x itself is changing as you move along the curve. But then you can also find dx/dt^2 (rate of change of the rate of change) and so on. This method is known as forward differencing.

Then what you can do is have an x, y starting point and draw a pixel there. Then you add the first order difference (dx/dt, dy/dt) to x and y. Then you add the second order difference to the first order difference and so on.

Here is a link I found on forward differencing:
http://www.nptel.ac.in/courses/122104018/node103.html

I haven't read it but it looks promising.

--edit--

Here's an example that was derived in my computer graphics class:
Some of the algebra can be tricky so it may or may not be correct.

Q(t) = a*t^3 + b*t^2 + c*t + k
0 &lt; t &lt; 1
segment size d
num segments: 1/d

Q1(t) = Q(t + d) - Q(t)
= 3*a*d*t^2 + 3*a*t*d^2 + a*d^3 + 2*b + d + b*d^2 + c*d

Q2(t) = Q1(t + d) - Q1(t)
= b*a*t*d^2 + 6*a*d^3 + 2*b*d^2

Q3(t) = Q2(t + d) - Q2(t)
= b*a*d^3      &lt;==== no longer depends on t!


Iterate:

init variables:
Q  = Q(0)  = k
Q1 = Q1(0) = a*d^3 + b*d^2 + c*d
Q2 = Q2(0) = b*a*d^3 + 2*b*d
Q3 = Q3(0) = b*a*d^3

repeat 1/d times:
    drawLine(Q, Q + Q1)
    Q  += Q1
    Q1 += Q2
    Q2 += Q3


Q is just for one of the x or y variables. You could have a QX, QX1, ... and QY, QY1, ... and forward difference them both in the same loop. Then draw using (QX, QY) and (QX + QX1, QY + QY1). You could also extend this into as many dimensions as you like.