Bresenham Algorithms (Incremental Differentials)

Although you'll usually hear about this in a graphics course, the basic concept of using integer ratios to implement incremental step sequences approximating a continuous function comes up all the time in other guises.

To draw a line in K-dimensional space, basically you need to know two things:

1. In which dimension is the change (absolute value) greatest? Call this the dominant dimension.
2. What are the (signed) integer ratios of the other dimension motions to the motion in the dominant dimension?

The following little 2D demonstration code assumes that x is the dominant dimension:

inline int
abs(register int x)
{
        register int y = (x >> 31);
        return((x ^ y) - y);
}

void
setxy(register int x,
register int y)
{
        printf("%5d %5d\n", x, y);
}

int
main(int argc, char **argv)
{
        register int x0 = atoi(argv[1]);
        register int y0 = atoi(argv[2]);
        register int x1 = atoi(argv[3]);
        register int y1 = atoi(argv[4]);
        register dx = abs(x1 - x0);
        register dy = abs(y1 - y0);
        register int i0 = dy + dy;
        register int d = i0 - dx;
        register int i1 = d - dx;

        i0 ^= i1;
        if (x0 > x1) {
                do {
                        setxy(x1++, y1);
                        y1 += (1 - (y0 = (d >> 31)));
                        d += ((y0 & i0) ^ i1);
                } while (x0 > x1);
                setxy(x1, y1);
        } else {
                do {
                        setxy(x0++, y0);
                        y0 += (1 - (y1 = (d >> 31)));
                        d += ((y1 & i0) ^ i1);
                } while (x1 > x0);
                setxy(x0, y0);
        }

        exit(0);
}