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