Bresenham Integer Equation (Not just the algorithm)

Question

I am looking for an equation for a basic version of the bresenham line algorithm that would allow me to calculate the position of the Y value if the X value is known.

The X is always positive and always larger then the Y. The loop just adds 1 to the X until the end is reached.

Here is my code:

int err = (Y << 1) - X;
for(i=0; i<=X; i++)
{
    if(err > 0)
    {
        step++;
        err = (err - (X << 1)) + (Y << 1);
    }
    else
    {
        err = err + (Y << 1);
    }
    printf("X=%d  Y=%d\n", i, step);
}

What I am looking for is a way to figure out what the value of step(Y axis) is at a specific X value with out running the algorithm and with only integer math.

The reason for this is that I have a system that I can pause, but only returns the current X value (Not the Y) and I need to figure out the Y value when this happens.

Dave

Answer 1

I'm assuming that step is initially 0. From your code, we can derive inductively the equation

step * (X << 1) + err - (i + 1) * (Y << 1) == (Y << 1) - X,

which applies at the time of the printf statement. Solve for step.

step == ((Y << 1) - X + (i + 1) * (Y << 1) - err) / (X << 1)

The division here is exact. Since X > Y, we know inductively that -err is between -(Y << 1) inclusive and (X << 1) - (Y << 1) exclusive, so we should add the maximum of that range and let floor division do its thing.

step == ((Y << 1) - X + (i + 1) * (Y << 1) + (X << 1) - (Y << 1) - 1) / (X << 1),

or, simplifying,

step == ((i + 1) * (Y << 1) + X - 1) / (X << 1).

We can get an equation for err as well.

((Y << 1) - X + (i + 1) * (Y << 1) - err) % (X << 1) == 0
err ==   ((Y << 1) - X + (i + 1) * (Y << 1) + (X << 1) - (Y << 1) - 1) % (X << 1)
       - (X << 1) + (Y << 1) + 1
err == ((i + 1) * (Y << 1) + X - 1) % (X << 1) - (X << 1) + (Y << 1) + 1