src/model/modeloctant.cpp

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