©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.
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:
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.
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.
This implementation could be further optimized by somehow narrowing the list of polygons to be tested (to skip dot product calculations).
How to narrow the list of which polygons to be tested?
Last modified: Tue Aug 15 15:54:45 EDT 2006