An accurate algorithm for rasterizing algebraic curves

Publisher Website
Google Scholar
Abstract
In this paper we introduce a new algorithm for ras- terizing algebraic curves, and we discuss applications to surface and surface-surface intersection rendering and visualization. By rustm"zing 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 prob- lem is be reduced to testing whether the curve cuts a square or not. Other mwearchers have followed this approach, but their tests are either computationally ex- pensive, or apply just to special cases. Curves with singularities are particularly difficult to deal with, and most know algorithms fail to nmder these curves cor- rectly. Our contribution in this paper is the introduction of a computationally effiaent and asymptotically cor- rect test, which applies not only to dimension two, but also to dimension time 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 ~ is a polynomial, it produces the same results whether the coefficients of ~ or ~z 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 sin- gular surface, space algebraic curves (surface-surface intemections) can be approximated as well. We show examples of these applications. This sets of voxels can be used for tolerance analysis and to compute polyhe- dral or piecewise linear approximations of the curves or surfaces for interactive nmdering purposes as well.

This publication has 0 references indexed in Scilit: