src/model/modeloctant.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/ModelOctant.cpp $
  11  * $Revision$
  12  * $Date$
  13  * $Author$
  14  *
  15  * Routines for model octants
  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:47  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  * 3     1/06/99 2:24p Dave
  32  * Stubs and release build fixes.
  33  *
  34  * 2     10/07/98 10:53a Dave
  35  * Initial checkin.
  36  *
  37  * 1     10/07/98 10:50a Dave
  38  *
  39  * 16    4/29/98 5:01p Mike
  40  * Large overhaul in how turrets fire.
  41  *
  42  * 15    4/02/98 8:16a John
  43  * Fixed SDL_assert in model_collide with large ships
  44  *
  45  * 14    4/01/98 5:34p John
  46  * Made only the used POFs page in for a level.   Reduced some interp
  47  * arrays.    Made custom detail level work differently.
  48  *
  49  * 13    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  * 12    10/31/97 3:19p John
  56  * changed id field in face to be radius
  57  *
  58  * 11    9/10/97 11:40a John
  59  * took out unused parts of model_octant, like faces and submodels.   Made
  60  * the vertices actually be face center points.   Made the find_faces code
  61  * save the poly center as the normal_point in the face structure.
  62  *
  63  * 10    8/15/97 4:10p John
  64  * new code to use the new octrees style bsp trees
  65  *
  66  * 9     7/22/97 9:41a John
  67  * Made flat faces appear in octant list, so collision detection now
  68  * works.  Made them do smoothing if needed.
  69  *
  70  * 8     7/03/97 9:14a John
  71  * fixed incorrect octant vertices.
  72  *
  73  * 7     6/26/97 12:37p John
  74  * fixed bug with octant submodels.  disabled octant submodels correctly,
  75  * since they aren't yet implemented.
  76  *
  77  * 6     6/26/97 11:19a John
  78  * Made model face & shield collisions look only at octants it needs to.
  79  * Shield sped up 4x, faces sped up about 2x.
  80  *
  81  * 5     6/26/97 9:02a Mike
  82  * Comment out frequent mprintf().
  83  *
  84  * 4     6/25/97 6:08p John
  85  * made which_octant functions also return a pointer to the octant data.
  86  *
  87  * 3     6/25/97 5:34p John
  88  * Added functions to tell which octant a point is in.
  89  *
  90  * 2     6/25/97 5:11p John
  91  * added foundation for model octants.
  92  *
  93  * 1     6/25/97 4:07p John
  94  *
  95  * $NoKeywords: $
  96  */
  97
  98
  99 #include <math.h>
 100
 101 #define MODEL_LIB
 102
 103 #include "2d.h"
 104 #include "3d.h"
 105 #include "model.h"
 106 #include "tmapper.h"
 107 #include "floating.h"
 108 #include "fvi.h"
 109 #include "lighting.h"
 110 #include "modelsinc.h"
 111
 112
 113 // returns 1 if a point is in an octant.
 114 int point_in_octant( polymodel * pm, model_octant * oct, vector *vert )
 115 {
 116         if ( vert->xyz.x < oct->min.xyz.x ) return 0;
 117         if ( vert->xyz.x > oct->max.xyz.x ) return 0;
 118
 119         if ( vert->xyz.y < oct->min.xyz.y ) return 0;
 120         if ( vert->xyz.y > oct->max.xyz.y ) return 0;
 121
 122         if ( vert->xyz.z< oct->min.xyz.z) return 0;
 123         if ( vert->xyz.z> oct->max.xyz.z) return 0;
 124
 125         return 1;
 126 }
 127
 128
 129 void model_octant_find_shields( polymodel * pm, model_octant * oct )
 130 {
 131         int i, j, n;
 132         shield_tri *tri;
 133
 134         n = 0;
 135
 136         //      Scan all the triangles in the mesh to find how many tris there are.
 137         for (i=0; i<pm->shield.ntris; i++ )     {
 138
 139                 tri = &pm->shield.tris[i];
 140
 141                 for (j=0; j<3; j++ )    {
 142                         if ( point_in_octant( pm, oct, &pm->shield.verts[tri->verts[j]].pos ))  {
 143                                 n++;
 144                                 break;
 145                         }
 146                 }
 147         }
 148
 149         //mprintf(( "Octant has %d shield polys in it\n", n ));
 150
 151         oct->nshield_tris = n;
 152         oct->shield_tris = (shield_tri **)malloc( sizeof(shield_tri *) * oct->nshield_tris );
 153         SDL_assert(oct->shield_tris!=NULL);
 154
 155         n = 0;
 156
 157         //      Rescan all the triangles in the mesh.
 158         for (i=0; i<pm->shield.ntris; i++ )     {
 159
 160                 tri = &pm->shield.tris[i];
 161
 162                 for (j=0; j<3; j++ )    {
 163                         if ( point_in_octant( pm, oct, &pm->shield.verts[tri->verts[j]].pos ))  {
 164                                 oct->shield_tris[n++] = tri;
 165                                 break;
 166                         }
 167                 }
 168         }
 169
 170         SDL_assert( oct->nshield_tris == n );
 171 }
 172
 173
 174
 175 void moff_defpoints(ubyte * p)
 176 {
 177         int n;
 178         int nverts = w(p+8);
 179         int offset = w(p+16);
 180
 181         ubyte * normcount = p+20;
 182         vector *src = vp(p+offset);
 183
 184         SDL_assert( nverts < MAX_POLYGON_VECS );
 185         // SDL_assert( nnorms < MAX_POLYGON_NORMS );
 186
 187         for (n=0; n<nverts; n++ )       {
 188
 189                 Interp_verts[n] = src;
 190
 191                 src += normcount[n]+1;
 192         }
 193 }
 194
 195
 196
 197 // Textured Poly
 198 // +0      int         id
 199 // +4      int         size
 200 // +8      vector      normal
 201 // +20     vector      center
 202 // +32     float      radius
 203 // +36     int         nverts
 204 // +40     int         tmap_num
 205 // +44     nverts*(model_tmap_vert) vertlist (n,u,v)
 206 void moff_tmappoly(ubyte * p, polymodel * pm, model_octant * oct, int just_count )
 207 {
 208         int i, nv;
 209         model_tmap_vert *verts;
 210
 211         nv = w(p+36);
 212         if ( nv < 0 ) return;
 213
 214         verts = (model_tmap_vert *)(p+44);
 215
 216         if ( pm->version < 2003 )       {
 217                 // Set the "normal_point" part of field to be the center of the polygon
 218                 vector center_point;
 219                 vm_vec_zero( &center_point );
 220
 221                 for (i=0;i<nv;i++)      {
 222                         vm_vec_add2( &center_point, Interp_verts[verts[i].vertnum] );
 223                 }
 224
 225                 center_point.xyz.x /= nv;
 226                 center_point.xyz.y /= nv;
 227                 center_point.xyz.z /= nv;
 228
 229                 *vp(p+20) = center_point;
 230
 231                 float rad = 0.0f;
 232
 233                 for (i=0;i<nv;i++)      {
 234                         float dist = vm_vec_dist( &center_point, Interp_verts[verts[i].vertnum] );
 235                         if ( dist > rad )       {
 236                                 rad = dist;
 237                         }
 238                 }
 239                 fl(p+32) = rad;
 240         }
 241
 242         // Put each face into a particular octant
 243         if ( point_in_octant( pm, oct, vp(p+20) ) )     {
 244                 if (just_count)
 245                         oct->nverts++;
 246                 else
 247                         oct->verts[oct->nverts++] = vp(p+20);
 248                 return;
 249         }
 250 }
 251
 252
 253 // Flat Poly
 254 // +0      int         id
 255 // +4      int         size
 256 // +8      vector      normal
 257 // +20     vector      center
 258 // +32     float       radius
 259 // +36     int         nverts
 260 // +40     byte        red
 261 // +41     byte        green
 262 // +42     byte        blue
 263 // +43     byte        pad
 264 // +44     nverts*int  vertlist
 265 void moff_flatpoly(ubyte * p, polymodel * pm, model_octant * oct, int just_count )
 266 {
 267         int i, nv;
 268         short *verts;
 269
 270         nv = w(p+36);
 271         if ( nv < 0 ) return;
 272
 273         verts = (short *)(p+44);
 274
 275         if ( pm->version < 2003 )       {
 276                 // Set the "normal_point" part of field to be the center of the polygon
 277                 vector center_point;
 278                 vm_vec_zero( &center_point );
 279
 280                 for (i=0;i<nv;i++)      {
 281                         vm_vec_add2( &center_point, Interp_verts[verts[i*2]] );
 282                 }
 283
 284                 center_point.xyz.x /= nv;
 285                 center_point.xyz.y /= nv;
 286                 center_point.xyz.z /= nv;
 287
 288                 *vp(p+20) = center_point;
 289
 290                 float rad = 0.0f;
 291
 292                 for (i=0;i<nv;i++)      {
 293                         float dist = vm_vec_dist( &center_point, Interp_verts[verts[i*2]] );
 294                         if ( dist > rad )       {
 295                                 rad = dist;
 296                         }
 297                 }
 298                 fl(p+32) = rad;
 299         }
 300
 301         // Put each face's center point into a particular octant
 302         if ( point_in_octant( pm, oct, vp(p+20) ) )     {
 303                 if (just_count)
 304                         oct->nverts++;
 305                 else
 306                         oct->verts[oct->nverts++] = vp(p+20);
 307         }
 308 }
 309
 310
 311
 312 int model_octant_find_faces_sub(polymodel * pm, model_octant * oct, void *model_ptr, int just_count )
 313 {
 314         ubyte *p = (ubyte *)model_ptr;
 315         int chunk_type, chunk_size;
 316
 317         chunk_type = w(p);
 318         chunk_size = w(p+4);
 319
 320         while (chunk_type != OP_EOF)    {
 321
 322                 switch (chunk_type) {
 323                 case OP_EOF:                    return 1;
 324                 case OP_DEFPOINTS:
 325                         moff_defpoints(p);
 326                         break;
 327                 case OP_FLATPOLY:               moff_flatpoly(p, pm, oct, just_count ); break;
 328                 case OP_TMAPPOLY:               moff_tmappoly(p, pm, oct, just_count ); break;
 329                 case OP_SORTNORM:               {
 330                                 int frontlist = w(p+36);
 331                                 int backlist = w(p+40);
 332                                 int prelist = w(p+44);
 333                                 int postlist = w(p+48);
 334                                 int onlist = w(p+52);
 335
 336                                 if (prelist) model_octant_find_faces_sub(pm,oct,p+prelist,just_count);
 337                                 if (backlist) model_octant_find_faces_sub(pm,oct,p+backlist,just_count);
 338                                 if (onlist) model_octant_find_faces_sub(pm,oct,p+onlist,just_count);
 339                                 if (frontlist) model_octant_find_faces_sub(pm,oct,p+frontlist,just_count);
 340                                 if (postlist) model_octant_find_faces_sub(pm,oct,p+postlist,just_count);
 341                         }
 342                         break;
 343                 case OP_BOUNDBOX:               break;
 344                 default:
 345                         mprintf(( "Bad chunk type %d, len=%d in model_octant_find_faces_sub\n", chunk_type, chunk_size ));
 346                         Int3();         // Bad chunk type!
 347                         return 0;
 348                 }
 349                 p += chunk_size;
 350                 chunk_type = w(p);
 351                 chunk_size = w(p+4);
 352         }
 353         return 1;
 354 }
 355
 356
 357 void model_octant_find_faces( polymodel * pm, model_octant * oct )
 358 {
 359         ubyte *p;
 360         int submodel_num = pm->detail[0];
 361
 362         p = pm->submodel[submodel_num].bsp_data;
 363
 364         oct->nverts = 0;
 365         model_octant_find_faces_sub(pm, oct, p, 1 );
 366
 367         if ( oct->nverts < 1 ) {
 368                 oct->nverts = 0;
 369                 oct->verts = NULL;
 370                 return;
 371         }
 372
 373         oct->verts = (vector **)malloc( sizeof(vector *) * oct->nverts );
 374         SDL_assert(oct->verts!=NULL);
 375
 376         oct->nverts = 0;
 377         model_octant_find_faces_sub(pm, oct, p, 0 );
 378
 379 //      mprintf(( "Octant has %d faces\n", oct->nfaces ));
 380 }
 381
 382
 383 // Creates the octants for a given polygon model
 384 void model_octant_create( polymodel * pm )
 385 {
 386         vector min, max, center;
 387         int i, x, y, z;
 388
 389         min = pm->mins;
 390         max = pm->maxs;
 391
 392         vm_vec_avg( &center, &min, &max );
 393
 394         for (i=0; i<8; i++ )    {
 395                 x = i & 4;
 396                 y = i & 2;
 397                 z = i & 1;
 398
 399                 if ( x )        {
 400                         pm->octants[i].max.xyz.x = max.xyz.x;
 401                         pm->octants[i].min.xyz.x = center.xyz.x;
 402                 } else {
 403                         pm->octants[i].max.xyz.x = center.xyz.x;
 404                         pm->octants[i].min.xyz.x = min.xyz.x;
 405                 }
 406
 407                 if ( y )        {
 408                         pm->octants[i].max.xyz.y = max.xyz.y;
 409                         pm->octants[i].min.xyz.y = center.xyz.y;
 410                 } else {
 411                         pm->octants[i].max.xyz.y = center.xyz.y;
 412                         pm->octants[i].min.xyz.y = min.xyz.y;
 413                 }
 414
 415                 if ( z )        {
 416                         pm->octants[i].max.xyz.z = max.xyz.z;
 417                         pm->octants[i].min.xyz.z = center.xyz.z;
 418                 } else {
 419                         pm->octants[i].max.xyz.z = center.xyz.z;
 420                         pm->octants[i].min.xyz.z = min.xyz.z;
 421                 }
 422
 423                 model_octant_find_shields( pm, &pm->octants[i] );
 424                 model_octant_find_faces( pm, &pm->octants[i] );
 425
 426         }
 427
 428 }
 429
 430
 431 // frees the memory the octants use for a given polygon model
 432 void model_octant_free( polymodel * pm )
 433 {
 434         int i;
 435
 436         for (i=0; i<8; i++ )    {
 437                 model_octant * oct = &pm->octants[i];
 438
 439                 if ( oct->verts )       {
 440                         free(oct->verts);
 441                         oct->verts = NULL;
 442                 }
 443
 444                 if ( oct->shield_tris ) {
 445                         free( oct->shield_tris );
 446                         oct->shield_tris = NULL;
 447                 }
 448
 449         }
 450 }
 451
 452
 453 // Returns which octant point pnt is closet to. This will always return
 454 // a valid octant (0-7) since the point doesn't have to be in an octant.
 455 // If model_orient and/or model_pos are NULL, pnt is assumed to already
 456 // be rotated into the model's local coordinates.
 457 // If oct is not null, it will be filled in with a pointer to the octant
 458 // data.
 459 int model_which_octant_distant_many( vector *pnt, int model_num,matrix *model_orient, vector * model_pos, polymodel **pm, int *octs)
 460 {
 461         vector tempv, rotpnt;
 462
 463         *pm = model_get(model_num);
 464
 465         if ( model_orient && model_pos )        {
 466                 // First, rotate pnt into the model's frame of reference.
 467                 vm_vec_sub( &tempv, pnt, model_pos );
 468                 vm_vec_rotate( &rotpnt, &tempv, model_orient );
 469         } else {
 470                 rotpnt = *pnt;
 471         }
 472
 473         vector center;
 474         vm_vec_avg( &center, &((*pm)->mins), &((*pm)->maxs ));
 475         int i, x, y, z;
 476
 477         if ( rotpnt.xyz.x > center.xyz.x ) x = 1; else x = 0;
 478         if ( rotpnt.xyz.y > center.xyz.y ) y = 1; else y = 0;
 479         if ( rotpnt.xyz.z > center.xyz.z ) z = 1; else z = 0;
 480
 481         i = ( (x<<2) | (y<<1) | z );
 482
 483         octs[0] = i;
 484         octs[1] = i ^ 4;        //      Adjacent octant in x dimension
 485         octs[2] = i ^ 2;        //      Adjacent octant in y dimension
 486         octs[3] = i ^ 1;        //      Adjacent octant in z dimension
 487
 488         return i;
 489 }
 490
 491
 492 // Returns which octant point pnt is closet to. This will always return
 493 // a valid octant (0-7) since the point doesn't have to be in an octant.
 494 // If model_orient and/or model_pos are NULL, pnt is assumed to already
 495 // be rotated into the model's local coordinates.
 496 // If oct is not null, it will be filled in with a pointer to the octant
 497 // data.
 498 int model_which_octant_distant( vector *pnt, int model_num,matrix *model_orient, vector * model_pos, model_octant **oct )
 499 {
 500         polymodel * pm;
 501         vector tempv, rotpnt;
 502
 503         pm = model_get(model_num);
 504
 505         if ( model_orient && model_pos )        {
 506                 // First, rotate pnt into the model's frame of reference.
 507                 vm_vec_sub( &tempv, pnt, model_pos );
 508                 vm_vec_rotate( &rotpnt, &tempv, model_orient );
 509         } else {
 510                 rotpnt = *pnt;
 511         }
 512
 513         vector center;
 514         vm_vec_avg( &center, &pm->mins, &pm->maxs );
 515         int i, x, y, z;
 516
 517         if ( rotpnt.xyz.x > center.xyz.x ) x = 1; else x = 0;
 518         if ( rotpnt.xyz.y > center.xyz.y ) y = 1; else y = 0;
 519         if ( rotpnt.xyz.z > center.xyz.z ) z = 1; else z = 0;
 520
 521         i = ( (x<<2) | (y<<1) | z );
 522
 523         if ( oct )
 524                 *oct = &pm->octants[i];
 525
 526         return i;
 527 }
 528
 529
 530
 531 // Returns which octant point pnt is in. This might return
 532 // -1 if the point isn't in any octant.
 533 // If model_orient and/or model_pos are NULL, pnt is assumed to already
 534 // be rotated into the model's local coordinates.
 535 // If oct is not null, it will be filled in with a pointer to the octant
 536 // data.  Or NULL if the pnt isn't in the octant.
 537 int model_which_octant( vector *pnt, int model_num,matrix *model_orient, vector * model_pos, model_octant **oct )
 538 {
 539         polymodel * pm;
 540         vector tempv, rotpnt;
 541
 542         pm = model_get(model_num);
 543
 544         if ( model_orient && model_pos )        {
 545                 // First, rotate pnt into the model's frame of reference.
 546                 vm_vec_sub( &tempv, pnt, model_pos );
 547                 vm_vec_rotate( &rotpnt, &tempv, model_orient );
 548         } else {
 549                 rotpnt = *pnt;
 550         }
 551
 552         vector center;
 553         vm_vec_avg( &center, &pm->mins, &pm->maxs );
 554         int i, x, y, z;
 555
 556         if ( rotpnt.xyz.x > center.xyz.x ) x = 1; else x = 0;
 557         if ( rotpnt.xyz.y > center.xyz.y ) y = 1; else y = 0;
 558         if ( rotpnt.xyz.z > center.xyz.z ) z = 1; else z = 0;
 559
 560         i =  (x<<2) | (y<<1) | z;
 561
 562         if ( point_in_octant( pm, &pm->octants[i], &rotpnt ) )  {
 563                 if ( oct )
 564                         *oct = &pm->octants[i];
 565                 return i;
 566         }
 567
 568         if ( oct )
 569                 *oct = NULL;
 570
 571         return -1;
 572 }
 573