Graphics Reference
In-Depth Information
Figure 13.10.
Hunting grids for Timmer's
algorithm.
An early marching method is one due to Timmer. See [Timm77] or [Mort85].
Suppose that two surfaces
S
1
and
S
2
have parameterizations p(u,v) and q(u,v), respec-
tively, each with a rectangular domain. To find their intersection
X
, we shall find the
subset of the domain of p(u,v) which parameterizes this set. The three solid curves in
Figure 13.10 are an example of a set of parameter values for one possible such
X
.
Timmer's Hunting Phase.
Subdivide the domain of p into subrectangles. Restrict-
ing p to the associated grid lines defines a grid of curves p(u
i
,v) and p(u,v
j
) on
S
1
. The
intersections of these curves with
S
2
will provide the starting points that are used to
trace the pieces of
X
. We run into the usual problem of making our grid fine enough,
so that we will not miss any part of
X
. In Figure 13.10 the intersection of the grid
lines with this set consists of points that have been numbered from 1 to 15. Let uv
i
denote the parameter point numbered i. The numbering is based on an ordering of
the grid lines and the intersections that lie on them. We started with the vertical grid
lines ordered from left to right and ordered their intersections based on increasing v
value and then moved on to the horizontal lines ordered from bottom to top and
ordered their intersections based on increasing u value. Actually, we do not really have
to compute the intersection points precisely initially. They only need to be accurate
enough so that a Newton-Raphson method, say, can be used to converge to the actual
values. Therefore, the initial guesses for the intersection points could be found by dis-
cretizing the curves p(u
i
,v) and p(u,v
j
) also. Alternatively, we can think of the problem
as one of finding points on a curve that are closest to a surface and use any algorithm
that is known to solve this problem. Once we have our intersection parameter values
uv
i
we start the next phase.
Timmer's Tracing Phase.
We consider the part of the intersection over each subgrid
separately. We analyze each subgrid one after another based on a left to right, bottom
to top order. Figure 13.11 shows the subgrid labeled A in Figure 13.10. Since the points
uv
i
correspond to endpoints of curves in the subgrid, we now use them one at a time
based on their ordering to trace the parts of the curves that lie in the subgrid. This
not only gives an ordering to the pieces but also a direction. Figure 13.10 also showed
the ordering, indicated with the labels a, b, ..., k, and the direction in which curve
segments were traced.
