Graphics Reference
In-Depth Information
we also want those two vectors to be almost parallel or the angle between them small.
See Figure 13.13(b). The e
FT
and e
ELT
in the figures represent some predefined
flatness
and
edge linearity tolerances
, respectively.
At this stage, a parallelopiped bounding box is associated to each subpatch. Care
must be taken in the definition of these bounding boxes so that they satisfy their essen-
tial property, which is that they contain their subpatch. The initial guess for a bound-
ing box is determined from the vertices of the patch but is then enlarged using
geometric information about the edge tangents and normal vectors. The subdivision
is assumed to be fine enough so that the simple geometric argument that is used
works. One uses the bounding boxes to cull away subpatches from the two surfaces
that cannot possibly intersect. Determining whether two parallelopipeds intersect is
done by transforming the second into the skew coordinate system determined by the
first. The problem reduces to determining whether a parallelopiped intersects the unit
cube and this has a straightforward solution.
Once one has found potential subpatch intersections, there may be some more
subdivisions of those to increase accuracy and/or achieve convergence for subsequent
Newton-Raphson steps. Suppose now that we have two bounding boxes that inter-
sect, one from each surface. One then takes the average of the corner vertices of the
subpatches associated to the bounding boxes and relaxes it to the intersection. One
does this for every pair of intersecting bounding boxes. This will give us a collection
of points on the intersection that are used as start points for the tracing stage, but
before we get to that we want to describe how points are relaxed in [BarK90]. Such
an operation is performed repeatedly in the tracing stage.
Relaxing Points in the Barnhill-Kersey Algorithm.
Let
p
be the point to be
relaxed. The point
q
in the intersection to which
p
is relaxed will be the limit of a
sequence of points
p
i
, where
p
0
=
p
. Assume that we have already found
p
i
. We describe
how the point
p
i+1
is defined. The first step is to find points
q
1
in
S
1
and
q
2
in
S
2
that
are closest to
p
i
. Ways to carry out this step are described in Section 14.2. If the points
q
1
and
q
2
are within a predefined
same point tolerance
e
SPT
, then we have found our
q
and we quit. Otherwise, let
T
j
be the tangent planes to
S
j
at
q
j
. The point
p
i+1
will
be the midpoint of the projections of
q
1
and
q
2
onto the line which is the intersection
of
T
1
and
T
2
. See Figure 13.14. Alternatively, let
n
j
be a unit normal vector for plane
T
j
and define a third nonparallel plane
T
3
as the plane through the point (1/2)(
q
1
+
Figure 13.14.
The Barnhill-Kersey relaxation
algorithm.
