neo/tools/compilers/aas/AASFile_sample.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 #include "../../../idlib/precompiled.h"
  30 #pragma hdrstop
  31
  32 #include "AASFile.h"
  33 #include "AASFile_local.h"
  34
  35
  36 //===============================================================
  37 //
  38 //      Environment Sampling
  39 //
  40 //===============================================================
  41
  42 /*
  43 ================
  44 idAASFileLocal::EdgeCenter
  45 ================
  46 */
  47 idVec3 idAASFileLocal::EdgeCenter( int edgeNum ) const {
  48         const aasEdge_t *edge;
  49         edge = &edges[edgeNum];
  50         return ( vertices[edge->vertexNum[0]] + vertices[edge->vertexNum[1]] ) * 0.5f;
  51 }
  52
  53 /*
  54 ================
  55 idAASFileLocal::FaceCenter
  56 ================
  57 */
  58 idVec3 idAASFileLocal::FaceCenter( int faceNum ) const {
  59         int i, edgeNum;
  60         const aasFace_t *face;
  61         const aasEdge_t *edge;
  62         idVec3 center;
  63
  64         center = vec3_origin;
  65
  66         face = &faces[faceNum];
  67         if ( face->numEdges > 0 ) {
  68                 for ( i = 0; i < face->numEdges; i++ ) {
  69                         edgeNum = edgeIndex[ face->firstEdge + i ];
  70                         edge = &edges[ abs( edgeNum ) ];
  71                         center += vertices[ edge->vertexNum[ INTSIGNBITSET(edgeNum) ] ];
  72                 }
  73                 center /= face->numEdges;
  74         }
  75         return center;
  76 }
  77
  78 /*
  79 ================
  80 idAASFileLocal::AreaCenter
  81 ================
  82 */
  83 idVec3 idAASFileLocal::AreaCenter( int areaNum ) const {
  84         int i, faceNum;
  85         const aasArea_t *area;
  86         idVec3 center;
  87
  88         center = vec3_origin;
  89
  90         area = &areas[areaNum];
  91         if ( area->numFaces > 0 ) {
  92                 for ( i = 0; i < area->numFaces; i++ ) {
  93                         faceNum = faceIndex[area->firstFace + i];
  94                         center += FaceCenter( abs(faceNum) );
  95                 }
  96                 center /= area->numFaces;
  97         }
  98         return center;
  99 }
 100
 101 /*
 102 ============
 103 idAASFileLocal::AreaReachableGoal
 104 ============
 105 */
 106 idVec3 idAASFileLocal::AreaReachableGoal( int areaNum ) const {
 107         int i, faceNum, numFaces;
 108         const aasArea_t *area;
 109         idVec3 center;
 110         idVec3 start, end;
 111         aasTrace_t trace;
 112
 113         area = &areas[areaNum];
 114
 115         if ( !(area->flags & (AREA_REACHABLE_WALK|AREA_REACHABLE_FLY)) || (area->flags & AREA_LIQUID) ) {
 116                 return AreaCenter( areaNum );
 117         }
 118
 119         center = vec3_origin;
 120
 121         numFaces = 0;
 122         for ( i = 0; i < area->numFaces; i++ ) {
 123                 faceNum = faceIndex[area->firstFace + i];
 124                 if ( !(faces[abs(faceNum)].flags & FACE_FLOOR) ) {
 125                         continue;
 126                 }
 127                 center += FaceCenter( abs(faceNum) );
 128                 numFaces++;
 129         }
 130         if ( numFaces > 0 ) {
 131                 center /= numFaces;
 132         }
 133         center[2] += 1.0f;
 134         end = center;
 135         end[2] -= 1024;
 136         Trace( trace, center, end );
 137
 138         return trace.endpos;
 139 }
 140
 141 /*
 142 ================
 143 idAASFileLocal::EdgeBounds
 144 ================
 145 */
 146 idBounds idAASFileLocal::EdgeBounds( int edgeNum ) const {
 147         const aasEdge_t *edge;
 148         idBounds bounds;
 149
 150         edge = &edges[ abs( edgeNum ) ];
 151         bounds[0] = bounds[1] = vertices[ edge->vertexNum[0] ];
 152         bounds += vertices[ edge->vertexNum[1] ];
 153         return bounds;
 154 }
 155
 156 /*
 157 ================
 158 idAASFileLocal::FaceBounds
 159 ================
 160 */
 161 idBounds idAASFileLocal::FaceBounds( int faceNum ) const {
 162         int i, edgeNum;
 163         const aasFace_t *face;
 164         const aasEdge_t *edge;
 165         idBounds bounds;
 166
 167         face = &faces[faceNum];
 168         bounds.Clear();
 169
 170         for ( i = 0; i < face->numEdges; i++ ) {
 171                 edgeNum = edgeIndex[ face->firstEdge + i ];
 172                 edge = &edges[ abs( edgeNum ) ];
 173                 bounds.AddPoint( vertices[ edge->vertexNum[ INTSIGNBITSET(edgeNum) ] ] );
 174         }
 175         return bounds;
 176 }
 177
 178 /*
 179 ================
 180 idAASFileLocal::AreaBounds
 181 ================
 182 */
 183 idBounds idAASFileLocal::AreaBounds( int areaNum ) const {
 184         int i, faceNum;
 185         const aasArea_t *area;
 186         idBounds bounds;
 187
 188         area = &areas[areaNum];
 189         bounds.Clear();
 190
 191         for ( i = 0; i < area->numFaces; i++ ) {
 192                 faceNum = faceIndex[area->firstFace + i];
 193                 bounds += FaceBounds( abs(faceNum) );
 194         }
 195         return bounds;
 196 }
 197
 198 /*
 199 ============
 200 idAASFileLocal::PointAreaNum
 201 ============
 202 */
 203 int idAASFileLocal::PointAreaNum( const idVec3 &origin ) const {
 204         int nodeNum;
 205         const aasNode_t *node;
 206
 207         nodeNum = 1;
 208         do {
 209                 node = &nodes[nodeNum];
 210                 if ( planeList[node->planeNum].Side( origin ) == PLANESIDE_BACK ) {
 211                         nodeNum = node->children[1];
 212                 }
 213                 else {
 214                         nodeNum = node->children[0];
 215                 }
 216                 if ( nodeNum < 0 ) {
 217                         return -nodeNum;
 218                 }
 219         } while( nodeNum );
 220
 221         return 0;
 222 }
 223
 224 /*
 225 ============
 226 idAASFileLocal::PointReachableAreaNum
 227 ============
 228 */
 229 int idAASFileLocal::PointReachableAreaNum( const idVec3 &origin, const idBounds &searchBounds, const int areaFlags, const int excludeTravelFlags ) const {
 230         int areaList[32], areaNum, i;
 231         idVec3 start, end, pointList[32];
 232         aasTrace_t trace;
 233         idBounds bounds;
 234         float frac;
 235
 236         start = origin;
 237
 238         trace.areas = areaList;
 239         trace.points = pointList;
 240         trace.maxAreas = sizeof( areaList ) / sizeof( int );
 241         trace.getOutOfSolid = true;
 242
 243         areaNum = PointAreaNum( start );
 244         if ( areaNum ) {
 245                 if ( ( areas[areaNum].flags & areaFlags ) && ( ( areas[areaNum].travelFlags & excludeTravelFlags ) == 0 ) ) {
 246                         return areaNum;
 247                 }
 248         }
 249         else {
 250                 // trace up
 251                 end = start;
 252                 end[2] += 32.0f;
 253                 Trace( trace, start, end );
 254                 if ( trace.numAreas >= 1 ) {
 255                         if ( ( areas[0].flags & areaFlags ) && ( ( areas[0].travelFlags & excludeTravelFlags ) == 0 ) ) {
 256                                 return areaList[0];
 257                         }
 258                         start = pointList[0];
 259                         start[2] += 1.0f;
 260                 }
 261         }
 262
 263         // trace down
 264         end = start;
 265         end[2] -= 32.0f;
 266         Trace( trace, start, end );
 267         if ( trace.lastAreaNum ) {
 268                 if ( ( areas[trace.lastAreaNum].flags & areaFlags ) && ( ( areas[trace.lastAreaNum].travelFlags & excludeTravelFlags ) == 0 ) ) {
 269                         return trace.lastAreaNum;
 270                 }
 271                 start = trace.endpos;
 272         }
 273
 274         // expand bounds until an area is found
 275         for ( i = 1; i <= 12; i++ ) {
 276                 frac = i * ( 1.0f / 12.0f );
 277                 bounds[0] = origin + searchBounds[0] * frac;
 278                 bounds[1] = origin + searchBounds[1] * frac;
 279                 areaNum = BoundsReachableAreaNum( bounds, areaFlags, excludeTravelFlags );
 280                 if ( areaNum && ( areas[areaNum].flags & areaFlags ) && ( ( areas[areaNum].travelFlags & excludeTravelFlags ) == 0 ) ) {
 281                         return areaNum;
 282                 }
 283         }
 284         return 0;
 285 }
 286
 287 /*
 288 ============
 289 idAASFileLocal::BoundsReachableAreaNum_r
 290 ============
 291 */
 292 int idAASFileLocal::BoundsReachableAreaNum_r( int nodeNum, const idBounds &bounds, const int areaFlags, const int excludeTravelFlags ) const {
 293         int res;
 294         const aasNode_t *node;
 295
 296         while( nodeNum ) {
 297                 if ( nodeNum < 0 ) {
 298                         if ( ( areas[-nodeNum].flags & areaFlags ) && ( ( areas[-nodeNum].travelFlags & excludeTravelFlags ) == 0 ) ) {
 299                                 return -nodeNum;
 300                         }
 301                         return 0;
 302                 }
 303                 node = &nodes[nodeNum];
 304                 res = bounds.PlaneSide( planeList[node->planeNum] );
 305                 if ( res == PLANESIDE_BACK ) {
 306                         nodeNum = node->children[1];
 307                 }
 308                 else if ( res == PLANESIDE_FRONT ) {
 309                         nodeNum = node->children[0];
 310                 }
 311                 else {
 312                         nodeNum = BoundsReachableAreaNum_r( node->children[1], bounds, areaFlags, excludeTravelFlags );
 313                         if ( nodeNum ) {
 314                                 return nodeNum;
 315                         }
 316                         nodeNum = node->children[0];
 317                 }
 318         }
 319
 320         return 0;
 321 }
 322
 323 /*
 324 ============
 325 idAASFileLocal::BoundsReachableAreaNum
 326 ============
 327 */
 328 int idAASFileLocal::BoundsReachableAreaNum( const idBounds &bounds, const int areaFlags, const int excludeTravelFlags ) const {
 329
 330         return BoundsReachableAreaNum_r( 1, bounds, areaFlags, excludeTravelFlags );
 331 }
 332
 333 /*
 334 ============
 335 idAASFileLocal::PushPointIntoAreaNum
 336 ============
 337 */
 338 void idAASFileLocal::PushPointIntoAreaNum( int areaNum, idVec3 &point ) const {
 339         int i, faceNum;
 340         const aasArea_t *area;
 341         const aasFace_t *face;
 342
 343         area = &areas[areaNum];
 344
 345         // push the point to the right side of all area face planes
 346         for ( i = 0; i < area->numFaces; i++ ) {
 347                 faceNum = faceIndex[area->firstFace + i];
 348                 face = &faces[abs( faceNum )];
 349
 350                 const idPlane &plane = planeList[face->planeNum ^ INTSIGNBITSET( faceNum )];
 351                 float dist = plane.Distance( point );
 352
 353                 // project the point onto the face plane if it is on the wrong side
 354                 if ( dist < 0.0f ) {
 355                         point -= dist * plane.Normal();
 356                 }
 357         }
 358 }
 359
 360 /*
 361 ============
 362 idAASFileLocal::Trace
 363 ============
 364 */
 365 #define TRACEPLANE_EPSILON              0.125f
 366
 367 typedef struct aasTraceStack_s
 368 {
 369         idVec3                  start;
 370         idVec3                  end;
 371         int                             planeNum;
 372         int                             nodeNum;
 373 } aasTraceStack_t;
 374
 375 bool idAASFileLocal::Trace( aasTrace_t &trace, const idVec3 &start, const idVec3 &end ) const {
 376         int side, nodeNum, tmpPlaneNum;
 377         double front, back, frac;
 378         idVec3 cur_start, cur_end, cur_mid, v1, v2;
 379         aasTraceStack_t tracestack[MAX_AAS_TREE_DEPTH];
 380         aasTraceStack_t *tstack_p;
 381         const aasNode_t *node;
 382         const idPlane *plane;
 383
 384         trace.numAreas = 0;
 385         trace.lastAreaNum = 0;
 386         trace.blockingAreaNum = 0;
 387
 388         tstack_p = tracestack;
 389         tstack_p->start = start;
 390         tstack_p->end = end;
 391         tstack_p->planeNum = 0;
 392         tstack_p->nodeNum = 1;          //start with the root of the tree
 393         tstack_p++;
 394
 395         while( 1 ) {
 396
 397                 tstack_p--;
 398                 // if the trace stack is empty
 399                 if ( tstack_p < tracestack ) {
 400                         if ( !trace.lastAreaNum ) {
 401                                 // completely in solid
 402                                 trace.fraction = 0.0f;
 403                                 trace.endpos = start;
 404                         }
 405                         else {
 406                                 // nothing was hit
 407                                 trace.fraction = 1.0f;
 408                                 trace.endpos = end;
 409                         }
 410                         trace.planeNum = 0;
 411                         return false;
 412                 }
 413
 414                 // number of the current node to test the line against
 415                 nodeNum = tstack_p->nodeNum;
 416
 417                 // if it is an area
 418                 if ( nodeNum < 0) {
 419                         // if can't enter the area
 420                         if ( ( areas[-nodeNum].flags & trace.flags ) || ( areas[-nodeNum].travelFlags & trace.travelFlags ) ) {
 421                                 if ( !trace.lastAreaNum ) {
 422                                         trace.fraction = 0.0f;
 423                                         v1 = vec3_origin;
 424                                 } else {
 425                                         v1 = end - start;
 426                                         v2 = tstack_p->start - start;
 427                                         trace.fraction = v2.Length() / v1.Length();
 428                                 }
 429                                 trace.endpos = tstack_p->start;
 430                                 trace.blockingAreaNum = -nodeNum;
 431                                 trace.planeNum = tstack_p->planeNum;
 432                                 // always take the plane with normal facing towards the trace start
 433                                 plane = &planeList[trace.planeNum];
 434                                 if ( v1 * plane->Normal() > 0.0f ) {
 435                                         trace.planeNum ^= 1;
 436                                 }
 437                                 return true;
 438                         }
 439                         trace.lastAreaNum = -nodeNum;
 440                         if ( trace.numAreas < trace.maxAreas ) {
 441                                 if ( trace.areas ) {
 442                                         trace.areas[trace.numAreas] = -nodeNum;
 443                                 }
 444                                 if ( trace.points ) {
 445                                         trace.points[trace.numAreas] = tstack_p->start;
 446                                 }
 447                                 trace.numAreas++;
 448                         }
 449                         continue;
 450                 }
 451
 452                 // if it is a solid leaf
 453                 if ( !nodeNum ) {
 454                         if ( !trace.lastAreaNum ) {
 455                                 trace.fraction = 0.0f;
 456                                 v1 = vec3_origin;
 457                         } else {
 458                                 v1 = end - start;
 459                                 v2 = tstack_p->start - start;
 460                                 trace.fraction = v2.Length() / v1.Length();
 461                         }
 462                         trace.endpos = tstack_p->start;
 463                         trace.blockingAreaNum = 0;      // hit solid leaf
 464                         trace.planeNum = tstack_p->planeNum;
 465                         // always take the plane with normal facing towards the trace start
 466                         plane = &planeList[trace.planeNum];
 467                         if ( v1 * plane->Normal() > 0.0f ) {
 468                                 trace.planeNum ^= 1;
 469                         }
 470                         if ( !trace.lastAreaNum && trace.getOutOfSolid ) {
 471                                 continue;
 472                         }
 473                         else {
 474                                 return true;
 475                         }
 476                 }
 477
 478                 // the node to test against
 479                 node = &nodes[nodeNum];
 480                 // start point of current line to test against node
 481                 cur_start = tstack_p->start;
 482                 // end point of the current line to test against node
 483                 cur_end = tstack_p->end;
 484                 // the current node plane
 485                 plane = &planeList[node->planeNum];
 486
 487                 front = plane->Distance( cur_start );
 488                 back = plane->Distance( cur_end );
 489
 490                 // if the whole to be traced line is totally at the front of this node
 491                 // only go down the tree with the front child
 492                 if ( front >= -ON_EPSILON && back >= -ON_EPSILON ) {
 493                         // keep the current start and end point on the stack and go down the tree with the front child
 494                         tstack_p->nodeNum = node->children[0];
 495                         tstack_p++;
 496                         if ( tstack_p >= &tracestack[MAX_AAS_TREE_DEPTH] ) {
 497                                 common->Error("idAASFileLocal::Trace: stack overflow\n" );
 498                                 return false;
 499                         }
 500                 }
 501                 // if the whole to be traced line is totally at the back of this node
 502                 // only go down the tree with the back child
 503                 else if ( front < ON_EPSILON && back < ON_EPSILON ) {
 504                         // keep the current start and end point on the stack and go down the tree with the back child
 505                         tstack_p->nodeNum = node->children[1];
 506                         tstack_p++;
 507                         if ( tstack_p >= &tracestack[MAX_AAS_TREE_DEPTH] ) {
 508                                 common->Error("idAASFileLocal::Trace: stack overflow\n" );
 509                                 return false;
 510                         }
 511                 }
 512                 // go down the tree both at the front and back of the node
 513                 else {
 514                         tmpPlaneNum = tstack_p->planeNum;
 515                         // calculate the hit point with the node plane
 516                         // put the cross point TRACEPLANE_EPSILON on the near side
 517                         if (front < 0) {
 518                                 frac = (front + TRACEPLANE_EPSILON) / ( front - back );
 519                         }
 520                         else {
 521                                 frac = (front - TRACEPLANE_EPSILON) / ( front - back );
 522                         }
 523
 524                         if (frac < 0) {
 525                                 frac = 0.001f; //0
 526                         }
 527                         else if (frac > 1) {
 528                                 frac = 0.999f; //1
 529                         }
 530
 531                         cur_mid = cur_start + ( cur_end - cur_start ) * frac;
 532
 533                         // side the front part of the line is on
 534                         side = front < 0;
 535
 536                         // first put the end part of the line on the stack (back side)
 537                         tstack_p->start = cur_mid;
 538                         tstack_p->planeNum = node->planeNum;
 539                         tstack_p->nodeNum = node->children[!side];
 540                         tstack_p++;
 541                         if ( tstack_p >= &tracestack[MAX_AAS_TREE_DEPTH] ) {
 542                                 common->Error("idAASFileLocal::Trace: stack overflow\n" );
 543                                 return false;
 544                         }
 545                         // now put the part near the start of the line on the stack so we will
 546                         // continue with that part first.
 547                         tstack_p->start = cur_start;
 548                         tstack_p->end = cur_mid;
 549                         tstack_p->planeNum = tmpPlaneNum;
 550                         tstack_p->nodeNum = node->children[side];
 551                         tstack_p++;
 552                         if ( tstack_p >= &tracestack[MAX_AAS_TREE_DEPTH] ) {
 553                                 common->Error("idAASFileLocal::Trace: stack overflow\n" );
 554                                 return false;
 555                         }
 556                 }
 557         }
 558         return false;
 559 }
 560
 561 /*
 562 ============
 563 idAASLocal::AreaContentsTravelFlags
 564 ============
 565 */
 566 int idAASFileLocal::AreaContentsTravelFlags( int areaNum ) const {
 567         if ( areas[areaNum].contents & AREACONTENTS_WATER ) {
 568                 return TFL_WATER;
 569         }
 570         return TFL_AIR;
 571 }
 572
 573 /*
 574 ============
 575 idAASFileLocal::MaxTreeDepth_r
 576 ============
 577 */
 578 void idAASFileLocal::MaxTreeDepth_r( int nodeNum, int &depth, int &maxDepth ) const {
 579         const aasNode_t *node;
 580
 581         if ( nodeNum <= 0 ) {
 582                 return;
 583         }
 584
 585         depth++;
 586         if ( depth > maxDepth ) {
 587                 maxDepth = depth;
 588         }
 589
 590         node = &nodes[nodeNum];
 591         MaxTreeDepth_r( node->children[0], depth, maxDepth );
 592         MaxTreeDepth_r( node->children[1], depth, maxDepth );
 593
 594         depth--;
 595 }
 596
 597 /*
 598 ============
 599 idAASFileLocal::MaxTreeDepth
 600 ============
 601 */
 602 int idAASFileLocal::MaxTreeDepth( void ) const {
 603         int depth, maxDepth;
 604
 605         depth = maxDepth = 0;
 606         MaxTreeDepth_r( 1, depth, maxDepth );
 607         return maxDepth;
 608 }