Graphics Reference
In-Depth Information
its level,
the coordinate transformation and its inverse for the associated bounding box,
edge linearity and flatness measures,
the parameter domain,
the values, partials, and normals at the vertices and the centroid,
a pointer to a doubly linked adjacency list used for sorting, and
pointers to child nodes.
An adjacency list node consisted of a pointer to a doubly linked list of nodes that con-
tained intersection information, namely,
the start and endpoint of the domain of the segment in the form of four reals u
1
,
v
1
, u
2
, and v
2
,
the start and endpoint
p
1
and
p
2
of the segment in
R
3
, and
a flag indicating whether the segment terminated.
There was a list of pairs of quadtree nodes whose bounding boxes intersected.
The Barnhill-Kersey Sorting Phase.
The quadtree data structure facilitated the
sorting phase, but is not necessary. Note that all non-closed polygonal curve segments
generated by the tracing phase terminate at boundary or branch points. When sorting
those segments, endpoints are considered the same if they are within a tolerance of
e
SPT
. The recursive divide-and-conquer algorithm described in [HEFS85] was used on
the partial adjacency lists associated to the quadtree nodes.
This finishes our discussion of the algorithm in [BarK90]. The authors compared
their algorithm to others, in particular to those in [BFJP87] and [HEFS85]. The advan-
tages were that it also worked for parameterizations with triangular domains, did
not need second derivatives, and handled more tricky cases correctly. It was at least
as robust or more than other surface intersection algorithms. The tolerance constants
described above could be adjusted manually to achieve better results in difficult cases.
The reader might also look at the algorithm in [Luka89] for additional details on the
Newton-Raphson mathematics.
As a third example of a marching method for finding the intersection of two sur-
faces, assume that the intersection curve lies in the uv-plane, is defined by an equa-
tion f(u,v) = 0, and we have already computed the ith solution point
p
i
= (u
i
,v
i
). Of
course, one can look at this version of the intersection problem from various points
of view. It can be thought of as an implicit curve or contour problem. Sections 14.5.1
and 14.6 discuss those. Here we shall describe a “step constraint” approach for getting
the next point. Let us add another constraint g(u,v) = 0. For example,
2
2
(
)
=-
(
)
(
)
2
guv
,
u u
+-
v
v
-
d
(13.15)
i
i
corresponds to requiring that the next point
p
i+1
is on the intersection a distance d
from
p
i
. A step in the direction of the tangent of the curve at (u
i
,v
i
) is used as an initial
guess and then a Newton-Raphson method is used to converge to the next solution.
See Figure 13.17. There are the usual potential problems such as needing a start point
