Cafu Engine
BspTreeBuilder.hpp
1 /*
2 Cafu Engine, http://www.cafu.de/
3 Copyright (c) Carsten Fuchs and other contributors.
4 This project is licensed under the terms of the MIT license.
5 */
6 
7 #ifndef CAFU_BSPTREEBUILDER_HPP_INCLUDED
8 #define CAFU_BSPTREEBUILDER_HPP_INCLUDED
9 
10 #include "Math3D/Brush.hpp"
11 #include "Math3D/Polygon.hpp"
12 #include "Math3D/Vector3.hpp"
13 
14 #if defined(_WIN32) && _MSC_VER<1600
15 #include "pstdint.h" // Paul Hsieh's portable implementation of the stdint.h header.
16 #else
17 #include <stdint.h>
18 #endif
19 
20 
21 class MaterialT;
22 namespace cf { namespace SceneGraph { class BspTreeNodeT; } }
23 namespace cf { namespace SceneGraph { class FaceNodeT; } }
24 namespace cf { namespace SceneGraph { class GenericNodeT; } }
25 
26 
28 {
29  public:
30 
32  // ArrayT<cf::SceneGraph::BspTreeNodeT::NodeT>& Nodes;
33  // ArrayT<cf::SceneGraph::BspTreeNodeT::LeafT>& Leaves;
34  ArrayT<uint32_t>& PVS;
37  ArrayT<VectorT>& GlobalDrawVertices;
38 
39 
40  BspTreeBuilderT(cf::SceneGraph::BspTreeNodeT* BspTree_, bool MostSimpleTree, bool BspSplitFaces, bool ChopUpFaces);
41 
42  void Build(bool IsWorldspawn,
43  const ArrayT<Vector3dT>& FloodFillSources_,
44  const ArrayT<Vector3dT>& OutsidePointSamples,
45  const std::string& MapFileName /*for .pts pointfile*/);
46 
47 
48  // Alle sich schneidenden Faces werden geteilt, sodaß keine Schnitte mehr übrig bleiben.
49  // Splits werden aber nur dann durchgeführt, wenn dies nicht zu ungültigen Polygonen führt!
50  // Übergeordnetes Ziel ist es, von sich schneidenden Faces so viel wie möglich beim "FloodFillInside" loswerden zu können,
51  // sodaß am Schluß nur eine perfekt glatte Haut der Welt übrigbleibt!
52  void ChopUpFaces();
53 
54  // Prepare the world for leak detection. Must be called before 'BuildBSPTree()'.
55  // Never pollute the final BSP tree with the polygons generated by this function!
56  void PrepareLeakDetection(const ArrayT<Vector3dT>& FloodFillSources, MaterialT* LeakDetectMat);
57 
58  // Builds a BSP tree from the 'Faces'.
59  // The created nodes and leaves are stored in the 'Nodes' and 'Leaves' members, respectively.
60  // Note that some members of the leaves remain empty.
61  // Also the 'Faces' array will be modified during the process when BSP splits occur.
62  void BuildBSPTree();
63 
64  // Creates the 'Portals' for the leaves.
65  void Portalize();
66 
67  // Starting from the 'FloodFillOrigins', this flood-fills the world.
68  // The 'IsInnerLeaf' member of all reached leaves is set to true.
69  void FloodFillInside(const ArrayT<VectorT>& FloodFillOrigins, const ArrayT<VectorT>& WorldOutsidePointSamples);
70 
71  // Detects if a world has leaks. 'PrepareLeakDetection()' must have been called earlier.
72  // Must be called after 'FloodFillInside()' and before 'RemoveOuterFaces()' resp. 'RemoveOuterFacesTIsAndTDs()'.
73  void DetectLeaks(const ArrayT<VectorT>& FloodFillOrigins, const std::string& WorldFileName, MaterialT* LeakDetectMat);
74 
75  // This fills the 'OtherChildrenSet' of the leaves.
76  void AssignOtherChildrenToLeaves();
77 
78  // Removes all contents from the 'Faces' array that is not referenced by an "inner" leaf.
79  // The contents of the 'Nodes' and 'Leaves' becomes invalid thereafter, and thus is deleted.
80  void RemoveOuterFaces();
81 
82  // Removes portals from outer leaves. The tree remains intact!
83  void RemoveOuterPortals();
84 
85  // Merges faces as far as possible (but they must remain convex and their TexInfos must match).
86  // The contents of the 'Nodes' and 'Leaves', if any, becomes invalid.
87  void MergeFaces();
88 
89  // Sortiert die Faces gemäß ihres Texture-Namens und paßt die anderen Datenstrukturen entsprechend an.
90  // Der BSP-Baum bleibt also intakt.
91  void SortFacesIntoTexNameOrder();
92 
93  // Splits up faces that are too large to be covered by a single LightMap.
94  void ChopUpForMaxLightMapSize();
95 
96  // Splits up faces that are too large to be covered by a single SHLMap.
97  void ChopUpForMaxSHLMapSize();
98 
99  // Creates full-bright LightMaps for all faces.
100  // After this function was called, the 'Faces' MUST REMAIN UNMODIFIED! No further split or sorting operations!
101  void CreateFullBrightLightMaps();
102 
103  // Creates empty, zero-band SHLMaps for all faces.
104  // After this function was called, the 'Faces' MUST REMAIN UNMODIFIED! No further split or sorting operations!
105  void CreateZeroBandSHLMaps();
106 
107  // Basing on the contents of the 'Faces' array, this function computes the 'FacesDrawVertices' and 'FacesDrawIndices'.
108  // The result will have all T-Junctions removed and can be used with the OpenGL "glDrawElements()" function.
109  void ComputeDrawStructures();
110 
111  // Creates the trivial full-visibility PVS information for all leaves,
112  // that is, each leaf can see every other leaf.
113  void CreateFullVisPVS();
114 
115 
116  private:
117 
118  Plane3T<double> ChooseSplitPlane(const ArrayT<unsigned long>& FaceSet) const;
119  void BuildBSPTree_SplitFaces(const ArrayT<unsigned long>& FaceSet);
120  void BuildBSPTree_NeverSplit(const ArrayT<unsigned long>& FaceSet, const ArrayT<cf::SceneGraph::FaceNodeT*>& SplitFaces);
121  void FillBSPLeaves(unsigned long NodeNr, const ArrayT<cf::SceneGraph::FaceNodeT*>& Face2, const ArrayT<unsigned long>& FaceSet, const BoundingBox3T<double>& BB);
122  void CreateLeafPortals(unsigned long LeafNr, const ArrayT< Plane3T<double> >& NodeList);
123  void BuildBSPPortals(unsigned long NodeNr, ArrayT< Plane3T<double> >& NodeList);
124  void FloodFillInsideRecursive(unsigned long Leaf1Nr);
125  void ComputeLeakPathByBFS(const VectorT& Start) const;
126  void LeakDetected(const VectorT& InfoPlayerStartOrigin, const std::string& PointFileName, const unsigned long LeafNr) const;
127  void QuickSortFacesIntoTexNameOrder();
128 
129  const bool m_Option_MostSimpleTree;
130  const bool m_Option_BspSplitFaces;
131  const bool m_Option_ChopUpFaces;
132 };
133 
134 #endif
Definition: BspTreeBuilder.hpp:27
This class represents a polymorphic 3-dimensional vector.
Definition: Misc.hpp:11
This class represents a surface material ("A datastructural representation of a scripts material def...
Definition: Material.hpp:22
The class represents a BSP Tree node, implementing the Composite design pattern.
Definition: BspTreeNode.hpp:30