Accurate algorithm for rasterizing algebraic curves

Abstract

In this paper we introduce a new algorithm for rasterizing algebraic curves, and we discuss applications to surface and surface-surface intersection rendering and visualization. By rasterizing an algebraic curve we mean to determine which cells, or pixels, from a square mesh of cells in the plane, are cut by a curve represented as the set of zeros of a polynomial in two variables. By using a recursive space subdivision scheme, the problem is be reduced to testing whether the curve cuts a square or not. Other researchers have followed this approach, but their tests are either computationally expensive, or apply just to special cases. Curves with singularities are particularly difficult to deal with, and most know algorithms fail to render these curves correctly. Our contribution in this paper is the introduction of a computationally efficient and asymptotically correct test, which applies not only to dimension two, but also to dimension three and above. We prove that the recursive space subdivision algorithm based on this new test renders a curve of constant width, even in neighborhoods of singular points, and with no missing parts. For example, if f is a polynomial, it produces the same results whether the coefficients of f or f2 are given as input to the algorithm. Not many algorithms satisfy this property. Finally, the same methodology can be applied to compute a set of voxels containing an algebraic surface, and by representing it as a singular surface, space algebraic curves (surface-surface intersections) can be approximated as well. We show examples of these applications. This sets of voxels can be used for tolerance analysis and to compute polyhedral or piecewise linear approximations of the curves or surfaces for interactive rendering purposes as well.