Hacker News Reader

Comment by christkv | Hacker News Reader

You can always try Bresenham’s circle drawing algorithm.

Back in the '80s in Bulgaria, I was only able to find the Bresenham's algorithm for circles, but needed to draw an ellipse (in 6052 assembly, well, machine code), and was so proud that I manage to do it.

Did it work for any axes?

As far as I can recall, yeah. By the way, I found this [0] implementation in pseudo code.

[0]: https://dai.fmph.uniba.sk/upload/0/01/Ellipse.pdf

The lessons you learn on your own stick the best, don't they?

I remember a similar "heureka" moment when I derived a line-drawing algorithm that respected "subpixel" starting and ending points. That is, don't assume a line starts/ends in the middle of a pixel (like most algos do), but rather at an arbitrary point.

I forgot why I needed this (something to do with near-axis-aligned polygon slopes not looking right on a highly rasterized problem). But I do remember the elation when I finally got it to work :-) Also early 1990s, no internet and no English for extra fun.

This is the era where prior art doesn't exist. Why read a book when you can blog about discovering "something new". I could probably make a killing blogging about my "discovery" of the algorithms in the book "Hacker's Delight".

The author titled one of the sections "Midpoint circle algorithm".

There happens to be a Wikipedia page on "Midpoint circle algorithm": https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

The page claims, "Bresenham's circle algorithm is derived from the midpoint circle algorithm."

The author of this blog post even made it clear, at the end of their article, that... "many explanations of midpoint algorithm use the final, optimized version. But I added several unoptimized steps."

I think there's a lot of value in a blogpost that demonstrates how someone could re-derive a widely-used algorithm from scratch.

This always blows my mind - for the first time in human history we live in a world where almost all prior art is relatively easily discoverable, and people don't even bother.

I guess I shouldn't be surprised, after all, I've met a lot of people.

The sheer weight of information can make it harder to find. Also, nobody gets paid for being the prior art.

Finding the prior art pays you back the time you’d have spent repeating the same mistakes, though.

Beat me to it. And there are several optimizations on top that by, more or less, by reflecting the points as you compute one quadrant of the circle.

that was my first reaction on reading the title..that's how retro computers back in the day displayed circles on sparse pixel displays

And pen based vector plotters.

I loved pen based plotters it was mesmerising to watch them draw.

Indeed, but oh those pens were so expensive and woe to you if a pen ever punctured the paper. That could get messy in a hurry. And then of course the printerbuffer would have another 250K worth of plotter commands and good luck getting that to stop.

Reply on news.ycombinator.com