home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Peter's Final Project / src / collision.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-10  |  9.4 KB  |  372 lines  |  [TEXT/KAHL]
  1. /*
  2.  *  Peter's Final Project -- A texture mapping demonstration
  3.  *  © 1995, Peter Mattis
  4.  *
  5.  *  E-mail:
  6.  *  petm@soda.csua.berkeley.edu
  7.  *
  8.  *  Snail-mail:
  9.  *   Peter Mattis
  10.  *   557 Fort Laramie Dr.
  11.  *   Sunnyvale, CA 94087
  12.  *
  13.  *  Avaible from:
  14.  *  http://www.csua.berkeley.edu/~petm/final.html
  15.  *
  16.  *  This program is free software; you can redistribute it and/or modify
  17.  *  it under the terms of the GNU General Public License as published by
  18.  *  the Free Software Foundation; either version 2 of the License, or
  19.  *  (at your option) any later version.
  20.  *
  21.  *  This program is distributed in the hope that it will be useful,
  22.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  23.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  24.  *  GNU General Public License for more details.
  25.  *
  26.  *  You should have received a copy of the GNU General Public License
  27.  *  along with this program; if not, write to the Free Software
  28.  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  29.  */
  30.  
  31. #include <signal.h>
  32. #include <stdlib.h>
  33.  
  34. #include "collision.h"
  35. #include "face.h"
  36. #include "matrix.vector.h"
  37. #include "object.h"
  38. #include "sector.h"
  39.  
  40. /*
  41.  * Declare the functions private to this module.
  42.  */
  43.  
  44. static void collide_sector (SECTOR, NUM, VECTOR, VECTOR);
  45. static void collide_face (FACE, NUM, VECTOR, VECTOR);
  46. static short collide_check (FACE, VECTOR, NUM);
  47. static short point_in_sector (SECTOR, VECTOR, NUM);
  48.  
  49. /*
  50.  * Collide the object with its environment. 
  51.  * "start" and "end" are the starting and ending positions 
  52.  *  of its movement. If its movement is obstructed, the 
  53.  *  value of "end" will be modified.
  54.  * Currently, we only look for collisions with the sector the
  55.  *  object is in and its neighboring sectors. This isn't a
  56.  *  problem for us, since the object cannot move more than a
  57.  *  sectors distance at one time. But it is forseeable in a
  58.  *  different environment that we would want to check for collisions
  59.  *  with more distant sectors. 
  60.  * This function also makes sure that all the sectors that
  61.  *  the object overlaps know that the object is in that sector.
  62.  */
  63.  
  64. void
  65. collision (object, start, end)
  66.     OBJECT object;
  67.     VECTOR start, end;
  68. {
  69.     SECTORS neighbors;
  70.     SECTORS sectors;
  71.     SECTOR cur_sector;
  72.     LIST temp_list;
  73.  
  74.     /*
  75.      * First remove the object from all the sectors it
  76.      *  currently overlaps. These sectors are stored in
  77.      *  the "sectors" list.
  78.      */
  79.     sectors = object_sectors (object);
  80.     set_object_sectors (object, NULL);
  81.  
  82.     while (sectors)
  83.     {
  84.         cur_sector = sectors_first (sectors);
  85.  
  86.         temp_list = sectors;
  87.         sectors = sectors_rest (sectors);
  88.         free_list (temp_list);
  89.  
  90.         sector_objects (cur_sector) = objects_remove_object (sector_objects (cur_sector), object);
  91.     }
  92.     
  93.     /*
  94.      * Next, collide the object with the current sector and
  95.      *  its neighbors.
  96.      */
  97.     cur_sector = object_sector (object);
  98.     collide_sector (cur_sector, object_radius (object), start, end);
  99.  
  100.     neighbors = sector_neighbors (cur_sector);
  101.     while (neighbors)
  102.     {
  103.         cur_sector = sectors_first (neighbors);
  104.         neighbors = sectors_rest (neighbors);
  105.  
  106.         collide_sector (cur_sector, object_radius (object), start, end);
  107.     }
  108.  
  109.     /*
  110.      * Finally, determine which sectors the object overlaps.
  111.      * If an object overlaps a sector, check to see if that sector
  112.      *  contains the center of the object. (There is only one such sector).
  113.      */
  114.     cur_sector = object_sector (object);
  115.     if (point_in_sector (cur_sector, end, object_radius (object)))
  116.     {
  117.         if (point_in_sector (cur_sector, end, NUM_ZERO))
  118.             set_object_sector (object, cur_sector);
  119.         sector_objects (cur_sector) = objects_add_object (sector_objects (cur_sector), object);
  120.         object_sectors (object) = sectors_add_sector (object_sectors (object), cur_sector);
  121.     }
  122.  
  123.     neighbors = sector_neighbors (cur_sector);
  124.     while (neighbors)
  125.     {
  126.         cur_sector = sectors_first (neighbors);
  127.         neighbors = sectors_rest (neighbors);
  128.  
  129.         if (point_in_sector (cur_sector, end, object_radius (object)))
  130.         {
  131.             if (point_in_sector (cur_sector, end, NUM_ZERO))
  132.                 set_object_sector (object, cur_sector);
  133.             sector_objects (cur_sector) = objects_add_object (sector_objects (cur_sector), object);
  134.             object_sectors (object) = sectors_add_sector (object_sectors (object), cur_sector);
  135.         }
  136.     }
  137. }
  138.  
  139. /*
  140.  * Collide an object with the given radius with a sector.
  141.  */
  142.  
  143. static void
  144. collide_sector (sector, radius, start, end)
  145.     SECTOR sector;
  146.     NUM radius;
  147.     VECTOR start, end;
  148. {
  149.     FACES faces;
  150.     FACE face;
  151.  
  152.     /*
  153.      * All we have to do is call "collide_face" for every
  154.      *  face in the sector.
  155.      */
  156.     faces = sector_faces (sector);
  157.     while (faces)
  158.     {
  159.         face = faces_first (faces);
  160.         faces = faces_rest (faces);
  161.  
  162.         collide_face (face, radius, start, end);
  163.     }
  164. }
  165.  
  166. /*
  167.  * Collide an object with the given radius with a face.
  168.  */
  169.  
  170. static void
  171. collide_face (face, radius, start, end)
  172.     FACE face;
  173.     NUM radius;
  174.     VECTOR start, end;
  175. {
  176.     POINT normal;
  177.     POINT point;
  178.     VECTOR new_normal;
  179.     VECTOR new_point;
  180.     VECTOR diff;
  181.     NUM num, denom;
  182.     NUM d, t;
  183.  
  184.     /*
  185.      * Only perform the collision if this is an obstructing face.
  186.      */
  187.     if (face_obstructs (face))
  188.     {
  189.         /*
  190.          * The "start" and "end" points define a line segment.
  191.          * What we'll do is intersect the line and the plane.
  192.          */
  193.         
  194.         normal = face_normal (face);
  195.         point = points_first (face_points (face));
  196.  
  197.         /*
  198.          * To handle the fact that an object has some radius,
  199.          *  I offset the point on the face a distance of the radius
  200.          *  out along the direction of the normal. This has the
  201.          *  effect of moving the plane defining the face out a
  202.          *  distance of the radius along the normal, which is exactly
  203.          *  what we want.
  204.          */
  205.         vector_mul (point_coord (normal), radius, new_normal);
  206.         vector_add (point_coord (point), new_normal, new_point);
  207.  
  208.         vector_sub (end, new_point, diff);
  209.         if (vector_dot (point_coord (normal), diff) > NUM_ZERO)
  210.             return;
  211.  
  212.         d = vector_dot (point_coord (normal), new_point);
  213.         vector_sub (end, start, diff);
  214.  
  215.         num = -vector_dot (point_coord (normal), start) + d;
  216.  
  217.         /*
  218.          * If "denom" is equal to 0, then the line and plane
  219.          *  are parallel and no intersection can occur.
  220.          */
  221.         denom = vector_dot (point_coord (normal), diff);
  222.         if (denom == 0)
  223.             return;
  224.  
  225.         /*
  226.          * "t" is the parameterized distance along the line
  227.          *  from the "start". If it lies between 0 and 1, then
  228.          *  then line segment intersects the plane.
  229.          */
  230.         t = my_div (num, denom);
  231.         if ((t < NUM_ZERO) || (t > NUM_ONE))
  232.             return;
  233.  
  234.         /*
  235.          * Calculate the point of intersection.
  236.          */
  237.         set_vector_x (new_point, vector_x (start) + my_mul (vector_x (diff), t));
  238.         set_vector_y (new_point, vector_y (start) + my_mul (vector_y (diff), t));
  239.         set_vector_z (new_point, vector_z (start) + my_mul (vector_z (diff), t));
  240.         set_vector_w (new_point, NUM_ONE);
  241.  
  242.         /*
  243.          * If the line segment intersects the plane, then we
  244.          *  next want to know if the point if intersection is
  245.          *  within the face.
  246.          */
  247.         if (collide_check (face, new_point, radius))
  248.         {
  249.             /*
  250.              * An collision occurred, so slide the object
  251.              *  along the face. This is a bit of hack, because
  252.              *  I make use of the fact that we're dealing with
  253.              *  a simple environment.
  254.              */
  255.             vector_sub (end, new_point, diff);
  256.             vector_copy (new_point, end);
  257.  
  258.             if (point_x (normal) == NUM_ONE)
  259.                 set_vector_z (end, vector_z (end) + vector_z (diff));
  260.             else if (point_x (normal) == -NUM_ONE)
  261.                 set_vector_z (end, vector_z (end) + vector_z (diff));
  262.             else if (point_z (normal) == NUM_ONE)
  263.                 set_vector_x (end, vector_x (end) + vector_x (diff));
  264.             else if (point_z (normal) == -NUM_ONE)
  265.                 set_vector_x (end, vector_x (end) + vector_x (diff));
  266.         }
  267.     }
  268. }
  269.  
  270. /*
  271.  * Determine if the point "v" is within the face.
  272.  * I'm not going to comment on this function except to
  273.  *  say I don't handle the true 3d case. I assume that
  274.  *  the face is 2d and aligned with the coordinate axes.
  275.  *  This simplifies the problem, to checking to see if
  276.  *  a value lies within some bounds. I have an idea of
  277.  *  how to do the true 3d check, though its a little 
  278.  *  more work.
  279.  */
  280.  
  281. static short
  282. collide_check (f, v, r)
  283.     FACE f;
  284.     VECTOR v;
  285.     NUM r;
  286. {
  287.     POINTS pts;
  288.     POINT pt;
  289.     NUM min, max;
  290.  
  291.     min = 100000000;
  292.     max = -min;
  293.     pts = face_points (f);
  294.  
  295.     if (point_x (face_normal (f)) != 0)
  296.     {
  297.         while (pts)
  298.         {
  299.             pt = points_first (pts);
  300.             pts = points_rest (pts);
  301.  
  302.             if ((point_z (pt) - r) < min)
  303.                 min = point_z (pt) - r;
  304.             if ((point_z (pt) + r) > max)
  305.                 max = point_z (pt) + r;
  306.         }
  307.  
  308.         return ((vector_z (v) >= min) && (vector_z (v) <= max));
  309.     }
  310.     else if (point_z (face_normal (f)) != 0)
  311.     {
  312.         while (pts)
  313.         {
  314.             pt = points_first (pts);
  315.             pts = points_rest (pts);
  316.  
  317.             if ((point_x (pt) - r) < min)
  318.                 min = point_x (pt) - r;
  319.             if ((point_x (pt) + r) > max)
  320.                 max = point_x (pt) + r;
  321.         }
  322.  
  323.         return ((vector_x (v) >= min) && (vector_x (v) <= max));
  324.     }
  325.     else
  326.     {
  327.         return 0;
  328.     }
  329. }
  330.  
  331. /*
  332.  * Determine if a point lies within sector, (with
  333.  *  some overlap).
  334.  */
  335.  
  336. static short
  337. point_in_sector (s, v, r)
  338.     SECTOR s;
  339.     VECTOR v;
  340.     NUM r;
  341. {
  342.     FACES faces;
  343.     FACE face;
  344.     POINT temp_point;
  345.     VECTOR temp_vector;
  346.     NUM dot;
  347.  
  348.     /*
  349.      * Simply check to see if the point lies on the
  350.      *  correct side of every face.
  351.      * The dest against "-r" allows the point to lie
  352.      *  a distance "r" outside a face and still be
  353.      *  considered to lie inside. This allows use to
  354.      *  check to whether an object overlaps a sector.
  355.      */
  356.     faces = sector_faces (s);
  357.     while (faces)
  358.     {
  359.         face = faces_first (faces);
  360.         faces = faces_rest (faces);
  361.  
  362.         temp_point = points_first (face_points (face));
  363.         vector_sub (v, point_coord (temp_point), temp_vector);
  364.  
  365.         dot = vector_dot (temp_vector, point_coord (face_normal (face)));
  366.         if (dot < -r)
  367.             return 0;
  368.     }
  369.  
  370.     return 1;
  371. }
  372.