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