Game Development Reference
In-Depth Information
Simplifying the problem
Surprisingly, many collision detection problems in 3D can be simplified to
a 2D solution. If your character is wandering around a set where the floor
is flat and the walls are fairly vertical, then collision detection can be
reduced to detecting whether a single 2D polygon intersects another 2D
polygon. Before we look at this general case, we can simplify the problem
still further by looking at a single point inside a polygon. If the polygon is
convex, then a point is inside this
polygon if the dot product of a
unit length vector from the point
to each corner vertex in the
polygon and a unit length vector
from the same corner vertex to
value under 1.0. A dot product of
two normalized vectors gives the
cosine of the angle between the
two vectors. The cosine curve
runs from 1.0 to 0.0 for angle
values of 0-90°.
Unfortunately, normalized
vectors require a square root
operation, which is computa-
tionally expensive. Another flaw
in using this method is that the technique only works on convex
polygons. An alternative approach that works with any arbitrary polygon
Divide the polygon into four quadrants centred on the test point. Start
at the first edge in the polygon; if this edge crosses a quadrant
boundary in a clockwise direction add 1 to a count, if the edge crosses
a quadrant boundary in an anticlockwise direction then subtract 1 from
your count. If the value of the count after iterating through all the edges
in the polygon is either 4 or -4 then the point is inside the polygon.
Figure 13.7 illustrates the concept; of points A-E, only point A gives a
result of 4.
If the quadrants are labelled as in Figure 13.7 then the truth table for
the updating of the count variable is as in Table 13.1.
Notice that the leading diagonal, where both ends of the edge are in
the same quadrant, has no effect on the count and that quadrants
cannot be reached across the diagonals. We can use the truth table to
calculate the count value for vertex A:
Figure 13.6 Determining whether a point
is inside a polygon using the dot product
method.