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