[ Pobierz całość w formacie PDF ]4 Similarly, given a pair of edges EA and EB as inputs, if their nearest points PA
and PB satisfy the point-edge applicability criterion imposed by EB and EA, then
they are a pair of closest features between two polyhedra. If not, one of the edges
will be changed to a neighboring vertex or a face and the veri cation process will be
done again on the new pair of features.
5 When a given pair of features is an edge EA and a face FB, we rst need to decide
34
whether the edge is parallel to the face. If it is not, then either one of two edge's
endpoints and the face, or the edge and some other edge bounding the face will be the
next candidate pair. The former case occurs when the head or tail of the edge satis es
the point-face applicability condition imposed by the face, and when one endpoint of
E is closer to the plane containing F than the other endpoint of E. Otherwise, the
edge E and the closest edge EF on the face's boundary to E will be returned as the
next candidate features.
If the edge and the face are parallel, then they are the closest features
provided three conditions are met. i The edge must cut the applicability prism"
PrismF which is the region bounded by the constraint planes perpendicular to FB
and passing through FB's boundary or the region swept out by FB along its normal
direction , that is E PrismF = ; ii the face normal must lie between the face
6
normals of the faces bounding the edge see Fig. 3.7, Sec. 3.4, and the pseudo code in
Appendix B , iii the edge must lie above the face. There are several other situations
which may occur, please see Appendix B or the proof of completeness in Sec. 3.4 for
a detailed treatment of edge-face case.
6 In the rare occasion when two faces FA and FB are given as inputs, the algorithm
rst has to decide if they are parallel. If they are, it will invoke an overlap-checking
subroutine which runs in linear time in the total number of edges of FA and FB.
Note: it actually runs in constant time after we preprocess the polyhedra, since
now all the faces have constant size of boundaries. If they are both parallel, FA's
projection down onto the face FB overlaps FB and each face is above the other face
relative to their outward normals, then they are in fact the closest features.
But, if they are parallel yet not overlapping, then we use a linear time
procedure 71 to nd the closest pair of edges, say EA and EB between FA and FB,
then invoke the algorithm again with this new pair of candidates EA; EB .
If FA and FB are not parallel, then rst we nd the closest feature either
a vertex or an edge fA of FA to the plane containing FB and vice versa. Then, we
check if this closest feature fA satisfy the applicability constraint imposed by FB.
If so, the new candidate pair will be this closest feature fA and FB; otherwise, we
35
Object A
NL NR
E
NF
F
(a)
Object A
NL x E E x NR
E
NL NR
NF
F
(b)
PL PR
Figure 3.7: a An overhead view of an edge lying above a face b A side view of
the face outward normal bounded by the two outward normals of the edge's left and
right faces.
36
enumerate over all edge-pairs between two faces to nd a closest pair of edges and
proceed from there.
If one face lies on the far side" of the other where the face is beneath the
other face relative to their face outward normals or vice versa, then the algorithm
invokes a linear-time routine to step away from this local minimum of distance, and
provides a new pair of features much closer than the previous pair. Please refer to
Appendix B for a complete description of face-face case.
3.3.2 Geometric Subroutines
In this section, we will present some algorithms for geometric operations on
polytopes. They are used in our implementation of the algorithms described in this
thesis.
Edge & Face's Prism Intersection:
To test for the intersection of a parallel edge EA to FB within a prism PrismF
swept out by a face FB along its face normal direction NF, we check whether portion
of this edge lies within the interior region of PrismF. This region can be visualized
as the space bounded by n planes which are perpendicular to the face FB and passing
through the n edges in its boundary.
Suppose Fi is a face of the prismatic region PrismF and perpendicular to the
face FB and passing through the edge Ei bounding FB. To test for EA's intersection
within the prism PrismF, we need to check whether EA intersects some face Fi of
RF.
We can perform this test with easy and e cient implementation1 of this
intersection test. We rst parameterize the edge EA between 0 and l where l is the
length of EA. The idea is to intersect the intervals of the edge EA contained in the
exterior2 of each half-space with each constraint plane in the prism of a face FB.
1
suggested by Brian Mirtich
2
We de ne the exterior half-space of each constraint plane to be the half-space where all the points
satisfy the applicability constraints imposed by FB's boundary. The "point-cell-checkp" routine in
the pseudo code can clarify all the ambiguity. Please refer to Appendix B if necessary.
37
First, we decide whether the edge EA points inward or outward of each hyperplane
Fi of the region by taking the inner product of EA's unit directional vector with Fi's
outward normal NFi .
Then, we can decide which portion of EA intersect the exterior half-space
of Fi by taking another inner product of the head of EA and Fi's outward normal
normalized by the inner product of EA and NFi to calculate the relative inclusion"
factor of EA inside of the prism region. The relative beginning and ending inclusion
factors should be in the range of 0 and l for an indication of an edge-face's prism
intersection.
Pseudo code for this approach just described is listed in Appendix B. This
geometric test is used in our implementation of distance computation algorithm as a
subroutine to check whether a given edge intersects the Voronoi prism of a given face
to test their eligibilities be a pair of closest features.
Face & Face's Prisim Intersection:
To check if two convex polygons A and B are overlapping, one of the basic
approaches is to verify if there is some vertex of A lying on the inside" of all edges in
the boundary of B or vice versa. The inside" refers to the interior half-plane of the
edge, not necessary the interior of the polygon. A n-sided convex polygon is formed
by the intersection of interior half-planes of n edges. We can use the fact that two
polygons do no overlap if there exists a separating line passing through one edge in
the boundary of either face. The polygons overlap, if and only if none of the edges
in the boundary of both polygons forms a separating line.
For our own application, we are interested to verify whether a face A's pro-
jection down to the plane containing the face B overlaps with the face B, where A
and B are parallel and in R3. To nd a separating line between two such polygons
in R3, we check if there exists a supporting plane passing through an edge in the
boundary of one polygon such that all vertices of the other polygon lies in the exte-
rior half-space" of the supporting plane. The supporting plane is perpendicular the
polygon and containing an edge in the polygon's boundary. This approach runs in
O N2 time where N is the number of edges of each polygon.
38
[ Pobierz całość w formacie PDF ]zanotowane.pldoc.pisz.plpdf.pisz.plkajaszek.htw.pl
