[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"
|
---|
| 19 | #include "KdIntersectable.h"
|
---|
| 20 | #include "VspTree.h"
|
---|
| 21 | #include "OspTree.h"
|
---|
| 22 |
|
---|
| 23 |
|
---|
| 24 | namespace GtpVisibilityPreprocessor {
|
---|
| 25 |
|
---|
| 26 |
|
---|
| 27 | #define USE_FIXEDPOINT_T 0
|
---|
| 28 |
|
---|
| 29 |
|
---|
| 30 | /*******************************************************************/
|
---|
| 31 | /* class HierarchyManager implementation */
|
---|
| 32 | /*******************************************************************/
|
---|
| 33 |
|
---|
| 34 |
|
---|
| 35 | HierarchyManager::HierarchyManager(VspTree &vspTree, OspTree &ospTree):
|
---|
| 36 | mVspTree(vspTree), mOspTree(ospTree)
|
---|
| 37 | {
|
---|
| 38 | // cross references
|
---|
| 39 | mVspTree.mOspTree = &ospTree;
|
---|
| 40 | mOspTree.mVspTree = &vspTree;
|
---|
| 41 |
|
---|
| 42 | char subdivisionStatsLog[100];
|
---|
| 43 | Environment::GetSingleton()->GetStringValue("Hierarchy.subdivisionStats",
|
---|
| 44 | subdivisionStatsLog);
|
---|
| 45 | mSubdivisionStats.open(subdivisionStatsLog);
|
---|
| 46 | }
|
---|
| 47 |
|
---|
| 48 |
|
---|
| 49 | SubdivisionCandidate *HierarchyManager::NextSubdivisionCandidate()
|
---|
| 50 | {
|
---|
| 51 | SubdivisionCandidate *splitCandidate = mTQueue.Top();
|
---|
| 52 | mTQueue.Pop();
|
---|
| 53 |
|
---|
| 54 | return splitCandidate;
|
---|
| 55 | }
|
---|
| 56 |
|
---|
| 57 |
|
---|
| 58 | void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
|
---|
| 59 | const ObjectContainer &objects,
|
---|
| 60 | AxisAlignedBox3 *forcedViewSpace,
|
---|
| 61 | RayInfoContainer &viewSpaceRays,
|
---|
| 62 | RayInfoContainer &objectSpaceRays)
|
---|
| 63 | {
|
---|
| 64 | SubdivisionCandidate *vsc =
|
---|
| 65 | mVspTree.PrepareConstruction(sampleRays, forcedViewSpace, viewSpaceRays);
|
---|
| 66 | mTQueue.Push(vsc);
|
---|
| 67 |
|
---|
| 68 | SubdivisionCandidate *osc =
|
---|
| 69 | mOspTree.PrepareConstruction(sampleRays, objects, forcedViewSpace, objectSpaceRays);
|
---|
| 70 |
|
---|
| 71 | mTQueue.Push(osc);
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 |
|
---|
| 75 | void HierarchyManager::EvalSubdivisionStats(const SubdivisionCandidate &tData)
|
---|
| 76 | {
|
---|
| 77 | const float costDecr = tData.GetRenderCostDecrease();
|
---|
| 78 |
|
---|
| 79 | //mTotalCost -= costDecr;
|
---|
| 80 | // mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
|
---|
| 81 |
|
---|
| 82 | AddSubdivisionStats(mOspTree.mOspStats.Leaves() + mVspTree.mVspStats.Leaves(),
|
---|
| 83 | costDecr,
|
---|
| 84 | mTotalCost
|
---|
| 85 | );
|
---|
| 86 | }
|
---|
| 87 |
|
---|
| 88 |
|
---|
| 89 | void HierarchyManager::AddSubdivisionStats(const int splits,
|
---|
| 90 | const float renderCostDecr,
|
---|
| 91 | const float totalRenderCost)
|
---|
| 92 | {
|
---|
| 93 | mSubdivisionStats
|
---|
| 94 | << "#Splits\n" << splits << endl
|
---|
| 95 | << "#RenderCostDecrease\n" << renderCostDecr << endl
|
---|
| 96 | << "#TotalRenderCost\n" << totalRenderCost << endl;
|
---|
| 97 | //<< "#AvgRenderCost\n" << avgRenderCost << endl;
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 |
|
---|
| 101 | bool HierarchyManager::GlobalTerminationCriteriaMet(SubdivisionCandidate *candidate) const
|
---|
| 102 | {
|
---|
| 103 | // TODO matt: make virtual by creating superclasss for traveral data
|
---|
| 104 | return candidate->GlobalTerminationCriteriaMet();
|
---|
| 105 | }
|
---|
| 106 |
|
---|
| 107 |
|
---|
| 108 | void HierarchyManager::Construct(const VssRayContainer &sampleRays,
|
---|
| 109 | const ObjectContainer &objects,
|
---|
| 110 | AxisAlignedBox3 *forcedViewSpace)
|
---|
| 111 | {
|
---|
| 112 | RayInfoContainer *objectSpaceRays = new RayInfoContainer();
|
---|
| 113 | RayInfoContainer *viewSpaceRays = new RayInfoContainer();
|
---|
| 114 |
|
---|
| 115 | // prepare vsp and osp trees for traversal
|
---|
| 116 | PrepareConstruction(sampleRays, objects, forcedViewSpace, *viewSpaceRays, *objectSpaceRays);
|
---|
| 117 |
|
---|
| 118 | mVspTree.mVspStats.Reset();
|
---|
| 119 | mVspTree.mVspStats.Start();
|
---|
| 120 |
|
---|
| 121 | cout << "Constructing view space / object space tree ... \n";
|
---|
| 122 | const long startTime = GetTime();
|
---|
| 123 |
|
---|
| 124 | RunConstruction(true);
|
---|
| 125 |
|
---|
| 126 | cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
|
---|
| 127 |
|
---|
| 128 | mVspTree.mVspStats.Stop();
|
---|
| 129 | }
|
---|
| 130 |
|
---|
| 131 |
|
---|
| 132 | bool HierarchyManager::SubdivideSubdivisionCandidate(SubdivisionCandidate *sc)
|
---|
| 133 | {
|
---|
| 134 | const bool globalTerminationCriteriaMet =
|
---|
| 135 | GlobalTerminationCriteriaMet(sc);
|
---|
| 136 |
|
---|
| 137 | const bool vspSplit = (sc->Type() == SubdivisionCandidate::VIEW_SPACE);
|
---|
| 138 |
|
---|
| 139 | if (vspSplit)
|
---|
| 140 | {
|
---|
| 141 | VspNode *n = mVspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
|
---|
| 142 | }
|
---|
| 143 | else
|
---|
| 144 | {
|
---|
| 145 | KdNode *n = mOspTree.Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
|
---|
| 146 | }
|
---|
| 147 |
|
---|
| 148 | return !globalTerminationCriteriaMet;
|
---|
| 149 | }
|
---|
| 150 |
|
---|
| 151 |
|
---|
| 152 | void HierarchyManager::RunConstruction(const bool repair)
|
---|
| 153 | {
|
---|
| 154 | int numNodes = 0;
|
---|
| 155 |
|
---|
| 156 | while (!FinishedConstruction())
|
---|
| 157 | {
|
---|
| 158 | SubdivisionCandidate *splitCandidate = NextSubdivisionCandidate();
|
---|
| 159 |
|
---|
| 160 | mTotalCost -= splitCandidate->GetRenderCostDecrease();
|
---|
| 161 |
|
---|
| 162 | // cost ratio of cost decrease / totalCost
|
---|
| 163 | const float costRatio = splitCandidate->GetRenderCostDecrease() / mTotalCost;
|
---|
| 164 |
|
---|
| 165 | if (costRatio < mTermMinGlobalCostRatio)
|
---|
| 166 | ++ mGlobalCostMisses;
|
---|
| 167 |
|
---|
| 168 | /*Debug << "\n**********" << endl
|
---|
| 169 | << "total cost: " << mTotalCost << " render cost decr: "
|
---|
| 170 | << splitCandidate->GetRenderCostDecrease()
|
---|
| 171 | << " cost ratio: " << costRatio << endl << endl;*/
|
---|
| 172 |
|
---|
| 173 | //-- subdivide leaf node
|
---|
| 174 |
|
---|
| 175 | if (SubdivideSubdivisionCandidate(splitCandidate))
|
---|
| 176 | {
|
---|
| 177 | // subdivision successful
|
---|
| 178 | EvalSubdivisionStats(*splitCandidate);
|
---|
| 179 |
|
---|
| 180 | // reevaluate candidates affected by the split
|
---|
| 181 | // for view space splits, this would be object space splits
|
---|
| 182 | // and other way round
|
---|
| 183 | if (repair)
|
---|
| 184 | RepairQueue();
|
---|
| 185 |
|
---|
| 186 | cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
|
---|
| 187 | }
|
---|
| 188 |
|
---|
| 189 | DEL_PTR(splitCandidate);
|
---|
| 190 | }
|
---|
| 191 | }
|
---|
| 192 |
|
---|
| 193 |
|
---|
| 194 | void HierarchyManager::Construct2(const VssRayContainer &sampleRays,
|
---|
| 195 | const ObjectContainer &objects,
|
---|
| 196 | AxisAlignedBox3 *forcedViewSpace)
|
---|
| 197 | {
|
---|
| 198 | // rays clipped in view space and in object space
|
---|
| 199 | RayInfoContainer *viewSpaceRays = new RayInfoContainer();
|
---|
| 200 | RayInfoContainer *objectSpaceRays = new RayInfoContainer();
|
---|
| 201 |
|
---|
| 202 |
|
---|
| 203 | /////////////////////////////////////////////////////////////
|
---|
| 204 | // view space space partition
|
---|
| 205 | /////////////////////////////////////////////////////////////
|
---|
| 206 |
|
---|
| 207 | #if 0
|
---|
| 208 | // makes no sense otherwise because only one kd cell available
|
---|
| 209 | // during view space partition
|
---|
| 210 | const bool savedCountMethod = mVspTree.mUseKdPvsForHeuristics;
|
---|
| 211 | const bool savedStoreMethod = mVspTree.mStoreKdPvs;
|
---|
| 212 |
|
---|
| 213 | mVspTree.mUseKdPvsForHeuristics = false;
|
---|
| 214 | mVspTree.mStoreKdPvs = false;
|
---|
| 215 | #endif
|
---|
| 216 |
|
---|
| 217 | SubdivisionCandidate *vsc =
|
---|
| 218 | mVspTree.PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
|
---|
| 219 |
|
---|
| 220 | // add to queue
|
---|
| 221 | mTQueue.Push(vsc);
|
---|
| 222 |
|
---|
| 223 | long startTime = GetTime();
|
---|
| 224 | cout << "starting vsp contruction ... " << endl;
|
---|
| 225 |
|
---|
| 226 | mVspTree.mVspStats.Reset();
|
---|
| 227 | mVspTree.mVspStats.Start();
|
---|
| 228 |
|
---|
| 229 | int i = 0;
|
---|
| 230 |
|
---|
| 231 | // all objects can be seen from everywhere
|
---|
| 232 | mTotalCost = (float)dynamic_cast<VspTree::VspSubdivisionCandidate *>(vsc)->mParentData.mPvs;
|
---|
| 233 |
|
---|
| 234 | const bool repairQueue = false;
|
---|
| 235 |
|
---|
| 236 | // process view space candidates
|
---|
| 237 | RunConstruction(repairQueue);
|
---|
| 238 |
|
---|
| 239 | cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
|
---|
| 240 | mVspTree.mVspStats.Stop();
|
---|
| 241 |
|
---|
| 242 |
|
---|
| 243 |
|
---|
| 244 | /////////////////////////////////////////////////////////////
|
---|
| 245 | // object space partition
|
---|
| 246 | /////////////////////////////////////////////////////////////
|
---|
| 247 |
|
---|
| 248 |
|
---|
| 249 | Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
|
---|
| 250 | cout << "starting osp contruction ... " << endl;
|
---|
| 251 |
|
---|
| 252 | // start with one big kd cell - all objects can be seen from everywhere
|
---|
| 253 | // note: only true for view space = object space
|
---|
| 254 |
|
---|
| 255 | // compute first candidate
|
---|
| 256 | SubdivisionCandidate *osc =
|
---|
| 257 | mOspTree.PrepareConstruction(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
|
---|
| 258 |
|
---|
| 259 | Debug << "reseting cost, new total cost: " << mTotalCost << endl;
|
---|
| 260 | mTotalCost = mOspTree.mTotalCost;
|
---|
| 261 |
|
---|
| 262 | mTQueue.Push(osc);
|
---|
| 263 |
|
---|
| 264 | mOspTree.mOspStats.Reset();
|
---|
| 265 | mOspTree.mOspStats.Start();
|
---|
| 266 |
|
---|
| 267 | startTime = GetTime();
|
---|
| 268 |
|
---|
| 269 | // process object space candidates
|
---|
| 270 | RunConstruction(repairQueue);
|
---|
| 271 |
|
---|
| 272 | cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
|
---|
| 273 |
|
---|
| 274 | mOspTree.mOspStats.Stop();
|
---|
| 275 |
|
---|
| 276 | float rc = mOspTree.EvalRenderCost(sampleRays);
|
---|
| 277 |
|
---|
| 278 | Debug << "here47 My render cost evalulation: " << rc << endl;
|
---|
| 279 |
|
---|
| 280 | #if 0
|
---|
| 281 | // reset parameters
|
---|
| 282 | mVspTree.mUseKdPvsForHeuristics = savedCountMethod;
|
---|
| 283 | mVspTree.mStoreKdPvs = savedStoreMethod;
|
---|
| 284 | #endif
|
---|
| 285 | }
|
---|
| 286 |
|
---|
| 287 |
|
---|
| 288 | void HierarchyManager::Construct3(const VssRayContainer &sampleRays,
|
---|
| 289 | const ObjectContainer &objects,
|
---|
| 290 | AxisAlignedBox3 *forcedViewSpace)
|
---|
| 291 | {
|
---|
| 292 | // only view space partition
|
---|
| 293 | // object kd tree is taken for osp
|
---|
| 294 |
|
---|
| 295 | mVspTree.mVspStats.Reset();
|
---|
| 296 | mVspTree.mVspStats.Start();
|
---|
| 297 |
|
---|
| 298 | RayInfoContainer *viewSpaceRays = new RayInfoContainer();
|
---|
| 299 |
|
---|
| 300 | SubdivisionCandidate *sc =
|
---|
| 301 | mVspTree.PrepareConstruction(sampleRays, forcedViewSpace, *viewSpaceRays);
|
---|
| 302 |
|
---|
| 303 | mTQueue.Push(sc);
|
---|
| 304 |
|
---|
| 305 | cout << "starting vsp contruction ... " << endl;
|
---|
| 306 |
|
---|
| 307 | long startTime = GetTime();
|
---|
| 308 |
|
---|
| 309 | RunConstruction(false);
|
---|
| 310 |
|
---|
| 311 | cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
|
---|
| 312 | mVspTree.mVspStats.Stop();
|
---|
| 313 | }
|
---|
| 314 |
|
---|
| 315 |
|
---|
| 316 | bool HierarchyManager::FinishedConstruction() const
|
---|
| 317 | {
|
---|
| 318 | return mTQueue.Empty();
|
---|
| 319 | }
|
---|
| 320 |
|
---|
| 321 |
|
---|
| 322 | void HierarchyManager::CollectDirtyCandidates(vector<SubdivisionCandidate *> &dirtyList)
|
---|
| 323 | {
|
---|
| 324 | // we have either a object space or view space split
|
---|
| 325 | if (mCurrentCandidate->Type() == SubdivisionCandidate::VIEW_SPACE)
|
---|
| 326 | {
|
---|
| 327 | VspTree::VspSubdivisionCandidate *sc =
|
---|
| 328 | dynamic_cast<VspTree::VspSubdivisionCandidate *>(mCurrentCandidate);
|
---|
| 329 |
|
---|
| 330 | mVspTree.CollectDirtyCandidates(sc, dirtyList);
|
---|
| 331 | }
|
---|
| 332 | else // object space split
|
---|
| 333 | {
|
---|
| 334 | OspTree::OspSubdivisionCandidate *sc =
|
---|
| 335 | dynamic_cast<OspTree::OspSubdivisionCandidate *>(mCurrentCandidate);
|
---|
| 336 |
|
---|
| 337 | mOspTree.CollectDirtyCandidates(sc, dirtyList);
|
---|
| 338 | }
|
---|
| 339 | }
|
---|
| 340 |
|
---|
| 341 |
|
---|
| 342 | void HierarchyManager::RepairQueue()
|
---|
| 343 | {
|
---|
| 344 | // TODO
|
---|
| 345 | // for each update of the view space partition:
|
---|
| 346 | // the candidates from object space partition which
|
---|
| 347 | // have been afected by the view space split (the kd split candidates
|
---|
| 348 | // which saw the view cell which was split) must be reevaluated
|
---|
| 349 | // (maybe not locally, just reinsert them into the queue)
|
---|
| 350 | //
|
---|
| 351 | // vice versa for the view cells
|
---|
| 352 | // for each update of the object space partition
|
---|
| 353 | // reevaluate split candidate for view cells which saw the split kd cell
|
---|
| 354 | //
|
---|
| 355 | // the priority queue update can be solved by implementing a binary heap
|
---|
| 356 | // (explicit data structure, binary tree)
|
---|
| 357 | // *) inserting and removal is efficient
|
---|
| 358 | // *) search is not efficient => store queue position with each
|
---|
| 359 | // split candidate
|
---|
| 360 |
|
---|
| 361 | // collect list of "dirty" candidates
|
---|
| 362 | vector<SubdivisionCandidate *> dirtyList;
|
---|
| 363 | CollectDirtyCandidates(dirtyList);
|
---|
| 364 |
|
---|
| 365 | //-- reevaluate the dirty list
|
---|
| 366 | vector<SubdivisionCandidate *>::const_iterator sit, sit_end = dirtyList.end();
|
---|
| 367 |
|
---|
| 368 | for (sit = dirtyList.begin(); sit != sit_end; ++ sit)
|
---|
| 369 | {
|
---|
| 370 | SubdivisionCandidate* sc = *sit;
|
---|
| 371 |
|
---|
| 372 | mTQueue.Erase(sc);
|
---|
| 373 |
|
---|
| 374 | // reevaluate
|
---|
| 375 | sc->EvalPriority();
|
---|
| 376 |
|
---|
| 377 | // reinsert
|
---|
| 378 | mTQueue.Push(sc);
|
---|
| 379 | }
|
---|
| 380 | }
|
---|
| 381 |
|
---|
| 382 | } |
---|