src/model/modelcollide.cpp

   1 /*
   2  * $Logfile: /Freespace2/code/Model/ModelCollide.cpp $
   3  * $Revision$
   4  * $Date$
   5  * $Author$
   6  *
   7  * Routines for detecting collisions of models.
   8  *
   9  * $Log$
  10  * Revision 1.2  2002/05/07 03:16:46  theoddone33
  11  * The Great Newline Fix
  12  *
  13  * Revision 1.1.1.1  2002/05/03 03:28:10  root
  14  * Initial import.
  15  *
  16  *
  17  * 5     3/08/99 7:03p Dave
  18  * First run of new object update system. Looks very promising.
  19  *
  20  * 4     1/06/99 2:24p Dave
  21  * Stubs and release build fixes.
  22  *
  23  * 3     11/19/98 11:07p Andsager
  24  * Check in of physics and collision detection of rotating submodels
  25  *
  26  * 2     10/07/98 10:53a Dave
  27  * Initial checkin.
  28  *
  29  * 1     10/07/98 10:50a Dave
  30  *
  31  * 82    4/22/98 9:43p John
  32  * Added code to allow checking of invisible faces, flagged by any texture
  33  * name with invisible in it.
  34  *
  35  * 81    4/02/98 8:16a John
  36  * Fixed Assert in model_collide with large ships
  37  *
  38  * 80    3/31/98 5:18p John
  39  * Removed demo/save/restore.  Made NDEBUG defined compile.  Removed a
  40  * bunch of debug stuff out of player file.  Made model code be able to
  41  * unload models and malloc out only however many models are needed.
  42  *
  43  *
  44  * 79    3/25/98 1:36p Andsager
  45  * comment out assert
  46  *
  47  * 78    3/18/98 3:04p Andsager
  48  * Increase collision error warning distance
  49  *
  50  * 77    3/09/98 12:08a Andsager
  51  * Remove assert
  52  *
  53  * 76    2/12/98 3:47p Hoffoss
  54  * Added MC_CHECK_RAY support in model_collide(), since Fred would be
  55  * better using rays instead of line segments for intersection tests.
  56  *
  57  * 75    2/05/98 9:21p John
  58  * Some new Direct3D code.   Added code to monitor a ton of stuff in the
  59  * game.
  60  *
  61  * 74    1/27/98 11:02a John
  62  * Added first rev of sparks.   Made all code that calls model_render call
  63  * clear_instance first.   Made debris pieces not render by default when
  64  * clear_instance is called.
  65  *
  66  * 73    1/19/98 11:30a Sandeep
  67  * Remove Int3() in sphere poly collision
  68  *
  69  * 72    1/16/98 5:30p Andsager
  70  * Added debug code for bad collisions.
  71  *
  72  * 71    1/12/98 9:21p Andsager
  73  * Modify calling procedure to fvi_sphere_plane.
  74  *
  75  * 70    12/22/97 9:17a John
  76  * added functions for Dave that check only one submodel.
  77  *
  78  * 69    12/18/97 9:26a John
  79  * put back in some critical "debug" code DaveA deleted.
  80  *
  81  * 68    12/16/97 5:25p Andsager
  82  * Get best collision info.  Comment out some debug info.
  83  *
  84  * 67    11/14/97 5:29p Andsager
  85  * Improve bounding box test for sphere:polygon.  Set higher tolerance for
  86  * collision alert.
  87  *
  88  * 66    11/12/97 11:09p Jasen
  89  * Comment out another Int3() that causes grief, but seems to do little
  90  * good.
  91  *
  92  * 65    11/12/97 12:13p Mike
  93  * Suppress disruptive, but apparently harmless, Int3().
  94  *
  95  * 64    11/05/97 5:48p Andsager
  96  * Added debug code to check_sphereline_face.  Expected radius separation
  97  * can be off by up to .003 for 1 m sphere.
  98  *
  99  * 63    10/31/97 4:01p John
 100  * added face_Radius to call to check_face
 101  *
 102  * 62    10/31/97 3:19p John
 103  * changed id field in face to be radius
 104  *
 105  * 61    10/30/97 3:41p Andsager
 106  * fixed bug in check_sphereline_face that allowed collisions at negative
 107  * times
 108  *
 109  * 60    10/28/97 4:57p John
 110  * Put Andsager's new sphereline collide code officially into the code
 111  * base and did a little restructuring.  Fixed a few little bugs with it
 112  * and added some simple bounding box elimination and did some timings.
 113  *
 114  *
 115  * 59    10/25/97 10:14a Andsager
 116  * Moved SPHERE_POLY_CHECK to ObjCollide.h
 117  *
 118  * 58    10/22/97 10:26p Andsager
 119  * modify (slightly) mc_check_shield to allow sphere-polygon collisions
 120  *
 121  * 57    10/19/97 9:32p Andsager
 122  * Using model_collide with 2nd parameter radius (default = 0)
 123  *
 124  * 56    10/17/97 2:06a Andsager
 125  * moved assert
 126  *
 127  * 55    10/17/97 1:26a Andsager
 128  * added radius to mc_info struct.  add sphere_face collisions
 129  *
 130  * 54    9/17/97 5:12p John
 131  * Restructured collision routines.  Probably broke a lot of stuff.
 132  *
 133  * 53    9/15/97 5:45p John
 134  * took out chunk stuff.
 135  * made pofview display thrusters as blue polies.
 136  *
 137  * 52    9/12/97 8:54a John
 138  * made model_collide fill in mc_info even if invalid model passed
 139  * through.
 140  *
 141  * 51    9/03/97 12:02a Andsager
 142  * implement sphere_sphere collision detection.  Use debug console
 143  * CHECK_SPHERE
 144  *
 145  * 50    8/25/97 11:27a John
 146  * took out the USE_OCTANTS define, since we want to always use them.
 147  *
 148  * 49    8/15/97 4:10p John
 149  * new code to use the new octrees style bsp trees
 150  *
 151  * 48    8/11/97 10:43a Mike
 152  * Enable octant checking by defining USE_OCTANTS
 153  *
 154  * 47    8/11/97 10:19a John
 155  * fixed a bug that was setting the wrong triangle for shield hit with new
 156  * octant stuff.
 157  *
 158  * 46    8/10/97 3:04p Lawrance
 159  * get rid of warning if USE_OCTANTS no defined
 160  *
 161  * 45    8/08/97 3:58p Mike
 162  * Shield hit system.
 163  * Shield damage handled/managed-by-AI on a quadrant basis.
 164  *
 165  * 44    8/06/97 5:40p Mike
 166  * Add hit_normal field to mc_info so we can have ships react to the
 167  * object they hit.
 168  *
 169  * 43    7/22/97 9:41a John
 170  * Made flat faces appear in octant list, so collision detection now
 171  * works.  Made them do smoothing if needed.
 172  *
 173  * 42    7/21/97 2:29p John
 174  * moved the bounding sphere check into the model collide code
 175  *
 176  *
 177  * 41    7/03/97 9:14a John
 178  * fixed incorrect octant vertices.
 179  *
 180  * 40    6/27/97 12:15p John
 181  * added support for only checking model's bounding box... made hud_target
 182  * use it.
 183  *
 184  * 39    6/26/97 11:44a John
 185  * made model_collide require that you specifically tell it to check the
 186  * model to avoid unnecessary checks.
 187  *
 188  * 38    6/26/97 11:19a John
 189  * Made model face & shield collisions look only at octants it needs to.
 190  * Shield sped up 4x, faces sped up about 2x.
 191  *
 192  * 37    6/23/97 1:42p John
 193  * updated sphere checking code
 194  *
 195  * 36    5/30/97 3:42p Mike
 196  * Shield mesh and hit system.
 197  *
 198  * 35    5/28/97 12:52p John
 199  * Added code in to check shield mesh.
 200  *
 201  * 34    4/17/97 6:06p John
 202  * New code/data for v19 of BSPGEN with smoothing and zbuffer
 203  * optimizations.
 204  *
 205  * 33    4/07/97 3:08p John
 206  * added flag to model_collide to allow collision checks with rays not
 207  * just segments.
 208  *
 209  * 32    4/07/97 10:37a John
 210  * Took out limits on number of children a submodel can have.    (So now
 211  * capital ships can have tons of children on them).
 212  *
 213  * 31    4/01/97 1:05p John
 214  * took out debug printf
 215  *
 216  * 30    4/01/97 1:03p John
 217  * Changed fvi_ray_plane to take a dir, not two points.
 218  *
 219  * 29    3/24/97 4:43p John
 220  * speed up chunked collision detection by only checking cubes the vector
 221  * goes through.
 222  *
 223  * 28    3/24/97 3:55p John
 224  * renamed fvi functions so rays and segments aren't confusing.
 225  *
 226  * 27    3/24/97 3:26p John
 227  * Cleaned up and restructured model_collide code and fvi code.  In fvi
 228  * made code that finds uvs work..  Added bm_get_pixel to BmpMan.
 229  *
 230  * 26    3/20/97 5:19p John
 231  * began adding a fast bounding box checks for collision detection.
 232  *
 233  *
 234  * 25    2/26/97 5:28p John
 235  * Fixed a bunch of chunked model bugs.  Basically they almost work better
 236  * than non-chunked objects!
 237  *
 238  * 24    2/07/97 10:45a John
 239  * Initial bare bones implementation of blowing off turrets.
 240  *
 241  * 23    2/04/97 7:37p John
 242  * Finally!!! Turret stuff working!
 243  *
 244  * 22    1/31/97 11:36a John
 245  *
 246  * 21    1/28/97 10:07a John
 247  * More turret stuff, still not working, though.
 248  *
 249  * 20    1/27/97 2:35p Adam
 250  * (John) One of the models is getting a subcall with model 10 billion or
 251  * something so I just made it return when it gets something that big.
 252  *
 253  * 19    1/27/97 10:25a Mike
 254  * Fix AVI file load error message.
 255  * Hack physics to allow weapons to pass through a destroyed shield
 256  * triangle.  Need to have something cleaner (and faster).
 257  *
 258  * 18    1/24/97 4:55p John
 259  * Started adding code for turning turrets.
 260  * Had to change POF format to 18.0
 261  *
 262  * $NoKeywords: $
 263  */
 264
 265
 266 #include <math.h>
 267
 268 #define MODEL_LIB
 269
 270 #include "2d.h"
 271 #include "3d.h"
 272 #include "model.h"
 273 #include "tmapper.h"
 274 #include "floating.h"
 275 #include "fvi.h"
 276 #include "lighting.h"
 277 #include "modelsinc.h"
 278 #include "objcollide.h"
 279
 280 #define TOL             1E-4
 281 #define DIST_TOL        1.0
 282
 283 // Some global variables that get set by model_collide and are used internally for
 284 // checking a collision rather than passing a bunch of parameters around. These are
 285 // not persistant between calls to model_collide
 286
 287 static mc_info          *Mc;                            // The mc_info passed into model_collide
 288
 289 static polymodel        *Mc_pm;                 // The polygon model we're checking
 290 static int                      Mc_submodel;    // The current submodel we're checking
 291
 292 static matrix           Mc_orient;              // A matrix to rotate a world point into the current
 293                                                                                         // submodel's frame of reference.
 294 static vector           Mc_base;                        // A point used along with Mc_orient.
 295
 296 static vector           Mc_p0;                  // The ray origin rotated into the current submodel's frame of reference
 297 static vector           Mc_p1;                  // The ray end rotated into the current submodel's frame of reference
 298 static float            Mc_mag;                 // The length of the ray
 299 static vector           Mc_direction;   // A vector from the ray's origin to it's end, in the current submodel's frame of reference
 300
 301 static vector * Mc_point_list[MAX_POLYGON_VECS];        // A pointer to the current submodel's vertex list
 302
 303 static float            Mc_edge_time;
 304
 305
 306 // Returns non-zero if vector from p0 to pdir
 307 // intersects the bounding box.
 308 // hitpos could be NULL, so don't fill it if it is.
 309 int mc_ray_boundingbox( vector *min, vector *max, vector * p0, vector *pdir, vector *hitpos )
 310 {
 311
 312         vector tmp_hitpos;
 313         if ( hitpos == NULL )   {
 314                 hitpos = &tmp_hitpos;
 315         }
 316
 317
 318         if ( Mc->flags & MC_CHECK_SPHERELINE )  {
 319
 320                 // In the case of a sphere, just increase the size of the box by the radius
 321                 // of the sphere in all directions.
 322
 323                 vector sphere_mod_min, sphere_mod_max;
 324
 325                 sphere_mod_min.x = min->x - Mc->radius;
 326                 sphere_mod_max.x = max->x + Mc->radius;
 327                 sphere_mod_min.y = min->y - Mc->radius;
 328                 sphere_mod_max.y = max->y + Mc->radius;
 329                 sphere_mod_min.z = min->z - Mc->radius;
 330                 sphere_mod_max.z = max->z + Mc->radius;
 331
 332                 return fvi_ray_boundingbox( &sphere_mod_min, &sphere_mod_max, p0, pdir, hitpos );
 333         } else {
 334                 return fvi_ray_boundingbox( min, max, p0, pdir, hitpos );
 335         }
 336 }
 337
 338
 339
 340 // -----
 341 // mc_check_face
 342 // nv -- number of vertices
 343 // verts -- actual vertices
 344 // plane_pnt -- A point on the plane.  Could probably use the first vertex.
 345 // plane_norm -- normal of the plane
 346 // uvl_list -- list of uv coords for the poly.
 347 // ntmap -- The tmap index into the model's textures array.
 348 //
 349 // detects whether or not a vector has collided with a polygon.  vector points stored in global
 350 // Mc_p0 and Mc_p1.  Results stored in global mc_info * Mc.
 351
 352 static void mc_check_face(int nv, vector **verts, vector *plane_pnt, float face_rad, vector *plane_norm, uv_pair *uvl_list, int ntmap, ubyte *poly)
 353 {
 354         vector  hit_point;
 355         float           dist;
 356         float           u, v;
 357
 358         // Check to see if poly is facing away from ray.  If so, don't bother
 359         // checking it.
 360         if (vm_vec_dot(&Mc_direction,plane_norm) > 0.0f)        {
 361                 return;
 362         }
 363
 364         // Find the intersection of this ray with the plane that the poly
 365         dist = fvi_ray_plane(NULL, plane_pnt, plane_norm, &Mc_p0, &Mc_direction, 0.0f);
 366
 367         if ( dist < 0.0f ) return; // If the ray is behind the plane there is no collision
 368         if ( !(Mc->flags & MC_CHECK_RAY) && (dist > 1.0f) ) return; // The ray isn't long enough to intersect the plane
 369
 370         // If the ray hits, but a closer intersection has already been found, return
 371         if ( Mc->num_hits && (dist >= Mc->hit_dist ) ) return;
 372
 373         // Find the hit point
 374         vm_vec_scale_add( &hit_point, &Mc_p0, &Mc_direction, dist );
 375
 376         // Check to see if the point of intersection is on the plane.  If so, this
 377         // also finds the uv's where the ray hit.
 378         if ( fvi_point_face(&hit_point, nv, verts, plane_norm, &u,&v, uvl_list ) )      {
 379                 Mc->hit_dist = dist;
 380
 381                 Mc->hit_point = hit_point;
 382                 Mc->hit_submodel = Mc_submodel;
 383
 384                 Mc->hit_normal = *plane_norm;
 385
 386                 if ( uvl_list ) {
 387                         Mc->hit_u = u;
 388                         Mc->hit_v = v;
 389                         Mc->hit_bitmap = Mc_pm->textures[ntmap];
 390                 }
 391
 392                 if(ntmap >= 0){
 393                         Mc->t_poly = poly;
 394                         Mc->f_poly = NULL;
 395                 } else {
 396                         Mc->t_poly = NULL;
 397                         Mc->f_poly = poly;
 398                 }
 399
 400 //              mprintf(( "Bing!\n" ));
 401
 402                 Mc->num_hits++;
 403         }
 404 }
 405
 406 // ----------------------------------------------------------------------------------------------------------
 407 // check face with spheres
 408 //
 409 //      inputs: nv                              =>              number of vertices
 410 //                              verts                   =>              array of vertices
 411 //                              plane_pnt       =>              center point in plane (about which radius is measured)
 412 //                              face_rad                =>              radius of face
 413 //                              plane_norm      =>              normal of face
 414 static void mc_check_sphereline_face( int nv, vector ** verts, vector * plane_pnt, float face_rad, vector * plane_norm, uv_pair * uvl_list, int ntmap, ubyte *poly)
 415 {
 416         vector  hit_point;
 417         float           u, v;
 418         float           delta_t;                        // time sphere takes to cross from one side of plane to the other
 419         float           face_t;                 // time at which face touches plane
 420                                                                         // NOTE all times are normalized so that t = 1.0 at the end of the frame
 421         int             check_face = 1;         // assume we'll check the face.
 422         int             check_edges = 1;                // assume we'll check the edges.
 423
 424         // Check to see if poly is facing away from ray.  If so, don't bother
 425         // checking it.
 426
 427         if (vm_vec_dot(&Mc_direction,plane_norm) > 0.0f)        {
 428                 return;
 429         }
 430
 431         // Find the intersection of this sphere with the plane of the poly
 432         if ( !fvi_sphere_plane( &hit_point, &Mc_p0, &Mc_direction, Mc->radius, plane_norm, plane_pnt, &face_t, &delta_t ) ) {
 433                 return;
 434         }
 435
 436         if ( face_t < 0 || face_t > 1) {
 437                 check_face = 0;         // If the ray is behind the plane there is no collision
 438         }
 439
 440         if ( !(Mc->flags & MC_CHECK_RAY) && (face_t > 1.0f) ) {
 441                 check_face = 0;         // The ray isn't long enough to intersect the plane
 442         }
 443
 444         // If the ray hits, but a closer intersection has already been found, don't check face
 445         if ( Mc->num_hits && (face_t >= Mc->hit_dist ) ) {
 446                 check_face = 0;         // The ray isn't long enough to intersect the plane
 447         }
 448
 449
 450         vector temp_sphere;
 451         vector temp_dir;
 452         float temp_dist;
 453         // DA 11/5/97  Above is used to test distance between hit_point and sphere_hit_point.
 454         // This can be as large as 0.003 on a unit sphere.  I suspect that with larger spheres,
 455         // both the relative and absolute error decrease, but this should still be checked for the
 456         // case of larger spheres (about 5-10 units).  The error also depends on the geometry of the
 457         // object we're colliding against, but I think to a lesser degree.
 458
 459         if ( check_face )       {
 460                 // Find the time of the sphere surface touches the plane
 461                 // If this is within the collision window, check to see if we hit a face
 462                 if ( fvi_point_face(&hit_point, nv, verts, plane_norm, &u, &v, uvl_list) ) {
 463
 464                         Mc->hit_dist = face_t;
 465                         Mc->hit_point = hit_point;
 466                         Mc->hit_normal = *plane_norm;
 467                         Mc->hit_submodel = Mc_submodel;
 468                         Mc->edge_hit = 0;
 469
 470                         if ( uvl_list ) {
 471                                 Mc->hit_u = u;
 472                                 Mc->hit_v = v;
 473                                 Mc->hit_bitmap = Mc_pm->textures[ntmap];
 474                         }
 475
 476                         if(ntmap >= 0){
 477                                 Mc->t_poly = poly;
 478                                 Mc->f_poly = NULL;
 479                         } else {
 480                                 Mc->t_poly = NULL;
 481                                 Mc->f_poly = poly;
 482                         }
 483
 484                         Mc->num_hits++;
 485                         check_edges = 0;
 486                         vm_vec_scale_add( &temp_sphere, &Mc_p0, &Mc_direction, Mc->hit_dist );
 487                         temp_dist = vm_vec_dist( &temp_sphere, &hit_point );
 488                         if ( (temp_dist - DIST_TOL > Mc->radius) || (temp_dist + DIST_TOL < Mc->radius) ) {
 489                                 // get Andsager
 490                                 mprintf(("Estimated radius error: Estimate %f, actual %f Mc->radius\n", temp_dist, Mc->radius));
 491                         }
 492                         vm_vec_sub( &temp_dir, &hit_point, &temp_sphere );
 493                         // Assert( vm_vec_dotprod( &temp_dir, &Mc_direction ) > 0 );
 494                 }
 495         }
 496
 497
 498         if ( check_edges ) {
 499
 500                 // Either (face_t) is out of range or we miss the face
 501                 // Check for sphere hitting edge
 502
 503                 // If checking shields, we *still* need to check edges
 504
 505                 // First check whether sphere can hit edge in allowed time range
 506                 if ( face_t > 1.0f || face_t+delta_t < 0.0f )   {
 507                         return;
 508                 }
 509
 510                 // this is where we need another test to cull checking for edges
 511                 // PUT TEST HERE
 512
 513                 // check each edge to see if we hit, find the closest edge
 514                 // Mc->hit_dist stores the best edge time of *all* faces
 515                 float sphere_time;
 516                 if ( fvi_polyedge_sphereline(&hit_point, &Mc_p0, &Mc_direction, Mc->radius, nv, verts, &sphere_time)) {
 517
 518                         Assert( sphere_time >= 0.0f );
 519                         vm_vec_scale_add( &temp_sphere, &Mc_p0, &Mc_direction, sphere_time );
 520                         temp_dist = vm_vec_dist( &temp_sphere, &hit_point );
 521                         if ( (temp_dist - DIST_TOL > Mc->radius) || (temp_dist + DIST_TOL < Mc->radius) ) {
 522                                 // get Andsager
 523                                 mprintf(("Estimated radius error: Estimate %f, actual %f Mc->radius\n", temp_dist, Mc->radius));
 524                         }
 525                         vm_vec_sub( &temp_dir, &hit_point, &temp_sphere );
 526 //                      Assert( vm_vec_dotprod( &temp_dir, &Mc_direction ) > 0 );
 527
 528                         if ( (Mc->num_hits==0) || (sphere_time < Mc->hit_dist) ) {
 529                                 // This is closer than best so far
 530                                 Mc->hit_dist = sphere_time;
 531                                 Mc->hit_point = hit_point;
 532                                 Mc->hit_submodel = Mc_submodel;
 533                                 Mc->edge_hit = 1;
 534                                 Mc->hit_bitmap = Mc_pm->textures[ntmap];
 535
 536                                 if(ntmap >= 0){
 537                                         Mc->t_poly = poly;
 538                                         Mc->f_poly = NULL;
 539                                 } else {
 540                                         Mc->t_poly = NULL;
 541                                         Mc->f_poly = poly;
 542                                 }
 543
 544                                 Mc->num_hits++;
 545
 546                         //      nprintf(("Physics", "edge sphere time: %f, normal: (%f, %f, %f) hit_point: (%f, %f, %f)\n", sphere_time,
 547                         //              Mc->hit_normal.x, Mc->hit_normal.y, Mc->hit_normal.z,
 548                         //              hit_point.x, hit_point.y, hit_point.z));
 549                         } else  {       // Not best so far
 550                                 Assert(Mc->num_hits>0);
 551                                 Mc->num_hits++;
 552                         }
 553                 }
 554         }
 555 }
 556
 557
 558 // Point list
 559 // +0      int         id
 560 // +4      int         size
 561 // +8      int         n_verts
 562 // +12     int         n_norms
 563 // +16     int         offset from start of chunk to vertex data
 564 // +20     n_verts*char    norm_counts
 565 // +offset             vertex data. Each vertex n is a point followed by norm_counts[n] normals.
 566 void model_collide_defpoints(ubyte * p)
 567 {
 568         int n;
 569         int nverts = w(p+8);
 570         int offset = w(p+16);
 571
 572         ubyte * normcount = p+20;
 573         vector *src = vp(p+offset);
 574
 575         Assert( nverts < MAX_POLYGON_VECS );
 576
 577         for (n=0; n<nverts; n++ )       {
 578
 579                 Mc_point_list[n] = src;
 580
 581                 src += normcount[n]+1;
 582         }
 583 }
 584
 585
 586 // Flat Poly
 587 // +0      int         id
 588 // +4      int         size
 589 // +8      vector      normal
 590 // +20     vector      center
 591 // +32     float       radius
 592 // +36     int         nverts
 593 // +40     byte        red
 594 // +41     byte        green
 595 // +42     byte        blue
 596 // +43     byte        pad
 597 // +44     nverts*int  vertlist
 598 void model_collide_flatpoly(ubyte * p)
 599 {
 600         int i;
 601         int nv;
 602         vector * points[TMAP_MAX_VERTS];
 603         short *verts;
 604
 605         nv = w(p+36);
 606         if ( nv < 0 ) return;
 607
 608         verts = (short *)(p+44);
 609
 610         for (i=0;i<nv;i++)      {
 611                 points[i] = Mc_point_list[verts[i*2]];
 612         }
 613
 614         if ( Mc->flags & MC_CHECK_SPHERELINE )  {
 615                 mc_check_sphereline_face(nv, points, vp(p+20), fl(p+32), vp(p+8), NULL, -1, p);
 616         } else {
 617                 mc_check_face(nv, points, vp(p+20), fl(p+32), vp(p+8), NULL, -1, p);
 618         }
 619 }
 620
 621
 622 // Textured Poly
 623 // +0      int         id
 624 // +4      int         size
 625 // +8      vector      normal
 626 // +20     vector      normal_point
 627 // +32     int         tmp = 0
 628 // +36     int         nverts
 629 // +40     int         tmap_num
 630 // +44     nverts*(model_tmap_vert) vertlist (n,u,v)
 631 void model_collide_tmappoly(ubyte * p)
 632 {
 633         int i;
 634         int nv;
 635         uv_pair uvlist[TMAP_MAX_VERTS];
 636         vector * points[TMAP_MAX_VERTS];
 637         model_tmap_vert *verts;
 638
 639         nv = w(p+36);
 640         if ( nv < 0 ) return;
 641
 642         int tmap_num = w(p+40);
 643
 644         if ( (!(Mc->flags & MC_CHECK_INVISIBLE_FACES)) && (Mc_pm->textures[tmap_num] < 0) )     {
 645                 // Don't check invisible polygons.
 646                 return;
 647         }
 648
 649         verts = (model_tmap_vert *)(p+44);
 650
 651         for (i=0;i<nv;i++)      {
 652                 points[i] = Mc_point_list[verts[i].vertnum];
 653                 uvlist[i].u = verts[i].u;
 654                 uvlist[i].v = verts[i].v;
 655         }
 656
 657         if ( Mc->flags & MC_CHECK_SPHERELINE )  {
 658                 mc_check_sphereline_face(nv, points, vp(p+20), fl(p+32), vp(p+8), uvlist, tmap_num, p);
 659         } else {
 660                 mc_check_face(nv, points, vp(p+20), fl(p+32), vp(p+8), uvlist, tmap_num, p);
 661         }
 662 }
 663
 664
 665 // Sortnorms
 666 // +0      int         id
 667 // +4      int         size
 668 // +8      vector      normal
 669 // +20     vector      center
 670 // +32     float       radius
 671 // 36     int     front offset
 672 // 40     int     back offset
 673 // 44     int     prelist offset
 674 // 48     int     postlist offset
 675 // 52     int     online offset
 676
 677 int model_collide_sub( void *model_ptr );
 678
 679 void model_collide_sortnorm(ubyte * p)
 680 {
 681         int frontlist = w(p+36);
 682         int backlist = w(p+40);
 683         int prelist = w(p+44);
 684         int postlist = w(p+48);
 685         int onlist = w(p+52);
 686
 687         if ( Mc_pm->version >= 2000 )   {
 688                 if (!mc_ray_boundingbox( vp(p+56), vp(p+68), &Mc_p0, &Mc_direction, NULL ))     {
 689                         return;
 690                 }
 691         }
 692
 693         if (prelist) model_collide_sub(p+prelist);
 694         if (backlist) model_collide_sub(p+backlist);
 695         if (onlist) model_collide_sub(p+onlist);
 696         if (frontlist) model_collide_sub(p+frontlist);
 697         if (postlist) model_collide_sub(p+postlist);
 698 }
 699
 700 //calls the object interpreter to render an object.  The object renderer
 701 //is really a seperate pipeline. returns true if drew
 702 int model_collide_sub(void *model_ptr )
 703 {
 704         ubyte *p = (ubyte *)model_ptr;
 705         int chunk_type, chunk_size;
 706
 707         chunk_type = w(p);
 708         chunk_size = w(p+4);
 709
 710         while (chunk_type != OP_EOF)    {
 711
 712 //              mprintf(( "Processing chunk type %d, len=%d\n", chunk_type, chunk_size ));
 713
 714                 switch (chunk_type) {
 715                 case OP_EOF: return 1;
 716                 case OP_DEFPOINTS:      model_collide_defpoints(p); break;
 717                 case OP_FLATPOLY:               model_collide_flatpoly(p); break;
 718                 case OP_TMAPPOLY:               model_collide_tmappoly(p); break;
 719                 case OP_SORTNORM:               model_collide_sortnorm(p); break;
 720                 case OP_BOUNDBOX:
 721                         if (!mc_ray_boundingbox( vp(p+8), vp(p+20), &Mc_p0, &Mc_direction, NULL ))      {
 722                                 return 1;
 723                         }
 724                         break;
 725                 default:
 726                         mprintf(( "Bad chunk type %d, len=%d in model_collide_sub\n", chunk_type, chunk_size ));
 727                         Int3();         // Bad chunk type!
 728                         return 0;
 729                 }
 730                 p += chunk_size;
 731                 chunk_type = w(p);
 732                 chunk_size = w(p+4);
 733         }
 734         return 1;
 735 }
 736
 737
 738
 739 // checks a vector collision against a ships shield (if it has shield points defined).
 740 void mc_check_shield()
 741 {
 742         int i, j;
 743         vector * points[3];
 744         float dist;
 745         float sphere_check_closest_shield_dist = FLT_MAX;
 746
 747         if ( Mc_pm->shield.ntris < 1 )
 748                 return;
 749
 750         int o;
 751         for (o=0; o<8; o++ )    {
 752                 model_octant * poct1 = &Mc_pm->octants[o];
 753
 754                 if (!mc_ray_boundingbox( &poct1->min, &poct1->max, &Mc_p0, &Mc_direction, NULL ))       {
 755                         continue;
 756                 }
 757
 758                 for (i = 0; i < poct1->nshield_tris; i++) {
 759                         vector hitpoint;
 760                         shield_tri      * tri;
 761                         tri = poct1->shield_tris[i];
 762
 763                         // Check to see if Mc_pmly is facing away from ray.  If so, don't bother
 764                         // checking it.
 765                         if (vm_vec_dot(&Mc_direction,&tri->norm) > 0.0f)        {
 766                                 continue;
 767                         }
 768
 769                         // get the vertices in the form the next function wants them
 770                         for (j = 0; j < 3; j++ )
 771                                 points[j] = &Mc_pm->shield.verts[tri->verts[j]].pos;
 772
 773                         if (!(Mc->flags & MC_CHECK_SPHERELINE) ) {      // Don't do this test for sphere colliding against shields
 774                                 // Find the intersection of this ray with the plane that the Mc_pmly
 775                                 // lies in
 776                                 dist = fvi_ray_plane(NULL, points[0],&tri->norm,&Mc_p0,&Mc_direction,0.0f);
 777
 778                                 if ( dist < 0.0f ) continue; // If the ray is behind the plane there is no collision
 779                                 if ( !(Mc->flags & MC_CHECK_RAY) && (dist > 1.0f) ) continue; // The ray isn't long enough to intersect the plane
 780
 781                                 // Find the hit Mc_pmint
 782                                 vm_vec_scale_add( &hitpoint, &Mc_p0, &Mc_direction, dist );
 783
 784                                 // Check to see if the Mc_pmint of intersection is on the plane.  If so, this
 785                                 // also finds the uv's where the ray hit.
 786                                 if ( fvi_point_face(&hitpoint, 3, points, &tri->norm, NULL,NULL,NULL ) )        {
 787                                         Mc->hit_dist = dist;
 788                                         Mc->shield_hit_tri = tri - Mc_pm->shield.tris;
 789                                         Mc->hit_point = hitpoint;
 790                                         Mc->hit_normal = tri->norm;
 791                                         Mc->hit_submodel = -1;
 792                                         Mc->num_hits++;
 793                                         return;         // We hit, so we're done
 794                                 }
 795                         } else {                // Sphere check against shield
 796                                                         // This needs to look at *all* shield tris and not just return after the first hit
 797
 798                                 // HACK HACK!! The 10000.0 is the face radius, I didn't know this,
 799                                 // so I'm assume 10000 would be as big as ever.
 800                                 mc_check_sphereline_face(3, points, points[0], 10000.0f, &tri->norm, NULL, 0, NULL);
 801                                 if (Mc->num_hits && Mc->hit_dist < sphere_check_closest_shield_dist) {
 802
 803                                         // same behavior whether face or edge
 804                                         // normal, edge_hit, hit_point all updated thru sphereline_face
 805                                         sphere_check_closest_shield_dist = Mc->hit_dist;
 806                                         Mc->shield_hit_tri = tri - Mc_pm->shield.tris;
 807                                         Mc->hit_submodel = -1;
 808                                         Mc->num_hits++;
 809                                 }
 810                         }
 811                 }
 812         }
 813 }
 814
 815
 816 // This function recursively checks a submodel and its children
 817 // for a collision with a vector.
 818 void mc_check_subobj( int mn )
 819 {
 820         vector tempv;
 821         vector hitpt;           // used in bounding box check
 822         bsp_info * sm;
 823         int i;
 824
 825         Assert( mn >= 0 );
 826         Assert( mn < Mc_pm->n_models );
 827
 828         if ( (mn < 0) || (mn>=Mc_pm->n_models) ) return;
 829
 830         sm = &Mc_pm->submodel[mn];
 831
 832         // Rotate the world check points into the current subobject's
 833         // frame of reference.
 834         // After this block, Mc_p0, Mc_p1, Mc_direction, and Mc_mag are correct
 835         // and relative to this subobjects' frame of reference.
 836         vm_vec_sub(&tempv, Mc->p0, &Mc_base);
 837         vm_vec_rotate(&Mc_p0, &tempv, &Mc_orient);
 838
 839         vm_vec_sub(&tempv, Mc->p1, &Mc_base);
 840         vm_vec_rotate(&Mc_p1, &tempv, &Mc_orient);
 841         vm_vec_sub(&Mc_direction, &Mc_p1, &Mc_p0);
 842
 843         // If we are checking the root submodel, then we might want
 844         // to check the shield at this point
 845         if (Mc_pm->detail[0] == mn)     {
 846
 847                 // Do a quick out on the entire bounding box of the object
 848                 if (!mc_ray_boundingbox( &Mc_pm->mins, &Mc_pm->maxs, &Mc_p0, &Mc_direction, NULL))      {
 849                         return;
 850                 }
 851
 852                 // Check shield if we're supposed to
 853                 if ((Mc->flags & MC_CHECK_SHIELD) && (Mc_pm->shield.ntris > 0 )) {
 854                 //      Mc->flags &= ~MC_CHECK_SPHERELINE;
 855                 //      mc_check_shield();
 856                 //      int ray_num_hits = Mc->num_hits;
 857                 //      Mc->num_hits = 0;
 858                 //      Mc->flags |= MC_CHECK_SPHERELINE;
 859                         mc_check_shield();
 860                 //      if ( (ray_num_hits > 0)  && (Mc->num_hits == 0))
 861                 //              Int3();
 862                         return;
 863                 }
 864
 865         }
 866
 867         if(!(Mc->flags & MC_CHECK_MODEL)) return;
 868
 869         Mc_submodel = mn;
 870
 871         // Check if the ray intersects this subobject's bounding box
 872         if (mc_ray_boundingbox(&sm->min, &sm->max, &Mc_p0, &Mc_direction, &hitpt))      {
 873
 874                 // The ray interects this bounding box, so we have to check all the
 875                 // polygons in this submodel.
 876                 if ( Mc->flags & MC_ONLY_BOUND_BOX )    {
 877                         float dist = vm_vec_dist( &Mc_p0, &hitpt );
 878
 879                         if ( dist < 0.0f ) goto NoHit; // If the ray is behind the plane there is no collision
 880                         if ( !(Mc->flags & MC_CHECK_RAY) && (dist > Mc_mag) ) goto NoHit; // The ray isn't long enough to intersect the plane
 881
 882                         // If the ray hits, but a closer intersection has already been found, return
 883                         if ( Mc->num_hits && (dist >= Mc->hit_dist ) ) goto NoHit;
 884
 885                         Mc->hit_dist = dist;
 886                         Mc->hit_point = hitpt;
 887                         Mc->hit_submodel = Mc_submodel;
 888                         Mc->hit_bitmap = -1;
 889                         Mc->num_hits++;
 890                 } else {
 891                         model_collide_sub(sm->bsp_data);
 892                 }
 893         } else {
 894                 //Int3();
 895         }
 896
 897 NoHit:
 898
 899         // If we're only checking one submodel, return
 900         if (Mc->flags & MC_SUBMODEL)    {
 901                 return;
 902         }
 903
 904
 905         // If this subobject doesn't have any children, we're done checking it.
 906         if ( sm->num_children < 1 ) return;
 907
 908         // Save instance (Mc_orient, Mc_base, Mc_point_base)
 909         matrix saved_orient = Mc_orient;
 910         vector saved_base = Mc_base;
 911
 912         // Check all of this subobject's children
 913         i = sm->first_child;
 914         while ( i>-1 )  {
 915                 bsp_info * csm = &Mc_pm->submodel[i];
 916
 917                 // Don't check it or its children if it is destroyed
 918                 if (!csm->blown_off)    {
 919                         //instance for this subobject
 920                         matrix tm;
 921
 922                         vm_vec_unrotate(&Mc_base, &csm->offset, &saved_orient );
 923                         vm_vec_add2(&Mc_base, &saved_base );
 924
 925                         vm_angles_2_matrix(&tm, &csm->angs);
 926                         vm_matrix_x_matrix(&Mc_orient, &saved_orient, &tm);
 927
 928                         mc_check_subobj( i );
 929                 }
 930
 931                 i = csm->next_sibling;
 932         }
 933
 934 }
 935
 936 MONITOR(NumFVI);
 937
 938 // See model.h for usage.   I don't want to put the
 939 // usage here because you need to see the #defines and structures
 940 // this uses while reading the help.
 941 int model_collide(mc_info * mc_info)
 942 {
 943         Mc = mc_info;
 944
 945         MONITOR_INC(NumFVI,1);
 946
 947         Mc->num_hits = 0;                               // How many collisions were found
 948         Mc->shield_hit_tri = -1;        // Assume we won't hit any shield polygons
 949         Mc->hit_bitmap = -1;
 950         Mc->edge_hit = 0;
 951
 952         if ( (Mc->flags & MC_CHECK_SHIELD) && (Mc->flags & MC_CHECK_MODEL) )    {
 953                 Error( LOCATION, "Checking both shield and model!\n" );
 954                 return 0;
 955         }
 956
 957         //Fill in some global variables that all the model collide routines need internally.
 958         Mc_pm = model_get(Mc->model_num);
 959         Mc_orient = *Mc->orient;
 960         Mc_base = *Mc->pos;
 961         Mc_mag = vm_vec_dist( Mc->p0, Mc->p1 );
 962         Mc_edge_time = FLT_MAX;
 963
 964         // DA 11/19/98 - disable this check for rotating submodels
 965         // Don't do check if for very small movement
 966 //      if (Mc_mag < 0.01f) {
 967 //              return 0;
 968 //      }
 969
 970         float model_radius;             // How big is the model we're checking against
 971         int first_submodel;             // Which submodel gets returned as hit if MC_ONLY_SPHERE specified
 972
 973         if ( (Mc->flags & MC_SUBMODEL) || (Mc->flags & MC_SUBMODEL_INSTANCE) )  {
 974                 first_submodel = Mc->submodel_num;
 975                 model_radius = Mc_pm->submodel[first_submodel].rad;
 976         } else {
 977                 first_submodel = Mc_pm->detail[0];
 978                 model_radius = Mc_pm->rad;
 979         }
 980
 981         if ( Mc->flags & MC_CHECK_SPHERELINE ) {
 982                 Assert( Mc->radius > 0.0f );
 983
 984                 // Do a quick check on the Bounding Sphere
 985                 if (fvi_segment_sphere(&Mc->hit_point_world, Mc->p0, Mc->p1, Mc->pos, model_radius+Mc->radius) )        {
 986                         if ( Mc->flags & MC_ONLY_SPHERE )       {
 987                                 Mc->hit_point = Mc->hit_point_world;
 988                                 Mc->hit_submodel = first_submodel;
 989                                 Mc->num_hits++;
 990                                 return (Mc->num_hits > 0);
 991                         }
 992                         // continue checking polygons.
 993                 } else {
 994                         return 0;
 995                 }
 996         } else {
 997                 int r;
 998
 999                 // Do a quick check on the Bounding Sphere
1000                 if ( Mc->flags & MC_CHECK_RAY ) {
1001                         r = fvi_ray_sphere(&Mc->hit_point_world, Mc->p0, Mc->p1, Mc->pos, model_radius);
1002                 } else {
1003                         r = fvi_segment_sphere(&Mc->hit_point_world, Mc->p0, Mc->p1, Mc->pos, model_radius);
1004                 }
1005                 if (r) {
1006                         if ( Mc->flags & MC_ONLY_SPHERE ) {
1007                                 Mc->hit_point = Mc->hit_point_world;
1008                                 Mc->hit_submodel = first_submodel;
1009                                 Mc->num_hits++;
1010                                 return (Mc->num_hits > 0);
1011                         }
1012                         // continue checking polygons.
1013                 } else {
1014                         return 0;
1015                 }
1016
1017         }
1018
1019         if ( Mc->flags & MC_SUBMODEL )  {
1020                 // Check only one subobject
1021                 mc_check_subobj( Mc->submodel_num );
1022                 // Check submodel and any children
1023         } else if (Mc->flags & MC_SUBMODEL_INSTANCE) {
1024                 mc_check_subobj(Mc->submodel_num);
1025         } else {
1026                 // Check all the the highest detail model polygons and subobjects for intersections
1027
1028                 // Don't check it or its children if it is destroyed
1029                 if (!Mc_pm->submodel[Mc_pm->detail[0]].blown_off)       {
1030                         mc_check_subobj( Mc_pm->detail[0] );
1031                 }
1032         }
1033
1034
1035         //If we found a hit, then rotate it into world coordinates
1036         if ( Mc->num_hits )     {
1037                 if ( Mc->flags & MC_SUBMODEL )  {
1038                         // If we're just checking one submodel, don't use normal instancing to find world points
1039                         vm_vec_unrotate(&Mc->hit_point_world, &Mc->hit_point, Mc->orient);
1040                         vm_vec_add2(&Mc->hit_point_world, Mc->pos);
1041                 } else {
1042                         model_find_world_point(&Mc->hit_point_world, &Mc->hit_point,Mc->model_num, Mc->hit_submodel, Mc->orient, Mc->pos);
1043                 }
1044         }
1045
1046         return Mc->num_hits;
1047 }
1048