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 WAS SUPERCEDED AND NEVER FINISHED --
This describes polygon interior testing based on calculating 2D normal vectors and dot products.
See the simpler alternative that is based on turning 2D polygons into 2D squares.

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 purple vectors are 2D normals vectors on the edges of the polygon on its 2D plane.

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 the above 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 a 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

By geometry, a 2D point lies on a polygon if the angle between it and all of the outward normal vectors on the polygon's edges are greater than 180 degrees.

Most dot product calculations can be bypassed by this fact: a polygon that encloses the origin must occupy at least 3 of the 2D quadrants. This condition can be quickly identified by examining the signs of (X,Y). But this condition only indicates the polygon might enclose the origin -- calculating 2D dot products is necessary to be certain.

How would the 2D normal vectors be calculated?

These questions led to the alternative of turning 2D polygons into 2D squares rather than calculating a radius rather than normal vectors and dot products.


Implementation

This implementation could be further optimized by somehow narrowing the list of polygons to be tested (to skip dot product calculations).

  1. As documented elsewhere, faster approximate collision detections are done before doing this.
  2. Of the object that the Dyna might collide into, transform its vertexs into the Dyna's local space.
  3. Calculate the 2D normal vectors (how?)

Questions

How to narrow the list of which polygons to be tested?


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