CODEWITHSUNDEEP
c++calgorithmfloating-pointinteger
Ariel Yael
Ariel Yael

Reputation: 373

C/CPP - Converting floating point arithmetic to integer arithmetic

I have the following c++ functions (implementing Bresenham's line algorithm), seen in the book

Computer Graphics From Pixels to Programmable Graphics Hardware By Alexey Boreskov, Evgeniy Shikin

One of the function uses floats, and due to their inefficiency the book has presented another function which uses integer arithmetic only.

I'm having trouble understading why are the two equivalent, and why are we using left shift << here, doesn't a<<1 simply multiply a by 2?

Note: We assume the points A:(xa,ya) and B:(xb,yb) have integer values.

Float Version

void drawLine(int xa, int ya, int xb, int yb, int color) {
    float k = (float)(yb-ya)/(float)(xb-xa);
    float d = 2*k - 1
    int y = ya;

    putPixel(xa, ya, color); // paint the pixel (xa,ya) in color "color"

    for (int x = xa+1; x<=xb; x++) {
        if (d > 0) {
            d += 2*k + 2;
            y++;
        } else {
            d += 2*k;
        }
        putPixel(x, y, color);
    }
}

Integer Version

void drawLine(int xa, int ya, int xb, int yb, int color) {
    int dx = xb - xa;
    int dy = yb -ya;
    int d = (dy<<1) - dx;
    int d1 = dy <<1;
    int d2 = (dy - dx) << 1;
    int y = ya;

    putPixel(xa, ya, color); // paint the pixel (xa,ya) in color "color"

    for (int x = xa+1; x<=xb; x++) {
        if (d > 0) {
            d += d2;
            y++;
        } else {
            d += d1;
        }
        putPixel(x, y, color);
    }
}

Upvotes: 2

Views: 183

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 222923

The floating-point code does four things with d:

  1. Initialize d to 2dy/dx−1, where dy and dx are yb−ya and xb−xa, respectively.
  2. Evaluate whether d is greater than 0.
  3. Add 2dy/dx+2 to d.
  4. Add 2dy/dx to d.

In floating-point, the division by dx may produce a non-integer. To avoid this, we transform the operations by multiplying everything by dx, yielding:

  1. Initialize d to 2dy−dx.
  2. Evaluate whether d is greater than 0dx (equal to 0).
  3. Add 2dy+2dx to d.
  4. Add 2dy to d.

We can readily see that these four equivalent operations are implemented in the integer code except for 3. The integer code appears to add 2dy−2dx to d. The integer code matches code shown in the Wikipedia page for Bresenham’s line algorithm. I suspect the + in the floating-point version is an error in the book.

Upvotes: 5

Related Questions