CaPVS/CaPVSWorld.cpp

   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 /**************************/
   8 /*** CaPVS World (Code) ***/
   9 /**************************/
  10
  11 #include <stdio.h>
  12 #include "CaPVSWorld.hpp"
  13 #include "SceneGraph/Node.hpp"
  14 #include "SceneGraph/BspTreeNode.hpp"
  15 #include "SceneGraph/FaceNode.hpp"
  16
  17
  18 CaPVSWorldT::CaPVSWorldT(const char* FileName, ModelManagerT& ModelMan, cf::GuiSys::GuiResourcesT& GuiRes, unsigned long SLC_MaxRecursionDepth_, double SLC_MinSubTreeFacesArea_)
  19     : m_World(FileName, ModelMan, GuiRes),
  20       m_BspTree(m_World.m_StaticEntityData[0]->m_BspTree),
  21       SLC_MaxRecursionDepth(SLC_MaxRecursionDepth_),
  22       SLC_MinSubTreeFacesArea(SLC_MinSubTreeFacesArea_)
  23 {
  24 }
  25
  26
  27 double CaPVSWorldT::SubTreeFacesArea(unsigned long NodeNr) const
  28 {
  29     const ArrayT<cf::SceneGraph::BspTreeNodeT::NodeT>& Nodes  = m_BspTree->Nodes;
  30     const ArrayT<cf::SceneGraph::BspTreeNodeT::LeafT>& Leaves = m_BspTree->Leaves;
  31
  32     // TODO: This method counts faces that are in multiple leaves multiply!
  33     // This is a BUG that should be fixed!!!
  34     double Area=0.0;
  35
  36     if (Nodes[NodeNr].FrontIsLeaf)
  37     {
  38         const cf::SceneGraph::BspTreeNodeT::LeafT& L=Leaves[Nodes[NodeNr].FrontChild];
  39
  40         for (unsigned long SetNr=0; SetNr<L.FaceChildrenSet.Size(); SetNr++)
  41             Area += m_BspTree->FaceChildren[L.FaceChildrenSet[SetNr]]->Polygon.GetArea();
  42     }
  43     else Area+=SubTreeFacesArea(Nodes[NodeNr].FrontChild);
  44
  45     if (Nodes[NodeNr].BackIsLeaf)
  46     {
  47         const cf::SceneGraph::BspTreeNodeT::LeafT& L=Leaves[Nodes[NodeNr].BackChild];
  48
  49         for (unsigned long SetNr=0; SetNr<L.FaceChildrenSet.Size(); SetNr++)
  50             Area += m_BspTree->FaceChildren[L.FaceChildrenSet[SetNr]]->Polygon.GetArea();
  51     }
  52     else Area+=SubTreeFacesArea(Nodes[NodeNr].BackChild);
  53
  54     return Area;
  55 }
  56
  57
  58 // Considers the sub-tree beginning at node 'NodeNr', and determines whether a SuperLeaf should be constructed from it or not.
  59 // Returns 'true' when a SuperLeaf should be constructed, 'false' otherwise.
  60 bool CaPVSWorldT::SuperLeafConditionIsMet(unsigned long NodeNr, unsigned long RecursionDepth) const
  61 {
  62     if (RecursionDepth>SLC_MaxRecursionDepth) return true;
  63     if (SubTreeFacesArea(NodeNr)<SLC_MinSubTreeFacesArea) return true;
  64
  65     return false;
  66 }
  67
  68
  69 void CaPVSWorldT::CreateSuperLeafFromSubTreeRecursive(unsigned long NodeNr, SuperLeafT& SuperLeaf) const
  70 {
  71     const ArrayT<cf::SceneGraph::BspTreeNodeT::NodeT>& Nodes  = m_BspTree->Nodes;
  72     const ArrayT<cf::SceneGraph::BspTreeNodeT::LeafT>& Leaves = m_BspTree->Leaves;
  73
  74     if (Nodes[NodeNr].FrontIsLeaf)
  75     {
  76         const unsigned long LeafNr=Nodes[NodeNr].FrontChild;
  77
  78         SuperLeaf.LeafSet.PushBack(LeafNr);
  79
  80         for (unsigned long PortalNr=0; PortalNr<Leaves[LeafNr].Portals.Size(); PortalNr++)
  81             SuperLeaf.Portals.PushBack(Leaves[LeafNr].Portals[PortalNr]);
  82
  83         if (SuperLeaf.LeafSet.Size()>1)
  84         {
  85             SuperLeaf.BB.Insert(Leaves[LeafNr].BB.Min);
  86             SuperLeaf.BB.Insert(Leaves[LeafNr].BB.Max);
  87         }
  88         else SuperLeaf.BB=Leaves[LeafNr].BB;
  89     }
  90     else CreateSuperLeafFromSubTreeRecursive(Nodes[NodeNr].FrontChild, SuperLeaf);
  91
  92     if (Nodes[NodeNr].BackIsLeaf)
  93     {
  94         const unsigned long LeafNr=Nodes[NodeNr].BackChild;
  95
  96         SuperLeaf.LeafSet.PushBack(LeafNr);
  97
  98         for (unsigned long PortalNr=0; PortalNr<Leaves[LeafNr].Portals.Size(); PortalNr++)
  99             SuperLeaf.Portals.PushBack(Leaves[LeafNr].Portals[PortalNr]);
 100
 101         if (SuperLeaf.LeafSet.Size()>1)
 102         {
 103             SuperLeaf.BB.Insert(Leaves[LeafNr].BB.Min);
 104             SuperLeaf.BB.Insert(Leaves[LeafNr].BB.Max);
 105         }
 106         else SuperLeaf.BB=Leaves[LeafNr].BB;
 107     }
 108     else CreateSuperLeafFromSubTreeRecursive(Nodes[NodeNr].BackChild, SuperLeaf);
 109 }
 110
 111
 112 // Traverses the sub-tree beginning at node 'NodeNr' and constructs a SuperLeaf from it.
 113 // The resulting SuperLeaf is returned.
 114 SuperLeafT CaPVSWorldT::CreateSuperLeafFromSubTree(unsigned long NodeNr) const
 115 {
 116     SuperLeafT SuperLeaf;
 117
 118     CreateSuperLeafFromSubTreeRecursive(NodeNr, SuperLeaf);
 119
 120     return SuperLeaf;
 121 }
 122
 123
 124 void CaPVSWorldT::CreateSuperLeavesRecursive(unsigned long NodeNr, ArrayT<SuperLeafT>& SuperLeaves, unsigned long RecursionDepth) const
 125 {
 126     const ArrayT<cf::SceneGraph::BspTreeNodeT::NodeT>& Nodes  = m_BspTree->Nodes;
 127     const ArrayT<cf::SceneGraph::BspTreeNodeT::LeafT>& Leaves = m_BspTree->Leaves;
 128
 129     if (Nodes[NodeNr].FrontIsLeaf)
 130     {
 131         // Create SuperLeaf from single leaf child.
 132         const unsigned long LeafNr=Nodes[NodeNr].FrontChild;
 133
 134         SuperLeaves.PushBackEmpty();
 135         SuperLeaves[SuperLeaves.Size()-1].LeafSet.PushBack(LeafNr);
 136         SuperLeaves[SuperLeaves.Size()-1].Portals=Leaves[LeafNr].Portals;
 137         SuperLeaves[SuperLeaves.Size()-1].BB     =Leaves[LeafNr].BB;
 138     }
 139     else
 140     {
 141         if (SuperLeafConditionIsMet(Nodes[NodeNr].FrontChild, RecursionDepth+1))
 142         {
 143             // Create SuperLeaf from the remaining front sub-tree.
 144             SuperLeaves.PushBack(CreateSuperLeafFromSubTree(Nodes[NodeNr].FrontChild));
 145         }
 146         else CreateSuperLeavesRecursive(Nodes[NodeNr].FrontChild, SuperLeaves, RecursionDepth+1);
 147     }
 148
 149     if (Nodes[NodeNr].BackIsLeaf)
 150     {
 151         // Create SuperLeaf from single leaf child.
 152         const unsigned long LeafNr=Nodes[NodeNr].BackChild;
 153
 154         SuperLeaves.PushBackEmpty();
 155         SuperLeaves[SuperLeaves.Size()-1].LeafSet.PushBack(LeafNr);
 156         SuperLeaves[SuperLeaves.Size()-1].Portals=Leaves[LeafNr].Portals;
 157         SuperLeaves[SuperLeaves.Size()-1].BB     =Leaves[LeafNr].BB;
 158     }
 159     else
 160     {
 161         if (SuperLeafConditionIsMet(Nodes[NodeNr].BackChild, RecursionDepth+1))
 162         {
 163             // Create SuperLeaf from the remaining back sub-tree.
 164             SuperLeaves.PushBack(CreateSuperLeafFromSubTree(Nodes[NodeNr].BackChild));
 165         }
 166         else CreateSuperLeavesRecursive(Nodes[NodeNr].BackChild, SuperLeaves, RecursionDepth+1);
 167     }
 168 }
 169
 170
 171 void CaPVSWorldT::CreateSuperLeaves(ArrayT<SuperLeafT>& SuperLeaves) const
 172 {
 173     const ArrayT<cf::SceneGraph::BspTreeNodeT::LeafT>& Leaves = m_BspTree->Leaves;
 174
 175     printf("\n*** Create SuperLeaves ***\n");
 176
 177     CreateSuperLeavesRecursive(0, SuperLeaves, 0);
 178
 179     printf("%5lu SuperLeaves created from\n", SuperLeaves.Size());
 180     printf("%5lu world leaves in CW file.\n", Leaves.Size());
 181 }
 182
 183
 184 unsigned long CaPVSWorldT::WhatLeaf(const VectorT& Position) const
 185 {
 186     return m_BspTree->WhatLeaf(Position);
 187 }
 188
 189
 190 double CaPVSWorldT::ClipLine(const VectorT& P, const VectorT& U) const
 191 {
 192     return m_BspTree->ClipLine(P, U, 0.0, 1.0);
 193 }
 194
 195
 196 void CaPVSWorldT::StorePVS(const ArrayT<SuperLeafT>& SuperLeaves, const ArrayT<unsigned long>& SuperLeavesPVS)
 197 {
 198     const ArrayT<cf::SceneGraph::BspTreeNodeT::LeafT>& Leaves = m_BspTree->Leaves;
 199     ArrayT<uint32_t>&                                  PVS    = m_BspTree->PVS;
 200
 201     // 'PVS' zurücksetzen (völlige Blindheit).
 202     for (unsigned long Vis=0; Vis<PVS.Size(); Vis++) PVS[Vis]=0;
 203
 204     // 'SuperLeavesPVS' ins 'PVS' übertragen.
 205     for (unsigned long SL1Nr=0; SL1Nr<SuperLeaves.Size(); SL1Nr++)
 206         for (unsigned long SL2Nr=0; SL2Nr<SuperLeaves.Size(); SL2Nr++)
 207         {
 208             const unsigned long PVSTotalBitNr1=SL1Nr*SuperLeaves.Size()+SL2Nr;
 209             const unsigned long PVSTotalBitNr2=SL2Nr*SuperLeaves.Size()+SL1Nr;
 210             const bool          CanSeeFrom1To2=bool((SuperLeavesPVS[PVSTotalBitNr1 >> 5] >> (PVSTotalBitNr1 & 31)) & 1);
 211             const bool          CanSeeFrom2To1=bool((SuperLeavesPVS[PVSTotalBitNr2 >> 5] >> (PVSTotalBitNr2 & 31)) & 1);
 212
 213             // 'CanSeeFrom2To1' ist nicht wirklich notwendig, nur wegen der PVS-Matrix-Symmetrie
 214             // (um "Can see from A to B, but not vice versa!" zu vermeiden)!
 215             if (CanSeeFrom1To2 && CanSeeFrom2To1)
 216             {
 217                 // Kann von allen Leaves in 'SuperLeaves[SL1Nr]' alle Leaves in 'SuperLeaves[SL2Nr]' sehen.
 218                 for (unsigned long LeafSet1Nr=0; LeafSet1Nr<SuperLeaves[SL1Nr].LeafSet.Size(); LeafSet1Nr++)
 219                     for (unsigned long LeafSet2Nr=0; LeafSet2Nr<SuperLeaves[SL2Nr].LeafSet.Size(); LeafSet2Nr++)
 220                     {
 221                         const unsigned long Leaf1Nr=SuperLeaves[SL1Nr].LeafSet[LeafSet1Nr];
 222                         const unsigned long Leaf2Nr=SuperLeaves[SL2Nr].LeafSet[LeafSet2Nr];
 223
 224                         if (!Leaves[Leaf1Nr].IsInnerLeaf) continue;
 225                         if (!Leaves[Leaf2Nr].IsInnerLeaf) continue;
 226
 227                         // Kann von 'Leaf1Nr' nach 'Leaf2Nr' sehen, markiere also 'Leaf2Nr' als von 'Leaf1Nr' aus sichtbar.
 228                         const unsigned long PVSTotalBitNr=Leaf1Nr*Leaves.Size()+Leaf2Nr;
 229                         const unsigned long PVS_W32_Nr   =PVSTotalBitNr >> 5;
 230                         const unsigned long PVSBitMask   =1 << (PVSTotalBitNr & 31);
 231                         PVS[PVS_W32_Nr]|=PVSBitMask;
 232                     }
 233             }
 234         }
 235 }
 236
 237
 238 unsigned long CaPVSWorldT::GetChecksumAndPrintStats() const
 239 {
 240     const ArrayT<uint32_t>& PVS = m_BspTree->PVS;
 241
 242     printf("\n*** Statistics ***\n");
 243
 244     unsigned long CheckSum=0;
 245
 246     for (unsigned long Count=0; Count<PVS.Size(); Count++)
 247     {
 248         CheckSum+=(PVS[Count] >> 24) & 0xFF;
 249         CheckSum+=(PVS[Count] >> 16) & 0xFF;
 250         CheckSum+=(PVS[Count] >>  8) & 0xFF;
 251         CheckSum+=(PVS[Count]      ) & 0xFF;
 252     }
 253
 254     printf("Size (bytes)        : %10lu\n", PVS.Size()*4);
 255     printf("CheckSum            : %10lu\n", CheckSum    );
 256
 257     return CheckSum;
 258 }
 259
 260
 261 void CaPVSWorldT::SaveToDisk(const char* FileName) const
 262 {
 263     m_World.SaveToDisk(FileName);
 264 }