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

the adjacent vertex returns a

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

uses the quadrant technique.

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.

Search Nedrilad ::

Custom Search