# Collision-detection at a polygon

©2005 Jim E. Brooks http://www.palomino3d.org http://www.jimbrooks.org/sim
Diagrams were drawn using GNOME dia.

This is an alteration of a prior idea to be optimal and easier to implement. Reading the prior idea may help to understand this. How polygon interior testing is done is the difference.

The idea is to detect a collision into an object by testing if a dynamic object's trajectory has passed thru a polygon of the object.

## Trajectory passing thru a polygon

In the above illustration, the blue vector is the trajectory of the dynamic object (Dyna) which has passed thru the polygon of another object. In one stride, one point on the trajectory faces the polygon but a further point doesn't. The orange vector is the polygon's 3D normal vector.

The Dyna passing thru (colliding into) a polygon can be detected by two conditions:

1. If the 3D dot product of the Dyna and a polygon's normal vector transitions from facing to not-facing.
2. If the Dyna's origin lies in the 2D interior of the polygon after projecting the polygon from the viewpoint of the Dyna and transformed the polygon into the Dyna's 3D local space (see below illustration).

## Transforming an object into the Dyna's local space

In this illustration, the vertexs of an object have been transformed into the Dyna's local space. This is like the perspective of a first-person view -- but from the viewpoint of the Dyna rather than the Eye. Notice that one triangle encloses the Dyna's origin in the XY plane (in 2D, the Dyna's origin is in the interior of a polygon). The Dyna is moving towards that triangle and might pass thru it (collide). Although the illustration is 2D, a project calculation isn't implied, rather, 3D transformation of (X,Y) without Z will suffice.

## Polygon Interior Testing

The prior idea would've tested if a 2D point (the Dyna origin) lies in the interior of a polygon by calculating 2D normal vectors and dot products with them and the Dyna's origin. A simpler and more practical alternative, which eliminates those calculations, is to turn 2D polygons into 2D squares. The problem of polygon interior testing then becomes a 2D clipping problem. The latter is easier to solve and implement.

A 2D square that encloses a polygon equals its pair of min/max (X,Y) coordinates. By turning a polygon into a square, to polygon interior test becames easy and fast: the origin is in the interior if the signs of the min coordiante is (-,-) and the the max one is (+,+).

Shown is a polygon that would be a part of mesh of other polygons (not shown).

## Implementation

Once an object has passed the approximate collision-detection tests (radius method, slice method), this polygon-interior test is reached (this is the final test that is "exact"). Since this test is based on determining if the Dyna object was-facing-then-isn't-facing, current and previous states are needed. Each state is an array of booleans, correlating to every polygon, and true if the Dyna was facing that polygon. The first time there is a transition from a last approximate test to this test, allocate two boolean arrays, compute one, then return. If the next frame also transitions, swap the arrays, compute the other. Now that both states are available, test for the transition of the Dyna from facing-to-not-facing. When a polygon is found that isn't facing the Dyna, check the previous array if the polygon was facing. If it was, transform the polygon's vertexs to Dyna space. If the polygon, when turned into a 2D square (as described earlier), encloses the Dyna origin, return that a collision was detected. To support multiple views, the pair of boolean arrays (and frame count) should be per-view.

Last modified: Tue Aug 15 15:54:33 EDT 2006