- Timestamp:
- 12/13/05 17:28:02 (19 years ago)
- Location:
- trunk/VUT/GtpVisibilityPreprocessor
- Files:
-
- 21 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
r452 r462 25 25 26 26 VssPreprocessor { 27 samplesPerPass 10000 28 initialSamples 100000 29 vssSamples 300000 30 vssSamplesPerPass 10000 27 samplesPerPass 100000 28 initialSamples 1000000 29 vssSamples 3000000 30 vssSamplesPerPass 100000 31 31 useImportanceSampling true 32 32 } … … 153 153 154 154 height 5.0 155 maxViewCells 0155 maxViewCells 5000 156 156 157 157 PostProcessing { … … 284 284 Termination { 285 285 maxDepth 40 286 minPvs 40287 minRays 10 0286 minPvs 90 287 minRays 10 288 288 minSize 0.1 289 289 maxCostRatio 999.0 … … 297 297 #splitType heuristics 298 298 ct_div_ci 0.0 299 300 # maximal cost for merging a view cell 301 maxCostRatio 1.4 299 302 } 300 303 -
trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
r448 r462 1395 1395 RegisterOption("VspKdTree.Construction.samples", 1396 1396 optInt, 1397 "-vsp_ construction_samples=",1397 "-vsp_kd_construction_samples=", 1398 1398 "100000"); 1399 1400 RegisterOption("VspKdTree.maxCostRatio", 1401 optFloat, 1402 "-vsp_kd_max_cost_ratio=", 1403 "1.5"); 1399 1404 1400 1405 RegisterOption("VspKdTree.Termination.maxDepth", -
trunk/VUT/GtpVisibilityPreprocessor/src/Exporter.h
r459 r462 119 119 const Vector3 direction) = 0; 120 120 121 virtual bool 122 ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs = 0) = 0; 123 121 124 void SetExportRayDensity(const bool d) { mExportRayDensity = d; } 122 125 -
trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp
r403 r462 502 502 int 503 503 KdTree::CastRay( 504 505 504 Ray &ray 505 ) 506 506 { 507 507 int hits = 0; -
trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp
r448 r462 23 23 Preprocessor::~Preprocessor() 24 24 { 25 DEL_PTR(mViewCellsManager); 26 25 27 DEL_PTR(mBspTree); 26 28 DEL_PTR(mKdTree); 27 29 DEL_PTR(mVspKdTree); 28 30 DEL_PTR(mVspBspTree); 29 DEL_PTR(mViewCellsManager);30 31 } 31 32 -
trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp
r449 r462 239 239 } 240 240 241 /******************************************************** /242 /* class BspRenderSimulator implementation */243 /******************************************************** /241 /**********************************************************/ 242 /* class BspRenderSimulator implementation */ 243 /**********************************************************/ 244 244 245 245 VspBspRenderSimulator::VspBspRenderSimulator(VspBspTree *vspBspTree): -
trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp
r459 r462 627 627 628 628 //-- several visualizations and statistics 629 Debug << "===== Final view cells statistics ==========" << endl;630 631 629 mViewCellsManager->PrintStatistics(Debug); 632 630 -
trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp
r452 r462 398 398 399 399 //-- several visualizations and statistics 400 Debug << "===== Final view cells statistics ==========" << endl;401 402 400 mViewCellsManager->PrintStatistics(Debug); 403 401 … … 412 410 413 411 mViewCellsManager->Visualize(objects, mSampleRays); 414 412 415 413 return true; 416 414 } -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp
r439 r462 4 4 #include "MeshKdTree.h" 5 5 #include "Triangle3.h" 6 #include <time.h> 7 #include <iomanip> 6 8 7 9 ViewCell::ViewCell(): MeshInstance(NULL), mPiercingRays(0) … … 32 34 mPassingRays.AddRay(ray, contributions); 33 35 } 36 37 /************************************************************************/ 38 /* class ViewCellsStatistics implementation */ 39 /************************************************************************/ 40 41 void ViewCellsStatistics::Print(ostream &app) const 42 { 43 app << "=========== View Cells Statistics ===============\n"; 44 45 app << setprecision(4); 46 47 //app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n"; 48 49 app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl; 50 51 app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl; 52 53 app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl; 54 55 app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl; 56 57 app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl; 58 59 app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl; 60 61 app << "#N_AVGLEAVES (average number of leaves per view cell )\n" << AvgLeaves() << endl; 62 63 app << "#N_MAXLEAVES ( maximal number of leaves per view cell )\n" << maxLeaves << endl; 64 65 app << "========== End of View Cells Statistics ==========\n"; 66 } -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.h
r454 r462 5 5 #include "Containers.h" 6 6 #include "Ray.h" 7 7 #include "Statistics.h" 8 8 //namespace GtpVisibilityPreprocessor { 9 9 … … 13 13 class BspLeaf; 14 14 class VspKdTree; 15 class VspKdTreeLeaf; 15 class VspKdLeaf; 16 16 17 17 18 /** … … 22 23 public: 23 24 ViewCell(); 25 24 26 /** Constructor taking a mesh representing the shape of the viewcell. 25 27 */ 26 28 ViewCell(Mesh *mesh); 29 30 31 virtual ~ViewCell() {} 27 32 /** Returns Pvs. 28 33 */ … … 67 72 ViewCell(mesh), mVspKdLeaves(0) {} 68 73 69 float GetSize() {return 0;}74 float GetSize() {return mSize;} 70 75 void SetSize(float size) {mSize = size;} 71 76 72 77 /// Leaves which hold this view cell. 73 vector<VspKd TreeLeaf *> mVspKdLeaves;78 vector<VspKdLeaf *> mVspKdLeaves; 74 79 75 80 protected: 76 81 float mSize; 77 82 }; 83 84 class ViewCellsStatistics: public StatisticsBase 85 { 86 public: 87 88 /// number of view cells 89 int viewCells; 90 91 /// size of the PVS 92 int pvs; 93 94 /// largest PVS of all view cells 95 int maxPvs; 96 97 /// smallest PVS of all view cells 98 int minPvs; 99 100 /// view cells with empty PVS 101 int emptyPvs; 102 103 /// number of leaves covering the view space 104 int leaves; 105 106 /// largest number of leaves covered by one view cell 107 int maxLeaves; 108 109 // Constructor 110 ViewCellsStatistics() 111 { 112 Reset(); 113 } 114 115 double AvgLeaves() const {return (double)leaves / (double)viewCells;}; 116 double AvgPvs() const {return (double)pvs / (double)viewCells;}; 117 118 void Reset() 119 { 120 viewCells = 0; 121 pvs = 0; 122 maxPvs = 0; 123 124 minPvs = 999999; 125 emptyPvs = 0; 126 leaves = 0; 127 maxLeaves = 0; 128 } 129 130 void Print(ostream &app) const; 131 132 friend ostream &operator<<(ostream &s, const ViewCellsStatistics &stat) 133 { 134 stat.Print(s); 135 return s; 136 } 137 }; 138 78 139 #endif -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
r452 r462 9 9 #include "AxisAlignedBox3.h" 10 10 #include <stack> 11 #include <time.h> 12 #include <iomanip> 11 13 12 #include "Exporter.h" 14 13 #include "Plane3.h" … … 1907 1906 } 1908 1907 1909 void BspTree::EvaluateViewCellsStats( BspViewCellsStatistics &stat) const1910 { 1911 stat.Reset();1908 void BspTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const 1909 { 1910 vcStat.Reset(); 1912 1911 1913 1912 stack<BspNode *> nodeStack; … … 1926 1925 if (node->IsLeaf()) 1927 1926 { 1928 ++ stat.bspLeaves;1927 ++ vcStat.leaves; 1929 1928 1930 1929 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->mViewCell; … … 1934 1933 viewCell->Mail(); 1935 1934 1936 ++ stat.viewCells;1935 ++ vcStat.viewCells; 1937 1936 const int pvsSize = viewCell->GetPvs().GetSize(); 1938 1937 1939 stat.pvs += pvsSize;1938 vcStat.pvs += pvsSize; 1940 1939 1941 1940 if (pvsSize < 1) 1942 ++ stat.emptyPvs;1943 1944 if (pvsSize > stat.maxPvs)1945 stat.maxPvs = pvsSize;1946 1947 if (pvsSize < stat.minPvs)1948 stat.minPvs = pvsSize;1949 1950 if ((int)viewCell->mBspLeaves.size() > stat.maxBspLeaves)1951 stat.maxBspLeaves = (int)viewCell->mBspLeaves.size();1941 ++ vcStat.emptyPvs; 1942 1943 if (pvsSize > vcStat.maxPvs) 1944 vcStat.maxPvs = pvsSize; 1945 1946 if (pvsSize < vcStat.minPvs) 1947 vcStat.minPvs = pvsSize; 1948 1949 if ((int)viewCell->mBspLeaves.size() > vcStat.maxLeaves) 1950 vcStat.maxLeaves = (int)viewCell->mBspLeaves.size(); 1952 1951 } 1953 1952 } … … 2412 2411 } 2413 2412 2414 void BspViewCellsStatistics::Print(ostream &app) const2415 {2416 app << "===== BspViewCells statistics ===============\n";2417 2418 app << setprecision(4);2419 2420 //app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";2421 2422 app << "#N_OVERALLPVS ( objects in PVS )\n" << pvs << endl;2423 2424 app << "#N_PMAXPVS ( largest PVS )\n" << maxPvs << endl;2425 2426 app << "#N_PMINPVS ( smallest PVS )\n" << minPvs << endl;2427 2428 app << "#N_PAVGPVS ( average PVS )\n" << AvgPvs() << endl;2429 2430 app << "#N_PEMPTYPVS ( view cells with PVS smaller 2 )\n" << emptyPvs << endl;2431 2432 app << "#N_VIEWCELLS ( number of view cells)\n" << viewCells << endl;2433 2434 app << "#N_AVGBSPLEAVES (average number of BSP leaves per view cell )\n" << AvgBspLeaves() << endl;2435 2436 app << "#N_MAXBSPLEAVES ( maximal number of BSP leaves per view cell )\n" << maxBspLeaves << endl;2437 2438 app << "===== END OF BspViewCells statistics ==========\n";2439 }2440 2413 2441 2414 /*************************************************************/ -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
r448 r462 18 18 class AxisAlignedBox3; 19 19 class Ray; 20 class ViewCellsStatistics; 20 21 21 22 class BspNodeGeometry … … 157 158 }; 158 159 159 class BspViewCellsStatistics: public StatisticsBase160 {161 public:162 163 /// number of view cells164 int viewCells;165 166 /// size of the PVS167 int pvs;168 169 /// largest PVS of all view cells170 int maxPvs;171 172 /// smallest PVS of all view cells173 int minPvs;174 175 /// view cells with empty PVS176 int emptyPvs;177 178 /// number of bsp leaves covering the view space179 int bspLeaves;180 181 /// largest number of leaves covered by one view cell182 int maxBspLeaves;183 184 // Constructor185 BspViewCellsStatistics()186 {187 Reset();188 }189 190 double AvgBspLeaves() const {return (double)bspLeaves / (double)viewCells;};191 double AvgPvs() const {return (double)pvs / (double)viewCells;};192 193 void Reset()194 {195 viewCells = 0;196 pvs = 0;197 maxPvs = 0;198 199 minPvs = 999999;200 emptyPvs = 0;201 bspLeaves = 0;202 maxBspLeaves = 0;203 }204 205 void Print(ostream &app) const;206 207 friend ostream &operator<<(ostream &s, const BspViewCellsStatistics &stat)208 {209 stat.Print(s);210 return s;211 }212 };213 160 214 161 /** … … 499 446 /** Traverses tree and counts all view cells as well as their PVS size. 500 447 */ 501 void EvaluateViewCellsStats( BspViewCellsStatistics &stat) const;448 void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 502 449 503 450 /** Returns view cell corresponding to unbounded space. -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp
r453 r462 154 154 ViewCell *ViewCellsManager::MergeViewCells(ViewCell &front, ViewCell &back) const 155 155 { 156 // generate merged view cell 156 157 ViewCell *vc = GenerateViewCell(); 158 157 159 // merge pvs 158 160 vc->GetPvs().Merge(front.GetPvs(), back.GetPvs()); 159 161 160 // merge ray sets162 //-- merge ray sets 161 163 stable_sort(front.mPiercingRays.begin(), front.mPiercingRays.end()); 162 164 stable_sort(back.mPiercingRays.begin(), back.mPiercingRays.end()); … … 223 225 mRenderSimulator = new BspRenderSimulator(bspTree); 224 226 InitRenderSimulator(); 227 } 228 229 230 BspViewCellsManager::~BspViewCellsManager() 231 { 232 ViewCellContainer vc; 233 mBspTree->CollectViewCells(vc); 234 235 CLEAR_CONTAINER(vc); 225 236 } 226 237 … … 336 347 int pvsSize = 0; 337 348 338 BspViewCellsStatistics vcStats;349 ViewCellsStatistics vcStats; 339 350 mBspTree->EvaluateViewCellsStats(vcStats); 340 351 Debug << "original view cell partition:\n" << vcStats << endl; … … 438 449 439 450 //-- recount pvs 440 BspViewCellsStatistics vcStats;451 ViewCellsStatistics vcStats; 441 452 mBspTree->EvaluateViewCellsStats(vcStats); 442 453 … … 721 732 return false; 722 733 723 // change view cells of all leaves associated with the 724 // previous view cells 725 734 //-- change pointer to view cells of all leaves associated with the previous view cells 726 735 BspViewCell *fVc = front->GetViewCell(); 727 736 BspViewCell *bVc = back->GetViewCell(); … … 774 783 void BspViewCellsManager::PrintStatistics(ostream &s) const 775 784 { 776 BspViewCellsStatistics vcStats;785 ViewCellsStatistics vcStats; 777 786 mBspTree->EvaluateViewCellsStats(vcStats); 778 787 s << vcStats << endl; … … 973 982 /**********************************************************************/ 974 983 975 VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples): 984 VspKdViewCellsManager::VspKdViewCellsManager(VspKdTree *vspKdTree, 985 int constructionSamples): 976 986 ViewCellsManager(constructionSamples), 977 987 mVspKdTree(vspKdTree) 978 988 { 979 989 mRenderSimulator = new VspKdRenderSimulator(vspKdTree); 990 mVspKdTree->SetViewCellsManager(this); 991 980 992 InitRenderSimulator(); 981 993 } 994 995 996 VspKdViewCellsManager::~VspKdViewCellsManager() 997 { 998 ViewCellContainer vc; 999 mVspKdTree->CollectViewCells(vc); 1000 1001 CLEAR_CONTAINER(vc); 1002 } 1003 982 1004 983 1005 int VspKdViewCellsManager::Construct(const ObjectContainer &objects, … … 1015 1037 return 0; 1016 1038 1017 //if (castRay)1018 //mVspKdTree->CastRay(ray);1039 if (castRay) 1040 mVspKdTree->CastRay(ray); 1019 1041 1020 1042 int sampleContributions = 0; 1021 1043 1022 1044 return sampleContributions; 1045 } 1046 1047 ViewCell *VspKdViewCellsManager::GenerateViewCell(Mesh *mesh) const 1048 { 1049 return new VspKdViewCell(mesh); 1023 1050 } 1024 1051 … … 1029 1056 return 0; 1030 1057 1031 return 0;1058 return mVspKdTree->MergeLeaves(); 1032 1059 } 1033 1060 … … 1043 1070 Exporter *exporter = Exporter::GetExporter("vspkdtree.x3d"); 1044 1071 //exporter->SetWireframe(); 1045 exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize); 1046 1047 Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl; 1072 //exporter->ExportVspKdTree(*mVspKdTree, mVspKdTree->GetStatistics().maxPvsSize); 1073 exporter->ExportVspKdTree(*mVspKdTree); 1048 1074 1049 1075 if (0) … … 1073 1099 } 1074 1100 1101 //-- export single leaves 1075 1102 if (1) 1076 1103 { 1077 vector<VspKdTreeLeaf *> leafContainer; 1078 1104 vector<VspKdLeaf *> leafContainer; 1079 1105 mVspKdTree->CollectLeaves(leafContainer); 1080 1106 … … 1086 1112 1087 1113 // export geometry 1088 VspKd TreeLeaf *leaf = leafContainer[Random((int)leafContainer.size())];1114 VspKdLeaf *leaf = leafContainer[Random((int)leafContainer.size())]; 1089 1115 AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf); 1090 1116 … … 1116 1142 } 1117 1143 } 1144 1145 // evaluate maximal pvs 1146 ViewCellsStatistics vcStats; 1147 mVspKdTree->EvaluateViewCellsStats(vcStats); 1148 1149 //-- export final view cells 1150 Exporter *exporter = Exporter::GetExporter("vspkdtree_merged.x3d"); 1151 //exporter->SetWireframe(); 1152 //exporter->ExportVspKdTreeViewCells(*mVspKdTree, vcStats.maxPvs); 1153 exporter->ExportVspKdTreeViewCells(*mVspKdTree); 1154 1155 Debug << "average PVS size: " << mVspKdTree->GetAvgPvsSize() << endl; 1156 1157 if (0) 1158 exporter->ExportGeometry(objects); 1159 1160 bool exportRays = false; 1161 1162 if (exportRays) 1163 { 1164 int raysSize = 2000; 1165 float prob = raysSize / (float)sampleRays.size(); 1166 1167 exporter->SetWireframe(); 1168 1169 RayContainer rays; 1170 1171 for (int i = 0; i < sampleRays.size(); ++ i) 1172 { 1173 if (RandomValue(0,1) < prob) 1174 rays.push_back(sampleRays[i]); 1175 } 1176 exporter->ExportRays(rays, 1000, RgbColor(1, 0, 0)); 1177 } 1178 1179 delete exporter; 1118 1180 } 1119 1181 … … 1125 1187 void VspKdViewCellsManager::PrintStatistics(ostream &s) const 1126 1188 { 1189 ViewCellsStatistics vcStats; 1190 1191 mVspKdTree->EvaluateViewCellsStats(vcStats); 1192 Debug << vcStats << endl; 1127 1193 } 1128 1194 … … 1141 1207 } 1142 1208 1209 1210 1211 VspBspViewCellsManager::~VspBspViewCellsManager() 1212 { 1213 ViewCellContainer vc; 1214 mVspBspTree->CollectViewCells(vc); 1215 1216 CLEAR_CONTAINER(vc); 1217 } 1218 1143 1219 bool VspBspViewCellsManager::ViewCellsConstructed() const 1144 1220 { 1145 1221 return mVspBspTree->GetRoot() != NULL; 1146 1222 } 1223 1147 1224 1148 1225 ViewCell *VspBspViewCellsManager::GenerateViewCell(Mesh *mesh) const … … 1247 1324 1248 1325 1249 BspViewCellsStatistics vcStats;1326 ViewCellsStatistics vcStats; 1250 1327 mVspBspTree->EvaluateViewCellsStats(vcStats); 1251 1328 Debug << "original view cell partition:\n" << vcStats << endl; … … 1340 1417 1341 1418 //-- recount pvs 1342 BspViewCellsStatistics vcStats;1419 ViewCellsStatistics vcStats; 1343 1420 mVspBspTree->EvaluateViewCellsStats(vcStats); 1344 1421 … … 1628 1705 void VspBspViewCellsManager::PrintStatistics(ostream &s) const 1629 1706 { 1630 BspViewCellsStatistics vcStats;1707 ViewCellsStatistics vcStats; 1631 1708 mVspBspTree->EvaluateViewCellsStats(vcStats); 1632 1709 s << vcStats << endl; -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.h
r452 r462 39 39 ViewCellsManager(); 40 40 41 ~ViewCellsManager();41 virtual ~ViewCellsManager(); 42 42 43 43 /** Constructs view cell container with a given number of samples. … … 221 221 void PrintStatistics(ostream &s) const; 222 222 223 ~BspViewCellsManager(); 223 224 protected: 224 225 … … 303 304 VspKdViewCellsManager(VspKdTree *vspKdTree, int constructionSamples); 304 305 306 ~VspKdViewCellsManager(); 307 305 308 int Construct(const ObjectContainer &objects, 306 309 const VssRayContainer &rays, … … 321 324 virtual void PrintStatistics(ostream &s) const; 322 325 326 ViewCell *GenerateViewCell(Mesh *mesh) const; 327 323 328 protected: 324 329 … … 338 343 339 344 VspBspViewCellsManager(VspBspTree *tree, int constructionSamples); 345 346 ~VspBspViewCellsManager(); 340 347 341 348 int Construct(const ObjectContainer &objects, -
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
r452 r462 1220 1220 } 1221 1221 1222 void VspBspTree::EvaluateViewCellsStats( BspViewCellsStatistics &stat) const1222 void VspBspTree::EvaluateViewCellsStats(ViewCellsStatistics &stat) const 1223 1223 { 1224 1224 stat.Reset(); … … 1239 1239 if (node->IsLeaf()) 1240 1240 { 1241 ++ stat. bspLeaves;1241 ++ stat.leaves; 1242 1242 1243 1243 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell(); … … 1261 1261 stat.minPvs = pvsSize; 1262 1262 1263 if ((int)viewCell->mBspLeaves.size() > stat.max BspLeaves)1264 stat.max BspLeaves = (int)viewCell->mBspLeaves.size();1263 if ((int)viewCell->mBspLeaves.size() > stat.maxLeaves) 1264 stat.maxLeaves = (int)viewCell->mBspLeaves.size(); 1265 1265 } 1266 1266 } -
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h
r448 r462 19 19 class AxisAlignedBox3; 20 20 class Ray; 21 class ViewCellsStatistics; 21 22 22 23 /*class BspNodeGeometry; 23 24 class BspTreeStatistics; 24 class BspViewCellsStatistics;25 class ViewCellsStatistics; 25 26 class BspNode; 26 27 class BspLeaf; … … 196 197 /** Traverses tree and counts all view cells as well as their PVS size. 197 198 */ 198 void EvaluateViewCellsStats( BspViewCellsStatistics &stat) const;199 void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 199 200 200 201 -
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
r453 r462 25 25 #include "Ray.h" 26 26 #include "RayInfo.h" 27 #include "ViewCell.h" 27 28 #include "ViewCellsManager.h" 28 #include "ViewCell .h"29 #include "ViewCellBsp.h" 29 30 30 31 // Static variables 31 int VspKdTreeLeaf::mailID = 0; 32 int VspKdLeaf::sMailId = 0; 33 int MergeCandidate::sMaxPvsSize = 150; 34 32 35 33 36 #define USE_FIXEDPOINT_T 0 … … 70 73 71 74 /**************************************************************/ 72 /* class VspKd TreeNode implementation */75 /* class VspKdNode implementation */ 73 76 /**************************************************************/ 74 77 75 78 // Inline constructor 76 VspKd TreeNode::VspKdTreeNode(VspKdTreeInterior *p):79 VspKdNode::VspKdNode(VspKdInterior *p): 77 80 mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0) 78 81 {} 79 82 80 VspKd TreeNode::~VspKdTreeNode()83 VspKdNode::~VspKdNode() 81 84 {}; 82 85 83 inline VspKd TreeInterior *VspKdTreeNode::GetParent() const86 inline VspKdInterior *VspKdNode::GetParent() const 84 87 { 85 88 return mParent; 86 89 } 87 90 88 inline void VspKd TreeNode::SetParent(VspKdTreeInterior *p)91 inline void VspKdNode::SetParent(VspKdInterior *p) 89 92 { 90 93 mParent = p; 91 94 } 92 95 93 bool VspKd TreeNode::IsLeaf() const96 bool VspKdNode::IsLeaf() const 94 97 { 95 98 return mAxis == -1; 96 99 } 97 100 98 int VspKd TreeNode::GetAccessTime()101 int VspKdNode::GetAccessTime() 99 102 { 100 103 return 0x7FFFFFF; … … 102 105 103 106 /**************************************************************/ 104 /* VspKd TreeInterior implementation */107 /* VspKdInterior implementation */ 105 108 /**************************************************************/ 106 109 107 VspKd TreeInterior::VspKdTreeInterior(VspKdTreeInterior *p):108 VspKd TreeNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)109 { 110 } 111 112 int VspKd TreeInterior::GetAccessTime()110 VspKdInterior::VspKdInterior(VspKdInterior *p): 111 VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1) 112 { 113 } 114 115 int VspKdInterior::GetAccessTime() 113 116 { 114 117 return mLastAccessTime; 115 118 } 116 119 117 void VspKd TreeInterior::SetupChildLinks(VspKdTreeNode *b, VspKdTreeNode *f)120 void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f) 118 121 { 119 122 mBack = b; … … 123 126 } 124 127 125 void VspKd TreeInterior::ReplaceChildLink(VspKdTreeNode *oldChild,126 VspKd TreeNode *newChild)128 void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild, 129 VspKdNode *newChild) 127 130 { 128 131 if (mBack == oldChild) … … 132 135 } 133 136 134 int VspKd TreeInterior::Type() const137 int VspKdInterior::Type() const 135 138 { 136 139 return EInterior; 137 140 } 138 141 139 VspKd TreeInterior::~VspKdTreeInterior()142 VspKdInterior::~VspKdInterior() 140 143 { 141 144 DEL_PTR(mBack); … … 143 146 } 144 147 145 void VspKd TreeInterior::Print(ostream &s) const148 void VspKdInterior::Print(ostream &s) const 146 149 { 147 150 switch (mAxis) … … 161 164 } 162 165 163 int VspKd TreeInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)166 int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t) 164 167 { 165 168 return rayData.ComputeRayIntersection(mAxis, mPosition, t); 166 169 } 167 170 168 VspKd TreeNode *VspKdTreeInterior::GetBack() const171 VspKdNode *VspKdInterior::GetBack() const 169 172 { 170 173 return mBack; 171 174 } 172 175 173 VspKd TreeNode *VspKdTreeInterior::GetFront() const176 VspKdNode *VspKdInterior::GetFront() const 174 177 { 175 178 return mFront; … … 178 181 179 182 /**************************************************************/ 180 /* class VspKd TreeLeaf implementation */183 /* class VspKdLeaf implementation */ 181 184 /**************************************************************/ 182 VspKdTreeLeaf::VspKdTreeLeaf(VspKdTreeInterior *p, const int nRays): 183 VspKdTreeNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL) 185 186 187 VspKdLeaf::VspKdLeaf(VspKdInterior *p, const int nRays): 188 VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL) 184 189 { 185 190 mRays.reserve(nRays); 186 191 } 187 192 188 VspKdTreeLeaf::~VspKdTreeLeaf() 189 {} 190 191 int VspKdTreeLeaf::Type() const 193 VspKdLeaf::~VspKdLeaf() 194 { 195 } 196 197 int VspKdLeaf::Type() const 192 198 { 193 199 return ELeaf; 194 200 } 195 201 196 void VspKd TreeLeaf::Print(ostream &s) const202 void VspKdLeaf::Print(ostream &s) const 197 203 { 198 204 s << endl << "L: r = " << (int)mRays.size() << endl; 199 205 }; 200 206 201 void VspKd TreeLeaf::AddRay(const RayInfo &data)207 void VspKdLeaf::AddRay(const RayInfo &data) 202 208 { 203 209 mValidPvs = false; … … 206 212 } 207 213 208 int VspKd TreeLeaf::GetPvsSize() const214 int VspKdLeaf::GetPvsSize() const 209 215 { 210 216 return mPvsSize; 211 217 } 212 218 213 void VspKd TreeLeaf::SetPvsSize(const int s)219 void VspKdLeaf::SetPvsSize(const int s) 214 220 { 215 221 mPvsSize = s; 216 222 } 217 223 218 void VspKd TreeLeaf::Mail()224 void VspKdLeaf::Mail() 219 225 { 220 mMailbox = mailID;221 } 222 223 void VspKd TreeLeaf::NewMail()226 mMailbox = sMailId; 227 } 228 229 void VspKdLeaf::NewMail() 224 230 { 225 ++ mailID;226 } 227 228 bool VspKd TreeLeaf::Mailed() const231 ++ sMailId; 232 } 233 234 bool VspKdLeaf::Mailed() const 229 235 { 230 return mMailbox == mailID; 231 } 232 233 bool VspKdTreeLeaf::Mailed(const int mail) 234 { 235 return mMailbox >= mailID + mail; 236 } 237 238 float VspKdTreeLeaf::GetAvgRayContribution() const 236 return mMailbox == sMailId; 237 } 238 239 bool VspKdLeaf::Mailed(const int mail) const 240 { 241 return mMailbox == mail; 242 } 243 244 int VspKdLeaf::GetMailbox() const 245 { 246 return mMailbox; 247 } 248 249 float VspKdLeaf::GetAvgRayContribution() const 239 250 { 240 251 return GetPvsSize() / ((float)mRays.size() + Limits::Small); 241 252 } 242 253 243 float VspKd TreeLeaf::GetSqrRayContribution() const254 float VspKdLeaf::GetSqrRayContribution() const 244 255 { 245 256 return sqr(GetAvgRayContribution()); 246 257 } 247 258 248 RayInfoContainer &VspKd TreeLeaf::GetRays()259 RayInfoContainer &VspKdLeaf::GetRays() 249 260 { 250 261 return mRays; 251 262 } 252 263 253 void VspKd TreeLeaf::ExtractPvs(ObjectContainer &objects) const264 void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const 254 265 { 255 266 RayInfoContainer::const_iterator it, it_end = mRays.end(); … … 264 275 } 265 276 266 void VspKd TreeLeaf::GetRays(VssRayContainer &rays)277 void VspKdLeaf::GetRays(VssRayContainer &rays) 267 278 { 268 279 RayInfoContainer::const_iterator it, it_end = mRays.end(); … … 272 283 } 273 284 274 V iewCell *VspKdTreeLeaf::GetViewCell()285 VspKdViewCell *VspKdLeaf::GetViewCell() 275 286 { 276 287 return mViewCell; 277 288 } 278 289 279 /*********************************************************/ 280 /* class VspKdTree implementation */ 281 /*********************************************************/ 282 283 284 VspKdTree::VspKdTree(): mOnlyDrivingAxis(true) 285 { 286 environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth); 287 environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs); 288 environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays); 289 environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution); 290 environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio); 291 environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize); 292 293 mTermMinSize = sqr(mTermMinSize); 294 295 environment->GetFloatValue("VspKdTree.epsilon", mEpsilon); 296 environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi); 297 298 environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory); 299 environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory); 300 301 environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold); 302 environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth); 303 304 // split type 305 char sname[128]; 306 environment->GetStringValue("VspKdTree.splitType", sname); 307 string name(sname); 308 309 Debug << "======= vsp kd tree options ========" << endl; 310 Debug << "max depth: "<< mTermMaxDepth << endl; 311 Debug << "min pvs: "<< mTermMinPvs << endl; 312 Debug << "min rays: "<< mTermMinRays << endl; 313 Debug << "max ray contribution: "<< mTermMaxRayContribution << endl; 314 Debug << "max cost ratio: "<< mTermMaxCostRatio << endl; 315 Debug << "min size: "<<mTermMinSize << endl; 316 317 if (name.compare("regular") == 0) 318 { 319 Debug << "using regular split" << endl; 320 splitType = ESplitRegular; 321 } 322 else 323 { 324 if (name.compare("heuristic") == 0) 325 { 326 Debug << "using heuristic split" << endl; 327 splitType = ESplitHeuristic; 328 } 329 else 330 { 331 cerr << "Invalid VspKdTree split type " << name << endl; 332 exit(1); 333 } 334 } 335 336 mRoot = NULL; 337 338 mSplitCandidates = new vector<SortableEntry>; 339 } 340 341 342 VspKdTree::~VspKdTree() 343 { 344 DEL_PTR(mRoot); 345 DEL_PTR(mSplitCandidates); 346 } 347 348 void VspKdStatistics::Print(ostream &app) const 349 { 350 app << "===== VspKdTree statistics ===============\n"; 351 352 app << "#N_RAYS ( Number of rays )\n" 353 << rays << endl; 354 355 app << "#N_INITPVS ( Initial PVS size )\n" 356 << initialPvsSize << endl; 357 358 app << "#N_NODES ( Number of nodes )\n" << nodes << "\n"; 359 360 app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n"; 361 362 app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n"; 363 364 for (int i=0; i<7; i++) 365 app << splits[i] <<" "; 366 app << endl; 367 368 app << "#N_RAYREFS ( Number of rayRefs )\n" << 369 rayRefs << "\n"; 370 371 app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" << 372 rayRefs / (double)rays << "\n"; 373 374 app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" << 375 rayRefs / (double)Leaves() << "\n"; 376 377 app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" << 378 maxRayRefs << "\n"; 379 380 // app << setprecision(4); 381 382 app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" << 383 maxDepthNodes * 100 / (double)Leaves() << endl; 384 385 app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n" << 386 minPvsNodes * 100 / (double)Leaves() << endl; 387 388 app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n" << 389 minRaysNodes * 100 / (double)Leaves() << endl; 390 391 app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<< 392 minSizeNodes * 100 / (double)Leaves() << endl; 393 394 app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n" << 395 maxRayContribNodes * 100 / (double)Leaves() << endl; 396 397 app << "#N_ADDED_RAYREFS ( Number of dynamically added ray references )\n"<< 398 addedRayRefs << endl; 399 400 app << "#N_REMOVED_RAYREFS ( Number of dynamically removed ray references )\n"<< 401 removedRayRefs << endl; 402 403 // app << setprecision(4); 404 405 app << "#N_MAXPVS ( Maximal PVS size / leaf)\n" 406 << maxPvsSize << endl; 407 408 app << "#N_CTIME ( Construction time [s] )\n" 409 << Time() << " \n"; 410 411 app << "===== END OF VspKdTree statistics ==========\n"; 412 } 413 414 415 void 416 VspKdTreeLeaf::UpdatePvsSize() 290 void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell) 291 { 292 mViewCell = viewCell; 293 } 294 295 296 void VspKdLeaf::UpdatePvsSize() 417 297 { 418 298 if (!mValidPvs) … … 449 329 } 450 330 451 452 void 453 VspKdTree::Construct(const VssRayContainer &rays, 454 AxisAlignedBox3 *forcedBoundingBox) 331 /*********************************************************/ 332 /* class VspKdTree implementation */ 333 /*********************************************************/ 334 335 336 337 VspKdTree::VspKdTree(): mOnlyDrivingAxis(true) 338 { 339 environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth); 340 environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs); 341 environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays); 342 environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution); 343 environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio); 344 environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize); 345 346 mTermMinSize = sqr(mTermMinSize); 347 348 environment->GetFloatValue("VspKdTree.epsilon", mEpsilon); 349 environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi); 350 351 environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory); 352 environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory); 353 354 environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold); 355 environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth); 356 357 environment->GetFloatValue("VspKdTree.maxCostRatio", mMaxCostRatio); 358 environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 359 360 MergeCandidate::sMaxPvsSize = 300; // TODO: add option 361 362 // split type 363 char sname[128]; 364 environment->GetStringValue("VspKdTree.splitType", sname); 365 string name(sname); 366 367 Debug << "======= vsp kd tree options ========" << endl; 368 Debug << "max depth: "<< mTermMaxDepth << endl; 369 Debug << "min pvs: "<< mTermMinPvs << endl; 370 Debug << "min rays: "<< mTermMinRays << endl; 371 Debug << "max ray contribution: "<< mTermMaxRayContribution << endl; 372 Debug << "max cost ratio: "<< mTermMaxCostRatio << endl; 373 Debug << "min size: "<<mTermMinSize << endl; 374 375 if (name.compare("regular") == 0) 376 { 377 Debug << "using regular split" << endl; 378 splitType = ESplitRegular; 379 } 380 else 381 { 382 if (name.compare("heuristic") == 0) 383 { 384 Debug << "using heuristic split" << endl; 385 splitType = ESplitHeuristic; 386 } 387 else 388 { 389 cerr << "Invalid VspKdTree split type " << name << endl; 390 exit(1); 391 } 392 } 393 394 mRoot = NULL; 395 396 mSplitCandidates = new vector<SortableEntry>; 397 } 398 399 400 VspKdTree::~VspKdTree() 401 { 402 DEL_PTR(mRoot); 403 DEL_PTR(mSplitCandidates); 404 } 405 406 void VspKdStatistics::Print(ostream &app) const 407 { 408 app << "===== VspKdTree statistics ===============\n"; 409 410 app << "#N_RAYS ( Number of rays )\n" 411 << rays << endl; 412 413 app << "#N_INITPVS ( Initial PVS size )\n" 414 << initialPvsSize << endl; 415 416 app << "#N_NODES ( Number of nodes )\n" << nodes << "\n"; 417 418 app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n"; 419 420 app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n"; 421 422 for (int i=0; i<7; i++) 423 app << splits[i] <<" "; 424 app << endl; 425 426 app << "#N_RAYREFS ( Number of rayRefs )\n" << 427 rayRefs << "\n"; 428 429 app << "#N_RAYRAYREFS ( Number of rayRefs / ray )\n" << 430 rayRefs / (double)rays << "\n"; 431 432 app << "#N_LEAFRAYREFS ( Number of rayRefs / leaf )\n" << 433 rayRefs / (double)Leaves() << "\n"; 434 435 app << "#N_MAXRAYREFS ( Max number of rayRefs / leaf )\n" << 436 maxRayRefs << "\n"; 437 438 // app << setprecision(4); 439 440 app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" << 441 maxDepthNodes * 100 / (double)Leaves() << endl; 442 443 app << "#N_PMINPVSLEAVES ( Percentage of leaves with mininimal PVS )\n" << 444 minPvsNodes * 100 / (double)Leaves() << endl; 445 446 app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n" << 447 minRaysNodes * 100 / (double)Leaves() << endl; 448 449 app << "#N_PMINSIZELEAVES ( Percentage of leaves with minSize )\n"<< 450 minSizeNodes * 100 / (double)Leaves() << endl; 451 452 app << "#N_PMAXRAYCONTRIBLEAVES ( Percentage of leaves with maximal ray contribution )\n" << 453 maxRayContribNodes * 100 / (double)Leaves() << endl; 454 455 app << "#N_ADDED_RAYREFS ( Number of dynamically added ray references )\n"<< 456 addedRayRefs << endl; 457 458 app << "#N_REMOVED_RAYREFS ( Number of dynamically removed ray references )\n"<< 459 removedRayRefs << endl; 460 461 // app << setprecision(4); 462 463 app << "#N_( Maximal PVS size / leaf)\n" 464 << maxPvsSize << endl; 465 466 app << "#N_CTIME ( Construction time [s] )\n" 467 << Time() << " \n"; 468 469 app << "===== END OF VspKdTree statistics ==========\n"; 470 } 471 472 473 void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const 474 { 475 stack<VspKdNode *> nodeStack; 476 nodeStack.push(mRoot); 477 478 ViewCell::NewMail(); 479 480 while (!nodeStack.empty()) 481 { 482 VspKdNode *node = nodeStack.top(); 483 nodeStack.pop(); 484 485 if (node->IsLeaf()) 486 { 487 ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell; 488 489 if (!viewCell->Mailed()) 490 { 491 viewCell->Mail(); 492 viewCells.push_back(viewCell); 493 } 494 } 495 else 496 { 497 VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 498 499 nodeStack.push(interior->GetFront()); 500 nodeStack.push(interior->GetBack()); 501 } 502 } 503 } 504 505 void VspKdTree::Construct(const VssRayContainer &rays, 506 AxisAlignedBox3 *forcedBoundingBox) 455 507 { 456 508 mStat.Start(); … … 459 511 DEL_PTR(mRoot); 460 512 461 mRoot = new VspKd TreeLeaf(NULL, (int)rays.size());513 mRoot = new VspKdLeaf(NULL, (int)rays.size()); 462 514 463 515 // first construct a leaf that will get subdivided 464 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(mRoot);516 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot); 465 517 466 518 mStat.nodes = 1; … … 523 575 524 576 525 VspKd TreeNode *VspKdTree::Subdivide(const TraversalData &tdata)526 { 527 VspKd TreeNode *result = NULL;577 VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata) 578 { 579 VspKdNode *result = NULL; 528 580 529 581 priority_queue<TraversalData> tStack; … … 562 614 tStack.pop(); 563 615 564 VspKd TreeNode *node = SubdivideNode((VspKdTreeLeaf *) data.mNode,616 VspKdNode *node = SubdivideNode((VspKdLeaf *) data.mNode, 565 617 data.mBox, backBox, frontBox); 566 618 if (result == NULL) … … 569 621 if (!node->IsLeaf()) 570 622 { 571 VspKd TreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);623 VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 572 624 573 625 // push the children on the stack … … 586 638 587 639 // returns selected plane for subdivision 588 int VspKdTree::SelectPlane(VspKd TreeLeaf *leaf,640 int VspKdTree::SelectPlane(VspKdLeaf *leaf, 589 641 const AxisAlignedBox3 &box, 590 642 float &position, … … 641 693 642 694 643 float VspKdTree::EvalCostRatio(VspKd TreeLeaf *leaf,695 float VspKdTree::EvalCostRatio(VspKdLeaf *leaf, 644 696 const int axis, 645 697 const float position, … … 711 763 } 712 764 713 float VspKdTree::BestCostRatioRegular(VspKd TreeLeaf *leaf,765 float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf, 714 766 int &axis, 715 767 float &position, … … 772 824 } 773 825 774 float VspKdTree::BestCostRatioHeuristic(VspKd TreeLeaf *leaf,826 float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf, 775 827 int &axis, 776 828 float &position, … … 895 947 } 896 948 897 void VspKdTree::SortSplitCandidates(VspKd TreeLeaf *node,949 void VspKdTree::SortSplitCandidates(VspKdLeaf *node, 898 950 const int axis) 899 951 { … … 930 982 { 931 983 // the node became a leaf -> evaluate stats for leafs 932 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);984 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode); 933 985 934 986 if (leaf->GetPvsSize() > mStat.maxPvsSize) … … 956 1008 957 1009 958 inline bool VspKdTree::TerminationCriteriaMet(const VspKd TreeLeaf *leaf,1010 inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf, 959 1011 const AxisAlignedBox3 &box) const 960 1012 { 961 1013 return ((leaf->GetPvsSize() < mTermMinPvs) || 962 1014 (leaf->mRays.size() < mTermMinRays) || 963 (leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||1015 //(leaf->GetAvgRayContribution() > mTermMaxRayContribution ) || 964 1016 (leaf->mDepth >= mTermMaxDepth) || 965 1017 (SqrMagnitude(box.Size()) <= mTermMinSize)); … … 967 1019 968 1020 969 VspKd TreeNode *VspKdTree::SubdivideNode(VspKdTreeLeaf *leaf,1021 VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf, 970 1022 const AxisAlignedBox3 &box, 971 1023 AxisAlignedBox3 &backBBox, … … 1005 1057 1006 1058 // add the new nodes to the tree 1007 VspKd TreeInterior *node = new VspKdTreeInterior(leaf->mParent);1059 VspKdInterior *node = new VspKdInterior(leaf->mParent); 1008 1060 1009 1061 node->mAxis = axis; … … 1014 1066 frontBBox = box; 1015 1067 1016 VspKd TreeLeaf *back = new VspKdTreeLeaf(node, raysBack);1068 VspKdLeaf *back = new VspKdLeaf(node, raysBack); 1017 1069 back->SetPvsSize(pvsBack); 1018 VspKd TreeLeaf *front = new VspKdTreeLeaf(node, raysFront);1070 VspKdLeaf *front = new VspKdLeaf(node, raysFront); 1019 1071 front->SetPvsSize(pvsFront); 1020 1072 … … 1025 1077 node->SetupChildLinks(back, front); 1026 1078 1027 if (axis <= VspKd TreeNode::SPLIT_Z)1079 if (axis <= VspKdNode::SPLIT_Z) 1028 1080 { 1029 1081 backBBox.SetMax(axis, position); … … 1110 1162 int VspKdTree::ReleaseMemory(const int time) 1111 1163 { 1112 stack<VspKd TreeNode *> tstack;1164 stack<VspKdNode *> tstack; 1113 1165 1114 1166 // find a node in the tree which subtree will be collapsed … … 1120 1172 while (!tstack.empty()) 1121 1173 { 1122 VspKd TreeNode *node = tstack.top();1174 VspKdNode *node = tstack.top(); 1123 1175 tstack.pop(); 1124 1176 1125 1177 if (!node->IsLeaf()) 1126 1178 { 1127 VspKd TreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);1179 VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 1128 1180 // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl; 1129 1181 if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime) … … 1156 1208 1157 1209 1158 VspKd TreeNode *VspKdTree::SubdivideLeaf(VspKdTreeLeaf *leaf,1210 VspKdNode *VspKdTree::SubdivideLeaf(VspKdLeaf *leaf, 1159 1211 const float sizeThreshold) 1160 1212 { 1161 VspKd TreeNode *node = leaf;1213 VspKdNode *node = leaf; 1162 1214 1163 1215 AxisAlignedBox3 leafBBox = GetBBox(leaf); … … 1188 1240 VssRayContainer &add) 1189 1241 { 1190 VspKd TreeLeaf::NewMail();1242 VspKdLeaf::NewMail(); 1191 1243 1192 1244 // schedule rays for removal … … 1218 1270 1219 1271 void VspKdTree::RemoveRay(VssRay *ray, 1220 vector<VspKd TreeLeaf *> *affectedLeaves,1272 vector<VspKdLeaf *> *affectedLeaves, 1221 1273 const bool removeAllScheduledRays) 1222 1274 { … … 1243 1295 // remove the ray from the leaf 1244 1296 // find the ray in the leaf and swap it with the last ray... 1245 VspKd TreeLeaf *leaf = (VspKdTreeLeaf *)data.mNode;1297 VspKdLeaf *leaf = (VspKdLeaf *)data.mNode; 1246 1298 1247 1299 if (!leaf->Mailed()) … … 1329 1381 // remove the ray from the leaf 1330 1382 // find the ray in the leaf and swap it with the last ray 1331 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(data.mNode);1383 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode); 1332 1384 1333 1385 leaf->AddRay(data.mRayData); … … 1340 1392 stack<RayTraversalData> &tstack) 1341 1393 { 1342 VspKd TreeInterior *in = dynamic_cast<VspKdTreeInterior *>(data.mNode);1343 1344 if (in->mAxis <= VspKd TreeNode::SPLIT_Z)1394 VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode); 1395 1396 if (in->mAxis <= VspKdNode::SPLIT_Z) 1345 1397 { 1346 1398 // determine the side of this ray with respect to the plane … … 1387 1439 1388 1440 1389 int VspKdTree::CollapseSubtree(VspKd TreeNode *sroot, const int time)1441 int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time) 1390 1442 { 1391 1443 // first count all rays in the subtree 1392 1444 // use mail 1 for this purpose 1393 stack<VspKd TreeNode *> tstack;1445 stack<VspKdNode *> tstack; 1394 1446 1395 1447 int rayCount = 0; … … 1413 1465 ++ collapsedNodes; 1414 1466 1415 VspKd TreeNode *node = tstack.top();1467 VspKdNode *node = tstack.top(); 1416 1468 tstack.pop(); 1417 1469 if (node->IsLeaf()) 1418 1470 { 1419 VspKd TreeLeaf *leaf = (VspKdTreeLeaf *) node;1471 VspKdLeaf *leaf = (VspKdLeaf *) node; 1420 1472 1421 1473 for(RayInfoContainer::iterator ri = leaf->mRays.begin(); … … 1433 1485 else 1434 1486 { 1435 tstack.push(((VspKd TreeInterior *)node)->GetFront());1436 tstack.push(((VspKd TreeInterior *)node)->GetBack());1487 tstack.push(((VspKdInterior *)node)->GetFront()); 1488 tstack.push(((VspKdInterior *)node)->GetBack()); 1437 1489 } 1438 1490 } … … 1441 1493 1442 1494 // create a new node that will hold the rays 1443 VspKd TreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->mParent, rayCount);1495 VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount); 1444 1496 1445 1497 if (newLeaf->mParent) … … 1450 1502 while (!tstack.empty()) 1451 1503 { 1452 VspKd TreeNode *node = tstack.top();1504 VspKdNode *node = tstack.top(); 1453 1505 tstack.pop(); 1454 1506 1455 1507 if (node->IsLeaf()) 1456 1508 { 1457 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);1509 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 1458 1510 1459 1511 for(RayInfoContainer::iterator ri = leaf->mRays.begin(); … … 1476 1528 else 1477 1529 { 1478 VspKd TreeInterior *interior =1479 dynamic_cast<VspKd TreeInterior *>(node);1530 VspKdInterior *interior = 1531 dynamic_cast<VspKdInterior *>(node); 1480 1532 tstack.push(interior->GetBack()); 1481 1533 tstack.push(interior->GetFront()); … … 1486 1538 DEL_PTR(sroot); 1487 1539 1488 // for(VspKd TreeNode::SRayContainer::iterator ri = newleaf->mRays.begin();1540 // for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin(); 1489 1541 // ri != newleaf->mRays.end(); ++ ri) 1490 1542 // (*ri).ray->UnMail(2); … … 1510 1562 1511 1563 1512 int VspKdTree::GetPvsSize(VspKd TreeNode *node, const AxisAlignedBox3 &box) const1513 { 1514 stack<VspKd TreeNode *> tstack;1564 int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const 1565 { 1566 stack<VspKdNode *> tstack; 1515 1567 tstack.push(mRoot); 1516 1568 … … 1520 1572 while (!tstack.empty()) 1521 1573 { 1522 VspKd TreeNode *node = tstack.top();1574 VspKdNode *node = tstack.top(); 1523 1575 tstack.pop(); 1524 1576 1525 1577 if (node->IsLeaf()) 1526 1578 { 1527 VspKd TreeLeaf *leaf = (VspKdTreeLeaf *)node;1579 VspKdLeaf *leaf = (VspKdLeaf *)node; 1528 1580 for (RayInfoContainer::iterator ri = leaf->mRays.begin(); 1529 1581 ri != leaf->mRays.end(); ++ ri) … … 1552 1604 else 1553 1605 { 1554 VspKd TreeInterior *in = dynamic_cast<VspKdTreeInterior *>(node);1606 VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 1555 1607 1556 1608 if (in->mAxis < 3) … … 1578 1630 float &avgRayContribution) 1579 1631 { 1580 stack<VspKd TreeNode *> tstack;1632 stack<VspKdNode *> tstack; 1581 1633 tstack.push(mRoot); 1582 1634 … … 1589 1641 while (!tstack.empty()) 1590 1642 { 1591 VspKd TreeNode *node = tstack.top();1643 VspKdNode *node = tstack.top(); 1592 1644 tstack.pop(); 1593 1645 if (node->IsLeaf()) 1594 1646 { 1595 1647 leaves++; 1596 VspKd TreeLeaf *leaf = (VspKdTreeLeaf *)node;1648 VspKdLeaf *leaf = (VspKdLeaf *)node; 1597 1649 float c = leaf->GetAvgRayContribution(); 1598 1650 … … 1605 1657 } 1606 1658 else { 1607 VspKd TreeInterior *in = (VspKdTreeInterior *)node;1659 VspKdInterior *in = (VspKdInterior *)node; 1608 1660 // both nodes for directional splits 1609 1661 tstack.push(in->GetFront()); … … 1621 1673 SimpleRayContainer &rays) 1622 1674 { 1623 stack<VspKd TreeNode *> tstack;1675 stack<VspKdNode *> tstack; 1624 1676 tstack.push(mRoot); 1625 1677 1626 1678 while (!tstack.empty()) 1627 1679 { 1628 VspKd TreeNode *node = tstack.top();1680 VspKdNode *node = tstack.top(); 1629 1681 tstack.pop(); 1630 1682 1631 1683 if (node->IsLeaf()) 1632 1684 { 1633 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);1685 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 1634 1686 1635 1687 float c = leaf->GetAvgRayContribution(); … … 1649 1701 else 1650 1702 { 1651 VspKd TreeInterior *in =1652 dynamic_cast<VspKd TreeInterior *>(node);1703 VspKdInterior *in = 1704 dynamic_cast<VspKdInterior *>(node); 1653 1705 // both nodes for directional splits 1654 1706 tstack.push(in->GetFront()); … … 1663 1715 float VspKdTree::GetAvgPvsSize() 1664 1716 { 1665 stack<VspKd TreeNode *> tstack;1717 stack<VspKdNode *> tstack; 1666 1718 tstack.push(mRoot); 1667 1719 … … 1671 1723 while (!tstack.empty()) 1672 1724 { 1673 VspKd TreeNode *node = tstack.top();1725 VspKdNode *node = tstack.top(); 1674 1726 tstack.pop(); 1675 1727 1676 1728 if (node->IsLeaf()) 1677 1729 { 1678 VspKd TreeLeaf *leaf = (VspKdTreeLeaf *)node;1730 VspKdLeaf *leaf = (VspKdLeaf *)node; 1679 1731 // update pvs size 1680 1732 leaf->UpdatePvsSize(); … … 1684 1736 else 1685 1737 { 1686 VspKd TreeInterior *in = (VspKdTreeInterior *)node;1738 VspKdInterior *in = (VspKdInterior *)node; 1687 1739 // both nodes for directional splits 1688 1740 tstack.push(in->GetFront()); … … 1694 1746 } 1695 1747 1696 VspKd TreeNode *VspKdTree::GetRoot() const1748 VspKdNode *VspKdTree::GetRoot() const 1697 1749 { 1698 1750 return mRoot; 1699 1751 } 1700 1752 1701 AxisAlignedBox3 VspKdTree::GetBBox(VspKd TreeNode *node) const1753 AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const 1702 1754 { 1703 1755 if (node->mParent == NULL) … … 1705 1757 1706 1758 if (!node->IsLeaf()) 1707 return (dynamic_cast<VspKd TreeInterior *>(node))->mBox;1759 return (dynamic_cast<VspKdInterior *>(node))->mBox; 1708 1760 1709 1761 if (node->mParent->mAxis >= 3) … … 1740 1792 return 1741 1793 (sizeof(VspKdTree) + 1742 mStat.Leaves() * sizeof(VspKd TreeLeaf) +1743 mStat.Interior() * sizeof(VspKd TreeInterior) +1794 mStat.Leaves() * sizeof(VspKdLeaf) + 1795 mStat.Interior() * sizeof(VspKdInterior) + 1744 1796 mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f); 1745 1797 } … … 1750 1802 } 1751 1803 1752 int VspKdTree::ComputePvsSize(VspKd TreeNode *node,1804 int VspKdTree::ComputePvsSize(VspKdNode *node, 1753 1805 const RayInfoContainer &globalRays) const 1754 1806 { … … 1766 1818 } 1767 1819 1768 void VspKdTree::CollectLeaves(vector<VspKd TreeLeaf *> &leaves) const1769 { 1770 stack<VspKd TreeNode *> nodeStack;1820 void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const 1821 { 1822 stack<VspKdNode *> nodeStack; 1771 1823 nodeStack.push(mRoot); 1772 1824 1773 1825 while (!nodeStack.empty()) 1774 1826 { 1775 VspKd TreeNode *node = nodeStack.top();1827 VspKdNode *node = nodeStack.top(); 1776 1828 1777 1829 nodeStack.pop(); … … 1779 1831 if (node->IsLeaf()) 1780 1832 { 1781 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);1833 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 1782 1834 leaves.push_back(leaf); 1783 1835 } 1784 1836 else 1785 1837 { 1786 VspKd TreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);1838 VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 1787 1839 1788 1840 nodeStack.push(interior->GetBack()); … … 1792 1844 } 1793 1845 1794 int VspKdTree::FindNeighbors(VspKd TreeLeaf *n,1795 vector<VspKd TreeLeaf *> &neighbors,1846 int VspKdTree::FindNeighbors(VspKdLeaf *n, 1847 vector<VspKdLeaf *> &neighbors, 1796 1848 bool onlyUnmailed) 1797 1849 { 1798 stack<VspKd TreeNode *> nodeStack;1850 stack<VspKdNode *> nodeStack; 1799 1851 1800 1852 nodeStack.push(mRoot); … … 1804 1856 while (!nodeStack.empty()) 1805 1857 { 1806 VspKd TreeNode *node = nodeStack.top();1858 VspKdNode *node = nodeStack.top(); 1807 1859 nodeStack.pop(); 1808 1860 1809 1861 if (node->IsLeaf()) 1810 1862 { 1811 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);1863 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 1812 1864 1813 1865 if (leaf != n && (!onlyUnmailed || !leaf->Mailed())) … … 1816 1868 else 1817 1869 { 1818 VspKd TreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);1870 VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 1819 1871 1820 1872 if (interior->mPosition > box.Max(interior->mAxis)) … … 1837 1889 } 1838 1890 1839 void VspKdTree::MergeLeaves() 1840 { 1841 vector<VspKdTreeLeaf *> leaves; 1842 priority_queue<LeafPair> mergeCandidates; 1843 vector<VspKdTreeLeaf *> neighbors; 1844 1891 1892 1893 void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm) 1894 { 1895 mViewCellsManager = vcm; 1896 } 1897 1898 1899 int VspKdTree::CastRay(Ray &ray) 1900 { 1901 int hits = 0; 1902 1903 stack<RayTraversalData> tStack; 1904 1905 float maxt = 1e6; 1906 float mint = 0; 1907 1908 Intersectable::NewMail(); 1909 1910 if (!mBox.GetMinMaxT(ray, &mint, &maxt)) 1911 return 0; 1912 1913 if (mint < 0) 1914 mint = 0; 1915 1916 maxt += Limits::Threshold; 1917 1918 Vector3 entp = ray.Extrap(mint); 1919 Vector3 extp = ray.Extrap(maxt); 1920 1921 VspKdNode *node = mRoot; 1922 VspKdNode *farChild; 1923 1924 float position; 1925 int axis; 1926 1927 while (1) 1928 { 1929 if (!node->IsLeaf()) 1930 { 1931 VspKdInterior *in = dynamic_cast<VspKdInterior *>(node); 1932 position = in->mPosition; 1933 axis = in->mAxis; 1934 1935 if (entp[axis] <= position) 1936 { 1937 if (extp[axis] <= position) 1938 { 1939 node = in->mBack; 1940 // cases N1,N2,N3,P5,Z2,Z3 1941 continue; 1942 } else 1943 { 1944 // case N4 1945 node = in->mBack; 1946 farChild = in->mFront; 1947 } 1948 } 1949 else 1950 { 1951 if (position <= extp[axis]) 1952 { 1953 node = in->mFront; 1954 // cases P1,P2,P3,N5,Z1 1955 continue; 1956 } 1957 else 1958 { 1959 node = in->mFront; 1960 farChild = in->mBack; 1961 // case P4 1962 } 1963 } 1964 1965 // $$ modification 3.5.2004 - hints from Kamil Ghais 1966 // case N4 or P4 1967 float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis); 1968 //tStack.push(RayTraversalData(farChild, extp, maxt)); //TODO 1969 extp = ray.GetLoc() + ray.GetDir()*tdist; 1970 maxt = tdist; 1971 } 1972 else 1973 { 1974 // compute intersection with all objects in this leaf 1975 /*KdLeaf *leaf = (KdLeaf *) node; 1976 if (ray.mFlags & Ray::STORE_KDLEAVES) 1977 ray.kdLeaves.push_back(leaf); 1978 1979 ObjectContainer::const_iterator mi; 1980 for ( mi = leaf->mObjects.begin(); mi != leaf->mObjects.end(); mi++) 1981 { 1982 Intersectable *object = *mi; 1983 if (!object->Mailed() ) 1984 { 1985 object->Mail(); 1986 if (ray.mFlags & Ray::STORE_TESTED_OBJECTS) 1987 ray.testedObjects.push_back(object); 1988 hits += object->CastRay(ray); 1989 } 1990 } 1991 1992 if (hits && ray.GetType() == Ray::LOCAL_RAY) 1993 if (ray.intersections[0].mT <= maxt) 1994 break; 1995 1996 // get the next node from the stack 1997 if (tStack.empty()) 1998 break; 1999 2000 entp = extp; 2001 mint = maxt; 2002 if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f) 2003 break; 2004 2005 RayTraversalData &s = tStack.top(); 2006 node = s.mNode; 2007 extp = s.mExitPoint; 2008 maxt = s.mMaxT; 2009 tStack.pop(); 2010 */ 2011 } 2012 } 2013 2014 return hits; 2015 } 2016 2017 2018 void VspKdTree::GenerateViewCell(VspKdLeaf *leaf) 2019 { 2020 RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end(); 2021 2022 VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCellsManager->GenerateViewCell()); 2023 leaf->SetViewCell(vc); 2024 2025 vc->SetSize(GetBBox(leaf).GetVolume()); 2026 vc->mVspKdLeaves.push_back(leaf); 2027 2028 for (it = leaf->GetRays().begin(); it != it_end; ++ it) 2029 { 2030 VssRay *ray = (*it).mRay; 2031 2032 if (ray->mTerminationObject) 2033 vc->GetPvs().AddSample(ray->mTerminationObject); 2034 2035 if (ray->mOriginObject) 2036 vc->GetPvs().AddSample(ray->mOriginObject); 2037 } 2038 } 2039 2040 2041 void VspKdTree::EvaluateViewCellsStats(ViewCellsStatistics &vcStat) const 2042 { 2043 vcStat.Reset(); 2044 2045 stack<VspKdNode *> nodeStack; 2046 nodeStack.push(mRoot); 2047 2048 ViewCell::NewMail(); 2049 2050 // exclude root cell 2051 //mRootCell->Mail(); 2052 2053 while (!nodeStack.empty()) 2054 { 2055 VspKdNode *node = nodeStack.top(); 2056 nodeStack.pop(); 2057 2058 if (node->IsLeaf()) 2059 { 2060 ++ vcStat.leaves; 2061 2062 VspKdViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell; 2063 2064 if (!viewCell->Mailed()) 2065 { 2066 viewCell->Mail(); 2067 2068 ++ vcStat.viewCells; 2069 const int pvsSize = viewCell->GetPvs().GetSize(); 2070 2071 vcStat.pvs += pvsSize; 2072 2073 if (pvsSize < 1) 2074 ++ vcStat.emptyPvs; 2075 2076 if (pvsSize > vcStat.maxPvs) 2077 vcStat.maxPvs = pvsSize; 2078 2079 if (pvsSize < vcStat.minPvs) 2080 vcStat.minPvs = pvsSize; 2081 2082 if ((int)viewCell->mVspKdLeaves.size() > vcStat.maxLeaves) 2083 vcStat.maxLeaves = (int)viewCell->mVspKdLeaves.size(); 2084 } 2085 } 2086 else 2087 { 2088 VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 2089 2090 nodeStack.push(interior->GetFront()); 2091 nodeStack.push(interior->GetBack()); 2092 } 2093 } 2094 } 2095 2096 2097 bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2) 2098 { 2099 //-- change pointer to view cells of all leaves associated with the previous view cells 2100 VspKdViewCell *fVc = l1->GetViewCell(); 2101 VspKdViewCell *bVc = l2->GetViewCell(); 2102 2103 VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>( 2104 mViewCellsManager->MergeViewCells(*fVc, *bVc)); 2105 2106 // if merge was unsuccessful 2107 if (!vc) return false; 2108 2109 // set new size of view cell 2110 vc->SetSize(fVc->GetSize() + bVc->GetSize()); 2111 2112 vector<VspKdLeaf *> fLeaves = fVc->mVspKdLeaves; 2113 vector<VspKdLeaf *> bLeaves = bVc->mVspKdLeaves; 2114 2115 vector<VspKdLeaf *>::const_iterator it; 2116 2117 //-- change view cells of all the other leaves the view cell belongs to 2118 for (it = fLeaves.begin(); it != fLeaves.end(); ++ it) 2119 { 2120 (*it)->SetViewCell(vc); 2121 vc->mVspKdLeaves.push_back(*it); 2122 } 2123 2124 for (it = bLeaves.begin(); it != bLeaves.end(); ++ it) 2125 { 2126 (*it)->SetViewCell(vc); 2127 vc->mVspKdLeaves.push_back(*it); 2128 } 2129 2130 // clean up old view cells 2131 DEL_PTR(fVc); 2132 DEL_PTR(bVc); 2133 2134 return true; 2135 } 2136 2137 2138 2139 int VspKdTree::MergeLeaves() 2140 { 2141 vector<VspKdLeaf *> leaves; 2142 priority_queue<MergeCandidate> mergeQueue; 2143 2144 // collect the leaves, e.g., the "voxels" that will build the view cells 1845 2145 CollectLeaves(leaves); 1846 2146 1847 VspKdTreeLeaf::NewMail(); 1848 1849 vector<VspKdTreeLeaf *>::const_iterator it, it_end = leaves.end(); 1850 1851 2147 int vcSize = (int)leaves.size(); 2148 2149 VspKdLeaf::NewMail(); 2150 2151 vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end(); 2152 2153 // generate view cells 1852 2154 for (it = leaves.begin(); it != it_end; ++ it) 1853 { 1854 VspKdTreeLeaf *leaf = *it; 1855 2155 GenerateViewCell(*it); 2156 2157 // find merge candidates and push them into queue 2158 for (it = leaves.begin(); it != it_end; ++ it) 2159 { 2160 VspKdLeaf *leaf = *it; 2161 2162 // no leaf is part of two merge candidates 1856 2163 if (!leaf->Mailed()) 1857 2164 { 2165 leaf->Mail(); 2166 2167 vector<VspKdLeaf *> neighbors; 1858 2168 FindNeighbors(leaf, neighbors, true); 1859 2169 1860 vector<VspKdTreeLeaf *>::const_iterator nit, nit_end = neighbors.end(); 1861 1862 for (nit = neighbors.begin(); nit != neighbors.end(); ++ nit) 1863 mergeCandidates.push(LeafPair(leaf, *nit)); 2170 vector<VspKdLeaf *>::const_iterator nit, 2171 nit_end = neighbors.end(); 2172 2173 for (nit = neighbors.begin(); nit != nit_end; ++ nit) 2174 mergeQueue.push(MergeCandidate(leaf, *nit)); 2175 } 2176 } 2177 2178 int merged = 0; 2179 2180 float savedMaxCostRatio = 0; 2181 2182 Debug << "merge cost " << mergeQueue.top().GetMergeCost() << " of " << mMaxCostRatio << endl; 2183 2184 // use priority queue to merge leaves 2185 while (!mergeQueue.empty() && 2186 ((mMaxViewCells < vcSize) || 2187 (mergeQueue.top().GetMergeCost() < mMaxCostRatio))) 2188 { 2189 ViewCell::NewMail(); 2190 2191 Debug << "=====================" << endl; 2192 MergeCandidate mc = mergeQueue.top(); 2193 mergeQueue.pop(); 2194 2195 if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) 2196 // both view cells the same! 2197 { 2198 Debug << "same view cell!!" << endl; 2199 -- vcSize; 2200 2201 continue; 2202 } 2203 2204 if (mc.Valid()) 2205 { 2206 mc.GetLeaf1()->GetViewCell()->Mail(); 2207 mc.GetLeaf2()->GetViewCell()->Mail(); 1864 2208 1865 leaf->Mail(); 1866 } 1867 } 1868 } 1869 2209 Debug << "merging cells with cost " << mc.GetMergeCost() << " of " << mMaxCostRatio << endl; 2210 savedMaxCostRatio = mc.GetMergeCost(); 2211 2212 MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2()); 2213 2214 ++ merged; 2215 -- vcSize; 2216 } 2217 // merge candidate not valid, because one of the leaves was already 2218 // merged with another one 2219 else 2220 { 2221 Debug << "not valid " << mc.GetMergeCost() << endl; 2222 2223 // validate and reinsert into queue 2224 mc.SetValid(); 2225 Debug << "ag. valid " << mc.GetMergeCost() << endl; 2226 2227 mergeQueue.push(mc); 2228 } 2229 } 2230 2231 if (mergeQueue.empty()) 2232 Debug << "empty queue" << endl; 2233 2234 Debug << "max cost ratio: " << savedMaxCostRatio << endl; 2235 2236 return merged; 2237 } 1870 2238 1871 2239 … … 1875 2243 1876 2244 1877 MergeCandidate::MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2): 1878 mLeaf1(l1), mLeaf2(l2) 1879 {} 1880 1881 float MergeCandidate::EvaluateMergeCost() const 1882 { 1883 // pvs difference 1884 VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell()); 1885 VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell()); 2245 MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2): 2246 mMergeCost(0), 2247 mLeaf1(l1), 2248 mLeaf2(l2), 2249 mLeaf1Id(l1->GetViewCell()->mMailbox), 2250 mLeaf2Id(l2->GetViewCell()->mMailbox) 2251 { 2252 EvalMergeCost(); 2253 } 2254 2255 2256 void MergeCandidate::EvalMergeCost() 2257 { 2258 // compute pvs differences 2259 VspKdViewCell *vc1 = mLeaf1->GetViewCell(); 2260 VspKdViewCell *vc2 = mLeaf2->GetViewCell(); 2261 2262 //VspKdViewCell *vc1 = dynamic_cast<VspKdViewCell *>(mLeaf1->GetViewCell()); 2263 //VspKdViewCell *vc2 = dynamic_cast<VspKdViewCell *>(mLeaf2->GetViewCell()); 1886 2264 1887 2265 const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs()); 1888 1889 //const int diff2 = vc2->GetPvs().Diff(vc1->GetPvs()); 1890 //const float simDiff = (float)max(diff1, diff2); 1891 2266 const int vcPvs = diff1 + vc1->GetPvs().GetSize(); 2267 2268 //-- compute ratio of old cost 2269 //-- (added size of left and right view cell times pvs size) 2270 //-- to new rendering cost (size of merged view cell times pvs size) 1892 2271 const float oldCost = 1893 vc1->GetSize() * vc1->GetPvs().GetSize() + 1894 vc2->GetSize() * vc2->GetPvs().GetSize(); 1895 1896 const float mergedPvsCost = 1897 (diff1 + vc1->GetPvs().GetSize()) * 1898 (vc1->GetSize() + vc2->GetSize()); 1899 1900 return mergedPvsCost / oldCost; 1901 } 2272 (float)vc1->GetPvs().GetSize() * vc1->GetSize() + 2273 (float)vc2->GetPvs().GetSize() * vc2->GetSize(); 2274 2275 const float newCost = 2276 (float)vcPvs * (vc1->GetSize() + vc2->GetSize()); 2277 2278 mMergeCost = newCost / oldCost; 2279 2280 Debug << "******************************" << endl; 2281 Debug << "pvs size: " << vcPvs << " max: " << sMaxPvsSize << endl; 2282 if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large 2283 mMergeCost += 1.0; 2284 2285 Debug << "old cost: " << oldCost << endl; 2286 Debug << "new cost: " << newCost << endl; 2287 } 2288 2289 void MergeCandidate::SetLeaf1(VspKdLeaf *l) 2290 { 2291 mLeaf1 = l; 2292 } 2293 2294 void MergeCandidate::SetLeaf2(VspKdLeaf *l) 2295 { 2296 mLeaf2 = l; 2297 } 2298 2299 VspKdLeaf *MergeCandidate::GetLeaf1() 2300 { 2301 return mLeaf1; 2302 } 2303 2304 VspKdLeaf *MergeCandidate::GetLeaf2() 2305 { 2306 return mLeaf2; 2307 } 2308 2309 bool MergeCandidate::Valid() const 2310 { 2311 //Debug << mLeaf1->GetViewCell()->mMailbox << " " << mLeaf1Id << endl; 2312 //Debug << mLeaf2->GetViewCell()->mMailbox << " " << mLeaf2Id << endl; 2313 2314 return 2315 (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) && 2316 (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id); 2317 } 2318 2319 float MergeCandidate::GetMergeCost() const 2320 { 2321 return mMergeCost; 2322 } 2323 2324 void MergeCandidate::SetValid() 2325 { 2326 mLeaf1Id = mLeaf1->GetViewCell()->mMailbox; 2327 mLeaf2Id = mLeaf2->GetViewCell()->mMailbox; 2328 2329 EvalMergeCost(); 2330 } -
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
r454 r462 34 34 #include "Containers.h" 35 35 36 class VspKdTreeLeaf; 36 class VspKdLeaf; 37 class ViewCellsManager; 38 class VspKdViewCell; 39 class ViewCellsStatistics; 40 37 41 38 42 /** … … 42 46 { 43 47 public: 44 VspKdTreeLeaf *mLeaf1; 45 VspKdTreeLeaf *mLeaf2; 46 47 MergeCandidate(VspKdTreeLeaf *l1, VspKdTreeLeaf *l2); 48 49 MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2); 48 50 49 51 /** Computes PVS difference between the leaves. … … 51 53 //int ComputePvsDifference() const; 52 54 53 /** Evaluates the merge costs of this leaf. 54 */ 55 float EvaluateMergeCost() const; 56 57 friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb) 55 /** If this merge pair is still valid. 56 */ 57 bool Valid() const; 58 59 /** Sets this merge candidate to be valid. 60 */ 61 void SetValid(); 62 63 friend bool operator<(const MergeCandidate &leafa, const MergeCandidate &leafb) 58 64 { 59 return leaf a.EvaluateMergeCost() < leafb.EvaluateMergeCost();65 return leafb.GetMergeCost() < leafa.GetMergeCost(); 60 66 } 67 68 void SetLeaf1(VspKdLeaf *l); 69 void SetLeaf2(VspKdLeaf *l); 70 71 VspKdLeaf *GetLeaf1(); 72 VspKdLeaf *GetLeaf2(); 73 74 /** Merge cost of this candidate pair. 75 */ 76 float GetMergeCost() const; 77 78 /// maximal pvs size 79 static int sMaxPvsSize; 80 81 protected: 82 83 /** Evaluates the merge costs of the leaves. 84 */ 85 void EvalMergeCost(); 86 87 int mLeaf1Id; 88 int mLeaf2Id; 89 90 float mMergeCost; 91 92 VspKdLeaf *mLeaf1; 93 VspKdLeaf *mLeaf2; 61 94 }; 62 95 … … 142 175 143 176 144 class VspKd TreeInterior;177 class VspKdInterior; 145 178 146 179 147 180 /** Abstract superclass of Vsp-Kd-Tree nodes. 148 181 */ 149 class VspKd TreeNode182 class VspKdNode 150 183 { 151 184 public: … … 157 190 /** Constructs new interior node from the parent node. 158 191 */ 159 inline VspKd TreeNode(VspKdTreeInterior *p);192 inline VspKdNode(VspKdInterior *p); 160 193 161 194 /** Destroys this node and the subtree. 162 195 */ 163 virtual ~VspKd TreeNode();196 virtual ~VspKdNode(); 164 197 165 198 /** Type of the node (Einterior or ELeaf) … … 181 214 /** Returns parent node. 182 215 */ 183 VspKd TreeInterior *GetParent() const;216 VspKdInterior *GetParent() const; 184 217 185 218 /** Sets parent node. 186 219 */ 187 void SetParent(VspKd TreeInterior *p);220 void SetParent(VspKdInterior *p); 188 221 189 222 protected: … … 192 225 193 226 /// link to the parent 194 VspKd TreeInterior *mParent;227 VspKdInterior *mParent; 195 228 196 229 enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z, SPLIT_DIRX, SPLIT_DIRY, SPLIT_DIRZ}; … … 206 239 // KD-tree node - interior node 207 240 // -------------------------------------------------------------- 208 class VspKd TreeInterior: public VspKdTreeNode241 class VspKdInterior: public VspKdNode 209 242 { 210 243 public: … … 213 246 /** Constructs new interior node from parent node. 214 247 */ 215 VspKd TreeInterior(VspKdTreeInterior *p);248 VspKdInterior(VspKdInterior *p); 216 249 217 250 virtual int GetAccessTime(); … … 219 252 virtual int Type() const; 220 253 221 virtual ~VspKd TreeInterior();254 virtual ~VspKdInterior(); 222 255 223 256 virtual void Print(ostream &s) const; … … 225 258 /** Returns back child. 226 259 */ 227 inline VspKd TreeNode *GetBack() const;260 inline VspKdNode *GetBack() const; 228 261 /** Returns front child. 229 262 */ 230 inline VspKd TreeNode *GetFront() const;263 inline VspKdNode *GetFront() const; 231 264 232 265 protected: … … 234 267 /** Sets pointers to back child and front child. 235 268 */ 236 void SetupChildLinks(VspKd TreeNode *b, VspKdTreeNode *f);269 void SetupChildLinks(VspKdNode *b, VspKdNode *f); 237 270 238 271 /** Replaces the pointer to oldChild with a pointer to newChild. 239 272 */ 240 void ReplaceChildLink(VspKd TreeNode *oldChild, VspKdTreeNode *newChild);273 void ReplaceChildLink(VspKdNode *oldChild, VspKdNode *newChild); 241 274 242 275 /** Computes intersection of the ray with the node boundaries. … … 248 281 249 282 // pointers to children 250 VspKd TreeNode *mBack;251 VspKd TreeNode *mFront;283 VspKdNode *mBack; 284 VspKdNode *mFront; 252 285 253 286 // the bbox of the node … … 263 296 // KD-tree node - leaf node 264 297 // -------------------------------------------------------------- 265 class VspKd TreeLeaf: public VspKdTreeNode298 class VspKdLeaf: public VspKdNode 266 299 { 267 300 public: … … 272 305 @param nRays preallocates memory to store this number of rays 273 306 */ 274 VspKd TreeLeaf(VspKdTreeInterior *p, const int nRays);275 276 virtual ~VspKd TreeLeaf();307 VspKdLeaf(VspKdInterior *p, const int nRays); 308 309 virtual ~VspKdLeaf(); 277 310 278 311 virtual int Type() const; … … 317 350 bool Mailed() const; 318 351 319 bool Mailed(const int mail); 320 352 /** Returns true if mail equals the leaf mail box. 353 */ 354 bool Mailed(const int mail) const; 355 356 void SetViewCell(VspKdViewCell *viewCell); 357 358 /** Returns mail box of this leaf. 359 */ 360 int GetMailbox() const; 361 362 /** Returns view cell associated with this leaf. 363 */ 364 VspKdViewCell *GetViewCell(); 365 366 //////////////////////////////////////////// 367 321 368 static void NewMail(); 322 369 323 static int mailID; 324 325 /** Returns view cell. 326 */ 327 ViewCell *GetViewCell(); 370 static int sMailId; 371 328 372 329 373 protected: … … 337 381 338 382 RayInfoContainer mRays; 383 384 /// true if mPvsSize is valid => PVS does not have to be updated 339 385 bool mValidPvs; 340 386 341 ViewCell *mViewCell; 387 /// the view cell associated with this leaf 388 VspKdViewCell *mViewCell; 389 342 390 private: 391 /// stores PVS size so we have to evaluate PVS size only once 343 392 int mPvsSize; 344 393 }; … … 380 429 struct TraversalData 381 430 { 382 VspKd TreeNode *mNode;431 VspKdNode *mNode; 383 432 AxisAlignedBox3 mBox; 384 433 int mDepth; … … 387 436 TraversalData() {} 388 437 389 TraversalData(VspKd TreeNode *n, const float p):438 TraversalData(VspKdNode *n, const float p): 390 439 mNode(n)//, mPriority(p) 391 440 {} 392 441 393 TraversalData(VspKd TreeNode *n, const AxisAlignedBox3 &b, const int d):442 TraversalData(VspKdNode *n, const AxisAlignedBox3 &b, const int d): 394 443 mNode(n), mBox(b), mDepth(d) {} 395 444 … … 406 455 { 407 456 // return a.node->queries.size() < b.node->queries.size(); 408 VspKd TreeLeaf *leafa = (VspKdTreeLeaf *) a.mNode;409 VspKd TreeLeaf *leafb = (VspKdTreeLeaf *) b.mNode;457 VspKdLeaf *leafa = (VspKdLeaf *) a.mNode; 458 VspKdLeaf *leafb = (VspKdLeaf *) b.mNode; 410 459 #if 0 411 460 return … … 446 495 { 447 496 RayInfo mRayData; 448 VspKd TreeNode *mNode;497 VspKdNode *mNode; 449 498 450 499 RayTraversalData() {} 451 500 452 RayTraversalData(VspKd TreeNode *n, const RayInfo &data):501 RayTraversalData(VspKdNode *n, const RayInfo &data): 453 502 mRayData(data), mNode(n) {} 454 503 }; … … 464 513 /** Returns bounding box of the specified node. 465 514 */ 466 AxisAlignedBox3 GetBBox(VspKd TreeNode *node) const;515 AxisAlignedBox3 GetBBox(VspKdNode *node) const; 467 516 468 517 const VspKdStatistics &GetStatistics() const; … … 470 519 /** Get the root of the tree. 471 520 */ 472 VspKd TreeNode *GetRoot() const;521 VspKdNode *GetRoot() const; 473 522 474 523 /** Returns average PVS size in tree. … … 484 533 /** Collects leaves of this tree. 485 534 */ 486 void CollectLeaves(vector<VspKd TreeLeaf *> &leaves) const;535 void CollectLeaves(vector<VspKdLeaf *> &leaves) const; 487 536 488 537 /** Merges leaves of this tree according to some criteria. 489 538 */ 490 voidMergeLeaves();539 int MergeLeaves(); 491 540 492 541 /** Finds neighbours of this node. … … 495 544 @param onlyUnmailed if only unmailed neighbors are collected 496 545 */ 497 int FindNeighbors(VspKd TreeLeaf *n,498 vector<VspKd TreeLeaf *> &neighbors,546 int FindNeighbors(VspKdLeaf *n, 547 vector<VspKdLeaf *> &neighbors, 499 548 bool onlyUnmailed); 549 550 551 /** Sets pointer to view cells manager. 552 */ 553 void SetViewCellsManager(ViewCellsManager *vcm); 554 555 /** A ray is cast possible intersecting the tree. 556 @param the ray that is cast. 557 @returns the number of intersections with objects stored in the tree. 558 */ 559 int CastRay(Ray &ray); 560 561 /** Collects view cells generated by this tree. 562 */ 563 void CollectViewCells(ViewCellContainer &viewCells) const; 564 565 /** Traverses tree and counts all view cells as well as their PVS size. 566 */ 567 void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 500 568 501 569 protected: … … 506 574 virtual void AddRays(VssRayContainer &add); 507 575 508 VspKd TreeNode *Locate(const Vector3 &v);509 510 VspKd TreeNode *SubdivideNode(VspKdTreeLeaf *leaf,576 VspKdNode *Locate(const Vector3 &v); 577 578 VspKdNode *SubdivideNode(VspKdLeaf *leaf, 511 579 const AxisAlignedBox3 &box, 512 580 AxisAlignedBox3 &backBox, 513 581 AxisAlignedBox3 &frontBox); 514 582 515 VspKd TreeNode *Subdivide(const TraversalData &tdata);516 517 int SelectPlane(VspKd TreeLeaf *leaf,583 VspKdNode *Subdivide(const TraversalData &tdata); 584 585 int SelectPlane(VspKdLeaf *leaf, 518 586 const AxisAlignedBox3 &box, 519 587 float &position, … … 523 591 int &pvsFront); 524 592 525 void SortSplitCandidates(VspKd TreeLeaf *node,593 void SortSplitCandidates(VspKdLeaf *node, 526 594 const int axis); 527 595 528 float BestCostRatioHeuristic(VspKd TreeLeaf *node,596 float BestCostRatioHeuristic(VspKdLeaf *node, 529 597 int &axis, 530 598 float &position, … … 534 602 int &pvsFront); 535 603 536 float BestCostRatioRegular(VspKd TreeLeaf *node,604 float BestCostRatioRegular(VspKdLeaf *node, 537 605 int &axis, 538 606 float &position, … … 542 610 int &pvsFront); 543 611 544 float EvalCostRatio(VspKd TreeLeaf *node,612 float EvalCostRatio(VspKdLeaf *node, 545 613 const int axis, 546 614 const float position, … … 551 619 552 620 553 VspKd TreeNode * SubdivideLeaf(VspKdTreeLeaf *leaf,621 VspKdNode * SubdivideLeaf(VspKdLeaf *leaf, 554 622 const float SAThreshold); 555 623 556 624 void RemoveRay(VssRay *ray, 557 vector<VspKd TreeLeaf *> *affectedLeaves,625 vector<VspKdLeaf *> *affectedLeaves, 558 626 const bool removeAllScheduledRays); 559 627 … … 568 636 int GetRootPvsSize() const; 569 637 570 int GetPvsSize(VspKd TreeNode *node, const AxisAlignedBox3 &box) const;638 int GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const; 571 639 572 640 void GetRayContributionStatistics(float &minRayContribution, … … 580 648 @returns number of collapsed rays. 581 649 */ 582 int CollapseSubtree(VspKd TreeNode *sroot, const int time);650 int CollapseSubtree(VspKdNode *sroot, const int time); 583 651 584 652 int ReleaseMemory(const int time); 585 653 586 bool TerminationCriteriaMet(const VspKd TreeLeaf *leaf,654 bool TerminationCriteriaMet(const VspKdLeaf *leaf, 587 655 const AxisAlignedBox3 &box) const; 588 656 … … 590 658 @returns PVS size of the intersection of this node bounding box with the rays. 591 659 */ 592 int ComputePvsSize(VspKdTreeNode *node, const RayInfoContainer &globalRays) const; 593 660 int ComputePvsSize(VspKdNode *node, 661 const RayInfoContainer &globalRays) const; 662 663 664 /** Generates view cell for this leaf taking the ray contributions. 665 */ 666 void GenerateViewCell(VspKdLeaf *leaf); 667 668 /** Merges view cells of the two leaves. 669 */ 670 bool MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2); 671 672 594 673 protected: 595 674 … … 597 676 ///////////////////////////// 598 677 // The core pointer 599 VspKd TreeNode *mRoot;678 VspKdNode *mRoot; 600 679 601 680 ///////////////////////////// … … 615 694 616 695 // type of the splitting to use for the tree construction 617 enum {ESplitRegular, ESplitHeuristic 696 enum {ESplitRegular, ESplitHeuristic}; 618 697 int splitType; 619 698 … … 637 716 vector<SortableEntry> *mSplitCandidates; 638 717 718 ViewCellsManager *mViewCellsManager; 719 720 /// maximal cost ratio of a merge 721 float mMaxCostRatio; 722 639 723 ///////////////////////////// 640 724 // Construction parameters … … 658 742 float mTermMaxRayContribution; 659 743 744 /// if only the "driving axis", i.e., the axis with the biggest extent 745 /// should be used for subdivision 660 746 bool mOnlyDrivingAxis; 661 747 662 typedef std::pair<VspKdTreeLeaf *, VspKdTreeLeaf *> LeafPair; 748 /// maximal numbers of view cells 749 int mMaxViewCells; 663 750 664 751 ///////////////////////////// … … 667 754 668 755 669 #endif // __ LSDS_KDTREE_H__670 756 #endif // __VSP_KDTREE_H__ 757 -
trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp
r452 r462 578 578 579 579 //-- several visualizations and statistics 580 Debug << "===== Final view cells statistics ==========" << endl;581 582 580 mViewCellsManager->PrintStatistics(Debug); 583 581 -
trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.cpp
r459 r462 593 593 bool X3dExporter::ExportVspKdTree(const VspKdTree &tree, const int maxPvs) 594 594 { 595 stack<VspKd TreeNode *> tStack;595 stack<VspKdNode *> tStack; 596 596 597 597 tStack.push(tree.GetRoot()); … … 604 604 while (!tStack.empty()) 605 605 { 606 VspKd TreeNode *node = tStack.top();606 VspKdNode *node = tStack.top(); 607 607 608 608 tStack.pop(); … … 634 634 if (maxPvs > 0) 635 635 { 636 VspKd TreeLeaf *leaf = dynamic_cast<VspKdTreeLeaf *>(node);636 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); 637 637 638 638 mForcedMaterial.mDiffuseColor.b = 1.0f; … … 650 650 else 651 651 { 652 VspKd TreeInterior *interior = dynamic_cast<VspKdTreeInterior *>(node);652 VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node); 653 653 tStack.push(interior->GetFront()); 654 654 tStack.push(interior->GetBack()); … … 658 658 //ExportMesh(mesh); 659 659 //DEL_PTR(mesh); 660 661 return true; 662 } 663 664 bool X3dExporter::ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs) 665 { 666 ViewCellContainer vc; 667 668 //if (maxPvs > 0) 669 mUseForcedMaterial = true; 670 671 tree.CollectViewCells(vc); 672 673 ViewCellContainer::const_iterator it, it_end = vc.end(); 674 675 for (it = vc.begin(); it != it_end; ++ it) 676 { 677 VspKdViewCell *viewCell = dynamic_cast<VspKdViewCell *>(*it); 678 679 if (maxPvs > 0) 680 { 681 mForcedMaterial.mDiffuseColor.b = 1.0f; 682 683 const float importance = (float)viewCell->GetPvs().GetSize() / (float)maxPvs; 684 mForcedMaterial.mDiffuseColor.r = importance; 685 mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r; 686 } 687 else 688 mForcedMaterial = RandomMaterial(); 689 690 ExportVspKdTreeViewCell(tree, *viewCell); 691 } 692 693 return true; 694 } 695 696 bool X3dExporter::ExportVspKdTreeViewCell(const VspKdTree &tree, const VspKdViewCell &vc) 697 { 698 vector<VspKdLeaf *>::const_iterator it, it_end = vc.mVspKdLeaves.end(); 699 700 for (it = vc.mVspKdLeaves.begin(); it != it_end; ++ it) 701 ExportBox(tree.GetBBox(*it)); 660 702 661 703 return true; -
trunk/VUT/GtpVisibilityPreprocessor/src/X3dExporter.h
r459 r462 21 21 class VspBspTree; 22 22 class BspNode; 23 class VspKdViewCell; 24 23 25 24 26 class X3dExporter : public Exporter … … 55 57 ); 56 58 57 bool 59 bool 58 60 ExportVspKdTree(const VspKdTree &tree, const int maxPvs); 59 61 … … 61 63 62 64 bool 63 ExportScene(SceneGraphNode *root) 65 ExportScene(SceneGraphNode *root) 64 66 { 65 67 ExportSceneNode(root); 66 68 return true; 67 69 } 68 69 virtual void 70 71 virtual void 70 72 ExportPolygon(Polygon3 *poly); 71 73 72 virtual void 74 virtual void 73 75 ExportPolygons(const PolygonContainer &polys); 74 76 … … 85 87 ExportMesh(Mesh *mesh); 86 88 87 virtual void 89 virtual void 88 90 ExportViewCell(ViewCell *viewCell); 89 91 90 virtual void 92 virtual void 91 93 ExportViewCells(const ViewCellContainer &viewCells); 92 94 93 virtual void 95 virtual void 94 96 ExportGeometry(const ObjectContainer &objects); 95 97 … … 102 104 const RgbColor &color = RgbColor(1,1,1)); 103 105 104 virtual void 106 virtual void 105 107 ExportBspSplitPlanes(const BspTree &tree); 106 107 virtual void 108 109 virtual void 108 110 ExportBspSplits(const BspTree &tree, const bool exportDepth); 109 111 … … 114 116 ExportBspViewCellPartition(const BspTree &tree, const int maxPvs = 0); 115 117 116 virtual void 118 virtual void 117 119 ExportBspLeaves(const BspTree &tree, const int maxPvs = 0); 118 120 119 121 120 virtual void 122 virtual void 121 123 ExportBspSplits(const VspBspTree &tree, const bool exportDepth); 122 124 123 125 virtual void 124 126 ExportBspViewCellPartition(const VspBspTree &tree, const int maxPvs = 0); 127 128 virtual bool 129 ExportVspKdTreeViewCells(const VspKdTree &tree, const int maxPvs = 0); 125 130 126 131 protected: … … 135 140 bool 136 141 ExportBspTreeRayDensity(const BspTree &tree); 137 142 138 143 void 139 144 AddBoxToMesh(const AxisAlignedBox3 &box, … … 141 146 142 147 void ExportBspNodeSplits(BspNode *root, 143 const AxisAlignedBox3 &box, 148 const AxisAlignedBox3 &box, 144 149 const bool exportDepth, 150 const bool epsilon); 145 151 152 bool ExportVspKdTreeViewCell(const VspKdTree &tree, const VspKdViewCell &vc); 146 153 147 const bool epsilon);148 154 149 155 void ExportViewpoint(const Vector3 &point, const Vector3 &direction); 150 156 151 157 }; 152 158 153 159 154 160
Note: See TracChangeset
for help on using the changeset viewer.