Hacker News Reader

Comment by kazinator | Hacker News Reader

TL; DR: > If you think a 64-bit DIV instruction is a good way to divide by two, then no wonder the compiler's asm output beat your hand-written code.

Once (maybe 25 years ago?) I came across a book on assembly language programming for the Macintosh.

The authors wrote a circle-filling graphic routine which internally calculated the integer square root in assembly language, drawing the circle using the y = sqrt(r * r - x * x) formula!

What is more, the accompanying description of the function in book featured sentences that were boasting about how it draws a big circle in a small amount of time (like a "only" quarter of a second or some eternity of that order) because of the blazing speed of assembly language!

How could the authors not have used, say, MacPaint, and not be aware that circles and ellipses can be drawn instantaneously on the same hardware: fast enough for drag-and-drop interactive resizing?

View on HN

Bresenham's line algorithms and the adaptation of the general principle to circles and arcs are absolute gems. I've used those over and over in the first two decades of my career and I never ceased to be impressed with the elegance and speed.

Surprising that people writing a book 25 years ago would not have been aware of this work.

https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

https://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Yes, it's absolutely brilliant. The line drawing algorithm is also applicable to other problems, whenever you need to interpolate between two integer values.

It's so useful I embedded it in a library module called 'dda' (for digital differential analyzer), and then used that module in all kinds of applications. It's one of those Swiss army knife subroutines, you end up using it in places not even remotely related to rendering bitmaps.

https://en.wikipedia.org/wiki/Digital_differential_analyzer_...

I have two-D and three-D versions of it.

Bresenham is applicable to other conic sections and functions.

I proved this back as an undergrad: i used Bresenham to plot the y = K/x hyperbolic curve.

I had this idea that since 1/x can be interpolated with Bresenham without doing division, somehow that could be applicable to the perspective transformation when walking over texture maps in 3D rendering.

Hehe. That's so cool, this is something I did without knowing any of the formal math behind it when writing a small 3D game engine (after seeing Doom). It seemed to be the shortest path to a solution and it worked very well.

Then, after getting it to work I replaced the interpolator with a bunch of assembly starting from the intermediary representation the compiler output.

I unfortunately didn't date that source file but I do remember I was living in Amstelveen when I wrote it so this was about 23 years ago, summer of '94.

We made the textures with one of the first affordable and commercially available digital cameras:

http://www.digicamhistory.com/1991.html

Back in the 90s there was a series of books "Graphics Gems" that was a great resource in learning these tricks. Most people are further removed from drawing directly into a frame buffer today,

https://www.amazon.com/Graphics-Gems-Andrew-S-Glassner/dp/01...

Relevant: https://www.folklore.org/StoryView.py?story=Round_Rects_Are_...

How are rounded corners on rects harder than circles and ovals?

Is a rounded rect not just a circle sliced with straight lines between the quarter circles?

I get the feeling that what you mention is the precise realisation that Atkinson had when he figured out a way to draw them quickly. It's quite possible that he was initially thinking of ways to describe rounded rects using a single equation. Even one as undeniably brilliant as Atkinson can get stuck in thinking and overcomplicate things. A good night's sleep can bring a fresh perspective and make simplicity much more apparent.

I think he came to this realization while looking at all the examples jobs was showing him, which is why he suddenly agreed to give it a try.

I needed to create a circle drawing algorithm for some purposes a long ways back. I was in middle school at the time.

While speed wasn't a huge issue, consistency was. Simply using sin/cos to draw the circle works, but it can lead to jagged and inconsistently placed pixels if your degree step isn't perfect. Even with my middle school level math, I realized I could just iterate over the bounding box for the circle and just use r^2 as a threshold on x^2+y^2 to determine whether a pixel should be on or off - no square root required, since it's totally redundant.

It has the bonuses of using only integer math (consistency!) and only requires slight changes to yield filled or unfilled circles. It's also almost as fast as drawing a simple filled rectangle!

The idea that the author could miss such a simple algorithm baffles me.

> iterate over the bounding box for the circle and just use r^2 as a threshold on x^2+y^2 to determine whether a pixel should be on or off -

Jeff Tupper's GrafEq software does this kind of plotting.

Over the development of this, Jeff Tupper came up with a quine concept: a formula whose f(x,y) thresholded plot reproduces an image that can be interpreted as its math notation.

See here:

https://en.wikipedia.org/wiki/Tupper%27s_self-referential_fo...

The Devil is in that 543 digit integer. :)

(It's been submitted to HN a few times already.)

Reply on news.ycombinator.com