neo/tools/compilers/aas/BrushBSP.h

   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 #ifndef __BRUSHBSP_H__
  30 #define __BRUSHBSP_H__
  31
  32 /*
  33 ===============================================================================
  34
  35         BrushBSP
  36
  37 ===============================================================================
  38 */
  39
  40 class idBrushBSP;
  41 class idBrushBSPNode;
  42 class idBrushBSPPortal;
  43
  44
  45 //===============================================================
  46 //
  47 //      idBrushBSPPortal
  48 //
  49 //===============================================================
  50
  51 class idBrushBSPPortal {
  52
  53         friend class idBrushBSP;
  54         friend class idBrushBSPNode;
  55
  56 public:
  57                                                         idBrushBSPPortal( void );
  58                                                         ~idBrushBSPPortal( void );
  59         void                                    AddToNodes( idBrushBSPNode *front, idBrushBSPNode *back );
  60         void                                    RemoveFromNode( idBrushBSPNode *l );
  61         void                                    Flip( void );
  62         int                                             Split( const idPlane &splitPlane, idBrushBSPPortal **front, idBrushBSPPortal **back );
  63         idWinding *                             GetWinding( void ) const { return winding; }
  64         const idPlane &                 GetPlane( void ) const { return plane; }
  65         void                                    SetFaceNum( int num ) { faceNum = num; }
  66         int                                             GetFaceNum( void ) const { return faceNum; }
  67         int                                             GetFlags( void ) const { return flags; }
  68         void                                    SetFlag( int flag ) { flags |= flag; }
  69         void                                    RemoveFlag( int flag ) { flags &= ~flag; }
  70         idBrushBSPPortal *              Next( int side ) const { return next[side]; }
  71         idBrushBSPNode *                GetNode( int side ) const { return nodes[side]; }
  72
  73 private:
  74         idPlane                                 plane;                  // portal plane
  75         int                                             planeNum;               // number of plane this portal is on
  76         idWinding *                             winding;                // portal winding
  77         idBrushBSPNode *                nodes[2];               // nodes this portal seperates
  78         idBrushBSPPortal *              next[2];                // next portal in list for both nodes
  79         int                                             flags;                  // portal flags
  80         int                                             faceNum;                // number of the face created for this portal
  81 };
  82
  83
  84 //===============================================================
  85 //
  86 //      idBrushBSPNode
  87 //
  88 //===============================================================
  89
  90 #define NODE_VISITED            BIT(30)
  91 #define NODE_DONE                       BIT(31)
  92
  93 class idBrushBSPNode {
  94
  95         friend class idBrushBSP;
  96         friend class idBrushBSPPortal;
  97
  98 public:
  99                                                         idBrushBSPNode( void );
 100                                                         ~idBrushBSPNode( void );
 101         void                                    SetContentsFromBrushes( void );
 102         idBounds                                GetPortalBounds( void );
 103         idBrushBSPNode *                GetChild( int index ) const { return children[index]; }
 104         idBrushBSPNode *                GetParent( void ) const { return parent; }
 105         void                                    SetContents( int contents ) { this->contents = contents; }
 106         int                                             GetContents( void ) const { return contents; }
 107         const idPlane &                 GetPlane( void ) const { return plane; }
 108         idBrushBSPPortal *              GetPortals( void ) const { return portals; }
 109         void                                    SetAreaNum( int num ) { areaNum = num; }
 110         int                                             GetAreaNum( void ) const { return areaNum; }
 111         int                                             GetFlags( void ) const { return flags; }
 112         void                                    SetFlag( int flag ) { flags |= flag; }
 113         void                                    RemoveFlag( int flag ) { flags &= ~flag; }
 114         bool                                    TestLeafNode( void );
 115                                                         // remove the flag from nodes found by flooding through portals to nodes with the flag set
 116         void                                    RemoveFlagFlood( int flag );
 117                                                         // recurse down the tree and remove the flag from all visited nodes
 118         void                                    RemoveFlagRecurse( int flag );
 119                                                         // first recurse down the tree and flood from there
 120         void                                    RemoveFlagRecurseFlood( int flag );
 121                                                         // returns side of the plane the node is on
 122         int                                             PlaneSide( const idPlane &plane, float epsilon = ON_EPSILON ) const;
 123                                                         // split the leaf node with a plane
 124         bool                                    Split( const idPlane &splitPlane, int splitPlaneNum );
 125
 126
 127 private:
 128         idPlane                                 plane;                  // split plane if this is not a leaf node
 129         idBrush *                               volume;                 // node volume
 130         int                                             contents;               // node contents
 131         idBrushList                             brushList;              // list with brushes for this node
 132         idBrushBSPNode *                parent;                 // parent of this node
 133         idBrushBSPNode *                children[2];    // both are NULL if this is a leaf node
 134         idBrushBSPPortal *              portals;                // portals of this node
 135         int                                             flags;                  // node flags
 136         int                                             areaNum;                // number of the area created for this node
 137         int                                             occupied;               // true when portal is occupied
 138 };
 139
 140
 141 //===============================================================
 142 //
 143 //      idBrushBSP
 144 //
 145 //===============================================================
 146
 147 class idBrushBSP {
 148
 149 public:
 150                                                         idBrushBSP( void );
 151                                                         ~idBrushBSP( void );
 152                                                         // build a bsp tree from a set of brushes
 153         void                                    Build( idBrushList brushList, int skipContents,
 154                                                                                         bool (*ChopAllowed)( idBrush *b1, idBrush *b2 ),
 155                                                                                                                 bool (*MergeAllowed)( idBrush *b1, idBrush *b2 ) );
 156                                                         // remove splits in subspaces with the given contents
 157         void                                    PruneTree( int contents );
 158                                                         // portalize the bsp tree
 159         void                                    Portalize( void );
 160                                                         // remove subspaces outside the map not reachable by entities
 161         bool                                    RemoveOutside( const idMapFile *mapFile, int contents, const idStrList &classNames );
 162                                                         // write file with a trace going through a leak
 163         void                                    LeakFile( const idStr &fileName );
 164                                                         // try to merge portals
 165         void                                    MergePortals( int skipContents );
 166                                                         // try to merge the two leaf nodes at either side of the portal
 167         bool                                    TryMergeLeafNodes( idBrushBSPPortal *portal, int side );
 168         void                                    PruneMergedTree_r( idBrushBSPNode *node );
 169                                                         // melt portal windings
 170         void                                    MeltPortals( int skipContents );
 171                                                         // write a map file with a brush for every leaf node that has the given contents
 172         void                                    WriteBrushMap( const idStr &fileName, const idStr &ext, int contents );
 173                                                         // bounds for the whole tree
 174         const idBounds &                GetTreeBounds( void ) const { return treeBounds; }
 175                                                         // root node of the tree
 176         idBrushBSPNode *                GetRootNode( void ) const { return root; }
 177
 178 private:
 179         idBrushBSPNode *                root;
 180         idBrushBSPNode *                outside;
 181         idBounds                                treeBounds;
 182         idPlaneSet                              portalPlanes;
 183         int                                             numGridCells;
 184         int                                             numSplits;
 185         int                                             numGridCellSplits;
 186         int                                             numPrunedSplits;
 187         int                                             numPortals;
 188         int                                             solidLeafNodes;
 189         int                                             outsideLeafNodes;
 190         int                                             insideLeafNodes;
 191         int                                             numMergedPortals;
 192         int                                             numInsertedPoints;
 193         idVec3                                  leakOrigin;
 194         int                                             brushMapContents;
 195         idBrushMap *                    brushMap;
 196
 197         bool                                    (*BrushChopAllowed)( idBrush *b1, idBrush *b2 );
 198         bool                                    (*BrushMergeAllowed)( idBrush *b1, idBrush *b2 );
 199
 200 private:
 201         void                                    RemoveMultipleLeafNodeReferences_r( idBrushBSPNode *node );
 202         void                                    Free_r( idBrushBSPNode *node );
 203         void                                    IncreaseNumSplits( void );
 204         bool                                    IsValidSplitter( const idBrushSide *side );
 205         int                                             BrushSplitterStats( const idBrush *brush, int planeNum, const idPlaneSet &planeList, bool *testedPlanes, struct splitterStats_s &stats );
 206         int                                             FindSplitter( idBrushBSPNode *node, const idPlaneSet &planeList, bool *testedPlanes, struct splitterStats_s &bestStats );
 207         void                                    SetSplitterUsed( idBrushBSPNode *node, int planeNum );
 208         idBrushBSPNode *                BuildBrushBSP_r( idBrushBSPNode *node, const idPlaneSet &planeList, bool *testedPlanes, int skipContents );
 209         idBrushBSPNode *                ProcessGridCell( idBrushBSPNode *node, int skipContents );
 210         void                                    BuildGrid_r( idList<idBrushBSPNode *> &gridCells, idBrushBSPNode *node );
 211         void                                    PruneTree_r( idBrushBSPNode *node, int contents );
 212         void                                    MakeOutsidePortals( void );
 213         idWinding *                             BaseWindingForNode( idBrushBSPNode *node );
 214         void                                    MakeNodePortal( idBrushBSPNode *node );
 215         void                                    SplitNodePortals( idBrushBSPNode *node );
 216         void                                    MakeTreePortals_r( idBrushBSPNode *node );
 217         void                                    FloodThroughPortals_r( idBrushBSPNode *node, int contents, int depth );
 218         bool                                    FloodFromOrigin( const idVec3 &origin, int contents );
 219         bool                                    FloodFromEntities( const idMapFile *mapFile, int contents, const idStrList &classNames );
 220         void                                    RemoveOutside_r( idBrushBSPNode *node, int contents );
 221         void                                    SetPortalPlanes_r( idBrushBSPNode *node, idPlaneSet &planeList );
 222         void                                    SetPortalPlanes( void );
 223         void                                    MergePortals_r( idBrushBSPNode *node, int skipContents );
 224         void                                    MergeLeafNodePortals( idBrushBSPNode *node, int skipContents );
 225         void                                    UpdateTreeAfterMerge_r( idBrushBSPNode *node, const idBounds &bounds, idBrushBSPNode *oldNode, idBrushBSPNode *newNode );
 226         void                                    RemoveLeafNodeColinearPoints( idBrushBSPNode *node );
 227         void                                    RemoveColinearPoints_r( idBrushBSPNode *node, int skipContents );
 228         void                                    MeltFlood_r( idBrushBSPNode *node, int skipContents, idBounds &bounds, idVectorSet<idVec3,3> &vertexList );
 229         void                                    MeltLeafNodePortals( idBrushBSPNode *node, int skipContents, idVectorSet<idVec3,3> &vertexList );
 230         void                                    MeltPortals_r( idBrushBSPNode *node, int skipContents, idVectorSet<idVec3,3> &vertexList );
 231 };
 232
 233 #endif /* !__BRUSHBSP_H__ */