[1237] | 1 | #include <stack>
|
---|
| 2 | #include <time.h>
|
---|
| 3 | #include <iomanip>
|
---|
| 4 |
|
---|
| 5 | #include "ViewCell.h"
|
---|
| 6 | #include "Plane3.h"
|
---|
| 7 | #include "HierarchyManager.h"
|
---|
| 8 | #include "Mesh.h"
|
---|
| 9 | #include "common.h"
|
---|
| 10 | #include "Environment.h"
|
---|
| 11 | #include "Polygon3.h"
|
---|
| 12 | #include "Ray.h"
|
---|
| 13 | #include "AxisAlignedBox3.h"
|
---|
| 14 | #include "Exporter.h"
|
---|
| 15 | #include "Plane3.h"
|
---|
| 16 | #include "ViewCellsManager.h"
|
---|
| 17 | #include "Beam.h"
|
---|
| 18 | #include "KdTree.h"
|
---|
[1315] | 19 | #include "IntersectableWrapper.h"
|
---|
[1237] | 20 | #include "VspTree.h"
|
---|
| 21 | #include "OspTree.h"
|
---|
[1259] | 22 | #include "BvHierarchy.h"
|
---|
[1237] | 23 |
|
---|
| 24 |
|
---|
| 25 | namespace GtpVisibilityPreprocessor {
|
---|
| 26 |
|
---|
| 27 |
|
---|
| 28 | #define USE_FIXEDPOINT_T 0
|
---|
| 29 |
|
---|
| 30 |
|
---|
| 31 | /*******************************************************************/
|
---|
| 32 | /* class HierarchyManager implementation */
|
---|
| 33 | /*******************************************************************/
|
---|
| 34 |
|
---|
| 35 |
|
---|
[1421] | 36 | HierarchyManager::HierarchyManager(const int objectSpaceSubdivisionType):
|
---|
[1308] | 37 | mObjectSpaceSubdivisionType(objectSpaceSubdivisionType),
|
---|
[1279] | 38 | mOspTree(NULL),
|
---|
| 39 | mBvHierarchy(NULL)
|
---|
[1237] | 40 | {
|
---|
[1308] | 41 | switch(mObjectSpaceSubdivisionType)
|
---|
[1279] | 42 | {
|
---|
| 43 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 44 | mOspTree = new OspTree();
|
---|
| 45 | mOspTree->mVspTree = mVspTree;
|
---|
[1379] | 46 | mOspTree->mHierarchyManager = this;
|
---|
[1279] | 47 | break;
|
---|
| 48 | case BV_BASED_OBJ_SUBDIV:
|
---|
| 49 | mBvHierarchy = new BvHierarchy();
|
---|
[1379] | 50 | mBvHierarchy->mHierarchyManager = this;
|
---|
[1279] | 51 | break;
|
---|
| 52 | default:
|
---|
| 53 | break;
|
---|
| 54 | }
|
---|
| 55 |
|
---|
[1379] | 56 | // hierarchy manager links view space partition and object space partition
|
---|
[1421] | 57 | mVspTree = new VspTree();
|
---|
[1379] | 58 | mVspTree->mHierarchyManager = this;
|
---|
| 59 |
|
---|
[1580] | 60 | mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
|
---|
[1288] | 61 | ParseEnvironment();
|
---|
[1237] | 62 | }
|
---|
| 63 |
|
---|
| 64 |
|
---|
[1421] | 65 | HierarchyManager::HierarchyManager(KdTree *kdTree):
|
---|
[1308] | 66 | mObjectSpaceSubdivisionType(KD_BASED_OBJ_SUBDIV),
|
---|
[1279] | 67 | mBvHierarchy(NULL)
|
---|
| 68 | {
|
---|
| 69 | mOspTree = new OspTree(*kdTree);
|
---|
| 70 | mOspTree->mVspTree = mVspTree;
|
---|
| 71 |
|
---|
[1421] | 72 | mVspTree = new VspTree();
|
---|
[1379] | 73 | mVspTree->mHierarchyManager = this;
|
---|
[1279] | 74 |
|
---|
[1580] | 75 | mViewSpaceSubdivisionType = KD_BASED_VIEWSPACE_SUBDIV;
|
---|
[1288] | 76 | ParseEnvironment();
|
---|
| 77 | }
|
---|
| 78 |
|
---|
| 79 |
|
---|
| 80 | void HierarchyManager::ParseEnvironment()
|
---|
| 81 | {
|
---|
| 82 | Environment::GetSingleton()->GetFloatValue(
|
---|
| 83 | "Hierarchy.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
|
---|
| 84 | Environment::GetSingleton()->GetIntValue(
|
---|
| 85 | "Hierarchy.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
|
---|
| 86 |
|
---|
[1370] | 87 | Environment::GetSingleton()->GetBoolValue(
|
---|
| 88 | "Hierarchy.Construction.startWithObjectSpace", mStartWithObjectSpace);
|
---|
| 89 |
|
---|
[1293] | 90 | Environment::GetSingleton()->GetIntValue(
|
---|
[1294] | 91 | "Hierarchy.Termination.maxLeaves", mTermMaxLeaves);
|
---|
| 92 |
|
---|
| 93 | Environment::GetSingleton()->GetIntValue(
|
---|
[1293] | 94 | "Hierarchy.Construction.type", mConstructionType);
|
---|
| 95 |
|
---|
[1311] | 96 | Environment::GetSingleton()->GetIntValue(
|
---|
| 97 | "Hierarchy.Construction.minDepthForOsp", mMinDepthForObjectSpaceSubdivion);
|
---|
[1370] | 98 |
|
---|
| 99 | Environment::GetSingleton()->GetIntValue(
|
---|
| 100 | "Hierarchy.Construction.minDepthForVsp", mMinDepthForViewSpaceSubdivion);
|
---|
[1311] | 101 |
|
---|
[1314] | 102 | Environment::GetSingleton()->GetBoolValue(
|
---|
| 103 | "Hierarchy.Construction.repairQueue", mRepairQueue);
|
---|
| 104 |
|
---|
[1449] | 105 | Environment::GetSingleton()->GetBoolValue(
|
---|
[1564] | 106 | "Hierarchy.Construction.useMultiLevel", mUseMultiLevelConstruction);
|
---|
[1449] | 107 |
|
---|
[1580] | 108 | Environment::GetSingleton()->GetIntValue(
|
---|
| 109 | "Hierarchy.Construction.levels", mNumMultiLevels);
|
---|
| 110 |
|
---|
[1640] | 111 | Environment::GetSingleton()->GetIntValue(
|
---|
| 112 | "Hierarchy.Construction.minStepsOfSameType", mMinStepsOfSameType);
|
---|
| 113 |
|
---|
[1684] | 114 | Environment::GetSingleton()->GetIntValue(
|
---|
| 115 | "Hierarchy.Construction.maxStepsOfSameType", mMaxStepsOfSameType);
|
---|
| 116 |
|
---|
[1624] | 117 | char subdivisionStatsLog[100];
|
---|
| 118 | Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats", subdivisionStatsLog);
|
---|
| 119 | mSubdivisionStats.open(subdivisionStatsLog);
|
---|
| 120 |
|
---|
[1633] | 121 | Environment::GetSingleton()->GetBoolValue(
|
---|
| 122 | "Hierarchy.Construction.recomputeSplitPlaneOnRepair", mRecomputeSplitPlaneOnRepair);
|
---|
[1624] | 123 |
|
---|
[1662] | 124 | Environment::GetSingleton()->GetBoolValue(
|
---|
| 125 | "Hierarchy.Construction.considerMemory", mConsiderMemory);
|
---|
| 126 |
|
---|
[1673] | 127 | Environment::GetSingleton()->GetBoolValue(
|
---|
| 128 | "Hierarchy.Construction.considerMemory2", mConsiderMemory2);
|
---|
| 129 |
|
---|
[1649] | 130 | Environment::GetSingleton()->GetFloatValue(
|
---|
| 131 | "Hierarchy.Termination.maxMemory", mTermMaxMemory);
|
---|
| 132 |
|
---|
[1684] | 133 | if (1 && mConsiderMemory2)
|
---|
| 134 | {
|
---|
| 135 | mMemoryConst = (float)(sizeof(VspLeaf *) + sizeof (VspViewCell *));
|
---|
| 136 | }
|
---|
| 137 | else
|
---|
| 138 | {
|
---|
| 139 | Environment::GetSingleton()->GetFloatValue(
|
---|
| 140 | "Hierarchy.Termination.memoryConst", mMemoryConst);
|
---|
| 141 | }
|
---|
[1666] | 142 |
|
---|
[1662] | 143 | // compare to bytes
|
---|
[1653] | 144 | mTermMaxMemory *= (1024.0f * 1024.0f);
|
---|
| 145 |
|
---|
[1640] | 146 | Debug << "******** Hierachy Manager Options ***********" << endl;
|
---|
[1294] | 147 | Debug << "max leaves: " << mTermMaxLeaves << endl;
|
---|
[1288] | 148 | Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
|
---|
| 149 | Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
|
---|
[1314] | 150 | Debug << "min depth for object space subdivision: " << mMinDepthForObjectSpaceSubdivion << endl;
|
---|
| 151 | Debug << "repair queue: " << mRepairQueue << endl;
|
---|
[1580] | 152 | Debug << "number of multilevels: " << mNumMultiLevels << endl;
|
---|
[1633] | 153 | Debug << "recompute split plane on repair: " << mRecomputeSplitPlaneOnRepair << endl;
|
---|
[1640] | 154 | Debug << "minimal number of steps from same type: " << mMinStepsOfSameType << endl;
|
---|
[1649] | 155 | Debug << "maximal allowed memory: " << mTermMaxMemory << endl;
|
---|
[1673] | 156 | Debug << "consider memory: " << mConsiderMemory << endl;
|
---|
| 157 | Debug << "consider memory2: " << mConsiderMemory << endl;
|
---|
[1666] | 158 | Debug << "mem const: " << mMemoryConst << endl;
|
---|
[1684] | 159 | Debug << "min steps of same kind: " << mMinStepsOfSameType << endl;
|
---|
| 160 | Debug << "max steps of same kind: " << mMaxStepsOfSameType << endl;
|
---|
[1632] | 161 |
|
---|
| 162 | switch (mConstructionType)
|
---|
| 163 | {
|
---|
| 164 | case 0:
|
---|
| 165 | Debug << "construction type: sequential" << endl;
|
---|
| 166 | break;
|
---|
| 167 | case 1:
|
---|
| 168 | Debug << "construction type: interleaved" << endl;
|
---|
| 169 | break;
|
---|
| 170 | case 2:
|
---|
| 171 | Debug << "construction type: gradient" << endl;
|
---|
| 172 | break;
|
---|
| 173 | case 3:
|
---|
| 174 | Debug << "construction type: multilevel" << endl;
|
---|
| 175 | break;
|
---|
| 176 | default:
|
---|
| 177 | Debug << "construction type " << mConstructionType << " unknown" << endl;
|
---|
| 178 | break;
|
---|
| 179 | }
|
---|
| 180 |
|
---|
[1625] | 181 | //Debug << "min render cost " << mMinRenderCostDecrease << endl;
|
---|
[1449] | 182 | Debug << endl;
|
---|
[1279] | 183 | }
|
---|
| 184 |
|
---|
| 185 |
|
---|
| 186 | HierarchyManager::~HierarchyManager()
|
---|
| 187 | {
|
---|
| 188 | DEL_PTR(mOspTree);
|
---|
[1421] | 189 | DEL_PTR(mVspTree);
|
---|
[1279] | 190 | DEL_PTR(mBvHierarchy);
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 |
|
---|
[1370] | 194 | int HierarchyManager::GetObjectSpaceSubdivisionType() const
|
---|
| 195 | {
|
---|
| 196 | return mObjectSpaceSubdivisionType;
|
---|
| 197 | }
|
---|
| 198 |
|
---|
| 199 |
|
---|
| 200 | int HierarchyManager::GetViewSpaceSubdivisionType() const
|
---|
| 201 | {
|
---|
| 202 | return mViewSpaceSubdivisionType;
|
---|
| 203 | }
|
---|
| 204 |
|
---|
| 205 |
|
---|
[1279] | 206 | void HierarchyManager::SetViewCellsManager(ViewCellsManager *vcm)
|
---|
| 207 | {
|
---|
| 208 | mVspTree->SetViewCellsManager(vcm);
|
---|
| 209 |
|
---|
| 210 | if (mOspTree)
|
---|
[1576] | 211 | {
|
---|
[1279] | 212 | mOspTree->SetViewCellsManager(vcm);
|
---|
[1576] | 213 | }
|
---|
[1416] | 214 | else if (mBvHierarchy)
|
---|
[1576] | 215 | {
|
---|
[1279] | 216 | mBvHierarchy->SetViewCellsManager(vcm);
|
---|
[1576] | 217 | }
|
---|
[1279] | 218 | }
|
---|
| 219 |
|
---|
| 220 |
|
---|
| 221 | void HierarchyManager::SetViewCellsTree(ViewCellsTree *vcTree)
|
---|
| 222 | {
|
---|
| 223 | mVspTree->SetViewCellsTree(vcTree);
|
---|
| 224 | }
|
---|
| 225 |
|
---|
| 226 |
|
---|
[1379] | 227 | VspTree *HierarchyManager::GetVspTree()
|
---|
| 228 | {
|
---|
| 229 | return mVspTree;
|
---|
| 230 | }
|
---|
| 231 |
|
---|
[1563] | 232 | /*
|
---|
[1379] | 233 | AxisAlignedBox3 HierarchyManager::GetViewSpaceBox() const
|
---|
| 234 | {
|
---|
| 235 | return mVspTree->mBoundingBox;
|
---|
[1563] | 236 | }*/
|
---|
[1379] | 237 |
|
---|
| 238 |
|
---|
[1416] | 239 | AxisAlignedBox3 HierarchyManager::GetObjectSpaceBox() const
|
---|
| 240 | {
|
---|
| 241 | switch (mObjectSpaceSubdivisionType)
|
---|
| 242 | {
|
---|
| 243 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 244 | return mOspTree->mBoundingBox;
|
---|
| 245 | case BV_BASED_OBJ_SUBDIV:
|
---|
| 246 | return mBvHierarchy->mBoundingBox;
|
---|
| 247 | default:
|
---|
[1576] | 248 | // hack: empty box
|
---|
[1416] | 249 | return AxisAlignedBox3();
|
---|
| 250 | }
|
---|
| 251 | }
|
---|
| 252 |
|
---|
| 253 |
|
---|
[1625] | 254 | SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate(SplitQueue &splitQueue)
|
---|
[1237] | 255 | {
|
---|
[1625] | 256 | SubdivisionCandidate *splitCandidate = splitQueue.Top();
|
---|
| 257 | splitQueue.Pop();
|
---|
[1237] | 258 |
|
---|
| 259 | return splitCandidate;
|
---|
| 260 | }
|
---|
| 261 |
|
---|
| 262 |
|
---|
[1624] | 263 | void HierarchyManager::EvalSubdivisionStats()
|
---|
[1237] | 264 | {
|
---|
[1649] | 265 | // question: should I also add the mem usage of the hierarchies?
|
---|
| 266 | const float objectSpaceMem = 0;//GetObjectSpaceMemUsage();
|
---|
| 267 | const float viewSpaceMem = 0;//mVspTree->GetMemUsage();
|
---|
[1640] | 268 |
|
---|
| 269 | // calculate cost in MB
|
---|
[1676] | 270 | const float memoryCost = mHierarchyStats.mMemory / float(1024 * 1024)
|
---|
[1640] | 271 | + objectSpaceMem + viewSpaceMem;
|
---|
| 272 |
|
---|
[1580] | 273 | //cout << "pvs entries " << mHierarchyStats.pvsEntries << endl;
|
---|
[1576] | 274 | AddSubdivisionStats(mHierarchyStats.Leaves(),
|
---|
[1624] | 275 | mHierarchyStats.mRenderCostDecrease,
|
---|
| 276 | mHierarchyStats.mTotalCost,
|
---|
[1625] | 277 | mHierarchyStats.mPvsEntries,
|
---|
[1640] | 278 | memoryCost,
|
---|
[1654] | 279 | 1.0f / (mHierarchyStats.mTotalCost * memoryCost),
|
---|
| 280 | (float)mVspTree->mVspStats.Leaves() / (float)GetObjectSpaceSubdivisionLeaves()
|
---|
[1576] | 281 | );
|
---|
[1237] | 282 | }
|
---|
| 283 |
|
---|
| 284 |
|
---|
| 285 | void HierarchyManager::AddSubdivisionStats(const int splits,
|
---|
| 286 | const float renderCostDecr,
|
---|
[1576] | 287 | const float totalRenderCost,
|
---|
[1625] | 288 | const int pvsEntries,
|
---|
[1640] | 289 | const float memory,
|
---|
[1654] | 290 | const float renderCostPerStorage,
|
---|
| 291 | const float vspOspRatio)
|
---|
[1237] | 292 | {
|
---|
[1308] | 293 | mSubdivisionStats
|
---|
[1237] | 294 | << "#Splits\n" << splits << endl
|
---|
| 295 | << "#RenderCostDecrease\n" << renderCostDecr << endl
|
---|
[1577] | 296 | << "#TotalEntriesInPvs\n" << pvsEntries << endl
|
---|
[1625] | 297 | << "#TotalRenderCost\n" << totalRenderCost << endl
|
---|
| 298 | << "#Memory\n" << memory << endl
|
---|
[1660] | 299 | << "#FpsPerMb\n" << renderCostPerStorage << endl
|
---|
[1654] | 300 | << "#VspOspRatio\n" << vspOspRatio << endl;
|
---|
[1237] | 301 | }
|
---|
| 302 |
|
---|
| 303 |
|
---|
| 304 | bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
|
---|
| 305 | {
|
---|
[1421] | 306 | const bool terminationCriteriaMet =
|
---|
| 307 | (0
|
---|
[1294] | 308 | || (mHierarchyStats.Leaves() >= mTermMaxLeaves)
|
---|
[1649] | 309 | || (mHierarchyStats.mMemory >= mTermMaxMemory)
|
---|
| 310 | || candidate->GlobalTerminationCriteriaMet()
|
---|
| 311 | //|| (mHierarchyStats.mRenderCostDecrease < mMinRenderCostDecrease)
|
---|
[1633] | 312 | //|| (mHierarchyStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
|
---|
[1288] | 313 | );
|
---|
[1421] | 314 |
|
---|
[1653] | 315 | #if _DEBUG
|
---|
[1610] | 316 | if (terminationCriteriaMet)
|
---|
[1421] | 317 | {
|
---|
| 318 | Debug << "hierarchy global termination criteria met:" << endl;
|
---|
| 319 | Debug << "leaves: " << mHierarchyStats.Leaves() << " " << mTermMaxLeaves << endl;
|
---|
[1449] | 320 | Debug << "cost misses: " << mHierarchyStats.mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
|
---|
[1649] | 321 | Debug << "memory: " << mHierarchyStats.mMemory << " " << mTermMaxMemory << endl;
|
---|
[1421] | 322 | }
|
---|
[1653] | 323 | #endif
|
---|
[1610] | 324 |
|
---|
[1421] | 325 | return terminationCriteriaMet;
|
---|
[1237] | 326 | }
|
---|
| 327 |
|
---|
| 328 |
|
---|
| 329 | void HierarchyManager::Construct(const VssRayContainer &sampleRays,
|
---|
[1311] | 330 | const ObjectContainer &objects,
|
---|
| 331 | AxisAlignedBox3 *forcedViewSpace)
|
---|
[1237] | 332 | {
|
---|
[1679] | 333 | mTimeStamp = 1;
|
---|
| 334 |
|
---|
[1627] | 335 | switch (mConstructionType)
|
---|
[1449] | 336 | {
|
---|
[1627] | 337 | case MULTILEVEL:
|
---|
[1449] | 338 | ConstructMultiLevel(sampleRays, objects, forcedViewSpace);
|
---|
[1627] | 339 | break;
|
---|
| 340 | case INTERLEAVED:
|
---|
| 341 | case SEQUENTIAL:
|
---|
[1624] | 342 | ConstructInterleaved(sampleRays, objects, forcedViewSpace);
|
---|
[1627] | 343 | break;
|
---|
| 344 | case GRADIENT:
|
---|
| 345 | ConstructInterleavedWithGradient(sampleRays, objects, forcedViewSpace);
|
---|
| 346 | break;
|
---|
| 347 | default:
|
---|
| 348 | break;
|
---|
[1624] | 349 | }
|
---|
[1642] | 350 |
|
---|
| 351 | // hack: should be different parameter name
|
---|
| 352 | if (mUseMultiLevelConstruction)
|
---|
| 353 | {
|
---|
| 354 | cout << "starting optimizing multilevel ... " << endl;
|
---|
| 355 | // try to optimize on the above hierarchy
|
---|
| 356 | OptimizeMultiLevel(sampleRays, objects, forcedViewSpace);
|
---|
| 357 |
|
---|
| 358 | cout << "finished" << endl;
|
---|
| 359 | }
|
---|
[1624] | 360 | }
|
---|
| 361 |
|
---|
| 362 |
|
---|
[1686] | 363 | void HierarchyManager::ConstructInterleavedWithGradient(const VssRayContainer &sampleRays,
|
---|
[1626] | 364 | const ObjectContainer &objects,
|
---|
| 365 | AxisAlignedBox3 *forcedViewSpace)
|
---|
[1624] | 366 | {
|
---|
| 367 | mHierarchyStats.Reset();
|
---|
| 368 | mHierarchyStats.Start();
|
---|
[1625] | 369 |
|
---|
[1624] | 370 | mHierarchyStats.mNodes = 2;
|
---|
[1640] | 371 |
|
---|
| 372 | // create first nodes
|
---|
| 373 | mVspTree->Initialise(sampleRays, forcedViewSpace);
|
---|
| 374 | InitialiseObjectSpaceSubdivision(objects);
|
---|
| 375 |
|
---|
| 376 | // hack: assume that object space can be seen from view space
|
---|
[1677] | 377 | mHierarchyStats.mTotalCost = mInitialRenderCost = (float)objects.size();
|
---|
[1667] | 378 | // only one entry for start
|
---|
[1640] | 379 | mHierarchyStats.mPvsEntries = 1;
|
---|
[1667] | 380 | mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
|
---|
[1640] | 381 |
|
---|
| 382 | EvalSubdivisionStats();
|
---|
[1624] | 383 | Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
|
---|
| 384 |
|
---|
| 385 | const long startTime = GetTime();
|
---|
| 386 | cout << "Constructing view space / object space tree ... \n";
|
---|
| 387 |
|
---|
[1633] | 388 | SplitQueue objectSpaceQueue;
|
---|
| 389 | SplitQueue viewSpaceQueue;
|
---|
| 390 |
|
---|
[1696] | 391 | int vspSteps = 0, ospSteps = 0;
|
---|
[1684] | 392 |
|
---|
[1624] | 393 | // use sah for evaluating osp tree construction
|
---|
| 394 | // in the first iteration of the subdivision
|
---|
| 395 | mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
|
---|
| 396 | mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
|
---|
[1662] | 397 | mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
|
---|
[1624] | 398 |
|
---|
[1632] | 399 | // number of initial splits
|
---|
[1640] | 400 | const int minSteps = mMinStepsOfSameType;
|
---|
[1684] | 401 | const int maxSteps = mMaxStepsOfSameType;
|
---|
[1625] | 402 |
|
---|
[1676] | 403 | SubdivisionCandidate *osc = PrepareObjectSpaceSubdivision(sampleRays, objects);
|
---|
[1633] | 404 | objectSpaceQueue.Push(osc);
|
---|
| 405 |
|
---|
[1640] | 406 |
|
---|
[1633] | 407 | /////////////////////////
|
---|
| 408 | // calulcate initial object space splits
|
---|
| 409 |
|
---|
[1684] | 410 | SubdivisionCandidateContainer dirtyList;
|
---|
[1633] | 411 |
|
---|
| 412 | // subdivide object space first
|
---|
| 413 | // for first round, use sah splits. Once view space partition
|
---|
| 414 | // has started, use render cost heuristics instead
|
---|
[1684] | 415 | ospSteps = RunConstruction(objectSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
|
---|
[1640] | 416 | cout << "\n" << ospSteps << " object space partition steps taken" << endl;
|
---|
[1633] | 417 |
|
---|
[1640] | 418 | // create view space
|
---|
[1667] | 419 | SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
|
---|
[1684] | 420 | viewSpaceQueue.Push(vsc);
|
---|
[1633] | 421 |
|
---|
[1684] | 422 | dirtyList.clear();
|
---|
| 423 |
|
---|
[1642] | 424 | // view space subdivision started
|
---|
[1633] | 425 | mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
|
---|
| 426 |
|
---|
[1684] | 427 | if (1)
|
---|
| 428 | {
|
---|
| 429 | // rather also start with 100 view space splits to avoid initial bias.
|
---|
| 430 | vspSteps = RunConstruction(viewSpaceQueue, dirtyList, NULL, minSteps, maxSteps);
|
---|
| 431 | cout << "\n" << vspSteps << " view space partition steps taken" << endl;
|
---|
| 432 |
|
---|
| 433 | /// Repair split queue
|
---|
| 434 | cout << "repairing queue ... " << endl;
|
---|
| 435 | RepairQueue(dirtyList, objectSpaceQueue, true);
|
---|
| 436 | cout << "repaired " << (int)dirtyList.size() << " candidates" << endl;
|
---|
[1633] | 437 |
|
---|
[1684] | 438 | dirtyList.clear();
|
---|
| 439 | }
|
---|
| 440 | else
|
---|
| 441 | {
|
---|
| 442 | // the priorities were calculated for driving sah.
|
---|
| 443 | // => recalculate "real" priorities taking visibility into
|
---|
| 444 | // account so we can compare to view space splits
|
---|
| 445 | ResetQueue(objectSpaceQueue, false);
|
---|
| 446 | }
|
---|
| 447 |
|
---|
[1624] | 448 | // This method subdivides view space / object space
|
---|
| 449 | // in order to converge to some optimal cost for this partition
|
---|
| 450 | // start with object space partiton
|
---|
| 451 | // then optimizate view space partition for the current osp
|
---|
| 452 | // and vice versa until iteration depth is reached.
|
---|
[1696] | 453 |
|
---|
[1684] | 454 | bool lastSplitWasOsp = true;
|
---|
| 455 |
|
---|
[1633] | 456 | while (!(viewSpaceQueue.Empty() && objectSpaceQueue.Empty()))
|
---|
[1624] | 457 | {
|
---|
[1662] | 458 | // decide upon next split type
|
---|
[1701] | 459 | const float vspPriority = viewSpaceQueue.Top() ? viewSpaceQueue.Top()->GetPriority() : -1e20f;
|
---|
| 460 | const float ospPriority = objectSpaceQueue.Top() ? objectSpaceQueue.Top()->GetPriority() : -1e20f;
|
---|
[1662] | 461 |
|
---|
[1640] | 462 | cout << "new decicion, vsp: " << vspPriority << ", osp: " << ospPriority << endl;
|
---|
| 463 |
|
---|
[1633] | 464 | // should view or object space be subdivided further?
|
---|
[1684] | 465 | if (ospPriority >= vspPriority)
|
---|
| 466 | //if (!lastSplitWasOsp)
|
---|
[1633] | 467 | {
|
---|
[1679] | 468 | lastSplitWasOsp = true;
|
---|
[1673] | 469 | cout << "osp" << endl;
|
---|
[1684] | 470 |
|
---|
[1633] | 471 | // dirtied view space candidates
|
---|
| 472 | SubdivisionCandidateContainer dirtyVspList;
|
---|
[1624] | 473 |
|
---|
[1633] | 474 | // subdivide object space first
|
---|
| 475 | // for first round, use sah splits. Once view space partition
|
---|
| 476 | // has started, use render cost heuristics instead
|
---|
[1684] | 477 | const int ospSteps =
|
---|
| 478 | RunConstruction(objectSpaceQueue, dirtyVspList, viewSpaceQueue.Top(), minSteps, maxSteps);
|
---|
[1624] | 479 |
|
---|
[1640] | 480 | cout << "\n" << ospSteps << " object space partition steps taken" << endl;
|
---|
[1684] | 481 | Debug << "\n" << ospSteps << " object space partition steps taken" << endl;
|
---|
| 482 |
|
---|
[1640] | 483 | /// Repair split queue, i.e., affected view space candidates
|
---|
[1633] | 484 | cout << "repairing queue ... " << endl;
|
---|
| 485 | RepairQueue(dirtyVspList, viewSpaceQueue, true);
|
---|
[1640] | 486 | cout << "\nrepaired " << (int)dirtyVspList.size() << " candidates" << endl;
|
---|
[1633] | 487 | }
|
---|
| 488 | else
|
---|
| 489 | {
|
---|
[1679] | 490 | lastSplitWasOsp = false;
|
---|
[1673] | 491 | cout << "vsp" << endl;
|
---|
| 492 |
|
---|
[1633] | 493 | /////////////////
|
---|
| 494 | // subdivide view space with respect to the objects
|
---|
[1625] | 495 |
|
---|
[1684] | 496 | // dirtied object space candidates
|
---|
[1633] | 497 | SubdivisionCandidateContainer dirtyOspList;
|
---|
[1624] | 498 |
|
---|
[1633] | 499 | // process view space candidates
|
---|
| 500 | const int vspSteps =
|
---|
[1676] | 501 | RunConstruction(viewSpaceQueue, dirtyOspList, objectSpaceQueue.Top(), minSteps, maxSteps);
|
---|
[1624] | 502 |
|
---|
[1640] | 503 | cout << "\n" << vspSteps << " view space partition steps taken" << endl;
|
---|
[1684] | 504 | Debug << "\n" << vspSteps << " view space partition steps taken" << endl;
|
---|
[1625] | 505 |
|
---|
[1633] | 506 | // view space subdivision constructed
|
---|
| 507 | mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
|
---|
[1624] | 508 |
|
---|
[1633] | 509 | /// Repair split queue
|
---|
| 510 | cout << "repairing queue ... " << endl;
|
---|
| 511 | RepairQueue(dirtyOspList, objectSpaceQueue, true);
|
---|
[1640] | 512 | cout << "repaired " << (int)dirtyOspList.size() << " candidates" << endl;
|
---|
[1633] | 513 | }
|
---|
[1449] | 514 | }
|
---|
[1633] | 515 |
|
---|
[1624] | 516 | cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
|
---|
| 517 |
|
---|
| 518 | mHierarchyStats.Stop();
|
---|
| 519 | mVspTree->mVspStats.Stop();
|
---|
[1625] | 520 |
|
---|
[1649] | 521 | FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
|
---|
[1449] | 522 | }
|
---|
| 523 |
|
---|
| 524 |
|
---|
| 525 | void HierarchyManager::ConstructInterleaved(const VssRayContainer &sampleRays,
|
---|
| 526 | const ObjectContainer &objects,
|
---|
| 527 | AxisAlignedBox3 *forcedViewSpace)
|
---|
| 528 | {
|
---|
[1308] | 529 | mHierarchyStats.Reset();
|
---|
| 530 | mHierarchyStats.Start();
|
---|
[1664] | 531 |
|
---|
| 532 | // two nodes for view space and object space
|
---|
| 533 | mHierarchyStats.mNodes = 2;
|
---|
[1640] | 534 | mHierarchyStats.mPvsEntries = 1;
|
---|
[1667] | 535 | mHierarchyStats.mMemory = (float)ObjectPvs::GetEntrySizeByte();
|
---|
[1640] | 536 | mHierarchyStats.mTotalCost = (float)objects.size();
|
---|
[1449] | 537 |
|
---|
[1624] | 538 | mHierarchyStats.mRenderCostDecrease = 0;
|
---|
[1237] | 539 |
|
---|
[1624] | 540 | EvalSubdivisionStats();
|
---|
| 541 | Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
|
---|
| 542 |
|
---|
[1311] | 543 | const long startTime = GetTime();
|
---|
[1308] | 544 | cout << "Constructing view space / object space tree ... \n";
|
---|
[1237] | 545 |
|
---|
[1640] | 546 | // create only roots
|
---|
| 547 | mVspTree->Initialise(sampleRays, forcedViewSpace);
|
---|
| 548 | InitialiseObjectSpaceSubdivision(objects);
|
---|
[1379] | 549 |
|
---|
[1633] | 550 | // use objects for evaluating vsp tree construction in the
|
---|
| 551 | // first levels of the subdivision
|
---|
[1323] | 552 | mSavedObjectSpaceSubdivisionType = mObjectSpaceSubdivisionType;
|
---|
| 553 | mObjectSpaceSubdivisionType = NO_OBJ_SUBDIV;
|
---|
| 554 |
|
---|
[1370] | 555 | mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
|
---|
| 556 | mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
|
---|
| 557 |
|
---|
[1632] | 558 | // start view space subdivison immediately?
|
---|
[1329] | 559 | if (StartViewSpaceSubdivision())
|
---|
| 560 | {
|
---|
[1624] | 561 | // prepare vsp tree for traversal
|
---|
[1640] | 562 | mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
|
---|
| 563 | SubdivisionCandidate *vspSc =
|
---|
| 564 | PrepareViewSpaceSubdivision(sampleRays, objects);
|
---|
| 565 |
|
---|
[1632] | 566 | mTQueue.Push(vspSc);
|
---|
[1329] | 567 | }
|
---|
| 568 |
|
---|
[1323] | 569 | // start object space subdivision immediately?
|
---|
| 570 | if (StartObjectSpaceSubdivision())
|
---|
| 571 | {
|
---|
| 572 | mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
|
---|
[1632] | 573 | SubdivisionCandidate *ospSc =
|
---|
| 574 | PrepareObjectSpaceSubdivision(sampleRays, objects);
|
---|
| 575 | mTQueue.Push(ospSc);
|
---|
[1323] | 576 | }
|
---|
[1632] | 577 |
|
---|
[1624] | 578 | // begin subdivision
|
---|
[1667] | 579 | RunConstruction(mRepairQueue, sampleRays, objects, forcedViewSpace);
|
---|
[1308] | 580 |
|
---|
[1418] | 581 | cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
|
---|
[1370] | 582 |
|
---|
[1548] | 583 | mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
|
---|
| 584 | mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
|
---|
| 585 |
|
---|
[1313] | 586 | mHierarchyStats.Stop();
|
---|
[1259] | 587 | mVspTree->mVspStats.Stop();
|
---|
[1649] | 588 |
|
---|
| 589 | FinishObjectSpaceSubdivision(objects, !mUseMultiLevelConstruction);
|
---|
[1237] | 590 | }
|
---|
| 591 |
|
---|
| 592 |
|
---|
[1625] | 593 | SubdivisionCandidate *HierarchyManager::PrepareViewSpaceSubdivision(const VssRayContainer &sampleRays,
|
---|
| 594 | const ObjectContainer &objects)
|
---|
[1311] | 595 | {
|
---|
[1632] | 596 | cout << "\npreparing view space hierarchy construction ... " << endl;
|
---|
[1625] | 597 |
|
---|
[1580] | 598 | // hack: reset global cost misses
|
---|
[1548] | 599 | mHierarchyStats.mGlobalCostMisses = 0;
|
---|
[1625] | 600 |
|
---|
[1311] | 601 | RayInfoContainer *viewSpaceRays = new RayInfoContainer();
|
---|
| 602 | SubdivisionCandidate *vsc =
|
---|
[1379] | 603 | mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
|
---|
[1311] | 604 |
|
---|
[1661] | 605 | /////////
|
---|
| 606 | //-- new stats
|
---|
| 607 |
|
---|
[1624] | 608 | mHierarchyStats.mTotalCost = mVspTree->mTotalCost;
|
---|
[1662] | 609 |
|
---|
[1624] | 610 | cout << "\nreseting cost for vsp, new total cost: " << mHierarchyStats.mTotalCost << endl;
|
---|
[1421] | 611 |
|
---|
[1625] | 612 | return vsc;
|
---|
[1311] | 613 | }
|
---|
| 614 |
|
---|
| 615 |
|
---|
[1640] | 616 | float HierarchyManager::GetObjectSpaceMemUsage() const
|
---|
| 617 | {
|
---|
| 618 | if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
|
---|
| 619 | {
|
---|
| 620 | // TODO;
|
---|
| 621 | }
|
---|
| 622 | else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
|
---|
| 623 | {
|
---|
| 624 | return mBvHierarchy->GetMemUsage();
|
---|
| 625 | }
|
---|
| 626 |
|
---|
| 627 | return -1;
|
---|
| 628 | }
|
---|
| 629 |
|
---|
| 630 | void HierarchyManager::InitialiseObjectSpaceSubdivision(const ObjectContainer &objects)
|
---|
| 631 | {
|
---|
| 632 | if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
|
---|
| 633 | {
|
---|
| 634 | // TODO;
|
---|
| 635 | }
|
---|
| 636 | else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
|
---|
| 637 | {
|
---|
| 638 | mBvHierarchy->Initialise(objects);
|
---|
| 639 | }
|
---|
| 640 | }
|
---|
| 641 |
|
---|
| 642 |
|
---|
[1625] | 643 | SubdivisionCandidate *HierarchyManager::PrepareObjectSpaceSubdivision(const VssRayContainer &sampleRays,
|
---|
| 644 | const ObjectContainer &objects)
|
---|
[1308] | 645 | {
|
---|
[1625] | 646 | // hack: reset global cost misses
|
---|
| 647 | mHierarchyStats.mGlobalCostMisses = 0;
|
---|
[1522] | 648 |
|
---|
[1308] | 649 | if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
|
---|
| 650 | {
|
---|
[1625] | 651 | return PrepareOspTree(sampleRays, objects);
|
---|
[1308] | 652 | }
|
---|
| 653 | else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
|
---|
| 654 | {
|
---|
[1625] | 655 | return PrepareBvHierarchy(sampleRays, objects);
|
---|
[1308] | 656 | }
|
---|
[1625] | 657 |
|
---|
| 658 | return NULL;
|
---|
[1308] | 659 | }
|
---|
[1294] | 660 |
|
---|
[1308] | 661 |
|
---|
[1625] | 662 | SubdivisionCandidate *HierarchyManager::PrepareBvHierarchy(const VssRayContainer &sampleRays,
|
---|
| 663 | const ObjectContainer &objects)
|
---|
[1294] | 664 | {
|
---|
[1421] | 665 | const long startTime = GetTime();
|
---|
| 666 |
|
---|
| 667 | cout << "preparing bv hierarchy construction ... " << endl;
|
---|
[1548] | 668 |
|
---|
[1294] | 669 | // compute first candidate
|
---|
| 670 | SubdivisionCandidate *sc =
|
---|
| 671 | mBvHierarchy->PrepareConstruction(sampleRays, objects);
|
---|
| 672 |
|
---|
[1624] | 673 | mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
|
---|
| 674 | Debug << "\nreseting cost, new total cost: " << mHierarchyStats.mTotalCost << endl;
|
---|
[1294] | 675 |
|
---|
[1548] | 676 | cout << "finished bv hierarchy preparation in "
|
---|
| 677 | << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
|
---|
[1625] | 678 |
|
---|
| 679 | return sc;
|
---|
[1294] | 680 | }
|
---|
| 681 |
|
---|
| 682 |
|
---|
[1625] | 683 | SubdivisionCandidate *HierarchyManager::PrepareOspTree(const VssRayContainer &sampleRays,
|
---|
| 684 | const ObjectContainer &objects)
|
---|
[1294] | 685 | {
|
---|
[1370] | 686 | cout << "starting osp tree construction ... " << endl;
|
---|
| 687 |
|
---|
[1294] | 688 | RayInfoContainer *objectSpaceRays = new RayInfoContainer();
|
---|
| 689 |
|
---|
| 690 | // start with one big kd cell - all objects can be seen from everywhere
|
---|
| 691 | // note: only true for view space = object space
|
---|
| 692 |
|
---|
| 693 | // compute first candidate
|
---|
| 694 | SubdivisionCandidate *osc =
|
---|
| 695 | mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
|
---|
| 696 |
|
---|
[1624] | 697 | mHierarchyStats.mTotalCost = mOspTree->mTotalCost;
|
---|
[1625] | 698 | Debug << "\nreseting cost for osp, new total cost: " << mHierarchyStats.mTotalCost << endl;
|
---|
[1294] | 699 |
|
---|
[1625] | 700 | return osc;
|
---|
[1294] | 701 | }
|
---|
| 702 |
|
---|
| 703 |
|
---|
[1624] | 704 | bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc,
|
---|
[1625] | 705 | SplitQueue &splitQueue,
|
---|
[1624] | 706 | const bool repairQueue)
|
---|
[1237] | 707 | {
|
---|
[1624] | 708 | const bool terminationCriteriaMet = GlobalTerminationCriteriaMet(sc);
|
---|
[1633] | 709 | const bool success = sc->Apply(splitQueue, terminationCriteriaMet);
|
---|
[1444] | 710 |
|
---|
[1610] | 711 | if (!success) // split was not taken
|
---|
| 712 | {
|
---|
| 713 | return false;
|
---|
| 714 | }
|
---|
| 715 |
|
---|
| 716 | ///////////////
|
---|
[1624] | 717 | //-- split was successful => update stats and queue
|
---|
[1610] | 718 |
|
---|
| 719 | // cost ratio of cost decrease / totalCost
|
---|
[1624] | 720 | const float costRatio = sc->GetRenderCostDecrease() / mHierarchyStats.mTotalCost;
|
---|
[1610] | 721 | //Debug << "ratio: " << costRatio << " min ratio: " << mTermMinGlobalCostRatio << endl;
|
---|
| 722 |
|
---|
| 723 | if (costRatio < mTermMinGlobalCostRatio)
|
---|
| 724 | {
|
---|
| 725 | ++ mHierarchyStats.mGlobalCostMisses;
|
---|
| 726 | }
|
---|
| 727 |
|
---|
[1580] | 728 | cout << sc->Type() << " ";
|
---|
| 729 |
|
---|
[1640] | 730 | /////////////
|
---|
[1580] | 731 | // update stats
|
---|
[1640] | 732 |
|
---|
[1624] | 733 | mHierarchyStats.mNodes += 2;
|
---|
[1640] | 734 | mHierarchyStats.mTotalCost -= sc->GetRenderCostDecrease();
|
---|
| 735 |
|
---|
| 736 | const int pvsEntriesIncr = sc->GetPvsEntriesIncr();
|
---|
| 737 | mHierarchyStats.mPvsEntries += pvsEntriesIncr;
|
---|
| 738 | //cout << "pvs entries: " << pvsEntriesIncr << " " << mHierarchyStats.pvsEntries << endl;
|
---|
| 739 |
|
---|
| 740 | // memory size in byte
|
---|
[1676] | 741 | mHierarchyStats.mMemory += (float)ObjectPvs::GetEntrySizeByte() * pvsEntriesIncr;
|
---|
[1624] | 742 | mHierarchyStats.mRenderCostDecrease = sc->GetRenderCostDecrease();
|
---|
| 743 |
|
---|
[1654] | 744 | static float memoryCount = 0;
|
---|
| 745 |
|
---|
| 746 | if (mHierarchyStats.mMemory > memoryCount)
|
---|
| 747 | {
|
---|
| 748 | memoryCount += 100000;
|
---|
[1684] | 749 | cout << "\nstorage cost: " << mHierarchyStats.mMemory / float(1024 * 1024)
|
---|
| 750 | << " MB, steps: " << mHierarchyStats.Leaves() << endl;
|
---|
[1654] | 751 | }
|
---|
| 752 |
|
---|
[1640] | 753 | // output stats
|
---|
[1624] | 754 | EvalSubdivisionStats();
|
---|
[1580] | 755 |
|
---|
| 756 | if (repairQueue)
|
---|
[1624] | 757 | {
|
---|
| 758 | // reevaluate candidates affected by the split for view space splits,
|
---|
| 759 | // this would be object space splits and other way round
|
---|
[1625] | 760 | vector<SubdivisionCandidate *> dirtyList;
|
---|
[1633] | 761 | sc->CollectDirtyCandidates(dirtyList, false);
|
---|
[1624] | 762 |
|
---|
[1633] | 763 | RepairQueue(dirtyList, splitQueue, mRecomputeSplitPlaneOnRepair);
|
---|
[1580] | 764 | }
|
---|
| 765 |
|
---|
[1416] | 766 | return true;
|
---|
[1237] | 767 | }
|
---|
| 768 |
|
---|
| 769 |
|
---|
[1370] | 770 | int HierarchyManager::GetObjectSpaceSubdivisionDepth() const
|
---|
| 771 | {
|
---|
| 772 | int maxDepth = 0;
|
---|
| 773 |
|
---|
| 774 | if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
|
---|
| 775 | {
|
---|
| 776 | maxDepth = mOspTree->mOspStats.maxDepth;
|
---|
| 777 | }
|
---|
| 778 | else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
|
---|
| 779 | {
|
---|
| 780 | maxDepth = mBvHierarchy->mBvhStats.maxDepth;
|
---|
| 781 | }
|
---|
| 782 |
|
---|
| 783 | return maxDepth;
|
---|
| 784 | }
|
---|
| 785 |
|
---|
| 786 |
|
---|
[1640] | 787 | int HierarchyManager::GetObjectSpaceSubdivisionLeaves() const
|
---|
| 788 | {
|
---|
| 789 | int maxLeaves= 0;
|
---|
| 790 |
|
---|
| 791 | if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
|
---|
| 792 | {
|
---|
| 793 | maxLeaves = mOspTree->mOspStats.Leaves();
|
---|
| 794 | }
|
---|
| 795 | else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
|
---|
| 796 | {
|
---|
| 797 | maxLeaves = mBvHierarchy->mBvhStats.Leaves();
|
---|
| 798 | }
|
---|
| 799 |
|
---|
| 800 | return maxLeaves;
|
---|
| 801 | }
|
---|
| 802 |
|
---|
| 803 |
|
---|
[1663] | 804 | int HierarchyManager::GetObjectSpaceSubdivisionNodes() const
|
---|
| 805 | {
|
---|
| 806 | int maxLeaves = 0;
|
---|
| 807 |
|
---|
| 808 | if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
|
---|
| 809 | {
|
---|
| 810 | maxLeaves = mOspTree->mOspStats.nodes;
|
---|
| 811 | }
|
---|
| 812 | else if (mObjectSpaceSubdivisionType == BV_BASED_OBJ_SUBDIV)
|
---|
| 813 | {
|
---|
| 814 | maxLeaves = mBvHierarchy->mBvhStats.nodes;
|
---|
| 815 | }
|
---|
| 816 |
|
---|
| 817 | return maxLeaves;
|
---|
| 818 | }
|
---|
| 819 |
|
---|
[1308] | 820 | bool HierarchyManager::StartObjectSpaceSubdivision() const
|
---|
[1237] | 821 | {
|
---|
[1370] | 822 | // view space construction already started
|
---|
| 823 | if (ObjectSpaceSubdivisionConstructed())
|
---|
| 824 | return false;
|
---|
| 825 |
|
---|
| 826 | // start immediately with object space subdivision?
|
---|
| 827 | if (mStartWithObjectSpace)
|
---|
| 828 | return true;
|
---|
| 829 |
|
---|
| 830 | // is the queue empty again?
|
---|
| 831 | if (ViewSpaceSubdivisionConstructed() && mTQueue.Empty())
|
---|
| 832 | return true;
|
---|
| 833 |
|
---|
| 834 | // has the depth for subdivision been reached?
|
---|
| 835 | return
|
---|
| 836 | ((mConstructionType == INTERLEAVED) &&
|
---|
[1640] | 837 | (mMinStepsOfSameType <= mVspTree->mVspStats.nodes));
|
---|
[1308] | 838 | }
|
---|
| 839 |
|
---|
| 840 |
|
---|
[1329] | 841 | bool HierarchyManager::StartViewSpaceSubdivision() const
|
---|
| 842 | {
|
---|
[1370] | 843 | // view space construction already started
|
---|
| 844 | if (ViewSpaceSubdivisionConstructed())
|
---|
| 845 | return false;
|
---|
| 846 |
|
---|
| 847 | // start immediately with view space subdivision?
|
---|
| 848 | if (!mStartWithObjectSpace)
|
---|
| 849 | return true;
|
---|
| 850 |
|
---|
| 851 | // is the queue empty again?
|
---|
| 852 | if (ObjectSpaceSubdivisionConstructed() && mTQueue.Empty())
|
---|
| 853 | return true;
|
---|
| 854 |
|
---|
| 855 | // has the depth for subdivision been reached?
|
---|
| 856 | return
|
---|
| 857 | ((mConstructionType == INTERLEAVED) &&
|
---|
[1640] | 858 | (mMinStepsOfSameType <= GetObjectSpaceSubdivisionLeaves()));
|
---|
[1329] | 859 | }
|
---|
| 860 |
|
---|
| 861 |
|
---|
[1449] | 862 | void HierarchyManager::RunConstruction(const bool repairQueue,
|
---|
| 863 | const VssRayContainer &sampleRays,
|
---|
[1311] | 864 | const ObjectContainer &objects,
|
---|
[1640] | 865 | AxisAlignedBox3 *forcedViewSpace)
|
---|
[1308] | 866 | {
|
---|
[1313] | 867 | while (!FinishedConstruction())
|
---|
| 868 | {
|
---|
[1625] | 869 | SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
|
---|
[1632] | 870 |
|
---|
[1415] | 871 | ///////////////////
|
---|
[1237] | 872 | //-- subdivide leaf node
|
---|
[1415] | 873 |
|
---|
[1625] | 874 | ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
|
---|
[1580] | 875 |
|
---|
[1313] | 876 | // we use objects for evaluating vsp tree construction until
|
---|
[1415] | 877 | // a certain depth once a certain depth existiert ...
|
---|
[1313] | 878 | if (StartObjectSpaceSubdivision())
|
---|
| 879 | {
|
---|
[1323] | 880 | mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
|
---|
[1314] | 881 |
|
---|
[1640] | 882 | cout << "\nstarting object space subdivision after "
|
---|
[1676] | 883 | << mVspTree->mVspStats.nodes << " (" << mMinStepsOfSameType << ") " << endl;
|
---|
[1329] | 884 |
|
---|
[1632] | 885 | SubdivisionCandidate *ospSc = PrepareObjectSpaceSubdivision(sampleRays, objects);
|
---|
[1640] | 886 |
|
---|
[1313] | 887 | cout << "reseting queue ... ";
|
---|
[1640] | 888 | ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
|
---|
[1313] | 889 | cout << "finished" << endl;
|
---|
[1640] | 890 |
|
---|
| 891 | mTQueue.Push(ospSc);
|
---|
[1313] | 892 | }
|
---|
| 893 |
|
---|
[1329] | 894 | if (StartViewSpaceSubdivision())
|
---|
| 895 | {
|
---|
| 896 | mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
|
---|
| 897 |
|
---|
[1415] | 898 | cout << "\nstarting view space subdivision at depth "
|
---|
[1640] | 899 | << GetObjectSpaceSubdivisionLeaves() << " ("
|
---|
| 900 | << mMinStepsOfSameType << ") " << endl;
|
---|
[1329] | 901 |
|
---|
[1640] | 902 | SubdivisionCandidate *vspSc = PrepareViewSpaceSubdivision(sampleRays, objects);
|
---|
[1329] | 903 |
|
---|
| 904 | cout << "reseting queue ... ";
|
---|
[1640] | 905 | ResetQueue(mTQueue, mRecomputeSplitPlaneOnRepair);
|
---|
[1329] | 906 | cout << "finished" << endl;
|
---|
[1640] | 907 |
|
---|
| 908 | // push view space candidate
|
---|
| 909 | mTQueue.Push(vspSc);
|
---|
[1329] | 910 | }
|
---|
| 911 |
|
---|
[1624] | 912 | DEL_PTR(sc);
|
---|
[1237] | 913 | }
|
---|
| 914 | }
|
---|
| 915 |
|
---|
| 916 |
|
---|
[1449] | 917 | void HierarchyManager::RunConstruction(const bool repairQueue)
|
---|
| 918 | {
|
---|
[1580] | 919 | // main loop
|
---|
[1449] | 920 | while (!FinishedConstruction())
|
---|
| 921 | {
|
---|
[1625] | 922 | SubdivisionCandidate *sc = NextSubdivisionCandidate(mTQueue);
|
---|
[1649] | 923 |
|
---|
[1624] | 924 | ////////
|
---|
| 925 | //-- subdivide leaf node of either type
|
---|
[1642] | 926 | ApplySubdivisionCandidate(sc, mTQueue, repairQueue);
|
---|
| 927 |
|
---|
[1624] | 928 | DEL_PTR(sc);
|
---|
[1449] | 929 | }
|
---|
| 930 | }
|
---|
| 931 |
|
---|
| 932 |
|
---|
[1625] | 933 | int HierarchyManager::RunConstruction(SplitQueue &splitQueue,
|
---|
[1633] | 934 | SubdivisionCandidateContainer &dirtyCandidates,
|
---|
[1667] | 935 | SubdivisionCandidate *oldCandidate,
|
---|
[1676] | 936 | const int minSteps,
|
---|
| 937 | const int maxSteps)
|
---|
[1624] | 938 | {
|
---|
[1676] | 939 | if (minSteps >= maxSteps)
|
---|
| 940 | cout << "error!! " << minSteps << " equal or larger maxSteps" << endl;
|
---|
| 941 |
|
---|
[1625] | 942 | int steps = 0;
|
---|
[1633] | 943 | SubdivisionCandidate::NewMail();
|
---|
[1625] | 944 |
|
---|
[1624] | 945 | // main loop
|
---|
[1634] | 946 | while (!splitQueue.Empty())
|
---|
[1624] | 947 | {
|
---|
[1701] | 948 | const float priority = splitQueue.Top()->GetPriority();
|
---|
[1686] | 949 | const float threshold = oldCandidate ? oldCandidate->GetPriority() : 1e20f;
|
---|
[1679] | 950 |
|
---|
[1701] | 951 | // minimum slope reached
|
---|
| 952 | if ((steps >= maxSteps) || ((priority < threshold) && !(steps < minSteps)))
|
---|
| 953 | {
|
---|
| 954 | cout << "\n**************** breaking on " << priority << " smaller than " << threshold << endl;
|
---|
| 955 | break;
|
---|
| 956 | }
|
---|
| 957 |
|
---|
| 958 | SubdivisionCandidate *sc = NextSubdivisionCandidate(splitQueue);
|
---|
| 959 |
|
---|
[1624] | 960 | ////////
|
---|
| 961 | //-- subdivide leaf node of either type
|
---|
| 962 |
|
---|
[1625] | 963 | const bool repairQueue = false;
|
---|
[1633] | 964 | const bool success = ApplySubdivisionCandidate(sc, splitQueue, repairQueue);
|
---|
[1625] | 965 |
|
---|
[1632] | 966 | if (success)
|
---|
| 967 | {
|
---|
[1697] | 968 | sc->CollectDirtyCandidates(dirtyCandidates, true);
|
---|
[1633] | 969 | ++ steps;
|
---|
[1632] | 970 | }
|
---|
[1696] | 971 |
|
---|
| 972 | DEL_PTR(sc);
|
---|
[1624] | 973 | }
|
---|
[1625] | 974 |
|
---|
| 975 | return steps;
|
---|
[1624] | 976 | }
|
---|
| 977 |
|
---|
| 978 |
|
---|
[1625] | 979 | SubdivisionCandidate *HierarchyManager::ResetObjectSpaceSubdivision(const VssRayContainer &sampleRays,
|
---|
| 980 | const ObjectContainer &objects)
|
---|
[1580] | 981 | {
|
---|
[1632] | 982 | SubdivisionCandidate *firstCandidate;
|
---|
[1625] | 983 |
|
---|
[1580] | 984 | // object space partition constructed => reconstruct
|
---|
[1557] | 985 | switch (mObjectSpaceSubdivisionType)
|
---|
| 986 | {
|
---|
| 987 | case BV_BASED_OBJ_SUBDIV:
|
---|
[1580] | 988 | {
|
---|
| 989 | cout << "\nreseting bv hierarchy" << endl;
|
---|
| 990 | Debug << "old bv hierarchy:\n " << mBvHierarchy->mBvhStats << endl;
|
---|
[1663] | 991 |
|
---|
| 992 | // rather use this: remove previous nodes and add the two new ones
|
---|
| 993 | //mHierarchyStats.mNodes -= mBvHierarchy->mBvhStats.nodes + 1;
|
---|
| 994 | mHierarchyStats.mNodes = mVspTree->mVspStats.nodes;
|
---|
[1649] | 995 |
|
---|
[1663] | 996 | // create root
|
---|
[1642] | 997 | mBvHierarchy->Initialise(objects);
|
---|
[1649] | 998 |
|
---|
[1632] | 999 | firstCandidate = mBvHierarchy->Reset(sampleRays, objects);
|
---|
[1649] | 1000 |
|
---|
[1625] | 1001 | mHierarchyStats.mTotalCost = mBvHierarchy->mTotalCost;
|
---|
[1663] | 1002 |
|
---|
[1662] | 1003 | //mHierarchyStats.mPvsEntries -= mBvHierarchy->mPvsEntries + 1;
|
---|
[1649] | 1004 | mHierarchyStats.mPvsEntries = mBvHierarchy->CountViewCells(objects);
|
---|
[1663] | 1005 |
|
---|
[1667] | 1006 | mHierarchyStats.mMemory =
|
---|
| 1007 | (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
|
---|
[1642] | 1008 |
|
---|
[1662] | 1009 | mHierarchyStats.mRenderCostDecrease = 0;
|
---|
| 1010 |
|
---|
[1625] | 1011 | // evaluate stats before first subdivision
|
---|
| 1012 | EvalSubdivisionStats();
|
---|
[1649] | 1013 | cout << "finished bv hierarchy preparation" << endl;
|
---|
[1580] | 1014 | }
|
---|
[1548] | 1015 | break;
|
---|
[1557] | 1016 |
|
---|
[1548] | 1017 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 1018 | // TODO
|
---|
| 1019 | default:
|
---|
[1632] | 1020 | firstCandidate = NULL;
|
---|
[1548] | 1021 | break;
|
---|
| 1022 | }
|
---|
[1633] | 1023 |
|
---|
[1625] | 1024 | return firstCandidate;
|
---|
[1449] | 1025 | }
|
---|
| 1026 |
|
---|
| 1027 |
|
---|
[1625] | 1028 | SubdivisionCandidate *HierarchyManager::ResetViewSpaceSubdivision(const VssRayContainer &sampleRays,
|
---|
[1642] | 1029 | const ObjectContainer &objects,
|
---|
| 1030 | AxisAlignedBox3 *forcedViewSpace)
|
---|
[1557] | 1031 | {
|
---|
[1649] | 1032 | ViewCellsManager *vm = mVspTree->mViewCellsManager;
|
---|
[1557] | 1033 |
|
---|
[1624] | 1034 | // HACK: rather not destroy vsp tree
|
---|
[1580] | 1035 | DEL_PTR(mVspTree);
|
---|
| 1036 | mVspTree = new VspTree();
|
---|
[1649] | 1037 |
|
---|
[1580] | 1038 | mVspTree->mHierarchyManager = this;
|
---|
[1649] | 1039 | mVspTree->mViewCellsManager = vm;
|
---|
[1580] | 1040 |
|
---|
[1642] | 1041 | mVspTree->Initialise(sampleRays, forcedViewSpace);
|
---|
[1580] | 1042 |
|
---|
[1662] | 1043 | //-- reset stats
|
---|
[1663] | 1044 | mHierarchyStats.mNodes = GetObjectSpaceSubdivisionNodes();//-mVspTree->mVspStats.nodes + 1;
|
---|
[1662] | 1045 |
|
---|
| 1046 | SubdivisionCandidate *vsc = PrepareViewSpaceSubdivision(sampleRays, objects);
|
---|
| 1047 |
|
---|
| 1048 | mHierarchyStats.mPvsEntries = mVspTree->mPvsEntries;
|
---|
[1661] | 1049 | mHierarchyStats.mRenderCostDecrease = 0;
|
---|
| 1050 |
|
---|
[1667] | 1051 | mHierarchyStats.mMemory = (float)mHierarchyStats.mPvsEntries * ObjectPvs::GetEntrySizeByte();
|
---|
[1662] | 1052 |
|
---|
[1640] | 1053 | // evaluate new stats before first subdivsiion
|
---|
[1624] | 1054 | EvalSubdivisionStats();
|
---|
[1625] | 1055 |
|
---|
| 1056 | return vsc;
|
---|
[1557] | 1057 | }
|
---|
| 1058 |
|
---|
| 1059 |
|
---|
[1449] | 1060 | void HierarchyManager::ConstructMultiLevel(const VssRayContainer &sampleRays,
|
---|
| 1061 | const ObjectContainer &objects,
|
---|
| 1062 | AxisAlignedBox3 *forcedViewSpace)
|
---|
| 1063 | {
|
---|
| 1064 | mHierarchyStats.Reset();
|
---|
| 1065 | mHierarchyStats.Start();
|
---|
[1624] | 1066 | mHierarchyStats.mNodes = 2;
|
---|
[1449] | 1067 |
|
---|
[1624] | 1068 | mHierarchyStats.mTotalCost = (float)objects.size();
|
---|
| 1069 | Debug << "setting total cost to " << mHierarchyStats.mTotalCost << endl;
|
---|
[1449] | 1070 |
|
---|
| 1071 | const long startTime = GetTime();
|
---|
| 1072 | cout << "Constructing view space / object space tree ... \n";
|
---|
| 1073 |
|
---|
[1640] | 1074 | // initialise view / object space
|
---|
| 1075 | mVspTree->Initialise(sampleRays, forcedViewSpace);
|
---|
| 1076 | InitialiseObjectSpaceSubdivision(objects);
|
---|
[1449] | 1077 |
|
---|
[1580] | 1078 | // use sah for evaluating osp tree construction
|
---|
| 1079 | // in the first iteration of the subdivision
|
---|
[1642] | 1080 |
|
---|
[1449] | 1081 | mSavedViewSpaceSubdivisionType = mViewSpaceSubdivisionType;
|
---|
| 1082 | mViewSpaceSubdivisionType = NO_VIEWSPACE_SUBDIV;
|
---|
[1640] | 1083 |
|
---|
[1642] | 1084 | SubdivisionCandidate *osc =
|
---|
| 1085 | PrepareObjectSpaceSubdivision(sampleRays, objects);
|
---|
| 1086 | mTQueue.Push(osc);
|
---|
[1640] | 1087 |
|
---|
[1649] | 1088 | //////////////////////////
|
---|
[1642] | 1089 |
|
---|
| 1090 |
|
---|
[1640] | 1091 | const int limit = mNumMultiLevels;
|
---|
| 1092 | int i = 0;
|
---|
| 1093 |
|
---|
| 1094 | // This method subdivides view space / object space
|
---|
| 1095 | // in order to converge to some optimal cost for this partition
|
---|
| 1096 | // start with object space partiton
|
---|
| 1097 | // then optimizate view space partition for the current osp
|
---|
| 1098 | // and vice versa until iteration depth is reached.
|
---|
| 1099 | while (1)
|
---|
| 1100 | {
|
---|
| 1101 | char subdivisionStatsLog[100];
|
---|
| 1102 | sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
|
---|
| 1103 | mSubdivisionStats.open(subdivisionStatsLog);
|
---|
| 1104 |
|
---|
| 1105 | // subdivide object space first
|
---|
[1642] | 1106 | osc = ResetObjectSpaceSubdivision(sampleRays, objects);
|
---|
| 1107 | mTQueue.Push(osc);
|
---|
[1640] | 1108 |
|
---|
| 1109 | // process object space candidates
|
---|
| 1110 | RunConstruction(false);
|
---|
| 1111 |
|
---|
| 1112 | // object space subdivision constructed
|
---|
| 1113 | mObjectSpaceSubdivisionType = mSavedObjectSpaceSubdivisionType;
|
---|
| 1114 |
|
---|
| 1115 | cout << "iteration " << i << " of " << limit << " finished" << endl;
|
---|
| 1116 | mSubdivisionStats.close();
|
---|
| 1117 |
|
---|
| 1118 | if ((i ++) >= limit)
|
---|
| 1119 | break;
|
---|
| 1120 |
|
---|
| 1121 | sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", i);
|
---|
| 1122 | mSubdivisionStats.open(subdivisionStatsLog);
|
---|
| 1123 |
|
---|
[1649] | 1124 |
|
---|
[1640] | 1125 | /////////////////
|
---|
| 1126 | // subdivide view space with respect to the objects
|
---|
| 1127 |
|
---|
[1649] | 1128 | SubdivisionCandidate *vspVc =
|
---|
| 1129 | ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
|
---|
[1640] | 1130 | mTQueue.Push(vspVc);
|
---|
| 1131 |
|
---|
| 1132 | // view space subdivision constructed
|
---|
| 1133 | mViewSpaceSubdivisionType = mSavedViewSpaceSubdivisionType;
|
---|
| 1134 |
|
---|
| 1135 | // process view space candidates
|
---|
| 1136 | RunConstruction(false);
|
---|
| 1137 |
|
---|
| 1138 | cout << "iteration " << i << " of " << limit << " finished" << endl;
|
---|
| 1139 | mSubdivisionStats.close();
|
---|
| 1140 |
|
---|
| 1141 | if ((i ++) >= limit)
|
---|
| 1142 | break;
|
---|
| 1143 | }
|
---|
[1635] | 1144 |
|
---|
[1640] | 1145 | cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
|
---|
[1580] | 1146 |
|
---|
[1640] | 1147 | mHierarchyStats.Stop();
|
---|
| 1148 | mVspTree->mVspStats.Stop();
|
---|
| 1149 | FinishObjectSpaceSubdivision(objects);
|
---|
| 1150 | }
|
---|
| 1151 |
|
---|
| 1152 |
|
---|
| 1153 | void HierarchyManager::OptimizeMultiLevel(const VssRayContainer &sampleRays,
|
---|
| 1154 | const ObjectContainer &objects,
|
---|
| 1155 | AxisAlignedBox3 *forcedViewSpace)
|
---|
| 1156 | {
|
---|
[1649] | 1157 | const long startTime = GetTime();
|
---|
| 1158 | const int limit = mNumMultiLevels;
|
---|
| 1159 |
|
---|
| 1160 | // open up new subdivision
|
---|
| 1161 | mSubdivisionStats.close();
|
---|
| 1162 |
|
---|
| 1163 | int steps = 0;
|
---|
| 1164 |
|
---|
| 1165 | int maxViewSpaceLeaves = mVspTree->mVspStats.Leaves();
|
---|
| 1166 | int maxObjectSpaceLeaves;
|
---|
| 1167 |
|
---|
[1642] | 1168 | // set the number of leaves 'evaluated' from the previous methods
|
---|
[1649] | 1169 | // we go for the same numbers, but we try to optimize both subdivisions
|
---|
[1642] | 1170 | switch (mObjectSpaceSubdivisionType)
|
---|
| 1171 | {
|
---|
| 1172 | case BV_BASED_OBJ_SUBDIV:
|
---|
[1649] | 1173 | maxObjectSpaceLeaves = mBvHierarchy->mBvhStats.Leaves();
|
---|
[1642] | 1174 | break;
|
---|
| 1175 | case KD_BASED_OBJ_SUBDIV:
|
---|
[1649] | 1176 | maxObjectSpaceLeaves = mOspTree->mOspStats.Leaves();
|
---|
[1642] | 1177 | default:
|
---|
[1649] | 1178 | maxObjectSpaceLeaves = 0;
|
---|
[1642] | 1179 | break;
|
---|
| 1180 | }
|
---|
[1640] | 1181 |
|
---|
[1624] | 1182 | // This method subdivides view space / object space
|
---|
| 1183 | // in order to converge to some optimal cost for this partition
|
---|
[1557] | 1184 | // start with object space partiton
|
---|
| 1185 | // then optimizate view space partition for the current osp
|
---|
| 1186 | // and vice versa until iteration depth is reached.
|
---|
| 1187 | while (1)
|
---|
[1548] | 1188 | {
|
---|
[1580] | 1189 | char subdivisionStatsLog[100];
|
---|
[1642] | 1190 | sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
|
---|
[1580] | 1191 | mSubdivisionStats.open(subdivisionStatsLog);
|
---|
| 1192 |
|
---|
[1624] | 1193 | // subdivide object space first
|
---|
[1643] | 1194 | SubdivisionCandidate *ospVc =
|
---|
| 1195 | ResetObjectSpaceSubdivision(sampleRays, objects);
|
---|
[1649] | 1196 |
|
---|
| 1197 | // set the number of leaves 'evaluated' from the previous methods
|
---|
| 1198 | // we go for the same numbers, but we try to optimize both subdivisions
|
---|
| 1199 | mBvHierarchy->mTermMaxLeaves = maxObjectSpaceLeaves;
|
---|
[1642] | 1200 | mTQueue.Push(ospVc);
|
---|
[1624] | 1201 |
|
---|
[1548] | 1202 | // process object space candidates
|
---|
| 1203 | RunConstruction(false);
|
---|
[1449] | 1204 |
|
---|
[1642] | 1205 | cout << "iteration " << steps << " of " << limit << " finished" << endl;
|
---|
[1580] | 1206 | mSubdivisionStats.close();
|
---|
[1635] | 1207 |
|
---|
[1642] | 1208 | if ((++ steps) >= limit)
|
---|
[1557] | 1209 | break;
|
---|
| 1210 |
|
---|
[1642] | 1211 | sprintf(subdivisionStatsLog, "tests/i3d/subdivision-%04d.log", steps);
|
---|
[1580] | 1212 | mSubdivisionStats.open(subdivisionStatsLog);
|
---|
| 1213 |
|
---|
[1557] | 1214 | /////////////////
|
---|
[1580] | 1215 | // subdivide view space with respect to the objects
|
---|
| 1216 |
|
---|
[1643] | 1217 | SubdivisionCandidate *vspVc =
|
---|
| 1218 | ResetViewSpaceSubdivision(sampleRays, objects, forcedViewSpace);
|
---|
[1649] | 1219 |
|
---|
| 1220 | mVspTree->mMaxViewCells = maxViewSpaceLeaves;
|
---|
[1640] | 1221 | mTQueue.Push(vspVc);
|
---|
[1624] | 1222 |
|
---|
[1548] | 1223 | // process view space candidates
|
---|
| 1224 | RunConstruction(false);
|
---|
[1624] | 1225 |
|
---|
[1642] | 1226 | cout << "iteration " << steps << " of " << limit << " finished" << endl;
|
---|
[1580] | 1227 | mSubdivisionStats.close();
|
---|
| 1228 |
|
---|
[1642] | 1229 | if ((++ steps) >= limit)
|
---|
[1557] | 1230 | break;
|
---|
[1548] | 1231 | }
|
---|
| 1232 |
|
---|
[1449] | 1233 | cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
|
---|
| 1234 |
|
---|
| 1235 | mHierarchyStats.Stop();
|
---|
| 1236 | mVspTree->mVspStats.Stop();
|
---|
| 1237 | FinishObjectSpaceSubdivision(objects);
|
---|
| 1238 | }
|
---|
| 1239 |
|
---|
| 1240 |
|
---|
[1640] | 1241 |
|
---|
[1237] | 1242 | bool HierarchyManager::FinishedConstruction() const
|
---|
| 1243 | {
|
---|
| 1244 | return mTQueue.Empty();
|
---|
| 1245 | }
|
---|
| 1246 |
|
---|
| 1247 |
|
---|
[1313] | 1248 | bool HierarchyManager::ObjectSpaceSubdivisionConstructed() const
|
---|
[1311] | 1249 | {
|
---|
[1642] | 1250 | /*switch (mObjectSpaceSubdivisionType)
|
---|
[1311] | 1251 | {
|
---|
| 1252 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 1253 | return mOspTree && mOspTree->GetRoot();
|
---|
| 1254 | case BV_BASED_OBJ_SUBDIV:
|
---|
[1344] | 1255 | return mBvHierarchy && mBvHierarchy->GetRoot();
|
---|
[1311] | 1256 | default:
|
---|
[1580] | 1257 | return false;
|
---|
[1642] | 1258 | }*/
|
---|
| 1259 | return mObjectSpaceSubdivisionType != NO_OBJ_SUBDIV;
|
---|
[1311] | 1260 | }
|
---|
| 1261 |
|
---|
| 1262 |
|
---|
[1329] | 1263 | bool HierarchyManager::ViewSpaceSubdivisionConstructed() const
|
---|
| 1264 | {
|
---|
[1635] | 1265 | return mViewSpaceSubdivisionType != NO_VIEWSPACE_SUBDIV;
|
---|
| 1266 | //return mVspTree && mVspTree->GetRoot();
|
---|
[1329] | 1267 | }
|
---|
| 1268 |
|
---|
| 1269 |
|
---|
[1625] | 1270 | void HierarchyManager::CollectDirtyCandidates(const SubdivisionCandidateContainer &chosenCandidates,
|
---|
| 1271 | SubdivisionCandidateContainer &dirtyList)
|
---|
[1237] | 1272 | {
|
---|
[1625] | 1273 | SubdivisionCandidateContainer::const_iterator sit, sit_end = chosenCandidates.end();
|
---|
[1633] | 1274 | SubdivisionCandidate::NewMail();
|
---|
[1625] | 1275 |
|
---|
| 1276 | for (sit = chosenCandidates.begin(); sit != sit_end; ++ sit)
|
---|
| 1277 | {
|
---|
[1633] | 1278 | (*sit)->CollectDirtyCandidates(dirtyList, true);
|
---|
[1625] | 1279 | }
|
---|
| 1280 | }
|
---|
| 1281 |
|
---|
| 1282 |
|
---|
[1633] | 1283 | void HierarchyManager::RepairQueue(const SubdivisionCandidateContainer &dirtyList,
|
---|
| 1284 | SplitQueue &splitQueue,
|
---|
| 1285 | const bool recomputeSplitPlaneOnRepair)
|
---|
[1625] | 1286 | {
|
---|
[1237] | 1287 | // for each update of the view space partition:
|
---|
| 1288 | // the candidates from object space partition which
|
---|
| 1289 | // have been afected by the view space split (the kd split candidates
|
---|
| 1290 | // which saw the view cell which was split) must be reevaluated
|
---|
| 1291 | // (maybe not locally, just reinsert them into the queue)
|
---|
| 1292 | //
|
---|
| 1293 | // vice versa for the view cells
|
---|
| 1294 | // for each update of the object space partition
|
---|
| 1295 | // reevaluate split candidate for view cells which saw the split kd cell
|
---|
| 1296 | //
|
---|
| 1297 | // the priority queue update can be solved by implementing a binary heap
|
---|
| 1298 | // (explicit data structure, binary tree)
|
---|
| 1299 | // *) inserting and removal is efficient
|
---|
| 1300 | // *) search is not efficient => store queue position with each
|
---|
| 1301 | // split candidate
|
---|
| 1302 |
|
---|
| 1303 | // collect list of "dirty" candidates
|
---|
[1580] | 1304 | const long startTime = GetTime();
|
---|
[1625] | 1305 | if (0) cout << "repairing " << (int)dirtyList.size() << " candidates ... ";
|
---|
[1313] | 1306 |
|
---|
[1624] | 1307 |
|
---|
[1684] | 1308 | ///////////////////////////
|
---|
[1305] | 1309 | //-- reevaluate the dirty list
|
---|
[1415] | 1310 |
|
---|
[1313] | 1311 | SubdivisionCandidateContainer::const_iterator sit, sit_end = dirtyList.end();
|
---|
[1302] | 1312 |
|
---|
[1237] | 1313 | for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
|
---|
| 1314 | {
|
---|
| 1315 | SubdivisionCandidate* sc = *sit;
|
---|
[1305] | 1316 | const float rcd = sc->GetRenderCostDecrease();
|
---|
[1302] | 1317 |
|
---|
[1667] | 1318 | // erase from queue
|
---|
| 1319 | splitQueue.Erase(sc);
|
---|
| 1320 | // reevaluate candidate
|
---|
| 1321 | sc->EvalCandidate(recomputeSplitPlaneOnRepair);
|
---|
| 1322 | // reinsert
|
---|
| 1323 | splitQueue.Push(sc);
|
---|
| 1324 |
|
---|
| 1325 | cout << ".";
|
---|
| 1326 |
|
---|
[1580] | 1327 | #ifdef _DEBUG
|
---|
[1305] | 1328 | Debug << "candidate " << sc << " reevaluated\n"
|
---|
| 1329 | << "render cost decrease diff " << rcd - sc->GetRenderCostDecrease()
|
---|
[1580] | 1330 | << " old: " << rcd << " new " << sc->GetRenderCostDecrease() << endl;
|
---|
| 1331 | #endif
|
---|
[1237] | 1332 | }
|
---|
[1313] | 1333 |
|
---|
[1625] | 1334 | const long endTime = GetTime();
|
---|
| 1335 | const Real timeDiff = TimeDiff(startTime, endTime);
|
---|
| 1336 |
|
---|
[1624] | 1337 | mHierarchyStats.mRepairTime += timeDiff;
|
---|
[1313] | 1338 |
|
---|
[1633] | 1339 | if (0) cout << "repaired in " << timeDiff * 1e-3f << " secs" << endl;
|
---|
[1237] | 1340 | }
|
---|
| 1341 |
|
---|
[1259] | 1342 |
|
---|
[1640] | 1343 | void HierarchyManager::ResetQueue(SplitQueue &splitQueue, const bool recomputeSplitPlane)
|
---|
[1313] | 1344 | {
|
---|
| 1345 | SubdivisionCandidateContainer mCandidateBuffer;
|
---|
| 1346 |
|
---|
| 1347 | // remove from queue
|
---|
[1640] | 1348 | while (!splitQueue.Empty())
|
---|
[1313] | 1349 | {
|
---|
[1640] | 1350 | SubdivisionCandidate *candidate = NextSubdivisionCandidate(splitQueue);
|
---|
[1625] | 1351 | // reevaluate local split plane and priority
|
---|
[1667] | 1352 | candidate->EvalCandidate(recomputeSplitPlane);
|
---|
[1313] | 1353 | cout << ".";
|
---|
| 1354 | mCandidateBuffer.push_back(candidate);
|
---|
| 1355 | }
|
---|
| 1356 |
|
---|
| 1357 | // put back into queue
|
---|
| 1358 | SubdivisionCandidateContainer::const_iterator sit, sit_end = mCandidateBuffer.end();
|
---|
| 1359 | for (sit = mCandidateBuffer.begin(); sit != sit_end; ++ sit)
|
---|
[1580] | 1360 | {
|
---|
[1640] | 1361 | splitQueue.Push(*sit);
|
---|
[1313] | 1362 | }
|
---|
| 1363 | }
|
---|
| 1364 |
|
---|
| 1365 |
|
---|
[1279] | 1366 | void HierarchyManager::ExportObjectSpaceHierarchy(OUT_STREAM &stream)
|
---|
| 1367 | {
|
---|
| 1368 | // the type of the view cells hierarchy
|
---|
[1308] | 1369 | switch (mObjectSpaceSubdivisionType)
|
---|
[1279] | 1370 | {
|
---|
| 1371 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 1372 | stream << "<ObjectSpaceHierarchy type=\"osp\">" << endl;
|
---|
| 1373 | mOspTree->Export(stream);
|
---|
| 1374 | stream << endl << "</ObjectSpaceHierarchy>" << endl;
|
---|
[1305] | 1375 | break;
|
---|
[1279] | 1376 | case BV_BASED_OBJ_SUBDIV:
|
---|
| 1377 | stream << "<ObjectSpaceHierarchy type=\"bvh\">" << endl;
|
---|
| 1378 | mBvHierarchy->Export(stream);
|
---|
| 1379 | stream << endl << "</ObjectSpaceHierarchy>" << endl;
|
---|
| 1380 | break;
|
---|
| 1381 | }
|
---|
| 1382 | }
|
---|
| 1383 |
|
---|
| 1384 |
|
---|
| 1385 | bool HierarchyManager::AddSampleToPvs(Intersectable *obj,
|
---|
| 1386 | const Vector3 &hitPoint,
|
---|
| 1387 | ViewCell *vc,
|
---|
| 1388 | const float pdf,
|
---|
| 1389 | float &contribution) const
|
---|
| 1390 | {
|
---|
| 1391 | if (!obj) return false;
|
---|
| 1392 |
|
---|
[1308] | 1393 | switch (mObjectSpaceSubdivisionType)
|
---|
[1279] | 1394 | {
|
---|
| 1395 | case NO_OBJ_SUBDIV:
|
---|
[1486] | 1396 | {
|
---|
| 1397 | // potentially visible objects
|
---|
| 1398 | return vc->AddPvsSample(obj, pdf, contribution);
|
---|
| 1399 | }
|
---|
[1279] | 1400 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 1401 | {
|
---|
| 1402 | // potentially visible kd cells
|
---|
| 1403 | KdLeaf *leaf = mOspTree->GetLeaf(hitPoint/*ray->mOriginNode*/);
|
---|
| 1404 | return mOspTree->AddLeafToPvs(leaf, vc, pdf, contribution);
|
---|
| 1405 | }
|
---|
| 1406 | case BV_BASED_OBJ_SUBDIV:
|
---|
| 1407 | {
|
---|
| 1408 | BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
|
---|
[1370] | 1409 | BvhIntersectable *bvhObj = mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
|
---|
| 1410 |
|
---|
| 1411 | return vc->AddPvsSample(bvhObj, pdf, contribution);
|
---|
[1279] | 1412 | }
|
---|
| 1413 | default:
|
---|
| 1414 | return false;
|
---|
| 1415 | }
|
---|
| 1416 | }
|
---|
| 1417 |
|
---|
| 1418 |
|
---|
[1421] | 1419 | void HierarchyManager::PrintHierarchyStatistics(ostream &stream) const
|
---|
[1279] | 1420 | {
|
---|
[1313] | 1421 | stream << mHierarchyStats << endl;
|
---|
| 1422 | stream << "\nview space:" << endl << endl;
|
---|
| 1423 | stream << mVspTree->GetStatistics() << endl;
|
---|
| 1424 | stream << "\nobject space:" << endl << endl;
|
---|
[1370] | 1425 |
|
---|
[1308] | 1426 | switch (mObjectSpaceSubdivisionType)
|
---|
[1279] | 1427 | {
|
---|
| 1428 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 1429 | {
|
---|
[1313] | 1430 | stream << mOspTree->GetStatistics() << endl;
|
---|
[1279] | 1431 | break;
|
---|
| 1432 | }
|
---|
| 1433 | case BV_BASED_OBJ_SUBDIV:
|
---|
| 1434 | {
|
---|
[1313] | 1435 | stream << mBvHierarchy->GetStatistics() << endl;
|
---|
[1279] | 1436 | break;
|
---|
| 1437 | }
|
---|
| 1438 | default:
|
---|
| 1439 | break;
|
---|
| 1440 | }
|
---|
| 1441 | }
|
---|
| 1442 |
|
---|
| 1443 |
|
---|
[1287] | 1444 | void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
|
---|
[1416] | 1445 | const ObjectContainer &objects,
|
---|
[1418] | 1446 | const AxisAlignedBox3 *bbox,
|
---|
| 1447 | const bool exportBounds) const
|
---|
[1279] | 1448 | {
|
---|
[1308] | 1449 | switch (mObjectSpaceSubdivisionType)
|
---|
[1286] | 1450 | {
|
---|
| 1451 | case KD_BASED_OBJ_SUBDIV:
|
---|
[1279] | 1452 | {
|
---|
[1287] | 1453 | ExportOspTree(exporter, objects);
|
---|
[1286] | 1454 | break;
|
---|
| 1455 | }
|
---|
| 1456 | case BV_BASED_OBJ_SUBDIV:
|
---|
| 1457 | {
|
---|
[1418] | 1458 | exporter->ExportBvHierarchy(*mBvHierarchy, 0, bbox, exportBounds);
|
---|
[1286] | 1459 | break;
|
---|
| 1460 | }
|
---|
| 1461 | default:
|
---|
| 1462 | break;
|
---|
| 1463 | }
|
---|
| 1464 | }
|
---|
[1279] | 1465 |
|
---|
[1286] | 1466 |
|
---|
[1287] | 1467 | void HierarchyManager::ExportOspTree(Exporter *exporter,
|
---|
| 1468 | const ObjectContainer &objects) const
|
---|
[1286] | 1469 | {
|
---|
[1287] | 1470 | if (0) exporter->ExportGeometry(objects);
|
---|
[1279] | 1471 |
|
---|
[1287] | 1472 | exporter->SetWireframe();
|
---|
| 1473 | exporter->ExportOspTree(*mOspTree, 0);
|
---|
[1286] | 1474 | }
|
---|
| 1475 |
|
---|
| 1476 |
|
---|
[1418] | 1477 | Intersectable *HierarchyManager::GetIntersectable(const VssRay &ray,
|
---|
| 1478 | const bool isTermination) const
|
---|
| 1479 | {
|
---|
| 1480 |
|
---|
| 1481 | Intersectable *obj;
|
---|
| 1482 | Vector3 pt;
|
---|
| 1483 | KdNode *node;
|
---|
| 1484 |
|
---|
| 1485 | ray.GetSampleData(isTermination, pt, &obj, &node);
|
---|
| 1486 |
|
---|
| 1487 | if (!obj) return NULL;
|
---|
| 1488 |
|
---|
| 1489 | switch (mObjectSpaceSubdivisionType)
|
---|
| 1490 | {
|
---|
| 1491 | case HierarchyManager::KD_BASED_OBJ_SUBDIV:
|
---|
| 1492 | {
|
---|
| 1493 | KdLeaf *leaf = mOspTree->GetLeaf(pt, node);
|
---|
| 1494 | return mOspTree->GetOrCreateKdIntersectable(leaf);
|
---|
| 1495 | }
|
---|
| 1496 | case HierarchyManager::BV_BASED_OBJ_SUBDIV:
|
---|
| 1497 | {
|
---|
| 1498 | BvhLeaf *leaf = mBvHierarchy->GetLeaf(obj);
|
---|
| 1499 | return mBvHierarchy->GetOrCreateBvhIntersectable(leaf);
|
---|
| 1500 | }
|
---|
| 1501 | default:
|
---|
| 1502 | return obj;
|
---|
| 1503 | }
|
---|
| 1504 | }
|
---|
| 1505 |
|
---|
| 1506 |
|
---|
[1313] | 1507 | void HierarchyStatistics::Print(ostream &app) const
|
---|
| 1508 | {
|
---|
| 1509 | app << "=========== Hierarchy statistics ===============\n";
|
---|
| 1510 |
|
---|
| 1511 | app << setprecision(4);
|
---|
| 1512 |
|
---|
| 1513 | app << "#N_CTIME ( Construction time [s] )\n" << Time() << " \n";
|
---|
| 1514 |
|
---|
[1624] | 1515 | app << "#N_RTIME ( Repair time [s] )\n" << mRepairTime * 1e-3f << " \n";
|
---|
[1313] | 1516 |
|
---|
[1624] | 1517 | app << "#N_NODES ( Number of nodes )\n" << mNodes << "\n";
|
---|
[1313] | 1518 |
|
---|
| 1519 | app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
|
---|
| 1520 |
|
---|
| 1521 | app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
|
---|
| 1522 |
|
---|
[1624] | 1523 | app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << mMaxDepth << endl;
|
---|
[1449] | 1524 |
|
---|
| 1525 | app << "#N_GLOBALCOSTMISSES ( Global cost misses )\n" << mGlobalCostMisses << endl;
|
---|
[1313] | 1526 |
|
---|
| 1527 | app << "========== END OF Hierarchy statistics ==========\n";
|
---|
| 1528 | }
|
---|
| 1529 |
|
---|
| 1530 |
|
---|
[1418] | 1531 | static void RemoveRayRefs(const ObjectContainer &objects)
|
---|
[1370] | 1532 | {
|
---|
[1418] | 1533 | ObjectContainer::const_iterator oit, oit_end = objects.end();
|
---|
| 1534 | for (oit = objects.begin(); oit != oit_end; ++ oit)
|
---|
| 1535 | {
|
---|
[1696] | 1536 | (*oit)->DelRayRefs();
|
---|
[1418] | 1537 | }
|
---|
| 1538 | }
|
---|
| 1539 |
|
---|
| 1540 |
|
---|
[1679] | 1541 | void HierarchyManager::FinishObjectSpaceSubdivision(const ObjectContainer &objects,
|
---|
| 1542 | const bool removeRayRefs) const
|
---|
[1418] | 1543 | {
|
---|
[1370] | 1544 | switch (mObjectSpaceSubdivisionType)
|
---|
| 1545 | {
|
---|
| 1546 | case KD_BASED_OBJ_SUBDIV:
|
---|
| 1547 | {
|
---|
| 1548 | mOspTree->mOspStats.Stop();
|
---|
| 1549 | break;
|
---|
| 1550 | }
|
---|
| 1551 | case BV_BASED_OBJ_SUBDIV:
|
---|
| 1552 | {
|
---|
| 1553 | mBvHierarchy->mBvhStats.Stop();
|
---|
[1649] | 1554 | if (removeRayRefs)
|
---|
| 1555 | RemoveRayRefs(objects);
|
---|
[1370] | 1556 | break;
|
---|
| 1557 | }
|
---|
| 1558 | default:
|
---|
| 1559 | break;
|
---|
| 1560 | }
|
---|
| 1561 | }
|
---|
| 1562 |
|
---|
[1614] | 1563 |
|
---|
| 1564 | void HierarchyManager::ExportBoundingBoxes(OUT_STREAM &stream, const ObjectContainer &objects)
|
---|
| 1565 | {
|
---|
| 1566 | stream << "<BoundingBoxes>" << endl;
|
---|
| 1567 |
|
---|
| 1568 | if (mObjectSpaceSubdivisionType == KD_BASED_OBJ_SUBDIV)
|
---|
| 1569 | {
|
---|
| 1570 | KdIntersectableMap::const_iterator kit, kit_end = mOspTree->mKdIntersectables.end();
|
---|
| 1571 |
|
---|
| 1572 | int id = 0;
|
---|
| 1573 | for (kit = mOspTree->mKdIntersectables.begin(); kit != kit_end; ++ kit, ++ id)
|
---|
| 1574 | {
|
---|
| 1575 | Intersectable *obj = (*kit).second;
|
---|
| 1576 | const AxisAlignedBox3 box = obj->GetBox();
|
---|
| 1577 |
|
---|
| 1578 | obj->SetId(id);
|
---|
| 1579 |
|
---|
| 1580 | stream << "<BoundingBox" << " id=\"" << id << "\""
|
---|
| 1581 | << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
|
---|
| 1582 | << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
|
---|
| 1583 | }
|
---|
| 1584 | }
|
---|
| 1585 | else
|
---|
| 1586 | {
|
---|
| 1587 | ObjectContainer::const_iterator oit, oit_end = objects.end();
|
---|
| 1588 |
|
---|
| 1589 | for (oit = objects.begin(); oit != oit_end; ++ oit)
|
---|
| 1590 | {
|
---|
| 1591 | const AxisAlignedBox3 box = (*oit)->GetBox();
|
---|
| 1592 |
|
---|
| 1593 | stream << "<BoundingBox" << " id=\"" << (*oit)->GetId() << "\""
|
---|
| 1594 | << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
|
---|
| 1595 | << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\" />" << endl;
|
---|
| 1596 | }
|
---|
| 1597 | }
|
---|
| 1598 |
|
---|
| 1599 | stream << "</BoundingBoxes>" << endl;
|
---|
| 1600 | }
|
---|
| 1601 |
|
---|
[1680] | 1602 | /*typedef priority_queue<ViewCell *, vector<ViewCell *>,
|
---|
| 1603 | myless<vector<ViewCell *>::value_type> > ViewCellsQueue;
|
---|
| 1604 |
|
---|
| 1605 | typedef priority_queue<BvhNode *, vector<BvhNode *>,
|
---|
| 1606 | myless<vector<BvhNode *>::value_type> > BvhQueue;
|
---|
| 1607 |
|
---|
| 1608 | typedef priority_queue<VspNode *, vector<VspNode *>,
|
---|
| 1609 | myless<vector<VspNode *>::value_type> > VspQueue;
|
---|
| 1610 | */
|
---|
| 1611 | static void UpdateStats(ofstream &stats,
|
---|
| 1612 | const int splits,
|
---|
| 1613 | const float totalRenderCost,
|
---|
| 1614 | const int entriesInPvs,
|
---|
| 1615 | const float memoryCost,
|
---|
| 1616 | const bool vsp)
|
---|
| 1617 | {
|
---|
| 1618 | stats << "#Pass\n" << 0 << endl
|
---|
| 1619 | << "#Splits\n" << splits << endl
|
---|
| 1620 | << "#TotalRenderCost\n" << totalRenderCost << endl
|
---|
| 1621 | << "#TotalEntriesInPvs\n" << entriesInPvs << endl
|
---|
| 1622 | << "#Memory\n" << memoryCost << endl
|
---|
| 1623 | << "#Vsp\n" << (vsp ? 1 : 0) << endl
|
---|
| 1624 | << endl;
|
---|
| 1625 | }
|
---|
| 1626 |
|
---|
| 1627 |
|
---|
[1692] | 1628 | void HierarchyManager::EvaluateSubdivision(const VssRayContainer &sampleRays,
|
---|
| 1629 | const ObjectContainer &objects,
|
---|
[1686] | 1630 | const string &filename)
|
---|
[1680] | 1631 | {
|
---|
| 1632 | VspTree *oldVspTree = mVspTree;
|
---|
[1686] | 1633 | ViewCellsManager *vm = mVspTree->mViewCellsManager;
|
---|
[1684] | 1634 | BvHierarchy *oldHierarchy = mBvHierarchy;
|
---|
[1680] | 1635 |
|
---|
[1684] | 1636 | mBvHierarchy = new BvHierarchy();
|
---|
| 1637 | mBvHierarchy->mHierarchyManager = this;
|
---|
[1686] | 1638 | mBvHierarchy->mViewCellsManager = vm;
|
---|
| 1639 |
|
---|
[1680] | 1640 | mVspTree = new VspTree();
|
---|
| 1641 | mVspTree->mHierarchyManager = this;
|
---|
[1686] | 1642 | mVspTree->mViewCellsManager = vm;
|
---|
[1680] | 1643 |
|
---|
| 1644 | // create first nodes
|
---|
| 1645 | mVspTree->Initialise(sampleRays, &oldVspTree->mBoundingBox);
|
---|
| 1646 | InitialiseObjectSpaceSubdivision(objects);
|
---|
| 1647 |
|
---|
[1686] | 1648 | const long startTime = GetTime();
|
---|
| 1649 | cout << "Constructing evaluation hierarchies ... \n";
|
---|
| 1650 |
|
---|
| 1651 | ofstream stats;
|
---|
| 1652 | stats.open(filename.c_str());
|
---|
| 1653 | SplitQueue tQueue;
|
---|
[1680] | 1654 |
|
---|
[1686] | 1655 | BvhNode *oldBvhRoot = oldHierarchy->GetRoot();
|
---|
| 1656 | VspNode *oldVspRoot = oldVspTree->GetRoot();
|
---|
[1680] | 1657 |
|
---|
[1686] | 1658 | RayInfoContainer *viewSpaceRays = new RayInfoContainer();
|
---|
[1680] | 1659 |
|
---|
[1686] | 1660 | SubdivisionCandidate *firstVsp = mVspTree->PrepareConstruction(sampleRays, *viewSpaceRays);
|
---|
| 1661 | SubdivisionCandidate *firstBvh = mBvHierarchy->PrepareConstruction(sampleRays, objects);
|
---|
[1680] | 1662 |
|
---|
[1686] | 1663 | firstVsp->mEvaluationHack = oldVspRoot;
|
---|
| 1664 | firstBvh->mEvaluationHack = oldBvhRoot;
|
---|
[1680] | 1665 |
|
---|
[1687] | 1666 | firstVsp->SetPriority((float)-oldVspRoot->mTimeStamp);
|
---|
| 1667 | firstBvh->SetPriority((float)-oldBvhRoot->mTimeStamp);
|
---|
| 1668 |
|
---|
[1686] | 1669 | tQueue.Push(firstVsp);
|
---|
| 1670 | tQueue.Push(firstBvh);
|
---|
[1680] | 1671 |
|
---|
[1686] | 1672 | ExportStats(stats, tQueue, objects);
|
---|
[1680] | 1673 |
|
---|
[1686] | 1674 | cout << "\nfinished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
|
---|
| 1675 | RemoveRayRefs(objects);
|
---|
[1680] | 1676 |
|
---|
[1686] | 1677 | // view cells needed only for evaluation
|
---|
| 1678 | ViewCellContainer viewCells;
|
---|
| 1679 | mVspTree->CollectViewCells(viewCells, false);
|
---|
[1692] | 1680 |
|
---|
[1686] | 1681 | // helper trees can be destroyed
|
---|
| 1682 | DEL_PTR(mVspTree);
|
---|
| 1683 | DEL_PTR(mBvHierarchy);
|
---|
[1684] | 1684 |
|
---|
[1692] | 1685 | CLEAR_CONTAINER(viewCells);
|
---|
| 1686 |
|
---|
[1686] | 1687 | // reset hierarchies
|
---|
| 1688 | mVspTree = oldVspTree;
|
---|
| 1689 | mBvHierarchy = oldHierarchy;
|
---|
[1684] | 1690 |
|
---|
[1686] | 1691 | // reinstall old bv refs
|
---|
| 1692 | vector<BvhLeaf *> leaves;
|
---|
| 1693 | mBvHierarchy->CollectLeaves(leaves);
|
---|
| 1694 | vector<BvhLeaf *>::const_iterator bit, bit_end = leaves.end();
|
---|
[1680] | 1695 |
|
---|
[1686] | 1696 | for (bit = leaves.begin(); bit != bit_end; ++ bit)
|
---|
| 1697 | {
|
---|
| 1698 | mBvHierarchy->AssociateObjectsWithLeaf(*bit);
|
---|
| 1699 | }
|
---|
| 1700 | }
|
---|
[1680] | 1701 |
|
---|
[1686] | 1702 |
|
---|
| 1703 | void HierarchyManager::ExportStats(ofstream &stats,
|
---|
| 1704 | SplitQueue &tQueue,
|
---|
| 1705 | const ObjectContainer &objects)
|
---|
| 1706 | {
|
---|
| 1707 | float totalRenderCost = (float)objects.size();
|
---|
| 1708 | int entriesInPvs = 1;
|
---|
| 1709 | int steps = 0;
|
---|
| 1710 |
|
---|
[1680] | 1711 | cout << "exporting vsposp stats ... " << endl;
|
---|
| 1712 | const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
|
---|
| 1713 |
|
---|
| 1714 | /////////////
|
---|
| 1715 | //-- first view cell
|
---|
[1684] | 1716 | UpdateStats(stats, 2, totalRenderCost, entriesInPvs, memoryCost, true);
|
---|
[1680] | 1717 |
|
---|
| 1718 | //-- go through tree in the order of render cost decrease
|
---|
| 1719 | //-- which is the same order as the view cells were merged
|
---|
| 1720 | //-- or the reverse order of subdivision for subdivision-only
|
---|
| 1721 | //-- view cell hierarchies.
|
---|
[1686] | 1722 |
|
---|
[1684] | 1723 | while (!tQueue.Empty())
|
---|
| 1724 | {
|
---|
| 1725 | SubdivisionCandidate *nextCandidate = NextSubdivisionCandidate(tQueue);
|
---|
[1692] | 1726 | bool isLeaf;
|
---|
| 1727 | int timeStamp;
|
---|
| 1728 | float rcDecr;
|
---|
| 1729 | int entriesIncr;
|
---|
[1684] | 1730 |
|
---|
[1687] | 1731 | if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
|
---|
| 1732 | {
|
---|
[1692] | 1733 | timeStamp = (int)-nextCandidate->GetPriority();
|
---|
[1687] | 1734 |
|
---|
[1692] | 1735 | VspNode *newNode = mVspTree->SubdivideAndCopy(tQueue, nextCandidate);
|
---|
[1687] | 1736 | VspNode *oldNode = (VspNode *)nextCandidate->mEvaluationHack;
|
---|
| 1737 |
|
---|
[1692] | 1738 | isLeaf = newNode->IsLeaf();
|
---|
| 1739 | rcDecr = oldNode->mRenderCostDecr;
|
---|
| 1740 | entriesIncr = oldNode->mPvsEntriesIncr;
|
---|
[1687] | 1741 | }
|
---|
[1686] | 1742 | else
|
---|
[1692] | 1743 | {
|
---|
| 1744 | timeStamp = (int)-nextCandidate->GetPriority();
|
---|
[1687] | 1745 |
|
---|
[1692] | 1746 | BvhNode *newNode = mBvHierarchy->SubdivideAndCopy(tQueue, nextCandidate);
|
---|
[1687] | 1747 | BvhNode *oldNode = (BvhNode *)nextCandidate->mEvaluationHack;
|
---|
| 1748 |
|
---|
[1692] | 1749 | isLeaf = newNode->IsLeaf();
|
---|
| 1750 | rcDecr = oldNode->mRenderCostDecr;
|
---|
| 1751 | entriesIncr = oldNode->mPvsEntriesIncr;
|
---|
[1687] | 1752 | }
|
---|
[1692] | 1753 |
|
---|
| 1754 | if (!isLeaf)
|
---|
| 1755 | {
|
---|
| 1756 | totalRenderCost -= rcDecr;
|
---|
| 1757 | entriesInPvs += entriesIncr;
|
---|
| 1758 | // if (rcDecr <= 0)
|
---|
| 1759 | if (nextCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
|
---|
| 1760 | cout << "v";//cout << "vsp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
|
---|
| 1761 | else
|
---|
| 1762 | cout << "o";//"osp t: " << timeStamp << " rc: " << rcDecr << " pvs: " << entriesIncr << endl;
|
---|
[1686] | 1763 |
|
---|
[1692] | 1764 | ++ steps;
|
---|
[1684] | 1765 |
|
---|
[1692] | 1766 | if ((steps % 500) == 499)
|
---|
| 1767 | cout << steps << " steps taken" << endl;
|
---|
| 1768 | const float memoryCost = (float)entriesInPvs * (float)ObjectPvs::GetEntrySize();
|
---|
| 1769 | UpdateStats(stats, steps, totalRenderCost, entriesInPvs, memoryCost, false);
|
---|
| 1770 | }
|
---|
| 1771 |
|
---|
| 1772 | DEL_PTR(nextCandidate);
|
---|
[1684] | 1773 | }
|
---|
[1686] | 1774 |
|
---|
[1684] | 1775 | stats.close();
|
---|
| 1776 | }
|
---|
| 1777 |
|
---|
[1686] | 1778 |
|
---|
[1237] | 1779 | } |
---|