5 ms·
The Beauty of Bresenham's Algorithm
- zackangelo 14y agoI first learned of Brensenham's line drawing algorithm from Michael Abrash in his Graphics Programming Black Book. I've yet to come across a more thorough and easy to understand discussion: http://downloads.gamedev.net/pdf/gpbb/gpbb35.pdf http://downloads.gamedev.net/pdf/gpbb/gpbb35.pdf
- patrickmclaren 14y agoHere'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."
- CamperBob2 14y agoBresenham'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?
- justinsb 14y agoI 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.
- deleted 14y ago[deleted]
- mkl 14y agoIt'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.
- barbs 14y agoWhy do people write non-conditional loops as "for(;;)" instead of "while(1)"?
- ephemient 14y agoSo that you can do tricks like this: #define ever (;;) for ever {...} ;-)
- nitrogen 14y agoBecause while(1) still has a condition that is checked on every loop iteration when optimizations are disabled. for(;;) can be read as "forever".
- morsch 14y agoFWIW, GCC and Perl generate the same code for both. http://stackoverflow.com/questions/885908/while-1-vs-for-is-there-a-speed-difference http://stackoverflow.com/questions/885908/while-1-vs-for-is-...
- barbs 14y agoInteresting. Looks like they'd be the same performance wise, since for (;;); is the same as { while (true) { ; ; } } I originally asked this question cos it's used this way in first C program in the link. Bit of a tangent though :P
- FredBrach 14y agoI do doubt that even for a for(;;), a jmp (x86) is use instead of a conditional jump like jz.
- FredBrach 14y agoBy 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 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 < ω
- 6ren 14y agoWouldn't the exception be for lines whose slope is irrational? (i.e. that can't be represented by a ratio of integers), so the repeating pattern is analogous to the repeating pattern in a decimal representation of a rational number.
- pvarangot 14y agoAbout a week ago I came to know Bresenham's Algorithm is also important in mobile robotics. Basically, you model your map using a grid, after firing a sensor such as a LIDAR or sonar and finding something blocks its cone of sight you use Bresenham's to see what cells in your map the new reading provides information about. (i.e. something bouncing 2 meters from where your robot is not only tells you about a block at 2 meters but also about no block in that trajectory, all those cells you now suppose are free and the one you suppose is not are the result of Bressenham's Algorithm)
- maximz 14y agoCould you please elaborate on how this works or point to some resources on this application of the algorithm (if you know of any)?
- Schwolop 14y agoEssentially it's ray-tracing but in a grid. Bresenham's algorithm let's you do the ray-tracing efficiently. This is done because a LIDAR/sonar/whatever scanning range sensor returns the angle and range to a reflective object. In most cases, there's an implicit additional piece of information - namely that there's nothing in between the sensor and the object, since the EM radiation was able to get there and back. Bresenham's algorithm is used to tell you the grid cells in which you can assume free space.
- mjcohenw 14y agoAre you sure about the Bezier curve algorithm? It has "xx *= xx;" and xx is never reset (unless I misunderstand the code).
- wollw 14y agoI 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 https://gist.github.com/3291916
- dag11 14y agoTo save you guys the time of running the code yourself, here's the output in codepad.org: http://codepad.org/y7fIoHlm http://codepad.org/y7fIoHlm
- Uchikoma 14y agoThis enabled and was core to many demos from the demo scene of the 80s (c64, Amiga).
- spitfire 14y agoI remember implementing this in ask! Fun times. it's very funny how this sort of stuff comes back at opportune times to magically solve really hard problems for you with a single pass. Sort of like having Knuth on your bookshelf.
- greggman 14y agoBresenham'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.
- comatose_kid 14y agoI remember coding this up in ARM7 assembler (Gameboy Advance) a while back. Clever algorithm.