Graphics Reference
In-Depth Information
and the references in those papers. The solutions to the general problem involve five
basic approaches referred to as lattice evaluation methods, marching methods,
homotopy methods, recursive subdivision methods, and methods based on algebraic
geometry. When the actual complete surface intersection algorithms that have been
proposed are classified as belonging to one of these approaches one must keep in mind
that the algorithms usually consist of several stages and different methods can be used
for the separate stages. Therefore, many algorithms are really hybrids that do not fit
under any single roof as, for example, the ones described in [BarK90], [Kopa91], and
[GraK97]. The next five sections will discuss the various approaches.
[MarM91] describes a parameterization for the intersection curve. [GarW89]
represents the intersection curve algebraically, basically as an algebraic curve and a
birational map between the plane and space curve. Bounding boxes are sometimes
used in intersection algorithms and [FiMM86] gives some general bounds for surfaces.
Parallelism has also been used to speed up intersection algorithms. See [BurS93]
and [ChBA94].
13.5.1
Surface Lattice Evaluation Methods
A common special case of the lattice evaluation method was already described in
Section 13.4.3 in the context of finding contours of the graph of a function of two
variables. For more general surface intersection algorithms the method is used at most
as a preprocessing step to get some starting points in the intersection. Given two para-
metric surfaces p(u,v) and q(u,v), one considers the lattice of curves p(u
i
,v) and p(u,v
j
)
defined over grid lines in the rectangular domain of p(u,v) and finds their intersec-
tion with the surface q(u,v). The intersections give us starting points to which a march-
ing method can be applied to find the complete intersection of the two surfaces. One
might have to refine the lattice at places to make sure that no part of the intersection
is missed. We shall see an example of this in the discussion of Timmer's algorithm in
the next section. In [BFJP87] polygonal approximations of the curves p(u
i
,v) and
p(u,v
j
) were intersected with a polygonal approximation of q(u,v) and a Newton-
Raphson method was then used to find real points on the intersection curves.
13.5.2
Surface Marching Methods
Marching methods
, also sometimes referred to as
tracing methods
, are the most widely
used methods for computing intersections. They assume that one has found points
on the intersection and one then “marches” out from those points along the inter-
section curve by using information about the local geometry. We have already seen
examples of this approach in other contexts. In general, this type of approach has
three phases: a
hunting phase
, a
tracing phase
, and a
sorting phase
. In the initial
hunting phase one tries to find start values that one then uses in the tracing phase to
generate sequences of points that lie on the intersection. One needs enough start
values, so that no part of the intersection is missed. Finally, in the sorting phase one
separates the sequences of points generated by the tracing phase into sequences that
define the connected pieces and loops that are the subcurves of the entire intersec-
tion. We end up with a discrete approximation to the intersection.
