The Beauty of Bresenham's Algorithm
free.pages.at
The Beauty of Bresenham's Algorithm
1–10 of 50 posts
Re: The Beauty of Bresenham's Algorithm
#2Here's the abstract to Bresenham's Algorithm from Wikipedia, if anyone wants to know a little more about it, generally:
"The Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics. A minor extension to the original algorithm also deals with drawing circles."
Re: The Beauty of Bresenham's Algorithm
#3Bresenham'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?
Re: The Beauty of Bresenham's Algorithm
#4Bresenham'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.
Re: The Beauty of Bresenham's Algorithm
#5Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?
Re: The Beauty of Bresenham's Algorithm
#6Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?
So that you can do tricks like this:
#define ever (;;)
for ever {...}
Re: The Beauty of Bresenham's Algorithm
#7Why 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".
Re: The Beauty of Bresenham's Algorithm
#8By the way, I had a teacher (J.P Reveilès) who had invented the theoretically fastest drawline algorithm ever: he simply figure out that, for a line, there is a pixel pattern which repeat itself (unless the variation is a transcendental number http://en.wikipedia.org/wiki/Transcendental_number) so you only have to compute that pattern once and copy/paste it. If I remember well, for example, a line which has a variation of 1/4, has a 4-pixel wide pattern only!
His discrete line equation is relatively beautiful (it is easily extractible from Bresenham's algorithm however): 0 ≤ ax − by < ω
Re: The Beauty of Bresenham's Algorithm
#9Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?
Not applicable to the original article, but the reason I do it is because Go has no while loop. It doesn't require all those extra semis, though:
for {
...
}Re: The Beauty of Bresenham's Algorithm
#10Why 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".
FWIW, GCC and Perl generate the same code for both.
http://stackoverflow.com/questions/885908/while-1-vs-for-is-...