Scan Conversion of 3D Spheres

Jon Leech,, 11 Feb 1994

[A poster to writes:]

Scan conversion algorithms are relatively easy to find or derive for polygons, since a transformation matrix turns the 3D rendering problem directly into a 2D scan conversion.

I've noticed that there doesn't seem to be much mention of the equivalent problem for scan converting a sphere. Basically, given a sphere center and radius, a 4x4 transformation matrix (from your camera model, including perspective), determine which pixels are covered by the sphere.

The clearest (and almost the only) explanation of general quadric scan-conversion algorithms I've seen was in a 1983?84? paper by Jim Blinn that was not, as far as I know, published (might have been in SIGGRAPH course notes). A substantially compressed version appeared in his CG&A column a few years back. Here's a summary:

An arbitrary quadric equation Ax^2 + ... + J = 0 can be expressed in matrix form as

    (x y z 1) Q (x y z 1)  = 0	[1]
where Q is a symmetric matrix formed from the coefficients. Given an arbitrary 4x4 transform T that transforms points P' = P T (row vectors), T transforms quadrics as
	  adj	adj	<- denotes adjoint
    Q' = T   Q T	    [2]

Let T be the complete model -> screen transform (not to NDC, but to actual pixel coordinates). You would typically start with a unit sphere, x^2 + y^2 + z^2 - 1 = 0, and scale and translate its matrix giving the matrix Q for a particular center and radius. Then Q' represents the quadric surface in screen space. Note Q' is not neccessarily the same kind of quadric surface as Q. Now at each pixel (Xs,Ys) on the screen, construct the point (Xs Ys z 1). Substitute this into [1], yielding a quadratic equation for Z. Solve this equation, reject roots outside the canonical Z clipping volume, and if any solutions remain, the surface is visible at that point.

So far this is not significantly different from ray-tracing quadrics - we just transformed the object all the way into screen space instead of doing the ray-object intersection in world or model space. What makes it worthwhile as a scan conversion algorithm is that you can perform numerous optimizations. Operating on the coefficient matrix in various ways lets you rapidly find the overall Y range and the per-scanline X range of the surface, then you can use quadratic forward differencing to walk the scanline segments (still have to solve for the roots, but you don't have to evaluate as much at each pixel). And given the screen space solution, you can transform backwards to get viewing space normals and texture coordinates for lighting calculations. You can do lots of other interesting tricks, like classifying quadric matrices into surface types depending on their eigenvalues, or finding silhouette curves.

Contrasting this to fast sphere algorithms of various sorts:

Note that quadrics are the most complex type of surface you can come up with direct closed-form scan conversion algorithms for. Move up to, say, bicubic patches and you either tesselate or use root-finding algorithms (or combinations thereof). And aside from spheres, quadrics are not all that useful as modelling primitives.