Drawing circles in the 8-bit world

Someone reminded me that 40 years ago, when we developed games for the Commodore-64, there were no GPUs. That 8-bit CPUs did not even have a machine instruction for multiplication. And they were dreadfully slow.

Therefore, it was essential to use fast and efficient algorithms for graphics primitives.

One such primitive is Bresenham’s algorithm although back then, I didn’t know it had a name beyond being called a forward differences algorithm. It’s a wonderful, powerful example of an algorithm that produces a circle relying only on integer addition and bitwise shifts; never mind floating point, it doesn’t even need multiplication!

Here’s a C-language implementation for an R=20 circle (implemented in this case as a character map just for demonstration purposes):

#include <stdio.h>
#include <string.h>

#define R 20

void main(void)
{
    int x, y, d, dA, dB;
    int i;
    char B[2*R+1][2*R+2];

    memset(B, ' ', sizeof(B));
    for (i = 0; i < 2*R+1; i++) B[i][2*R+1] = 0;

    x = 0;
    y = R;
    d = 5 - (R<<2);
    dA = 12;
    dB = 20 - (R<<3);
    while (x<=y)
    {
        B[R+x][R+y] = B[R+x][R-y] = B[R-x][R+y] = B[R-x][R-y] =
        B[R+y][R+x] = B[R+y][R-x] = B[R-y][R+x] = B[R-y][R-x] = 'X';
        if (d<0)
        {
            d += dA;
            dB += 8;
        }
        else
        {
            y--;
            d += dB;
            dB += 16;
        }
        x++;
        dA += 8;
    }

    for (i = 0; i < 2*R+1; i++) printf("%s\n", B[i]);
}

And the output it produces:

                XXXXXXXXX                
             XXX         XXX             
           XX               XX           
         XX                   XX         
        X                       X        
       X                         X       
      X                           X      
     X                             X     
    X                               X    
   X                                 X   
   X                                 X   
  X                                   X  
  X                                   X  
 X                                     X 
 X                                     X 
 X                                     X 
X                                       X
X                                       X
X                                       X
X                                       X
X                                       X
X                                       X
X                                       X
X                                       X
X                                       X
 X                                     X 
 X                                     X 
 X                                     X 
  X                                   X  
  X                                   X  
   X                                 X   
   X                                 X   
    X                               X    
     X                             X     
      X                           X      
       X                         X       
        X                       X        
         XX                   XX         
           XX               XX           
             XXX         XXX             
                XXXXXXXXX                

Don’t tell me it’s not beautiful. And even in machine language, it’s just a few dozen instructions.