Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Beauty of Bresenham's Algorithm

free.pages.at

Post reply on HN
Print view View original

41–50 of 50 posts

Re: The Beauty of Bresenham's Algorithm

#41

Post by mkl »

justinsb wrote: post #4
CamperBob2 wrote: post #3

Bresenham's Algorithm is a useful argument when someone suggests that software patents are a good thing. How far back would the progress of computer graphics have been set if Bresenham or his employer had claimed ownership of this idea?

I think you do Bresenham a great disservice, by underestimating how far ahead of its time this really was. This was published in 1962, so any patent would have expired in 1982. So any patent would probably have had almost no effect, because it would have expired before the market advanced to the point where it was generally applicable.

It's useful for a lot more than just graphics. E.g. linear interpolation with CPUs that are integer-only (most of them at the time) and have small registers (most again) so fixed point is of limited usefulness. That has a huge number of applications.

Re: The Beauty of Bresenham's Algorithm

#42

Post by zanny »

sp332 wrote: post #14
pslam wrote: post #13

Earlier quoted context omitted.

Why do people write while(1) instead of for(;;)? Are you saying that "while(1)" is superior in some way? Why? I prefer "for(;;)" because it is explicitly defined as an infinite loop, but "while(1)" needs an implicit cast of "1" to "true", and even then there's an implicit test for "true".

You could just say while(true). And I'm not sure that the test for true is implicit, since that is what while() explicitly does.

C doesn't have true / false as language constants, only as override-able macros.

The good thing is modern compilers can evaluate a loop and if the break condition is constant it can just do an infinite loop without checking.

Re: The Beauty of Bresenham's Algorithm

#43

Post by sclangdon »

barbs wrote: post #5

Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?

Because while(1) evaluates to a constant, which can sometimes be a bug and thus, some compilers emit a warning.

http://msdn.microsoft.com/en-us/library/6t66728h%28v=vs.80%2...

http://stackoverflow.com/questions/3490823/why-msvc-generate...

Re: The Beauty of Bresenham's Algorithm

#44

Post by tsahyt »

pslam wrote: post #13
barbs wrote: post #5

Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?

Why do people write while(1) instead of for(;;)? Are you saying that "while(1)" is superior in some way? Why? I prefer "for(;;)" because it is explicitly defined as an infinite loop, but "while(1)" needs an implicit cast of "1" to "true", and even then there's an implicit test for "true".

There's no casting involved in while(1). 1 is "true" in C, in fact, any integer != 0 is "true".

I just did a quick check and gcc -S produces the same ASM output for both of them, which doesn't include any comparisons whatsoever, just a jmp. So both of them are really compiled to an actual infinite loop.

Re: The Beauty of Bresenham's Algorithm

#45

Post by dag11 »

wollw wrote: post #25

I doubt anyone here really needs it but here's a C program that demonstrates all three functions in a terminal. Just making a global array and a macro for setPixel is enough to play with these and is really pretty much all I did. https://gist.github.com/3291916

To save you guys the time of running the code yourself, here's the output in codepad.org:

http://codepad.org/y7fIoHlm

Re: The Beauty of Bresenham's Algorithm

#46

Post by ralph »

FredBrach wrote: post #33
mjcohenw wrote: post #23

Earlier quoted context omitted.

The algorithm only works with points with integer coordinates, so the slope is always rational.

I think you have the last words because line drawing algorithms become irrelevant if you use a Floating Point Unit. just: { x++ and y+=slope } or { y++ and x+= 1./slope } Then slopes are always rational in line drawing algorithms.

If y and slope are floating point in the first block then might not y end at other than the desired endpoint because of accumulative error?

Re: The Beauty of Bresenham's Algorithm

#47

Post by greggman »

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 ? 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.

Re: The Beauty of Bresenham's Algorithm

#48

Post by Someone »

nitrogen wrote: post #7
barbs wrote: post #5

Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?

Because while(1) still has a condition that is checked on every loop iteration when optimizations are disabled. for(;;) can be read as "forever".

for(;;), being equivalent to for(;1;), also has that condition that has to be checked. So, it all boils down to how compilers treat the two.

And to add oil to the fire, here are some even 'better' ways to do this:

  do {
    ...
  } while(1);
At least that fits the common macro pattern "do{...}while(0)" (http://stackoverflow.com/questions/257418/do-while-0-what-is...).

Of course, all of these are inferior to:

  considered:
    ...
  goto considered;

Re: The Beauty of Bresenham's Algorithm

#49

Post by tsahyt »

FredBrach wrote: post #11
nitrogen wrote: post #7

Earlier quoted context omitted.

Because while(1) still has a condition that is checked on every loop iteration when optimizations are disabled. for(;;) can be read as "forever".

I do doubt that even for a for(;;), a jmp (x86) is use instead of a conditional jump like jz.

It is, you can easily check that yourself. for(;;) compiles to exactly one jmp in GCC (tested with gcc 4.7.0)
Post reply on HN