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

11–20 of 48 posts

Re: Bresenham's Circle Drawing Algorithm (2021)

#11

Post by tengwar2 »

_0ffh wrote: post #7
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…

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

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

Re: Bresenham's Circle Drawing Algorithm (2021)

#12

Post by mabster »

eru wrote: post #4
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…

It's also from an era when floats were rather expensive.

I still picture them as expensive. Things like trig functions are still very expensive.

Re: Bresenham's Circle Drawing Algorithm (2021)

#13

Post by eru »

mabster wrote: post #12
eru wrote: post #4

Earlier quoted context omitted.

It's also from an era when floats were rather expensive.

I still picture them as expensive. Things like trig functions are still very expensive.

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

Re: Bresenham's Circle Drawing Algorithm (2021)

#14

Post by owisd »

Someone wrote: post #6
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…

> 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#His... That definitely didn’t have many single cycle instructions. Skimming https://ibm-1401.info/A24-6447-0_1401_1460_Instruction_and_…

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

Re: Bresenham's Circle Drawing Algorithm (2021)

#16

Post by dahart »

mabster wrote: post #12
eru wrote: post #4

Earlier quoted context omitted.

It's also from an era when floats were rather expensive.

I still picture them as expensive. Things like trig functions are still very expensive.

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

Re: Bresenham's Circle Drawing Algorithm (2021)

#17

Post by phire »

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.

Re: Bresenham's Circle Drawing Algorithm (2021)

#18

Post by chillingeffect »

Someone wrote: post #6
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…

> 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#His... That definitely didn’t have many single cycle instructions. Skimming https://ibm-1401.info/A24-6447-0_1401_1460_Instruction_and_…

Adsp-218x family of harvard architecture DSPs. Each 25 ns clock cycle = 1 MAC, 1 data fetch, and one instruction fetch. All instructions 1 cycle long. And many other gizmos like reversible address bit ranges for DFT in place, separate register bank for IRQ handlers. And all laid out by hand.

Re: Bresenham's Circle Drawing Algorithm (2021)

#19

Post by sischoel »

dahart wrote: post #16
mabster wrote: post #12

Earlier quoted context omitted.

I still picture them as expensive. Things like trig functions are still very expensive.

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

The CUDA documenation tells me that there are more performant but less precise trigonometric functions: https://docs.nvidia.com/cuda/cuda-c-programming-guide/index....

Do you know if that hardware pipeline works only for these intrinsic variants?

Re: Bresenham's Circle Drawing Algorithm (2021)

#20

Post by chiph »

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

Post reply on HN