Secrets of the Grey Beards: drawing circles with additions and shifts

A long time ago, before GPUs, before multicore processors and gigabytes of RAM, clever algorithms were the only way to render complex graphics in real-time. Those algorithms are now mostly forgotten as nobody needs them or is interested in them. Nobody? Well, almost. I like to reverse-engineer the clever tricks programmers of that era were using (in fact, I was one of them), and I hope you'll follow me on this exploration.

In this post, I'm going to show you algorithms that solve the seemingly simple task of drawing a circle, and we'll do so with very strong constraints on the operations we're allowed to use. In the early days of video games, the late 70s and early 80s, the processors in home computers and game consoles were mostly 8-bit processors such as the 6502 and the Z80. Those processors were not only slow by today's standards with frequencies around 1-2MHz and no parallel execution of any kind, they had very limited instruction sets, without multiplication and division operations, and with only support for integer numbers. That doesn't mean that multiplications were impossible, but just that they were very, very expensive. As a consequence, algorithms avoiding them were preferable.

Operations that 8-bit processors were very good at running fast, because they can be implemented with few simple logic gates, include additions and bit shifting.

The way mathematicians would describe circles is often with equations such as $x^2+y^2=r^2$ or $\{\begin{array}{l}x=r\cos \theta \\ y=r\sin \theta \end{array}$.

Both of those involve multiplications, or worse, trigonometric function evaluation. So what are we to do?

The first thing we can notice is that the first equation is quadratic, so everything in there, once differentiated, becomes linear, and as such, easy to compute using additions and multiplications by constants. Let's keep that differentiation idea but it's the second system of equations that I'm going to differentiate, to come up with the first algorithm:

$\{\begin{array}{l}dx=-r\sin \theta d\theta \\ dy=r\cos \theta d\theta \end{array}$

We can then notice that we can spot the expressions for $y$ and $x$ in those differential equations and reformulate them as follows.

$\{\begin{array}{l}dx=-yd\theta \\ dy=xd\theta \end{array}$

What that tells us is that when the angle $\theta$ changes by an infinitesimally small amount $d\theta$, $x$ changes by $-yd\theta$ and $y$ changes by $xd\theta$. This still contains a multiplication, but only by the constant amount we want to vary the angle between two steps of the rendering. If we choose that amount to be the inverse of a power of two so that the corresponding change in coordinate is always under one pixel, thus ensuring continuity, we can avoid the multiplication because multiplication by the inverse of a power of two is the same as shifting bits to the right by a number of bits that is that power: x/2^n is the same as x >> n.

We still have the problem of determining the value of $n$, but we only have to do it once per circle, so this is less of a hot path. It turns out, all you have to do is shift 1 left (which is the same as enumerating powers of two) until you run over $r$:

And this is it, we now have a working algorithm:

The call to drawPointAndSymmetries is just using the axial symmetries of a circle to only compute one eights of the circle:

If you're wondering about bdp, this is the fixed point bit depth that we use to make decimal calculations using only integers. It's 8 in the sample below, meaning eight bits of precision under the decimal point.

This works fine, but we can do better and faster.

Imagine we wanted to walk the circle in the dark. If we could erect a wall around the circle, we could just walk straight ahead and whenever we hit the wall, take a lateral step away from it. This strategy produces a trajectory that is very close to the circle. It also works on any concave shape, not just circles.

The wall in question is called a discriminating function. It's a function of the coordinates that evaluates as positive outside of the shape and as negative inside. It's called discriminating because by just evaluating it on a point, you can discriminate whether you are inside or outside.

For a circle, it's easy to build a discriminating function from the circle's equation: $f\left(x,y\right)=x^2+y^2-r^2$.

It may seem like computing this function for every point is going to be challenging because of all those squarings. In this case again, variations of the function from pixel to pixel are going to be sufficient if we know the value at any point.

When we move one pixel to the right, here's how the function varies:

$f\left(x+1,y\right)-f\left(x,y\right)=2x+1$

This is of course very easy to compute: shift $x$ left and add one.

Whenever the new value of the discriminating function goes positive, we need to make a side step, for which it is also easy to compute the discriminating function variation:

$f\left(x,y-1\right)-f\left(x,y\right)=1-2y$

Subtract left-shifted $y$ from one.

You may also notice that this second algorithm has no need for fixed-point decimal numbers, it can work on regular integer coordinates, which further simplifies it and makes it more efficeint.

Here's the implementation:

You can see both of those algorithms in action below:

The source code can be found here: https://github.com/bleroy/3d-junkyard/tree/main/AddAndShift

But of course, this is javascript running on a modern computer, and I sold this as a way to draw a circle on vintage 8-bit computers. Does it work on old computers? Yes, of course it does. Here's the algorithm implemented and running on an Atari 8-bit computer in 6502 assembly (what you see below is an actual emulator in your browser, hosted by the excellent https://8bitworkshop.com; if you see the circle as a little oval, that's normal, vintage computers often have pixels that are not exactly square):

Here's the source code for this: