Algorithm for drawing generalised circles

Question

A generalised circle is either a circle in the plane or a line. The general equation of one is:

$$A(x^2 + y^2) + Bx + Cy + D=0,$$

where $4AD - B^2 - C^2 \leq 0$. This can be checked by completing the square on $x$ and $y$, and checking that the minimum value of the LHS is $4AD - B^2 - C^2$.

My question is: What algorithm would you use to draw it?

Seems there are different approaches:

1. Break it into the circle case and line case. Draw each using a dedicated routine. This way, you can use pre-existing drawing routines. There is a problem here, which is that out of many possible floating point values, only one of them is exactly $0$. So the line case happens in one case out of $2^{64}$ (if you use $64$-bit floats). And on top of that, thanks to rounding errors, what should be a line can become a circle. The circle case requires finding the centre and radius, but these can both be large values, subject to floating-point rounding errors. You can use a threshold instead of checking whether $A = 0$, but which threshold should get used?
2. Traverse each value of $x$ in the viewport, and compute the (at most) $2$ different values of $y$, and draw those points. Then do the same again, but traversing each value of $y$ and finding $x$.
3. A generalised circle determines a constant-speed motion along it. Use this somehow.
4. A generalised circle determines an inversion through it. Use this fact somehow.

Approach 2 explicitly uses the viewport. Approaches 3 and 4 are vague, but depend on knowing it as well.

What approaches are there?

Answer 1

I am assuming you want to generate a raster image of the circle, since you are considering the viewport.

Given that, I think you're focusing on the wrong thing: If you have the viewport, you can just check if each coordinate satisfies the equation. The point is, if your A goes to zero, the 'other end' of the circle might not even be in the viewport(you don't have to 'treat' it differently). The main problem is, the pixels in the viewport might not even have a few floating point coordinates that satisfy the equation(that's where you'd need a threshold):

Increasing the margin of error would give you this:

I've made a small shader toy for this: https://www.shadertoy.com/view/7tVBDV

You can change it/tell me if you're looking for something else.

Answer 2

• For each pixel in the image:
  • For each corner $(x,y)$ of the pixel (imagining the image as a small square tiling), compute the sign of $A(x^2+y^2)+Bx+Cy+D$.
  • If all the signs are the same, plot the background colour.
  • If any of the signs differ, plot the foreground colour.

See https://www.shadertoy.com/view/NlGBWt for a live WebGL-based example. There is a slight thickening artifact for certain parameters, when the curve gives a sign of exactly $0$ for many pixel corner coordinates.