Graphics Reference
In-Depth Information
We first consider the case where
S
is faceted. Assume that
S
has convex facets. To
find the section of
S
with respect to some plane there is again no loss of generality
by assuming that the plane is the x-y plane. The idea will be to find all the edges of
S
that cross the x-y plane and then to connect the intersection points appropriately. To
find the crossing edges, we only need to look at the z-coordinates of the endpoints of
the edges and see if they straddle 0. To facilitate connecting the edge intersections we
use the fact that if the section crosses a face then it crosses two of its edges (unless
it just touches the face in an edge or vertex). Therefore, we associate a pair of inte-
gers to each face which will either both be -1 or the index of an edge in the edge array.
The resulting algorithm is shown in Algorithm 13.4.3.1.
The problem of finding sections of smooth surfaces is more complicated. We have
actually run into this problem earlier in the topic. In fact, some of the techniques
described in Section 7.10 that provided a scan line visible surface determination algo-
rithm for smooth surfaces would also apply to solve this problem. Here we describe
another approach. See [PraG86] or [Sutc80].
The Grid or Lattice Evaluation Method.
First of all, we may again transform the
intersection problem by a rigid motion to the case where the plane is parallel or in
fact equal to the x-y plane. The problem then is equivalent to finding a contour on a
surface. If the surface is parameterized by a function
(
)
=
(
(
)
(
)
(
)
)
puv
,
xuv yuv zuv
,
,
,
,
,
,
then the problem is to solve the equation z(u,v) = 0. The basic idea is to reduce the
problem to a lower-dimensional one by adding some constraints. Typically, one eval-
uates z(u,v) at a grid of points (u
i
,v
j
). Let z
ij
= z(u
i
,v
j
). If adjacent z
ij
's have opposite
signs, then the contour will cross the corresponding edge between the grid points.
One finds the crossing point by solving a one-dimensional problem of the form z(u
i
,v)
= 0 or z(u,v
j
) = 0. The intersection points are then connected to get a polygonal approx-
imation of the contour. See Figure 13.9(a). One major problem with this approach is
that it can be difficult to determine how to connect intersection points on the grid
Figure 13.9.
Sections using a lattice evaluation method and ambiguities.
