src/model/modelcollide.cpp

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