doom physic based on tesselation

  Algorithm so far

  We have a quadtree that will pre-filter elements.
  The quadtree only knows about AABB (Axis Aligned Bounding Box).
  It associates an AABB with an ELEMENT, which is
  1) a type and
  2) an id.

  There is right now two kind of type: TRIANGLE and LINEDEF
  When the type is TRIANGLE, the id refers to a triangle in the tesselation.
  When the type is LINEDEF, the id refers to a linedef in the map.

  As the tesselation is not an array but an array of array, there is a trick when the type is TRIANGLE : we have an array of pairs of index.
  The id is an index into this array.


  That being said, the two type have also two differents meaning.
  When the type is TRIANGLE, we only perform two tests:
  1) is the center of the AABB inside the triangle ?
  2) is the center of the triangle inside the AABB ?

  Iff the answer of any of these questions is "yes", then we record the thing as being "in this sector".

  When the type is LINEDEF, we check if the AABB actually intersects (or contains) the linedef.
  Iff the answer is yes we check if this movement is valid. This mean:
  1) If both linedef's sides have a sector
  2) If both linedef's side's sector's floor's height is "not to high".

  Now, you maw wonder "why don't you perform a complete collision test when the type is TRIANGLE ?".
  Well, here are the different cases:
  1) the AABB is entirely inside the triangle => check the center is enough
  2) the triangle is entirely inside the AABB => check the center is enough
  3) the triangle is entirely outside the AABB => no intersection anyway.
  4) the AABB is crossing the triangle.

  In this last case, several sub-cases:
  1) the AABB is crossing a triangle side which happens to be a linedef => there will handled with other LINEDEF
  2) the AABB is crossing only non-linedefs.

  This 2) means that an other triangle of the SAME sector contains the center of the AABB, because non-linedef side only exists between triangles of the same sector.

  The reason why we use the center (for both triangle and AABB) is that
  1) it is easy to calculate
  2) it avoid rounding problems