How to render a circle with as few vertices as pos

Question

I'm trying to figure out how to decide how many vertices I need to have to make my circle look as smooth as possible.

Here is an example of two circles, both having 24 vertices:

As you see, the bigger the circle becomes, the more vertices I need to hide the straight lines.

At first I thought that the minimum length of one line on the edge should be 6px, but that approach failed when I increased the circle size: I got way too many vertices. I also thought about calculating the angles, but I quickly realised that angles doesn't differ on different sized circles. I also checked this answer, but I don't have a clue how to convert it into code (and some weird stuff there: th uses itself for calculating itself), and I think it doesn't even work, since the author is using the angle from one slice to the middle of circle, which doesn't change if the circle gets larger.

Then I realised that maybe the solution is to check the angle between two vertices at the edges, in this way:

As you see, the fewer vertices, the bigger the lengths are for those triangles. So this has to be the answer, I just don't know how to calculate the number of vertices by using this information.

Answer 1

First of all, if you are using OpenGL or DirectX you can significantly decrease the number of vertices by using a triangle fan structure.

As for the problem of the amount of vertices, I would imagine the number of vertices required for a smooth circle to scale with the circumference. This scales with r, so I would advice to find a good factor A such that:

#vertices = A * r

Answer 2

The answer you link to actually implements exactly the idea you propose at the end of your question.

The decisive formula that you need from that answer is this one:

th = arccos(2 * (1 - e / r)^2 - 1)

This tells you the angle between two vertices, where r is the radius of the circle and e is the maximum error you're willing to tolerate, i.e. the maximum deviation of your polygon from the circle -- this is the error marked in your diagram. For example, you might choose to set e to 0.5 of a pixel.

Because th is measured in radians, and 360 degrees (a full circle) is equal to 2*pi in radians, the number of vertices you need is

num_vertices = ceil(2*pi/th)

Answer 3

The angles are the same in the two cases of 24 vertices.

But with larger circle, the human eye is able to better see the individual straight lines.

So you need some heuristic that takes into account

• the angle between two consecutive line segments in the curve, and

• the size, and possibly

• the scaling for display.

The third point is difficult since one does not in general know the size at which some graphic will be displayed. E.g., an SVG format picture can be displayed at any size. The most general solution, I think, is to have direct support for various figures (Bezier lines, circles, etc.) in the renderer, and then define the figure with a few parameters instead of as a sequence of points. Or, define it in terms of some figure that the renderer supports, e.g. as a sequence of connected Bezier curves. That way, the renderer can add the necessary number of points to make it look smooth and nice.

However, I guess that you're not creating a renderer, so then perhaps only the first two points above are relevant.