Game Development Reference
In-Depth Information
new lower bound on d min . Note that it is neither simple nor practical to literally
search through all vertices for a given face in FV and VF cases. Obviously,
since we know the potential s min direction for the face, we can just directly find
the opposing-shape support vertex, which is faster and easier. The support-plane
search can be accelerated using the Dobkin-Kirkpatrick (DK) hierarchy [Dobkin
and Kirkpatrick 90] or gradient walk. Most of the signed distance values will
usually be deeply negative, if we enumerate all of the possibilities.
If d min
0, it means the polytopes intersect and we found the correct
( s min ,d min ). Otherwise, we have the following choices:
1. Stop and detect no collision.
2. Stop and return d min as the lower bound of distance.
3. Continue to find the exact Euclidean distance (Equation (4.5)).
In the latter case, we need to incrementally compute ( s ,d ) for the remaining
sets VE , EV ,and VV
( s min ,d min )=max
d
{
( s ,d ): s
FV
VF
EE
VE
EV
VV
}
. (4.5)
The algorithm from Equation (4.5) is in Listing 4.2. Please refer to Table 4.4
for the notation used.
v 0 ( e ) , v 1 ( e )
The two vertices of edge e ; v 0 ( e ) = v 1 ( e )
norm ||·|| ( x )
Normalization operator :
x /|| x ||
n 0 ( e ) , n 1 ( e )
Normals of faces adjacent to edge e ; n 0 = n 1
e ( e )
Edge e direction ± norm ||·|| ( v 1 ( e ) v 0 ( e ))
e ( e )= norm ||·|| ( n 0 ( e ) × n 1 ( e )) if n 0 = n 1
proj ( v ,e )
Projection of
v
onto edge e :
v 0 ( e )+ e ( e )(( v v 0 ( e )) · e ( e ))
n ( f )
Normal of face f
V ( S ) , E ( S ) , F ( S )
Sets of vertices { v i } , edges {e i } , faces {f i } of shape S
Ta b l e 4 . 4 . Notation guide.