When drawing an ellipse or circle with OpenGL, how many vertices should we use?

Question

Should we just blindly use 360 vertices? 720 seems to work better, but where do we stop?

Answer 1

It depends on how much error you can tolerate (i.e. the visual quality) and the size of the circle (ellipse). A bigger circle will need more points to achieve the same quality. You can work out exactly how many points you need for a given error with a bit of maths.

If you consider the circle represented by a series of line segments, the end points of the line segments lie exactly on the circle (ignoring the pixel grid). The biggest deviation between the real circle and our line segment representation occurs in the center of each line segment, and this error is the same for all of the line segments.

Looking at the first segment from the x-axis going anti-clockwise, its two endpoints are:

A = (r, 0)
B = (r . cos(th), r . sin(th))

where r is the radius of the circle and th is the angle covered by each line segment (e.g. if we have 720 points then each line segment covers 0.5 degree so th would be 0.5 degrees).

The midpoint of this line segment is at

M = A + (B - A) / 2
  = (r, 0) + (r (cos(th) - 1) / 2, r . sin(th) / 2)
  = (r / 2) . (1 + cos(th), sin(th))

and the distance from the origin to the point is

l = (r / 2) . sqrt((1 + cos(th))^2 + (sin(th))^2)
  = (r / 2) . sqrt(2) . sqrt(1 + cos(th))

If our line segment representation were perfect then this length should be equal to the radius (the midpoint of the line segment should fall on the circle). Normally there'll be some error and this point will be slightly less than the radius. The error is

e = r - l
  = r . (1 - sqrt(2) . sqrt(1 + cos(th)) / 2)

Rearranging so we have th in terms of e and r

2 . e / r = 2 - sqrt(2) . sqrt(1 + cos(th))
sqrt(2) . sqrt(1 + cos(th)) = 2 . (1 - e / r)
1 + cos(th) = 2 . (1 - e / r)^2

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

This lets us calculate the maximum angle we can have between each point to achieve a certain error. For example, say we're drawing a circle with a radius of 100 pixels and we want a maximum error of 0.5 pixels. We can calculate

th = arccos(2 . (1 - 0.5 / 100)^2 - 1))
   = 11.46 degrees

This corresponds to ceil(360 / 11.46) = 32 points. So if we draw a circle of radius 100 using 32 points our worst pixel will be off by less than a half which should mean every pixel we draw will be in the correct place (ignoring aliasing).

This kind of analysis can be performed for ellipses too, but in the spirit of all good maths that is left as an exercise for the reader ;) (the only difference is determining where the maximum error occurs).

Answer 2

as many as the resolution you are using requires, or as many as the visual result requires an accurate representation. It's difficult to say, and mostly depends on what you want to achieve. In a CAD program, having a circle visually similar to an octagon could be annoying. On the other hand, if you are programming a game on the iphone, if the wheel of a car looks like an octagon it's not a big deal.

A possible strategy you could use is to evaluate the length of each segment with respect to the resolution of the current view, and if longer than, say, 3 pixels, increase the number of vertexes you use, but only for the visible segments. This way, you increase the resolution when zooming in, but you don't have to describe vertexes you are not going to draw.