neo/tools/compilers/aas/AASBuild_file.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 "AASBuild_local.h"
  33
  34 #define VERTEX_HASH_BOXSIZE                             (1<<6)  // must be power of 2
  35 #define VERTEX_HASH_SIZE                                (VERTEX_HASH_BOXSIZE*VERTEX_HASH_BOXSIZE)
  36 #define EDGE_HASH_SIZE                                  (1<<14)
  37
  38 #define INTEGRAL_EPSILON                                0.01f
  39 #define VERTEX_EPSILON                                  0.1f
  40
  41 #define AAS_PLANE_NORMAL_EPSILON                0.00001f
  42 #define AAS_PLANE_DIST_EPSILON                  0.01f
  43
  44
  45 idHashIndex *aas_vertexHash;
  46 idHashIndex *aas_edgeHash;
  47 idBounds aas_vertexBounds;
  48 int aas_vertexShift;
  49
  50 /*
  51 ================
  52 idAASBuild::SetupHash
  53 ================
  54 */
  55 void idAASBuild::SetupHash( void ) {
  56         aas_vertexHash = new idHashIndex( VERTEX_HASH_SIZE, 1024 );
  57         aas_edgeHash = new idHashIndex( EDGE_HASH_SIZE, 1024 );
  58 }
  59
  60 /*
  61 ================
  62 idAASBuild::ShutdownHash
  63 ================
  64 */
  65 void idAASBuild::ShutdownHash( void ) {
  66         delete aas_vertexHash;
  67         delete aas_edgeHash;
  68 }
  69
  70 /*
  71 ================
  72 idAASBuild::ClearHash
  73 ================
  74 */
  75 void idAASBuild::ClearHash( const idBounds &bounds ) {
  76         int i;
  77         float f, max;
  78
  79         aas_vertexHash->Clear();
  80         aas_edgeHash->Clear();
  81         aas_vertexBounds = bounds;
  82
  83         max = bounds[1].x - bounds[0].x;
  84         f = bounds[1].y - bounds[0].y;
  85         if ( f > max ) {
  86                 max = f;
  87         }
  88         aas_vertexShift = (float) max / VERTEX_HASH_BOXSIZE;
  89         for ( i = 0; (1<<i) < aas_vertexShift; i++ ) {
  90         }
  91         if ( i == 0 ) {
  92                 aas_vertexShift = 1;
  93         }
  94         else {
  95                 aas_vertexShift = i;
  96         }
  97 }
  98
  99 /*
 100 ================
 101 idAASBuild::HashVec
 102 ================
 103 */
 104 ID_INLINE int idAASBuild::HashVec( const idVec3 &vec ) {
 105         int x, y;
 106
 107         x = (((int) (vec[0] - aas_vertexBounds[0].x + 0.5)) + 2) >> 2;
 108         y = (((int) (vec[1] - aas_vertexBounds[0].y + 0.5)) + 2) >> 2;
 109         return (x + y * VERTEX_HASH_BOXSIZE) & (VERTEX_HASH_SIZE-1);
 110 }
 111
 112 /*
 113 ================
 114 idAASBuild::GetVertex
 115 ================
 116 */
 117 bool idAASBuild::GetVertex( const idVec3 &v, int *vertexNum ) {
 118         int i, hashKey, vn;
 119         aasVertex_t vert, *p;
 120
 121         for (i = 0; i < 3; i++) {
 122                 if ( idMath::Fabs(v[i] - idMath::Rint(v[i])) < INTEGRAL_EPSILON ) {
 123                         vert[i] = idMath::Rint(v[i]);
 124                 }
 125                 else {
 126                         vert[i] = v[i];
 127                 }
 128         }
 129
 130         hashKey = idAASBuild::HashVec( vert );
 131
 132         for ( vn = aas_vertexHash->First( hashKey ); vn >= 0; vn = aas_vertexHash->Next( vn ) ) {
 133                 p = &file->vertices[vn];
 134                 // first compare z-axis because hash is based on x-y plane
 135                 if (idMath::Fabs( vert.z - p->z ) < VERTEX_EPSILON &&
 136                         idMath::Fabs( vert.x - p->x ) < VERTEX_EPSILON &&
 137                         idMath::Fabs( vert.y - p->y ) < VERTEX_EPSILON )
 138                 {
 139                         *vertexNum = vn;
 140                         return true;
 141                 }
 142         }
 143
 144         *vertexNum = file->vertices.Num();
 145         aas_vertexHash->Add( hashKey, file->vertices.Num() );
 146         file->vertices.Append( vert );
 147
 148         return false;
 149 }
 150
 151 /*
 152 ================
 153 idAASBuild::GetEdge
 154 ================
 155 */
 156 bool idAASBuild::GetEdge( const idVec3 &v1, const idVec3 &v2, int *edgeNum, int v1num ) {
 157         int v2num, hashKey, e;
 158         int *vertexNum;
 159         aasEdge_t edge;
 160         bool found;
 161
 162         if ( v1num != -1 ) {
 163                 found = true;
 164         }
 165         else {
 166                 found = GetVertex( v1, &v1num );
 167         }
 168         found &= GetVertex( v2, &v2num );
 169         // if both vertexes are the same or snapped onto each other
 170         if ( v1num == v2num ) {
 171                 *edgeNum = 0;
 172                 return true;
 173         }
 174         hashKey = aas_edgeHash->GenerateKey( v1num, v2num );
 175         // if both vertexes where already stored
 176         if ( found ) {
 177                 for ( e = aas_edgeHash->First( hashKey ); e >= 0; e = aas_edgeHash->Next( e ) ) {
 178
 179                         vertexNum = file->edges[e].vertexNum;
 180                         if ( vertexNum[0] == v2num ) {
 181                                 if ( vertexNum[1] == v1num ) {
 182                                         // negative for a reversed edge
 183                                         *edgeNum = -e;
 184                                         break;
 185                                 }
 186                         }
 187                         else if ( vertexNum[0] == v1num ) {
 188                                 if ( vertexNum[1] == v2num ) {
 189                                         *edgeNum = e;
 190                                         break;
 191                                 }
 192                         }
 193                 }
 194                 // if edge found in hash
 195                 if ( e >= 0 ) {
 196                         return true;
 197                 }
 198         }
 199
 200         *edgeNum = file->edges.Num();
 201         aas_edgeHash->Add( hashKey, file->edges.Num() );
 202
 203         edge.vertexNum[0] = v1num;
 204         edge.vertexNum[1] = v2num;
 205
 206         file->edges.Append( edge );
 207
 208         return false;
 209 }
 210
 211 /*
 212 ================
 213 idAASBuild::GetFaceForPortal
 214 ================
 215 */
 216 bool idAASBuild::GetFaceForPortal( idBrushBSPPortal *portal, int side, int *faceNum ) {
 217         int i, j, v1num;
 218         int numFaceEdges, faceEdges[MAX_POINTS_ON_WINDING];
 219         idWinding *w;
 220         aasFace_t face;
 221
 222         if ( portal->GetFaceNum() > 0 ) {
 223                 if ( side ) {
 224                         *faceNum = -portal->GetFaceNum();
 225                 }
 226                 else {
 227                         *faceNum = portal->GetFaceNum();
 228                 }
 229                 return true;
 230         }
 231
 232         w = portal->GetWinding();
 233         // turn the winding into a sequence of edges
 234         numFaceEdges = 0;
 235         v1num = -1;             // first vertex unknown
 236         for ( i = 0; i < w->GetNumPoints(); i++ ) {
 237
 238                 GetEdge( (*w)[i].ToVec3(), (*w)[(i+1)%w->GetNumPoints()].ToVec3(), &faceEdges[numFaceEdges], v1num );
 239
 240                 if ( faceEdges[numFaceEdges] ) {
 241                         // last vertex of this edge is the first vertex of the next edge
 242                         v1num = file->edges[ abs(faceEdges[numFaceEdges]) ].vertexNum[ INTSIGNBITNOTSET(faceEdges[numFaceEdges]) ];
 243
 244                         // this edge is valid so keep it
 245                         numFaceEdges++;
 246                 }
 247         }
 248
 249         // should have at least 3 edges
 250         if ( numFaceEdges < 3 ) {
 251                 return false;
 252         }
 253
 254         // the polygon is invalid if some edge is found twice
 255         for ( i = 0; i < numFaceEdges; i++ ) {
 256                 for ( j = i+1; j < numFaceEdges; j++ ) {
 257                         if ( faceEdges[i] == faceEdges[j] || faceEdges[i] == -faceEdges[j] ) {
 258                                 return false;
 259                         }
 260                 }
 261         }
 262
 263         portal->SetFaceNum( file->faces.Num() );
 264
 265         face.planeNum = file->planeList.FindPlane( portal->GetPlane(), AAS_PLANE_NORMAL_EPSILON, AAS_PLANE_DIST_EPSILON );
 266         face.flags = portal->GetFlags();
 267         face.areas[0] = face.areas[1] = 0;
 268         face.firstEdge = file->edgeIndex.Num();
 269         face.numEdges = numFaceEdges;
 270         for ( i = 0; i < numFaceEdges; i++ ) {
 271                 file->edgeIndex.Append( faceEdges[i] );
 272         }
 273         if ( side ) {
 274                 *faceNum = -file->faces.Num();
 275         }
 276         else {
 277                 *faceNum = file->faces.Num();
 278         }
 279         file->faces.Append( face );
 280
 281         return true;
 282 }
 283
 284 /*
 285 ================
 286 idAASBuild::GetAreaForLeafNode
 287 ================
 288 */
 289 bool idAASBuild::GetAreaForLeafNode( idBrushBSPNode *node, int *areaNum ) {
 290         int s, faceNum;
 291         idBrushBSPPortal *p;
 292         aasArea_t area;
 293
 294         if ( node->GetAreaNum() ) {
 295                 *areaNum = -node->GetAreaNum();
 296                 return true;
 297         }
 298
 299         area.flags = node->GetFlags();
 300         area.cluster = area.clusterAreaNum = 0;
 301         area.contents = node->GetContents();
 302         area.firstFace = file->faceIndex.Num();
 303         area.numFaces = 0;
 304         area.reach = NULL;
 305         area.rev_reach = NULL;
 306
 307         for ( p = node->GetPortals(); p; p = p->Next(s) ) {
 308                 s = (p->GetNode(1) == node);
 309
 310                 if ( !GetFaceForPortal( p, s, &faceNum ) ) {
 311                         continue;
 312                 }
 313
 314                 file->faceIndex.Append( faceNum );
 315                 area.numFaces++;
 316
 317                 if ( faceNum > 0 ) {
 318                         file->faces[abs(faceNum)].areas[0] = file->areas.Num();
 319                 }
 320                 else {
 321                         file->faces[abs(faceNum)].areas[1] = file->areas.Num();
 322                 }
 323         }
 324
 325         if ( !area.numFaces ) {
 326                 *areaNum = 0;
 327                 return false;
 328         }
 329
 330         *areaNum = -file->areas.Num();
 331         node->SetAreaNum( file->areas.Num() );
 332         file->areas.Append( area );
 333
 334         DisplayRealTimeString( "\r%6d", file->areas.Num() );
 335
 336         return true;
 337 }
 338
 339 /*
 340 ================
 341 idAASBuild::StoreTree_r
 342 ================
 343 */
 344 int idAASBuild::StoreTree_r( idBrushBSPNode *node ) {
 345         int areaNum, nodeNum, child0, child1;
 346         aasNode_t aasNode;
 347
 348         if ( !node ) {
 349                 return 0;
 350         }
 351
 352         if ( node->GetContents() & AREACONTENTS_SOLID ) {
 353                 return 0;
 354         }
 355
 356         if ( !node->GetChild(0) && !node->GetChild(1) ) {
 357                 if ( GetAreaForLeafNode( node, &areaNum ) ) {
 358                         return areaNum;
 359                 }
 360                 return 0;
 361         }
 362
 363         aasNode.planeNum = file->planeList.FindPlane( node->GetPlane(), AAS_PLANE_NORMAL_EPSILON, AAS_PLANE_DIST_EPSILON );
 364         aasNode.children[0] = aasNode.children[1] = 0;
 365         nodeNum = file->nodes.Num();
 366         file->nodes.Append( aasNode );
 367
 368         // !@#$%^ cause of some bug we cannot set the children directly with the StoreTree_r return value
 369         child0 = StoreTree_r( node->GetChild(0) );
 370         file->nodes[nodeNum].children[0] = child0;
 371         child1 = StoreTree_r( node->GetChild(1) );
 372         file->nodes[nodeNum].children[1] = child1;
 373
 374         if ( !child0 && !child1 ) {
 375                 file->nodes.SetNum( file->nodes.Num()-1 );
 376                 return 0;
 377         }
 378
 379         return nodeNum;
 380 }
 381
 382 /*
 383 ================
 384 idAASBuild::GetSizeEstimate_r
 385 ================
 386 */
 387 typedef struct sizeEstimate_s {
 388         int                     numEdgeIndexes;
 389         int                     numFaceIndexes;
 390         int                     numAreas;
 391         int                     numNodes;
 392 } sizeEstimate_t;
 393
 394 void idAASBuild::GetSizeEstimate_r( idBrushBSPNode *parent, idBrushBSPNode *node, struct sizeEstimate_s &size ) {
 395         idBrushBSPPortal *p;
 396         int s;
 397
 398         if ( !node ) {
 399                 return;
 400         }
 401
 402         if ( node->GetContents() & AREACONTENTS_SOLID ) {
 403                 return;
 404         }
 405
 406         if ( !node->GetChild(0) && !node->GetChild(1) ) {
 407                 // multiple branches of the bsp tree might point to the same leaf node
 408                 if ( node->GetParent() == parent ) {
 409                         size.numAreas++;
 410                         for ( p = node->GetPortals(); p; p = p->Next(s) ) {
 411                                 s = (p->GetNode(1) == node);
 412                                 size.numFaceIndexes++;
 413                                 size.numEdgeIndexes += p->GetWinding()->GetNumPoints();
 414                         }
 415                 }
 416         }
 417         else {
 418                 size.numNodes++;
 419         }
 420
 421         GetSizeEstimate_r( node, node->GetChild(0), size );
 422         GetSizeEstimate_r( node, node->GetChild(1), size );
 423 }
 424
 425 /*
 426 ================
 427 idAASBuild::SetSizeEstimate
 428 ================
 429 */
 430 void idAASBuild::SetSizeEstimate( const idBrushBSP &bsp, idAASFileLocal *file ) {
 431         sizeEstimate_t size;
 432
 433         size.numEdgeIndexes = 1;
 434         size.numFaceIndexes = 1;
 435         size.numAreas = 1;
 436         size.numNodes = 1;
 437
 438         GetSizeEstimate_r( NULL, bsp.GetRootNode(), size );
 439
 440         file->planeList.Resize( size.numNodes / 2, 1024 );
 441         file->vertices.Resize( size.numEdgeIndexes / 3, 1024 );
 442         file->edges.Resize( size.numEdgeIndexes / 2, 1024 );
 443         file->edgeIndex.Resize( size.numEdgeIndexes, 4096 );
 444         file->faces.Resize( size.numFaceIndexes, 1024 );
 445         file->faceIndex.Resize( size.numFaceIndexes, 4096 );
 446         file->areas.Resize( size.numAreas, 1024 );
 447         file->nodes.Resize( size.numNodes, 1024 );
 448 }
 449
 450 /*
 451 ================
 452 idAASBuild::StoreFile
 453 ================
 454 */
 455 bool idAASBuild::StoreFile( const idBrushBSP &bsp ) {
 456         aasEdge_t edge;
 457         aasFace_t face;
 458         aasArea_t area;
 459         aasNode_t node;
 460
 461         common->Printf( "[Store AAS]\n" );
 462
 463         SetupHash();
 464         ClearHash( bsp.GetTreeBounds() );
 465
 466         file = new idAASFileLocal();
 467
 468         file->Clear();
 469
 470         SetSizeEstimate( bsp, file );
 471
 472         // the first edge is a dummy
 473         memset( &edge, 0, sizeof( edge ) );
 474         file->edges.Append( edge );
 475
 476         // the first face is a dummy
 477         memset( &face, 0, sizeof( face ) );
 478         file->faces.Append( face );
 479
 480         // the first area is a dummy
 481         memset( &area, 0, sizeof( area ) );
 482         file->areas.Append( area );
 483
 484         // the first node is a dummy
 485         memset( &node, 0, sizeof( node ) );
 486         file->nodes.Append( node );
 487
 488         // store the tree
 489         StoreTree_r( bsp.GetRootNode() );
 490
 491         // calculate area bounds and a reachable point in the area
 492         file->FinishAreas();
 493
 494         ShutdownHash();
 495
 496         common->Printf( "\r%6d areas\n", file->areas.Num() );
 497
 498         return true;
 499 }