Changeset 1020 for GTP/trunk/Lib/Vis/Preprocessing
- Timestamp:
- 06/18/06 03:47:06 (19 years ago)
- Location:
- GTP/trunk/Lib/Vis/Preprocessing
- Files:
-
- 2 added
- 18 edited
Legend:
- Unmodified
- Added
- Removed
-
GTP/trunk/Lib/Vis/Preprocessing/scripts/Preprocessor.vcproj
r1006 r1020 386 386 </File> 387 387 <File 388 RelativePath="..\src\SamplingStrategy.cpp"> 389 </File> 390 <File 391 RelativePath="..\src\SamplingStrategy.h"> 392 </File> 393 <File 388 394 RelativePath="..\src\SceneGraph.cpp"> 389 395 </File> -
GTP/trunk/Lib/Vis/Preprocessing/src/Environment.cpp
r1006 r1020 1314 1314 "20000"); 1315 1315 1316 RegisterOption("ViewCells.Visualization.maxOutput", 1317 optInt, 1318 "view_cells_visualization_max_output=", 1319 "20"); 1320 1316 1321 RegisterOption("ViewCells.Filter.maxSize", 1317 1322 optInt, … … 2047 2052 "0.5"); 2048 2053 2054 RegisterOption("VspBspTree.Construction.renderCostDecreaseWeight", 2055 optFloat, 2056 "vsp_bsp_post_process_render_cost_decrease_weight=", 2057 "0.99"); 2058 2049 2059 RegisterOption("VspBspTree.Construction.randomize", 2050 2060 optBool, -
GTP/trunk/Lib/Vis/Preprocessing/src/Intersectable.h
r870 r1020 48 48 49 49 50 virtual AxisAlignedBox3 GetBox() = 0;50 virtual AxisAlignedBox3 GetBox() const = 0; 51 51 virtual int CastRay(GtpVisibilityPreprocessor::Ray &ray) = 0; 52 52 53 virtual bool IsConvex() = 0;54 virtual bool IsWatertight() = 0;53 virtual bool IsConvex() const = 0; 54 virtual bool IsWatertight() const = 0; 55 55 virtual float IntersectionComplexity() = 0; 56 56 -
GTP/trunk/Lib/Vis/Preprocessing/src/Mesh.cpp
r1005 r1020 412 412 Mesh::GetRandomSurfacePoint(Vector3 &point, Vector3 &normal) 413 413 { 414 int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1));414 const int faceIndex = (int)RandomValue(0, (Real)((int)mFaces.size()-1)); 415 415 416 416 // assume the face is convex and generate a convex combination 417 417 // 418 418 Face *face = mFaces[faceIndex]; 419 419 420 point = Vector3(0,0,0); 420 421 float sum = 0.0f; 422 421 423 for (int i = 0; i < face->mVertexIndices.size(); i++) { 422 424 float r = RandomValue(0,1); … … 603 605 604 606 605 Mesh::Mesh(const Mesh &rhs) 607 Mesh::Mesh(const Mesh &rhs): 608 mKdTree(NULL) 606 609 { 607 610 mVertices = rhs.mVertices; … … 609 612 mId = rhs.mId; 610 613 mMaterial = rhs.mMaterial; 611 614 612 615 FaceContainer::const_iterator it, it_end = rhs.mFaces.end(); 613 616 … … 766 769 767 770 768 void TransformedMeshInstance::GetWorldTransform(Matrix4x4 &m) 771 void TransformedMeshInstance::GetWorldTransform(Matrix4x4 &m) const 769 772 { 770 773 m = mWorldTransform; … … 772 775 773 776 774 AxisAlignedBox3 TransformedMeshInstance::GetBox() 777 AxisAlignedBox3 TransformedMeshInstance::GetBox() const 775 778 { 776 779 return Transform(mMesh->mBox, mWorldTransform); 777 780 } 778 781 779 void TransformedMeshInstance::GetTransformedMesh(Mesh &transformedMesh) 780 { 781 // copy mesh 782 783 void TransformedMeshInstance::GetTransformedMesh(Mesh &transformedMesh) const 784 { 785 // copy mesh 782 786 transformedMesh = *mMesh; 783 787 transformedMesh.ApplyTransformation(mWorldTransform); 784 785 786 } 788 } 789 790 } -
GTP/trunk/Lib/Vis/Preprocessing/src/Mesh.h
r1005 r1020 244 244 Mesh *GetMesh() { return mMesh; } 245 245 246 virtual AxisAlignedBox3 GetBox() {246 virtual AxisAlignedBox3 GetBox() const { 247 247 return mMesh->mBox; 248 248 } … … 250 250 virtual int CastRay(Ray &ray); 251 251 252 virtual bool IsConvex() { return mMesh->mIsConvex; }253 virtual bool IsWatertight() { return mMesh->mIsWatertight; }252 virtual bool IsConvex() const { return mMesh->mIsConvex; } 253 virtual bool IsWatertight() const { return mMesh->mIsWatertight; } 254 254 virtual float IntersectionComplexity() { return (float)mMesh->mFaces.size(); } 255 255 256 256 virtual int NumberOfFaces() const { return (int)mMesh->mFaces.size(); } 257 257 258 258 virtual int Type() const { return MESH_INSTANCE; } … … 297 297 TransformedMeshInstance(Mesh *mesh); 298 298 299 virtual AxisAlignedBox3 GetBox() ;299 virtual AxisAlignedBox3 GetBox() const; 300 300 301 301 … … 318 318 /** The transformation is returned in m. 319 319 */ 320 void GetWorldTransform(Matrix4x4 &m) ;320 void GetWorldTransform(Matrix4x4 &m) const; 321 321 322 322 /** Transforms a mesh according to the stored world transform. 323 @param transformedMesh returns the tranformed mesh.324 */ 325 void GetTransformedMesh(Mesh &transformedMesh) ;323 @param transformedMesh returns the tranformed mesh. 324 */ 325 void GetTransformedMesh(Mesh &transformedMesh) const; 326 326 327 327 protected: -
GTP/trunk/Lib/Vis/Preprocessing/src/Parser.h
r863 r1020 17 17 virtual bool ParseFile(const std::string filename, 18 18 SceneGraphNode **root, 19 const bool loadPolygonsAsMeshes = false) {return false;}; 19 const bool loadPolygonsAsMeshes = false) 20 {return false;}; 20 21 21 22 }; -
GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.cpp
r1006 r1020 12 12 #include "GlRenderer.h" 13 13 #include "PlyParser.h" 14 #include "SamplingStrategy.h" 15 16 14 17 15 18 namespace GtpVisibilityPreprocessor { 16 19 20 const static bool ADDITIONAL_GEOMETRY_HACK = false; 17 21 18 22 Preprocessor *preprocessor; … … 76 80 //Vector3 boxSize = sceneBox.Size() * Vector3(0.0025, 0.01, 0.0025); 77 81 Vector3 boxSize = sceneBox.Size() * Vector3(0.005, 0.02, 0.005); 82 78 83 AxisAlignedBox3 box(pt2 + 0.1, pt2 + boxSize); 79 84 Mesh *mesh = CreateMeshFromBox(box); … … 243 248 { 244 249 // HACK 245 //AddGeometry(mSceneGraph); 246 mSceneGraph->AssignObjectIds(); 247 248 int intersectables, faces; 249 mSceneGraph->GetStatistics(intersectables, faces); 250 251 cout<<filename<<" parsed successfully."<<endl; 252 cout<<"#NUM_OBJECTS (Total numner of objects)\n"<<intersectables<<endl; 253 cout<<"#NUM_FACES (Total numner of faces)\n"<<faces<<endl; 254 mSceneGraph->CollectObjects(&mObjects); 255 mSceneGraph->mRoot->UpdateBox(); 256 257 /* Exporter *exporter = Exporter::GetExporter("testload.x3d"); 258 259 if (exporter) 260 { 261 exporter->ExportGeometry(mObjects); 262 delete exporter; 263 }*/ 264 250 if (ADDITIONAL_GEOMETRY_HACK) 251 AddGeometry(mSceneGraph); 252 253 mSceneGraph->AssignObjectIds(); 254 255 int intersectables, faces; 256 mSceneGraph->GetStatistics(intersectables, faces); 257 258 cout<<filename<<" parsed successfully."<<endl; 259 cout<<"#NUM_OBJECTS (Total numner of objects)\n"<<intersectables<<endl; 260 cout<<"#NUM_FACES (Total numner of faces)\n"<<faces<<endl; 261 mSceneGraph->CollectObjects(&mObjects); 262 mSceneGraph->mRoot->UpdateBox(); 263 264 if (0) 265 { 266 Exporter *exporter = Exporter::GetExporter("testload.x3d"); 267 268 if (exporter) 269 { 270 exporter->ExportGeometry(mObjects); 271 delete exporter; 272 } 273 } 265 274 } 266 275 … … 594 603 } 595 604 596 597 605 #if 0 // matt: implemented interface samplestrategy 598 606 bool 599 607 Preprocessor::GenerateRays( … … 656 664 return true; 657 665 } 658 659 } 666 #endif 667 bool Preprocessor::GenerateRays(const int number, 668 const int sampleType, 669 SimpleRayContainer &rays) 670 { 671 Vector3 origin, direction; 672 673 const int startSize = (int)rays.size(); 674 SamplingStrategy *strategy = GenerateSamplingStrategy(sampleType); 675 676 if (!strategy) 677 return false; 678 679 for (int i=0; (int)rays.size() - startSize < number; ++ i) 680 { 681 SimpleRay newRay; 682 bool success = strategy->GenerateSample(newRay); 683 684 if (success) 685 rays.AddRay(newRay); 686 } 687 688 delete strategy; 689 690 return true; 691 } 692 693 694 SamplingStrategy *Preprocessor::GenerateSamplingStrategy(const int strategyId) const 695 { 696 switch (strategyId) 697 { 698 case OBJECT_BASED_DISTRIBUTION: 699 return new ObjectBasedDistribution(*this); 700 case OBJECT_DIRECTION_BASED_DISTRIBUTION: 701 return new ObjectDirectionBasedDistribution(*this); 702 case DIRECTION_BASED_DISTRIBUTION: 703 return new DirectionBasedDistribution(*this); 704 case DIRECTION_BOX_BASED_DISTRIBUTION: 705 return new DirectionBoxBasedDistribution(*this); 706 case SPATIAL_BOX_BASED_DISTRIBUTION: 707 return new SpatialBoxBasedDistribution(*this); 708 case OBJECTS_INTERIOR_DISTRIBUTION: 709 return new ObjectsInteriorDistribution(*this); 710 default: // no valid strategy 711 return NULL; 712 } 713 // should never come here 714 return NULL; 715 } 716 717 718 } -
GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.h
r1006 r1020 21 21 class RenderSimulator; 22 22 struct VssRayContainer; 23 class SamplingStrategy; 23 24 24 25 class GlRendererBuffer; … … 80 81 bool PrepareViewCells(); 81 82 83 /** Returns the specified sample strategy, NULL if no valid strategy. 84 */ 85 SamplingStrategy *GenerateSamplingStrategy(const int strategyId) const; 86 82 87 bool 83 88 Export( const string filename, … … 115 120 RSS_SILHOUETTE_BASED_DISTRIBUTION, 116 121 VSS_BASED_DISTRIBUTION, 117 OBJECT_DIRECTION_BASED_DISTRIBUTION 122 OBJECT_DIRECTION_BASED_DISTRIBUTION, 123 OBJECTS_INTERIOR_DISTRIBUTION 118 124 }; 119 125 -
GTP/trunk/Lib/Vis/Preprocessing/src/RenderSimulator.cpp
r1006 r1020 12 12 void SimulationStatistics::Print(ostream &app) const 13 13 { 14 app << "===== Render Simulation statistics ===============\n";14 app << "============== Render Simulation statistics ==============\n"; 15 15 16 16 app << setprecision(4); … … 36 36 << validAvgRtWithoutOverhead << "\n"; 37 37 38 app << "===== END OF Render Simulation statistics ==========\n";38 app << "=========== END OF Render Simulation statistics ==========\n"; 39 39 } 40 40 41 41 42 RenderSimulator::RenderSimulator(ViewCellsManager *viewCellsManager): -
GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp
r1006 r1020 8 8 #include "ViewCellBsp.h" 9 9 #include "KdTree.h" 10 //#include "VspOspTree.h"10 #include "VspOspTree.h" 11 11 #include "Exporter.h" 12 12 #include "VspBspTree.h" … … 104 104 105 105 106 // sampling type for view cells construction samples 106 107 if (strcmp(buf, "box") == 0) 107 108 { … … 112 113 mSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION; 113 114 } 114 else 115 else if (strcmp(buf, "interior") == 0) 116 { 117 mSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION; 118 } 119 else if (strcmp(buf, "object_directional") == 0) 120 { 121 mSamplingType = Preprocessor::OBJECT_DIRECTION_BASED_DISTRIBUTION; 122 } 123 else 115 124 { 116 125 Debug << "error! wrong sampling type" << endl; … … 118 127 } 119 128 129 // sampling type for evaluation samples 120 130 Environment::GetSingleton()->GetStringValue("ViewCells.Evaluation.samplingType", buf); 121 131 … … 128 138 mEvaluationSamplingType = Preprocessor::DIRECTION_BASED_DISTRIBUTION; 129 139 } 130 else 140 else if (strcmp(buf, "object_directional") == 0) 141 { 142 mEvaluationSamplingType = Preprocessor::OBJECT_DIRECTION_BASED_DISTRIBUTION; 143 } 144 else if (strcmp(buf, "interior") == 0) 145 { 146 mEvaluationSamplingType = Preprocessor::OBJECTS_INTERIOR_DISTRIBUTION; 147 } 148 else 131 149 { 132 150 Debug << "error! wrong sampling type" << endl; … … 201 219 ViewCellsManager::~ViewCellsManager() 202 220 { 203 //DEL_PTR(mRenderer); 204 221 // HACK: if view cells tree does not 222 // take care of view cells, we have to do it 223 // question: rather create view cells resource manager? 205 224 if (!ViewCellsTreeConstructed()) 206 225 CLEAR_CONTAINER(mViewCells); 207 //else226 208 227 DEL_PTR(mViewCellsTree); 209 228 } … … 855 874 Debug << "view cell stats prefix: " << statsPrefix << endl; 856 875 857 858 876 // should directional sampling be used? 859 877 bool dirSamples = (mEvaluationSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION); 860 861 878 862 879 cout << "reseting pvs ... "; … … 1366 1383 ViewCellContainer::const_iterator it, it_end = mViewCells.end(); 1367 1384 1368 1369 1385 //-- compute expected value 1370 1371 1386 totalRenderCost = 0; 1372 1387 totalPvs = 0; … … 2480 2495 if (1) // export final view cells 2481 2496 { 2482 mColorCode = 1; 2483 2497 mColorCode = 1; // hack color code 2484 2498 Exporter *exporter = Exporter::GetExporter("final_view_cells.x3d"); 2485 2499 … … 2494 2508 2495 2509 //exporter->SetFilled(); 2496 bool b = mUseClipPlaneForViz;2510 const bool b = mUseClipPlaneForViz; 2497 2511 mUseClipPlaneForViz = false; 2512 2498 2513 ExportViewCellsForViz(exporter); 2514 2499 2515 mUseClipPlaneForViz = b; 2500 2516 delete exporter; … … 3101 3117 } 3102 3118 3119 3103 3120 int KdViewCellsManager::PostProcess(const ObjectContainer &objects, 3104 3121 const VssRayContainer &rays) … … 3106 3123 return 0; 3107 3124 } 3125 3108 3126 3109 3127 void KdViewCellsManager::Visualize(const ObjectContainer &objects, … … 3956 3974 mColorCode = 1; 3957 3975 3958 Exporter *exporter = Exporter::GetExporter("final_view_cells. x3d");3976 Exporter *exporter = Exporter::GetExporter("final_view_cells.wrl"); 3959 3977 3960 3978 if (exporter) … … 3976 3994 3977 3995 // export rays 3978 if ( mExportRays)3996 if (1 && mExportRays) 3979 3997 { 3980 3998 exporter->ExportRays(visRays, RgbColor(0, 1, 0)); … … 3982 4000 3983 4001 //exporter->SetFilled(); 4002 3984 4003 // HACK: export without clip plane 3985 4004 const bool b = mUseClipPlaneForViz; 3986 4005 mUseClipPlaneForViz = false; 4006 3987 4007 ExportViewCellsForViz(exporter); 4008 3988 4009 mUseClipPlaneForViz = b; 3989 3990 4010 delete exporter; 4011 3991 4012 cout << "finished" << endl; 3992 4013 } … … 4107 4128 const VssRayContainer &rays) 4108 4129 { 4109 const int leafOut = 20; 4130 int leafOut; 4131 Environment::GetSingleton()->GetIntValue("ViewCells.Visualization.maxOutput", leafOut); 4110 4132 4111 4133 ViewCell::NewMail(); … … 4116 4138 4117 4139 const bool sortViewCells = true; 4118 4119 4120 4140 // sort view cells to visualize the largest view cells 4121 4141 if (sortViewCells) … … 4145 4165 4146 4166 //bspLeaves[j]->Mail(); 4147 char s[64]; sprintf(s, "bsp-pvs%04d. x3d", i);4167 char s[64]; sprintf(s, "bsp-pvs%04d.wrl", i); 4148 4168 Exporter *exporter = Exporter::GetExporter(s); 4149 4169 … … 4151 4171 4152 4172 //-- export the sample rays 4153 if ( 1 ||mExportRays)4173 if (mExportRays) 4154 4174 { 4155 4175 // output rays stored with the view cells during subdivision … … 4219 4239 4220 4240 4241 //-- export view cell geometry 4221 4242 exporter->SetWireframe(); 4222 4243 … … 4228 4249 4229 4250 exporter->SetFilled(); 4251 4230 4252 4231 4253 //-- export pvs … … 4314 4336 case 1: // pvs 4315 4337 { 4316 importance = (float)mViewCellsTree->GetPvsSize(vc) / (float)mCurrentViewCellsStats.maxPvs; 4338 if (mCurrentViewCellsStats.maxPvs) 4339 importance = (float)mViewCellsTree->GetPvsSize(vc) / (float)mCurrentViewCellsStats.maxPvs; 4317 4340 } 4318 4341 break; … … 4469 4492 if (i != j) 4470 4493 { 4471 4472 4494 BspLeaf *leaf2 =dynamic_cast<BspViewCell *>(leaves[j])->mLeaf; 4473 4495 -
GTP/trunk/Lib/Vis/Preprocessing/src/VrmlExporter.cpp
r1006 r1020 42 42 stream<<"}"<<endl; 43 43 44 stream<<" IndexedLineSet { coordIndex=\""<<endl;44 stream<<"geometry IndexedLineSet { coordIndex [" << endl; 45 45 46 46 int index = 0; … … 51 51 } 52 52 53 stream << " }"<<endl;54 55 stream <<"<Coordinate point=\""<<endl;53 stream << "]"<<endl; 54 55 stream << "coord Coordinate { point [" << endl; 56 56 57 57 ri = rays.begin(); … … 77 77 stream << b.x << " " << b.y << " " << b.z << " ,\n"; 78 78 } 79 79 stream << "]" << endl; 80 80 stream << "}" << endl; 81 81 stream << "}" << endl; 82 82 stream << "}" << endl; 83 stream << "}" << endl;83 //stream << "}" << endl; 84 84 85 85 return true; … … 99 99 stream << "}" << endl; // end appearance 100 100 101 stream << " IndexedLineSet { coordIndex=\"" << endl;101 stream << "geometry IndexedLineSet { coordIndex [" << endl; 102 102 103 103 int index = 0; … … 108 108 } 109 109 110 stream << " }" << endl;111 112 stream << " Coordinate point= {" << endl;110 stream << "]" << endl; 111 112 stream << "coord Coordinate { point [" << endl; 113 113 114 114 ri = rays.begin(); … … 121 121 stream<<b.x<<" "<<b.y<<" "<<b.z<<" ,\n"; 122 122 } 123 123 stream << "]" << endl; 124 124 stream << "}" << endl; 125 125 stream << "}" << endl; 126 126 stream << "}" << endl; 127 stream << "}" << endl;127 //stream << "}" << endl; 128 128 129 129 return true; … … 215 215 tStack.push(pair<BspNode *, BspNodeGeometry *>(tree.GetRoot(), geom)); 216 216 217 if (maxPvs > 0)217 if (maxPvs) 218 218 mUseForcedMaterial = true; 219 219 220 220 while (!tStack.empty()) 221 221 { … … 242 242 else 243 243 { 244 if (maxPvs > 0)244 if (maxPvs) 245 245 { 246 246 BspLeaf *leaf = dynamic_cast<BspLeaf *>(node); 247 247 248 248 mForcedMaterial.mDiffuseColor.b = 1.0f; 249 float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs;249 const float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs; 250 250 251 251 mForcedMaterial.mDiffuseColor.r = importance; … … 599 599 //Mesh *mesh = new Mesh; 600 600 601 if (maxPvs > 0)601 if (maxPvs) 602 602 mUseForcedMaterial = true; 603 603 … … 632 632 mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) ); 633 633 634 if (maxPvs > 0)634 if (maxPvs) 635 635 { 636 636 VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node); -
GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp
r1016 r1020 21 21 22 22 #define USE_FIXEDPOINT_T 0 23 24 23 #define COUNT_ORIGIN_OBJECTS 1 24 25 25 26 //-- static members 26 27 27 28 28 int VspBspTree::sFrontId = 0; 29 29 int VspBspTree::sBackId = 0; 30 30 int VspBspTree::sFrontAndBackId = 0; 31 32 31 33 32 34 typedef pair<BspNode *, BspNodeGeometry *> bspNodePair; … … 113 115 114 116 Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight); 117 Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight); 115 118 Environment::GetSingleton()->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable); 116 119 … … 161 164 Debug << "maxband: " << mMaxBand << endl; 162 165 Debug << "use driving axis for max cost: " << mUseDrivingAxisIfMaxCostViolated << endl; 166 Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl; 163 167 164 168 Debug << "Split plane strategy: "; … … 189 193 190 194 191 m SplitCandidates = new vector<SortableEntry>;195 mLocalSplitCandidates = new vector<SortableEntry>; 192 196 193 197 Debug << endl; … … 236 240 { 237 241 DEL_PTR(mRoot); 238 DEL_PTR(m SplitCandidates);242 DEL_PTR(mLocalSplitCandidates); 239 243 } 240 244 … … 497 501 const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume(); 498 502 503 /// first traversal data 499 504 VspBspTraversalData tData(mRoot, 500 505 new PolygonContainer(polys), … … 520 525 mTotalPvsSize = tData.mPvs; 521 526 522 // first stats 523 mSubdivisionStats 524 << "#ViewCells\n1" << endl 525 << "#RenderCostDecrease\n0" << endl 526 << "#TotalRenderCost\n" << mTotalCost << endl 527 << "#AvgRenderCost\n" << mTotalPvsSize << endl; 528 529 Debug << "total cost: " << mTotalCost << endl; 530 531 527 // first subdivison statistics 528 AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize); 529 532 530 mBspStats.Start(); 533 531 cout << "Constructing vsp bsp tree ... \n"; … … 586 584 587 585 Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl; 588 cout << "finished \n";586 cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl; 589 587 590 588 mBspStats.Stop(); … … 624 622 mTotalPvsSize = tData.mPvs; 625 623 626 mSubdivisionStats 627 << "#ViewCells\n1\n" << endl 628 << "#RenderCostDecrease\n0\n" << endl 629 << "#SplitCandidateCost\n0\n" << endl 630 << "#TotalRenderCost\n" << mTotalCost << endl 631 << "#AvgRenderCost\n" << mTotalPvsSize << endl; 632 633 Debug << "total cost: " << mTotalCost << endl; 634 635 636 mBspStats.Start(); 624 // first subdivison statistics 625 AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize); 626 627 mBspStats.Start(); 637 628 cout << "Constructing vsp bsp tree ... \n"; 638 629 … … 654 645 655 646 // cost ratio of cost decrease / totalCost 656 float costRatio = splitCandidate.Get Cost() / mTotalCost;647 float costRatio = splitCandidate.GetPriority() / mTotalCost; 657 648 658 649 //Debug << "cost ratio: " << costRatio << endl; … … 716 707 717 708 709 void VspBspTree::AddSubdivisionStats(const int viewCells, 710 const float renderCostDecr, 711 const float splitCandidateCost, 712 const float totalRenderCost, 713 const float avgRenderCost) 714 { 715 mSubdivisionStats 716 << "#ViewCells\n" << viewCells << endl 717 << "#RenderCostDecrease\n" << renderCostDecr << endl 718 << "#SplitCandidateCost\n" << splitCandidateCost << endl 719 << "#TotalRenderCost\n" << totalRenderCost << endl 720 << "#AvgRenderCost\n" << avgRenderCost << endl; 721 } 722 723 718 724 bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const 719 725 { … … 726 732 727 733 728 729 734 BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue, 730 735 VspBspTraversalData &tData) … … 785 790 if (1) 786 791 { 787 float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;788 float cBack = (float)tBackData.mPvs * tBackData.mProbability;789 float cData = (float)tData.mPvs * tData.mProbability;;790 791 float costDecr = (cFront + cBack - cData) / mBox.GetVolume();792 const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability; 793 const float cBack = (float)tBackData.mPvs * tBackData.mProbability; 794 const float cData = (float)tData.mPvs * tData.mProbability;; 795 796 const float costDecr = (cFront + cBack - cData) / mBox.GetVolume(); 792 797 793 798 mTotalCost += costDecr; 794 799 mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs; 795 800 796 mSubdivisionStats797 << "#ViewCells\n" << mBspStats.Leaves() << endl798 << "#RenderCostDecrease\n" << -costDecr << endl799 << "#TotalRenderCost\n" << mTotalCost << endl800 << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl;801 AddSubdivisionStats(mBspStats.Leaves(), 802 -costDecr, 803 0, 804 mTotalCost, 805 (float)mTotalPvsSize / (float)mBspStats.Leaves()); 801 806 } 802 807 … … 814 819 { 815 820 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode); 821 816 822 BspViewCell *viewCell = new BspViewCell(); 817 818 823 leaf->SetViewCell(viewCell); 819 824 … … 860 865 leaf->mProbability = tData.mProbability; 861 866 867 // finally evaluate stats until this leaf 862 868 EvaluateLeafStats(tData); 863 869 } … … 906 912 tBackData.mMaxCostMisses = maxCostMisses; 907 913 908 914 // statistics 909 915 if (1) 910 916 { … … 920 926 mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs; 921 927 922 mSubdivisionStats 923 << "#ViewCells\n" << mBspStats.Leaves() << endl 924 << "#RenderCostDecrease\n" << -costDecr << endl 925 << "#SplitCandidateCost\n" << splitCandidate.GetCost() << endl 926 << "#TotalRenderCost\n" << mTotalCost << endl 927 << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mBspStats.Leaves() << endl; 928 AddSubdivisionStats(mBspStats.Leaves(), 929 -costDecr, 930 splitCandidate.GetPriority(), 931 mTotalCost, 932 (float)mTotalPvsSize / (float)mBspStats.Leaves()); 928 933 } 929 934 … … 948 953 { 949 954 BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode); 955 950 956 BspViewCell *viewCell = new BspViewCell(); 951 952 957 leaf->SetViewCell(viewCell); 953 958 … … 974 979 } 975 980 976 // should I check here?981 977 982 viewCell->mLeaf = leaf; 978 983 … … 984 989 leaf->mProbability = tData.mProbability; 985 990 991 // finally evaluate stats until this leaf 986 992 EvaluateLeafStats(tData); 987 993 } … … 1029 1035 1030 1036 // compute global decrease in render cost 1031 splitData.m RenderCost= EvalRenderCostDecrease(splitData.mSplitPlane, tData);1037 splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData); 1032 1038 splitData.mParentData = tData; 1033 1039 splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; … … 1192 1198 1193 1199 // only count termination objects? 1194 if ( 1&& ray->mOriginObject)1200 if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject) 1195 1201 { 1196 1202 if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution)) 1197 1203 madeContrib = true; 1204 1198 1205 sc += contribution; 1199 1206 } … … 1214 1221 float maxBand) 1215 1222 { 1216 m SplitCandidates->clear();1223 mLocalSplitCandidates->clear(); 1217 1224 1218 1225 int requestedSize = 2 * (int)(rays.size()); 1219 1226 // creates a sorted split candidates array 1220 if (m SplitCandidates->capacity() > 500000 &&1221 requestedSize < (int)(m SplitCandidates->capacity() / 10) )1222 { 1223 delete m SplitCandidates;1224 m SplitCandidates = new vector<SortableEntry>;1225 } 1226 1227 m SplitCandidates->reserve(requestedSize);1227 if (mLocalSplitCandidates->capacity() > 500000 && 1228 requestedSize < (int)(mLocalSplitCandidates->capacity() / 10) ) 1229 { 1230 delete mLocalSplitCandidates; 1231 mLocalSplitCandidates = new vector<SortableEntry>; 1232 } 1233 1234 mLocalSplitCandidates->reserve(requestedSize); 1228 1235 1229 1236 float pos; … … 1245 1252 if (0) ClipValue(pos, minBand, maxBand); 1246 1253 1247 m SplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,1254 mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 1248 1255 pos, (*ri).mRay)); 1249 1256 … … 1252 1259 if (0) ClipValue(pos, minBand, maxBand); 1253 1260 1254 m SplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,1261 mLocalSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 1255 1262 pos, (*ri).mRay)); 1256 1263 } 1257 1264 1258 stable_sort(m SplitCandidates->begin(), mSplitCandidates->end());1265 stable_sort(mLocalSplitCandidates->begin(), mLocalSplitCandidates->end()); 1259 1266 } 1260 1267 … … 1307 1314 Intersectable *tObject = (*ri).mRay->mTerminationObject; 1308 1315 1309 if ( oObject)1316 if (COUNT_ORIGIN_OBJECTS && oObject) 1310 1317 { 1311 1318 if (!oObject->Mailed()) … … 1319 1326 } 1320 1327 } 1328 1321 1329 if (tObject) 1322 1330 { … … 1335 1343 Intersectable::NewMail(); 1336 1344 1337 vector<SortableEntry>::const_iterator ci, ci_end = m SplitCandidates->end();1338 1339 for (ci = m SplitCandidates->begin(); ci != ci_end; ++ ci)1345 vector<SortableEntry>::const_iterator ci, ci_end = mLocalSplitCandidates->end(); 1346 1347 for (ci = mLocalSplitCandidates->begin(); ci != ci_end; ++ ci) 1340 1348 { 1341 1349 VssRay *ray; … … 1350 1358 case SortableEntry::ERayMin: 1351 1359 { 1352 if ( oObject && !oObject->Mailed())1360 if (COUNT_ORIGIN_OBJECTS && oObject && !oObject->Mailed()) 1353 1361 { 1354 1362 oObject->Mail(); 1355 1363 ++ pvsl; 1356 1364 } 1365 1357 1366 if (tObject && !tObject->Mailed()) 1358 1367 { … … 1360 1369 ++ pvsl; 1361 1370 } 1371 1362 1372 break; 1363 1373 } 1364 1374 case SortableEntry::ERayMax: 1365 1375 { 1366 if ( oObject)1376 if (COUNT_ORIGIN_OBJECTS && oObject) 1367 1377 { 1368 1378 if (-- oObject->mCounter == 0) … … 1379 1389 } 1380 1390 } 1381 1382 1383 1384 // Note: sufficient to compare size of bounding boxes of front and back side? 1391 1392 1393 // Note: we compare size of bounding boxes of front and back side because 1394 // of efficiency reasons (otherwise a new geometry would have to be computed 1395 // in each step and incremential evaluation would be difficult. 1396 // but then errors happen if the geometry is not an axis aligned box 1397 // (i.e., if a geometry aligned split was taken before) 1398 // question: is it sufficient to make this approximation? 1385 1399 if (((*ci).value >= minBand) && ((*ci).value <= maxBand)) 1386 1400 { … … 1873 1887 // find front and back pvs for origing and termination object 1874 1888 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs); 1875 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs); 1889 1890 if (COUNT_ORIGIN_OBJECTS) 1891 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs); 1876 1892 } 1877 1893 … … 1910 1926 1911 1927 // -- pvs rendering heuristics 1928 1929 // upper and lower bounds 1912 1930 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 1913 1931 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 1914 1932 1915 // only render cost heuristics or combined with standard deviation 1916 const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit); 1917 const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit); 1918 const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit); 1933 const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit); 1934 const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit); 1935 const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit); 1919 1936 1920 1937 const float oldRenderCost = pOverall * penaltyOld; … … 1924 1941 const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume(); 1925 1942 1926 1927 #if 1 1943 const float weight = mRenderCostDecreaseWeight; 1928 1944 // take render cost of node into account to avoid being stuck in a local minimum 1929 1945 const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume(); 1930 1946 1931 //Debug << "rendercostdecr: " << 0.99f * renderCostDecrease << " old render cost: " << 0.01f * normalizedOldRenderCost << endl; 1932 return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost; 1933 #else 1934 return renderCostDecrease; 1935 #endif 1947 //Debug << "rendercostdecr: " << weight * renderCostDecrease << " old render cost: " << (1.0f - weight) * normalizedOldRenderCost << endl; 1948 return weight * renderCostDecrease + (1.0f - weight) * normalizedOldRenderCost; 1936 1949 } 1937 1950 … … 1944 1957 float &pBack) const 1945 1958 { 1946 float cost = 0;1947 1948 1959 float totalPvs = 0; 1949 1960 float pvsFront = 0; … … 1957 1968 pBack = 0; 1958 1969 1959 1960 int limit; 1961 bool useRand; 1962 1970 int numTests; // the number of tests 1971 1972 // if random samples shold be taken instead of testing all the rays 1973 bool useRand; 1974 1975 if ((int)data.mRays->size() > mMaxTests) 1976 { 1977 useRand = true; 1978 numTests = mMaxTests; 1979 } 1980 else 1981 { 1982 useRand = false; 1983 numTests = (int)data.mRays->size(); 1984 } 1985 1963 1986 // create unique ids for pvs heuristics 1964 1987 GenerateUniqueIdsForPvs(); 1965 1988 1966 // choose test rays randomly if too much 1967 if ((int)data.mRays->size() > mMaxTests) 1968 { 1969 useRand = true; 1970 limit = mMaxTests; 1971 } 1972 else 1973 { 1974 useRand = false; 1975 limit = (int)data.mRays->size(); 1976 } 1977 1978 for (int i = 0; i < limit; ++ i) 1989 for (int i = 0; i < numTests; ++ i) 1979 1990 { 1980 1991 const int testIdx = useRand ? … … 1988 1999 // find front and back pvs for origing and termination object 1989 2000 AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs); 1990 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs); 2001 2002 if (COUNT_ORIGIN_OBJECTS) 2003 AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs); 1991 2004 } 1992 2005 … … 2057 2070 } 2058 2071 2059 co st += mPvsFactor * newCost / (oldCost + Limits::Small);2072 const float cost = mPvsFactor * newCost / (oldCost + Limits::Small); 2060 2073 2061 2074 … … 2165 2178 for(rit = data.mRays->begin(); rit != rit_end; ++ rit) 2166 2179 { 2167 //if (!(*rit).mRay->IsActive()) continue;2168 2169 2180 // determine the side of this ray with respect to the plane 2170 2181 float t; … … 2172 2183 2173 2184 AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal); 2174 AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal); 2175 } 2185 2186 if (COUNT_ORIGIN_OBJECTS) 2187 AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal); 2188 } 2189 2176 2190 2177 2191 //-- pvs heuristics 2178 float pOverall; 2179 2180 //-- compute heurstics 2181 //-- we take simplified computation for mid split 2182 2183 pOverall = data.mProbability; 2184 2192 2193 float pOverall = data.mProbability; 2194 2195 // note: we use a simplified computation assuming that we always do a 2196 // spatial mid split 2197 2185 2198 if (!mUseAreaForPvs) 2186 { // volume 2199 { 2200 // volume 2187 2201 pBack = pFront = pOverall * 0.5f; 2188 2189 2202 #if 0 2190 2203 // box length substitute for probability … … 3220 3233 VssRay *ray = (*rit).mRay; 3221 3234 3222 if ( ray->mOriginObject)3235 if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject) 3223 3236 { 3224 3237 if (!ray->mOriginObject->Mailed()) … … 3228 3241 } 3229 3242 } 3243 3230 3244 if (ray->mTerminationObject) 3231 3245 { … … 3343 3357 } 3344 3358 else // one of the ray end points is on the plane 3345 { // NOTE: what to do if ray is coincident with plane? 3359 { 3360 // NOTE: what to do if ray is coincident with plane? 3346 3361 if (extSide < 0) 3347 3362 node = in->GetBack(); … … 3365 3380 ViewCell *viewCell; 3366 3381 3382 // question: always contribute to leaf or to currently active view cell? 3367 3383 if (0) 3368 3384 viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell()); -
GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.h
r1016 r1020 168 168 VspBspTraversalData mParentData; 169 169 // prioriry of this split 170 float m RenderCost;171 172 VspBspSplitCandidate(): m RenderCost(0)170 float mPriority; 171 172 VspBspSplitCandidate(): mPriority(0) 173 173 {}; 174 174 175 175 VspBspSplitCandidate(const Plane3 &plane, const VspBspTraversalData &tData): 176 mSplitPlane(plane), mParentData(tData), m RenderCost(0)176 mSplitPlane(plane), mParentData(tData), mPriority(0) 177 177 {} 178 178 179 179 /** Returns cost of the traversal data. 180 180 */ 181 float Get Cost() const181 float GetPriority() const 182 182 { 183 183 #if 1 184 return m RenderCost;184 return mPriority; 185 185 #else 186 186 return (float) (-mDepth); // for kd tree … … 190 190 friend bool operator<(const VspBspSplitCandidate &a, const VspBspSplitCandidate &b) 191 191 { 192 return a.Get Cost() < b.GetCost();192 return a.GetPriority() < b.GetPriority(); 193 193 } 194 194 }; … … 211 211 /** Constructs the tree from a given set of rays. 212 212 @param sampleRays the set of sample rays the construction is based on 213 @param viewCells if not NULL, new view cells are 214 created in the leafs and stored in the container 213 @param forcedBoundingBox overwrites the view space box 215 214 */ 216 215 void Construct(const VssRayContainer &sampleRays, … … 454 453 VspBspTraversalData &tData); 455 454 455 /** Subdivides node using a best split priority queue. 456 @param tQueue the best split priority queue 457 @param splitCandidate the candidate for the next split 458 @returns new root of the subtree 459 */ 456 460 BspNode *Subdivide(VspBspSplitQueue &tQueue, 457 461 VspBspSplitCandidate &splitCandidate); … … 459 463 /** Constructs the tree from the given traversal data. 460 464 @param polys stores set of polygons on which subdivision may be based 461 @param rays stores set of rays on which subdivision may be based465 @param rays stores set of rays on which subdivision may be based 462 466 */ 463 467 void Construct(const PolygonContainer &polys, RayInfoContainer *rays); … … 496 500 497 501 /** Subdivides leaf. 498 @param leaf the leaf to be subdivided 499 500 @param polys the polygons to be split 501 @param frontPolys returns the polygons in front of the split plane 502 @param backPolys returns the polygons in the back of the split plane 502 503 @param tData data object holding, e.g., a pointer to the leaf 504 @param frontData returns the data (e.g., pointer to the leaf) in front of the split plane 505 @param backData returns the data (e.g., pointer to the leaf) in the back of the split plane 503 506 504 507 @param rays the polygons to be filtered 505 508 @param frontRays returns the polygons in front of the split plane 506 @param backRays returns the polygons in the back of the split plane 509 @param coincident returns the polygons which are coincident to the plane and thus discarded 510 for traversal 507 511 508 512 @returns the root of the subdivision … … 699 703 700 704 705 /** Adds stats to subdivision log file. 706 */ 707 void AddSubdivisionStats(const int viewCells, 708 const float renderCostDecr, 709 const float splitCandidateCost, 710 const float totalRenderCost, 711 const float avgRenderCost); 701 712 702 713 /////////////////////////////////////////////////////////// … … 716 727 717 728 /// sorted split candidates used for sweep-heuristics 718 vector<SortableEntry> *m SplitCandidates;729 vector<SortableEntry> *mLocalSplitCandidates; 719 730 720 731 /// box around the whole view domain … … 837 848 // if rays should be stored in leaves 838 849 bool mStoreRays; 839 /// render cost weight between expected valueand variance850 /// weight between render cost (expected value) and variance 840 851 float mRenderCostWeight; 841 852 /// weight between render cost decrease and node render cost 853 float mRenderCostDecreaseWeight; 842 854 843 855 //-- subdivision statistics -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp
r1016 r1020 16 16 #include "ViewCellsManager.h" 17 17 #include "Beam.h" 18 #include "KdTree.h" 19 18 20 19 21 namespace GtpVisibilityPreprocessor { … … 381 383 382 384 383 void VspTree:: Construct(const VssRayContainer &sampleRays,384 AxisAlignedBox3 *forcedBoundingBox)385 void VspTree::PrepareConstruction(const VssRayContainer &sampleRays, 386 AxisAlignedBox3 *forcedBoundingBox) 385 387 { 386 388 mVspStats.nodes = 1; 387 mBo x.Initialize(); // initialise BSPtree bounding box389 mBoundingBox.Initialize(); // initialise vsp tree bounding box 388 390 389 391 if (forcedBoundingBox) 390 mBox = *forcedBoundingBox; 391 392 PolygonContainer polys; 393 RayInfoContainer *rays = new RayInfoContainer(); 394 392 mBoundingBox = *forcedBoundingBox; 393 395 394 VssRayContainer::const_iterator rit, rit_end = sampleRays.end(); 396 395 397 long startTime = GetTime();398 399 cout << "Extracting polygons from rays ... ";400 401 396 Intersectable::NewMail(); 402 397 403 int numObj = 0; 404 405 //-- store rays 398 //-- compute bounding box 406 399 for (rit = sampleRays.begin(); rit != rit_end; ++ rit) 407 400 { 408 401 VssRay *ray = *rit; 409 402 410 float minT, maxT; 411 412 static Ray hray; 413 hray.Init(*ray); 414 415 // TODO: not very efficient to implictly cast between rays types 416 if (mBox.GetRaySegment(hray, minT, maxT)) 417 { 418 float len = ray->Length(); 419 420 if (!len) 421 len = Limits::Small; 422 423 rays->push_back(RayInfo(ray, minT / len, maxT / len)); 424 } 425 } 426 427 mTermMinProbability *= mBox.GetVolume(); 428 403 // compute bounding box of view space 404 if (!forcedBoundingBox) 405 { 406 mBoundingBox.Include(ray->GetTermination()); 407 mBoundingBox.Include(ray->GetOrigin()); 408 } 409 } 410 411 mTermMinProbability *= mBoundingBox.GetVolume(); 429 412 mGlobalCostMisses = 0; 430 431 cout << "finished" << endl; 432 433 // use split cost priority queue 434 Construct(rays); 413 } 414 415 416 void VspTree::AddSubdivisionStats(const int viewCells, 417 const float renderCostDecr, 418 const float splitCandidateCost, 419 const float totalRenderCost, 420 const float avgRenderCost) 421 { 422 mSubdivisionStats 423 << "#ViewCells\n" << viewCells << endl 424 << "#RenderCostDecrease\n" << renderCostDecr << endl 425 << "#SplitCandidateCost\n" << splitCandidateCost << endl 426 << "#TotalRenderCost\n" << totalRenderCost << endl 427 << "#AvgRenderCost\n" << avgRenderCost << endl; 435 428 } 436 429 … … 449 442 450 443 451 void VspTree::Construct(RayInfoContainer *rays)452 {453 #if TODO454 VspSplitQueue tQueue;455 /// create new vsp tree456 mRoot = new VspLeaf();457 /// we use the overall probability as normalizer458 const float prop = mBox.GetVolume();459 460 VspTraversalData tData(mRoot,461 0,462 rays,463 ComputePvsSize(*rays),464 prop,465 mBox);466 467 468 // compute first split candidate469 VspSplitCandidate splitCandidate;470 EvalSplitCandidate(tData, splitCandidate);471 472 tQueue.push(splitCandidate);473 474 mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();475 mTotalPvsSize = tData.mPvs;476 477 mSubdivisionStats478 << "#ViewCells\n1\n" << endl479 << "#RenderCostDecrease\n0\n" << endl480 << "#SplitCandidateCost\n0\n" << endl481 << "#TotalRenderCost\n" << mTotalCost << endl482 << "#AvgRenderCost\n" << mTotalPvsSize << endl;483 484 Debug << "total cost: " << mTotalCost << endl;485 486 487 mVspStats.Start();488 cout << "Constructing vsp bsp tree ... \n";489 490 long startTime = GetTime();491 int nLeaves = 500;492 int nViewCells = 500;493 494 // used for intermediate time measurements and progress495 long interTime = GetTime();496 497 mOutOfMemory = false;498 499 mCreatedViewCells = 0;500 501 while (!tQueue.empty())502 {503 splitCandidate = tQueue.top();504 tQueue.pop();505 506 // cost ratio of cost decrease / totalCost507 float costRatio = splitCandidate.GetCost() / mTotalCost;508 509 //Debug << "cost ratio: " << costRatio << endl;510 511 if (costRatio < mTermMinGlobalCostRatio)512 ++ mGlobalCostMisses;513 514 if (0 && !mOutOfMemory)515 {516 float mem = GetMemUsage();517 518 if (mem > mMaxMemory)519 {520 mOutOfMemory = true;521 Debug << "memory limit reached: " << mem << endl;522 }523 }524 525 // subdivide leaf node526 VspNode *r = Subdivide(tQueue, splitCandidate);527 528 if (r == mRoot)529 Debug << "VSP BSP tree construction time spent at root: "530 << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;531 532 if (mVspStats.Leaves() >= nLeaves)533 {534 nLeaves += 500;535 536 cout << "leaves=" << mVspStats.Leaves() << endl;537 Debug << "needed "538 << TimeDiff(interTime, GetTime())*1e-3539 << " secs to create 500 view cells" << endl;540 interTime = GetTime();541 }542 543 if (mCreatedViewCells == nViewCells)544 {545 nViewCells += 500;546 547 cout << "generated " << mCreatedViewCells << " viewcells" << endl;548 }549 }550 551 Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;552 cout << "finished\n";553 554 mVspStats.Stop();555 #endif556 }557 558 559 444 bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const 560 445 { … … 577 462 578 463 579 // subdivide using a split plane queue580 464 VspNode *VspTree::Subdivide(SplitQueue &tQueue, 581 VspSplitCandidate &splitCandidate) 465 VspSplitCandidate &splitCandidate, 466 const bool globalCriteriaMet) 582 467 { 583 468 VspTraversalData &tData = splitCandidate.mParentData; … … 585 470 VspNode *newNode = tData.mNode; 586 471 587 if (!LocalTerminationCriteriaMet(tData) && ! GlobalTerminationCriteriaMet(tData))472 if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet) 588 473 { 589 474 VspTraversalData tFrontData; … … 594 479 // create new interior node and two leaf node 595 480 const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane; 596 597 481 newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData); 598 482 … … 604 488 tBackData.mMaxCostMisses = maxCostMisses; 605 489 606 490 //-- statistics 607 491 if (1) 608 492 { 609 float cFront = (float)tFrontData.mPvs * tFrontData.mProbability; 610 float cBack = (float)tBackData.mPvs * tBackData.mProbability; 611 float cData = (float)tData.mPvs * tData.mProbability; 612 613 614 float costDecr = 615 (cFront + cBack - cData) / mBox.GetVolume(); 493 const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability; 494 const float cBack = (float)tBackData.mPvs * tBackData.mProbability; 495 const float cData = (float)tData.mPvs * tData.mProbability; 496 497 const float costDecr = 498 (cFront + cBack - cData) / mBoundingBox.GetVolume(); 616 499 617 500 mTotalCost += costDecr; 618 501 mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs; 619 502 620 mSubdivisionStats 621 << "#ViewCells\n" << mVspStats.Leaves() << endl 622 << "#RenderCostDecrease\n" << -costDecr << endl 623 << "#SplitCandidateCost\n" << splitCandidate.GetPriority() << endl 624 << "#TotalRenderCost\n" << mTotalCost << endl 625 << "#AvgRenderCost\n" << (float)mTotalPvsSize / (float)mVspStats.Leaves() << endl; 626 } 627 628 629 //-- push the new split candidates on the stack 630 VspSplitCandidate frontCandidate; 631 VspSplitCandidate backCandidate; 632 633 EvalSplitCandidate(tFrontData, frontCandidate); 634 EvalSplitCandidate(tBackData, backCandidate); 635 #if TODO 503 AddSubdivisionStats(mVspStats.Leaves(), 504 -costDecr, 505 splitCandidate.GetPriority(), 506 mTotalCost, 507 (float)mTotalPvsSize / (float)mVspStats.Leaves()); 508 } 509 510 511 //-- push the new split candidates on the queue 512 VspSplitCandidate *frontCandidate = new VspSplitCandidate(); 513 VspSplitCandidate *backCandidate = new VspSplitCandidate(); 514 515 EvalSplitCandidate(tFrontData, *frontCandidate); 516 EvalSplitCandidate(tBackData, *backCandidate); 517 636 518 tQueue.push(frontCandidate); 637 519 tQueue.push(backCandidate); 638 #endif 520 639 521 // delete old leaf node 640 522 DEL_PTR(tData.mNode); … … 646 528 { 647 529 VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode); 530 648 531 VspViewCell *viewCell = new VspViewCell(); 649 650 532 leaf->SetViewCell(viewCell); 651 533 … … 671 553 } 672 554 } 673 674 // should I check here? 555 675 556 viewCell->mLeaf = leaf; 676 557 … … 678 559 leaf->mProbability = tData.mProbability; 679 560 680 EvaluateLeafStats(tData); 561 // finally evaluate stats until this leaf 562 EvaluateLeafStats(tData); 681 563 } 682 564 683 565 //-- cleanup 684 566 tData.Clear(); 685 567 686 568 return newNode; 687 569 } … … 691 573 VspSplitCandidate &splitData) 692 574 { 693 VspTraversalData frontData;694 VspTraversalData backData;695 575 float frontProb; 576 float backtProb; 577 696 578 VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode); 697 579 698 580 // compute locally best split plane 699 581 const bool success = 700 582 SelectPlane(tData, splitData.mSplitPlane, 701 front Data.mProbability, backData.mProbability);583 frontProb, backtProb); 702 584 703 585 //TODO … … 789 671 return interior; 790 672 } 791 792 /*793 KdNode *VspOpsTree::SubdivideSpatialNode(KdLeaf *leaf,794 const AxisAlignedPlane &splitPlane,795 const AxisAlignedBox3 &box,796 AxisAlignedBox3 &backBBox,797 AxisAlignedBox3 &frontBBox)798 {799 float position;800 801 #if TODO802 mSpatialStat.nodes += 2;803 mSpatialStat.splits[axis];804 #endif805 806 // add the new nodes to the tree807 KdInterior *node = new KdInterior(leaf->mParent);808 809 node->mAxis = splitPlane.mAxis;810 node->mPosition = splitPlane.mPosition;811 node->mBox = box;812 813 backBBox = box;814 frontBBox = box;815 816 // first count ray sides817 int objectsBack = 0;818 int objectsFront = 0;819 820 backBBox.SetMax(axis, position);821 frontBBox.SetMin(axis, position);822 823 SplitObjects(leaf->m824 ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();825 826 for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)827 {828 // determine the side of this ray with respect to the plane829 AxisAlignedBox3 box = (*mi)->GetBox();830 831 if (box.Max(axis) > position )832 ++ objectsFront;833 834 if (box.Min(axis) < position )835 objectsBack++;836 }837 838 839 KdLeaf *back = new KdLeaf(node, objectsBack);840 KdLeaf *front = new KdLeaf(node, objectsFront);841 842 // replace a link from node's parent843 if ( leaf->mParent )844 leaf->mParent->ReplaceChildLink(leaf, node);845 846 // and setup child links847 node->SetupChildLinks(back, front);848 849 for (mi = leaf->mObjects.begin();850 mi != leaf->mObjects.end();851 mi++) {852 // determine the side of this ray with respect to the plane853 AxisAlignedBox3 box = (*mi)->GetBox();854 855 if (box.Max(axis) >= position )856 front->mObjects.push_back(*mi);857 858 if (box.Min(axis) < position )859 back->mObjects.push_back(*mi);860 861 mStat.objectRefs -= (int)leaf->mObjects.size();862 mStat.objectRefs += objectsBack + objectsFront;863 }864 865 delete leaf;866 return node;867 }868 */869 870 673 871 674 … … 1267 1070 1268 1071 1269 // 1072 //-- pvs rendering heuristics 1270 1073 const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize(); 1271 1074 const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize(); 1272 1075 1273 // only render cost heuristics or combined with standard deviation1274 const float penaltyOld = EvalPvsPenalty( totalPvs, lowerPvsLimit, upperPvsLimit);1275 const float penaltyFront = EvalPvsPenalty( pvsFront, lowerPvsLimit, upperPvsLimit);1276 const float penaltyBack = EvalPvsPenalty( pvsBack, lowerPvsLimit, upperPvsLimit);1076 //-- only render cost heuristics or combined with standard deviation 1077 const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit); 1078 const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit); 1079 const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit); 1277 1080 1278 1081 const float oldRenderCost = pOverall * penaltyOld; … … 1280 1083 1281 1084 //Debug << "decrease: " << oldRenderCost - newRenderCost << endl; 1282 const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBo x.GetVolume();1085 const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume(); 1283 1086 1284 1087 1285 1088 #if 1 1286 // take render cost of node into account to avoid being stuck in a local minimum 1287 const float normalizedOldRenderCost = oldRenderCost / mBox.GetVolume(); 1089 // take render cost of node into account 1090 // otherwise danger of being stuck in a local minimum!! 1091 const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume(); 1288 1092 return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost; 1289 1093 #else … … 1434 1238 AxisAlignedBox3 VspTree::GetBoundingBox() const 1435 1239 { 1436 return mBo x;1240 return mBoundingBox; 1437 1241 } 1438 1242 … … 1581 1385 void VspTree::ValidateTree() 1582 1386 { 1387 mVspStats.invalidLeaves = 0; 1388 1583 1389 stack<VspNode *> nodeStack; 1584 1390 … … 1587 1393 1588 1394 nodeStack.push(mRoot); 1589 1590 mVspStats.invalidLeaves = 0; 1395 1591 1396 while (!nodeStack.empty()) 1592 1397 { … … 1662 1467 } 1663 1468 } 1664 1665 1469 } 1666 1470 1667 1471 1668 1472 int VspTree::FindNeighbors(VspLeaf *n, 1669 1670 1473 vector<VspLeaf *> &neighbors, 1474 const bool onlyUnmailed) const 1671 1475 { 1672 1476 stack<VspNode *> nodeStack; 1673 1674 1477 nodeStack.push(mRoot); 1675 1478 … … 1946 1749 float maxt, mint; 1947 1750 1948 if (!mBo x.GetRaySegment(ray, mint, maxt))1751 if (!mBoundingBox.GetRaySegment(ray, mint, maxt)) 1949 1752 return 0; 1950 1753 … … 1978 1781 // cases N1,N2,N3,P5,Z2,Z3 1979 1782 continue; 1980 } else 1783 } 1784 else 1981 1785 { 1982 1786 // case N4 … … 2020 1824 ++ hits; 2021 1825 } 2022 2023 1826 #if 0 2024 1827 leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0))); 2025 1828 #endif 2026 1829 // get the next node from the stack … … 2088 1891 { 2089 1892 int collapsed = 0; 2090 //TODO 2091 #if HAS_TO_BE_REDONE 1893 2092 1894 (void)CollapseTree(mRoot, collapsed); 2093 2094 1895 // revalidate leaves 2095 1896 RepairViewCellsLeafLists(); 2096 #endif 1897 2097 1898 return collapsed; 2098 1899 } … … 2286 2087 2287 2088 int VspTree::SplitRays(const AxisAlignedPlane &plane, 2288 2289 2290 2089 RayInfoContainer &rays, 2090 RayInfoContainer &frontRays, 2091 RayInfoContainer &backRays) const 2291 2092 { 2292 2093 int splits = 0; … … 2338 2139 { 2339 2140 if (!node->GetParent()) 2340 return mBo x;2141 return mBoundingBox; 2341 2142 2342 2143 if (!node->IsLeaf()) … … 2358 2159 2359 2160 2161 2162 /*****************************************************************/ 2163 /* class OpsTree implementation */ 2164 /*****************************************************************/ 2165 2166 2167 void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane, 2168 const ObjectContainer &objects, 2169 ObjectContainer &back, 2170 ObjectContainer &front) 2171 { 2172 ObjectContainer::const_iterator oit, oit_end = objects.end(); 2173 2174 for (oit = objects.begin(); oit != oit_end; ++ oit) 2175 { 2176 // determine the side of this ray with respect to the plane 2177 const AxisAlignedBox3 box = (*oit)->GetBox(); 2178 2179 if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition) 2180 front.push_back(*oit); 2181 2182 if (box.Min(splitPlane.mAxis) < splitPlane.mPosition) 2183 back.push_back(*oit); 2184 #if TODO 2185 mStat.objectRefs -= (int)objects.size(); 2186 mStat.objectRefs += objectsBack + objectsFront; 2187 #endif 2188 } 2189 } 2190 2191 2192 KdInterior *OspTree::SubdivideNode(KdLeaf *leaf, 2193 const AxisAlignedPlane &splitPlane, 2194 const AxisAlignedBox3 &box, 2195 AxisAlignedBox3 &backBBox, 2196 AxisAlignedBox3 &frontBBox) 2197 { 2198 #if TODO 2199 mSpatialStat.nodes += 2; 2200 mSpatialStat.splits[axis]; 2201 #endif 2202 2203 // add the new nodes to the tree 2204 KdInterior *node = new KdInterior(leaf->mParent); 2205 2206 const int axis = splitPlane.mAxis; 2207 const float position = splitPlane.mPosition; 2208 2209 node->mAxis = axis; 2210 node->mPosition = position; 2211 node->mBox = box; 2212 2213 backBBox = box; 2214 frontBBox = box; 2215 2216 // first count ray sides 2217 int objectsBack = 0; 2218 int objectsFront = 0; 2219 2220 backBBox.SetMax(axis, position); 2221 frontBBox.SetMin(axis, position); 2222 2223 ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end(); 2224 2225 for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi) 2226 { 2227 // determine the side of this ray with respect to the plane 2228 const AxisAlignedBox3 box = (*mi)->GetBox(); 2229 2230 if (box.Max(axis) > position) 2231 ++ objectsFront; 2232 2233 if (box.Min(axis) < position) 2234 ++ objectsBack; 2235 } 2236 2237 KdLeaf *back = new KdLeaf(node, objectsBack); 2238 KdLeaf *front = new KdLeaf(node, objectsFront); 2239 2240 // replace a link from node's parent 2241 if (leaf->mParent) 2242 leaf->mParent->ReplaceChildLink(leaf, node); 2243 2244 // and setup child links 2245 node->SetupChildLinks(back, front); 2246 2247 SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects); 2248 2249 //delete leaf; 2250 return node; 2251 } 2252 2253 2254 KdNode *OspTree::Subdivide(SplitQueue &tQueue, 2255 OspSplitCandidate &splitCandidate, 2256 const bool globalCriteriaMet) 2257 { 2258 OspTraversalData &tData = splitCandidate.mParentData; 2259 2260 KdNode *newNode = tData.mNode; 2261 2262 if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet) 2263 { 2264 OspTraversalData tFrontData; 2265 OspTraversalData tBackData; 2266 2267 //-- continue subdivision 2268 2269 // create new interior node and two leaf node 2270 const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane; 2271 newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode), 2272 splitPlane, 2273 tData.mBoundingBox, 2274 tFrontData.mBoundingBox, 2275 tBackData.mBoundingBox); 2276 2277 const int maxCostMisses = splitCandidate.mMaxCostMisses; 2278 2279 // how often was max cost ratio missed in this branch? 2280 tFrontData.mMaxCostMisses = maxCostMisses; 2281 tBackData.mMaxCostMisses = maxCostMisses; 2282 2283 //-- push the new split candidates on the queue 2284 OspSplitCandidate *frontCandidate = new OspSplitCandidate(); 2285 OspSplitCandidate *backCandidate = new OspSplitCandidate(); 2286 2287 EvalSplitCandidate(tFrontData, *frontCandidate); 2288 EvalSplitCandidate(tBackData, *backCandidate); 2289 2290 tQueue.push(frontCandidate); 2291 tQueue.push(backCandidate); 2292 2293 // delete old leaf node 2294 DEL_PTR(tData.mNode); 2295 } 2296 2297 2298 //-- terminate traversal 2299 if (newNode->IsLeaf()) 2300 { 2301 //KdLeaf *leaf = dynamic_cast<KdLeaf *>(newNode); 2302 EvaluateLeafStats(tData); 2303 } 2304 2305 //-- cleanup 2306 tData.Clear(); 2307 2308 return newNode; 2309 } 2310 2311 2312 void OspTree::EvalSplitCandidate(OspTraversalData &tData, 2313 OspSplitCandidate &splitData) 2314 { 2315 float frontProb; 2316 float backtProb; 2317 2318 KdLeaf *leaf = dynamic_cast<KdLeaf *>(tData.mNode); 2319 2320 // compute locally best split plane 2321 const bool success = false; 2322 #if TODO 2323 SelectPlane(tData, splitData.mSplitPlane, 2324 frontData.mProbability, backData.mProbability); 2325 2326 //TODO 2327 // compute global decrease in render cost 2328 splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData); 2329 splitData.mParentData = tData; 2330 splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1; 2331 #endif 2332 } 2333 2334 2360 2335 /*****************************************************************/ 2361 2336 /* class HierarchyManager implementation */ … … 2376 2351 2377 2352 2378 void HierarchyManager::PrepareTraversal() 2379 { 2380 2381 #if TODO 2382 /// create new vsp tree 2383 mRoot = new VspLeaf(); 2384 /// we use the overall probability as normalizer 2385 const float prop = mBoundingBox.GetVolume(); 2386 2387 VspTraversalData tData(mRoot, 2388 0, 2389 rays, 2390 ComputePvsSize(*rays), 2391 prop, 2392 mBoundingBox); 2393 2394 2395 // compute first split candidates 2396 VspTree::VspSplitCandidate vspSplitCandidate = new VspTree::VspSplitCandidate(); 2397 EvalSplitCandidate(tData, *vspSplitCandidate); 2398 mTQueue.push(splitCandidate); 2399 2400 OspSplitCandidate ospSplitCandidate = new OspSplitCandidate(); 2401 EvalSplitCandidate(tData, *ospSplitCandidate); 2402 mTQueue.push(ospSplitCandidate); 2403 2404 mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume(); 2405 mTotalPvsSize = tData.mPvs; 2406 2407 mSubdivisionStats 2408 << "#ViewCells\n1\n" << endl 2409 << "#RenderCostDecrease\n0\n" << endl 2410 << "#SplitCandidateCost\n0\n" << endl 2411 << "#TotalRenderCost\n" << mTotalCost << endl 2412 << "#AvgRenderCost\n" << mTotalPvsSize << endl; 2413 2414 Debug << "total cost: " << mTotalCost << endl; 2415 2416 #endif 2353 void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays, 2354 AxisAlignedBox3 *forcedViewSpace, 2355 RayInfoContainer &rays) 2356 { 2357 VssRayContainer::const_iterator rit, rit_end = sampleRays.end(); 2358 2359 long startTime = GetTime(); 2360 2361 cout << "storing rays ... "; 2362 2363 Intersectable::NewMail(); 2364 2365 mVspTree->PrepareConstruction(sampleRays, forcedViewSpace); 2366 2367 //-- store rays 2368 for (rit = sampleRays.begin(); rit != rit_end; ++ rit) 2369 { 2370 VssRay *ray = *rit; 2371 2372 float minT, maxT; 2373 2374 static Ray hray; 2375 hray.Init(*ray); 2376 2377 // TODO: not very efficient to implictly cast between rays types 2378 if (mBoundingBox.GetRaySegment(hray, minT, maxT)) 2379 { 2380 float len = ray->Length(); 2381 2382 if (!len) 2383 len = Limits::Small; 2384 2385 rays.push_back(RayInfo(ray, minT / len, maxT / len)); 2386 } 2387 } 2388 2389 cout << "finished" << endl; 2390 2391 //mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays); 2392 } 2393 2394 2395 bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const 2396 { 2397 if (candidate->Type() == SplitCandidate::VIEW_SPACE) 2398 { 2399 VspTree::VspSplitCandidate *sc = 2400 dynamic_cast<VspTree::VspSplitCandidate *>(candidate); 2401 2402 return mVspTree->GlobalTerminationCriteriaMet(sc->mParentData); 2403 } 2404 2405 return true; 2417 2406 } 2418 2407 … … 2420 2409 void HierarchyManager::Construct(const VssRayContainer &sampleRays, 2421 2410 const ObjectContainer &objects, 2422 AxisAlignedBox3 *forcedBoundingBox) 2423 { 2424 #if TODO 2425 //-- store rays 2426 for (rit = sampleRays.begin(); rit != rit_end; ++ rit) 2427 { 2428 VssRay *ray = *rit; 2429 2430 float minT, maxT; 2431 2432 static Ray hray; 2433 hray.Init(*ray); 2434 2435 // TODO: not very efficient to implictly cast between rays types 2436 if (mBoundingBox.GetRaySegment(hray, minT, maxT)) 2437 { 2438 float len = ray->Length(); 2439 2440 if (!len) 2441 len = Limits::Small; 2442 2443 rays->push_back(RayInfo(ray, minT / len, maxT / len)); 2444 } 2445 } 2446 #endif 2447 } 2448 2449 2450 bool HierarchyManager::FinishedConstruction() 2451 { 2452 return mTQueue.empty(); 2453 } 2454 2455 2456 void HierarchyManager::Construct(RayInfoContainer *rays) 2457 { 2458 PrepareTraversal(); 2411 AxisAlignedBox3 *forcedViewSpace) 2412 { 2413 RayInfoContainer *rays = new RayInfoContainer(); 2414 2415 // prepare vsp and osp trees for traversal 2416 PrepareConstruction(sampleRays, forcedViewSpace, *rays); 2459 2417 2460 2418 mVspTree->mVspStats.Start(); 2461 cout << "Constructing vsp bsp tree ... \n"; 2462 2419 2420 cout << "Constructing view space / object space tree ... \n"; 2463 2421 const long startTime = GetTime(); 2464 2422 … … 2467 2425 SplitCandidate *splitCandidate = NextSplitCandidate(); 2468 2426 2427 const bool globalTerminationCriteriaMet = 2428 GlobalTerminationCriteriaMet(splitCandidate); 2429 2469 2430 // cost ratio of cost decrease / totalCost 2470 2431 const float costRatio = splitCandidate->GetPriority() / mTotalCost; 2471 2472 2432 //Debug << "cost ratio: " << costRatio << endl; 2473 2433 … … 2475 2435 ++ mGlobalCostMisses; 2476 2436 2477 // subdivide leaf node2478 // either object space or view space2437 //-- subdivide leaf node 2438 //-- either a object space or view space split 2479 2439 if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE) 2480 2440 { … … 2482 2442 dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate); 2483 2443 2484 VspNode *r = mVspTree->Subdivide(mTQueue, *sc );2485 } 2486 else // object space 2444 VspNode *r = mVspTree->Subdivide(mTQueue, *sc, globalTerminationCriteriaMet); 2445 } 2446 else // object space split 2487 2447 { 2488 2448 #if TODO … … 2490 2450 #endif 2491 2451 } 2492 } 2493 2494 cout << "finished\n"; 2452 2453 DEL_PTR(splitCandidate); 2454 } 2455 2456 cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl; 2495 2457 2496 2458 mVspTree->mVspStats.Stop(); 2497 2459 } 2498 2460 2499 } 2461 2462 bool HierarchyManager::FinishedConstruction() 2463 { 2464 return mTQueue.empty(); 2465 } 2466 2467 2468 } -
GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.h
r1016 r1020 28 28 class VspLeaf; 29 29 class VspNode; 30 30 class KdNode; 31 class KdInterior; 32 class KdLeaf; 33 34 class KdTreeStatistics; 31 35 32 36 /** A definition for an axis aligned plane. … … 36 40 public: 37 41 42 /** Computes intersection of this plane with the ray segment. 43 */ 38 44 int ComputeRayIntersection(const RayInfo &rayData, float &t) const 39 45 { … … 41 47 } 42 48 49 /// the split axis: one of 0=x, 1=y, 2=z 43 50 int mAxis; 51 /// the absolute position of the split axis 44 52 float mPosition; 45 53 }; 54 46 55 47 56 /** Candidate for a view space / object space split. … … 184 193 }; 185 194 195 196 /** View space partition statistics. 197 */ 198 class OspTreeStatistics: public StatisticsBase 199 { 200 public: 201 // total number of nodes 202 int nodes; 203 // number of splits 204 int splits[3]; 205 206 // totals number of rays 207 int rays; 208 // maximal reached depth 209 int maxDepth; 210 // minimal depth 211 int minDepth; 212 213 // max depth nodes 214 int maxDepthNodes; 215 // minimum depth nodes 216 int minDepthNodes; 217 // max depth nodes 218 int minPvsNodes; 219 // nodes with minimum PVS 220 int minRaysNodes; 221 // max ray contribution nodes 222 int maxRayContribNodes; 223 // minimum area nodes 224 int minProbabilityNodes; 225 /// nodes termination because of max cost ratio; 226 int maxCostNodes; 227 // max number of rays per node 228 int maxObjectRefs; 229 /// samples contributing to pvs 230 int contributingSamples; 231 /// sample contributions to pvs 232 int sampleContributions; 233 /// largest pvs 234 int maxPvs; 235 /// number of invalid leaves 236 int invalidLeaves; 237 /// accumulated number of rays refs 238 int accumRays; 239 int pvs; 240 // accumulated depth (used to compute average) 241 int accumDepth; 242 243 // Constructor 244 OspTreeStatistics() 245 { 246 Reset(); 247 } 248 249 int Nodes() const {return nodes;} 250 int Interior() const { return nodes / 2; } 251 int Leaves() const { return (nodes / 2) + 1; } 252 253 // TODO: computation wrong 254 double AvgDepth() const { return accumDepth / (double)Leaves();}; 255 double AvgRays() const { return accumRays / (double)Leaves();}; 256 257 void Reset() 258 { 259 nodes = 0; 260 for (int i = 0; i < 3; ++ i) 261 splits[i] = 0; 262 263 maxDepth = 0; 264 minDepth = 99999; 265 accumDepth = 0; 266 pvs = 0; 267 maxDepthNodes = 0; 268 minPvsNodes = 0; 269 minRaysNodes = 0; 270 maxRayContribNodes = 0; 271 minProbabilityNodes = 0; 272 maxCostNodes = 0; 273 274 contributingSamples = 0; 275 sampleContributions = 0; 276 277 maxPvs = 0; 278 invalidLeaves = 0; 279 accumRays = 0; 280 } 281 282 void Print(ostream &app) const; 283 284 friend ostream &operator<<(ostream &s, const OspTreeStatistics &stat) 285 { 286 stat.Print(s); 287 return s; 288 } 289 }; 290 291 186 292 /** 187 293 VspNode abstract class serving for interior and leaf node implementation 188 294 */ 189 class VspNode 295 class VspNode 190 296 { 191 297 public: … … 530 636 AxisAlignedBox3 GetBBox(VspNode *node) const; 531 637 532 /** Constructs the tree from a given set of rays.533 @param sampleRays the set of sample rays the construction is based on534 @param forcedBoundingBox a given bounding box is taken as view space535 */536 void Construct(const VssRayContainer &sampleRays,537 AxisAlignedBox3 *forcedBoundingBox);538 539 638 /** Returns list of BSP leaves with pvs smaller than 540 639 a certain threshold. … … 701 800 float &pBack) const; 702 801 802 void PrepareConstruction(const VssRayContainer &sampleRays, 803 AxisAlignedBox3 *forcedBoundingBox); 804 703 805 /** Evaluates candidate for splitting. 704 806 */ … … 713 815 float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane, 714 816 const VspTraversalData &data) const; 715 716 /** Constructs tree using the split priority queue.717 */718 void Construct(RayInfoContainer *rays);719 817 720 818 /** Collects view cells in the subtree under root. … … 747 845 void EvaluateLeafStats(const VspTraversalData &data); 748 846 749 /** Subdivides node with respect to the traversal data. 750 @param tStack current traversal stack 751 @param tData traversal data also holding node to be subdivided 847 /** Subdivides node using a best split priority queue. 848 @param tQueue the best split priority queue 849 @param splitCandidate the candidate for the next split 850 @param globalCriteriaMet if the global termination criteria were already met 752 851 @returns new root of the subtree 753 852 */ 754 853 VspNode *Subdivide(SplitQueue &tQueue, 755 VspSplitCandidate &splitCandidate); 756 854 VspSplitCandidate &splitCandidate, 855 const bool globalCriteriaMet); 856 857 /** Adds stats to subdivision log file. 858 */ 859 void AddSubdivisionStats(const int viewCells, 860 const float renderCostDecr, 861 const float splitCandidateCost, 862 const float totalRenderCost, 863 const float avgRenderCost); 757 864 758 865 /** Subdivides leaf. 759 @param leaf the leaf to be subdivided 760 761 @param polys the polygons to be split 762 @param frontPolys returns the polygons in front of the split plane 763 @param backPolys returns the polygons in the back of the split plane 866 867 @param tData data object holding, e.g., a pointer to the leaf 868 @param frontData returns the data (e.g., pointer to the leaf) in front of the split plane 869 @param backData returns the data (e.g., pointer to the leaf) in the back of the split plane 764 870 765 871 @param rays the polygons to be filtered 766 872 @param frontRays returns the polygons in front of the split plane 767 @param backRays returns the polygons in the back of the split plane 768 873 769 874 @returns the root of the subdivision 770 875 */ 771 772 876 VspInterior *SubdivideNode(const AxisAlignedPlane &splitPlane, 773 877 VspTraversalData &tData, … … 884 988 885 989 /// box around the whole view domain 886 AxisAlignedBox3 mBo x;990 AxisAlignedBox3 mBoundingBox; 887 991 888 992 … … 973 1077 974 1078 975 class KdTree; 1079 /** View Space Partitioning tree. 1080 */ 1081 class OspTree 1082 { 1083 friend class ViewCellsParseHandlers; 1084 friend class HierarchyManager; 1085 1086 public: 1087 1088 /** Additional data which is passed down the BSP tree during traversal. 1089 */ 1090 class OspTraversalData 1091 { 1092 public: 1093 /// the current node 1094 KdNode *mNode; 1095 /// current depth 1096 int mDepth; 1097 /// rays piercing this node 1098 RayInfoContainer *mRays; 1099 /// the probability that this node contains view point 1100 float mProbability; 1101 /// the bounding box of the node 1102 AxisAlignedBox3 mBoundingBox; 1103 /// pvs size 1104 int mPvs; 1105 /// how often this branch has missed the max-cost ratio 1106 int mMaxCostMisses; 1107 // current axis 1108 int mAxis; 1109 // current priority 1110 float mPriority; 1111 1112 1113 /** Returns average ray contribution. 1114 */ 1115 float GetAvgRayContribution() const 1116 { 1117 return (float)mPvs / ((float)mRays->size() + Limits::Small); 1118 } 1119 1120 1121 OspTraversalData(): 1122 mNode(NULL), 1123 mDepth(0), 1124 mRays(NULL), 1125 mPvs(0), 1126 mProbability(0.0), 1127 mMaxCostMisses(0), 1128 mPriority(0), 1129 mAxis(0) 1130 {} 1131 1132 OspTraversalData(KdNode *node, 1133 const int depth, 1134 RayInfoContainer *rays, 1135 const int pvs, 1136 const float p, 1137 const AxisAlignedBox3 &box): 1138 mNode(node), 1139 mDepth(depth), 1140 mRays(rays), 1141 mPvs(pvs), 1142 mProbability(p), 1143 mBoundingBox(box), 1144 mMaxCostMisses(0), 1145 mPriority(0), 1146 mAxis(0) 1147 {} 1148 1149 OspTraversalData(const int depth, 1150 RayInfoContainer *rays, 1151 const AxisAlignedBox3 &box): 1152 mNode(NULL), 1153 mDepth(depth), 1154 mRays(rays), 1155 mPvs(0), 1156 mProbability(0), 1157 mMaxCostMisses(0), 1158 mAxis(0), 1159 mBoundingBox(box) 1160 {} 1161 1162 /** Returns cost of the traversal data. 1163 */ 1164 float GetCost() const 1165 { 1166 //cout << mPriority << endl; 1167 return mPriority; 1168 } 1169 1170 // deletes contents and sets them to NULL 1171 void Clear() 1172 { 1173 DEL_PTR(mRays); 1174 } 1175 1176 friend bool operator<(const OspTraversalData &a, const OspTraversalData &b) 1177 { 1178 return a.GetCost() < b.GetCost(); 1179 } 1180 }; 1181 1182 /** Candidate for a view space split. 1183 */ 1184 class OspSplitCandidate: public SplitCandidate 1185 { 1186 public: 1187 /// parent data 1188 OspTraversalData mParentData; 1189 1190 OspSplitCandidate() 1191 {}; 1192 1193 int Type() const { return VIEW_SPACE; } 1194 1195 OspSplitCandidate(const AxisAlignedPlane &plane, const OspTraversalData &tData): 1196 SplitCandidate(plane), mParentData(tData) 1197 {} 1198 }; 1199 1200 /** Struct for traversing line segment. 1201 */ 1202 struct LineTraversalData 1203 { 1204 KdNode *mNode; 1205 Vector3 mExitPoint; 1206 1207 float mMaxT; 1208 1209 LineTraversalData () {} 1210 LineTraversalData (KdNode *n, const Vector3 &p, const float maxt): 1211 mNode(n), mExitPoint(p), mMaxT(maxt) {} 1212 }; 1213 1214 //typedef std::priority_queue<VspTraversalData> VspOspTraversalQueue; 1215 1216 /** Default constructor creating an empty tree. 1217 */ 1218 OspTree(); 1219 1220 /** Default destructor. 1221 */ 1222 ~OspTree(); 1223 1224 /** Returns BSP Tree statistics. 1225 */ 1226 const KdTreeStatistics &GetStatistics() const; 1227 1228 /** Returns bounding box of the specified node. 1229 */ 1230 AxisAlignedBox3 GetBoundingBox(KdNode *node) const; 1231 1232 /** Returns list of BSP leaves with pvs smaller than 1233 a certain threshold. 1234 @param onlyUnmailed if only the unmailed leaves should be considered 1235 @param maxPvs the maximal pvs of a leaf to be added (-1 means unlimited) 1236 */ 1237 void CollectLeaves(vector<VspLeaf *> &leaves, 1238 const bool onlyUnmailed = false, 1239 const int maxPvs = -1) const; 1240 1241 /** Returns box which bounds the whole tree. 1242 */ 1243 AxisAlignedBox3 GetBoundingBox()const; 1244 1245 /** Returns root of the view space partitioning tree. 1246 */ 1247 KdNode *GetRoot() const; 1248 1249 /** Collects the leaf view cells of the tree 1250 @param viewCells returns the view cells 1251 */ 1252 void CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const; 1253 1254 /** A ray is cast possible intersecting the tree. 1255 @param the ray that is cast. 1256 @returns the number of intersections with objects stored in the tree. 1257 */ 1258 int CastRay(Ray &ray); 1259 1260 /** finds neighbouring leaves of this tree node. 1261 */ 1262 int FindNeighbors(KdLeaf *n, 1263 vector<VspLeaf *> &neighbors, 1264 const bool onlyUnmailed) const; 1265 1266 /** Returns random leaf of BSP tree. 1267 @param halfspace defines the halfspace from which the leaf is taken. 1268 */ 1269 KdLeaf *GetRandomLeaf(const Plane3 &halfspace); 1270 1271 /** Returns random leaf of BSP tree. 1272 @param onlyUnmailed if only unmailed leaves should be returned. 1273 */ 1274 KdLeaf *GetRandomLeaf(const bool onlyUnmailed = false); 1275 1276 /** Returns epsilon of this tree. 1277 */ 1278 float GetEpsilon() const; 1279 1280 /** Casts line segment into the tree. 1281 @param origin the origin of the line segment 1282 @param termination the end point of the line segment 1283 @returns view cells intersecting the line segment. 1284 */ 1285 int CastLineSegment(const Vector3 &origin, 1286 const Vector3 &termination, 1287 ViewCellContainer &viewcells); 1288 1289 /** Sets pointer to view cells manager. 1290 */ 1291 void SetViewCellsManager(ViewCellsManager *vcm); 1292 1293 /** Writes tree to output stream 1294 */ 1295 #if ZIPPED_VIEWCELLS 1296 bool Export(ogzstream &stream); 1297 #else 1298 bool Export(ofstream &stream); 1299 #endif 1300 1301 /** Collects rays stored in the leaves. 1302 */ 1303 void CollectRays(VssRayContainer &rays); 1304 1305 /** Intersects box with the tree and returns the number of intersected boxes. 1306 @returns number of view cells found 1307 */ 1308 int ComputeBoxIntersections(const AxisAlignedBox3 &box, 1309 ViewCellContainer &viewCells) const; 1310 1311 1312 /// pointer to the hierarchy of view cells 1313 ViewCellsTree *mViewCellsTree; 1314 1315 1316 protected: 1317 1318 // -------------------------------------------------------------- 1319 // For sorting objects 1320 // -------------------------------------------------------------- 1321 struct SortableEntry 1322 { 1323 enum EType 1324 { 1325 ERayMin, 1326 ERayMax 1327 }; 1328 1329 int type; 1330 float value; 1331 VssRay *ray; 1332 1333 SortableEntry() {} 1334 SortableEntry(const int t, const float v, VssRay *r):type(t), 1335 value(v), ray(r) 1336 { 1337 } 1338 1339 friend bool operator<(const SortableEntry &a, const SortableEntry &b) 1340 { 1341 return a.value < b.value; 1342 } 1343 }; 1344 1345 /** faster evaluation of split plane cost for kd axis aligned cells. 1346 */ 1347 float EvalSplitCost(const OspTraversalData &data, 1348 const AxisAlignedBox3 &box, 1349 const int axis, 1350 const float &position, 1351 float &pFront, 1352 float &pBack) const; 1353 1354 /** Evaluates candidate for splitting. 1355 */ 1356 void EvalSplitCandidate(OspTraversalData &tData, OspSplitCandidate &splitData); 1357 1358 /** Computes priority of the traversal data and stores it in tData. 1359 */ 1360 void EvalPriority(OspTraversalData &tData) const; 1361 1362 /** Evaluates render cost decrease of next split. 1363 */ 1364 float EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane, 1365 const OspTraversalData &data) const; 1366 1367 /** Collects view cells in the subtree under root. 1368 */ 1369 void CollectViewCells(KdNode *root, 1370 bool onlyValid, 1371 ViewCellContainer &viewCells, 1372 bool onlyUnmailed = false) const; 1373 1374 /** Evaluates tree stats in the BSP tree leafs. 1375 */ 1376 void EvaluateLeafStats(const OspTraversalData &data); 1377 1378 /** Subdivides node using a best split priority queue. 1379 @param tQueue the best split priority queue 1380 @param splitCandidate the candidate for the next split 1381 @param globalCriteriaMet if the global termination criteria were already met 1382 @returns new root of the subtree 1383 */ 1384 KdNode *Subdivide(SplitQueue &tQueue, 1385 OspSplitCandidate &splitCandidate, 1386 const bool globalCriteriaMet); 1387 1388 /** Subdivides leaf. 1389 @param leaf the leaf to be subdivided 1390 1391 @param polys the polygons to be split 1392 @param frontPolys returns the polygons in front of the split plane 1393 @param backPolys returns the polygons in the back of the split plane 1394 1395 @param rays the polygons to be filtered 1396 @param frontRays returns the polygons in front of the split plane 1397 @param backRays returns the polygons in the back of the split plane 1398 1399 @returns the root of the subdivision 1400 */ 1401 void SplitObjects(const AxisAlignedPlane & splitPlane, 1402 const ObjectContainer &objects, 1403 ObjectContainer &back, 1404 ObjectContainer &front); 1405 1406 KdInterior *SubdivideNode(KdLeaf *leaf, 1407 const AxisAlignedPlane &splitPlane, 1408 const AxisAlignedBox3 &box, 1409 AxisAlignedBox3 &backBBox, 1410 AxisAlignedBox3 &frontBBox); 1411 1412 /*KdInterior *SubdivideNode(const AxisAlignedPlane &splitPlane, 1413 OspTraversalData &tData, 1414 OspTraversalData &frontData, 1415 OspTraversalData &backData);*/ 1416 1417 /** Selects an axis aligned for the next split. 1418 @returns cost for this split 1419 */ 1420 float SelectPlane(const OspTraversalData &tData, 1421 AxisAlignedPlane &plane, 1422 float &pFront, 1423 float &pBack); 1424 1425 /** Sorts split candidates for surface area heuristics for axis aligned splits. 1426 @param polys the input for choosing split candidates 1427 @param axis the current split axis 1428 @param splitCandidates returns sorted list of split candidates 1429 */ 1430 void SortSplitCandidates(const RayInfoContainer &rays, 1431 const int axis, 1432 float minBand, 1433 float maxBand); 1434 1435 /** Computes best cost for axis aligned planes. 1436 */ 1437 float BestCostRatioHeuristics(const RayInfoContainer &rays, 1438 const AxisAlignedBox3 &box, 1439 const int pvsSize, 1440 const int axis, 1441 float &position); 1442 1443 /** Subdivides the rays into front and back rays according to the split plane. 1444 1445 @param plane the split plane 1446 @param rays contains the rays to be split. The rays are 1447 distributed into front and back rays. 1448 @param frontRays returns rays on the front side of the plane 1449 @param backRays returns rays on the back side of the plane 1450 1451 @returns the number of splits 1452 */ 1453 int SplitRays(const AxisAlignedPlane &plane, 1454 RayInfoContainer &rays, 1455 RayInfoContainer &frontRays, 1456 RayInfoContainer &backRays) const; 1457 1458 /** Adds the object to the pvs of the front and back leaf with a given classification. 1459 1460 @param obj the object to be added 1461 @param cf the ray classification regarding the split plane 1462 @param frontPvs returns the PVS of the front partition 1463 @param backPvs returns the PVS of the back partition 1464 1465 */ 1466 void AddObjToPvs(Intersectable *obj, 1467 const int cf, 1468 float &frontPvs, 1469 float &backPvs, 1470 float &totalPvs) const; 1471 1472 /** Computes PVS size induced by the rays. 1473 */ 1474 int ComputePvsSize(const RayInfoContainer &rays) const; 1475 1476 /** Returns true if tree can be terminated. 1477 */ 1478 inline bool LocalTerminationCriteriaMet(const OspTraversalData &data) const; 1479 1480 /** Returns true if global tree can be terminated. 1481 */ 1482 inline bool GlobalTerminationCriteriaMet(const OspTraversalData &data) const; 1483 1484 /** Adds ray sample contributions to the PVS. 1485 @param sampleContributions the number contributions of the samples 1486 @param contributingSampels the number of contributing rays 1487 1488 */ 1489 void AddToPvs(VspLeaf *leaf, 1490 const RayInfoContainer &rays, 1491 float &sampleContributions, 1492 int &contributingSamples); 1493 1494 /** Propagates valid flag up the tree. 1495 */ 1496 void PropagateUpValidity(KdNode *node); 1497 1498 /** Writes the node to disk 1499 @note: should be implemented as visitor. 1500 */ 1501 #if ZIPPED_VIEWCELLS 1502 void ExportNode(KdNode *node, ogzstream &stream); 1503 #else 1504 void ExportNode(KdNode *node, ofstream &stream); 1505 #endif 1506 1507 /** Returns estimated memory usage of tree. 1508 */ 1509 float GetMemUsage() const; 1510 1511 1512 protected: 1513 1514 ViewCellsManager *mViewCellsManager; 1515 vector<SortableEntry> *mSplitCandidates; 1516 1517 /// Pointer to the root of the tree 1518 KdNode *mRoot; 1519 1520 OspTreeStatistics mOspStats; 1521 1522 /// box around the whole view domain 1523 AxisAlignedBox3 mBoundingBox; 1524 1525 1526 //-- local termination 1527 1528 /// minimal number of rays before subdivision termination 1529 int mTermMinRays; 1530 /// maximal possible depth 1531 int mTermMaxDepth; 1532 /// mininum probability 1533 float mTermMinProbability; 1534 /// mininum PVS 1535 int mTermMinPvs; 1536 /// maximal contribution per ray 1537 float mTermMaxRayContribution; 1538 /// maximal acceptable cost ratio 1539 float mTermMaxCostRatio; 1540 /// tolerance value indicating how often the max cost ratio can be failed 1541 int mTermMissTolerance; 1542 1543 1544 //-- global criteria 1545 float mTermMinGlobalCostRatio; 1546 int mTermGlobalCostMissTolerance; 1547 int mGlobalCostMisses; 1548 1549 /// maximal number of view cells 1550 int mMaxViewCells; 1551 /// maximal tree memory 1552 float mMaxMemory; 1553 /// the tree is out of memory 1554 bool mOutOfMemory; 1555 1556 1557 1558 //-- split heuristics based parameters 1559 1560 bool mUseCostHeuristics; 1561 /// balancing factor for PVS criterium 1562 float mCtDivCi; 1563 /// if only driving axis should be used for split 1564 bool mOnlyDrivingAxis; 1565 /// if random split axis should be used 1566 bool mUseRandomAxis; 1567 /// if vsp bsp tree should simulate octree 1568 bool mCirculatingAxis; 1569 /// minimal relative position where the split axis can be placed 1570 float mMinBand; 1571 /// maximal relative position where the split axis can be placed 1572 float mMaxBand; 1573 1574 1575 /// current time stamp (used for keeping split history) 1576 int mTimeStamp; 1577 // if rays should be stored in leaves 1578 bool mStoreRays; 1579 1580 /// epsilon for geometric comparisons 1581 float mEpsilon; 1582 1583 /// if we should use breath first priority for the splits 1584 int mNodePriorityQueueType; 1585 1586 1587 /// subdivision stats output file 1588 ofstream mSubdivisionStats; 1589 /// keeps track of cost during subdivision 1590 float mTotalCost; 1591 /// keeps track of overall pvs size during subdivision 1592 int mTotalPvsSize; 1593 /// number of currenly generated view cells 1594 int mCreatedViewCells; 1595 1596 private: 1597 1598 /// Generates unique ids for PVS criterium 1599 static void GenerateUniqueIdsForPvs(); 1600 1601 //-- unique ids for PVS criterium 1602 static int sFrontId; 1603 static int sBackId; 1604 static int sFrontAndBackId; 1605 }; 1606 976 1607 977 1608 /** This class implements a structure holding two different hierarchies, … … 1011 1642 void Construct(const VssRayContainer &sampleRays, 1012 1643 const ObjectContainer &objects, 1013 AxisAlignedBox3 *forced BoundingBox);1644 AxisAlignedBox3 *forcedViewSpace); 1014 1645 1015 1646 public: 1016 1647 VspTree *mVspTree; 1017 KdTree *mKdTree;1648 OspTree *mOspTree; 1018 1649 1019 1650 protected: 1020 1651 1021 void Construct(RayInfoContainer *rays); 1022 void PrepareTraversal(); 1652 bool GlobalTerminationCriteriaMet(SplitCandidate *candidate) const; 1653 1654 void PrepareConstruction(const VssRayContainer &sampleRays, 1655 AxisAlignedBox3 *forcedViewSpace, 1656 RayInfoContainer &rays); 1657 1023 1658 bool FinishedConstruction(); 1024 1659 SplitCandidate *NextSplitCandidate(); -
GTP/trunk/Lib/Vis/Preprocessing/src/X3dExporter.cpp
r1006 r1020 211 211 tStack.push(pair<BspNode *, BspNodeGeometry *>(tree.GetRoot(), geom)); 212 212 213 if (maxPvs > 0)213 if (maxPvs) 214 214 mUseForcedMaterial = true; 215 215 … … 238 238 else 239 239 { 240 if (maxPvs > 0)240 if (maxPvs) 241 241 { 242 242 BspLeaf *leaf = dynamic_cast<BspLeaf *>(node); 243 243 244 244 mForcedMaterial.mDiffuseColor.b = 1.0f; 245 float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs;245 const float importance = (float)leaf->GetViewCell()->GetPvs().GetSize() / (float)maxPvs; 246 246 247 247 mForcedMaterial.mDiffuseColor.r = importance; -
GTP/trunk/Lib/Vis/Preprocessing/src/X3dParser.cpp
r1005 r1020 30 30 #include "ViewCellsManager.h" 31 31 #include "ResourceManager.h" 32 #include <assert.h> 32 33 33 34 namespace GtpVisibilityPreprocessor { … … 80 81 // StdInParseHandlers: Constructors and Destructor 81 82 // --------------------------------------------------------------------------- 82 X3dParseHandlers::X3dParseHandlers(SceneGraphNode *root, const bool loadPolygonsAsMeshes): 83 X3dParseHandlers::X3dParseHandlers(SceneGraphNode *root, 84 const bool loadPolygonsAsMeshes): 83 85 mElementCount(0) 84 86 , mAttrCount(0) … … 96 98 X3dParseHandlers::~X3dParseHandlers() 97 99 { 98 if (!mTransformations.empty()) 100 assert(mTransformations.empty()); 101 if (0 && !mTransformations.empty()) 99 102 cout << "error: transformation stack size: " << (int)mTransformations.size() << endl; 100 103 } … … 166 169 float angle; 167 170 168 if (sscanf(ptr, "%f %f %f ", &axis.x, &axis.y, &axis.z, &angle) == 4)171 if (sscanf(ptr, "%f %f %f %f", &axis.x, &axis.y, &axis.z, &angle) == 4) 169 172 { 170 173 rotm = new Matrix4x4(RotationAxisMatrix(axis, angle)); … … 224 227 if (mLoadPolygonsAsMeshes) 225 228 { 229 cout << "m"; 226 230 FaceContainer::const_iterator fit, fit_end = mCurrentMesh->mFaces.end(); 227 228 cout << "m";229 231 230 232 for (fit = mCurrentMesh->mFaces.begin(); fit != fit_end; ++ fit) 231 233 { 232 234 cout << "f"; 233 234 235 Face *face = *fit; 235 236 … … 240 241 241 242 int i = 0; 243 // dummy vertex indices container 242 244 VertexIndexContainer vcIndices; 243 245 … … 250 252 mesh->mVertices.push_back(mCurrentMesh->mVertices[index]); 251 253 252 // indices don't make much sense if mesh = face, but253 // we need them anyway ...254 // indices don't make much sense if mesh == face, 255 // but we need them anyway ... 254 256 vcIndices.push_back(i); 255 257 } … … 257 259 mesh->mFaces.push_back(new Face(vcIndices)); 258 260 259 // NOTE: should rather be written into trafo of mesh instance 261 // write transformations directly in mesh 262 // note: could be transformed in parent mesh, save some transformations 260 263 ApplyTransformations(mTransformations, mesh); 261 264 262 265 mesh->Preprocess(); 263 266 264 // make an instance of this mesh 265 MeshInstance *mi = new MeshInstance(mesh); 266 mCurrentNode->mGeometry.push_back(mi); 267 if (mesh->mFaces.empty()) 268 { 269 cout << "error: empy mesh" << endl; 270 } 271 else 272 { 273 // make an instance of this mesh 274 MeshInstance *mi = new MeshInstance(mesh); 275 mCurrentNode->mGeometry.push_back(mi); 276 277 if (mCurrentMaterial) 278 { 279 // HACK: add the material to the mesh directly if no material yet 280 if (!mCurrentMesh->mMaterial) 281 mCurrentMesh->mMaterial = mCurrentMaterial; 282 } 283 } 267 284 } 268 285 269 286 // this mesh is not needed, unless it is used as a definition 270 if (!mUsingMeshDefinition) 287 if (!mUsingMeshDefinition) 288 { 271 289 MeshManager::GetSingleton()->DestroyEntry(mCurrentMesh->GetId()); 290 } 272 291 } 273 292 else // default usage: create a mesh instance from the current mesh … … 275 294 MeshInstance *mi; 276 295 277 if (mCurrentMesh->mFaces.empty())278 cout << "warning: empy mesh" << endl;279 280 296 if (!mUsingMeshDefinition) 281 297 { 282 298 // make an instance of this mesh 283 299 mi = new MeshInstance(mCurrentMesh); 284 300 285 301 // this mesh is used only once => write transformations directly into it … … 289 305 { 290 306 // make an instance of this mesh 291 307 TransformedMeshInstance *tmi = new TransformedMeshInstance(mCurrentMesh); 292 308 293 309 // apply transformation on the instance of the mesh 294 310 ApplyTransformations(mTransformations, tmi); 295 296 311 mi = tmi; 297 312 } 298 313 299 314 if (mCurrentMaterial) 300 315 { 301 316 // HACK: add the material to the mesh directly if no material yet 302 if ( mCurrentMesh->mMaterial)317 if (!mCurrentMesh->mMaterial) 303 318 { 304 319 mCurrentMesh->mMaterial = mCurrentMaterial; … … 309 324 } 310 325 } 311 326 312 327 // create local mesh kd tree 313 328 mCurrentMesh->Preprocess(); 314 // add to scene graph 315 mCurrentNode->mGeometry.push_back(mi); 316 329 330 if (mCurrentMesh->mFaces.empty()) 331 { 332 cout << "warning: empy mesh!!" << endl; 333 delete mi; 334 } 335 else 336 { 337 // add to scene graph 338 mCurrentNode->mGeometry.push_back(mi); 339 } 340 317 341 // reset current mesh 318 342 mCurrentMesh = NULL; -
GTP/trunk/Lib/Vis/Preprocessing/src/X3dParserXerces.h
r1001 r1020 121 121 AttributeList& attributes); 122 122 123 /// applies transformation m to this mesh 123 /** applies transformation matrix m to this mesh. 124 */ 124 125 void ApplyTransformation(Mesh *mesh, const Matrix4x4 &m) const; 125 126 126 /// transforms mesh using the given transformations 127 /** transforms mesh using the given transformations. 128 */ 127 129 void ApplyTransformations(TrafoStack trafos, Mesh *mesh) const; 128 130 void ApplyTransformations(TrafoStack trafos, TransformedMeshInstance *mi) const;
Note: See TracChangeset
for help on using the changeset viewer.