Collision Detection  
 

The collision detection method described is between a

sphere and a polygon mesh. The coodernate system used

is the universe. The mesh has only convex polygons.


The viewer is the sphere. The center is viewer

position, and, is recomendable, as minimum radius, the

half viewport diagonal measure, in universe reference system

coordenate units.


The collision detection is made in two steps. First, verify

if the distance between the sphere and the polygon plan is

equal or less than the radius. Second step, case the first

is true, verify if the intersection point between sphere

and the plan is inside the polygon area.


For each polygon in the mesh is needed make collision

detection tests. This can be optimized, as suggested bellow.


To implement the first step is needed define the distance,

between a point (viewer position) and a plan, using

the expression:

   distance = ax + by + cz - d

   where,

   (a, b, c) are the polygon normal vector normalized,

   (x, y, z) are viewer position,

   d = - ax' - by' - cz',
   
   (x', y', z') are any point inside plan (can be a vertex).

Both, "d" and (a, b, c), can be pre-calculated.

If the distance is equal or less than sphere radius is needed

run the second step.


In my implementations, the second step, doesn't work

for all cases. I don't know exactly why.


For the second step is needed one new information:

the intersection point.


The intersection point between the

sphere and the plan can be computed by projecting the

sphere center to the plan, using the expression:

   px = x - a * distance
   
   py = y - b * distance
   
   pz = z - c * distance

   where,

   (px, py, pz) is the projected point,

   (x, y, z) is sphere center position is space,

   (a, b, c) are the polygon normal vector normalized,

   "distance" is the value computed on first step.

 
To verify if a point is inside a convex polygon is used

dot-product between two vectors. The algorithm is:

   - select one polygon vertex;
  
   - make a vector from selected vertex to its next vertex;
  
   - make other vector from the selected vertex and the point
  
     to be tested;

   - compute dot-product;

   - select the next vertex and make all again.

If the dot-product sign change during the interaction, this

mean the point is outside the polygon. If there is no sign

change, the point is inside the polygon.


Example of how to get the vectors:


         1--------2
        /          \
       /            \
      /              \
     /                \
    /   polygon        3
   /                  /        
  /                  /
 /                  /
5------------------4           * point

Interaction 0:

         1--------2
        /          \
       /            \
      /              \
     /                \
    /   polygon      _ 3
   /                  /|      
  /                  /  
 /                  /
5------------------4------->* point

Interaction 1:

         1--------2_
        /         |\
       /            \
      /              \
     /                \
    /   polygon        3  
   /                  / \     
  /                  /   \
 /                  /    _\/
5------------------4       * point

....


The first step can be optimized if the mesh has explicit

information about its plans. Share a plan with many polygons

have other advantajes like: memory save, more efficient

back-face culling, ...


Other optimization can be made, if collision detection is

to avoid polygon crossing. For example, between the

viewer and a wall, in some cases, is only need the first step.

If the polygon is not in same plan as a portal (portals must

be crossable polygons) maybe this is possible.


If the collision detection is made only between the sector

where viewer is, there is a problem. No adjacent sectors

can be smaller than the viewer radius. Or while the viewer is

going to the adjacent sector it can cross some destin sector

polygons.


In second step, 3DFC v0.0.1 use other way to make sign test.

Is used, cross-product between two vectors to define a

normal vector. The sign test is made over each normal vector

component. This solution is more slow and don't work for

all cases.

Up