HN2new | past | comments | ask | show | jobs | submitlogin

Bresenham's, at least as implemented there is not the most efficient algorithm.

There are 4 checks per loop in that version. The faster impl recognizes that in 1 direction or the other one coordinate will always increment or decrement by 1 while the other coordinate will or will not increment on each iteration.

That will remove 2 of the 4 checks. The loop just becomes N where N is max(abs(dx), abs(dy))

I don't know if that's still considered Bresenham's or not.

    int sign(int v) {
        return v > 0 ? 1 : ((v < 0) ? -1 : 0);
    }

    int abs(int x) {
        return x > 0 ? x : -x;
    }

    int max(int a, b) {
        return a > b ? a : b;
    }
    
    void drawLine(int x1, int y1, int x2, int y2) {
        int deltaX = x2 - x1;
        int deltaRow = abs(deltaX);
        int rowInc = sign(deltaX);
      
        int deltaY = y2 - y1;   
        int deltaCol = abs(deltaY);
        int colInc = sign(deltaY);
        
        int rowAccum = 0;
        int colAccum = 0;
        int rowCursor = x1;
        int colCursor = y1;
        
        int counter = max(deltaCol, deltaRow);
        int endPnt = counter;
        if (counter == deltaCol) {
            rowAccum = endPnt / 2;
            for (; counter > 0; --counter) {
                rowAccum += deltaRow;
                if (rowAccum >= endPnt) {
                    rowAccum -= endPnt;
                    rowCursor += rowInc;
                }
    
                colCursor += colInc;            
                setPixel(rowCursor, colCursor);
            }
            
        } else {
            colAccum = endPnt / 2;
            for (; counter > 0; --counter) {
                colAccum += deltaCol;
                if (colAccum > endPnt) {
                    colAccum -= endPnt;
                    colCursor += colInc;
                }
                rowCursor += rowInc;
                setPixel(rowCursor, colCursor);
            }
        }    
    }
This is an optimized version of an algorithm I found in the Atari 400/800 Technical Reference Manual page 218.


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: