neo/tools/compilers/aas/AASBuild_merge.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 idAASBuild::AllGapsLeadToOtherNode
  37 ============
  38 */
  39 bool idAASBuild::AllGapsLeadToOtherNode( idBrushBSPNode *nodeWithGaps, idBrushBSPNode *otherNode ) {
  40         int s;
  41         idBrushBSPPortal *p;
  42
  43         for ( p = nodeWithGaps->GetPortals(); p; p = p->Next(s) ) {
  44                 s = (p->GetNode(1) == nodeWithGaps);
  45
  46                 if ( !PortalIsGap( p, s ) ) {
  47                         continue;
  48                 }
  49
  50                 if ( p->GetNode(!s) != otherNode ) {
  51                         return false;
  52                 }
  53         }
  54         return true;
  55 }
  56
  57 /*
  58 ============
  59 idAASBuild::MergeWithAdjacentLeafNodes
  60 ============
  61 */
  62 bool idAASBuild::MergeWithAdjacentLeafNodes( idBrushBSP &bsp, idBrushBSPNode *node ) {
  63         int s, numMerges = 0, otherNodeFlags;
  64         idBrushBSPPortal *p;
  65
  66         do {
  67                 for ( p = node->GetPortals(); p; p = p->Next(s) ) {
  68                         s = (p->GetNode(1) == node);
  69
  70                         // both leaf nodes must have the same contents
  71                         if ( node->GetContents() != p->GetNode(!s)->GetContents() ) {
  72                                 continue;
  73                         }
  74
  75                         // cannot merge leaf nodes if one is near a ledge and the other is not
  76                         if ( (node->GetFlags() & AREA_LEDGE) != (p->GetNode(!s)->GetFlags() & AREA_LEDGE) ) {
  77                                 continue;
  78                         }
  79
  80                         // cannot merge leaf nodes if one has a floor portal and the other a gap portal
  81                         if ( node->GetFlags() & AREA_FLOOR ) {
  82                                 if ( p->GetNode(!s)->GetFlags() & AREA_GAP ) {
  83                                         if ( !AllGapsLeadToOtherNode( p->GetNode(!s), node ) ) {
  84                                                 continue;
  85                                         }
  86                                 }
  87                         }
  88                         else if ( node->GetFlags() & AREA_GAP ) {
  89                                 if ( p->GetNode(!s)->GetFlags() & AREA_FLOOR ) {
  90                                         if ( !AllGapsLeadToOtherNode( node, p->GetNode(!s) ) ) {
  91                                                 continue;
  92                                         }
  93                                 }
  94                         }
  95
  96                         otherNodeFlags = p->GetNode(!s)->GetFlags();
  97
  98                         // try to merge the leaf nodes
  99                         if ( bsp.TryMergeLeafNodes( p, s ) ) {
 100                                 node->SetFlag( otherNodeFlags );
 101                                 if ( node->GetFlags() & AREA_FLOOR ) {
 102                                         node->RemoveFlag( AREA_GAP );
 103                                 }
 104                                 numMerges++;
 105                                 DisplayRealTimeString( "\r%6d", ++numMergedLeafNodes );
 106                                 break;
 107                         }
 108                 }
 109         } while( p );
 110
 111         if ( numMerges ) {
 112                 return true;
 113         }
 114         return false;
 115 }
 116
 117 /*
 118 ============
 119 idAASBuild::MergeLeafNodes_r
 120 ============
 121 */
 122 void idAASBuild::MergeLeafNodes_r( idBrushBSP &bsp, idBrushBSPNode *node ) {
 123
 124         if ( !node ) {
 125                 return;
 126         }
 127
 128         if ( node->GetContents() & AREACONTENTS_SOLID ) {
 129                 return;
 130         }
 131
 132         if ( node->GetFlags() & NODE_DONE ) {
 133                 return;
 134         }
 135
 136         if ( !node->GetChild(0) && !node->GetChild(1) ) {
 137                 MergeWithAdjacentLeafNodes( bsp, node );
 138                 node->SetFlag( NODE_DONE );
 139                 return;
 140         }
 141
 142         MergeLeafNodes_r( bsp, node->GetChild(0) );
 143         MergeLeafNodes_r( bsp, node->GetChild(1) );
 144
 145         return;
 146 }
 147
 148 /*
 149 ============
 150 idAASBuild::MergeLeafNodes
 151 ============
 152 */
 153 void idAASBuild::MergeLeafNodes( idBrushBSP &bsp ) {
 154         numMergedLeafNodes = 0;
 155
 156         common->Printf( "[Merge Leaf Nodes]\n" );
 157
 158         MergeLeafNodes_r( bsp, bsp.GetRootNode() );
 159         bsp.GetRootNode()->RemoveFlagRecurse( NODE_DONE );
 160         bsp.PruneMergedTree_r( bsp.GetRootNode() );
 161
 162         common->Printf( "\r%6d leaf nodes merged\n", numMergedLeafNodes );
 163 }