[A poster to comp.graphics.algorithms 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
t
(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
t
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:
- Generates correct image in all cases, including arbitrary (even degenerate) modelling and projection transformations. Fast sphere algorithms generally assume that a sphere always has a circular screen space silhouette, which is completely useless with non-uniform scaling and looks increasingly wrong as the sphere gets away from the center of the view cone. In screen space, spheres usually turn into other types of quadrics - ellipsoids and hyperboloids of 2 sheets - and ideally should be treated as such.
- Gives correct Z values for depth buffering against other objects (the parabolic approximations can lead to odd visual effects), and correct normals and texture coordinates for lighting.
- Works for all types of quadrics, not just spheres.
- Much slower than fast spheres, which are just fine in the typical case where you really want a bunch of spheres and you don't get too close to them. On the other hand, for software implementations, it's probably a lot faster than tesselating the quadric and scan-converting the polygons, as you don't transform dozens of vertices.
- Too complex for most hardware accelerators. Not only are the pixel-level calculations considerably more complex than polygons, the pipeline operations need to be reordered. Other than gross clipping, you have to clip at the pixel level. This would play merry havoc with the broad class of architectures that have a fast FP engine handling vertex transformation, clipping, and lighting and a stupid but very fast hardware scan-conversion unit feeding the frame buffer. We could do it on Pixel-Planes, but there's not really enough pixel memory to do it right even there.
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.