7 ms·
Bresenham's Circle Drawing Algorithm (2021)
- KingOfCoders 2y agoWhat I found most amazing about Bresenham during my Amiga days, is how you can use it to zoom and shrink bitmaps.
- corysama 2y agoDo note that Bresenham’s family of algorithms (and much of the venerable Computer Graphics Principles and Practice) are from a bygone era where computers executed 1 instruction per cycle without pipelining or prediction. These days processors prefer to draw shapes by having a coarse grained pass that conservatively selects tiles of interest then brute-force evaluates each pixel in each tile independently of all others. Instead of minimizing total work, the goal is to maximize pipelined parallelism while skipping over unnecessary work in large blocks.
- eru 2y agoIt's also from an era when floats were rather expensive.
- mabster 2y agoI still picture them as expensive. Things like trig functions are still very expensive.
- eru 2y agoYes, but here it's about avoiding multiplication (and division). I suspect on a modern processor the branches (ie "if"s) in Bresenham's algorithm are gonna be more expensive than the multiplications and divisions in the naive algorithm.
- ack_complete 2y agoBresenham is easy to implement branchlessly using conditional moves or arithmetic. It also produces a regular pattern of branches that is favorable for modern branch predictors that can do pattern prediction.
- dahart 2y agoI learned relatively recently that trig functions on the GPU are free if you don’t use too many of them; there’s a separate hardware pipe so they can execute in parallel with floats adds and muls. There’s still extra latency, but it’ll hide if there’s enough other stuff in the vicinity.
- sischoel 2y agoThe CUDA documenation tells me that there are more performant but less precise trigonometric functions: https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#intrinsic-functions https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.... Do you know if that hardware pipeline works only for these intrinsic variants?
- dahart 2y agoYep, these intrinsics are what I was referring to, and yes the software versions won’t use the hardware trig unit, they’ll be written using an approximating spline and/or Newton’s method, I would assume, probably mostly using adds and multiplies. Note the loss of precision with these fast-math intrinsics isn’t very much, it’s usually like 1 or 2 bits at most.
- mabster 2y agoI couldn't find much information on those. I assume that they don't include range reduction?
- dahart 2y agoI’m not totally sure but I think fast math usually comes with loss of support for denormals, which is a bit of range reduction. Note that even if they had denormals, the absolute error listed in the chart is much bigger than the biggest denorm. So you don’t lose range out at the large ends, but you might for very small numbers. Shouldn’t be a problem for sin/cos since the result is never large, but maybe it could be an issue for other ops.
- deleted 2y ago[deleted]
- mysterydip 2y ago"yes, but" there's still places that can take advantage of such algorithms today, namely microcontrollers. I think some scripting languages may even apply here, although many interpreters do some level of compilation/optimization instead of serial execution.
- Someone 2y ago> a bygone era where computers executed 1 instruction per cycle without pipelining or prediction 1 instruction per cycle? What luxury bygone era did you grow up in? Wikipedia tells me the algorithm is from 1962 on an IBM 1401 (https://en.wikipedia.org/wiki/Bresenham's_line_algorithm#History) https://en.wikipedia.org/wiki/Bresenham's_line_algorithm#His... That definitely didn’t have many single cycle instructions. Skimming https://ibm-1401.info/A24-6447-0_1401_1460_Instruction_and_Timing_Summary.pdf https://ibm-1401.info/A24-6447-0_1401_1460_Instruction_and_T..., I couldn’t find any. Certainly, in the era of 8-bit CPUs like Z80 and 6502 programmers would have been lyric about “1 instruction per cycle” Actually, did any CPU ever “execute 1 instruction per cycle without pipelining or prediction” (or, slightly looser “had fixed time instructions without pipelining or prediction”)? RISC introduced fixed time instructions, but also pipelining.
- owisd 2y agoProbably meant 'cycle' in the sense of instruction cycle, rather than clock cycle.
- Someone 2y agoEven then, few CPUs execute all instructions in the same amount of time. Division, for example, still takes longer than a register move on most architectures. Multiplication, historically, did too. As a sibling comment points out, DSPs can be an exception. I’m far from an expert on them, but CPUs that try to run all instructions in the same fixed amount of time used to accomplish that by avoiding complex addressing modes and by omitting the really slow instructions (division and instructions that push/pop multiple registers onto/from the stack being prime examples). IIRC, some of them also accomplished it by running some of the simpler instructions slower than necessary (raw speed isn’t as important as being hard real time isn many applications)
- kragen 2y ago> few CPUs execute all instructions in the same amount of time. Division, for example, still takes longer than a register move on most architectures easy solution, as you allude to, don't have a division instruction! arm doesn't, 8048 doesn't, sparcv7 doesn't, even the cdc 6600 and cray-1 didn't, and even risc-v finally got zmmul: https://wiki.riscv.org/display/HOME/Zmmul https://wiki.riscv.org/display/HOME/Zmmul. it's not just dsps the big issue with complex addressing modes is i think fault handling. if your nice orthogonal add instruction updates two registers as it reads operands and a third register with the sum of the operands, what do you do if you get a page fault on the second operand? if the os can service the page fault, how does it restart the instruction? as you point out, real-time latency is also an issue. on older arm chips you have to be careful not to ldm or stm too many registers in a single instruction so as not to damage interrupt latency. newer arm chips can restart the ldm/stm i'm no expert on the area either
- _0ffh 2y agoNah, while cycles/instruction where indeed fixed in those days (and for some time yet to come), it was not necessarily 1 cycle but rather depended on the instruction.
- tengwar2 2y agoIndeed. I used this algorithm on OS/2 1.0 as part of a GUI (OS/2 did not have a GUI until 1.1). That was on an 80386. MASM came with a nice ring-bound A6 book which summarised the instruction set, including timings. I seem to remember that 3 cycles was normal for a short instruction, but many were considerably longer.
- amelius 2y agoSounds like your algorithm is from a bygone era where power was not important ;)
- corysama 2y agoIf you can get the work done fast and hurry the processor back into a low-power sleep state ASAP, it can actually be power efficient too!
- phire 2y ago1 instruction per cycle? No, that's only possible with pipelining. We are talking about instructions which took 8-12 cycles to complete.
- kragen 2y agousually this is correct, but there are some exceptions. most instructions on a non-pipelined but synchronous stack machine like the mup21 take a single cycle, for example even with a register file, it isn't really inherent that you need to decode inputs, do alu operations, and write outputs in separate clock cycles; you can do all of that in combinational logic except writing the outputs, and you can even decode which register to write the output to. it just means your max clock rate is in the toilet for that kind of thing a harvard architecture is pretty useful; it allows you to read an instruction in instruction memory at the same time you're reading or writing data in data memory, instead of in two separate cycles
- chiph 2y agoI think it depends. I had Dr. Bresenham as my graphics instructor (he taught for a while after he retired from IBM) and the class used Borland Turbo Pascal and for it's time it was fast. Not as fast as raw assembly. But faster than Borlands Turbo C that had just come out. So far as 1 instruction per cycle - Wikipedia says the 80286 (the top dog PC processor of the time) could execute 0.21 "typical" instructions per clock. Optimized code was up to 0.5 instructions per clock. And that agrees with my memories. Today, I would try and use parallelism if I could. With lots of conditions though - is the process being applied to the image trivially parallelizable, will most/all of it fit in cache, etc. Trying to parallelize Bresenham's algorithms though would be futile - when drawing circles you can reflect it into the different quadrants (big savings) but the algorithm itself is going to be pretty serial because it has to keep up with the error coefficient as it draws.
- ack_complete 2y agoIt's actually not difficult to vectorize Bresenham algorithms, at least the line algorithm. You just have to preroll the algorithm for each of the lanes and then adjust the steps and error factors so each lane steps 4-8 pixels ahead at a time interleaved. I've done this for the floor type 1 render in Ogg Vorbis, which is defined in terms of a Bresenham-like algorithm.
- kragen 2y agooh wow, this is awesome, thanks! i never realized!
- brcmthrowaway 2y agoGot an exsmple?
- userbinator 2y agoIn particular, his line-drawing algorithm is easily beaten by fixed-point methods, which also have the advantage of a very short and non-branchy inner loop: https://news.ycombinator.com/item?id=9954975 https://news.ycombinator.com/item?id=9954975
- bsenftner 2y agoMy computer graphics professor back in the early 80's was Prof. Glen Bresenham, but not The Bresenham. It was a lot of fun being at SIGGRAPH back then and watching people freak upon reading his name badge. He'd let them believe for a bit, and then explain it's not him. Al Acorn was one that freaked, and that was fun.
- stefantalpalaru 2y ago[dead]
- possiblywrong 2y ago> Note that if F(x,y)=0, then the point (x,y) is exactly on the circle. If F(x,y)>0, then the point is outside of the circle, and if F(x,y)<0 then the point is inside of it. In other words, given any point (x,y), F(x,y) is the distance from the true circle line [my emphasis]. This last is not quite true. The exact distance from the circle, call it G(x,y), is the corresponding difference of square roots, i.e., def G(x, y, r): return math.sqrt(x * x + y * y) - math.sqrt(r * r) and G(x,y) isn't just the square root of F(x,y), and indeed doesn't behave monotonically with respect to F(x,y). It's an interest property of Bresenham's algorithm, that I've never seen even stated let alone proved in the literature, that this doesn't matter, and the algorithm is indeed exact in the sense that it always chooses the next point based on which is truly closest to the circle... despite using an error function that is only an approximation.
- ericyd 2y agoA cool write up with an approachable explanation of algorithm optimization! I wonder how long it would take me to arrive at this algorithm left to my own devices...
- nikolay 2y agoThis is easy; anti-aliasing is thougher. I used this algorithm in the '90s to come up with one for drawing ellipses. I've never had to do a disc or filled ellipse with or without outloune, but that would be interesting, too. Line size > 1 would be interesting as well.
- seanhunter 2y agoFeels like simply using the parametric form of the circle equation would be way easier For t in 0 to 2 pi in whatever small steps you want, draw_pixel(x=a+rcos t, y=b+rsin t) where a and b are the x and y coordinates you want for the centre of the circle and r is the radius. The derivation of this form is pretty simple if you know basic trig. https://publish.obsidian.md/uncarved/3+Resources/Public/Unit+Circle+Definitions+of+Trigonometric+Functions https://publish.obsidian.md/uncarved/3+Resources/Public/Unit...