Subject: The Fastest Circle Algorithm...

Author: James Frith


I've been working to improve upon Bresenham's circle algorithm, and I've come
up with a new algorithm that requires no multiplies or look-up tables, and it
draws the fastest circle I've ever seen.  Here it is in C...  
I also have a 486 optimized assembly version that is 5 times faster...  Just
email me I'll send it to you.

// FCircle.c - Draws a circle using Frith's algorithm.
// Copyright (c) 1996  James E. Frith - All Rights Reserved.
// Email:

typedef unsigned char   uchar;
typedef unsigned int    uint;

extern void SetPixel(uint x, uint y, uchar color);

// FCircle --------------------------------------------
// Draws a circle using Frith's Algorithm.

void FCircle(int x, int y, int radius, uchar color)
  int balance, xoff, yoff;

  xoff = 0;
  yoff = radius;
  balance = -radius;

  do {
    SetPixel(x+xoff, y+yoff, color);
    SetPixel(x-xoff, y+yoff, color);
    SetPixel(x-xoff, y-yoff, color);
    SetPixel(x+xoff, y-yoff, color);
    SetPixel(x+yoff, y+xoff, color);
    SetPixel(x-yoff, y+xoff, color);
    SetPixel(x-yoff, y-xoff, color);
    SetPixel(x+yoff, y-xoff, color);

    if ((balance += xoff++ + xoff) >= 0)
      balance -= --yoff + yoff;

  } while (xoff <= yoff);
} // FCircle //

Subject: Re: The Fastest Circle Algorithm...

Author: James Frith


Ok, I admit it...  there's an ambiguity in the statement:
  if ((balance += xoff++ + xoff) >= 0)
While I believe it *should* compile correctly if your compiler obeys operator
precedence rules (Borland and Watcom do), the fact is that one odd ball
doesn't (Microsoft C).  The problem is that xoff is changed *while* the
expression is being evaluated...  not before or after.
So, here's the fix:
  balance += xoff++;
  if ((balance += xoff) >= 0)
    balance -= --yoff * 2;


(2D Ellipse Technique Examined)