How to seamlessly sub-divide a circle at any scale

Update I’ve migrated this blog to blog.bearcats.nl. You can find an updated version of this post here.

GPUs render graphics strictly in triangles. A box or a square can be perfectly re-created using 2 triangles, and so can many other shapes with jagged edges. Circles on the other hand can be a little bit more problematic.

Triangles are jagged by nature, so there’s no way to perfectly build a circle out triangles. But we can approximate. What we normally do, is we divide the circle into $N$ equal sections, and then approximate each section with a triangle.

We usually just choose a fixed value for $N$ ahead of time, and as long as we choose a high enough value, the seams won’t be noticeable. This is very simple, and usually it’s effective. However, if we zoom in on a circle made like this then the seams can become noticeable.

Figure 1 A circle approximated using 16 triangles rasterized at different scales. From left to right we have 46, 64, 114, and 190 pixel wide circles.

How do we fix this? Well, we could just choose a larger $N$. This will allow us to zoom further in on the circle, but then we’ve just pushed the problem further back. Not only that, but we would also be wasting resources drawing a highly-detailed circle even the user is zoomed-out.

If your application or game supports arbitrary zooming and you don’t want your user’s to see the jaggies, or if you don’t want to waste resources rendering high-detail circles that are barely visible, then you shouldn’t sub-divide your circles into a fixed number of triangles.

Using a little bit of trigonometry, we can calculate a value of $N$ that sub-divides the circles such that the seams aren’t noticeable within some known error. What we really want to do is sub-divide the circle until the curve-to-chord distance is small.

Figure 2 A diagram of a triangle used to approximate a circle with radius $r$. The curve-to-chord distance is highlighted in red.

As you can see from the diagram, the curve-to-chord distance can be calculated as $r - d$. In turn, $d$ can be calculated simply as $r \cos\theta$.

Let’s call our acceptable curve-to-chord distance $\epsilon$. Now we set $\epsilon = r - r \cos\theta$, and we can use the fact that $\theta = 2\pi / N$ to calculate the number of subdivisions we need to get $\epsilon$. This turns out to be:

Here’s some OpenGL code that calculates $N$ like this, and then renders the circle using a triangle fan.

/* x, y    position of the *center* of the circle
 * error   an acceptable curve-to-chord distance, must be > 0 
 * SCALE   the current zoom-level of your program's view
 *          > 1 means zoomed-in
 *          < 1 means zoomed-out 
 * all parameters should be in the same units (pixels, em, ..) 
 */ 
void drawCircle(double x, double y, double radius, double error) {
    double theta = 2 * acos(1 - error / (SCALE * radius));
    int segments = (int)fmax(ceil(2 * pi / theta), 3);

    glBegin(GL_TRIANGLE_FAN);
    glVertex2d(x, y);
    for (int i = 0; i <= segments; ++i) {
        double segx = x + radius * cos(2 * pi * i / segments);
        double segy = y + radius * sin(2 * pi * i / segments);
        glVertex2d(segx, segy);
    }
    glEnd();
}

I actually used a very similar technique to draw the Q-learning agents when I made the Escape Room. Later I saw that the same techique was described in Graphics Gems V but I haven’t seen it posted anywhere online.

Anyway, using this technique you can render seamless looking circles at any zoom level, as long as you set the error as low as you can according to your memory and performance budget. You can try out how it works for yourself on the canvas below.

Try it out

SCROLL to change the error, SHIFT+SCROLL to zoom, CLICK-DRAG the view, SPACE reset view.