🚀 go-pugleaf

One idea that pops into mind is to split the geometric figure into 
triangles. That way it is defined more clearly what is inside the 
figure and what is not (crossing lines, etc).

Collision detection between two such objects is then reduced to
checking whether any points in one figure is inside the other figure
or the other way.

Which is then broken up to checking point against triangle.

To determine whether a point P is inside a triangle ABC, I calculate
the distances (squared) AP, BP and CP. The distances between the
corners of the triangle are also needed, but those should be precalculated.
The test is then simple. P is inside ABC if 

   AP is less than or equal to AB and AC
      and
   BP is less than or equal to BA and BC
      and
   CP is less than or equal to CA and CB

Otherwise P is not inside ABC.


This is how I would implement it :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

0) Design the figure, and calculate a table telling the (square) of all
   distances between points at ends of connecting lines and store in a 
   table DIST

                    ________------/C
             A\-----             /|
               \                / |
                \       P      /  |
                 \     x      /   |
                  \          /    |
                   \        /     |
                    \      /      |
                     \    /       |
                      \  /  ___---D
                       \/---
                        B

   DIST =

      A   B   C   D	Note that as there are no lines between A and D,
   A  -   5   6   -	the AD/DA distance will never be used. Similarly
   B  5   -   7   3	the AA, BB, CC, DD distances are never used ...
   C  6   7   -   4
   D  -   3   4   -


When checking if point P is inside the figure :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1) Calculate distances (squared) from all points in the figure to P, and
   store them in a table called PDIST

   PDIST = 

   A  3
   B  4
   C  4
   D  5

2) if |AP|<=|AC| and |AP|<=|AB| and
      |BP|<=|BA| and |BP|<=|BC| and
      |CP|<=|CA| and |CP|<=|CB| then P is inside ABC

   Triangles could be represented as arrays[1..3] of integer, the integers
   being references into the DIST table and PDIST table. Calling the 
   triange TRI :

   function triangle_hit (var tri : ... ) : boolean;
   begin
      triangle_hit :=
        (pdist[tri[1]] <= dist[tri[1],tri[2]]) and
        (pdist[tri[1]] <= dist[tri[1],tri[3]]) and
        (pdist[tri[2]] <= dist[tri[2],tri[1]]) and
        (pdist[tri[2]] <= dist[tri[2],tri[3]]) and
        (pdist[tri[3]] <= dist[tri[3],tri[1]]) and
        (pdist[tri[3]] <= dist[tri[3],tri[2]]);
   end;




Note that I have used the square of all distances. The reasons are :

   1) calculating square root takes time
   2) the squares will be integers (longs ?) and should be faster to
      compare than floats.


The algorithm for checking whether two objects collide can look like this :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1) Compare bounding boxes for the two objects, if overlap then continue.
2) For each point P in figure 1 do :
     if P inside bounding box for figure 2 then check for hit
3) For each point P in figure 2 do :
     if P inside bounding box for figure 1 then check for hit
4) If reaching this point without a hit, the objects have not collided.

The calculations involved in point (2) and (3) consist of finding
squared distance from points in the figure to the point P. 

   (sqr(Px - FPx) + sqr(Py - FPy)); where FP is a Figure Point.

With N points (N+1 triangles) we have :

2N subtractions
 N additions
2N multiplications
6N comparisons
Some table lookup


THE big question is of course :
   Is this efficient or not ?


B^?

--
Roar Foshaug                                      (roarf@stud.cs.uit.no)
Department of Computer Science
University of Tromsoe                             'oe' is '\o{}' in Tex
N-9000 TROMSOE, NORWAY                            'OE' is '\O{}' in Tex