Game Development Reference
In-Depth Information
4.6.10 Shamos and Hoey Polygon Intersection Algorithm
This algorithm [Shamos and Hoey 76] is very easy to understand, hence easy to
implement. First, split both polygons into two chains going top-to-bottom (from
the vertex with max y to the vertex with min y ). They will share the top and
bottom vertices, and there will be left and right chains for each polygon. Then
scan top-to-bottom and intersect trapezoids.
On every step, we need to check whether each side of the trapezoid inter-
sects each other side. And every step means introduction of an additional vertex,
so we'll need to check whether the other polygon's trapezoid contains the new
vertex. If it does, we'll include it into our contact manifold.
4.7 SAT Optimizations
SAT is used to compute the contact normal and penetration or separation for two
convex shapes. We describe the brute-force SAT in Sections 4.4 and 4.6.1. The
notation s is used for the contact normal. To use SAT for concave shapes, we
need to decompose them into convex pieces and generate a manifold for each
pair of pieces from both rigid bodies. Ideally, we need to cull contacts then. If
there are more than a few pieces, consider using some kind of bounding volume
hierarchy (BVH), like sphere tree, or some other heuristic limiting many candidate
features [Terdiman 08].
4.7.1
Limiting Candidate Features
One of the most obvious things to optimize is the number of candidate feature
pairs to check, especially edge-edge pairs, as their count grows quadratically
with the complexity of the polytopes and there's no obvious hill-climbing or DK-
hierarchy-based algorithm to restrict that complexity, like in the FV , VF ,and
VV cases.
AGaussmap(
) is a natural way to analyze support planes and features.
A face maps to its normal, just one point on a unit sphere. An edge maps to
an arc, and a vertex to a spherical polygon. Support features in direction s on
a polytope have the Gauss map areas that include vector
G
s is also a
witness feature in the same direction on the Gauss map. For example, if vertex
v supports polytope in direction
s .And
( v ), the solid angle or
spherical polygon v maps to. When the supporting feature is an edge e (and its
two vertices are v 0 and v 1 ),
s ,then s is inside
G
s will happen to be on the arc
G
( e ), which happens
to be the shared border between areas
A 0 =
G
( v 0 ) and
A 1 =
G
( v 1 ). When the
supporting feature is a face f with vertices v i , i =0 ,...,n ,
s =
G
( f ) will