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

Bresenham's Circle Drawing Algorithm (2021)

funloop.org

Post reply on HN
Print view View original

31–40 of 48 posts

Re: Bresenham's Circle Drawing Algorithm (2021)

#31

Post by kragen »

Someone wrote: post #23
owisd wrote: post #14

Earlier quoted context omitted.

Probably meant 'cycle' in the sense of instruction cycle, rather than clock cycle.

Even 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 m…

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

Re: Bresenham's Circle Drawing Algorithm (2021)

#32

Post by kragen »

phire wrote: post #17
corysama wrote: post #3

Do 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 other…

1 instruction per cycle? No, that's only possible with pipelining. We are talking about instructions which took 8-12 cycles to complete.

usually 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

Re: Bresenham's Circle Drawing Algorithm (2021)

#33

Post by nikolay »

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

Re: Bresenham's Circle Drawing Algorithm (2021)

#34

Post by ack_complete »

chiph wrote: post #20
corysama wrote: post #3

Do 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 other…

I 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 c…

It'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.

Re: Bresenham's Circle Drawing Algorithm (2021)

#35

Post by userbinator »

corysama wrote: post #3

Do 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 other…

In 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

Re: Bresenham's Circle Drawing Algorithm (2021)

#36

Post by ack_complete »

kragen wrote: post #31
Someone wrote: post #23

Earlier quoted context omitted.

Even 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 m…

> 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 . it's not just dsps the big issue with compl…

> don't have a division instruction! arm doesn't, 8048 doesn't

Heh, that's an understatement. The 8048 doesn't even have a subtract instruction, much less divide.

Re: Bresenham's Circle Drawing Algorithm (2021)

#37

Post by kragen »

ack_complete wrote: post #36
kragen wrote: post #31

Earlier quoted context omitted.

> 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 . it's not just dsps the big issue with compl…

> don't have a division instruction! arm doesn't, 8048 doesn't Heh, that's an understatement. The 8048 doesn't even have a subtract instruction, much less divide.

cpl add cpl was good enough for my daddy and it's good enough for me

Re: Bresenham's Circle Drawing Algorithm (2021)

#38

Post by kragen »

ack_complete wrote: post #34
chiph wrote: post #20

Earlier quoted context omitted.

I 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 c…

It'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.

oh wow, this is awesome, thanks! i never realized!

Re: Bresenham's Circle Drawing Algorithm (2021)

#39

Post by kragen »

bsenftner wrote: post #9

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

alcorn?

Re: Bresenham's Circle Drawing Algorithm (2021)

#40

Post by seanhunter »

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

Post reply on HN