How do I evenly subdivide the projection of a circle in 3D?

Question

I want to draw a circle in 3D from line segments. There are plenty of examples how to do this with an even number of subdivisions in 3D space, but I want the minimum number of subdivisions to produce a smooth circle after projection, without under- or over-subdividing. So a small circle (after projection) should require few subdivisions, a large circle should require more.

I could just calculate a fixed subdivision based on camera field-of-view and screen resolution, but that will only be correct for circles directly facing the camera.

Before I dig into the maths to figure this out I want to ask if there is already a well-known solution to this, because searches didn't come up with anything useful so far.

I have the feeling this is either solvable by stepping around the conic section projection of the circle in screen space, or by adjusting the step size based on the projection matrix.

Edit: I think subdivision methods are good solutions, especially for arbitrary curves. I was wondering if there is a closed solution exploiting symmetries of the circle. I'll need to have a think, but at least I doesn't look like I'm missing an existing solution.

Answer 1

What you are after is a curve flattening, i.e. turning a curve (an ellipse in your case) into a polyline, in such a way that the discretization is not visible.

This can be done by recursive subdivision: for a given arc of the curve, estimate the deviation from the line segment that joins the endpoints. If the deviation exceeds a visual threshold (a fraction of a pixel), split the arc in two subarcs and recurse.

A gross estimate of the deviation is obtained by just taking the distance of some intermediate point of the arc to the segment. This is inaccurate when the deviation is large, but quite sufficient for small deviations.

The method is suboptimal but easy and effective. It will not only adjust the point density for small vs. large circles, but also finely adjust as a function of local curvature. Needless to say, the flattening is completely viewpoint-dependent.

Also note that you needn't compute the equation of the ellipse.

---

A uniform subdivision is not such a good idea, because under grazing incidence, the curvature can become high and the angular step would need to be very small.

Answer 2

When doing it inside shader stages, one possibility is the following using vertex- and tessellation-shader (only one triangle (3 lines) are needed):

Within the vertex shader you can calculate the NDC by the following code:

vec4 NDC = mvp_matrix * vertexPosition;
NDC = NDC / NDC.a;

The NDC coordinate need to be handled over to the tessellation-control shader. There you can check, how far are the two connected vertices away from each other. Only test the x/y coordinates, because we want to know the distance of the pixels.

vec2 len = abs(NDC[0].xy - NDC[1].xy);

Finally, the screen resolution must be taken into account:

float numberOfDivisions = length(len * 0.5 * screenResolution); // the multiplication by 0.5 is required, because NDC range in x/y dimension is [-1, 1].

Pro:

1. No vertex buffer object is needed... you can execute the shader for a minimum of three lines.
2. No uploading of vertex data. So except the draw command there is no CPU->GPU communication.

Contra:

1. In case the circle lies partly outside the view frustum or partly behind the camera, the output will be not like expected. So you need to do some clipping before.
2. when having high screen resolution, the input of only 3 lines (1 triangle) can be not enough, because the maximum subdivision of the tessellation stage can be too poor.