source: GTP/trunk/Lib/Vis/Preprocessing/src/VspOspTree.cpp @ 1020

Revision 1020, 56.6 KB checked in by mattausch, 18 years ago (diff)

worked on view-object space partition
fixed some loading bugs
fixeds some exporting bugs using line segments
enabling other methods for view space sampling in ViewCellsManager? OBJECT_DIRECTION_BASED_DISTRIBUTION)
added class interface for a sampling strategy
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "ViewCell.h"
6#include "Plane3.h"
7#include "VspOspTree.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
20
21namespace GtpVisibilityPreprocessor {
22
23#define USE_FIXEDPOINT_T 0
24
25
26//-- static members
27
28int VspTree::sFrontId = 0;
29int VspTree::sBackId = 0;
30int VspTree::sFrontAndBackId = 0;
31
32
33
34// pvs penalty can be different from pvs size
35inline static float EvalPvsPenalty(const int pvs,
36                                                                   const int lower,
37                                                                   const int upper)
38{
39        // clamp to minmax values
40        if (pvs < lower)
41                return (float)lower;
42        if (pvs > upper)
43                return (float)upper;
44
45        return (float)pvs;
46}
47
48
49int VspNode::sMailId = 1;
50
51
52/******************************************************************/
53/*                  class VspNode implementation                  */
54/******************************************************************/
55
56
57VspNode::VspNode():
58mParent(NULL), mTreeValid(true), mTimeStamp(0)
59{}
60
61
62VspNode::VspNode(VspInterior *parent):
63mParent(parent), mTreeValid(true)
64{}
65
66
67bool VspNode::IsRoot() const
68{
69        return mParent == NULL;
70}
71
72
73VspInterior *VspNode::GetParent()
74{
75        return mParent;
76}
77
78
79void VspNode::SetParent(VspInterior *parent)
80{
81        mParent = parent;
82}
83
84
85bool VspNode::IsSibling(VspNode *n) const
86{
87        return  ((this != n) && mParent &&
88                         (mParent->GetFront() == n) || (mParent->GetBack() == n));
89}
90
91
92int VspNode::GetDepth() const
93{
94        int depth = 0;
95        VspNode *p = mParent;
96       
97        while (p)
98        {
99                p = p->mParent;
100                ++ depth;
101        }
102
103        return depth;
104}
105
106
107bool VspNode::TreeValid() const
108{
109        return mTreeValid;
110}
111
112
113void VspNode::SetTreeValid(const bool v)
114{
115        mTreeValid = v;
116}
117
118
119/****************************************************************/
120/*              class VspInterior implementation                */
121/****************************************************************/
122
123
124VspInterior::VspInterior(const AxisAlignedPlane &plane):
125mPlane(plane), mFront(NULL), mBack(NULL)
126{}
127
128
129VspInterior::~VspInterior()
130{
131        DEL_PTR(mFront);
132        DEL_PTR(mBack);
133}
134
135
136bool VspInterior::IsLeaf() const
137{
138        return false;
139}
140
141
142VspNode *VspInterior::GetBack()
143{
144        return mBack;
145}
146
147
148VspNode *VspInterior::GetFront()
149{
150        return mFront;
151}
152
153
154AxisAlignedPlane VspInterior::GetPlane() const
155{
156        return mPlane;
157}
158
159
160float VspInterior::GetPosition() const
161{
162        return mPlane.mPosition;
163}
164
165
166int VspInterior::GetAxis() const
167{
168        return mPlane.mAxis;
169}
170
171
172void VspInterior::ReplaceChildLink(VspNode *oldChild, VspNode *newChild)
173{
174        if (mBack == oldChild)
175                mBack = newChild;
176        else
177                mFront = newChild;
178}
179
180
181void VspInterior::SetupChildLinks(VspNode *b, VspNode *f)
182{
183    mBack = b;
184    mFront = f;
185}
186
187
188AxisAlignedBox3 VspInterior::GetBoundingBox() const
189{
190        return mBoundingBox;
191}
192
193
194void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
195{
196        mBoundingBox = box;
197}
198
199
200int VspInterior::Type() const
201{
202        return Interior;
203}
204
205/****************************************************************/
206/*                  class VspLeaf implementation                */
207/****************************************************************/
208
209
210VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
211{
212}
213
214
215VspLeaf::~VspLeaf()
216{
217        DEL_PTR(mPvs);
218}
219
220int VspLeaf::Type() const
221{
222        return Leaf;
223}
224
225
226
227VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
228mViewCell(viewCell)
229{
230}
231
232
233VspLeaf::VspLeaf(VspInterior *parent):
234VspNode(parent), mViewCell(NULL), mPvs(NULL)
235{}
236
237
238
239VspLeaf::VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell):
240VspNode(parent), mViewCell(viewCell), mPvs(NULL)
241{
242}
243
244ViewCellLeaf *VspLeaf::GetViewCell() const
245{
246        return mViewCell;
247}
248
249void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
250{
251        mViewCell = viewCell;
252}
253
254
255bool VspLeaf::IsLeaf() const
256{
257        return true;
258}
259
260
261/******************************************************************************/
262/*                       class VspTree implementation                      */
263/******************************************************************************/
264
265
266VspTree::VspTree():
267mRoot(NULL),
268mOutOfBoundsCell(NULL),
269mStoreRays(false),
270mUseRandomAxis(false),
271mTimeStamp(1)
272{
273        bool randomize = false;
274        Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
275        if (randomize)
276                Randomize(); // initialise random generator for heuristics
277
278        //-- termination criteria for autopartition
279        Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
280        Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
281        Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
282        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
283        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
284        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
285        Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
286        Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
287
288        //-- max cost ratio for early tree termination
289        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
290
291        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
292        Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
293
294        // HACK//mTermMinPolygons = 25;
295
296        //-- factors for bsp tree split plane heuristics
297        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
298
299        //-- partition criteria
300        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
301
302        // if only the driving axis is used for axis aligned split
303        Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
304       
305        //Environment::GetSingleton()->GetFloatValue("VspTree.maxTotalMemory", mMaxTotalMemory);
306        Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
307
308        Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
309        Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
310        Environment::GetSingleton()->GetBoolValue("VspTree.useRandomAxis", mUseRandomAxis);
311        Environment::GetSingleton()->GetIntValue("VspTree.nodePriorityQueueType", mNodePriorityQueueType);
312       
313        char subdivisionStatsLog[100];
314        Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
315        mSubdivisionStats.open(subdivisionStatsLog);
316
317        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
318        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
319       
320
321        //-- debug output
322
323        Debug << "******* VSP BSP options ******** " << endl;
324    Debug << "max depth: " << mTermMaxDepth << endl;
325        Debug << "min PVS: " << mTermMinPvs << endl;
326        Debug << "min probabiliy: " << mTermMinProbability << endl;
327        Debug << "min rays: " << mTermMinRays << endl;
328        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
329        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
330        Debug << "miss tolerance: " << mTermMissTolerance << endl;
331        Debug << "max view cells: " << mMaxViewCells << endl;
332        Debug << "randomize: " << randomize << endl;
333
334        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
335        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
336        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
337        Debug << "max memory: " << mMaxMemory << endl;
338        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
339        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
340        Debug << "use random axis: " << mUseRandomAxis << endl;
341        Debug << "priority queue type: " << mNodePriorityQueueType << endl;
342        Debug << "circulating axis: " << mCirculatingAxis << endl;
343        Debug << "minband: " << mMinBand << endl;
344        Debug << "maxband: " << mMaxBand << endl;
345       
346
347        mSplitCandidates = new vector<SortableEntry>;
348
349        Debug << endl;
350}
351
352
353VspViewCell *VspTree::GetOutOfBoundsCell()
354{
355        return mOutOfBoundsCell;
356}
357
358
359VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
360{
361        if (!mOutOfBoundsCell)
362        {
363                mOutOfBoundsCell = new VspViewCell();
364                mOutOfBoundsCell->SetId(-1);
365                mOutOfBoundsCell->SetValid(false);
366        }
367
368        return mOutOfBoundsCell;
369}
370
371
372const VspTreeStatistics &VspTree::GetStatistics() const
373{
374        return mVspStats;
375}
376
377
378VspTree::~VspTree()
379{
380        DEL_PTR(mRoot);
381        DEL_PTR(mSplitCandidates);
382}
383
384
385void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
386                                                                  AxisAlignedBox3 *forcedBoundingBox)
387{
388        mVspStats.nodes = 1;
389        mBoundingBox.Initialize();      // initialise vsp tree bounding box
390
391        if (forcedBoundingBox)
392                mBoundingBox = *forcedBoundingBox;
393       
394        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
395
396        Intersectable::NewMail();
397
398        //-- compute bounding box
399        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
400        {
401                VssRay *ray = *rit;
402
403                // compute bounding box of view space
404                if (!forcedBoundingBox)
405                {
406                        mBoundingBox.Include(ray->GetTermination());
407                        mBoundingBox.Include(ray->GetOrigin());
408                }
409        }
410
411        mTermMinProbability *= mBoundingBox.GetVolume();
412        mGlobalCostMisses = 0;
413}
414
415
416void VspTree::AddSubdivisionStats(const int viewCells,
417                                                                  const float renderCostDecr,
418                                                                  const float splitCandidateCost,
419                                                                  const float totalRenderCost,
420                                                                         const float avgRenderCost)
421{
422        mSubdivisionStats
423                        << "#ViewCells\n" << viewCells << endl
424                        << "#RenderCostDecrease\n" << renderCostDecr << endl
425                        << "#SplitCandidateCost\n" << splitCandidateCost << endl
426                        << "#TotalRenderCost\n" << totalRenderCost << endl
427                        << "#AvgRenderCost\n" << avgRenderCost << endl;
428}
429
430
431// TODO: return memory usage in MB
432float VspTree::GetMemUsage() const
433{
434        return (float)
435                 (sizeof(VspTree) +
436                  mVspStats.Leaves() * sizeof(VspLeaf) +
437                  mCreatedViewCells * sizeof(VspViewCell) +
438                  mVspStats.pvs * sizeof(ObjectPvsData) +
439                  mVspStats.Interior() * sizeof(VspInterior) +
440                  mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
441}
442
443
444bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
445{
446        return
447                (((int)data.mRays->size() <= mTermMinRays) ||
448                 (data.mPvs <= mTermMinPvs)   ||
449                 (data.mProbability <= mTermMinProbability) ||
450                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
451                 (data.mDepth >= mTermMaxDepth));
452}
453
454
455bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
456{
457        return
458                (mOutOfMemory ||
459                (mVspStats.Leaves() >= mMaxViewCells) ||
460                (mGlobalCostMisses >= mTermGlobalCostMissTolerance));
461}
462
463
464VspNode *VspTree::Subdivide(SplitQueue &tQueue,
465                                                        VspSplitCandidate &splitCandidate,
466                                                        const bool globalCriteriaMet)
467{
468        VspTraversalData &tData = splitCandidate.mParentData;
469
470        VspNode *newNode = tData.mNode;
471
472        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
473        {       
474                VspTraversalData tFrontData;
475                VspTraversalData tBackData;
476
477                //-- continue subdivision
478               
479                // create new interior node and two leaf node
480                const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
481                newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
482       
483                const int maxCostMisses = splitCandidate.mMaxCostMisses;
484
485
486                // how often was max cost ratio missed in this branch?
487                tFrontData.mMaxCostMisses = maxCostMisses;
488                tBackData.mMaxCostMisses = maxCostMisses;
489                       
490                //-- statistics
491                if (1)
492                {
493                        const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
494                        const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
495                        const float cData = (float)tData.mPvs * tData.mProbability;
496       
497                        const float costDecr =
498                                (cFront + cBack - cData) / mBoundingBox.GetVolume();
499
500                        mTotalCost += costDecr;
501                        mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
502
503                        AddSubdivisionStats(mVspStats.Leaves(),
504                                                                -costDecr,
505                                                                splitCandidate.GetPriority(),
506                                                                mTotalCost,
507                                                                (float)mTotalPvsSize / (float)mVspStats.Leaves());
508                }
509
510       
511                //-- push the new split candidates on the queue
512                VspSplitCandidate *frontCandidate = new VspSplitCandidate();
513                VspSplitCandidate *backCandidate = new VspSplitCandidate();
514
515                EvalSplitCandidate(tFrontData, *frontCandidate);
516                EvalSplitCandidate(tBackData, *backCandidate);
517
518                tQueue.push(frontCandidate);
519                tQueue.push(backCandidate);
520
521                // delete old leaf node
522                DEL_PTR(tData.mNode);
523        }
524
525
526        //-- terminate traversal and create new view cell
527        if (newNode->IsLeaf())
528        {
529                VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
530       
531                VspViewCell *viewCell = new VspViewCell();
532        leaf->SetViewCell(viewCell);
533               
534                //-- update pvs
535                int conSamp = 0;
536                float sampCon = 0.0f;
537                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
538
539                // update scalar pvs size value
540                mViewCellsManager->SetScalarPvsSize(viewCell, viewCell->GetPvs().GetSize());
541
542                mVspStats.contributingSamples += conSamp;
543                mVspStats.sampleContributions +=(int) sampCon;
544
545                //-- store additional info
546                if (mStoreRays)
547                {
548                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
549                        for (it = tData.mRays->begin(); it != it_end; ++ it)
550                        {
551                                (*it).mRay->Ref();                     
552                                leaf->mVssRays.push_back((*it).mRay);
553                        }
554                }
555               
556                viewCell->mLeaf = leaf;
557
558                viewCell->SetVolume(tData.mProbability);
559        leaf->mProbability = tData.mProbability;
560
561                // finally evaluate stats until this leaf
562                EvaluateLeafStats(tData);
563        }
564
565        //-- cleanup
566        tData.Clear();
567       
568        return newNode;
569}
570
571
572void VspTree::EvalSplitCandidate(VspTraversalData &tData,
573                                                                 VspSplitCandidate &splitData)
574{
575        float frontProb;
576        float backtProb;
577       
578        VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
579       
580        // compute locally best split plane
581        const bool success =
582                SelectPlane(tData, splitData.mSplitPlane,
583                                        frontProb, backtProb);
584
585        //TODO
586        // compute global decrease in render cost
587        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
588        splitData.mParentData = tData;
589        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
590}
591
592
593VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
594                                                                        VspTraversalData &tData,
595                                                                        VspTraversalData &frontData,
596                                                                        VspTraversalData &backData)
597{
598        VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
599       
600        //-- the front and back traversal data is filled with the new values
601        frontData.mDepth = tData.mDepth + 1;
602        frontData.mRays = new RayInfoContainer();
603       
604        backData.mDepth = tData.mDepth + 1;
605        backData.mRays = new RayInfoContainer();
606       
607        //-- subdivide rays
608        SplitRays(splitPlane,
609                          *tData.mRays,
610                          *frontData.mRays,
611                          *backData.mRays);
612
613        //-- compute pvs
614        frontData.mPvs = ComputePvsSize(*frontData.mRays);
615        backData.mPvs = ComputePvsSize(*backData.mRays);
616
617        // split front and back node geometry and compute area
618        tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
619                                                         frontData.mBoundingBox, backData.mBoundingBox);
620
621
622        frontData.mProbability = frontData.mBoundingBox.GetVolume();
623        backData.mProbability = tData.mProbability - frontData.mProbability;
624
625       
626    ///////////////////////////////////////////
627        // subdivide further
628
629        // store maximal and minimal depth
630        if (tData.mDepth > mVspStats.maxDepth)
631        {
632                Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
633                mVspStats.maxDepth = tData.mDepth;
634        }
635
636        mVspStats.nodes += 2;
637
638   
639        VspInterior *interior = new VspInterior(splitPlane);
640
641#ifdef _DEBUG
642        Debug << interior << endl;
643#endif
644
645
646        //-- create front and back leaf
647
648        VspInterior *parent = leaf->GetParent();
649
650        // replace a link from node's parent
651        if (parent)
652        {
653                parent->ReplaceChildLink(leaf, interior);
654                interior->SetParent(parent);
655        }
656        else // new root
657        {
658                mRoot = interior;
659        }
660
661        // and setup child links
662        interior->SetupChildLinks(new VspLeaf(interior), new VspLeaf(interior));
663        // add bounding box
664        interior->SetBoundingBox(tData.mBoundingBox);
665
666        frontData.mNode = interior->GetFront();
667        backData.mNode = interior->GetBack();
668
669        interior->mTimeStamp = mTimeStamp ++;
670       
671        return interior;
672}
673
674
675void VspTree::AddToPvs(VspLeaf *leaf,
676                                                  const RayInfoContainer &rays,
677                                                  float &sampleContributions,
678                                                  int &contributingSamples)
679{
680        sampleContributions = 0;
681        contributingSamples = 0;
682 
683        RayInfoContainer::const_iterator it, it_end = rays.end();
684 
685        ViewCellLeaf *vc = leaf->GetViewCell();
686 
687        // add contributions from samples to the PVS
688        for (it = rays.begin(); it != it_end; ++ it)
689        {
690                float sc = 0.0f;
691                VssRay *ray = (*it).mRay;
692
693                bool madeContrib = false;
694                float contribution;
695
696                if (ray->mTerminationObject)
697                {
698                        if (vc->AddPvsSample(ray->mTerminationObject, ray->mPdf, contribution))
699                                madeContrib = true;
700                        sc += contribution;
701                }
702         
703                if (ray->mOriginObject)
704                {
705                        if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
706                                madeContrib = true;
707                        sc += contribution;
708                }
709         
710          sampleContributions += sc;
711
712          if (madeContrib)
713                  ++ contributingSamples;
714               
715          //leaf->mVssRays.push_back(ray);
716        }
717}
718
719
720void VspTree::SortSplitCandidates(const RayInfoContainer &rays,
721                                                                         const int axis,
722                                                                         float minBand,
723                                                                         float maxBand)
724{
725        mSplitCandidates->clear();
726
727        int requestedSize = 2 * (int)(rays.size());
728        // creates a sorted split candidates array
729        if (mSplitCandidates->capacity() > 500000 &&
730                requestedSize < (int)(mSplitCandidates->capacity() / 10) )
731        {
732        delete mSplitCandidates;
733                mSplitCandidates = new vector<SortableEntry>;
734        }
735
736        mSplitCandidates->reserve(requestedSize);
737
738        float pos;
739
740        // float values => don't compare with exact values
741        if (0)
742        {
743                minBand += Limits::Small;
744                maxBand -= Limits::Small;
745        }
746
747        // insert all queries
748        for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
749        {
750                const bool positive = (*ri).mRay->HasPosDir(axis);
751                               
752                pos = (*ri).ExtrapOrigin(axis);
753                // clamp to min / max band
754                if (0) ClipValue(pos, minBand, maxBand);
755               
756                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
757                                                                        pos, (*ri).mRay));
758
759                pos = (*ri).ExtrapTermination(axis);
760                // clamp to min / max band
761                if (0) ClipValue(pos, minBand, maxBand);
762
763                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
764                                                                        pos, (*ri).mRay));
765        }
766
767        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
768}
769
770
771float VspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
772                                                                                  const AxisAlignedBox3 &box,
773                                                                                  const int pvsSize,
774                                                                                  const int axis,
775                                          float &position)
776{
777        const float minBox = box.Min(axis);
778        const float maxBox = box.Max(axis);
779
780        const float sizeBox = maxBox - minBox;
781
782        const float minBand = minBox + mMinBand * sizeBox;
783        const float maxBand = minBox + mMaxBand * sizeBox;
784
785        SortSplitCandidates(rays, axis, minBand, maxBand);
786
787        // go through the lists, count the number of objects left and right
788        // and evaluate the following cost funcion:
789        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
790
791        int pvsl = 0;
792        int pvsr = pvsSize;
793
794        int pvsBack = pvsl;
795        int pvsFront = pvsr;
796
797        float sum = (float)pvsSize * sizeBox;
798        float minSum = 1e20f;
799
800       
801        // if no border can be found, take mid split
802        position = minBox + 0.5f * sizeBox;
803       
804        // the relative cost ratio
805        float ratio = /*Limits::Infinity;*/99999999.0f;
806        bool splitPlaneFound = false;
807
808        Intersectable::NewMail();
809
810        RayInfoContainer::const_iterator ri, ri_end = rays.end();
811
812        // set all object as belonging to the front pvs
813        for(ri = rays.begin(); ri != ri_end; ++ ri)
814        {
815                Intersectable *oObject = (*ri).mRay->mOriginObject;
816                Intersectable *tObject = (*ri).mRay->mTerminationObject;
817
818                if (oObject)
819                {
820                        if (!oObject->Mailed())
821                        {
822                                oObject->Mail();
823                                oObject->mCounter = 1;
824                        }
825                        else
826                        {
827                                ++ oObject->mCounter;
828                        }
829                }
830                if (tObject)
831                {
832                        if (!tObject->Mailed())
833                        {
834                                tObject->Mail();
835                                tObject->mCounter = 1;
836                        }
837                        else
838                        {
839                                ++ tObject->mCounter;
840                        }
841                }
842        }
843
844        Intersectable::NewMail();
845
846        vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
847
848        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
849        {
850                VssRay *ray;
851                ray = (*ci).ray;
852               
853                Intersectable *oObject = ray->mOriginObject;
854                Intersectable *tObject = ray->mTerminationObject;
855               
856
857                switch ((*ci).type)
858                {
859                        case SortableEntry::ERayMin:
860                                {
861                                        if (oObject && !oObject->Mailed())
862                                        {
863                                                oObject->Mail();
864                                                ++ pvsl;
865                                        }
866                                        if (tObject && !tObject->Mailed())
867                                        {
868                                                tObject->Mail();
869                                                ++ pvsl;
870                                        }
871                                        break;
872                                }
873                        case SortableEntry::ERayMax:
874                                {
875                                        if (oObject)
876                                        {
877                                                if (-- oObject->mCounter == 0)
878                                                        -- pvsr;
879                                        }
880
881                                        if (tObject)
882                                        {
883                                                if (-- tObject->mCounter == 0)
884                                                        -- pvsr;
885                                        }
886
887                                        break;
888                                }
889                }
890
891               
892               
893                // Note: sufficient to compare size of bounding boxes of front and back side?
894                if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
895                {
896                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
897
898                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
899                        //Debug << "cost= " << sum << endl;
900
901                        if (sum < minSum)
902                        {
903                                splitPlaneFound = true;
904
905                                minSum = sum;
906                                position = (*ci).value;
907                               
908                                pvsBack = pvsl;
909                                pvsFront = pvsr;
910                        }
911                }
912        }
913       
914       
915        // -- compute cost
916        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
917        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
918
919        const float pOverall = sizeBox;
920
921        const float pBack = position - minBox;
922        const float pFront = maxBox - position;
923       
924        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
925    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
926        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
927       
928        const float oldRenderCost = penaltyOld * pOverall;
929        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
930
931        if (splitPlaneFound)
932        {
933                ratio = newRenderCost / (oldRenderCost + Limits::Small);
934        }
935        //if (axis != 1)
936        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
937         //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
938
939        return ratio;
940}
941
942
943float VspTree::SelectPlane(const VspTraversalData &tData,
944                                                   AxisAlignedPlane &plane,
945                                                   float &pFront,
946                                                   float &pBack)
947{
948        float nPosition[3];
949        float nCostRatio[3];
950        float nProbFront[3];
951        float nProbBack[3];
952
953        // create bounding box of node geometry
954        AxisAlignedBox3 box = tData.mBoundingBox;
955               
956        int sAxis = 0;
957        int bestAxis = -1;
958
959
960        // if we use some kind of specialised fixed axis
961    const bool useSpecialAxis =
962                mOnlyDrivingAxis || mUseRandomAxis || mCirculatingAxis;
963
964        if (mUseRandomAxis)
965                sAxis = Random(3);
966        else if (mCirculatingAxis)
967                sAxis = (tData.mAxis + 1) % 3;
968        else if (mOnlyDrivingAxis)
969                sAxis = box.Size().DrivingAxis();
970
971
972        for (int axis = 0; axis < 3 ; ++ axis)
973        {
974                if (!useSpecialAxis || (axis == sAxis))
975                {
976                        //-- place split plane using heuristics
977
978                        if (mUseCostHeuristics)
979                        {
980                                nCostRatio[axis] =
981                                        BestCostRatioHeuristics(*tData.mRays,
982                                                                                    box,
983                                                                                        tData.mPvs,
984                                                                                        axis,
985                                                                                        nPosition[axis]);                       
986                        }
987                        else //-- split plane position is spatial median
988                        {
989                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
990
991                                nCostRatio[axis] = EvalSplitCost(tData,
992                                                                                                 box,
993                                                                                                 axis,
994                                                                                                 nPosition[axis],
995                                                                                                 nProbFront[axis],
996                                                                                                 nProbBack[axis]);
997                        }
998                                               
999                        if (bestAxis == -1)
1000                        {
1001                                bestAxis = axis;
1002                        }
1003                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
1004                        {
1005                                bestAxis = axis;
1006                        }
1007                }
1008        }
1009
1010        //-- assign values
1011        plane.mAxis = bestAxis;
1012        pFront = nProbFront[bestAxis];
1013        pBack = nProbBack[bestAxis];
1014
1015        //-- split plane position
1016    plane.mPosition = nPosition[bestAxis];
1017
1018        return nCostRatio[bestAxis];
1019}
1020
1021
1022inline void VspTree::GenerateUniqueIdsForPvs()
1023{
1024        Intersectable::NewMail(); sBackId = Intersectable::sMailId;
1025        Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
1026        Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
1027}
1028
1029
1030float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1031                                                                          const VspTraversalData &data) const
1032{
1033        float pvsFront = 0;
1034        float pvsBack = 0;
1035        float totalPvs = 0;
1036
1037        // probability that view point lies in back / front node
1038        float pOverall = data.mProbability;
1039        float pFront = 0;
1040        float pBack = 0;
1041
1042
1043        // create unique ids for pvs heuristics
1044        GenerateUniqueIdsForPvs();
1045       
1046        RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1047
1048        for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
1049        {
1050                RayInfo rayInf = *rit;
1051
1052                float t;
1053                VssRay *ray = rayInf.mRay;
1054                const int cf =
1055                        rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1056                                                                                  candidatePlane.mPosition, t);
1057
1058                // find front and back pvs for origing and termination object
1059                AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1060                AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1061        }
1062
1063        AxisAlignedBox3 frontBox;
1064        AxisAlignedBox3 backBox;
1065
1066        data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
1067
1068        pFront = frontBox.GetVolume();
1069        pBack = pOverall - pFront;
1070               
1071
1072        //-- pvs rendering heuristics
1073        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1074        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1075
1076        //-- only render cost heuristics or combined with standard deviation
1077        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1078    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1079        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1080                       
1081        const float oldRenderCost = pOverall * penaltyOld;
1082        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1083
1084        //Debug << "decrease: " << oldRenderCost - newRenderCost << endl;
1085        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBoundingBox.GetVolume();
1086       
1087
1088#if 1
1089        // take render cost of node into account
1090        // otherwise danger of being stuck in a local minimum!!
1091        const float normalizedOldRenderCost = oldRenderCost / mBoundingBox.GetVolume();
1092        return 0.99f * renderCostDecrease + 0.01f * normalizedOldRenderCost;
1093#else
1094        return renderCostDecrease;
1095#endif
1096}
1097
1098
1099float VspTree::EvalSplitCost(const VspTraversalData &data,
1100                                                         const AxisAlignedBox3 &box,
1101                                                         const int axis,
1102                                                         const float &position,                                                                           
1103                                                         float &pFront,
1104                                                         float &pBack) const
1105{
1106        float pvsTotal = 0;
1107        float pvsFront = 0;
1108        float pvsBack = 0;
1109       
1110        // create unique ids for pvs heuristics
1111        GenerateUniqueIdsForPvs();
1112
1113        const int pvsSize = data.mPvs;
1114
1115        RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1116
1117        // this is the main ray classification loop!
1118        for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1119        {
1120                // determine the side of this ray with respect to the plane
1121                float t;
1122                const int side = (*rit).ComputeRayIntersection(axis, position, t);
1123       
1124                AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1125                AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1126        }
1127
1128        //-- pvs heuristics
1129        float pOverall;
1130
1131        //-- compute heurstics
1132        //-- we take simplified computation for mid split
1133               
1134        pOverall = data.mProbability;
1135        pBack = pFront = pOverall * 0.5f;
1136       
1137       
1138#ifdef _DEBUG
1139        Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1140        Debug << pFront << " " << pBack << " " << pOverall << endl;
1141#endif
1142
1143       
1144        const float newCost = pvsBack * pBack + pvsFront * pFront;
1145        const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1146
1147        return  (mCtDivCi + newCost) / oldCost;
1148}
1149
1150
1151void VspTree::AddObjToPvs(Intersectable *obj,
1152                                                         const int cf,
1153                                                         float &frontPvs,
1154                                                         float &backPvs,
1155                                                         float &totalPvs) const
1156{
1157        if (!obj)
1158                return;
1159
1160        const float renderCost = mViewCellsManager->EvalRenderCost(obj);
1161
1162        // new object
1163        if ((obj->mMailbox != sFrontId) &&
1164                (obj->mMailbox != sBackId) &&
1165                (obj->mMailbox != sFrontAndBackId))
1166        {
1167                totalPvs += renderCost;
1168        }
1169
1170        // TODO: does this really belong to no pvs?
1171        //if (cf == Ray::COINCIDENT) return;
1172
1173        // object belongs to both PVS
1174        if (cf >= 0)
1175        {
1176                if ((obj->mMailbox != sFrontId) &&
1177                        (obj->mMailbox != sFrontAndBackId))
1178                {
1179                        frontPvs += renderCost;
1180               
1181                        if (obj->mMailbox == sBackId)
1182                                obj->mMailbox = sFrontAndBackId;
1183                        else
1184                                obj->mMailbox = sFrontId;
1185                }
1186        }
1187
1188        if (cf <= 0)
1189        {
1190                if ((obj->mMailbox != sBackId) &&
1191                        (obj->mMailbox != sFrontAndBackId))
1192                {
1193                        backPvs += renderCost;
1194               
1195                        if (obj->mMailbox == sFrontId)
1196                                obj->mMailbox = sFrontAndBackId;
1197                        else
1198                                obj->mMailbox = sBackId;
1199                }
1200        }
1201}
1202
1203
1204void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1205                                                           const bool onlyUnmailed,
1206                                                           const int maxPvsSize) const
1207{
1208        stack<VspNode *> nodeStack;
1209        nodeStack.push(mRoot);
1210
1211        while (!nodeStack.empty())
1212        {
1213                VspNode *node = nodeStack.top();
1214                nodeStack.pop();
1215               
1216                if (node->IsLeaf())
1217                {
1218                        // test if this leaf is in valid view space
1219                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
1220                        if (leaf->TreeValid() &&
1221                                (!onlyUnmailed || !leaf->Mailed()) &&
1222                                ((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
1223                        {
1224                                leaves.push_back(leaf);
1225                        }
1226                }
1227                else
1228                {
1229                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1230
1231                        nodeStack.push(interior->GetBack());
1232                        nodeStack.push(interior->GetFront());
1233                }
1234        }
1235}
1236
1237
1238AxisAlignedBox3 VspTree::GetBoundingBox() const
1239{
1240        return mBoundingBox;
1241}
1242
1243
1244VspNode *VspTree::GetRoot() const
1245{
1246        return mRoot;
1247}
1248
1249
1250void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1251{
1252        // the node became a leaf -> evaluate stats for leafs
1253        VspLeaf *leaf = dynamic_cast<VspLeaf *>(data.mNode);
1254
1255
1256        if (data.mPvs > mVspStats.maxPvs)
1257        {
1258                mVspStats.maxPvs = data.mPvs;
1259        }
1260
1261        mVspStats.pvs += data.mPvs;
1262
1263        if (data.mDepth < mVspStats.minDepth)
1264        {
1265                mVspStats.minDepth = data.mDepth;
1266        }
1267       
1268        if (data.mDepth >= mTermMaxDepth)
1269        {
1270        ++ mVspStats.maxDepthNodes;
1271                //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
1272        }
1273
1274        // accumulate rays to compute rays /  leaf
1275        mVspStats.accumRays += (int)data.mRays->size();
1276
1277        if (data.mPvs < mTermMinPvs)
1278                ++ mVspStats.minPvsNodes;
1279
1280        if ((int)data.mRays->size() < mTermMinRays)
1281                ++ mVspStats.minRaysNodes;
1282
1283        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1284                ++ mVspStats.maxRayContribNodes;
1285
1286        if (data.mProbability <= mTermMinProbability)
1287                ++ mVspStats.minProbabilityNodes;
1288       
1289        // accumulate depth to compute average depth
1290        mVspStats.accumDepth += data.mDepth;
1291
1292        ++ mCreatedViewCells;
1293
1294#ifdef _DEBUG
1295        Debug << "BSP stats: "
1296                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1297                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1298          //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
1299                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1300                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1301                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1302#endif
1303}
1304
1305
1306void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1307{
1308        ViewCell::NewMail();
1309        CollectViewCells(mRoot, onlyValid, viewCells, true);
1310}
1311
1312
1313void VspTree::CollapseViewCells()
1314{
1315// TODO
1316#if HAS_TO_BE_REDONE
1317        stack<VspNode *> nodeStack;
1318
1319        if (!mRoot)
1320                return;
1321
1322        nodeStack.push(mRoot);
1323       
1324        while (!nodeStack.empty())
1325        {
1326                VspNode *node = nodeStack.top();
1327                nodeStack.pop();
1328               
1329                if (node->IsLeaf())
1330        {
1331                        BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
1332
1333                        if (!viewCell->GetValid())
1334                        {
1335                                BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
1336       
1337                                ViewCellContainer leaves;
1338                                mViewCellsTree->CollectLeaves(viewCell, leaves);
1339
1340                                ViewCellContainer::const_iterator it, it_end = leaves.end();
1341
1342                                for (it = leaves.begin(); it != it_end; ++ it)
1343                                {
1344                                        VspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
1345                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
1346                                        ++ mVspStats.invalidLeaves;
1347                                }
1348
1349                                // add to unbounded view cell
1350                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1351                                DEL_PTR(viewCell);
1352                        }
1353                }
1354                else
1355                {
1356                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1357               
1358                        nodeStack.push(interior->GetFront());
1359                        nodeStack.push(interior->GetBack());
1360                }
1361        }
1362
1363        Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1364#endif
1365}
1366
1367
1368void VspTree::CollectRays(VssRayContainer &rays)
1369{
1370        vector<VspLeaf *> leaves;
1371
1372        vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1373
1374        for (lit = leaves.begin(); lit != lit_end; ++ lit)
1375        {
1376                VspLeaf *leaf = *lit;
1377                VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
1378
1379                for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
1380                        rays.push_back(*rit);
1381        }
1382}
1383
1384
1385void VspTree::ValidateTree()
1386{
1387        mVspStats.invalidLeaves = 0;
1388
1389        stack<VspNode *> nodeStack;
1390
1391        if (!mRoot)
1392                return;
1393
1394        nodeStack.push(mRoot);
1395
1396        while (!nodeStack.empty())
1397        {
1398                VspNode *node = nodeStack.top();
1399                nodeStack.pop();
1400               
1401                if (node->IsLeaf())
1402                {
1403                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
1404
1405                        if (!leaf->GetViewCell()->GetValid())
1406                                ++ mVspStats.invalidLeaves;
1407
1408                        // validity flags don't match => repair
1409                        if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
1410                        {
1411                                leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
1412                                PropagateUpValidity(leaf);
1413                        }
1414                }
1415                else
1416                {
1417                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1418               
1419                        nodeStack.push(interior->GetFront());
1420                        nodeStack.push(interior->GetBack());
1421                }
1422        }
1423
1424        Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1425}
1426
1427
1428
1429void VspTree::CollectViewCells(VspNode *root,
1430                                                                  bool onlyValid,
1431                                                                  ViewCellContainer &viewCells,
1432                                                                  bool onlyUnmailed) const
1433{
1434        stack<VspNode *> nodeStack;
1435
1436        if (!root)
1437                return;
1438
1439        nodeStack.push(root);
1440       
1441        while (!nodeStack.empty())
1442        {
1443                VspNode *node = nodeStack.top();
1444                nodeStack.pop();
1445               
1446                if (node->IsLeaf())
1447                {
1448                        if (!onlyValid || node->TreeValid())
1449                        {
1450                                ViewCellLeaf *leafVc = dynamic_cast<VspLeaf *>(node)->GetViewCell();
1451
1452                                ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
1453                                               
1454                                if (!onlyUnmailed || !viewCell->Mailed())
1455                                {
1456                                        viewCell->Mail();
1457                                        viewCells.push_back(viewCell);
1458                                }
1459                        }
1460                }
1461                else
1462                {
1463                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1464               
1465                        nodeStack.push(interior->GetFront());
1466                        nodeStack.push(interior->GetBack());
1467                }
1468        }
1469}
1470
1471
1472int VspTree::FindNeighbors(VspLeaf *n,
1473                                                   vector<VspLeaf *> &neighbors,
1474                                                   const bool onlyUnmailed) const
1475{
1476        stack<VspNode *> nodeStack;
1477        nodeStack.push(mRoot);
1478
1479        const AxisAlignedBox3 box = GetBBox(n);
1480
1481        while (!nodeStack.empty())
1482        {
1483                VspNode *node = nodeStack.top();
1484                nodeStack.pop();
1485
1486                if (node->IsLeaf())
1487                {
1488                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
1489
1490                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))
1491                                neighbors.push_back(leaf);
1492                }
1493                else
1494                {
1495                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1496                       
1497                        if (interior->GetPosition() > box.Max(interior->GetAxis()))
1498                                nodeStack.push(interior->GetBack());
1499                        else
1500                        {
1501                                if (interior->GetPosition() < box.Min(interior->GetAxis()))
1502                                        nodeStack.push(interior->GetFront());
1503                                else
1504                                {
1505                                        // random decision
1506                                        nodeStack.push(interior->GetBack());
1507                                        nodeStack.push(interior->GetFront());
1508                                }
1509                        }
1510                }
1511        }
1512
1513        return (int)neighbors.size();
1514}
1515
1516
1517// Find random neighbor which was not mailed
1518VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
1519{
1520        stack<VspNode *> nodeStack;
1521        nodeStack.push(mRoot);
1522 
1523        int mask = rand();
1524 
1525        while (!nodeStack.empty())
1526        {
1527                VspNode *node = nodeStack.top();
1528               
1529                nodeStack.pop();
1530               
1531                if (node->IsLeaf())
1532                {
1533                        return dynamic_cast<VspLeaf *>(node);
1534                }
1535                else
1536                {
1537                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1538                        VspNode *next;
1539                       
1540                        if (GetBBox(interior->GetBack()).Side(plane) < 0)
1541                                next = interior->GetFront();
1542            else
1543                                if (GetBBox(interior->GetFront()).Side(plane) < 0)
1544                                        next = interior->GetBack();
1545                                else
1546                                {
1547                                        // random decision
1548                                        if (mask & 1)
1549                                                next = interior->GetBack();
1550                                        else
1551                                                next = interior->GetFront();
1552                                        mask = mask >> 1;
1553                                }
1554
1555                                nodeStack.push(next);
1556                }
1557        }
1558 
1559        return NULL;
1560}
1561
1562
1563VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
1564{
1565        stack<VspNode *> nodeStack;
1566
1567        nodeStack.push(mRoot);
1568
1569        int mask = rand();
1570
1571        while (!nodeStack.empty())
1572        {
1573                VspNode *node = nodeStack.top();
1574                nodeStack.pop();
1575
1576                if (node->IsLeaf())
1577                {
1578                        if ( (!onlyUnmailed || !node->Mailed()) )
1579                                return dynamic_cast<VspLeaf *>(node);
1580                }
1581                else
1582                {
1583                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1584
1585                        // random decision
1586                        if (mask & 1)
1587                                nodeStack.push(interior->GetBack());
1588                        else
1589                                nodeStack.push(interior->GetFront());
1590
1591                        mask = mask >> 1;
1592                }
1593        }
1594
1595        return NULL;
1596}
1597
1598
1599int VspTree::ComputePvsSize(const RayInfoContainer &rays) const
1600{
1601        int pvsSize = 0;
1602
1603        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1604
1605        Intersectable::NewMail();
1606
1607        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1608        {
1609                VssRay *ray = (*rit).mRay;
1610
1611                if (ray->mOriginObject)
1612                {
1613                        if (!ray->mOriginObject->Mailed())
1614                        {
1615                                ray->mOriginObject->Mail();
1616                                ++ pvsSize;
1617                        }
1618                }
1619                if (ray->mTerminationObject)
1620                {
1621                        if (!ray->mTerminationObject->Mailed())
1622                        {
1623                                ray->mTerminationObject->Mail();
1624                                ++ pvsSize;
1625                        }
1626                }
1627        }
1628
1629        return pvsSize;
1630}
1631
1632
1633float VspTree::GetEpsilon() const
1634{
1635        return mEpsilon;
1636}
1637
1638
1639int VspTree::CastLineSegment(const Vector3 &origin,
1640                                                                const Vector3 &termination,
1641                                                                ViewCellContainer &viewcells)
1642{
1643        int hits = 0;
1644
1645        float mint = 0.0f, maxt = 1.0f;
1646        const Vector3 dir = termination - origin;
1647
1648        stack<LineTraversalData> tStack;
1649
1650        Intersectable::NewMail();
1651        ViewCell::NewMail();
1652
1653        Vector3 entp = origin;
1654        Vector3 extp = termination;
1655
1656        VspNode *node = mRoot;
1657        VspNode *farChild;
1658
1659        float position;
1660        int axis;
1661
1662        while (1)
1663        {
1664                if (!node->IsLeaf())
1665                {
1666                        VspInterior *in = dynamic_cast<VspInterior *>(node);
1667                        position = in->GetPosition();
1668                        axis = in->GetAxis();
1669
1670                        if (entp[axis] <= position)
1671                        {
1672                                if (extp[axis] <= position)
1673                                {
1674                                        node = in->GetBack();
1675                                        // cases N1,N2,N3,P5,Z2,Z3
1676                                        continue;
1677                                } else
1678                                {
1679                                        // case N4
1680                                        node = in->GetBack();
1681                                        farChild = in->GetFront();
1682                                }
1683                        }
1684                        else
1685                        {
1686                                if (position <= extp[axis])
1687                                {
1688                                        node = in->GetFront();
1689                                        // cases P1,P2,P3,N5,Z1
1690                                        continue;
1691                                }
1692                                else
1693                                {
1694                                        node = in->GetFront();
1695                                        farChild = in->GetBack();
1696                                        // case P4
1697                                }
1698                        }
1699
1700                        // $$ modification 3.5.2004 - hints from Kamil Ghais
1701                        // case N4 or P4
1702                        const float tdist = (position - origin[axis]) / dir[axis];
1703                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
1704
1705                        extp = origin + dir * tdist;
1706                        maxt = tdist;
1707                }
1708                else
1709                {
1710                        // compute intersection with all objects in this leaf
1711                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
1712                        ViewCell *vc = leaf->GetViewCell();
1713
1714                        if (!vc->Mailed())
1715                        {
1716                                vc->Mail();
1717                                viewcells.push_back(vc);
1718                                ++ hits;
1719                        }
1720#if 0
1721                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
1722#endif
1723                        // get the next node from the stack
1724                        if (tStack.empty())
1725                                break;
1726
1727                        entp = extp;
1728                        mint = maxt;
1729                       
1730                        LineTraversalData &s  = tStack.top();
1731                        node = s.mNode;
1732                        extp = s.mExitPoint;
1733                        maxt = s.mMaxT;
1734                        tStack.pop();
1735                }
1736        }
1737
1738        return hits;
1739}
1740
1741
1742int VspTree::CastRay(Ray &ray)
1743{
1744        int hits = 0;
1745
1746        stack<LineTraversalData> tStack;
1747        const Vector3 dir = ray.GetDir();
1748
1749        float maxt, mint;
1750
1751        if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
1752                return 0;
1753
1754        Intersectable::NewMail();
1755        ViewCell::NewMail();
1756
1757        Vector3 entp = ray.Extrap(mint);
1758        Vector3 extp = ray.Extrap(maxt);
1759
1760        const Vector3 origin = entp;
1761
1762        VspNode *node = mRoot;
1763        VspNode *farChild = NULL;
1764
1765        float position;
1766        int axis;
1767
1768        while (1)
1769        {
1770                if (!node->IsLeaf())
1771                {
1772                        VspInterior *in = dynamic_cast<VspInterior *>(node);
1773                        position = in->GetPosition();
1774                        axis = in->GetAxis();
1775
1776                        if (entp[axis] <= position)
1777                        {
1778                                if (extp[axis] <= position)
1779                                {
1780                                        node = in->GetBack();
1781                                        // cases N1,N2,N3,P5,Z2,Z3
1782                                        continue;
1783                                }
1784                                else
1785                                {
1786                                        // case N4
1787                                        node = in->GetBack();
1788                                        farChild = in->GetFront();
1789                                }
1790                        }
1791                        else
1792                        {
1793                                if (position <= extp[axis])
1794                                {
1795                                        node = in->GetFront();
1796                                        // cases P1,P2,P3,N5,Z1
1797                                        continue;
1798                                }
1799                                else
1800                                {
1801                                        node = in->GetFront();
1802                                        farChild = in->GetBack();
1803                                        // case P4
1804                                }
1805                        }
1806
1807                        // $$ modification 3.5.2004 - hints from Kamil Ghais
1808                        // case N4 or P4
1809                        const float tdist = (position - origin[axis]) / dir[axis];
1810                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
1811                        extp = origin + dir * tdist;
1812                        maxt = tdist;
1813                }
1814                else
1815                {
1816                        // compute intersection with all objects in this leaf
1817                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
1818                        ViewCell *vc = leaf->GetViewCell();
1819
1820                        if (!vc->Mailed())
1821                        {
1822                                vc->Mail();
1823                                // todo: add view cells to ray
1824                                ++ hits;
1825                        }
1826#if 0
1827                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
1828#endif
1829                        // get the next node from the stack
1830                        if (tStack.empty())
1831                                break;
1832
1833                        entp = extp;
1834                        mint = maxt;
1835                       
1836                        LineTraversalData &s  = tStack.top();
1837                        node = s.mNode;
1838                        extp = s.mExitPoint;
1839                        maxt = s.mMaxT;
1840                        tStack.pop();
1841                }
1842        }
1843
1844        return hits;
1845}
1846
1847
1848VspNode *VspTree::CollapseTree(VspNode *node, int &collapsed)
1849{
1850// TODO
1851#if HAS_TO_BE_REDONE
1852        if (node->IsLeaf())
1853                return node;
1854
1855        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1856
1857        VspNode *front = CollapseTree(interior->GetFront(), collapsed);
1858        VspNode *back = CollapseTree(interior->GetBack(), collapsed);
1859
1860        if (front->IsLeaf() && back->IsLeaf())
1861        {
1862                VspLeaf *frontLeaf = dynamic_cast<VspLeaf *>(front);
1863                VspLeaf *backLeaf = dynamic_cast<VspLeaf *>(back);
1864
1865                //-- collapse tree
1866                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
1867                {
1868                        BspViewCell *vc = frontLeaf->GetViewCell();
1869
1870                        VspLeaf *leaf = new VspLeaf(interior->GetParent(), vc);
1871                        leaf->SetTreeValid(frontLeaf->TreeValid());
1872
1873                        // replace a link from node's parent
1874                        if (leaf->GetParent())
1875                                leaf->GetParent()->ReplaceChildLink(node, leaf);
1876                        else
1877                                mRoot = leaf;
1878
1879                        ++ collapsed;
1880                        delete interior;
1881
1882                        return leaf;
1883                }
1884        }
1885#endif
1886        return node;
1887}
1888
1889
1890int VspTree::CollapseTree()
1891{
1892        int collapsed = 0;
1893
1894        (void)CollapseTree(mRoot, collapsed);
1895        // revalidate leaves
1896        RepairViewCellsLeafLists();
1897
1898        return collapsed;
1899}
1900
1901
1902void VspTree::RepairViewCellsLeafLists()
1903{
1904// TODO
1905#if HAS_TO_BE_REDONE
1906        // list not valid anymore => clear
1907        stack<VspNode *> nodeStack;
1908        nodeStack.push(mRoot);
1909
1910        ViewCell::NewMail();
1911
1912        while (!nodeStack.empty())
1913        {
1914                VspNode *node = nodeStack.top();
1915                nodeStack.pop();
1916
1917                if (node->IsLeaf())
1918                {
1919                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
1920
1921                        BspViewCell *viewCell = leaf->GetViewCell();
1922
1923                        if (!viewCell->Mailed())
1924                        {
1925                                viewCell->mLeaves.clear();
1926                                viewCell->Mail();
1927                        }
1928       
1929                        viewCell->mLeaves.push_back(leaf);
1930
1931                }
1932                else
1933                {
1934                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1935
1936                        nodeStack.push(interior->GetFront());
1937                        nodeStack.push(interior->GetBack());
1938                }
1939        }
1940// TODO
1941#endif
1942}
1943
1944
1945
1946ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
1947{
1948        if (mRoot == NULL)
1949                return NULL;
1950
1951        stack<VspNode *> nodeStack;
1952        nodeStack.push(mRoot);
1953 
1954        ViewCellLeaf *viewcell = NULL;
1955 
1956        while (!nodeStack.empty()) 
1957        {
1958                VspNode *node = nodeStack.top();
1959                nodeStack.pop();
1960       
1961                if (node->IsLeaf())
1962                {
1963                        viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
1964                        break;
1965                }
1966                else   
1967                {       
1968                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1969     
1970                        // random decision
1971                        if (interior->GetPosition() - point[interior->GetAxis()] < 0)
1972                                nodeStack.push(interior->GetBack());
1973                        else
1974                                nodeStack.push(interior->GetFront());
1975                }
1976        }
1977 
1978        if (active)
1979                return mViewCellsTree->GetActiveViewCell(viewcell);
1980        else
1981                return viewcell;
1982}
1983
1984
1985bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
1986{
1987        VspNode *node = mRoot;
1988
1989        while (1)
1990        {
1991                // early exit
1992                if (node->TreeValid())
1993                        return true;
1994
1995                if (node->IsLeaf())
1996                        return false;
1997                       
1998                VspInterior *in = dynamic_cast<VspInterior *>(node);
1999                                       
2000                if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2001                {
2002                        node = in->GetBack();
2003                }
2004                else
2005                {
2006                        node = in->GetFront();
2007                }
2008        }
2009
2010        // should never come here
2011        return false;
2012}
2013
2014
2015void VspTree::PropagateUpValidity(VspNode *node)
2016{
2017        const bool isValid = node->TreeValid();
2018
2019        // propagative up invalid flag until only invalid nodes exist over this node
2020        if (!isValid)
2021        {
2022                while (!node->IsRoot() && node->GetParent()->TreeValid())
2023                {
2024                        node = node->GetParent();
2025                        node->SetTreeValid(false);
2026                }
2027        }
2028        else
2029        {
2030                // propagative up valid flag until one of the subtrees is invalid
2031                while (!node->IsRoot() && !node->TreeValid())
2032                {
2033            node = node->GetParent();
2034                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2035                       
2036                        // the parent is valid iff both leaves are valid
2037                        node->SetTreeValid(interior->GetBack()->TreeValid() &&
2038                                                           interior->GetFront()->TreeValid());
2039                }
2040        }
2041}
2042
2043#if ZIPPED_VIEWCELLS
2044bool VspTree::Export(ogzstream &stream)
2045#else
2046bool VspTree::Export(ofstream &stream)
2047#endif
2048{
2049        ExportNode(mRoot, stream);
2050
2051        return true;
2052}
2053
2054
2055#if ZIPPED_VIEWCELLS
2056void VspTree::ExportNode(VspNode *node, ogzstream &stream)
2057#else
2058void VspTree::ExportNode(VspNode *node, ofstream &stream)
2059#endif
2060{
2061        if (node->IsLeaf())
2062        {
2063                VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
2064                ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2065
2066                int id = -1;
2067                if (viewCell != mOutOfBoundsCell)
2068                        id = viewCell->GetId();
2069
2070                stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2071        }
2072        else
2073        {       
2074                VspInterior *interior = dynamic_cast<VspInterior *>(node);
2075       
2076                AxisAlignedPlane plane = interior->GetPlane();
2077                stream << "<Interior plane=\"" << plane.mPosition << " "
2078                           << plane.mAxis << "\">" << endl;
2079
2080                ExportNode(interior->GetBack(), stream);
2081                ExportNode(interior->GetFront(), stream);
2082
2083                stream << "</Interior>" << endl;
2084        }
2085}
2086
2087
2088int VspTree::SplitRays(const AxisAlignedPlane &plane,
2089                                           RayInfoContainer &rays,
2090                                           RayInfoContainer &frontRays,
2091                                           RayInfoContainer &backRays) const
2092{
2093        int splits = 0;
2094
2095        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2096
2097        for (rit = rays.begin(); rit != rit_end; ++ rit)
2098        {
2099                RayInfo bRay = *rit;
2100               
2101                VssRay *ray = bRay.mRay;
2102                float t;
2103
2104                // get classification and receive new t
2105                //-- test if start point behind or in front of plane
2106                const int side = plane.ComputeRayIntersection(bRay, t);
2107
2108                if (side == 0)
2109                {
2110                        ++ splits;
2111
2112                        if (ray->HasPosDir(plane.mAxis))
2113                        {
2114                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2115                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2116                        }
2117                        else
2118                        {
2119                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2120                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2121                        }
2122                }
2123                else if (side == 1)
2124                {
2125                        frontRays.push_back(bRay);
2126                }
2127                else
2128                {
2129                        backRays.push_back(bRay);
2130                }
2131
2132        }
2133
2134        return splits;
2135}
2136
2137
2138AxisAlignedBox3 VspTree::GetBBox(VspNode *node) const
2139{
2140        if (!node->GetParent())
2141                return mBoundingBox;
2142
2143        if (!node->IsLeaf())
2144        {
2145                return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();           
2146        }
2147
2148        VspInterior *parent = dynamic_cast<VspInterior *>(node->GetParent());
2149
2150        AxisAlignedBox3 box(parent->GetBoundingBox());
2151
2152        if (parent->GetFront() == node)
2153                box.SetMin(parent->GetAxis(), parent->GetPosition());
2154        else
2155                box.SetMax(parent->GetAxis(), parent->GetPosition());
2156
2157        return box;
2158}
2159
2160
2161
2162/*****************************************************************/
2163/*                class OpsTree implementation                   */
2164/*****************************************************************/
2165
2166
2167void OspTree::SplitObjects(const AxisAlignedPlane & splitPlane,
2168                                                   const ObjectContainer &objects,
2169                                                   ObjectContainer &back,
2170                                                   ObjectContainer &front)
2171{
2172        ObjectContainer::const_iterator oit, oit_end = objects.end();
2173
2174    for (oit = objects.begin(); oit != oit_end; ++ oit)
2175        {
2176                // determine the side of this ray with respect to the plane
2177                const AxisAlignedBox3 box = (*oit)->GetBox();
2178
2179                if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
2180            front.push_back(*oit);
2181   
2182                if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
2183                        back.push_back(*oit);
2184#if TODO   
2185                mStat.objectRefs -= (int)objects.size();
2186                mStat.objectRefs += objectsBack + objectsFront;
2187#endif
2188        }
2189}
2190
2191
2192KdInterior *OspTree::SubdivideNode(KdLeaf *leaf,
2193                                                                   const AxisAlignedPlane &splitPlane,
2194                                                                   const AxisAlignedBox3 &box,
2195                                                                   AxisAlignedBox3 &backBBox,
2196                                                                   AxisAlignedBox3 &frontBBox)
2197{
2198#if TODO
2199    mSpatialStat.nodes += 2;
2200        mSpatialStat.splits[axis];
2201#endif
2202
2203        // add the new nodes to the tree
2204        KdInterior *node = new KdInterior(leaf->mParent);
2205
2206        const int axis = splitPlane.mAxis;
2207        const float position = splitPlane.mPosition;
2208
2209        node->mAxis = axis;
2210        node->mPosition = position;
2211        node->mBox = box;
2212
2213    backBBox = box;
2214        frontBBox = box;
2215 
2216        // first count ray sides
2217        int objectsBack = 0;
2218        int objectsFront = 0;
2219 
2220        backBBox.SetMax(axis, position);
2221        frontBBox.SetMin(axis, position);
2222
2223        ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
2224
2225        for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
2226        {
2227                // determine the side of this ray with respect to the plane
2228                const AxisAlignedBox3 box = (*mi)->GetBox();
2229               
2230                if (box.Max(axis) > position)
2231                        ++ objectsFront;
2232   
2233                if (box.Min(axis) < position)
2234                        ++ objectsBack;
2235        }
2236
2237        KdLeaf *back = new KdLeaf(node, objectsBack);
2238        KdLeaf *front = new KdLeaf(node, objectsFront);
2239
2240        // replace a link from node's parent
2241        if (leaf->mParent)
2242                leaf->mParent->ReplaceChildLink(leaf, node);
2243
2244        // and setup child links
2245        node->SetupChildLinks(back, front);
2246
2247        SplitObjects(splitPlane, leaf->mObjects, back->mObjects, front->mObjects);
2248 
2249        //delete leaf;
2250        return node;
2251}
2252
2253
2254KdNode *OspTree::Subdivide(SplitQueue &tQueue,
2255                                                   OspSplitCandidate &splitCandidate,
2256                                                   const bool globalCriteriaMet)
2257{
2258        OspTraversalData &tData = splitCandidate.mParentData;
2259
2260        KdNode *newNode = tData.mNode;
2261
2262        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
2263        {       
2264                OspTraversalData tFrontData;
2265                OspTraversalData tBackData;
2266
2267                //-- continue subdivision
2268               
2269                // create new interior node and two leaf node
2270                const AxisAlignedPlane splitPlane = splitCandidate.mSplitPlane;
2271                newNode = SubdivideNode(dynamic_cast<KdLeaf *>(newNode),
2272                                                                splitPlane,
2273                                                                tData.mBoundingBox,
2274                                                                tFrontData.mBoundingBox,
2275                                                                tBackData.mBoundingBox);
2276       
2277                const int maxCostMisses = splitCandidate.mMaxCostMisses;
2278
2279                // how often was max cost ratio missed in this branch?
2280                tFrontData.mMaxCostMisses = maxCostMisses;
2281                tBackData.mMaxCostMisses = maxCostMisses;
2282                       
2283                //-- push the new split candidates on the queue
2284                OspSplitCandidate *frontCandidate = new OspSplitCandidate();
2285                OspSplitCandidate *backCandidate = new OspSplitCandidate();
2286
2287                EvalSplitCandidate(tFrontData, *frontCandidate);
2288                EvalSplitCandidate(tBackData, *backCandidate);
2289
2290                tQueue.push(frontCandidate);
2291                tQueue.push(backCandidate);
2292
2293                // delete old leaf node
2294                DEL_PTR(tData.mNode);
2295        }
2296
2297
2298        //-- terminate traversal
2299        if (newNode->IsLeaf())
2300        {
2301                //KdLeaf *leaf = dynamic_cast<KdLeaf *>(newNode);
2302                EvaluateLeafStats(tData);               
2303        }
2304
2305        //-- cleanup
2306        tData.Clear();
2307       
2308        return newNode;
2309}
2310
2311
2312void OspTree::EvalSplitCandidate(OspTraversalData &tData,
2313                                                                 OspSplitCandidate &splitData)
2314{
2315        float frontProb;
2316        float backtProb;
2317       
2318        KdLeaf *leaf = dynamic_cast<KdLeaf *>(tData.mNode);
2319
2320        // compute locally best split plane
2321        const bool success = false;
2322#if TODO
2323        SelectPlane(tData, splitData.mSplitPlane,
2324                                frontData.mProbability, backData.mProbability);
2325
2326        //TODO
2327        // compute global decrease in render cost
2328        splitData.mPriority = EvalRenderCostDecrease(splitData.mSplitPlane, tData);
2329        splitData.mParentData = tData;
2330        splitData.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
2331#endif
2332}
2333
2334
2335/*****************************************************************/
2336/*              class HierarchyManager implementation            */
2337/*****************************************************************/
2338
2339HierarchyManager::HierarchyManager()
2340{
2341}
2342
2343
2344SplitCandidate *HierarchyManager::NextSplitCandidate()
2345{
2346        SplitCandidate *splitCandidate = mTQueue.top();
2347        mTQueue.pop();
2348
2349        return splitCandidate;
2350}
2351
2352
2353void HierarchyManager::PrepareConstruction(const VssRayContainer &sampleRays,
2354                                                                                   AxisAlignedBox3 *forcedViewSpace,
2355                                                                                   RayInfoContainer &rays)
2356{
2357        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2358
2359        long startTime = GetTime();
2360
2361        cout << "storing rays ... ";
2362
2363        Intersectable::NewMail();
2364
2365        mVspTree->PrepareConstruction(sampleRays, forcedViewSpace);
2366
2367        //-- store rays
2368        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2369        {
2370                VssRay *ray = *rit;
2371
2372                float minT, maxT;
2373
2374                static Ray hray;
2375                hray.Init(*ray);
2376
2377                // TODO: not very efficient to implictly cast between rays types
2378                if (mBoundingBox.GetRaySegment(hray, minT, maxT))
2379                {
2380                        float len = ray->Length();
2381
2382                        if (!len)
2383                                len = Limits::Small;
2384
2385                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
2386                }
2387        }
2388
2389        cout << "finished" << endl;
2390
2391        //mOspTree->PrepareConstruction(sampleRays, forcedViewSpace, rays);
2392}
2393
2394
2395bool HierarchyManager::GlobalTerminationCriteriaMet(SplitCandidate *candidate) const
2396{
2397        if (candidate->Type() == SplitCandidate::VIEW_SPACE)
2398        {
2399                VspTree::VspSplitCandidate *sc =
2400                        dynamic_cast<VspTree::VspSplitCandidate *>(candidate);
2401               
2402                return mVspTree->GlobalTerminationCriteriaMet(sc->mParentData);
2403        }
2404
2405        return true;
2406}
2407
2408
2409void HierarchyManager::Construct(const VssRayContainer &sampleRays,
2410                                                                 const ObjectContainer &objects,
2411                                                                 AxisAlignedBox3 *forcedViewSpace)
2412{
2413        RayInfoContainer *rays = new RayInfoContainer();
2414       
2415        // prepare vsp and osp trees for traversal
2416        PrepareConstruction(sampleRays, forcedViewSpace, *rays);
2417
2418        mVspTree->mVspStats.Start();
2419
2420        cout << "Constructing view space / object space tree ... \n";
2421        const long startTime = GetTime();       
2422
2423        while (!FinishedConstruction())
2424        {
2425                SplitCandidate *splitCandidate = NextSplitCandidate();
2426           
2427                const bool globalTerminationCriteriaMet =
2428                        GlobalTerminationCriteriaMet(splitCandidate);
2429
2430                // cost ratio of cost decrease / totalCost
2431                const float costRatio = splitCandidate->GetPriority() / mTotalCost;
2432                //Debug << "cost ratio: " << costRatio << endl;
2433
2434                if (costRatio < mTermMinGlobalCostRatio)
2435                        ++ mGlobalCostMisses;
2436       
2437                //-- subdivide leaf node
2438                //-- either a object space or view space split
2439                if (splitCandidate->Type() == SplitCandidate::VIEW_SPACE)
2440                {
2441                        VspTree::VspSplitCandidate *sc =
2442                                dynamic_cast<VspTree::VspSplitCandidate *>(splitCandidate);
2443
2444                        VspNode *r = mVspTree->Subdivide(mTQueue, *sc, globalTerminationCriteriaMet);
2445                }
2446                else // object space split
2447                {
2448#if TODO
2449                        KdNode *r = mKdtree->Subdivide(tOspQueue, dynamic_cast<OspSplitCandidate<(splitCandidate));
2450#endif
2451                }
2452
2453                DEL_PTR(splitCandidate);
2454        }
2455
2456        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
2457
2458        mVspTree->mVspStats.Stop();
2459}
2460
2461
2462bool HierarchyManager::FinishedConstruction()
2463{
2464        return mTQueue.empty();
2465}
2466
2467
2468}
Note: See TracBrowser for help on using the repository browser.