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