source: GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp @ 1251

Revision 1251, 69.1 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "ViewCell.h"
6#include "Plane3.h"
7#include "VspTree.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 "OspTree.h"
21
22namespace GtpVisibilityPreprocessor {
23
24
25#define USE_FIXEDPOINT_T 0
26
27
28//-- static members
29
30VspTree *VspTree::VspSubdivisionCandidate::sVspTree = NULL;
31
32
33// variable for debugging volume contribution for heuristics
34static float debugVol;
35
36int VspNode::sMailId = 1;
37
38// pvs penalty can be different from pvs size
39inline static float EvalPvsPenalty(const int pvs,
40                                                                   const int lower,
41                                                                   const int upper)
42{
43        // clamp to minmax values
44        if (pvs < lower)
45        {
46                return (float)lower;
47        }
48        else if (pvs > upper)
49        {
50                return (float)upper;
51        }
52
53        return (float)pvs;
54}
55
56
57static bool ViewCellHasMultipleReferences(Intersectable *obj,
58                                                                                  ViewCell *vc,
59                                                                                  bool checkOnlyMailed)
60{
61        MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
62//return false;
63        if (vdata)
64        {
65                // more than one view cell sees this object inside different kd cells
66                if (!checkOnlyMailed || !vdata->Mailed())
67                {
68                        if (checkOnlyMailed)
69                                vdata->Mail();
70                        //Debug << "sumpdf: " << vdata->mSumPdf << endl;
71                        if (vdata->mSumPdf > 1.5f)
72                                return true;
73                }
74        }
75
76        return false;
77}
78
79
80void VspTreeStatistics::Print(ostream &app) const
81{
82        app << "=========== VspTree statistics ===============\n";
83
84        app << setprecision(4);
85
86        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
87
88        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
89
90        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
91
92        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
93
94        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
95
96        app << "#N_SPLITS ( Number of splits in axes x y z)\n";
97
98        for (int i = 0; i < 3; ++ i)
99                app << splits[i] << " ";
100        app << endl;
101
102        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
103                <<      maxDepthNodes * 100 / (double)Leaves() << endl;
104
105        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n"
106                << minPvsNodes * 100 / (double)Leaves() << endl;
107
108        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n"
109                << minRaysNodes * 100 / (double)Leaves() << endl;
110
111        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
112                << maxCostNodes * 100 / (double)Leaves() << endl;
113
114        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
115                << minProbabilityNodes * 100 / (double)Leaves() << endl;
116
117        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n"
118                <<      maxRayContribNodes * 100 / (double)Leaves() << endl;
119
120        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
121
122        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
123
124        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
125
126        app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
127
128        app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
129        //app << "#N_PVS: " << pvs << endl;
130
131        //app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" << maxObjectRefs << "\n";
132
133        app << "========== END OF VspTree statistics ==========\n";
134}
135
136
137
138/******************************************************************/
139/*                  class VspNode implementation                  */
140/******************************************************************/
141
142
143VspNode::VspNode():
144mParent(NULL), mTreeValid(true), mTimeStamp(0)
145{}
146
147
148VspNode::VspNode(VspInterior *parent):
149mParent(parent), mTreeValid(true)
150{}
151
152
153bool VspNode::IsRoot() const
154{
155        return mParent == NULL;
156}
157
158
159VspInterior *VspNode::GetParent()
160{
161        return mParent;
162}
163
164
165void VspNode::SetParent(VspInterior *parent)
166{
167        mParent = parent;
168}
169
170
171bool VspNode::IsSibling(VspNode *n) const
172{
173        return  ((this != n) && mParent &&
174                         (mParent->GetFront() == n) || (mParent->GetBack() == n));
175}
176
177
178int VspNode::GetDepth() const
179{
180        int depth = 0;
181        VspNode *p = mParent;
182       
183        while (p)
184        {
185                p = p->mParent;
186                ++ depth;
187        }
188
189        return depth;
190}
191
192
193bool VspNode::TreeValid() const
194{
195        return mTreeValid;
196}
197
198
199void VspNode::SetTreeValid(const bool v)
200{
201        mTreeValid = v;
202}
203
204
205/****************************************************************/
206/*              class VspInterior implementation                */
207/****************************************************************/
208
209
210VspInterior::VspInterior(const AxisAlignedPlane &plane):
211mPlane(plane), mFront(NULL), mBack(NULL)
212{}
213
214
215VspInterior::~VspInterior()
216{
217        DEL_PTR(mFront);
218        DEL_PTR(mBack);
219}
220
221
222bool VspInterior::IsLeaf() const
223{
224        return false;
225}
226
227
228VspNode *VspInterior::GetBack()
229{
230        return mBack;
231}
232
233
234VspNode *VspInterior::GetFront()
235{
236        return mFront;
237}
238
239
240AxisAlignedPlane VspInterior::GetPlane() const
241{
242        return mPlane;
243}
244
245
246float VspInterior::GetPosition() const
247{
248        return mPlane.mPosition;
249}
250
251
252int VspInterior::GetAxis() const
253{
254        return mPlane.mAxis;
255}
256
257
258void VspInterior::ReplaceChildLink(VspNode *oldChild, VspNode *newChild)
259{
260        if (mBack == oldChild)
261                mBack = newChild;
262        else
263                mFront = newChild;
264}
265
266
267void VspInterior::SetupChildLinks(VspNode *front, VspNode *back)
268{
269    mBack = back;
270    mFront = front;
271}
272
273
274AxisAlignedBox3 VspInterior::GetBoundingBox() const
275{
276        return mBoundingBox;
277}
278
279
280void VspInterior::SetBoundingBox(const AxisAlignedBox3 &box)
281{
282        mBoundingBox = box;
283}
284
285
286int VspInterior::Type() const
287{
288        return Interior;
289}
290
291
292
293/****************************************************************/
294/*                  class VspLeaf implementation                */
295/****************************************************************/
296
297
298VspLeaf::VspLeaf(): mViewCell(NULL), mPvs(NULL)
299{
300}
301
302
303VspLeaf::~VspLeaf()
304{
305        DEL_PTR(mPvs);
306        CLEAR_CONTAINER(mVssRays);
307}
308
309
310int VspLeaf::Type() const
311{
312        return Leaf;
313}
314
315
316VspLeaf::VspLeaf(ViewCellLeaf *viewCell):
317mViewCell(viewCell)
318{
319}
320
321
322VspLeaf::VspLeaf(VspInterior *parent):
323VspNode(parent), mViewCell(NULL), mPvs(NULL)
324{}
325
326
327
328VspLeaf::VspLeaf(VspInterior *parent, ViewCellLeaf *viewCell):
329VspNode(parent), mViewCell(viewCell), mPvs(NULL)
330{
331}
332
333ViewCellLeaf *VspLeaf::GetViewCell() const
334{
335        return mViewCell;
336}
337
338void VspLeaf::SetViewCell(ViewCellLeaf *viewCell)
339{
340        mViewCell = viewCell;
341}
342
343
344bool VspLeaf::IsLeaf() const
345{
346        return true;
347}
348
349
350/*************************************************************************/
351/*                       class VspTree implementation                    */
352/*************************************************************************/
353
354
355VspTree::VspTree():
356mRoot(NULL),
357mOutOfBoundsCell(NULL),
358mStoreRays(false),
359mTimeStamp(1),
360mOspTree(NULL)
361{
362        bool randomize = false;
363        Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
364        if (randomize)
365                Randomize(); // initialise random generator for heuristics
366
367        //-- termination criteria for autopartition
368        Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxDepth", mTermMaxDepth);
369        Environment::GetSingleton()->GetIntValue("VspTree.Termination.minPvs", mTermMinPvs);
370        Environment::GetSingleton()->GetIntValue("VspTree.Termination.minRays", mTermMinRays);
371        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minProbability", mTermMinProbability);
372        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxRayContribution", mTermMaxRayContribution);
373       
374        Environment::GetSingleton()->GetIntValue("VspTree.Termination.missTolerance", mTermMissTolerance);
375        Environment::GetSingleton()->GetIntValue("VspTree.Termination.maxViewCells", mMaxViewCells);
376
377        //-- max cost ratio for early tree termination
378        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.maxCostRatio", mTermMaxCostRatio);
379
380        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
381        Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
382
383        //-- factors for bsp tree split plane heuristics
384        Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
385
386        //-- partition criteria
387        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.epsilon", mEpsilon);
388        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
389
390        // if only the driving axis is used for axis aligned split
391        Environment::GetSingleton()->GetBoolValue("VspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
392       
393        Environment::GetSingleton()->GetIntValue("VspTree.maxTests", mMaxTests);
394        Environment::GetSingleton()->GetFloatValue("VspTree.maxStaticMemory", mMaxMemory);
395
396        Environment::GetSingleton()->GetBoolValue("VspTree.useCostHeuristics", mUseCostHeuristics);
397        Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
398       
399        Environment::GetSingleton()->GetBoolValue("VspTree.useKdPvsForHeuristics", mUseKdPvsForHeuristics);
400
401        char subdivisionStatsLog[100];
402        Environment::GetSingleton()->GetStringValue("VspTree.subdivisionStats", subdivisionStatsLog);
403        mSubdivisionStats.open(subdivisionStatsLog);
404
405        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.minBand", mMinBand);
406        Environment::GetSingleton()->GetFloatValue("VspTree.Construction.maxBand", mMaxBand);
407       
408
409        //-- debug output
410
411        Debug << "******* VSP options ******** " << endl;
412
413    Debug << "max depth: " << mTermMaxDepth << endl;
414        Debug << "min PVS: " << mTermMinPvs << endl;
415        Debug << "min probabiliy: " << mTermMinProbability << endl;
416        Debug << "min rays: " << mTermMinRays << endl;
417        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
418        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
419        Debug << "miss tolerance: " << mTermMissTolerance << endl;
420        Debug << "max view cells: " << mMaxViewCells << endl;
421        Debug << "randomize: " << randomize << endl;
422
423        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
424        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
425        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
426        Debug << "max memory: " << mMaxMemory << endl;
427        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
428        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
429        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
430
431        Debug << "circulating axis: " << mCirculatingAxis << endl;
432        Debug << "minband: " << mMinBand << endl;
433        Debug << "maxband: " << mMaxBand << endl;
434
435        if (!mUseKdPvsForHeuristics)
436                Debug << "pvs heuristics: per object" << endl;
437        else
438                Debug << "pvs heuristics: per kd node" << endl;
439
440        mLocalSubdivisionCandidates = new vector<SortableEntry>;
441
442        Debug << endl;
443}
444
445
446VspViewCell *VspTree::GetOutOfBoundsCell()
447{
448        return mOutOfBoundsCell;
449}
450
451
452VspViewCell *VspTree::GetOrCreateOutOfBoundsCell()
453{
454        if (!mOutOfBoundsCell)
455        {
456                mOutOfBoundsCell = new VspViewCell();
457                mOutOfBoundsCell->SetId(-1);
458                mOutOfBoundsCell->SetValid(false);
459        }
460
461        return mOutOfBoundsCell;
462}
463
464
465const VspTreeStatistics &VspTree::GetStatistics() const
466{
467        return mVspStats;
468}
469
470
471VspTree::~VspTree()
472{
473        DEL_PTR(mRoot);
474        DEL_PTR(mLocalSubdivisionCandidates);
475}
476
477
478void VspTree::ComputeBoundingBox(const VssRayContainer &rays,
479                                                                 AxisAlignedBox3 *forcedBoundingBox)
480{       
481        if (forcedBoundingBox)
482        {
483                mBoundingBox = *forcedBoundingBox;
484        }
485        else // compute vsp tree bounding box
486        {
487                mBoundingBox.Initialize();
488                VssRayContainer::const_iterator rit, rit_end = rays.end();
489
490                //-- compute bounding box
491        for (rit = rays.begin(); rit != rit_end; ++ rit)
492                {
493                        VssRay *ray = *rit;
494
495                        // compute bounding box of view space
496                        mBoundingBox.Include(ray->GetTermination());
497                        mBoundingBox.Include(ray->GetOrigin());
498                }
499        }
500}
501
502
503void VspTree::AddSubdivisionStats(const int viewCells,
504                                                                  const float renderCostDecr,
505                                                                  const float totalRenderCost,
506                                                                  const float avgRenderCost)
507{
508        mSubdivisionStats
509                        << "#ViewCells\n" << viewCells << endl
510                        << "#RenderCostDecrease\n" << renderCostDecr << endl
511                        << "#TotalRenderCost\n" << totalRenderCost << endl
512                        << "#AvgRenderCost\n" << avgRenderCost << endl;
513}
514
515
516// TODO: return memory usage in MB
517float VspTree::GetMemUsage() const
518{
519        return (float)
520                 (sizeof(VspTree) +
521                  mVspStats.Leaves() * sizeof(VspLeaf) +
522                  mCreatedViewCells * sizeof(VspViewCell) +
523                  mVspStats.pvs * sizeof(PvsData) +
524                  mVspStats.Interior() * sizeof(VspInterior) +
525                  mVspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
526}
527
528
529inline bool VspTree::LocalTerminationCriteriaMet(const VspTraversalData &data) const
530{
531        const bool localTerminationCriteriaMet = (
532                ((int)data.mRays->size() <= mTermMinRays) ||
533                (data.mPvs <= mTermMinPvs)   ||
534                (data.mProbability <= mTermMinProbability) ||
535                (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
536                (data.mDepth >= mTermMaxDepth)
537                );
538
539        if (0 && localTerminationCriteriaMet)
540        {
541                Debug << "********local termination *********" << endl;
542                Debug << "rays: " << (int)data.mRays->size() << "  " << mTermMinRays << endl;
543                Debug << "pvs: " << data.mPvs << " " << mTermMinPvs << endl;
544                Debug << "p: " <<  data.mProbability << " " << mTermMinProbability << endl;
545                Debug << "avg contri: " << data.GetAvgRayContribution() << " " << mTermMaxRayContribution << endl;
546                Debug << "depth " << data.mDepth << " " << mTermMaxDepth << endl;
547        }
548
549        return localTerminationCriteriaMet;
550               
551}
552
553
554inline bool VspTree::GlobalTerminationCriteriaMet(const VspTraversalData &data) const
555{
556        const bool terminationCriteriaMet = (
557                // mOutOfMemory ||
558                (mVspStats.Leaves() >= mMaxViewCells) ||
559        (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
560                );
561
562        if (0 && terminationCriteriaMet)
563        {
564                Debug << "********* terminationCriteriaMet *********" << endl;
565                Debug << "cost misses: " << mGlobalCostMisses << " " << mTermGlobalCostMissTolerance << endl;
566                Debug << "leaves: " << mVspStats.Leaves() << " " <<  mMaxViewCells << endl;
567        }
568        return terminationCriteriaMet;
569}
570
571
572void VspTree::CreateViewCell(VspTraversalData &tData, const bool updatePvs)
573{
574        //-- create new view cell
575        VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
576       
577        VspViewCell *viewCell = new VspViewCell();
578    leaf->SetViewCell(viewCell);
579       
580        int conSamp = 0;
581        float sampCon = 0.0f;
582
583        if (updatePvs)
584        {
585                //-- update pvs of view cell
586                AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
587
588                // update scalar pvs size value
589                ObjectPvs &pvs = viewCell->GetPvs();
590                mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
591
592                mVspStats.contributingSamples += conSamp;
593                mVspStats.sampleContributions += (int)sampCon;
594        }
595
596
597        //-- store additional info
598        if (mStoreRays)
599        {
600                RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
601
602                for (it = tData.mRays->begin(); it != it_end; ++ it)
603                {
604                        (*it).mRay->Ref();                     
605                        leaf->mVssRays.push_back((*it).mRay);
606                }
607        }
608               
609        // set view cell values
610        viewCell->mLeaf = leaf;
611
612        viewCell->SetVolume(tData.mProbability);
613    leaf->mProbability = tData.mProbability;
614}
615
616
617void VspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
618{
619        const float costDecr = sc.GetRenderCostDecrease();
620       
621        AddSubdivisionStats(mVspStats.Leaves(),
622                                                costDecr,
623                                                mTotalCost,
624                                                (float)mTotalPvsSize / (float)mVspStats.Leaves());
625}
626
627
628VspNode *VspTree::Subdivide(SplitQueue &tQueue,
629                                                        SubdivisionCandidate *splitCandidate,
630                                                        const bool globalCriteriaMet)
631{
632        // todo remove dynamic cast
633        VspSubdivisionCandidate *sc = dynamic_cast<VspSubdivisionCandidate *>(splitCandidate);
634        VspTraversalData &tData = sc->mParentData;
635
636        VspNode *newNode = tData.mNode;
637
638
639        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
640        {       
641                VspTraversalData tFrontData;
642                VspTraversalData tBackData;
643
644                //-- continue subdivision
645               
646                // create new interior node and two leaf node
647                const AxisAlignedPlane splitPlane = sc->mSplitPlane;
648                newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData);
649       
650                const int maxCostMisses = sc->mMaxCostMisses;
651
652
653                // how often was max cost ratio missed in this branch?
654                tFrontData.mMaxCostMisses = maxCostMisses;
655                tBackData.mMaxCostMisses = maxCostMisses;
656                       
657                mTotalCost -= sc->GetRenderCostDecrease();
658                mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
659
660                // subdivision statistics
661                if (1) EvalSubdivisionStats(*sc);
662               
663                //-- evaluate new split candidates for global greedy cost heuristics
664
665                VspSubdivisionCandidate *frontCandidate = new VspSubdivisionCandidate(tFrontData);
666                VspSubdivisionCandidate *backCandidate = new VspSubdivisionCandidate(tBackData);
667
668                EvalSubdivisionCandidate(*frontCandidate);
669                EvalSubdivisionCandidate(*backCandidate);
670
671                tQueue.Push(frontCandidate);
672                tQueue.Push(backCandidate);
673               
674                // delete old view cell
675                delete tData.mNode->mViewCell;
676
677                // delete old leaf node
678                DEL_PTR(tData.mNode);
679        }
680
681        if (newNode->IsLeaf()) // subdivision terminated
682        {
683                // view cell is created during subdivision
684                //CreateViewCell(tData);
685
686                VspLeaf *leaf = dynamic_cast<VspLeaf *>(newNode);
687                ViewCell *viewCell = leaf->GetViewCell();
688
689                int conSamp = 0;
690                float sampCon = 0.0f;
691
692#if 0
693                //-- store pvs optained from rays
694
695                AddSamplesToPvs(leaf, *tData.mRays, sampCon, conSamp);
696
697                // update scalar pvs size value
698                ObjectPvs &pvs = viewCell->GetPvs();
699                mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
700
701                mVspStats.contributingSamples += conSamp;
702                mVspStats.sampleContributions += (int)sampCon;
703#endif
704                //-- store additional info
705                if (mStoreRays)
706                {
707                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
708                        for (it = tData.mRays->begin(); it != it_end; ++ it)
709                        {
710                                (*it).mRay->Ref();                     
711                                leaf->mVssRays.push_back((*it).mRay);
712                        }
713                }
714
715                // finally evaluate statistics for this leaf
716                EvaluateLeafStats(tData);
717        }
718
719        //-- cleanup
720        tData.Clear();
721       
722        return newNode;
723}
724
725
726void VspTree::EvalSubdivisionCandidate(VspSubdivisionCandidate &splitCandidate)
727{
728        float frontProb;
729        float backProb;
730       
731        VspLeaf *leaf = dynamic_cast<VspLeaf *>(splitCandidate.mParentData.mNode);
732       
733        // compute locally best split plane
734        const float ratio = SelectSplitPlane(
735                splitCandidate.mParentData,
736                splitCandidate.mSplitPlane,
737                frontProb,
738                backProb);
739
740        const bool success = ratio < mTermMaxCostRatio;
741
742        float oldRenderCost;
743
744        // compute global decrease in render cost
745        const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
746                                                                                                                splitCandidate.mParentData,
747                                                                                                                oldRenderCost);
748
749        splitCandidate.SetRenderCostDecrease(renderCostDecr);
750
751#if 0
752        const float priority = (float)-data.mDepth;
753#else   
754
755        // take render cost of node into account
756        // otherwise danger of being stuck in a local minimum!!
757        const float factor = mRenderCostDecreaseWeight;
758        const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
759#endif
760       
761        splitCandidate.SetPriority(priority);
762
763        // max cost threshold violated?
764        splitCandidate.mMaxCostMisses =
765                success ? splitCandidate.mParentData.mMaxCostMisses : splitCandidate.mParentData.mMaxCostMisses + 1;
766        //Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
767}
768
769
770VspInterior *VspTree::SubdivideNode(const AxisAlignedPlane &splitPlane,
771                                                                        VspTraversalData &tData,
772                                                                        VspTraversalData &frontData,
773                                                                        VspTraversalData &backData)
774{
775        VspLeaf *leaf = dynamic_cast<VspLeaf *>(tData.mNode);
776       
777        //-- the front and back traversal data is filled with the new values
778
779        frontData.mDepth = tData.mDepth + 1;
780        backData.mDepth = tData.mDepth + 1;
781
782        frontData.mRays = new RayInfoContainer();
783        backData.mRays = new RayInfoContainer();
784
785        //-- subdivide rays
786        SplitRays(splitPlane,
787                          *tData.mRays,
788                          *frontData.mRays,
789                          *backData.mRays);
790       
791        //Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
792
793        //-- compute pvs
794        frontData.mPvs = EvalPvsSize(*frontData.mRays);
795        backData.mPvs = EvalPvsSize(*backData.mRays);
796
797        // split front and back node geometry and compute area
798        tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
799                                                         frontData.mBoundingBox, backData.mBoundingBox);
800
801
802        frontData.mProbability = frontData.mBoundingBox.GetVolume();
803        backData.mProbability = tData.mProbability - frontData.mProbability;
804
805       
806    ///////////////////////////////////////////
807        // subdivide further
808
809        // store maximal and minimal depth
810        if (tData.mDepth > mVspStats.maxDepth)
811        {
812                Debug << "max depth increases to " << tData.mDepth << " at " << mVspStats.Leaves() << " leaves" << endl;
813                mVspStats.maxDepth = tData.mDepth;
814        }
815
816        // two more leaves
817        mVspStats.nodes += 2;
818   
819        VspInterior *interior = new VspInterior(splitPlane);
820
821#ifdef _DEBUG
822        Debug << interior << endl;
823#endif+
824
825
826        //-- create front and back leaf
827
828        VspInterior *parent = leaf->GetParent();
829
830        // replace a link from node's parent
831        if (parent)
832        {
833                parent->ReplaceChildLink(leaf, interior);
834                interior->SetParent(parent);
835
836                // remove "parent" view cell from pvs of all objects (traverse trough rays)
837                RemoveParentViewCellReferences(tData.mNode->GetViewCell());
838        }
839        else // new root
840        {
841                mRoot = interior;
842        }
843
844        VspLeaf *frontLeaf = new VspLeaf(interior);
845        VspLeaf *backLeaf = new VspLeaf(interior);
846
847        // and setup child links
848        interior->SetupChildLinks(frontLeaf, backLeaf);
849       
850        // add bounding box
851        interior->SetBoundingBox(tData.mBoundingBox);
852
853        // set front and back leaf
854        frontData.mNode = frontLeaf;
855        backData.mNode = backLeaf;
856
857        // explicitely create front and back view cell
858        CreateViewCell(frontData, false);
859        CreateViewCell(backData, false);
860
861
862#if WORK_WITH_VIEWCELL_PVS
863        // create front and back view cell
864        // add front and back view cell to "Potentially Visbilie View Cells"
865        // of the objects in front and back pvs
866
867        AddViewCellReferences(frontLeaf->GetViewCell());
868        AddViewCellReferences(backLeaf->GetViewCell());
869#endif
870
871        interior->mTimeStamp = mTimeStamp ++;
872       
873        return interior;
874}
875
876
877void VspTree::RemoveParentViewCellReferences(ViewCell *parent) const
878{
879        KdLeaf::NewMail();
880
881        // remove the parents from the object pvss
882        ObjectPvsMap::const_iterator oit, oit_end = parent->GetPvs().mEntries.end();
883
884        for (oit = parent->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
885        {
886                Intersectable *object = (*oit).first;
887                // HACK: make sure that the view cell is removed from the pvs
888                const float high_contri = 9999999;
889
890                // remove reference count of view cells
891                object->mViewCellPvs.RemoveSample(parent, high_contri);
892        }
893}
894
895
896void VspTree::AddViewCellReferences(ViewCell *vc) const
897{
898        KdLeaf::NewMail();
899
900        // Add front view cell to the object pvsss
901        ObjectPvsMap::const_iterator oit, oit_end = vc->GetPvs().mEntries.end();
902
903        for (oit = vc->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
904        {
905                Intersectable *object = (*oit).first;
906
907                // increase reference count of view cells
908                object->mViewCellPvs.AddSample(vc, 1);
909        }
910}
911
912
913bool VspTree::AddKdLeafToPvs(KdLeaf *leaf,
914                                                         ViewCell *vc,
915                                                         const float pdf,
916                                                         float &contribution)
917{
918        bool contri = false;
919
920#if 1 // add kd intersecable to pvs
921        KdIntersectable *kdObj = mOspTree->GetOrCreateKdIntersectable(leaf);
922       
923        if (vc->AddPvsSample(kdObj, pdf, contribution))
924        {
925                return true;
926        }
927
928#else // add all objects of kd node
929
930        contribution = 0;
931
932        ObjectContainer::const_iterator it, it_end = leaf->mObjects.end();
933
934        for (it = leaf->mObjects.begin(); it != it_end; ++ it)
935        {
936                Intersectable *object = *it;                                           
937
938                float newcontri;
939                                               
940                if (vc->AddPvsSample(object, pdf, newcontri))
941                {
942                        contri = true;
943                }
944
945                //pdf += newPdf;
946                newContri += contribution;
947        }
948#endif
949
950        return contri;
951}
952
953
954void VspTree::AddSamplesToPvs(VspLeaf *leaf,
955                                                          const RayInfoContainer &rays,
956                                                          float &sampleContributions,
957                                                          int &contributingSamples)
958{
959        sampleContributions = 0;
960        contributingSamples = 0;
961 
962        RayInfoContainer::const_iterator it, it_end = rays.end();
963 
964        ViewCellLeaf *vc = leaf->GetViewCell();
965
966        // add contributions from samples to the PVS
967        for (it = rays.begin(); it != it_end; ++ it)
968        {
969                float sc = 0.0f;
970                VssRay *ray = (*it).mRay;
971
972                bool madeContrib = false;
973                float contribution;
974
975                Intersectable *obj = ray->mTerminationObject;
976
977                if (obj)
978                {
979                        if (!mStoreKdPvs)
980                        {
981                                // potentially visible objects
982                                madeContrib = vc->AddPvsSample(obj, ray->mPdf, contribution);
983                        }
984                        else
985                        {
986                                // potentially visible kd cells
987                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);       
988                                madeContrib = AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
989                        }       
990
991                        sc += contribution;
992                }
993
994                obj = ray->mOriginObject;
995
996                if (obj)
997                {
998                        if (!mStoreKdPvs)
999                        {
1000                                // potentially visible objects
1001                                madeContrib = vc->AddPvsSample(obj, ray->mPdf, contribution);
1002                        }
1003                        else
1004                        {
1005                                // potentially visible kd cells
1006                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);       
1007                                madeContrib = AddKdLeafToPvs(leaf, vc, ray->mPdf, contribution);
1008                        }       
1009
1010                        sc += contribution;
1011                }
1012
1013                if (madeContrib)
1014                {
1015                        ++ contributingSamples;
1016                }
1017
1018                // store rays for visualization
1019                if (0) leaf->mVssRays.push_back(new VssRay(*ray));
1020        }
1021}
1022
1023
1024void VspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
1025                                                                  const int axis,
1026                                                                  float minBand,
1027                                                                  float maxBand)
1028{
1029        mLocalSubdivisionCandidates->clear();
1030
1031        int requestedSize = 2 * (int)(rays.size());
1032
1033        // creates a sorted split candidates array
1034        if (mLocalSubdivisionCandidates->capacity() > 500000 &&
1035                requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
1036        {
1037        delete mLocalSubdivisionCandidates;
1038                mLocalSubdivisionCandidates = new vector<SortableEntry>;
1039        }
1040
1041        mLocalSubdivisionCandidates->reserve(requestedSize);
1042
1043
1044        float pos;
1045
1046        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1047
1048        //-- insert all queries
1049        for (rit = rays.begin(); rit != rit_end; ++ rit)
1050        {
1051                const bool positive = (*rit).mRay->HasPosDir(axis);
1052                               
1053                pos = (*rit).ExtrapOrigin(axis);
1054               
1055                mLocalSubdivisionCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
1056                                                                        pos, (*rit).mRay));
1057
1058                pos = (*rit).ExtrapTermination(axis);
1059
1060                mLocalSubdivisionCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
1061                                                                        pos, (*rit).mRay));
1062        }
1063
1064        stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
1065}
1066
1067
1068int VspTree::GetPvsContribution(Intersectable *object) const
1069{
1070    int pvsContri = 0;
1071
1072        KdPvsMap::const_iterator kit, kit_end = object->mKdPvs.mEntries.end();
1073
1074        Intersectable::NewMail();
1075
1076        // Search kd leaves this object is attached to
1077        for (kit = object->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
1078        {
1079                KdNode *l = (*kit).first;
1080
1081                // new object found during sweep
1082                // => increase pvs contribution of this kd node
1083                if (!l->Mailed())
1084                {
1085                        l->Mail();
1086                        ++ pvsContri;
1087                }
1088        }
1089
1090        return pvsContri;
1091}
1092
1093
1094int VspTree::PrepareHeuristics(KdLeaf *leaf)
1095{       
1096        int pvsSize = 0;
1097       
1098        if (!leaf->Mailed())
1099        {
1100                leaf->Mail();
1101                leaf->mCounter = 1;
1102
1103                // add objects without the objects which are in several kd leaves
1104                pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1105                //Debug << "adding " << (int)leaf->mObjects.size() << " " << leaf->mMultipleObjects.size() << endl;
1106        }
1107        else
1108        {
1109                ++ leaf->mCounter;
1110        }
1111
1112        //-- the objects belonging to several leaves must be handled seperately
1113
1114        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1115
1116        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1117        {
1118                Intersectable *object = *oit;
1119                                               
1120                if (!object->Mailed())
1121                {
1122                        object->Mail();
1123                        object->mCounter = 1;
1124
1125                        ++ pvsSize;
1126                }
1127                else
1128                {
1129                        ++ object->mCounter;
1130                }
1131        }
1132       
1133        return pvsSize;
1134}
1135
1136
1137int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
1138{       
1139        Intersectable::NewMail();
1140        KdNode::NewMail();
1141
1142        int pvsSize = 0;
1143
1144        RayInfoContainer::const_iterator ri, ri_end = rays.end();
1145
1146        //-- set all kd nodes / objects as belonging to the front pvs
1147
1148        for (ri = rays.begin(); ri != ri_end; ++ ri)
1149        {
1150                VssRay *ray = (*ri).mRay;
1151                Intersectable *oObject = ray->mOriginObject;
1152
1153                if (oObject)
1154                {
1155                        if (!mUseKdPvsForHeuristics)
1156                        {
1157                                if (!oObject->Mailed())
1158                                {
1159                                        oObject->Mail();
1160                                        oObject->mCounter = 1;
1161
1162                                        ++ pvsSize;
1163                                }
1164                                else
1165                                {
1166                                        ++ oObject->mCounter;
1167                                }
1168                        }
1169                        else
1170                        {
1171                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
1172                                pvsSize += PrepareHeuristics(leaf);     
1173                        }       
1174                }
1175
1176                Intersectable *tObject = (*ri).mRay->mTerminationObject;
1177
1178                if (tObject)
1179                {
1180                        if (!mUseKdPvsForHeuristics)
1181                        {
1182                                if (!tObject->Mailed())
1183                                {
1184                                        tObject->Mail();
1185                                        tObject->mCounter = 1;
1186                                        ++ pvsSize;
1187                                }
1188                                else
1189                                {
1190                                        ++ tObject->mCounter;
1191                                }
1192                        }
1193                        else
1194                        {
1195                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
1196                                pvsSize += PrepareHeuristics(leaf);     
1197                        }       
1198                }
1199        }
1200
1201        return pvsSize;
1202}
1203
1204
1205void VspTree::RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const
1206{
1207        // leaf falls out of right pvs
1208        if (-- leaf->mCounter == 0)
1209        {
1210                pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1211        }
1212
1213        //-- handle objects which are in several kd leaves separately
1214        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1215
1216        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1217        {
1218                Intersectable *object = *oit;
1219
1220                if (-- object->mCounter == 0)
1221                {
1222                        -- pvs;
1223                }
1224        }
1225}
1226
1227
1228void VspTree::AddContriToPvs(KdLeaf *leaf, int &pvs) const
1229{
1230        if (leaf->Mailed())
1231                return;
1232       
1233        leaf->Mail();
1234
1235        // add objects without those which are part of several kd leaves
1236        pvs += ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
1237
1238        //-- handle objects of several kd leaves separately
1239        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1240
1241        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1242        {
1243                Intersectable *object = *oit;
1244
1245                // object not previously in pvs
1246                if (!object->Mailed())
1247                {
1248                        object->Mail();
1249                        ++ pvs;
1250                }
1251        }                                       
1252}
1253
1254
1255void VspTree::EvalPvsIncr(const SortableEntry &ci,
1256                                                  int &pvsLeft,
1257                                                  int &pvsRight) const
1258{
1259        VssRay *ray = ci.ray;
1260
1261        Intersectable *oObject = ray->mOriginObject;
1262        Intersectable *tObject = ray->mTerminationObject;
1263
1264        if (oObject)
1265        {       
1266                if (!mUseKdPvsForHeuristics)
1267                {
1268                        if (ci.type == SortableEntry::ERayMin)
1269                        {
1270                                if (!oObject->Mailed())
1271                                {
1272                                        oObject->Mail();
1273                                        ++ pvsLeft;
1274                                }
1275                        }
1276                        else if (ci.type == SortableEntry::ERayMax)
1277                        {
1278                                if (-- oObject->mCounter == 0)
1279                                        -- pvsRight;
1280                        }
1281                }
1282                else // per kd node
1283                {
1284                        KdLeaf *node = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
1285
1286                        // add contributions of the kd nodes
1287                        if (ci.type == SortableEntry::ERayMin)
1288                        {
1289                                AddContriToPvs(node, pvsLeft);
1290                        }
1291                        else if (ci.type == SortableEntry::ERayMax)
1292                        {
1293                                RemoveContriFromPvs(node, pvsRight);
1294                        }
1295                }
1296        }
1297       
1298        if (tObject)
1299        {       
1300                if (!mUseKdPvsForHeuristics)
1301                {
1302                        if (ci.type == SortableEntry::ERayMin)
1303                        {
1304                                if (!tObject->Mailed())
1305                                {
1306                                        tObject->Mail();
1307                                        ++ pvsLeft;
1308                                }
1309                        }
1310                        else if (ci.type == SortableEntry::ERayMax)
1311                        {
1312                                if (-- tObject->mCounter == 0)
1313                                        -- pvsRight;
1314                        }
1315                }
1316                else // per kd node
1317                {
1318                        KdLeaf *node = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
1319
1320                        if (ci.type == SortableEntry::ERayMin)
1321                        {
1322                                AddContriToPvs(node, pvsLeft);
1323                        }
1324                        else if (ci.type == SortableEntry::ERayMax)
1325                        {
1326                                RemoveContriFromPvs(node, pvsRight);
1327                        }
1328                }
1329        }
1330}
1331
1332
1333float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
1334                                                                           const AxisAlignedBox3 &box,
1335                                                                           const int axis,
1336                                                                           float &position)
1337{
1338        RayInfoContainer usedRays;
1339
1340        if (mMaxTests < (int)tData.mRays->size())
1341        {
1342                GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
1343        }
1344        else
1345        {
1346                usedRays = *tData.mRays;
1347        }
1348
1349        int pvsSize = tData.mPvs;
1350
1351        const float minBox = box.Min(axis);
1352        const float maxBox = box.Max(axis);
1353
1354        const float sizeBox = maxBox - minBox;
1355
1356        const float minBand = minBox + mMinBand * sizeBox;
1357        const float maxBand = minBox + mMaxBand * sizeBox;
1358
1359        SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
1360
1361        // prepare the sweep
1362        // (note: returns pvs size, so there would be no need
1363        // to give pvs size as argument)
1364        pvsSize = PrepareHeuristics(usedRays);
1365
1366        // go through the lists, count the number of objects left and right
1367        // and evaluate the following cost funcion:
1368        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
1369
1370        int pvsl = 0;
1371        int pvsr = pvsSize;
1372
1373        int pvsBack = pvsl;
1374        int pvsFront = pvsr;
1375
1376        float sum = (float)pvsSize * sizeBox;
1377        float minSum = 1e20f;
1378
1379       
1380        // if no good split can be found, take mid split
1381        position = minBox + 0.5f * sizeBox;
1382       
1383        // the relative cost ratio
1384        float ratio = 99999999.0f;
1385        bool splitPlaneFound = false;
1386
1387        Intersectable::NewMail();
1388        KdLeaf::NewMail();
1389
1390
1391        //-- traverse through visibility events
1392
1393        vector<SortableEntry>::const_iterator ci, ci_end = mLocalSubdivisionCandidates->end();
1394
1395        for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
1396        {
1397                EvalPvsIncr(*ci, pvsl, pvsr);
1398
1399                // Note: sufficient to compare size of bounding boxes of front and back side?
1400                if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
1401                {
1402
1403                        float currentPos;
1404                       
1405                        // HACK: current positition is BETWEEN visibility events
1406                        if (0 && ((ci + 1) != ci_end))
1407                                currentPos = ((*ci).value + (*(ci + 1)).value) * 0.5f;
1408                        else
1409                                currentPos = (*ci).value;                       
1410
1411                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
1412                        //Debug  << "pos=" << (*ci).value << "\t newpos=" << currentPos << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << "\t cost= " << sum << endl;
1413
1414                        if (sum < minSum)
1415                        {
1416                                splitPlaneFound = true;
1417
1418                                minSum = sum;
1419                                position = currentPos;
1420                               
1421                                pvsBack = pvsl;
1422                                pvsFront = pvsr;
1423                        }
1424                }
1425        }
1426       
1427       
1428        //-- compute cost
1429
1430        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1431        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1432
1433        const float pOverall = sizeBox;
1434        const float pBack = position - minBox;
1435        const float pFront = maxBox - position;
1436
1437        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
1438    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1439        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1440       
1441        const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
1442        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1443
1444        if (splitPlaneFound)
1445        {
1446                ratio = newRenderCost / oldRenderCost;
1447        }
1448       
1449        const float volRatio = tData.mBoundingBox.GetVolume() / (sizeBox * mBoundingBox.GetVolume());
1450
1451/*     
1452//if (axis != 1)
1453        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
1454        //      <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
1455
1456Debug << "\n§§§§ eval local cost §§§§" << endl
1457                  << "back pvs: " << penaltyBack << " front pvs: " << penaltyFront << " total pvs: " << penaltyOld << endl
1458                  << "back p: " << pBack * volRatio << " front p " << pFront * volRatio << " p: " << pOverall * volRatio << endl
1459                  << "old rc: " << oldRenderCost * volRatio << " new rc: " << newRenderCost * volRatio << endl
1460                  << "render cost decrease: " << oldRenderCost * volRatio - newRenderCost * volRatio << endl;
1461*/
1462        return ratio;
1463}
1464
1465
1466float VspTree::SelectSplitPlane(const VspTraversalData &tData,
1467                                                                AxisAlignedPlane &plane,
1468                                                                float &pFront,
1469                                                                float &pBack)
1470{
1471        float nPosition[3];
1472        float nCostRatio[3];
1473        float nProbFront[3];
1474        float nProbBack[3];
1475
1476        // create bounding box of node geometry
1477        AxisAlignedBox3 box = tData.mBoundingBox;
1478               
1479        int sAxis = 0;
1480        int bestAxis = -1;
1481
1482        // if we use some kind of specialised fixed axis
1483    const bool useSpecialAxis =
1484                mOnlyDrivingAxis || mCirculatingAxis;
1485        //Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
1486        if (mCirculatingAxis)
1487        {
1488                int parentAxis = 0;
1489                VspNode *parent = tData.mNode->GetParent();
1490
1491                if (parent)
1492                        parentAxis = dynamic_cast<VspInterior *>(parent)->GetAxis();
1493
1494                sAxis = (parentAxis + 1) % 3;
1495        }
1496        else if (mOnlyDrivingAxis)
1497        {
1498                sAxis = box.Size().DrivingAxis();
1499        }
1500       
1501        for (int axis = 0; axis < 3; ++ axis)
1502        {
1503                if (!useSpecialAxis || (axis == sAxis))
1504                {
1505                        if (mUseCostHeuristics)
1506                        {
1507                                //-- place split plane using heuristics
1508                                nCostRatio[axis] =
1509                                        EvalLocalCostHeuristics(tData,
1510                                                                                        box,
1511                                                                                        axis,
1512                                                                                        nPosition[axis]);                       
1513                        }
1514                        else
1515                        {
1516                                //-- split plane position is spatial median
1517                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1518                                nCostRatio[axis] = EvalLocalSplitCost(tData,
1519                                                                                                          box,
1520                                                                                                          axis,
1521                                                                                                          nPosition[axis],
1522                                                                                                          nProbFront[axis],
1523                                                                                                          nProbBack[axis]);
1524                        }
1525                                               
1526                        if (bestAxis == -1)
1527                        {
1528                                bestAxis = axis;
1529                        }
1530                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
1531                        {
1532                                bestAxis = axis;
1533                        }
1534                }
1535        }
1536
1537
1538        //-- assign values of best split
1539       
1540        plane.mAxis = bestAxis;
1541        plane.mPosition = nPosition[bestAxis]; // split plane position
1542
1543        pFront = nProbFront[bestAxis];
1544        pBack = nProbBack[bestAxis];
1545
1546        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1547        return nCostRatio[bestAxis];
1548}
1549
1550
1551float VspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1552                                                                          const VspTraversalData &data,
1553                                                                          float &normalizedOldRenderCost) const
1554{
1555        float pvsFront = 0;
1556        float pvsBack = 0;
1557        float totalPvs = 0;
1558
1559        // probability that view point lies in back / front node
1560        float pOverall = data.mProbability;
1561        float pFront = 0;
1562        float pBack = 0;
1563
1564        const float viewSpaceVol = mBoundingBox.GetVolume();
1565
1566        // create unique ids for pvs heuristics
1567        Intersectable::NewMail(3);
1568        KdLeaf::NewMail(3);
1569
1570        RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1571
1572        for (rit = data.mRays->begin(); rit != rit_end; ++ rit)
1573        {
1574                RayInfo rayInf = *rit;
1575
1576                float t;
1577                VssRay *ray = rayInf.mRay;
1578
1579                const int cf =
1580                        rayInf.ComputeRayIntersection(candidatePlane.mAxis,
1581                                                                                  candidatePlane.mPosition, t);
1582
1583                if (!mUseKdPvsForHeuristics)
1584                {
1585                        // find front and back pvs for origing and termination object
1586                        UpdateObjPvsContri(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1587                        UpdateObjPvsContri(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1588                }
1589                else
1590                {
1591                        if (ray->mTerminationObject)
1592                        {
1593                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
1594                                UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
1595                        }
1596
1597                        if (ray->mOriginObject)
1598                        {
1599                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
1600                                UpdateKdLeafPvsContri(leaf, cf, pvsFront, pvsBack, totalPvs);
1601                        }
1602                }
1603        }
1604
1605
1606        AxisAlignedBox3 frontBox;
1607        AxisAlignedBox3 backBox;
1608
1609        data.mBoundingBox.Split(candidatePlane.mAxis, candidatePlane.mPosition, frontBox, backBox);
1610
1611        pFront = frontBox.GetVolume();
1612        pBack = pOverall - pFront;
1613               
1614
1615        //-- pvs rendering heuristics
1616        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1617        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1618
1619        //-- only render cost heuristics or combined with standard deviation
1620        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
1621    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
1622        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
1623                       
1624        const float oldRenderCost = pOverall * penaltyOld;
1625        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1626
1627        normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1628
1629        const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1630        /*
1631        Debug << "\n==== eval render cost decrease ===" << endl
1632                  << "back pvs: " << pvsBack << " front pvs " << pvsFront << " total pvs: " << totalPvs << endl
1633                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << " p: " << pOverall / viewSpaceVol << endl
1634                  << "old rc: " << normalizedOldRenderCost << " new rc: " << newRenderCost / viewSpaceVol << endl
1635                  << "render cost decrease: " << renderCostDecrease << endl;
1636*/
1637        return renderCostDecrease;
1638}
1639
1640
1641float VspTree::EvalLocalSplitCost(const VspTraversalData &data,
1642                                                                  const AxisAlignedBox3 &box,
1643                                                                  const int axis,
1644                                                                  const float &position,
1645                                                                  float &pFront,
1646                                                                  float &pBack) const
1647{
1648        float pvsTotal = 0;
1649        float pvsFront = 0;
1650        float pvsBack = 0;
1651       
1652        // create unique ids for pvs heuristics
1653        Intersectable::NewMail(3);
1654
1655        const int pvsSize = data.mPvs;
1656
1657        RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1658
1659        // this is the main ray classification loop!
1660        for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1661        {
1662                // determine the side of this ray with respect to the plane
1663                float t;
1664                const int side = (*rit).ComputeRayIntersection(axis, position, t);
1665       
1666                UpdateObjPvsContri((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1667                UpdateObjPvsContri((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1668        }
1669
1670        //-- evaluate cost heuristics
1671
1672        float pOverall;
1673       
1674        pOverall = data.mProbability;
1675
1676        // we use spatial mid split => simplified computation
1677        pBack = pFront = pOverall * 0.5f;
1678       
1679        const float newCost = pvsBack * pBack + pvsFront * pFront;
1680        const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1681       
1682#ifdef _DEBUG
1683        Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1684        Debug << pFront << " " << pBack << " " << pOverall << endl;
1685#endif
1686
1687        return  (mCtDivCi + newCost) / oldCost;
1688}
1689
1690
1691void VspTree::UpdateObjPvsContri(Intersectable *obj,
1692                                                  const int cf,
1693                                                  float &frontPvs,
1694                                                  float &backPvs,
1695                                                  float &totalPvs) const
1696{
1697        if (!obj) return;
1698
1699        //const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1700        const int renderCost = 1;
1701
1702        // object in no pvs => new
1703        if (!obj->Mailed() && !obj->Mailed(1) && !obj->Mailed(2))
1704        {
1705                totalPvs += renderCost;
1706        }
1707
1708        // QUESTION matt: is it safe to assume that
1709        // the object belongs to no pvs in this case?
1710        //if (cf == Ray::COINCIDENT) return;
1711
1712        if (cf >= 0) // front pvs
1713        {
1714                if (!obj->Mailed() && !obj->Mailed(2))
1715                {
1716                        frontPvs += renderCost;
1717               
1718                        // already in back pvs => in both pvss
1719                        if (obj->Mailed(1))
1720                                obj->Mail(2);
1721                        else
1722                                obj->Mail();
1723                }
1724        }
1725
1726        if (cf <= 0) // back pvs
1727        {
1728                if (!obj->Mailed(1) && !obj->Mailed(2))
1729                {
1730                        backPvs += renderCost;
1731               
1732                        // already in front pvs => in both pvss
1733                        if (obj->Mailed())
1734                                obj->Mail(2);
1735                        else
1736                                obj->Mail(1);
1737                }
1738        }
1739}
1740
1741
1742void VspTree::UpdateKdLeafPvsContri(KdLeaf *leaf,
1743                                                                        const int cf,
1744                                                                        float &frontPvs,
1745                                                                        float &backPvs,
1746                                                                        float &totalPvs) const
1747{
1748        if (!leaf) return;
1749
1750        // the objects which are referenced in this and only this leaf
1751        const int contri = (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
1752       
1753        // newly found leaf
1754        if (!leaf->Mailed() && !leaf->Mailed(1) && !leaf->Mailed(2))
1755        {
1756                totalPvs += contri;
1757        }
1758
1759        // compute contribution of yet unclassified objects
1760        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
1761
1762        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
1763        {       
1764                UpdateObjPvsContri(*oit, cf, frontPvs, backPvs, totalPvs);
1765    }   
1766       
1767        // QUESTION matt: is it safe to assume that
1768        // the object belongs to no pvs in this case?
1769        //if (cf == Ray::COINCIDENT) return;
1770
1771        if (cf >= 0) // front pvs
1772        {
1773                if (!leaf->Mailed() && !leaf->Mailed(2))
1774                {
1775                        frontPvs += contri;
1776               
1777                        // already in back pvs => in both pvss
1778                        if (leaf->Mailed(1))
1779                                leaf->Mail(2);
1780                        else
1781                                leaf->Mail();
1782                }
1783        }
1784
1785        if (cf <= 0) // back pvs
1786        {
1787                if (!leaf->Mailed(1) && !leaf->Mailed(2))
1788                {
1789                        backPvs += contri;
1790               
1791                        // already in front pvs => in both pvss
1792                        if (leaf->Mailed())
1793                                leaf->Mail(2);
1794                        else
1795                                leaf->Mail(1);
1796                }
1797        }
1798}
1799
1800
1801void VspTree::CollectLeaves(vector<VspLeaf *> &leaves,
1802                                                        const bool onlyUnmailed,
1803                                                        const int maxPvsSize) const
1804{
1805        stack<VspNode *> nodeStack;
1806        nodeStack.push(mRoot);
1807
1808        while (!nodeStack.empty())
1809        {
1810                VspNode *node = nodeStack.top();
1811                nodeStack.pop();
1812               
1813                if (node->IsLeaf())
1814                {
1815                        // test if this leaf is in valid view space
1816                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
1817                        if (leaf->TreeValid() &&
1818                                (!onlyUnmailed || !leaf->Mailed()) &&
1819                                ((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().CountObjectsInPvs() <= maxPvsSize)))
1820                        {
1821                                leaves.push_back(leaf);
1822                        }
1823                }
1824                else
1825                {
1826                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1827
1828                        nodeStack.push(interior->GetBack());
1829                        nodeStack.push(interior->GetFront());
1830                }
1831        }
1832}
1833
1834
1835AxisAlignedBox3 VspTree::GetBoundingBox() const
1836{
1837        return mBoundingBox;
1838}
1839
1840
1841VspNode *VspTree::GetRoot() const
1842{
1843        return mRoot;
1844}
1845
1846
1847void VspTree::EvaluateLeafStats(const VspTraversalData &data)
1848{
1849        // the node became a leaf -> evaluate stats for leafs
1850        VspLeaf *leaf = dynamic_cast<VspLeaf *>(data.mNode);
1851
1852
1853        if (data.mPvs > mVspStats.maxPvs)
1854        {
1855                mVspStats.maxPvs = data.mPvs;
1856        }
1857
1858        mVspStats.pvs += data.mPvs;
1859
1860        if (data.mDepth < mVspStats.minDepth)
1861        {
1862                mVspStats.minDepth = data.mDepth;
1863        }
1864       
1865        if (data.mDepth >= mTermMaxDepth)
1866        {
1867        ++ mVspStats.maxDepthNodes;
1868                //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
1869        }
1870
1871        // accumulate rays to compute rays /  leaf
1872        mVspStats.accumRays += (int)data.mRays->size();
1873
1874        if (data.mPvs < mTermMinPvs)
1875                ++ mVspStats.minPvsNodes;
1876
1877        if ((int)data.mRays->size() < mTermMinRays)
1878                ++ mVspStats.minRaysNodes;
1879
1880        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1881                ++ mVspStats.maxRayContribNodes;
1882
1883        if (data.mProbability <= mTermMinProbability)
1884                ++ mVspStats.minProbabilityNodes;
1885       
1886        // accumulate depth to compute average depth
1887        mVspStats.accumDepth += data.mDepth;
1888
1889        ++ mCreatedViewCells;
1890
1891#ifdef _DEBUG
1892        Debug << "BSP stats: "
1893                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1894                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1895                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1896                  << "#pvs: " << leaf->GetViewCell()->GetPvs().CountObjectsInPvs() << "), "
1897                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1898#endif
1899}
1900
1901
1902void VspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1903{
1904        ViewCell::NewMail();
1905        CollectViewCells(mRoot, onlyValid, viewCells, true);
1906}
1907
1908
1909void VspTree::CollapseViewCells()
1910{
1911// TODO matt
1912#if HAS_TO_BE_REDONE
1913        stack<VspNode *> nodeStack;
1914
1915        if (!mRoot)
1916                return;
1917
1918        nodeStack.push(mRoot);
1919       
1920        while (!nodeStack.empty())
1921        {
1922                VspNode *node = nodeStack.top();
1923                nodeStack.pop();
1924               
1925                if (node->IsLeaf())
1926        {
1927                        BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
1928
1929                        if (!viewCell->GetValid())
1930                        {
1931                                BspViewCell *viewCell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
1932       
1933                                ViewCellContainer leaves;
1934                                mViewCellsTree->CollectLeaves(viewCell, leaves);
1935
1936                                ViewCellContainer::const_iterator it, it_end = leaves.end();
1937
1938                                for (it = leaves.begin(); it != it_end; ++ it)
1939                                {
1940                                        VspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
1941                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
1942                                        ++ mVspStats.invalidLeaves;
1943                                }
1944
1945                                // add to unbounded view cell
1946                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1947                                DEL_PTR(viewCell);
1948                        }
1949                }
1950                else
1951                {
1952                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
1953               
1954                        nodeStack.push(interior->GetFront());
1955                        nodeStack.push(interior->GetBack());
1956                }
1957        }
1958
1959        Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
1960#endif
1961}
1962
1963
1964void VspTree::CollectRays(VssRayContainer &rays)
1965{
1966        vector<VspLeaf *> leaves;
1967        CollectLeaves(leaves);
1968
1969        vector<VspLeaf *>::const_iterator lit, lit_end = leaves.end();
1970
1971        for (lit = leaves.begin(); lit != lit_end; ++ lit)
1972        {
1973                VspLeaf *leaf = *lit;
1974                VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
1975
1976                for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
1977                        rays.push_back(*rit);
1978        }
1979}
1980
1981
1982void VspTree::SetViewCellsManager(ViewCellsManager *vcm)
1983{
1984        mViewCellsManager = vcm;
1985}
1986
1987
1988void VspTree::ValidateTree()
1989{
1990        mVspStats.invalidLeaves = 0;
1991
1992        stack<VspNode *> nodeStack;
1993
1994        if (!mRoot)
1995                return;
1996
1997        nodeStack.push(mRoot);
1998
1999        while (!nodeStack.empty())
2000        {
2001                VspNode *node = nodeStack.top();
2002                nodeStack.pop();
2003               
2004                if (node->IsLeaf())
2005                {
2006                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
2007
2008                        if (!leaf->GetViewCell()->GetValid())
2009                                ++ mVspStats.invalidLeaves;
2010
2011                        // validity flags don't match => repair
2012                        if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
2013                        {
2014                                leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
2015                                PropagateUpValidity(leaf);
2016                        }
2017                }
2018                else
2019                {
2020                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2021               
2022                        nodeStack.push(interior->GetFront());
2023                        nodeStack.push(interior->GetBack());
2024                }
2025        }
2026
2027        Debug << "invalid leaves: " << mVspStats.invalidLeaves << endl;
2028}
2029
2030
2031
2032void VspTree::CollectViewCells(VspNode *root,
2033                                                                  bool onlyValid,
2034                                                                  ViewCellContainer &viewCells,
2035                                                                  bool onlyUnmailed) const
2036{
2037        stack<VspNode *> nodeStack;
2038
2039        if (!root)
2040                return;
2041
2042        nodeStack.push(root);
2043       
2044        while (!nodeStack.empty())
2045        {
2046                VspNode *node = nodeStack.top();
2047                nodeStack.pop();
2048               
2049                if (node->IsLeaf())
2050                {
2051                        if (!onlyValid || node->TreeValid())
2052                        {
2053                                ViewCellLeaf *leafVc = dynamic_cast<VspLeaf *>(node)->GetViewCell();
2054
2055                                ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
2056                                               
2057                                if (!onlyUnmailed || !viewCell->Mailed())
2058                                {
2059                                        viewCell->Mail();
2060                                        viewCells.push_back(viewCell);
2061                                }
2062                        }
2063                }
2064                else
2065                {
2066                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2067               
2068                        nodeStack.push(interior->GetFront());
2069                        nodeStack.push(interior->GetBack());
2070                }
2071        }
2072}
2073
2074
2075int VspTree::FindNeighbors(VspLeaf *n,
2076                                                   vector<VspLeaf *> &neighbors,
2077                                                   const bool onlyUnmailed) const
2078{
2079        stack<VspNode *> nodeStack;
2080        nodeStack.push(mRoot);
2081
2082        const AxisAlignedBox3 box = GetBoundingBox(n);
2083
2084        while (!nodeStack.empty())
2085        {
2086                VspNode *node = nodeStack.top();
2087                nodeStack.pop();
2088
2089                if (node->IsLeaf())
2090                {
2091                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
2092
2093                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))
2094                                neighbors.push_back(leaf);
2095                }
2096                else
2097                {
2098                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2099                       
2100                        if (interior->GetPosition() > box.Max(interior->GetAxis()))
2101                                nodeStack.push(interior->GetBack());
2102                        else
2103                        {
2104                                if (interior->GetPosition() < box.Min(interior->GetAxis()))
2105                                        nodeStack.push(interior->GetFront());
2106                                else
2107                                {
2108                                        // random decision
2109                                        nodeStack.push(interior->GetBack());
2110                                        nodeStack.push(interior->GetFront());
2111                                }
2112                        }
2113                }
2114        }
2115
2116        return (int)neighbors.size();
2117}
2118
2119
2120// Find random neighbor which was not mailed
2121VspLeaf *VspTree::GetRandomLeaf(const Plane3 &plane)
2122{
2123        stack<VspNode *> nodeStack;
2124        nodeStack.push(mRoot);
2125 
2126        int mask = rand();
2127 
2128        while (!nodeStack.empty())
2129        {
2130                VspNode *node = nodeStack.top();
2131               
2132                nodeStack.pop();
2133               
2134                if (node->IsLeaf())
2135                {
2136                        return dynamic_cast<VspLeaf *>(node);
2137                }
2138                else
2139                {
2140                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2141                        VspNode *next;
2142                       
2143                        if (GetBoundingBox(interior->GetBack()).Side(plane) < 0)
2144                        {
2145                                next = interior->GetFront();
2146                        }
2147            else
2148                        {
2149                                if (GetBoundingBox(interior->GetFront()).Side(plane) < 0)
2150                                {
2151                                        next = interior->GetBack();
2152                                }
2153                                else
2154                                {
2155                                        // random decision
2156                                        if (mask & 1)
2157                                                next = interior->GetBack();
2158                                        else
2159                                                next = interior->GetFront();
2160                                        mask = mask >> 1;
2161                                }
2162                        }
2163                       
2164                        nodeStack.push(next);
2165                }
2166        }
2167 
2168        return NULL;
2169}
2170
2171
2172VspLeaf *VspTree::GetRandomLeaf(const bool onlyUnmailed)
2173{
2174        stack<VspNode *> nodeStack;
2175
2176        nodeStack.push(mRoot);
2177
2178        int mask = rand();
2179
2180        while (!nodeStack.empty())
2181        {
2182                VspNode *node = nodeStack.top();
2183                nodeStack.pop();
2184
2185                if (node->IsLeaf())
2186                {
2187                        if ( (!onlyUnmailed || !node->Mailed()) )
2188                                return dynamic_cast<VspLeaf *>(node);
2189                }
2190                else
2191                {
2192                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2193
2194                        // random decision
2195                        if (mask & 1)
2196                                nodeStack.push(interior->GetBack());
2197                        else
2198                                nodeStack.push(interior->GetFront());
2199
2200                        mask = mask >> 1;
2201                }
2202        }
2203
2204        return NULL;
2205}
2206
2207
2208void VspTree::CollectPvs(const RayInfoContainer &rays,
2209                                                 ObjectContainer &objects) const
2210{
2211        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2212
2213        Intersectable::NewMail();
2214
2215        for (rit = rays.begin(); rit != rays.end(); ++ rit)
2216        {
2217                VssRay *ray = (*rit).mRay;
2218
2219                Intersectable *object;
2220                object = ray->mOriginObject;
2221
2222        if (object)
2223                {
2224                        if (!object->Mailed())
2225                        {
2226                                object->Mail();
2227                                objects.push_back(object);
2228                        }
2229                }
2230
2231                object = ray->mTerminationObject;
2232
2233                if (object)
2234                {
2235                        if (!object->Mailed())
2236                        {
2237                                object->Mail();
2238                                objects.push_back(object);
2239                        }
2240                }
2241        }
2242}
2243
2244
2245int VspTree::EvalPvsSize(const RayInfoContainer &rays) const
2246{
2247        int pvsSize = 0;
2248        Intersectable::NewMail();
2249
2250        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2251
2252        if (!mUseKdPvsForHeuristics)
2253        {
2254                for (rit = rays.begin(); rit != rays.end(); ++ rit)
2255                {
2256                        VssRay *ray = (*rit).mRay;
2257
2258                        if (ray->mOriginObject)
2259                        {
2260                                if (!ray->mOriginObject->Mailed())
2261                                {
2262                                        ray->mOriginObject->Mail();
2263                                        ++ pvsSize;
2264                                }
2265                        }
2266                        if (ray->mTerminationObject)
2267                        {
2268                                if (!ray->mTerminationObject->Mailed())
2269                                {
2270                                        ray->mTerminationObject->Mail();
2271                                        ++ pvsSize;
2272                                }
2273                        }
2274                }
2275        }
2276        else // compute pvs from kd nodes
2277        {
2278                KdNode::NewMail();
2279
2280                for (rit = rays.begin(); rit != rays.end(); ++ rit)
2281                {
2282                        VssRay *ray = (*rit).mRay;
2283
2284                        if (ray->mTerminationObject)
2285                        {
2286                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
2287
2288                                if (!leaf->Mailed())
2289                                {
2290                                        leaf->Mail();
2291                                        pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
2292                               
2293                                        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
2294                                        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
2295                                        {
2296                                                Intersectable *obj = *oit;
2297
2298                                                if (!obj->Mailed())
2299                                                {
2300                                                        obj->Mail();
2301                                                        ++ pvsSize;
2302                                                }
2303                                        }
2304                                }
2305                        }
2306
2307                        if (ray->mOriginObject)
2308                        {
2309                                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
2310
2311                                if (!leaf->Mailed())
2312                                {
2313                                        leaf->Mail();
2314                                        pvsSize += (int)(leaf->mObjects.size() - leaf->mMultipleObjects.size());
2315                               
2316                                        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
2317                                        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
2318                                        {
2319                                                Intersectable *obj = *oit;
2320
2321                                                if (!obj->Mailed())
2322                                                {
2323                                                        obj->Mail();
2324                                                        ++ pvsSize;
2325                                                }
2326                                        }
2327                                }
2328                        }
2329                }
2330        }
2331
2332        return pvsSize;
2333}
2334
2335
2336float VspTree::GetEpsilon() const
2337{
2338        return mEpsilon;
2339}
2340
2341
2342int VspTree::CastLineSegment(const Vector3 &origin,
2343                                                         const Vector3 &termination,
2344                             ViewCellContainer &viewcells)
2345{
2346        int hits = 0;
2347
2348        float mint = 0.0f, maxt = 1.0f;
2349        const Vector3 dir = termination - origin;
2350
2351        stack<LineTraversalData> tStack;
2352
2353        //Intersectable::NewMail();
2354        //ViewCell::NewMail();
2355
2356        Vector3 entp = origin;
2357        Vector3 extp = termination;
2358
2359        VspNode *node = mRoot;
2360        VspNode *farChild;
2361
2362        float position;
2363        int axis;
2364
2365        while (1)
2366        {
2367                if (!node->IsLeaf())
2368                {
2369                        VspInterior *in = dynamic_cast<VspInterior *>(node);
2370                        position = in->GetPosition();
2371                        axis = in->GetAxis();
2372
2373                        if (entp[axis] <= position)
2374                        {
2375                                if (extp[axis] <= position)
2376                                {
2377                                        node = in->GetBack();
2378                                        // cases N1,N2,N3,P5,Z2,Z3
2379                                        continue;
2380                                } else
2381                                {
2382                                        // case N4
2383                                        node = in->GetBack();
2384                                        farChild = in->GetFront();
2385                                }
2386                        }
2387                        else
2388                        {
2389                                if (position <= extp[axis])
2390                                {
2391                                        node = in->GetFront();
2392                                        // cases P1,P2,P3,N5,Z1
2393                                        continue;
2394                                }
2395                                else
2396                                {
2397                                        node = in->GetFront();
2398                                        farChild = in->GetBack();
2399                                        // case P4
2400                                }
2401                        }
2402
2403                        // $$ modification 3.5.2004 - hints from Kamil Ghais
2404                        // case N4 or P4
2405                        const float tdist = (position - origin[axis]) / dir[axis];
2406                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2407
2408                        extp = origin + dir * tdist;
2409                        maxt = tdist;
2410                }
2411                else
2412                {
2413                        // compute intersection with all objects in this leaf
2414                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
2415                        ViewCell *vc = leaf->GetViewCell();
2416
2417                        // don't have to mail because each view cell belongs to exactly one leaf
2418                        //if (!vc->Mailed())
2419                        //{
2420                        //      vc->Mail();
2421                                viewcells.push_back(vc);
2422                                ++ hits;
2423                        //}
2424#if 0
2425                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2426#endif
2427                        // get the next node from the stack
2428                        if (tStack.empty())
2429                                break;
2430
2431                        entp = extp;
2432                        mint = maxt;
2433                       
2434                        LineTraversalData &s  = tStack.top();
2435                        node = s.mNode;
2436                        extp = s.mExitPoint;
2437                        maxt = s.mMaxT;
2438                        tStack.pop();
2439                }
2440        }
2441
2442        return hits;
2443}
2444
2445
2446int VspTree::CastRay(Ray &ray)
2447{
2448        int hits = 0;
2449
2450        stack<LineTraversalData> tStack;
2451        const Vector3 dir = ray.GetDir();
2452
2453        float maxt, mint;
2454
2455        if (!mBoundingBox.GetRaySegment(ray, mint, maxt))
2456                return 0;
2457
2458        Intersectable::NewMail();
2459        ViewCell::NewMail();
2460
2461        Vector3 entp = ray.Extrap(mint);
2462        Vector3 extp = ray.Extrap(maxt);
2463
2464        const Vector3 origin = entp;
2465
2466        VspNode *node = mRoot;
2467        VspNode *farChild = NULL;
2468
2469        float position;
2470        int axis;
2471
2472        while (1)
2473        {
2474                if (!node->IsLeaf())
2475                {
2476                        VspInterior *in = dynamic_cast<VspInterior *>(node);
2477                        position = in->GetPosition();
2478                        axis = in->GetAxis();
2479
2480                        if (entp[axis] <= position)
2481                        {
2482                                if (extp[axis] <= position)
2483                                {
2484                                        node = in->GetBack();
2485                                        // cases N1,N2,N3,P5,Z2,Z3
2486                                        continue;
2487                                }
2488                                else
2489                                {
2490                                        // case N4
2491                                        node = in->GetBack();
2492                                        farChild = in->GetFront();
2493                                }
2494                        }
2495                        else
2496                        {
2497                                if (position <= extp[axis])
2498                                {
2499                                        node = in->GetFront();
2500                                        // cases P1,P2,P3,N5,Z1
2501                                        continue;
2502                                }
2503                                else
2504                                {
2505                                        node = in->GetFront();
2506                                        farChild = in->GetBack();
2507                                        // case P4
2508                                }
2509                        }
2510
2511                        // $$ modification 3.5.2004 - hints from Kamil Ghais
2512                        // case N4 or P4
2513                        const float tdist = (position - origin[axis]) / dir[axis];
2514                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2515                        extp = origin + dir * tdist;
2516                        maxt = tdist;
2517                }
2518                else
2519                {
2520                        // compute intersection with all objects in this leaf
2521                        VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
2522                        ViewCell *vc = leaf->GetViewCell();
2523
2524                        if (!vc->Mailed())
2525                        {
2526                                vc->Mail();
2527                                // todo: add view cells to ray
2528                                ++ hits;
2529                        }
2530#if 0
2531                        leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2532#endif
2533                        // get the next node from the stack
2534                        if (tStack.empty())
2535                                break;
2536
2537                        entp = extp;
2538                        mint = maxt;
2539                       
2540                        LineTraversalData &s  = tStack.top();
2541                        node = s.mNode;
2542                        extp = s.mExitPoint;
2543                        maxt = s.mMaxT;
2544                        tStack.pop();
2545                }
2546        }
2547
2548        return hits;
2549}
2550
2551
2552ViewCell *VspTree::GetViewCell(const Vector3 &point, const bool active)
2553{
2554        if (mRoot == NULL)
2555                return NULL;
2556
2557        stack<VspNode *> nodeStack;
2558        nodeStack.push(mRoot);
2559 
2560        ViewCellLeaf *viewcell = NULL;
2561 
2562        while (!nodeStack.empty()) 
2563        {
2564                VspNode *node = nodeStack.top();
2565                nodeStack.pop();
2566       
2567                if (node->IsLeaf())
2568                {
2569                        viewcell = dynamic_cast<VspLeaf *>(node)->GetViewCell();
2570                        break;
2571                }
2572                else   
2573                {       
2574                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2575     
2576                        // random decision
2577                        if (interior->GetPosition() - point[interior->GetAxis()] < 0)
2578                                nodeStack.push(interior->GetBack());
2579                        else
2580                                nodeStack.push(interior->GetFront());
2581                }
2582        }
2583 
2584        if (active)
2585                return mViewCellsTree->GetActiveViewCell(viewcell);
2586        else
2587                return viewcell;
2588}
2589
2590
2591bool VspTree::ViewPointValid(const Vector3 &viewPoint) const
2592{
2593        VspNode *node = mRoot;
2594
2595        while (1)
2596        {
2597                // early exit
2598                if (node->TreeValid())
2599                        return true;
2600
2601                if (node->IsLeaf())
2602                        return false;
2603                       
2604                VspInterior *in = dynamic_cast<VspInterior *>(node);
2605                                       
2606                if (in->GetPosition() - viewPoint[in->GetAxis()] <= 0)
2607                {
2608                        node = in->GetBack();
2609                }
2610                else
2611                {
2612                        node = in->GetFront();
2613                }
2614        }
2615
2616        // should never come here
2617        return false;
2618}
2619
2620
2621void VspTree::PropagateUpValidity(VspNode *node)
2622{
2623        const bool isValid = node->TreeValid();
2624
2625        // propagative up invalid flag until only invalid nodes exist over this node
2626        if (!isValid)
2627        {
2628                while (!node->IsRoot() && node->GetParent()->TreeValid())
2629                {
2630                        node = node->GetParent();
2631                        node->SetTreeValid(false);
2632                }
2633        }
2634        else
2635        {
2636                // propagative up valid flag until one of the subtrees is invalid
2637                while (!node->IsRoot() && !node->TreeValid())
2638                {
2639            node = node->GetParent();
2640                        VspInterior *interior = dynamic_cast<VspInterior *>(node);
2641                       
2642                        // the parent is valid iff both leaves are valid
2643                        node->SetTreeValid(interior->GetBack()->TreeValid() &&
2644                                                           interior->GetFront()->TreeValid());
2645                }
2646        }
2647}
2648
2649
2650bool VspTree::Export(OUT_STREAM &stream)
2651{
2652        ExportNode(mRoot, stream);
2653
2654        return true;
2655}
2656
2657
2658void VspTree::ExportNode(VspNode *node, OUT_STREAM &stream)
2659{
2660        if (node->IsLeaf())
2661        {
2662                VspLeaf *leaf = dynamic_cast<VspLeaf *>(node);
2663                ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2664
2665                int id = -1;
2666                if (viewCell != mOutOfBoundsCell)
2667                        id = viewCell->GetId();
2668
2669                stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
2670        }
2671        else
2672        {       
2673                VspInterior *interior = dynamic_cast<VspInterior *>(node);
2674       
2675                AxisAlignedPlane plane = interior->GetPlane();
2676                stream << "<Interior plane=\"" << plane.mPosition << " "
2677                           << plane.mAxis << "\">" << endl;
2678
2679                ExportNode(interior->GetBack(), stream);
2680                ExportNode(interior->GetFront(), stream);
2681
2682                stream << "</Interior>" << endl;
2683        }
2684}
2685
2686
2687int VspTree::SplitRays(const AxisAlignedPlane &plane,
2688                                           RayInfoContainer &rays,
2689                                           RayInfoContainer &frontRays,
2690                                           RayInfoContainer &backRays) const
2691{
2692        int splits = 0;
2693
2694        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2695
2696        for (rit = rays.begin(); rit != rit_end; ++ rit)
2697        {
2698                RayInfo bRay = *rit;
2699               
2700                VssRay *ray = bRay.mRay;
2701                float t;
2702
2703                // get classification and receive new t
2704                // test if start point behind or in front of plane
2705                const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
2706                       
2707                if (side == 0)
2708                {
2709                        ++ splits;
2710
2711                        if (ray->HasPosDir(plane.mAxis))
2712                        {
2713                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2714                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2715                        }
2716                        else
2717                        {
2718                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2719                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2720                        }
2721                }
2722                else if (side == 1)
2723                {
2724                        frontRays.push_back(bRay);
2725                }
2726                else
2727                {
2728                        backRays.push_back(bRay);
2729                }
2730        }
2731
2732        return splits;
2733}
2734
2735
2736AxisAlignedBox3 VspTree::GetBoundingBox(VspNode *node) const
2737{
2738        if (!node->GetParent())
2739                return mBoundingBox;
2740
2741        if (!node->IsLeaf())
2742        {
2743                return (dynamic_cast<VspInterior *>(node))->GetBoundingBox();           
2744        }
2745
2746        VspInterior *parent = dynamic_cast<VspInterior *>(node->GetParent());
2747
2748        AxisAlignedBox3 box(parent->GetBoundingBox());
2749
2750        if (parent->GetFront() == node)
2751      box.SetMin(parent->GetAxis(), parent->GetPosition());
2752    else
2753      box.SetMax(parent->GetAxis(), parent->GetPosition());
2754
2755        return box;
2756}
2757
2758
2759int VspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2760                                                                         ViewCellContainer &viewCells) const
2761{
2762        stack<VspNode *> nodeStack;
2763 
2764        ViewCell::NewMail();
2765
2766        while (!nodeStack.empty())
2767        {
2768                VspNode *node = nodeStack.top();
2769                nodeStack.pop();
2770
2771                const AxisAlignedBox3 bbox = GetBoundingBox(node);
2772
2773                if (bbox.Includes(box))
2774                {
2775                        // node geometry is contained in box
2776                        CollectViewCells(node, true, viewCells, true);
2777                }
2778                else if (Overlap(bbox, box))
2779                {
2780                        if (node->IsLeaf())
2781                        {
2782                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2783                       
2784                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2785                                {
2786                                        leaf->GetViewCell()->Mail();
2787                                        viewCells.push_back(leaf->GetViewCell());
2788                                }
2789                        }
2790                        else
2791                        {
2792                                VspInterior *interior = dynamic_cast<VspInterior *>(node);
2793                       
2794                                VspNode *first = interior->GetFront();
2795                                VspNode *second = interior->GetBack();
2796           
2797                                nodeStack.push(first);
2798                                nodeStack.push(second);
2799                        }
2800                }       
2801                // default: cull
2802        }
2803
2804        return (int)viewCells.size();
2805}
2806
2807
2808void VspTree::CollectDirtyCandidates(VspSubdivisionCandidate *sc,
2809                                                                         vector<SubdivisionCandidate *> &dirtyList)
2810{
2811        VspTraversalData &tData = sc->mParentData;
2812        VspLeaf *node = tData.mNode;
2813       
2814        KdLeaf::NewMail();
2815
2816        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2817
2818        // add all kd nodes seen by the rays
2819        for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2820        {
2821                VssRay *ray = (*rit).mRay;
2822       
2823                KdLeaf *leaf = mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
2824       
2825                if (!leaf->Mailed())
2826                {
2827                        leaf->Mail();
2828                        dirtyList.push_back(leaf->mSubdivisionCandidate);
2829                }
2830               
2831                leaf = mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
2832       
2833                if (!leaf->Mailed())
2834                {
2835                        leaf->Mail();
2836                        dirtyList.push_back(leaf->mSubdivisionCandidate);
2837                }
2838        }
2839}
2840
2841
2842void VspTree::PreprocessRays(const VssRayContainer &sampleRays,
2843                                                         RayInfoContainer &rays)
2844{
2845        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
2846
2847        long startTime = GetTime();
2848
2849        cout << "storing rays ... ";
2850
2851        Intersectable::NewMail();
2852
2853        //-- store rays and objects
2854        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
2855        {
2856                VssRay *ray = *rit;
2857                float minT, maxT;
2858                static Ray hray;
2859
2860                hray.Init(*ray);
2861               
2862                // TODO: not very efficient to implictly cast between rays types
2863                if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
2864                {
2865                        float len = ray->Length();
2866
2867                        if (!len)
2868                                len = Limits::Small;
2869
2870                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
2871                }
2872        }
2873
2874        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
2875}
2876
2877
2878void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
2879{
2880#if 0
2881        // use view cells manager to compute view cells
2882        mViewCellsManager->ComputeSampleContribution(ray, false, true);
2883        viewCells = ray.mViewCells;
2884        ray.mViewCells.clear();
2885       
2886#else
2887        static Ray hray;
2888        hray.Init(ray);
2889       
2890        float tmin = 0, tmax = 1.0;
2891
2892        if (!mBoundingBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
2893                return;
2894
2895        const Vector3 origin = hray.Extrap(tmin);
2896        const Vector3 termination = hray.Extrap(tmax);
2897
2898        // if no precomputation of view cells
2899        CastLineSegment(origin, termination, viewCells);
2900#endif
2901}
2902
2903
2904SubdivisionCandidate *VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
2905                                                                        AxisAlignedBox3 *forcedViewSpace,
2906                                                                        RayInfoContainer &rays)
2907{
2908        // store pointer to this tree
2909        VspSubdivisionCandidate::sVspTree = this;
2910        mVspStats.nodes = 1;
2911
2912        // compute view space bounding box
2913        ComputeBoundingBox(sampleRays, forcedViewSpace);
2914
2915        // initialise termination criteria
2916        mTermMinProbability *= mBoundingBox.GetVolume();
2917        mGlobalCostMisses = 0;
2918
2919        // get clipped rays
2920        PreprocessRays(sampleRays, rays);
2921
2922        const int pvsSize = EvalPvsSize(rays);
2923       
2924        Debug <<  "pvs size: " << (int)pvsSize << endl;
2925        Debug <<  "rays size: " << (int)rays.size() << endl;
2926
2927        //-- prepare view space partition
2928
2929        // add first candidate for view space partition
2930        VspLeaf *leaf = new VspLeaf();
2931        mRoot = leaf;
2932
2933        const float prop = mBoundingBox.GetVolume();
2934
2935        // first vsp traversal data
2936        VspTraversalData vData(leaf, 0, &rays, pvsSize, prop, mBoundingBox);
2937
2938        // create first view cell
2939        CreateViewCell(vData, false);
2940               
2941#if WORK_WITH_VIEWCELL_PVS
2942       
2943        // add first view cell to all the objects view cell pvs
2944        ObjectPvsMap::const_iterator oit,
2945                oit_end = leaf->GetViewCell()->GetPvs().mEntries.end();
2946
2947
2948        for (oit = leaf->GetViewCell()->GetPvs().mEntries.begin(); oit != oit_end; ++ oit)
2949        {
2950                Intersectable *obj = (*oit).first;
2951                obj->mViewCellPvs.AddSample(leaf->GetViewCell(), 1);
2952        }
2953#endif
2954
2955        //-- compute first split candidate
2956
2957        VspSubdivisionCandidate *splitCandidate = new VspSubdivisionCandidate(vData);
2958    EvalSubdivisionCandidate(*splitCandidate);
2959
2960        mTotalCost = (float)pvsSize;
2961        EvalSubdivisionStats(*splitCandidate);
2962
2963        return splitCandidate;
2964}
2965
2966
2967
2968}
Note: See TracBrowser for help on using the repository browser.