- Timestamp:
- 12/20/05 20:33:42 (19 years ago)
- Location:
- trunk/VUT/GtpVisibilityPreprocessor
- Files:
-
- 16 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env
r472 r473 13 13 #;../data/vienna/vienna-plane.x3d 14 14 # filename ../data/vienna/viewcells-25-sel.x3d 15 #filename ../data/atlanta/atlanta2.x3d15 filename ../data/atlanta/atlanta2.x3d 16 16 # filename ../data/soda/soda.dat 17 filename ../data/soda/soda5.dat17 # filename ../data/soda/soda5.dat 18 18 } 19 19 … … 71 71 72 72 RssTree { 73 useRss false73 #useRss false 74 74 epsilon 1e-6 75 75 … … 146 146 loadFromFile false 147 147 #type kdTree 148 type vspKdTree148 #type vspKdTree 149 149 #type bspTree 150 #type vspBspTree150 type vspBspTree 151 151 152 152 #type sceneDependent … … 172 172 # filename ../data/vienna/viewcells-25.x3d 173 173 # filename ../data/vienna/viewcells-large-sel.x3d 174 } 175 176 177 Simulation { 178 objRenderCost 1.0 179 vcOverhead 7.0 180 moveSpeed 3.0 181 } 182 183 184 VspKdTree { 185 epsilon 1e-6 186 187 Construction { 188 samples 300000 189 } 190 191 Termination { 192 maxDepth 40 193 minPvs 5 194 minRays 500 195 minSize 0.1 196 maxCostRatio 0.9 197 missTolerance 4 198 maxRayContribution 0.2 199 } 200 201 maxTotalMemory 400 202 maxStaticMemory 200 203 204 splitType regular 205 #splitType heuristics 206 ct_div_ci 0.0 207 208 # maximal cost for merging a view cell 209 PostProcess { 210 maxCostRatio 5000000 211 minViewCells 100 212 maxPvsSize 50000 213 } 214 215 216 Visualization { 217 exportRays true 218 exportGeometry false 219 } 220 } 221 222 VspBspTree { 223 Construction { 224 samples 100000 225 epsilon 0.005 226 } 227 228 229 # random polygon = 1 230 # axis aligned = 2 231 # least ray splits = 256 232 # balanced rays = 512 233 # pvs = 1024 234 235 splitPlaneStrategy 1024 236 237 # maximal candidates for split planes 238 maxPolyCandidates 50 239 maxRayCandidates 50 240 241 # maximal tested rays for split cost heuristics 242 maxTests 10000 243 244 # factors for evaluating split plane costs 245 Factor { 246 leastRaySplits 1.0 247 balancedRays 1.0 248 pvs 1.0 249 } 250 251 Termination { 252 # parameters used for autopartition 253 minRays 100 254 minPolygons -1 255 maxDepth 30 256 minPvs 100 257 minArea 0.01 258 maxRayContribution 0.005 259 maxCostRatio 0.9 260 missTolerance 1 261 #maxAccRayLength 100 262 263 # used for pvs criterium 264 ct_div_ci 0.0 265 266 # axis aligned splits 267 AxisAligned { 268 minPolys 5000 269 minRays 500 270 minObjects 10 271 ct_div_ci 0.5 272 } 273 } 274 275 AxisAligned { 276 splitBorder 0.01 277 } 278 279 280 Visualization { 281 # x3d visualization of the split planes 282 exportSplits true 283 exportRays true 284 exportGeometry true 285 } 174 286 } 175 287 … … 247 359 ct_div_ci 0.0 248 360 361 maxCostRatio 0.9 362 249 363 # axis aligned splits 250 364 AxisAligned { … … 252 366 minRays 500 253 367 minObjects 10 254 maxCostRatio 0.9255 368 ct_div_ci 0.5 256 369 } … … 269 382 } 270 383 } 271 272 Simulation {273 objRenderCost 1.0274 vcOverhead 7.0275 moveSpeed 3.0276 }277 278 279 VspKdTree {280 epsilon 1e-6281 282 Construction {283 samples 300000284 }285 286 Termination {287 maxDepth 40288 minPvs 5289 minRays 500290 minSize 0.1291 maxCostRatio 0.9292 missTolerance 4293 maxRayContribution 0.2294 }295 296 maxTotalMemory 400297 maxStaticMemory 200298 299 splitType regular300 #splitType heuristics301 ct_div_ci 0.0302 303 # maximal cost for merging a view cell304 PostProcess {305 maxCostRatio 5000000306 minViewCells 100307 maxPvsSize 50000308 }309 310 311 Visualization {312 exportRays true313 exportGeometry false314 }315 }316 317 VspBspTree {318 Construction {319 samples 100000320 epsilon 0.005321 }322 323 324 # random polygon = 1325 # axis aligned = 2326 # least ray splits = 256327 # balanced rays = 512328 # pvs = 1024329 330 splitPlaneStrategy 1024331 332 # maximal candidates for split planes333 maxPolyCandidates 50334 maxRayCandidates 50335 336 # maximal tested rays for split cost heuristics337 maxTests 10000338 339 # factors for evaluating split plane costs340 Factor {341 leastRaySplits 1.0342 balancedRays 1.0343 pvs 1.0344 }345 346 Termination {347 # parameters used for autopartition348 minRays 100349 minPolygons -1350 maxDepth 30351 minPvs 100352 minArea 0.01353 maxRayContribution 0.005354 maxCostRatio 0.9355 missTolerance 4356 #maxAccRayLength 100357 358 # used for pvs criterium359 ct_div_ci 0.0360 361 # axis aligned splits362 AxisAligned {363 minPolys 5000364 minRays 500365 minObjects 10366 maxCostRatio 0.9367 ct_div_ci 0.5368 }369 }370 371 AxisAligned {372 splitBorder 0.01373 }374 375 376 Visualization {377 # x3d visualization of the split planes378 exportSplits true379 exportRays true380 exportGeometry false381 }382 } -
trunk/VUT/GtpVisibilityPreprocessor/src/Environment.cpp
r472 r473 1512 1512 "false"); 1513 1513 1514 RegisterOption("VspKdTree.Termination.maxCostRatio",1515 optFloat,1516 "-vsp_kd_term_max_cost_ratio=",1517 "1.5");1518 1519 1514 RegisterOption("VspKdTree.Termination.missTolerance", 1520 1515 optInt, … … 1727 1722 "5000"); 1728 1723 1729 RegisterOption("VspBspTree.Visualization.exportSplits",1730 optBool,1731 "-vsp_bsp_visualization.exportSplits",1732 "false");1733 1734 1724 RegisterOption("VspBspTree.Construction.samples", 1735 1725 optInt, … … 1746 1736 "-vsp_bsp_visualization.export_splits", 1747 1737 "false"); 1748 RegisterOption(" BspTree.Visualization.exportRays",1738 RegisterOption("VspBspTree.Visualization.exportRays", 1749 1739 optBool, 1750 1740 "-vsp_bsp_visualization.export_rays", -
trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp
r469 r473 175 175 176 176 int constructionSamples = 0; 177 178 if (strcmp(viewCellsStr, "kdTree") == 0) 179 { 180 mViewCellsManager = new KdViewCellsManager(mKdTree); 181 } 182 else if (strcmp(viewCellsStr, "bspTree") == 0) 183 { 184 mBspTree = new BspTree(); 185 186 Debug << "view cell type: Bsp" << endl; 187 188 environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 189 mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 190 } 191 else if (strcmp(viewCellsStr, "vspBspTree") == 0) 192 { 193 mVspBspTree = new VspBspTree(); 194 195 Debug << "view cell type: VspBsp" << endl; 196 197 environment->GetIntValue("VspBspTree.Construction.samples", constructionSamples); 198 mViewCellsManager = new VspBspViewCellsManager(mVspBspTree, constructionSamples); 199 } 200 else if (strcmp(viewCellsStr, "vspKdTree") == 0) 201 { 202 mVspKdTree = new VspKdTree(); 203 204 environment->GetIntValue("VspKdTree.Construction.samples", constructionSamples); 205 mViewCellsManager = new VspKdViewCellsManager(mVspKdTree, constructionSamples); 206 } 207 else if (strcmp(viewCellsStr, "sceneDependent") == 0) 208 { 209 //TODO 210 mBspTree = new BspTree(); 211 212 Debug << "view cell type: Bsp" << endl; 213 environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 214 mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 215 } 216 else 217 { 218 cerr<<"Wrong view cells type" << viewCellsStr << endl; 219 exit(1); 220 } 177 221 178 222 float objRenderCost = 0, vcOverhead = 0, moveSpeed = 0; … … 182 226 environment->GetFloatValue("Simulation.moveSpeed", moveSpeed); 183 227 184 mRenderSimulator = new RenderSimulator(objRenderCost, vcOverhead, moveSpeed); 185 186 if (strcmp(viewCellsStr, "kdTree") == 0) 187 { 188 mViewCellsManager = new KdViewCellsManager(mKdTree); 189 } 190 else if (strcmp(viewCellsStr, "bspTree") == 0) 191 { 192 mBspTree = new BspTree(); 193 194 Debug << "view cell type: Bsp" << endl; 195 196 environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 197 mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 198 } 199 else if (strcmp(viewCellsStr, "vspBspTree") == 0) 200 { 201 mVspBspTree = new VspBspTree(); 202 203 Debug << "view cell type: VspBsp" << endl; 204 205 environment->GetIntValue("VspBspTree.Construction.samples", constructionSamples); 206 mViewCellsManager = new VspBspViewCellsManager(mVspBspTree, constructionSamples); 207 } 208 else if (strcmp(viewCellsStr, "vspKdTree") == 0) 209 { 210 mVspKdTree = new VspKdTree(); 211 212 environment->GetIntValue("VspKdTree.Construction.samples", constructionSamples); 213 mViewCellsManager = new VspKdViewCellsManager(mVspKdTree, constructionSamples); 214 } 215 else if (strcmp(viewCellsStr, "sceneDependent") == 0) 216 { 217 //TODO 218 mBspTree = new BspTree(); 219 220 Debug << "view cell type: Bsp" << endl; 221 environment->GetIntValue("BspTree.Construction.samples", constructionSamples); 222 mViewCellsManager = new BspViewCellsManager(mBspTree, constructionSamples); 223 } 224 else 225 { 226 cerr<<"Wrong view cells type" << viewCellsStr << endl; 227 exit(1); 228 } 229 228 mRenderSimulator = 229 new RenderSimulator(mViewCellsManager, objRenderCost, vcOverhead, moveSpeed); 230 230 231 int postProcessSamples = 0; 231 232 int visSamples = 0; -
trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp
r468 r473 26 26 } 27 27 28 RenderSimulator::RenderSimulator() 28 RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager): 29 Renderer(viewCellsManager) 29 30 {} 30 31 31 RenderSimulator::RenderSimulator(float objRenderCost, 32 RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager, 33 float objRenderCost, 32 34 float vcOverhead, 33 35 float moveSpeed): 36 Renderer(viewCellsManager), 34 37 mObjRenderCost(objRenderCost), 35 38 mVcOverhead(vcOverhead), … … 75 78 // compute render time of PVS times probability that view point is in view cell 76 79 const float vcCost = pInVc * mViewCellsManager->GetRendercost(vc, mObjRenderCost); 77 80 78 81 // crossing the border of a view cell is depending on the move speed 79 82 // and the probability that a view cell border is crossed … … 82 85 //-- update statistics 83 86 renderTime += vcCost; 84 87 85 88 if (vcCost > mSimulationStatistics.maxCost) 86 89 mSimulationStatistics.maxCost = vcCost; -
trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.h
r468 r473 48 48 49 49 public: 50 RenderSimulator( );50 RenderSimulator(ViewCellsManager *viewCellsManager); 51 51 /** Constructor taking the estimated render cost, 52 52 the view cell overhead, 53 53 and the average move speed of the player into account. 54 54 */ 55 RenderSimulator(float objRendercost, float vcOverhead, float moveSpeed); 55 RenderSimulator(ViewCellsManager *viewCellsManager, 56 float objRendercost, 57 float vcOverhead, 58 float moveSpeed); 56 59 57 60 /** Sets estimated render time for a single object in the PVS. -
trunk/VUT/GtpVisibilityPreprocessor/src/RssPreprocessor.cpp
r469 r473 397 397 398 398 int totalSamples = 0; 399 400 /// Rays used for post processing and visualizations.401 RayContainer storedRays;402 399 403 400 AxisAlignedBox3 *box = new AxisAlignedBox3(mKdTree->GetBox()); … … 507 504 mViewCellsManager->GetVisualizationSamples()); 508 505 float p = desired/(float)mVssRays.size(); 509 // rssTree->CollectRays(storedRays, desired);506 510 507 for (int i=0; i < mVssRays.size(); i++) { 511 508 if (Random(1.0f) < p) … … 520 517 if (1) 521 518 mViewCellsManager->Visualize(mObjects, selectedRays); 522 523 CLEAR_CONTAINER(storedRays);524 519 } 525 520 -
trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp
r469 r473 151 151 // pickup a random face of each mesh 152 152 Mesh *mesh = mi->GetMesh(); 153 int face = (int)Random ((int)mesh->mFaces.size());153 int face = (int)RandomValue(0, (int)mesh->mFaces.size() - 1); 154 154 155 155 Polygon3 poly(mesh->mFaces[face], mesh); 156 156 poly.Scale(1.001f); 157 157 // now extend a random edge of the face 158 int edge = Random((int)poly.mVertices.size());158 int edge = (int)RandomValue(0, (int)poly.mVertices.size() - 1); 159 159 float t = RandomValue(0.0f, 1.0f); 160 160 Vector3 target = t*poly.mVertices[edge] + (1.0f-t)*poly.mVertices[(edge + 1)% … … 192 192 Debug << "Finding random neighbour" << endl; 193 193 for (int tries = 0; tries < 10; tries++) { 194 int index = Random(pvsSize);194 int index = (int)RandomValue(0, pvsSize - 1); 195 195 KdPvsData data; 196 196 KdNode *node; -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp
r472 r473 355 355 356 356 app << "#N_PMINRAYSLEAVES ( Percentage of leaves with minimal number of rays)\n" 357 << minRaysNodes * 100 / (double)Leaves() << endl; 357 << minRaysNodes * 100 / (double)Leaves() << endl; 358 359 app << "#N_MAXCOSTNODES ( Percentage of leaves with terminated because of max cost ratio )\n" 360 << maxCostNodes * 100 / (double)Leaves() << endl; 358 361 359 362 app << "#N_PMINAREALEAVES ( Percentage of leaves with mininum area )\n" … … 412 415 mRoot = new BspLeaf(); 413 416 414 tStack.push(BspTraversalData(mRoot, polys, 0, mRootCell, new BoundedRayContainer(), 0, 415 mBox.SurfaceArea(), new BspNodeGeometry())); 417 tStack.push(BspTraversalData(mRoot, 418 polys, 419 0, 420 mRootCell, 421 new BoundedRayContainer(), 422 0, 423 mBox.SurfaceArea(), 424 new BspNodeGeometry())); 416 425 417 426 while (!tStack.empty()) … … 1142 1151 if (!data.mPolygons->empty()) 1143 1152 { 1144 Polygon3 *nextPoly = (*data.mPolygons)[ Random((int)data.mPolygons->size())];1153 Polygon3 *nextPoly = (*data.mPolygons)[(int)RandomValue(0, (int)data.mPolygons->size() - 1)]; 1145 1154 return nextPoly->GetSupportingPlane(); 1146 1155 } 1147 1156 else 1148 1157 { 1149 const int candidateIdx = Random((int)data.mRays->size());1158 const int candidateIdx = (int)RandomValue(0, (int)data.mRays->size() - 1); 1150 1159 BoundedRay *bRay = (*data.mRays)[candidateIdx]; 1151 1160 … … 1177 1186 int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates); 1178 1187 1179 int candidateIdx = limit ;1188 int candidateIdx = limit - 1; 1180 1189 1181 1190 for (int i = 0; i < limit; ++ i) … … 1207 1216 for (int i = 0; i < mMaxRayCandidates / 2; ++ i) 1208 1217 { 1209 candidateIdx = Random((int)rays->size());1218 candidateIdx = (int)RandomValue(0, (int)rays->size() - 1); 1210 1219 BoundedRay *bRay = (*rays)[candidateIdx]; 1211 1220 … … 1242 1251 for (int j = 0; j < 3; j ++) 1243 1252 { 1244 idx[j] = Random((int)rays->size() * 2);1253 idx[j] = (int)RandomValue(0, (int)rays->size() * 2 - 1); 1245 1254 1246 1255 if (idx[j] >= (int)rays->size()) … … 1279 1288 int BspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys) 1280 1289 { 1281 const int candidateIdx = Random(currentIdx --);1290 const int candidateIdx = (int)RandomValue(0, currentIdx --); 1282 1291 1283 1292 // swap candidates to avoid testing same plane 2 times … … 1285 1294 1286 1295 return currentIdx; 1287 //return Random((int)polys.size());1296 //return (int)RandomValue(0, (int)polys.size() - 1); 1288 1297 } 1289 1298 … … 1329 1338 for (int i = 0; i < limit; ++ i) 1330 1339 { 1331 const int testIdx = useRand ? Random(limit) : i;1340 const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i; 1332 1341 1333 1342 Polygon3 *poly = polys[testIdx]; … … 1494 1503 for (int i = 0; i < limit; ++ i) 1495 1504 { 1496 const int testIdx = useRand ? Random(limit) : i;1505 const int testIdx = useRand ? (int)RandomValue(0, limit - 1) : i; 1497 1506 1498 1507 BoundedRay *bRay = rays[testIdx]; … … 2076 2085 { 2077 2086 int splits = 0; 2078 2087 2079 2088 while (!rays.empty()) 2080 2089 { -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.h
r472 r473 102 102 // minimum area nodes 103 103 int minAreaNodes; 104 104 /// nodes termination because of max cost ratio; 105 int maxCostNodes; 105 106 // max number of rays per node 106 107 int maxObjectRefs; … … 144 145 maxRayContribNodes = 0; 145 146 minAreaNodes = 0; 147 maxCostNodes = 0; 146 148 147 149 contributingSamples = 0; … … 346 348 347 349 typedef std::stack<BspTraversalData> BspTraversalStack; 348 //typedef std::priority_queue<BspTraversalData> BspTraversalStack;349 350 /** Default constructorcreating an empty tree.350 351 /** Default constructor reading the environment file and 352 creating an empty tree. 351 353 */ 352 354 BspTree(); 353 355 /** Destroys tree and nodes. 356 */ 354 357 ~BspTree(); 355 358 -
trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsManager.cpp
r471 r473 266 266 VssRayContainer &savedRays) const 267 267 { 268 const int limit = min (mConstructionSamples, (int)sourceRays.size()); 269 268 const int limit = min(mConstructionSamples, (int)sourceRays.size()); 269 270 Debug << "size: " << sourceRays.size() << " limit " << limit << endl; 270 271 VssRayContainer::const_iterator it, it_end = sourceRays.end(); 272 273 const float prop = (float)limit / ((float)sourceRays.size() + Limits::Small); 271 274 272 275 for (it = sourceRays.begin(); it != it_end; ++ it) 273 276 { 274 if (Random( (int)constructionRays.size()) > limit)277 if (Random(1.0f) < prop) 275 278 constructionRays.push_back(*it); 276 279 else … … 350 353 VssRayContainer::const_iterator it, it_end = rays.end(); 351 354 355 const float prop = (float)limit / ((float)rays.size() + Limits::Small); 356 352 357 for (it = rays.begin(); it != it_end; ++ it) 353 358 { 354 if (Random( (int)constructionRays.size()) > limit)359 if (Random(1.0f) < prop) 355 360 constructionRays.push_back(new Ray(*(*it))); 356 361 else … … 602 607 bool exportGeometry = false; 603 608 604 environment->GetBoolValue("Bsp ViewCellsManager.Visualization.exportRays", exportRays);605 environment->GetBoolValue("Bsp ViewCellsManager.Visualization.exportGeometry", exportGeometry);609 environment->GetBoolValue("BspTree.Visualization.exportRays", exportRays); 610 environment->GetBoolValue("BspTree.Visualization.exportGeometry", exportGeometry); 606 611 607 612 // export rays … … 1186 1191 1187 1192 mVspKdTree->Construct(constructionRays, sceneBbox); 1188 1193 1189 1194 // collect view cells 1190 1195 mVspKdTree->CollectViewCells(mViewCells); … … 1227 1232 bool exportGeometry = false; 1228 1233 1229 environment->GetBoolValue(" BspViewCellsManager.Visualization.exportRays", exportRays);1230 environment->GetBoolValue(" BspViewCellsManager.Visualization.exportGeometry", exportGeometry);1234 environment->GetBoolValue("VspKdTree.Visualization.exportRays", exportRays); 1235 environment->GetBoolValue("VspKdTree.Visualization.exportGeometry", exportGeometry); 1231 1236 1232 1237 if (!ViewCellsConstructed()) … … 1278 1283 1279 1284 // export geometry 1280 VspKdLeaf *leaf = leafContainer[ Random((int)leafContainer.size())];1285 VspKdLeaf *leaf = leafContainer[(int)RandomValue(0.0, (Real)((int)leafContainer.size() - 1))]; 1281 1286 AxisAlignedBox3 box = mVspKdTree->GetBBox(leaf); 1282 1287 … … 1409 1414 return 0; 1410 1415 1411 Debug << "Constructing bsp view cells" << endl;1416 Debug << "Constructing vsp bsp view cells" << endl; 1412 1417 1413 1418 int sampleContributions = 0; … … 1417 1422 1418 1423 GetRaySets(rays, constructionRays, savedRays); 1419 1424 Debug << "rays " << rays.size() << " construction rays " << constructionRays.size() << endl; 1420 1425 mVspBspTree->Construct(constructionRays); 1426 1421 1427 mVspBspTree->CollectViewCells(mViewCells); 1422 1428 … … 1433 1439 const VssRayContainer &rays) 1434 1440 { 1441 Debug << "Post processing view cells" << endl; 1435 1442 if (!ViewCellsConstructed()) 1436 1443 { … … 1438 1445 return 0; 1439 1446 } 1440 1441 1447 1442 1448 //-- post processing of bsp view cells … … 1625 1631 bool exportGeometry = false; 1626 1632 1627 environment->GetBoolValue("BspViewCellsManager.Visualization.exportRays", exportRays); 1628 environment->GetBoolValue("BspViewCellsManager.Visualization.exportGeometry", exportGeometry); 1633 Debug << "here344" << endl; 1634 environment->GetBoolValue("VspBspTree.Visualization.exportRays", exportRays); 1635 environment->GetBoolValue("VspBspTree.Visualization.exportGeometry", exportGeometry); 1629 1636 1630 1637 const int leafOut = 10; … … 1667 1674 } 1668 1675 #endif 1669 1670 1676 Intersectable::NewMail(); 1671 1677 … … 1837 1843 } 1838 1844 } 1845 Debug << "here222211" << endl; 1839 1846 } 1840 1847 -
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp
r472 r473 75 75 environment->GetIntValue("VspBspTree.maxTests", mMaxTests); 76 76 77 Debug << "BSP max depth: " << mTermMaxDepth << endl; 78 Debug << "BSP min PVS: " << mTermMinPvs << endl; 79 Debug << "BSP min area: " << mTermMinArea << endl; 80 Debug << "BSP min rays: " << mTermMinRays << endl; 81 Debug << "BSP max polygon candidates: " << mMaxPolyCandidates << endl; 82 Debug << "BSP max plane candidates: " << mMaxRayCandidates << endl; 77 // maximum number of view cells 78 environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells); 79 80 //-- 81 Debug << "******* VSP BSP options ******** " << endl; 82 Debug << "max depth: " << mTermMaxDepth << endl; 83 Debug << "min PVS: " << mTermMinPvs << endl; 84 Debug << "min area: " << mTermMinArea << endl; 85 Debug << "min rays: " << mTermMinRays << endl; 86 Debug << "max ray contri: " << mTermMaxRayContribution << endl; 87 //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl; 88 Debug << "max cost ratio: " << mTermMaxCostRatio << endl; 89 Debug << "miss tolerance: " << mTermMissTolerance << endl; 90 Debug << "max view cells: " << mMaxViewCells << endl; 91 Debug << "max polygon candidates: " << mMaxPolyCandidates << endl; 92 Debug << "max plane candidates: " << mMaxRayCandidates << endl; 83 93 84 94 Debug << "Split plane strategy: "; … … 310 320 311 321 if (r == mRoot) 312 Debug << " BSP tree construction time spent at root: "322 Debug << "VSP BSP tree construction time spent at root: " 313 323 << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl; 314 324 } … … 319 329 } 320 330 321 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const 331 bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data, 332 const int numLeaves) const 322 333 { 323 334 return 324 335 (((int)data.mRays->size() <= mTermMinRays) || 325 (data.mPvs <= mTermMinPvs) ||336 (data.mPvs <= mTermMinPvs) || 326 337 (data.mArea <= mTermMinArea) || 338 (numLeaves >= mMaxViewCells) || 327 339 // (data.GetAvgRayContribution() >= mTermMaxRayContribution) || 328 340 (data.mDepth >= mTermMaxDepth)); … … 332 344 VspBspTraversalData &tData) 333 345 { 346 BspNode *newNode = tData.mNode; 347 348 if (!TerminationCriteriaMet(tData, (int)tStack.size())) 349 { 350 PolygonContainer coincident; 351 352 VspBspTraversalData tFrontData; 353 VspBspTraversalData tBackData; 354 355 // create new interior node and two leaf nodes 356 // or return leaf as it is (if maxCostRatio missed) 357 newNode = SubdivideNode(tData, tFrontData, tBackData, coincident); 358 359 if (!newNode->IsLeaf()) //-- continue subdivision 360 { 361 // push the children on the stack 362 tStack.push(tFrontData); 363 tStack.push(tBackData); 364 365 // delete old leaf node 366 DEL_PTR(tData.mNode); 367 } 368 } 369 334 370 //-- terminate traversal 335 if (TerminationCriteriaMet(tData)) 336 { 337 BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 338 371 if (newNode->IsLeaf()) 372 { 373 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode); 374 375 // create new view cell for this leaf 339 376 BspViewCell *viewCell = new BspViewCell(); 340 341 377 leaf->SetViewCell(viewCell); 342 378 viewCell->mLeaves.push_back(leaf); 343 379 344 //-- add pvs 345 if (viewCell != mRootCell) 346 { 347 int conSamp = 0, sampCon = 0; 348 AddToPvs(leaf, *tData.mRays, conSamp, sampCon); 380 //-- update pvs 381 int conSamp = 0, sampCon = 0; 382 AddToPvs(leaf, *tData.mRays, conSamp, sampCon); 349 383 350 mStat.contributingSamples += conSamp; 351 mStat.sampleContributions += sampCon; 352 } 353 384 mStat.contributingSamples += conSamp; 385 mStat.sampleContributions += sampCon; 386 354 387 EvaluateLeafStats(tData); 355 356 //-- clean up 357 DEL_PTR(tData.mPolygons); 358 DEL_PTR(tData.mRays); 359 DEL_PTR(tData.mGeometry); 360 361 return leaf; 362 } 363 364 //-- continue subdivision 365 PolygonContainer coincident; 366 367 VspBspTraversalData tFrontData(new PolygonContainer(), 368 tData.mDepth + 1, 369 new RayInfoContainer(), 370 new BspNodeGeometry()); 371 372 VspBspTraversalData tBackData(new PolygonContainer(), 373 tData.mDepth + 1, 374 new RayInfoContainer(), 375 new BspNodeGeometry()); 376 377 // create new interior node and two leaf nodes 378 BspNode *newNode = SubdivideNode(tData, tFrontData, tBackData, coincident); 379 380 // subdivide further 381 if (!newNode->IsLeaf()) 382 { 383 BspInterior *interior = dynamic_cast<BspInterior *>(newNode); 384 385 #ifdef _DEBUG 386 // if (frontPolys->empty() && backPolys->empty() && (coincident.size() > 2)) 387 // { for (PolygonContainer::iterator it = coincident.begin(); it != coincident.end(); ++it) 388 // Debug << (*it) << " " << (*it)->GetArea() << " " << (*it)->mParent << endl ; 389 // Debug << endl;} 390 #endif 391 392 // push the children on the stack 393 tStack.push(tFrontData); 394 tStack.push(tBackData); 395 396 // delete old leaf node 397 DEL_PTR(tData.mNode); 398 } 399 400 // cleanup 388 } 389 390 391 //-- cleanup 401 392 DEL_PTR(tData.mPolygons); 402 393 DEL_PTR(tData.mRays); … … 411 402 PolygonContainer &coincident) 412 403 { 413 mStat.nodes += 2;414 415 404 BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode); 416 405 417 406 int maxCostMisses = tData.mMaxCostMisses; 418 407 … … 423 412 ++ maxCostMisses; 424 413 425 if (maxCostMisses >= mTermMissTolerance) 414 /*if (maxCostMisses >= mTermMissTolerance) 415 { 416 // terminate branch because of max cost 417 ++ mStat.maxCostNodes; 426 418 return leaf; 427 } 428 429 // subdivide further 419 }*/ 420 } 421 422 mStat.nodes += 2; 423 424 //-- subdivide further 430 425 BspInterior *interior = new BspInterior(splitPlane); 431 426 … … 434 429 #endif 435 430 436 // subdivide rays into front and back rays 431 //-- the front and back traversal data is filled with the new values 432 frontData.mPolygons = new PolygonContainer(); 433 frontData.mDepth = tData.mDepth + 1; 434 frontData.mRays = new RayInfoContainer(); 435 frontData.mGeometry = new BspNodeGeometry(); 436 437 backData.mPolygons = new PolygonContainer(); 438 backData.mDepth = tData.mDepth + 1; 439 backData.mRays = new RayInfoContainer(); 440 backData.mGeometry = new BspNodeGeometry(); 441 442 // subdivide rays 437 443 SplitRays(interior->GetPlane(), 438 444 *tData.mRays, … … 440 446 *backData.mRays); 441 447 442 // subdivide polygons with plane448 // subdivide polygons 443 449 mStat.splits += SplitPolygons(interior->GetPlane(), 444 450 *tData.mPolygons, … … 447 453 coincident); 448 454 449 450 // -- set left and right traversal data455 456 // how often was max cost ratio missed in this branch? 451 457 frontData.mMaxCostMisses = maxCostMisses; 452 458 backData.mMaxCostMisses = maxCostMisses; … … 464 470 mBox, 465 471 mEpsilon); 466 472 467 473 // area is normalized with view space area 468 474 frontData.mArea = frontData.mGeometry->GetArea() / mBox.SurfaceArea(); … … 494 500 frontData.mNode = interior->GetFront(); 495 501 backData.mNode = interior->GetBack(); 496 502 497 503 //DEL_PTR(leaf); 498 504 return interior; … … 536 542 vector<SortableEntry> &splitCandidates) const 537 543 { 538 544 splitCandidates.clear(); 539 545 540 int requestedSize = 2 * (int)polys.size(); 541 // creates a sorted split candidates array 542 splitCandidates.reserve(requestedSize); 546 const int requestedSize = 2 * (int)polys.size(); 547 548 // creates a sorted split candidates array 549 splitCandidates.reserve(requestedSize); 543 550 544 545 546 547 548 549 550 551 552 551 PolygonContainer::const_iterator it, it_end = polys.end(); 552 553 AxisAlignedBox3 box; 554 555 // insert all queries 556 for(it = polys.begin(); it != it_end; ++ it) 557 { 558 box.Initialize(); 559 box.Include(*(*it)); 553 560 554 555 556 561 splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MIN, box.Min(axis), *it)); 562 splitCandidates.push_back(SortableEntry(SortableEntry::POLY_MAX, box.Max(axis), *it)); 563 } 557 564 558 565 stable_sort(splitCandidates.begin(), splitCandidates.end()); 559 566 } 560 567 … … 687 694 if (!data.mPolygons->empty()) 688 695 { 689 const int randIdx = Random((int)data.mPolygons->size());696 const int randIdx = (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1)); 690 697 Polygon3 *nextPoly = (*data.mPolygons)[randIdx]; 691 698 … … 696 703 { 697 704 //-- choose plane on midpoint of a ray 698 const int candidateIdx = Random((int)data.mRays->size());705 const int candidateIdx = (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)); 699 706 700 707 const Vector3 minPt = (*data.mRays)[candidateIdx].ExtrapOrigin(); … … 716 723 } 717 724 725 Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const 726 { 727 const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 728 729 const Vector3 minPt = rays[candidateIdx].ExtrapOrigin(); 730 const Vector3 maxPt = rays[candidateIdx].ExtrapTermination(); 731 732 const Vector3 pt = (maxPt + minPt) * 0.5; 733 const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir()); 734 735 return Plane3(normal, pt); 736 } 737 738 Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const 739 { 740 Vector3 pt[3]; 741 742 int idx[3]; 743 int cmaxT = 0; 744 int cminT = 0; 745 bool chooseMin = false; 746 747 for (int j = 0; j < 3; ++ j) 748 { 749 idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1)); 750 751 if (idx[j] >= (int)rays.size()) 752 { 753 idx[j] -= (int)rays.size(); 754 755 chooseMin = (cminT < 2); 756 } 757 else 758 chooseMin = (cmaxT < 2); 759 760 RayInfo rayInf = rays[idx[j]]; 761 pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination(); 762 } 763 764 return Plane3(pt[0], pt[1], pt[2]); 765 } 766 767 Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const 768 { 769 Vector3 pt[3]; 770 771 int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 772 int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1)); 773 774 // check if rays different 775 if (idx1 == idx2) 776 idx2 = (idx2 + 1) % (int)rays.size(); 777 778 const RayInfo ray1 = rays[idx1]; 779 const RayInfo ray2 = rays[idx2]; 780 781 // normal vector of the plane parallel to both lines 782 const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir())); 783 784 // vector from line 1 to line 2 785 const Vector3 vd = (ray2.ExtrapOrigin() - ray1.ExtrapOrigin()); 786 787 // project vector on normal to get distance 788 const float dist = DotProd(vd, norm); 789 790 // point on plane lies halfway between the two planes 791 const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5; 792 793 return Plane3(norm, planePt); 794 } 795 718 796 bool VspBspTree::SelectPlaneHeuristics(Plane3 &bestPlane, 719 797 BspLeaf *leaf, … … 725 803 726 804 const int limit = Min((int)data.mPolygons->size(), mMaxPolyCandidates); 727 int candidateIdx = limit;805 int maxIdx = (int)data.mPolygons->size(); 728 806 729 807 for (int i = 0; i < limit; ++ i) 730 808 { 731 candidateIdx = GetNextCandidateIdx(candidateIdx, *data.mPolygons); 732 809 // assure that no index is taken twice 810 const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx)); 811 //Debug << "current Idx: " << maxIdx << " cand idx " << candidateIdx << endl; 812 733 813 Polygon3 *poly = (*data.mPolygons)[candidateIdx]; 814 815 // swap candidate to the end to avoid testing same plane 816 std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]); 817 818 //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)]; 734 819 735 820 // evaluate current candidate … … 747 832 748 833 //-- choose candidate planes extracted from rays 749 // we currently use different twomethods chosen with834 // we use different methods chosen with 750 835 // equal probability 751 752 // take 3 ray endpoints, where two are minimum and one a maximum 753 // point or the other way round 754 for (int i = 0; i < mMaxRayCandidates / 2; ++ i) 755 { 756 candidateIdx = Random((int)data.mRays->size()); 757 758 RayInfo rayInf = (*data.mRays)[candidateIdx]; 759 760 const Vector3 minPt = rayInf.ExtrapOrigin(); 761 const Vector3 maxPt = rayInf.ExtrapTermination(); 762 763 const Vector3 pt = (maxPt + minPt) * 0.5; 764 const Vector3 normal = Normalize(rayInf.mRay->GetDir()); 765 766 plane = Plane3(normal, pt); 836 for (int i = 0; i < mMaxRayCandidates; ++ i) 837 { 838 plane = ChooseCandidatePlane3(*data.mRays); 767 839 768 840 const float candidateCost = SplitPlaneCost(plane, data); … … 774 846 } 775 847 } 776 777 // take plane normal as plane normal and the midpoint of the ray.778 // PROBLEM: does not resemble any point where visibility is likely to change779 //Debug << "lowest2: " << lowestCost << endl;780 for (int i = 0; i < mMaxRayCandidates / 2; ++ i)781 {782 Vector3 pt[3];783 int idx[3];784 int cmaxT = 0;785 int cminT = 0;786 bool chooseMin = false;787 788 for (int j = 0; j < 3; j ++)789 {790 idx[j] = Random((int)data.mRays->size() * 2);791 792 if (idx[j] >= (int)data.mRays->size())793 {794 idx[j] -= (int)data.mRays->size();795 796 chooseMin = (cminT < 2);797 }798 else799 chooseMin = (cmaxT < 2);800 801 RayInfo rayInf = (*data.mRays)[idx[j]];802 pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();803 }804 805 plane = Plane3(pt[0], pt[1], pt[2]);806 807 const float candidateCost = SplitPlaneCost(plane, data);808 809 if (candidateCost < lowestCost)810 {811 //Debug << "choose ray plane 2: " << candidateCost << endl;812 bestPlane = plane;813 814 lowestCost = candidateCost;815 }816 }817 848 818 849 // cost ratio miss … … 825 856 826 857 return true; 827 }828 829 int VspBspTree::GetNextCandidateIdx(int currentIdx, PolygonContainer &polys)830 {831 const int candidateIdx = Random(currentIdx --);832 833 // swap candidates to avoid testing same plane 2 times834 std::swap(polys[currentIdx], polys[candidateIdx]);835 836 return currentIdx;837 //return Random((int)polys.size());838 858 } 839 859 … … 905 925 for (int i = 0; i < limit; ++ i) 906 926 { 907 const int testIdx = useRand ? Random(limit) : i;927 const int testIdx = useRand ? (int)RandomValue(0, (Real)(limit - 1)) : i; 908 928 RayInfo rayInf = (*data.mRays)[testIdx]; 909 929 … … 1353 1373 { 1354 1374 RayInfo bRay = rays.back(); 1375 rays.pop_back(); 1376 1355 1377 VssRay *ray = bRay.mRay; 1356 1357 rays.pop_back();1358 1378 float t; 1359 // get classification and receive new t 1379 1380 // get classification and receive new t 1360 1381 const int cf = bRay.ComputeRayIntersection(plane, t); 1361 1382 1362 1383 switch (cf) 1363 1384 { … … 1370 1391 case 0: 1371 1392 //-- split ray 1372 1373 // if start point behind plane 1393 //-- look if start point behind or in front of plane 1374 1394 if (plane.Side(bRay.ExtrapOrigin()) <= 0) 1375 1395 { -
trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.h
r472 r473 60 60 /// how often this branch has missed the max-cost ratio 61 61 int mMaxCostMisses; 62 63 62 64 /** Returns average ray contribution. 63 65 */ … … 80 82 81 83 VspBspTraversalData(BspNode *node, 82 83 84 85 86 87 84 PolygonContainer *polys, 85 const int depth, 86 RayInfoContainer *rays, 87 int pvs, 88 float area, 89 BspNodeGeometry *geom): 88 90 mNode(node), 89 91 mPolygons(polys), … … 359 361 int AddMeshToPolygons(Mesh *mesh, PolygonContainer &polys, MeshInstance *parent); 360 362 361 /** returns next candidate index and reorders polygons so no candidate is chosen two times362 @param the current candidate index363 @param max the range of candidates364 */365 int GetNextCandidateIdx(int currentIdx, PolygonContainer &polys);366 367 363 /** Computes best cost ratio for the suface area heuristics for axis aligned 368 364 splits. This heuristics minimizes the cost for ray traversal. … … 431 427 /** Returns true if tree can be terminated. 432 428 */ 433 inline bool TerminationCriteriaMet(const VspBspTraversalData &data ) const;429 inline bool TerminationCriteriaMet(const VspBspTraversalData &data, const int numLeaves) const; 434 430 435 431 /** Computes accumulated ray lenght of this rays. … … 465 461 466 462 467 463 /** Take 3 ray endpoints, where two are minimum and one a maximum 464 point or the other way round. 465 */ 466 Plane3 ChooseCandidatePlane(const RayInfoContainer &rays) const; 467 468 /** Take plane normal as plane normal and the midpoint of the ray. 469 PROBLEM: does not resemble any point where visibility is likely to change 470 */ 471 Plane3 ChooseCandidatePlane2(const RayInfoContainer &rays) const; 472 473 /** Fit the plane between the two lines so that the plane has equal shortest 474 distance to both lines. 475 */ 476 Plane3 ChooseCandidatePlane3(const RayInfoContainer &rays) const; 468 477 469 478 /// Pointer to the root of the tree … … 537 546 /// number of different bsp split plane criteria 538 547 int mNumCriteria; 548 /// maximal number of view cells 549 int mMaxViewCells; 539 550 540 551 private: -
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp
r472 r473 382 382 Debug << "min rays: "<< mTermMinRays << endl; 383 383 Debug << "max ray contribution: "<< mTermMaxRayContribution << endl; 384 Debug << "max cost ratio: " << mTermMaxCostRatio << endl;385 Debug << "min size: " <<mTermMinSize << endl;384 Debug << "max cost ratio: " << mTermMaxCostRatio << endl; 385 Debug << "min size: " << mTermMinSize << endl; 386 386 387 387 if (name.compare("regular") == 0) … … 2310 2310 2311 2311 2312 void VspKdTree::RefineViewCells() 2313 { 2314 } 2315 2316 2312 2317 /*********************************************************************/ 2313 2318 /* MergeCandidate implementation */ -
trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h
r472 r473 601 601 void EvaluateViewCellsStats(ViewCellsStatistics &stat) const; 602 602 603 /** Refines view cells in a post processing step. 604 */ 605 void RefineViewCells(); 606 603 607 protected: 604 608 -
trunk/VUT/GtpVisibilityPreprocessor/src/VssPreprocessor.cpp
r469 r473 562 562 mViewCellsManager->Visualize(mObjects, storedRays); 563 563 564 CLEAR_CONTAINER(storedRays); 565 } 566 567 //-- render simulation after merge 568 cout << "\nevaluating bsp view cells render time after merge ... "; 564 Debug << "here2" << endl; 565 } 569 566 570 567 //-- render simulation after merge … … 572 569 573 570 mRenderSimulator->RenderScene(); 571 Debug << "here3" << endl; 574 572 SimulationStatistics ss; 575 573 mRenderSimulator->GetStatistics(ss); 576 574 Debug << "here244" << endl; 577 575 cout << " finished" << endl; 578 576 cout << ss << endl; 579 577 Debug << ss << endl; 580 578 581 582 579 delete vssTree; 583 580 581 Debug << "here4" << endl; 584 582 return true; 585 583 } -
trunk/VUT/GtpVisibilityPreprocessor/src/VssTree.cpp
r469 r473 1720 1720 for (int i=0; i < numberOfRays; i++) { 1721 1721 // pickup 3 random rays 1722 int r1 = Random(nrays-1);1723 int r2 = Random(nrays-1);1724 int r3 = Random(nrays-1);1722 int r1 = (int)RandomValue(0, nrays-1); 1723 int r2 = (int)RandomValue(0, nrays-1); 1724 int r3 = (int)RandomValue(0, nrays-1); 1725 1725 1726 1726 Vector3 o1 = leaf->rays[r1].Extrap(RandomValue(leaf->rays[r1].GetMinT(),
Note: See TracChangeset
for help on using the changeset viewer.