neo/tools/compilers/aas/AASBuild_gravity.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
  35 /*
  36 ============
  37 idAASBuild::SetPortalFlags_r
  38 ============
  39 */
  40 void idAASBuild::SetPortalFlags_r( idBrushBSPNode *node ) {
  41         int s;
  42         idBrushBSPPortal *p;
  43         idVec3 normal;
  44
  45         if ( !node ) {
  46                 return;
  47         }
  48
  49         if ( node->GetContents() & AREACONTENTS_SOLID ) {
  50                 return;
  51         }
  52
  53         if ( !node->GetChild(0) && !node->GetChild(1) ) {
  54                 for ( p = node->GetPortals(); p; p = p->Next(s) ) {
  55                         s = (p->GetNode(1) == node);
  56
  57                         // if solid at the other side of the portal
  58                         if ( p->GetNode(!s)->GetContents() & AREACONTENTS_SOLID ) {
  59                                 if ( s ) {
  60                                         normal = -p->GetPlane().Normal();
  61                                 }
  62                                 else {
  63                                         normal = p->GetPlane().Normal();
  64                                 }
  65                                 if ( normal * aasSettings->invGravityDir > aasSettings->minFloorCos ) {
  66                                         p->SetFlag( FACE_FLOOR );
  67                                 }
  68                                 else {
  69                                         p->SetFlag( FACE_SOLID );
  70                                 }
  71                         }
  72                 }
  73                 return;
  74         }
  75
  76         SetPortalFlags_r( node->GetChild(0) );
  77         SetPortalFlags_r( node->GetChild(1) );
  78 }
  79
  80 /*
  81 ============
  82 idAASBuild::PortalIsGap
  83 ============
  84 */
  85 bool idAASBuild::PortalIsGap( idBrushBSPPortal *portal, int side ) {
  86         idVec3 normal;
  87
  88         // if solid at the other side of the portal
  89         if ( portal->GetNode(!side)->GetContents() & AREACONTENTS_SOLID ) {
  90                 return false;
  91         }
  92
  93         if ( side ) {
  94                 normal = -(portal->GetPlane().Normal());
  95         }
  96         else {
  97                 normal = portal->GetPlane().Normal();
  98         }
  99         if ( normal * aasSettings->invGravityDir > aasSettings->minFloorCos ) {
 100                 return true;
 101         }
 102         return false;
 103 }
 104
 105 /*
 106 ============
 107 idAASBuild::GravSubdivLeafNode
 108 ============
 109 */
 110 #define FACE_CHECKED                    BIT(31)
 111 #define GRAVSUBDIV_EPSILON              0.1f
 112
 113 void idAASBuild::GravSubdivLeafNode( idBrushBSPNode *node ) {
 114         int s1, s2, i, j, k, side1;
 115         int numSplits, numSplitters;
 116         idBrushBSPPortal *p1, *p2;
 117         idWinding *w1, *w2;
 118         idVec3 normal;
 119         idPlane plane;
 120         idPlaneSet planeList;
 121         float d, min, max;
 122         int *splitterOrder;
 123         int *bestNumSplits;
 124         int floor, gap, numFloorChecked;
 125
 126         // if this leaf node is already classified it cannot have a combination of floor and gap portals
 127         if ( node->GetFlags() & (AREA_FLOOR|AREA_GAP) ) {
 128                 return;
 129         }
 130
 131         floor = gap = 0;
 132
 133         // check if the area has a floor
 134         for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
 135                 s1 = (p1->GetNode(1) == node);
 136
 137                 if ( p1->GetFlags() & FACE_FLOOR ) {
 138                         floor++;
 139                 }
 140         }
 141
 142         // find seperating planes between gap and floor portals
 143         for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
 144                 s1 = (p1->GetNode(1) == node);
 145
 146                 // if the portal is a gap seen from this side
 147                 if ( PortalIsGap( p1, s1 ) ) {
 148                         gap++;
 149                         // if the area doesn't have a floor
 150                         if ( !floor ) {
 151                                 break;
 152                         }
 153                 }
 154                 else {
 155                         continue;
 156                 }
 157
 158                 numFloorChecked = 0;
 159
 160                 w1 = p1->GetWinding();
 161
 162                 // test all edges of the gap
 163                 for ( i = 0; i < w1->GetNumPoints(); i++ ) {
 164
 165                         // create a plane through the edge of the gap parallel to the direction of gravity
 166                         normal = (*w1)[(i+1)%w1->GetNumPoints()].ToVec3() - (*w1)[i].ToVec3();
 167                         normal = normal.Cross( aasSettings->invGravityDir );
 168                         if ( normal.Normalize() < 0.2f ) {
 169                                 continue;
 170                         }
 171                         plane.SetNormal( normal );
 172                         plane.FitThroughPoint( (*w1)[i].ToVec3() );
 173
 174                         // get the side of the plane the gap is on
 175                         side1 = w1->PlaneSide( plane, GRAVSUBDIV_EPSILON );
 176                         if ( side1 == SIDE_ON ) {
 177                                 break;
 178                         }
 179
 180                         // test if the plane through the edge of the gap seperates the gap from a floor portal
 181                         for ( p2 = node->GetPortals(); p2; p2 = p2->Next(s2) ) {
 182                                 s2 = (p2->GetNode(1) == node);
 183
 184                                 if ( !( p2->GetFlags() & FACE_FLOOR ) ) {
 185                                         continue;
 186                                 }
 187
 188                                 if ( p2->GetFlags() & FACE_CHECKED ) {
 189                                         continue;
 190                                 }
 191
 192                                 w2 = p2->GetWinding();
 193
 194                                 min = 2.0f * GRAVSUBDIV_EPSILON;
 195                                 max = GRAVSUBDIV_EPSILON;
 196                                 if ( side1 == SIDE_FRONT ) {
 197                                         for ( j = 0; j < w2->GetNumPoints(); j++ ) {
 198                                                 d = plane.Distance( (*w2)[j].ToVec3() );
 199                                                 if ( d >= GRAVSUBDIV_EPSILON ) {
 200                                                         break;  // point at the same side of the plane as the gap
 201                                                 }
 202                                                 d = idMath::Fabs( d );
 203                                                 if ( d < min ) {
 204                                                         min = d;
 205                                                 }
 206                                                 if ( d > max ) {
 207                                                         max = d;
 208                                                 }
 209                                         }
 210                                 }
 211                                 else {
 212                                         for ( j = 0; j < w2->GetNumPoints(); j++ ) {
 213                                                 d = plane.Distance( (*w2)[j].ToVec3() );
 214                                                 if ( d <= -GRAVSUBDIV_EPSILON ) {
 215                                                         break;  // point at the same side of the plane as the gap
 216                                                 }
 217                                                 d = idMath::Fabs( d );
 218                                                 if ( d < min ) {
 219                                                         min = d;
 220                                                 }
 221                                                 if ( d > max ) {
 222                                                         max = d;
 223                                                 }
 224                                         }
 225                                 }
 226
 227                                 // a point of the floor portal was found to be at the same side of the plane as the gap
 228                                 if ( j < w2->GetNumPoints() ) {
 229                                         continue;
 230                                 }
 231
 232                                 // if the floor portal touches the plane
 233                                 if ( min < GRAVSUBDIV_EPSILON && max > GRAVSUBDIV_EPSILON ) {
 234                                         planeList.FindPlane( plane, 0.00001f, 0.1f );
 235                                 }
 236
 237                                 p2->SetFlag( FACE_CHECKED );
 238                                 numFloorChecked++;
 239
 240                         }
 241                         if ( numFloorChecked == floor ) {
 242                                 break;
 243                         }
 244                 }
 245
 246                 for ( p2 = node->GetPortals(); p2; p2 = p2->Next(s2) ) {
 247                         s2 = (p2->GetNode(1) == node);
 248                         p2->RemoveFlag( FACE_CHECKED );
 249                 }
 250         }
 251
 252         // if the leaf node does not have both floor and gap portals
 253         if ( !( gap && floor) ) {
 254                 if ( floor ) {
 255                         node->SetFlag( AREA_FLOOR );
 256                 }
 257                 else if ( gap ) {
 258                         node->SetFlag( AREA_GAP );
 259                 }
 260                 return;
 261         }
 262
 263         // if no valid seperators found
 264         if ( planeList.Num() == 0 ) {
 265                 // NOTE: this should never happend, if it does the leaf node has degenerate portals
 266                 return;
 267         }
 268
 269         splitterOrder = (int *) _alloca( planeList.Num() * sizeof( int ) );
 270         bestNumSplits = (int *) _alloca( planeList.Num() * sizeof( int ) );
 271         numSplitters = 0;
 272
 273         // test all possible seperators and sort them from best to worst
 274         for ( i = 0; i < planeList.Num(); i += 2 ) {
 275                 numSplits = 0;
 276
 277                 for ( p1 = node->GetPortals(); p1; p1 = p1->Next(s1) ) {
 278                         s1 = (p1->GetNode(1) == node);
 279                         if ( p1->GetWinding()->PlaneSide( planeList[i], 0.1f ) == SIDE_CROSS ) {
 280                                 numSplits++;
 281                         }
 282                 }
 283
 284                 for ( j = 0; j < numSplitters; j++ ) {
 285                         if ( numSplits < bestNumSplits[j] ) {
 286                                 for ( k = numSplitters; k > j; k-- ) {
 287                                         bestNumSplits[k] = bestNumSplits[k-1];
 288                                         splitterOrder[k] = splitterOrder[k-1];
 289                                 }
 290                                 bestNumSplits[j] = numSplits;
 291                                 splitterOrder[j] = i;
 292                                 numSplitters++;
 293                                 break;
 294                         }
 295                 }
 296                 if ( j >= numSplitters ) {
 297                         bestNumSplits[j] = numSplits;
 298                         splitterOrder[j] = i;
 299                         numSplitters++;
 300                 }
 301         }
 302
 303         // try all seperators in order from best to worst
 304         for ( i = 0; i < numSplitters; i++ ) {
 305                 if ( node->Split( planeList[splitterOrder[i]], -1 ) ) {
 306                         // we found a seperator that works
 307                         break;
 308                 }
 309         }
 310         if ( i >= numSplitters) {
 311                 return;
 312         }
 313
 314         DisplayRealTimeString( "\r%6d", ++numGravitationalSubdivisions );
 315
 316         // test children for further splits
 317         GravSubdivLeafNode( node->GetChild(0) );
 318         GravSubdivLeafNode( node->GetChild(1) );
 319 }
 320
 321 /*
 322 ============
 323 idAASBuild::GravSubdiv_r
 324 ============
 325 */
 326 void idAASBuild::GravSubdiv_r( idBrushBSPNode *node ) {
 327
 328         if ( !node ) {
 329                 return;
 330         }
 331
 332         if ( node->GetContents() & AREACONTENTS_SOLID ) {
 333                 return;
 334         }
 335
 336         if ( !node->GetChild(0) && !node->GetChild(1) ) {
 337                 GravSubdivLeafNode( node );
 338                 return;
 339         }
 340
 341         GravSubdiv_r( node->GetChild(0) );
 342         GravSubdiv_r( node->GetChild(1) );
 343 }
 344
 345 /*
 346 ============
 347 idAASBuild::GravitationalSubdivision
 348 ============
 349 */
 350 void idAASBuild::GravitationalSubdivision( idBrushBSP &bsp ) {
 351         numGravitationalSubdivisions = 0;
 352
 353         common->Printf( "[Gravitational Subdivision]\n" );
 354
 355         SetPortalFlags_r( bsp.GetRootNode() );
 356         GravSubdiv_r( bsp.GetRootNode() );
 357
 358         common->Printf( "\r%6d subdivisions\n", numGravitationalSubdivisions );
 359 }