Rasterizing Algebraic Curves and Surfaces

A new, recursive, space-subdivision algorithm for rasterizing algebraic curves and surfaces gets its accuracy from a newly devised, computationally efficient, and asymptotically correct test. The approach followed is essentially the interval arithmetic method for rendering implicit curves. The author's contribution is a particularly efficient way to construct inclusion functions for polynomials. An ideal algorithm is given for rendering an algebraic curve Z(f)={(x, y): F(x, y)=0} in a square box of side n. The algorithm scans the square and paints only those pixels cut by the curve. This algorithm is ideal, because every correct algorithm should paint exactly the same pixels, but it is impractical. It requires n/sup 2/ test evaluations, one for each pixel in the square. However, since in general it will be rendering a curve on a planar region, the number of pixels it is expected to paint is only O(n). We need a more efficient algorithm. There are two issues to examine. The first is how to reduce the computational complexity by recursive subdivision. The second is how to test whether the curve Z(f) cuts a square. © 1994 IEEE.