Graphics Reference
In-Depth Information
never end up at a pixel with a “maybe” as an answer. Taubin indicated how the algo-
rithm could be extended to three-dimensional rasterization of surfaces and surface
intersections. The answers in that case were collections of boxes useful for volume
rendering type situations.
A number of algorithms that solve equation (14.8) are based on marching
methods. They produce polygonal approximations to the curve. For example,
Timmer's algorithm for finding surface intersections can also be used to compute
implicit curves. One simply defines a grid in the plane. Another marching algorithm
is described by Snyder in [Snyd92]. It uses interval analysis and is better and more
robust than the algorithm by Timmer or [BHLH88]. Section 18.5 has an overview of
Snyder's algorithm. Of course, one could also use the algorithm described later in
Section 14.6 since implicit curves can be thought of as contours.
A final approach to solving equation (14.8) that we want to describe is one that
uses algebraic geometry methods. For more details see Bajaj et al. ([BHLH88]) and
Hoffmann ([Hoff89]). Algebraic geometry approaches to solving equation (14.8) fall
into two categories:
(1) One can try to find a parameterization for the curve.
(2) Starting with a point on the curve, one can use a standard incremental
approach to crawl along the curve when one is not near any singularities, but
use algebraic geometry to get past singularities.
Techniques for converting from implicit to parametric representations are dis-
cussed in Section 10.15 in [AgoM05], but not all algebraic curves are rational and
Sederberg et al. ([SeZZ89]) describe a way to get approximate parameterizations. Here
we describe an incremental approach. We start with a fundamental result from alge-
braic geometry (Theorem 10.13.26 in [AgoM05]) that says that every such curve can
be transformed birationally into a plane curve g(u,v) = 0 which contains at most ordi-
nary singularities, that is, points where the curve crosses itself in a transverse fashion.
(We shall not count ordinary singularities as singularities in the discussion that
follows.) Actually, there is a stronger theorem (Theorem 10.13.27 in [AgoM05]), which
states that a curve is birationally equivalent to a curve without any singularities at all,
but unfortunately the latter will in general be a curve in higher dimensions. At any
rate, the basic idea for tracing a curve
C
defined by equation (14.8) will therefore be
to toggle between two modes:
(1) If we are at a nonsingular point of f, then trace
C
using f and some standard
Newton-Raphson root-finding method until done or until we approach a sin-
gularity of f.
(2) If we are near a singularity, then trace
C
using g in a neighborhood of this sin-
gularity until we are past the singularity and then return to tracing
C
using f
again.
This approach works because a curve has only a finite number of singular points
(Theorem 10.6.4 in [AgoM05]). The reason that we cannot simply use g for the whole
process is that this would involve tracing through points at infinity. Algorithm 14.5.1.1
shows the steps of the algorithm. We shall now describe them in more detail.
The curve
C
is traced using what is called a
place
of f in algebraic geometry.
Assume that
p
0
= (x
0
,y
0
) is a point of
C
and that the formal power series
