Graphics Reference
In-Depth Information
t
V
i
V
i
+
t
Figure 9.14
For a convex polyhedron under a translational movement
t
, the convex hull of
the vertices
V
i
at the start and the vertices
V
i
+
t
at the end of motion corresponds to the
swept hull for the polyhedron.
respectively. To simplify the collision test, the problem is recast so that
Q
is sta-
tionary. The relative movement of
P
(with respect to
Q
) is now given by
t
=
t
1
−
t
2
.
Let
V
i
be the vertices of
P
in its initial position.
V
i
+
t
describes the location of the
vertices of
P
at the end of its translational motion.
It is not difficult to see that as
P
moves from start to end over its range of motion
the volume swept out by
P
corresponds to the convex hull of the initial vertices
V
i
and the final vertices
V
i
t
(Figure 9.14). Determining if
P
collides with
Q
during
its translational motion is therefore as simple as passing GJK the vertices of
P
at
both the start and end of
P
's motion (in that this convex hull is what GJK effectively
computes, given these two point sets). A drawback with this solution is that doubling
the number of vertices for
P
increases the time to find a supporting vertex. A better
approach, which does not suffer from this problem, is to consider the movement
vector
t
of
P
with respect to
d
, the vector for which an extreme vertex is sought. From
the definition of the extreme vertex it is easy to see that when
t
is pointing away from
d
, none of the vertices
V
i
+
+
t
can be more extreme than the vertices
V
i
. Thus, when
d
0, an extreme vertex is guaranteed to be found among the vertices
V
i
(Figure
9.15a). Similarly, when
d
·
t
≤
·
t
>
0 only the vertices
V
i
+
t
need to be considered for
locating an extreme vertex (Figure 9.15b).
The second of the two presented approaches is effectively implemented by chang-
ing the support mapping function such that the motion vector is added to the vertices
t
t
d
d
V
i
V
i
+
t
(a)
(b)
Figure 9.15
(a) When
d
·
t
≤ 0, the supporting vertex is found among the original vertices
V
i
and the vertices
V
i
+
t
do not have to be tested. (b) Similarly, when
d
·
t
> 0 only the vertices
V
i
+
t
have to be considered.
