source: trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp @ 483

Revision 483, 54.8 KB checked in by mattausch, 19 years ago (diff)
Line 
1
2// ================================================================
3// $Id: lsds_kdtree.cpp,v 1.18 2005/04/16 09:34:21 bittner Exp $
4// ****************************************************************
5/**
6   The KD tree based LSDS
7*/
8// Initial coding by
9/**
10   @author Jiri Bittner
11*/
12
13// Standard headers
14#include <stack>
15#include <queue>
16#include <algorithm>
17#include <fstream>
18#include <string>
19
20#include "VspKdTree.h"
21
22#include "Environment.h"
23#include "VssRay.h"
24#include "Intersectable.h"
25#include "Ray.h"
26#include "RayInfo.h"
27#include "ViewCellsManager.h"
28#include "ViewCellBsp.h"
29
30// Static variables
31int VspKdLeaf::sMailId = 0;
32int MergeCandidate::sMaxPvsSize = 150;
33float MergeCandidate::sOverallCost = Limits::Small;
34#define USE_FIXEDPOINT_T 0
35
36/// Adds object to the pvs of the front and back node
37inline void AddObject2Pvs(Intersectable *object,
38                                                  const int side,
39                                                  int &pvsBack,
40                                                  int &pvsFront)
41{
42        if (!object)
43                return;
44
45        if (side <= 0)
46        {
47                if (!object->Mailed() && !object->Mailed(2))
48                {
49                        ++ pvsBack;
50
51                        if (object->Mailed(1))
52                                object->Mail(2);
53                        else
54                                object->Mail();
55                }
56        }
57
58        if (side >= 0)
59        {
60                if (!object->Mailed(1) && !object->Mailed(2))
61                {
62                        ++ pvsFront;
63
64                        if (object->Mailed())
65                                object->Mail(2);
66                        else
67                                object->Mail(1);
68                }
69        }
70}
71
72/**************************************************************/
73/*                class VspKdNode implementation          */
74/**************************************************************/
75
76// Inline constructor
77VspKdNode::VspKdNode(VspKdInterior *p):
78mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)
79{}
80
81VspKdNode::~VspKdNode()
82{
83};
84
85inline VspKdInterior *VspKdNode::GetParent() const
86{
87        return mParent;
88}
89
90inline void VspKdNode::SetParent(VspKdInterior *p)
91{
92        mParent = p;
93}
94
95bool VspKdNode::IsLeaf() const
96{
97        return mAxis == -1;
98}
99
100int VspKdNode::GetAccessTime()
101{
102        return 0x7FFFFFF;
103}
104
105/**************************************************************/
106/*                VspKdInterior implementation            */
107/**************************************************************/
108
109VspKdInterior::VspKdInterior(VspKdInterior *p):
110VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
111{
112}
113
114int VspKdInterior::GetAccessTime()
115{
116        return mLastAccessTime;
117}
118
119void VspKdInterior::SetupChildLinks(VspKdNode *b, VspKdNode *f)
120{
121        mBack = b;
122        mFront = f;
123        b->SetParent(this);
124        f->SetParent(this);
125}
126
127void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild,
128                                                                                 VspKdNode *newChild)
129{
130        if (mBack == oldChild)
131                mBack = newChild;
132        else
133                mFront = newChild;
134}
135
136int VspKdInterior::Type() const
137{
138        return EInterior;
139}
140
141VspKdInterior::~VspKdInterior()
142{
143        DEL_PTR(mBack);
144        DEL_PTR(mFront);
145}
146
147void VspKdInterior::Print(ostream &s) const
148{
149        switch (mAxis)
150        {
151        case 0:
152                s << "x "; break;
153        case 1:
154                s << "y "; break;
155        case 2:
156                s << "z "; break;
157        }
158
159        s << mPosition << " ";
160
161        mBack->Print(s);
162        mFront->Print(s);
163}
164
165int VspKdInterior::ComputeRayIntersection(const RayInfo &rayData, float &t)
166{
167        return rayData.ComputeRayIntersection(mAxis, mPosition, t);
168}
169
170VspKdNode *VspKdInterior::GetBack() const
171{
172        return mBack;
173}
174
175VspKdNode *VspKdInterior::GetFront() const
176{
177        return mFront;
178}
179
180
181/**************************************************************/
182/*              class VspKdLeaf implementation            */
183/**************************************************************/
184
185
186VspKdLeaf::VspKdLeaf(VspKdInterior *p,
187                                         const int nRays,
188                                         const int maxCostMisses):
189VspKdNode(p), mRays(), mPvsSize(0), mValidPvs(false), mViewCell(NULL),
190mMaxCostMisses(maxCostMisses)
191{
192        mRays.reserve(nRays);
193}
194
195VspKdLeaf::~VspKdLeaf()
196{
197}
198
199
200int VspKdLeaf::GetMaxCostMisses()
201{
202        return mMaxCostMisses;
203}
204
205
206int VspKdLeaf::Type() const
207{
208        return ELeaf;
209}
210
211void VspKdLeaf::Print(ostream &s) const
212{
213        s << endl << "L: r = " << (int)mRays.size() << endl;
214};
215
216void VspKdLeaf::AddRay(const RayInfo &data)
217{
218        mValidPvs = false;
219        mRays.push_back(data);
220        data.mRay->Ref();
221}
222
223int VspKdLeaf::GetPvsSize() const
224{
225        return mPvsSize;
226}
227
228void VspKdLeaf::SetPvsSize(const int s)
229{
230        mPvsSize = s;
231}
232
233void VspKdLeaf::Mail()
234{
235        mMailbox = sMailId;
236}
237
238void VspKdLeaf::NewMail()
239{
240        ++ sMailId;
241}
242
243bool VspKdLeaf::Mailed() const
244{
245        return mMailbox == sMailId;
246}
247
248bool VspKdLeaf::Mailed(const int mail) const
249{
250        return mMailbox == mail;
251}
252
253int VspKdLeaf::GetMailbox() const
254{
255        return mMailbox;
256}
257
258float VspKdLeaf::GetAvgRayContribution() const
259{
260        return GetPvsSize() / ((float)mRays.size() + Limits::Small);
261}
262
263float VspKdLeaf::GetSqrRayContribution() const
264{
265        return sqr(GetAvgRayContribution());
266}
267
268RayInfoContainer &VspKdLeaf::GetRays()
269{
270        return mRays;
271}
272
273void VspKdLeaf::ExtractPvs(ObjectContainer &objects) const
274{
275        RayInfoContainer::const_iterator it, it_end = mRays.end();
276
277        for (it = mRays.begin(); it != it_end; ++ it)
278        {
279                if ((*it).mRay->mTerminationObject)
280                        objects.push_back((*it).mRay->mTerminationObject);
281                if ((*it).mRay->mOriginObject)
282                        objects.push_back((*it).mRay->mOriginObject);
283        }
284}
285
286void VspKdLeaf::GetRays(VssRayContainer &rays)
287{
288        RayInfoContainer::const_iterator it, it_end = mRays.end();
289
290        for (it = mRays.begin(); it != mRays.end(); ++ it)
291                rays.push_back((*it).mRay);
292}
293
294VspKdViewCell *VspKdLeaf::GetViewCell()
295{
296        return mViewCell;
297}
298
299void VspKdLeaf::SetViewCell(VspKdViewCell *viewCell)
300{
301        mViewCell = viewCell;
302}
303
304
305void VspKdLeaf::UpdatePvsSize()
306{
307        if (!mValidPvs)
308        {
309                Intersectable::NewMail();
310                int pvsSize = 0;
311                for(RayInfoContainer::iterator ri = mRays.begin();
312                        ri != mRays.end(); ++ ri)
313                {
314                        if ((*ri).mRay->IsActive())
315                        {
316                                Intersectable *object;
317#if BIDIRECTIONAL_RAY
318                                object = (*ri).mRay->mOriginObject;
319
320                                if (object && !object->Mailed())
321                                {
322                                        ++ pvsSize;
323                                        object->Mail();
324                                }
325#endif
326                                object = (*ri).mRay->mTerminationObject;
327                                if (object && !object->Mailed())
328                                {
329                                        ++ pvsSize;
330                                        object->Mail();
331                                }
332                        }
333                }
334
335                mPvsSize = pvsSize;
336                mValidPvs = true;
337        }
338}
339
340/*********************************************************/
341/*            class VspKdTree implementation             */
342/*********************************************************/
343
344
345VspKdTree::VspKdTree(): mOnlyDrivingAxis(false)
346{
347        environment->GetIntValue("VspKdTree.Termination.maxDepth", mTermMaxDepth);
348        environment->GetIntValue("VspKdTree.Termination.minPvs", mTermMinPvs);
349        environment->GetIntValue("VspKdTree.Termination.minRays", mTermMinRays);
350        environment->GetFloatValue("VspKdTree.Termination.maxRayContribution", mTermMaxRayContribution);
351        environment->GetFloatValue("VspKdTree.Termination.maxCostRatio", mTermMaxCostRatio);
352        environment->GetFloatValue("VspKdTree.Termination.minSize", mTermMinSize);
353
354        environment->GetIntValue("VspKdTree.Termination.missTolerance", mTermMissTolerance);
355
356        mTermMinSize = sqr(mTermMinSize);
357
358        environment->GetFloatValue("VspKdTree.epsilon", mEpsilon);
359        environment->GetFloatValue("VspKdTree.ct_div_ci", mCtDivCi);
360
361        environment->GetFloatValue("VspKdTree.maxTotalMemory", mMaxTotalMemory);
362        environment->GetFloatValue("VspKdTree.maxStaticMemory", mMaxStaticMemory);
363
364        environment->GetIntValue("VspKdTree.accessTimeThreshold", mAccessTimeThreshold);
365        environment->GetIntValue("VspKdTree.minCollapseDepth", mMinCollapseDepth);
366
367        //environment->GetIntValue("ViewCells.maxViewCells", mMaxViewCells);
368
369        environment->GetIntValue("VspKdTree.PostProcess.minViewCells", mMergeMinViewCells);
370        environment->GetFloatValue("VspKdTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
371        environment->GetIntValue("VspKdTree.PostProcess.maxPvsSize",
372                                                         MergeCandidate::sMaxPvsSize);
373
374        // split type
375        char sname[128];
376        environment->GetStringValue("VspKdTree.splitType", sname);
377        string name(sname);
378
379        Debug << "======= vsp kd tree options ========" << endl;
380        Debug << "max depth: "<< mTermMaxDepth << endl;
381        Debug << "min pvs: "<< mTermMinPvs << endl;
382        Debug << "min rays: "<< mTermMinRays << endl;
383        Debug << "max ray contribution: "<< mTermMaxRayContribution << endl;
384        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
385        Debug << "min size: " << mTermMinSize << endl;
386
387        if (name.compare("regular") == 0)
388        {
389                Debug << "using regular split" << endl;
390                splitType = ESplitRegular;
391        }
392        else
393        {
394                if (name.compare("heuristic") == 0)
395                {
396                        Debug << "using heuristic split" << endl;
397                        splitType = ESplitHeuristic;
398                }
399                else
400                {
401                        cerr << "Invalid VspKdTree split type " << name << endl;
402                        exit(1);
403                }
404        }
405
406        mRoot = NULL;
407
408        mSplitCandidates = new vector<SortableEntry>;
409}
410
411
412VspKdTree::~VspKdTree()
413{
414        DEL_PTR(mRoot);
415        DEL_PTR(mSplitCandidates);
416}
417
418void VspKdStatistics::Print(ostream &app) const
419{
420        app << "===== VspKdTree statistics ===============\n";
421
422        app << "#N_RAYS ( Number of rays )\n"
423                << rays << endl;
424
425        app << "#N_INITPVS ( Initial PVS size )\n"
426                << initialPvsSize << endl;
427
428        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
429
430        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
431
432        app << "#N_SPLITS ( Number of splits in axes x y z\n";
433
434        for (int i = 0; i < 3; ++ i)
435                app << splits[i] << " ";
436        app << endl;
437
438        app << "#N_RAYREFS ( Number of rayRefs )\n" <<
439                rayRefs << "\n";
440
441        app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
442                rayRefs / (double)rays << "\n";
443
444        app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
445                rayRefs / (double)Leaves() << "\n";
446
447        app << "#N_MAXRAYREFS  ( Max number of rayRefs / leaf )\n" <<
448                maxRayRefs << "\n";
449
450  //  app << setprecision(4);
451
452        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n" <<
453                maxDepthNodes * 100 / (double)Leaves() << endl;
454
455        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n" <<
456                minPvsNodes * 100 / (double)Leaves() << endl;
457
458        app << "#N_PMINRAYSLEAVES  ( Percentage of leaves with minimal number of rays)\n" <<
459                minRaysNodes * 100 / (double)Leaves() << endl;
460
461        app << "#N_PMINSIZELEAVES  ( Percentage of leaves with minSize )\n"<<
462                minSizeNodes * 100 / (double)Leaves() << endl;
463
464        app << "#N_PMAXRAYCONTRIBLEAVES  ( Percentage of leaves with maximal ray contribution )\n" <<
465                maxRayContribNodes * 100 / (double)Leaves() << endl;
466
467        app << "#N_PMAXRCOSTLEAVES  ( Percentage of leaves with maximal cost ratio )\n" <<
468                maxCostNodes * 100 / (double)Leaves() << endl;
469
470        app << "#N_ADDED_RAYREFS  ( Number of dynamically added ray references )\n"<<
471                addedRayRefs << endl;
472
473        app << "#N_REMOVED_RAYREFS  ( Number of dynamically removed ray references )\n"<<
474                removedRayRefs << endl;
475
476        //  app << setprecision(4);
477
478        app << "#N_( Maximal PVS size / leaf)\n"
479                << maxPvsSize << endl;
480
481        app << "#N_( Average PVS size / leaf)\n"
482                << (double) accPvsSize / (double)Leaves() << endl;
483
484        app << "#N_CTIME  ( Construction time [s] )\n"
485                << Time() << " \n";
486
487        app << "===== END OF VspKdTree statistics ==========\n";
488}
489
490
491void VspKdTree::CollectViewCells(ViewCellContainer &viewCells) const
492{
493        stack<VspKdNode *> nodeStack;
494        nodeStack.push(mRoot);
495
496        ViewCell::NewMail();
497
498        while (!nodeStack.empty())
499        {
500                VspKdNode *node = nodeStack.top();
501                nodeStack.pop();
502
503                if (node->IsLeaf())
504                {
505                        ViewCell *viewCell = dynamic_cast<VspKdLeaf *>(node)->mViewCell;
506
507                        if (!viewCell->Mailed())
508                        {
509                                viewCell->Mail();
510                                viewCells.push_back(viewCell);
511                        }
512                }
513                else
514                {
515                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
516
517                        nodeStack.push(interior->GetFront());
518                        nodeStack.push(interior->GetBack());
519                }
520        }
521}
522
523void VspKdTree::Construct(const VssRayContainer &rays,
524                                                  AxisAlignedBox3 *forcedBoundingBox)
525{
526        mStat.Start();
527
528        mMaxMemory = mMaxStaticMemory;
529        DEL_PTR(mRoot);
530
531        mRoot = new VspKdLeaf(NULL, (int)rays.size());
532
533        // first construct a leaf that will get subdivided
534        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(mRoot);
535
536        mStat.nodes = 1;
537        mBox.Initialize();
538
539        //-- compute bounding box
540        if (forcedBoundingBox)
541                mBox = *forcedBoundingBox;
542        else
543                for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
544                {
545                        if ((*ri)->mOriginObject)
546                mBox.Include((*ri)->GetOrigin());
547                        if ((*ri)->mTerminationObject)
548                                mBox.Include((*ri)->GetTermination());
549                }
550
551        Debug << "bbox = " << mBox << endl;
552
553        for (VssRayContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
554        {
555                //leaf->AddRay(RayInfo(*ri));
556                VssRay *ray = *ri;
557                float minT, maxT;
558               
559                // TODO: not very efficient to implictly cast between rays types!
560                if (mBox.GetRaySegment(*ray, minT, maxT))
561                {
562                        float len = ray->Length();
563
564                        if (!len)
565                                len = Limits::Small;
566
567                        leaf->AddRay(RayInfo(ray, minT / len, maxT / len));
568                }
569        }
570
571        mStat.rays = (int)leaf->mRays.size();
572        leaf->UpdatePvsSize();
573
574        mStat.initialPvsSize = leaf->GetPvsSize();
575
576        // Subdivide();
577        mRoot = Subdivide(TraversalData(leaf, mBox, 0));
578
579        if (mSplitCandidates)
580        {
581                // force release of this vector
582                delete mSplitCandidates;
583                mSplitCandidates = new vector<SortableEntry>;
584        }
585
586        mStat.Stop();
587
588        mStat.Print(cout);
589        Debug << "#Total memory=" << GetMemUsage() << endl;
590}
591
592
593
594VspKdNode *VspKdTree::Subdivide(const TraversalData &tdata)
595{
596        VspKdNode *result = NULL;
597
598        priority_queue<TraversalData> tStack;
599        //stack<TraversalData> tStack;
600
601        tStack.push(tdata);
602
603        AxisAlignedBox3 backBox;
604        AxisAlignedBox3 frontBox;
605
606        int lastMem = 0;
607
608        while (!tStack.empty())
609        {
610                float mem = GetMemUsage();
611
612                if (lastMem / 10 != ((int)mem) / 10)
613                {
614                        Debug << mem << " MB" << endl;
615                }
616                lastMem = (int)mem;
617
618                if (1 && mem > mMaxMemory)
619                {
620                        Debug << "memory limit reached: " << mem << endl;
621                        // count statistics on unprocessed leafs
622                        while (!tStack.empty())
623                        {
624                                EvaluateLeafStats(tStack.top());
625                                tStack.pop();
626                        }
627                        break;
628                }
629
630                TraversalData data = tStack.top();
631                tStack.pop();
632
633                VspKdNode *node = SubdivideNode(dynamic_cast<VspKdLeaf *>(data.mNode),
634                                                                                data.mBox, backBox,     frontBox);
635                if (result == NULL)
636                        result = node;
637
638                if (!node->IsLeaf())
639                {
640                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
641
642                        // push the children on the stack
643                        tStack.push(TraversalData(interior->GetBack(), backBox, data.mDepth + 1));
644                        tStack.push(TraversalData(interior->GetFront(), frontBox, data.mDepth + 1));
645                }
646                else
647                {
648                        EvaluateLeafStats(data);
649                }
650        }
651
652        return result;
653}
654
655
656// returns selected plane for subdivision
657int VspKdTree::SelectPlane(VspKdLeaf *leaf,
658                                                   const AxisAlignedBox3 &box,
659                                                   float &position,
660                                                   int &raysBack,
661                                                   int &raysFront,
662                                                   int &pvsBack,
663                                                   int &pvsFront)
664{
665        int axis = 0;
666        float costRatio = 0;
667
668        if (splitType == ESplitRegular)
669        {
670                costRatio = BestCostRatioRegular(leaf,
671                                                                                 box,
672                                                                                 axis,
673                                                                                 position,
674                                                                                 raysBack,
675                                                                                 raysFront,
676                                                                                 pvsBack,
677                                                                                 pvsFront);
678        }
679        else if (splitType == ESplitHeuristic)
680        {
681                costRatio = BestCostRatioHeuristic(leaf,
682                                                                                   box,
683                                                                                   axis,
684                                                                                   position,
685                                                                                   raysBack,
686                                                                                   raysFront,
687                                                                                   pvsBack,
688                                                                                   pvsFront);
689        }
690        else
691        {
692                cerr << "VspKdTree: Unknown split heuristics\n";
693                exit(1);
694        }
695
696        if (costRatio > mTermMaxCostRatio)
697        {
698                //Debug << "Too big cost ratio " << costRatio << endl;
699                ++ leaf->mMaxCostMisses;
700                if (leaf->mMaxCostMisses > mTermMissTolerance)
701                {
702                        ++ mStat.maxCostNodes;
703                        return -1;
704                }
705        }
706
707        if (0)
708                Debug << "pvs=" << leaf->mPvsSize
709                          << " rays=" << (int)leaf->mRays.size()
710                          << " rc=" << leaf->GetAvgRayContribution()
711                          << " axis=" << axis << endl;
712
713        return axis;
714}
715
716
717
718float VspKdTree::EvalCostRatio(VspKdLeaf *leaf,
719                                                           const AxisAlignedBox3 &box,
720                                                           const int axis,
721                                                           const float position,
722                                                           int &raysBack,
723                                                           int &raysFront,
724                                                           int &pvsBack,
725                                                           int &pvsFront)
726{
727        raysBack = 0;
728        raysFront = 0;
729        pvsFront = 0;
730        pvsBack = 0;
731
732        Intersectable::NewMail(3);
733
734        // eval pvs size
735        const int pvsSize = leaf->GetPvsSize();
736
737        // this is the main ray classification loop!
738        for(RayInfoContainer::iterator ri = leaf->mRays.begin();
739                        ri != leaf->mRays.end(); ++ ri)
740        {
741                if (!(*ri).mRay->IsActive())
742                        continue;
743
744                // determine the side of this ray with respect to the plane
745                float t;
746                int side = (*ri).ComputeRayIntersection(axis, position, t);
747                       
748                if (side <= 0)
749                        ++ raysBack;
750
751                if (side >= 0)
752                        ++ raysFront;
753
754                AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
755        }
756
757        //-- only one of these options should be one
758
759        if (0) //-- only pvs
760        {
761                const float sum = float(pvsBack + pvsFront);
762                const float oldCost = (float)pvsSize;
763
764                return sum / oldCost;
765        }
766
767        //-- pvs + probability heuristics
768        float pBack, pFront, pOverall;
769
770        if (0)
771        {
772                // box length substitute for probability
773                const float minBox = box.Min(axis);
774                const float maxBox = box.Max(axis);
775
776                pBack = position - minBox;
777                pFront = maxBox - position;
778                pOverall = maxBox - minBox;
779        }
780
781        if (1) //-- area substitute for probability
782        {
783               
784                const bool useMidSplit = true;
785                //const bool useMidSplit = false;
786                       
787                pOverall = box.SurfaceArea();
788                       
789                if (!useMidSplit)
790                {
791                        Vector3 pos = box.Max(); pos[axis] = position;
792                        pBack = AxisAlignedBox3(box.Min(), pos).SurfaceArea();
793
794                        pos = box.Min(); pos[axis] = position;
795                        pFront = AxisAlignedBox3(pos, box.Max()).SurfaceArea();
796                }
797                else
798                {
799                        //-- simplified computation for mid split
800                        const int axis2 = (axis + 1) % 3;
801                        const int axis3 = (axis + 2) % 3;
802
803                        const float faceArea =
804                                (box.Max(axis2) - box.Min(axis2)) *
805                                (box.Max(axis3) - box.Min(axis3));
806
807                        pBack = pFront = pOverall * 0.5f + faceArea;
808                }
809        }
810
811        //-- ray density substitute for probability
812        if (0)
813        {
814                pBack = (float)raysBack;
815                pFront = (float)raysFront;
816                pOverall = (float)leaf->mRays.size();
817        }
818
819        //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
820        //Debug << pFront << " " << pBack << " " << pOverall << endl;
821
822        // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
823        const float newCost = pvsBack * pBack + pvsFront * pFront;
824        //  float oldCost = leaf->mRays.size();
825        const float oldCost = (float)pvsSize * pOverall;
826
827        return  (mCtDivCi + newCost) / oldCost;
828}
829
830float VspKdTree::BestCostRatioRegular(VspKdLeaf *leaf,
831                                                                          const AxisAlignedBox3 &box,
832                                                                          int &axis,
833                                                                          float &position,
834                                                                          int &raysBack,
835                                                                          int &raysFront,
836                                                                          int &pvsBack,
837                                                                          int &pvsFront)
838{
839        int nRaysBack[3], nRaysFront[3];
840        int nPvsBack[3], nPvsFront[3];
841
842        float nPosition[3];
843        float nCostRatio[3];
844        int bestAxis = -1;
845
846        //AxisAlignedBox3 sBox = GetBBox(leaf);
847        const int sAxis = box.Size().DrivingAxis();
848
849        for (axis = 0; axis < 3; ++ axis)
850        {
851                if (!mOnlyDrivingAxis || axis == sAxis)
852                {
853
854                        nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
855
856                        nCostRatio[axis] = EvalCostRatio(leaf,
857                                                                                         box,
858                                                                                         axis,
859                                                                                         nPosition[axis],
860                                                                                         nRaysBack[axis],
861                                                                                         nRaysFront[axis],
862                                                                                         nPvsBack[axis],
863                                                                                         nPvsFront[axis]);
864                        if (bestAxis == -1)
865                        {
866                                bestAxis = axis;
867                        }
868                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
869                        {
870                                /*Debug << "pvs front " << nPvsBack[axis]
871                                          << " pvs back " << nPvsFront[axis]
872                                          << " overall pvs " << leaf->GetPvsSize() << endl;*/
873                                bestAxis = axis;
874                        }
875
876                }
877        }
878
879        //-- assign best axis
880        axis = bestAxis;
881        position = nPosition[bestAxis];
882
883        raysBack = nRaysBack[bestAxis];
884        raysFront = nRaysFront[bestAxis];
885
886        pvsBack = nPvsBack[bestAxis];
887        pvsFront = nPvsFront[bestAxis];
888
889        return nCostRatio[bestAxis];
890}
891
892float VspKdTree::BestCostRatioHeuristic(VspKdLeaf *leaf,
893                                                                                const AxisAlignedBox3 &box,
894                                                                                int &axis,
895                                                                                float &position,
896                                                                                int &raysBack,
897                                                                                int &raysFront,
898                                                                                int &pvsBack,
899                                                                                int &pvsFront)
900{
901        //AxisAlignedBox3 box = GetBBox(leaf);
902        //      AxisAlignedBox3 dirBox = GetDirBBox(node);
903
904        axis = box.Size().DrivingAxis();
905
906        SortSplitCandidates(leaf, axis);
907
908        // go through the lists, count the number of objects left and right
909        // and evaluate the following cost funcion:
910        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
911
912        int rl = 0, rr = (int)leaf->mRays.size();
913        int pl = 0, pr = leaf->GetPvsSize();
914
915        float minBox = box.Min(axis);
916        float maxBox = box.Max(axis);
917        float sizeBox = maxBox - minBox;
918
919        float minBand = minBox + 0.1f*(maxBox - minBox);
920        float maxBand = minBox + 0.9f*(maxBox - minBox);
921
922        float sum = rr*sizeBox;
923        float minSum = 1e20f;
924
925        Intersectable::NewMail();
926
927        // set all object as belonging to the fron pvs
928        for(RayInfoContainer::iterator ri = leaf->mRays.begin();
929                ri != leaf->mRays.end(); ++ ri)
930        {
931                if ((*ri).mRay->IsActive())
932                {
933                        Intersectable *object = (*ri).mRay->mTerminationObject;
934
935                        if (object)
936                                if (!object->Mailed())
937                                {
938                                        object->Mail();
939                                        object->mCounter = 1;
940                                }
941                                else
942                                        ++ object->mCounter;
943                }
944        }
945
946        Intersectable::NewMail();
947
948        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
949                ci < mSplitCandidates->end(); ++ ci)
950        {
951                VssRay *ray;
952
953                switch ((*ci).type)
954                {
955                        case SortableEntry::ERayMin:
956                                {
957                                        ++ rl;
958                                        ray = (*ci).ray;
959                                        Intersectable *object = ray->mTerminationObject;
960                                        if (object && !object->Mailed())
961                                        {
962                                                object->Mail();
963                                                ++ pl;
964                                        }
965                                        break;
966                                }
967                        case SortableEntry::ERayMax:
968                                {
969                                        -- rr;
970
971                                        ray = (*ci).ray;
972                                        Intersectable *object = ray->mTerminationObject;
973
974                                        if (object)
975                                        {
976                                                if (-- object->mCounter == 0)
977                                                -- pr;
978                                        }
979
980                                        break;
981                                }
982                }
983
984                if ((*ci).value > minBand && (*ci).value < maxBand)
985                {
986                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
987
988                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
989                        // cout<<"cost= "<<sum<<endl;
990
991                        if (sum < minSum)
992                        {
993                                minSum = sum;
994                                position = (*ci).value;
995
996                                raysBack = rl;
997                                raysFront = rr;
998
999                                pvsBack = pl;
1000                                pvsFront = pr;
1001
1002                        }
1003                }
1004        }
1005
1006        float oldCost = (float)leaf->GetPvsSize();
1007        float newCost = mCtDivCi + minSum / sizeBox;
1008        float ratio = newCost / oldCost;
1009
1010        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
1011        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
1012
1013        return ratio;
1014}
1015
1016void VspKdTree::SortSplitCandidates(VspKdLeaf *node,
1017                                                                        const int axis)
1018{
1019        mSplitCandidates->clear();
1020
1021        int requestedSize = 2 * (int)(node->mRays.size());
1022        // creates a sorted split candidates array
1023        if (mSplitCandidates->capacity() > 500000 &&
1024                requestedSize < (int)(mSplitCandidates->capacity()/10) )
1025        {
1026        DEL_PTR(mSplitCandidates);
1027                mSplitCandidates = new vector<SortableEntry>;
1028        }
1029
1030        mSplitCandidates->reserve(requestedSize);
1031
1032        // insert all queries
1033        for(RayInfoContainer::const_iterator ri = node->mRays.begin();
1034                ri < node->mRays.end(); ++ ri)
1035        {
1036                bool positive = (*ri).mRay->HasPosDir(axis);
1037                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
1038                                                                                                  (*ri).ExtrapOrigin(axis), (*ri).mRay));
1039
1040                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
1041                                                                                                  (*ri).ExtrapTermination(axis), (*ri).mRay));
1042        }
1043
1044        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
1045}
1046
1047
1048void VspKdTree::EvaluateLeafStats(const TraversalData &data)
1049{
1050        // the node became a leaf -> evaluate stats for leafs
1051        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
1052
1053        if (leaf->GetPvsSize() > mStat.maxPvsSize)
1054                mStat.maxPvsSize = leaf->GetPvsSize();
1055
1056        if ((int)(leaf->mRays.size()) > mStat.maxRayRefs)
1057                mStat.maxRayRefs = (int)leaf->mRays.size();
1058
1059        mStat.rays += (int)leaf->mRays.size();
1060
1061        if (data.mDepth >= mTermMaxDepth)
1062                ++ mStat.maxDepthNodes;
1063
1064        if (leaf->GetPvsSize() < mTermMinPvs)
1065                ++ mStat.minPvsNodes;
1066
1067        mStat.accPvsSize += leaf->GetPvsSize();
1068
1069        if ((int)leaf->GetRays().size() < mTermMinRays)
1070                ++ mStat.minRaysNodes;
1071
1072        if (leaf->GetAvgRayContribution() > mTermMaxRayContribution)
1073                ++ mStat.maxRayContribNodes;
1074
1075        if (SqrMagnitude(data.mBox.Size()) <= mTermMinSize)
1076                ++ mStat.minSizeNodes;
1077}
1078
1079
1080inline bool VspKdTree::TerminationCriteriaMet(const VspKdLeaf *leaf,
1081                                                                                          const AxisAlignedBox3 &box) const
1082{
1083        return ((leaf->GetPvsSize() < mTermMinPvs) ||
1084                    (leaf->mRays.size() < mTermMinRays) ||
1085                        (leaf->GetAvgRayContribution() > mTermMaxRayContribution ) ||
1086                        (leaf->mDepth >= mTermMaxDepth) ||
1087                        (SqrMagnitude(box.Size()) <= mTermMinSize));
1088}
1089
1090
1091VspKdNode *VspKdTree::SubdivideNode(VspKdLeaf *leaf,
1092                                                                        const AxisAlignedBox3 &box,
1093                                                                        AxisAlignedBox3 &backBBox,
1094                                                                        AxisAlignedBox3 &frontBBox)
1095{
1096        if (TerminationCriteriaMet(leaf, box))
1097        {
1098                if (1 && leaf->mDepth >= mTermMaxDepth)
1099                {
1100                        Debug << "Warning: max depth reached depth=" << (int)leaf->mDepth<<" rays=" << (int)leaf->mRays.size() << endl;
1101                        Debug << "Bbox: " << GetBBox(leaf) << endl;
1102                }
1103                //Debug << "depth: " << (int)leaf->mDepth << " pvs: " << leaf->GetPvsSize() << " rays: " << leaf->mRays.size() << endl;
1104
1105                return leaf;
1106        }
1107
1108        float position;
1109        // first count ray sides
1110        int raysBack;
1111        int raysFront;
1112        int pvsBack;
1113        int pvsFront;
1114
1115        // select subdivision axis
1116        const int axis = SelectPlane(leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
1117        //Debug << "rays back=" << raysBack << " rays front=" << raysFront << " pvs back=" << pvsBack << " pvs front=" <<       pvsFront << endl;
1118
1119        if (axis == -1)
1120                return leaf;
1121       
1122        mStat.nodes += 2;
1123        ++ mStat.splits[axis];
1124
1125        // add the new nodes to the tree
1126        VspKdInterior *node = new VspKdInterior(leaf->mParent);
1127
1128        node->mAxis = axis;
1129        node->mPosition = position;
1130        node->mBox = box;
1131
1132        backBBox = box;
1133        frontBBox = box;
1134
1135        VspKdLeaf *back = new VspKdLeaf(node, raysBack, leaf->GetMaxCostMisses());
1136        back->SetPvsSize(pvsBack);
1137        VspKdLeaf *front = new VspKdLeaf(node, raysFront, leaf->GetMaxCostMisses());
1138        front->SetPvsSize(pvsFront);
1139
1140        // replace a link from node's parent
1141        if (leaf->mParent)
1142                leaf->mParent->ReplaceChildLink(leaf, node);
1143        // and setup child links
1144        node->SetupChildLinks(back, front);
1145
1146        if (axis <= VspKdNode::SPLIT_Z)
1147        {
1148                backBBox.SetMax(axis, position);
1149                frontBBox.SetMin(axis, position);
1150
1151                for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1152                                ri != leaf->mRays.end(); ++ ri)
1153                {
1154                        if ((*ri).mRay->IsActive())
1155                        {
1156                                // first unref ray from the former leaf
1157                                (*ri).mRay->Unref();
1158                                  float t;
1159                                // determine the side of this ray with respect to the plane
1160                                int side = node->ComputeRayIntersection(*ri, t);
1161
1162                                if (side == 0)
1163                                {
1164                                        if ((*ri).mRay->HasPosDir(axis))
1165                                        {
1166                                                back->AddRay(RayInfo((*ri).mRay,
1167                                                                                         (*ri).mMinT,
1168                                                                                         t));
1169                                                front->AddRay(RayInfo((*ri).mRay,
1170                                                                                          t,
1171                                                                                          (*ri).mMaxT));
1172                                        }
1173                                        else
1174                                        {
1175                                                back->AddRay(RayInfo((*ri).mRay,
1176                                                                                         t,
1177                                                                                         (*ri).mMaxT));
1178                                                front->AddRay(RayInfo((*ri).mRay,
1179                                                                                          (*ri).mMinT,
1180                                                                                          t));
1181                                        }
1182                                }
1183                                else
1184                                        if (side == 1)
1185                                                front->AddRay(*ri);
1186                                        else
1187                                                back->AddRay(*ri);
1188                        } else
1189                                (*ri).mRay->Unref();
1190                }
1191        }
1192        else
1193        {
1194                // rays front/back
1195
1196        for (RayInfoContainer::iterator ri = leaf->mRays.begin();
1197                        ri != leaf->mRays.end(); ++ ri)
1198                {
1199                        if ((*ri).mRay->IsActive())
1200                        {
1201                                // first unref ray from the former leaf
1202                                (*ri).mRay->Unref();
1203
1204                                int side;
1205                                if ((*ri).mRay->GetDirParametrization(axis - 3) > position)
1206                                        side = 1;
1207                                else
1208                                        side = -1;
1209
1210                                if (side == 1)
1211                                        front->AddRay(*ri);
1212                                else
1213                                        back->AddRay(*ri);
1214                        }
1215                        else
1216                                (*ri).mRay->Unref();
1217                }
1218        }
1219
1220        // update stats
1221        mStat.rayRefs -= (int)leaf->mRays.size();
1222        mStat.rayRefs += raysBack + raysFront;
1223
1224        DEL_PTR(leaf);
1225
1226        return node;
1227}
1228
1229int VspKdTree::ReleaseMemory(const int time)
1230{
1231        stack<VspKdNode *> tstack;
1232
1233        // find a node in the tree which subtree will be collapsed
1234        int maxAccessTime = time - mAccessTimeThreshold;
1235        int released = 0;
1236
1237        tstack.push(mRoot);
1238
1239        while (!tstack.empty())
1240        {
1241                VspKdNode *node = tstack.top();
1242                tstack.pop();
1243
1244                if (!node->IsLeaf())
1245                {
1246                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
1247                        // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
1248                        if (in->mDepth >= mMinCollapseDepth && in->mLastAccessTime <= maxAccessTime)
1249                        {
1250                                released = CollapseSubtree(node, time);
1251                                break;
1252                        }
1253                        if (in->GetBack()->GetAccessTime() < in->GetFront()->GetAccessTime())
1254                        {
1255                                tstack.push(in->GetFront());
1256                                tstack.push(in->GetBack());
1257                        }
1258                        else
1259                        {
1260                                tstack.push(in->GetBack());
1261                                tstack.push(in->GetFront());
1262                        }
1263                }
1264        }
1265
1266        while (tstack.empty())
1267        {
1268                // could find node to collaps...
1269                // cout<<"Could not find a node to release "<<endl;
1270                break;
1271        }
1272
1273        return released;
1274}
1275
1276
1277VspKdNode *VspKdTree::SubdivideLeaf(VspKdLeaf *leaf,
1278                                                                                const float sizeThreshold)
1279{
1280        VspKdNode *node = leaf;
1281
1282        AxisAlignedBox3 leafBBox = GetBBox(leaf);
1283
1284        static int pass = 0;
1285        ++ pass;
1286
1287        // check if we should perform a dynamic subdivision of the leaf
1288        if (// leaf->mRays.size() > (unsigned)termMinCost &&
1289                (leaf->GetPvsSize() >= mTermMinPvs) &&
1290                (SqrMagnitude(leafBBox.Size()) > sizeThreshold) )
1291        {
1292        // memory check and release
1293                if (GetMemUsage() > mMaxTotalMemory)
1294                        ReleaseMemory(pass);
1295
1296                AxisAlignedBox3 backBBox, frontBBox;
1297
1298                // subdivide the node
1299                node = SubdivideNode(leaf, leafBBox, backBBox, frontBBox);
1300        }
1301        return node;
1302}
1303
1304
1305
1306void VspKdTree::UpdateRays(VssRayContainer &remove,
1307                                                   VssRayContainer &add)
1308{
1309        VspKdLeaf::NewMail();
1310
1311        // schedule rays for removal
1312        for(VssRayContainer::const_iterator ri = remove.begin();
1313                ri != remove.end(); ++ ri)
1314        {
1315                (*ri)->ScheduleForRemoval();
1316        }
1317
1318        int inactive = 0;
1319
1320        for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri)
1321        {
1322                if ((*ri)->ScheduledForRemoval())
1323                        //      RemoveRay(*ri, NULL, false);
1324                        // !!! BUG - with true it does not work correctly - aggreated delete
1325                        RemoveRay(*ri, NULL, true);
1326                else
1327                        ++ inactive;
1328        }
1329
1330        //  cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
1331        for (VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri)
1332        {
1333                AddRay(*ri);
1334        }
1335}
1336
1337
1338void VspKdTree::RemoveRay(VssRay *ray,
1339                                                  vector<VspKdLeaf *> *affectedLeaves,
1340                                                  const bool removeAllScheduledRays)
1341{
1342        stack<RayTraversalData> tstack;
1343
1344        tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
1345
1346        RayTraversalData data;
1347
1348        // cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
1349        while (!tstack.empty())
1350        {
1351                data = tstack.top();
1352                tstack.pop();
1353
1354                if (!data.mNode->IsLeaf())
1355                {
1356                        // split the set of rays in two groups intersecting the
1357                        // two subtrees
1358                        TraverseInternalNode(data, tstack);
1359        }
1360                else
1361                {
1362                        // remove the ray from the leaf
1363                        // find the ray in the leaf and swap it with the last ray...
1364                        VspKdLeaf *leaf = (VspKdLeaf *)data.mNode;
1365
1366                        if (!leaf->Mailed())
1367                        {
1368                                leaf->Mail();
1369
1370                                if (affectedLeaves)
1371                                        affectedLeaves->push_back(leaf);
1372
1373                                if (removeAllScheduledRays)
1374                                {
1375                                        int tail = (int)leaf->mRays.size() - 1;
1376
1377                                        for (int i=0; i < (int)(leaf->mRays.size()); ++ i)
1378                                        {
1379                                                if (leaf->mRays[i].mRay->ScheduledForRemoval())
1380                                                {
1381                                                        // find a ray to replace it with
1382                                                        while (tail >= i && leaf->mRays[tail].mRay->ScheduledForRemoval())
1383                                                        {
1384                                                                ++ mStat.removedRayRefs;
1385                                                                leaf->mRays[tail].mRay->Unref();
1386                                                                leaf->mRays.pop_back();
1387
1388                                                                -- tail;
1389                                                        }
1390
1391                                                        if (tail < i)
1392                                                                break;
1393
1394                                                        ++ mStat.removedRayRefs;
1395
1396                                                        leaf->mRays[i].mRay->Unref();
1397                                                        leaf->mRays[i] = leaf->mRays[tail];
1398                                                        leaf->mRays.pop_back();
1399                                                        -- tail;
1400                                                }
1401                                        }
1402                                }
1403                        }
1404
1405                        if (!removeAllScheduledRays)
1406                                for (int i=0; i < (int)leaf->mRays.size(); i++)
1407                                {
1408                                        if (leaf->mRays[i].mRay == ray)
1409                                        {
1410                                                ++ mStat.removedRayRefs;
1411                                                ray->Unref();
1412                                                leaf->mRays[i] = leaf->mRays[leaf->mRays.size() - 1];
1413                                                leaf->mRays.pop_back();
1414                                            // check this ray again
1415                                                break;
1416                                        }
1417                                }
1418                }
1419        }
1420
1421        if (ray->RefCount() != 0)
1422        {
1423                cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl;
1424                exit(1);
1425        }
1426
1427}
1428
1429void VspKdTree::AddRay(VssRay *ray)
1430{
1431        stack<RayTraversalData> tstack;
1432
1433        tstack.push(RayTraversalData(mRoot, RayInfo(ray)));
1434
1435        RayTraversalData data;
1436
1437        while (!tstack.empty())
1438        {
1439                data = tstack.top();
1440                tstack.pop();
1441
1442                if (!data.mNode->IsLeaf())
1443                {
1444                        TraverseInternalNode(data, tstack);
1445                }
1446                else
1447                {
1448                        // remove the ray from the leaf
1449                        // find the ray in the leaf and swap it with the last ray
1450                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(data.mNode);
1451
1452                        leaf->AddRay(data.mRayData);
1453                        ++ mStat.addedRayRefs;
1454                }
1455        }
1456}
1457
1458void VspKdTree::TraverseInternalNode(RayTraversalData &data,
1459                                                                         stack<RayTraversalData> &tstack)
1460{
1461        VspKdInterior *in = dynamic_cast<VspKdInterior *>(data.mNode);
1462
1463        if (in->mAxis <= VspKdNode::SPLIT_Z)
1464        {
1465            // determine the side of this ray with respect to the plane
1466 float t;
1467 int side = in->ComputeRayIntersection(data.mRayData, t);
1468
1469                if (side == 0)
1470                {
1471                        if (data.mRayData.mRay->HasPosDir(in->mAxis))
1472                        {
1473                                tstack.push(RayTraversalData(in->GetBack(),
1474                                                        RayInfo(data.mRayData.mRay, data.mRayData.mMinT, t)));
1475
1476                                tstack.push(RayTraversalData(in->GetFront(),
1477                                                        RayInfo(data.mRayData.mRay, t, data.mRayData.mMaxT)));
1478
1479                        }
1480                        else
1481                        {
1482                                tstack.push(RayTraversalData(in->GetBack(),
1483                                                        RayInfo(data.mRayData.mRay,
1484                                                        t,
1485                                                        data.mRayData.mMaxT)));
1486                                tstack.push(RayTraversalData(in->GetFront(),
1487                                                        RayInfo(data.mRayData.mRay,
1488                                                        data.mRayData.mMinT,
1489                                                        t)));
1490                        }
1491                }
1492                else
1493                        if (side == 1)
1494                                tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
1495                        else
1496                                tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
1497        }
1498        else
1499        {
1500                // directional split
1501                if (data.mRayData.mRay->GetDirParametrization(in->mAxis - 3) > in->mPosition)
1502                        tstack.push(RayTraversalData(in->GetFront(), data.mRayData));
1503                else
1504                        tstack.push(RayTraversalData(in->GetBack(), data.mRayData));
1505        }
1506}
1507
1508
1509int VspKdTree::CollapseSubtree(VspKdNode *sroot, const int time)
1510{
1511        // first count all rays in the subtree
1512        // use mail 1 for this purpose
1513        stack<VspKdNode *> tstack;
1514
1515        int rayCount = 0;
1516        int totalRayCount = 0;
1517        int collapsedNodes = 0;
1518
1519#if DEBUG_COLLAPSE
1520        cout << "Collapsing subtree" << endl;
1521        cout << "accessTime=" << sroot->GetAccessTime() << endl;
1522        cout << "depth=" << (int)sroot->depth << endl;
1523#endif
1524
1525        // tstat.collapsedSubtrees++;
1526        // tstat.collapseDepths += (int)sroot->depth;
1527        // tstat.collapseAccessTimes += time - sroot->GetAccessTime();
1528        tstack.push(sroot);
1529        VssRay::NewMail();
1530
1531        while (!tstack.empty())
1532        {
1533                ++ collapsedNodes;
1534
1535                VspKdNode *node = tstack.top();
1536                tstack.pop();
1537                if (node->IsLeaf())
1538                {
1539                        VspKdLeaf *leaf = (VspKdLeaf *) node;
1540
1541                        for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1542                                        ri != leaf->mRays.end(); ++ ri)
1543                        {
1544                                ++ totalRayCount;
1545
1546                                if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed())
1547                                {
1548                                        (*ri).mRay->Mail();
1549                                        ++ rayCount;
1550                                }
1551                        }
1552                }
1553                else
1554                {
1555                        tstack.push(dynamic_cast<VspKdInterior *>(node)->GetFront());
1556                        tstack.push(dynamic_cast<VspKdInterior *>(node)->GetBack());
1557                }
1558        }
1559
1560        VssRay::NewMail();
1561
1562        // create a new node that will hold the rays
1563        VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
1564
1565        if (newLeaf->mParent)
1566        {
1567                newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
1568        }
1569        tstack.push(sroot);
1570
1571        while (!tstack.empty())
1572        {
1573                VspKdNode *node = tstack.top();
1574                tstack.pop();
1575
1576                if (node->IsLeaf())
1577                {
1578                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
1579
1580                        for(RayInfoContainer::iterator ri = leaf->mRays.begin();
1581                                        ri != leaf->mRays.end(); ++ ri)
1582                        {
1583                                // unref this ray from the old node
1584                                if ((*ri).mRay->IsActive())
1585                                {
1586                                        (*ri).mRay->Unref();
1587                                        if (!(*ri).mRay->Mailed())
1588                                        {
1589                                                (*ri).mRay->Mail();
1590                                                newLeaf->AddRay(*ri);
1591                                        }
1592                                }
1593                                else
1594                                        (*ri).mRay->Unref();
1595                        }
1596                }
1597                else
1598                {
1599                        VspKdInterior *interior =
1600                                dynamic_cast<VspKdInterior *>(node);
1601                        tstack.push(interior->GetBack());
1602                        tstack.push(interior->GetFront());
1603                }
1604        }
1605
1606        // delete the node and all its children
1607        DEL_PTR(sroot);
1608
1609        // for(VspKdNode::SRayContainer::iterator ri = newleaf->mRays.begin();
1610    //      ri != newleaf->mRays.end(); ++ ri)
1611        //     (*ri).ray->UnMail(2);
1612
1613#if DEBUG_COLLAPSE
1614        cout << "Total memory before=" << GetMemUsage() << endl;
1615#endif
1616
1617        mStat.nodes -= collapsedNodes - 1;
1618        mStat.rayRefs -= totalRayCount - rayCount;
1619
1620#if DEBUG_COLLAPSE
1621        cout << "collapsed nodes" << collapsedNodes << endl;
1622        cout << "collapsed rays" << totalRayCount - rayCount << endl;
1623        cout << "Total memory after=" << GetMemUsage() << endl;
1624        cout << "================================" << endl;
1625#endif
1626
1627        //  tstat.collapsedNodes += collapsedNodes;
1628        //  tstat.collapsedRays += totalRayCount - rayCount;
1629    return totalRayCount - rayCount;
1630}
1631
1632
1633int VspKdTree::GetPvsSize(VspKdNode *node, const AxisAlignedBox3 &box) const
1634{
1635        stack<VspKdNode *> tstack;
1636        tstack.push(mRoot);
1637
1638        Intersectable::NewMail();
1639        int pvsSize = 0;
1640
1641        while (!tstack.empty())
1642        {
1643                VspKdNode *node = tstack.top();
1644                tstack.pop();
1645
1646          if (node->IsLeaf())
1647                {
1648                        VspKdLeaf *leaf = (VspKdLeaf *)node;
1649                        for (RayInfoContainer::iterator ri = leaf->mRays.begin();
1650                                 ri != leaf->mRays.end(); ++ ri)
1651                        {
1652                                if ((*ri).mRay->IsActive())
1653                                {
1654                                        Intersectable *object;
1655#if BIDIRECTIONAL_RAY
1656                                        object = (*ri).mRay->mOriginObject;
1657
1658                                        if (object && !object->Mailed())
1659                                        {
1660                                                ++ pvsSize;
1661                                                object->Mail();
1662                                        }
1663#endif
1664                                        object = (*ri).mRay->mTerminationObject;
1665                                        if (object && !object->Mailed())
1666                                        {
1667                                                ++ pvsSize;
1668                                                object->Mail();
1669                                        }
1670                                }
1671                        }
1672                }
1673                else
1674                {
1675                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
1676
1677                        if (in->mAxis < 3)
1678                        {
1679                                if (box.Max(in->mAxis) >= in->mPosition)
1680                                        tstack.push(in->GetFront());
1681
1682                                if (box.Min(in->mAxis) <= in->mPosition)
1683                                        tstack.push(in->GetBack());
1684                        }
1685                        else
1686                        {
1687                                // both nodes for directional splits
1688                                tstack.push(in->GetFront());
1689                                tstack.push(in->GetBack());
1690                        }
1691                }
1692        }
1693
1694        return pvsSize;
1695}
1696
1697void VspKdTree::GetRayContributionStatistics(float &minRayContribution,
1698                                                                                         float &maxRayContribution,
1699                                                                                         float &avgRayContribution)
1700{
1701        stack<VspKdNode *> tstack;
1702        tstack.push(mRoot);
1703
1704        minRayContribution = 1.0f;
1705        maxRayContribution = 0.0f;
1706
1707        float sumRayContribution = 0.0f;
1708        int leaves = 0;
1709
1710        while (!tstack.empty())
1711        {
1712                VspKdNode *node = tstack.top();
1713                tstack.pop();
1714                if (node->IsLeaf())
1715                {
1716                        leaves++;
1717                        VspKdLeaf *leaf = (VspKdLeaf *)node;
1718                        float c = leaf->GetAvgRayContribution();
1719
1720                        if (c > maxRayContribution)
1721                                maxRayContribution = c;
1722                        if (c < minRayContribution)
1723                                minRayContribution = c;
1724                        sumRayContribution += c;
1725
1726                }
1727                else
1728                {
1729                        VspKdInterior *in = (VspKdInterior *)node;
1730                       
1731                        tstack.push(in->GetFront());
1732                        tstack.push(in->GetBack());
1733                }
1734        }
1735
1736        Debug << "sum=" << sumRayContribution << endl;
1737        Debug << "leaves=" << leaves << endl;
1738        avgRayContribution = sumRayContribution / (float)leaves;
1739}
1740
1741
1742int VspKdTree::GenerateRays(const float ratioPerLeaf,
1743                                                        SimpleRayContainer &rays)
1744{
1745        stack<VspKdNode *> tstack;
1746        tstack.push(mRoot);
1747
1748        while (!tstack.empty())
1749        {
1750                VspKdNode *node = tstack.top();
1751                tstack.pop();
1752
1753                if (node->IsLeaf())
1754                {
1755                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
1756
1757                        float c = leaf->GetAvgRayContribution();
1758                        int num = (int)(c*ratioPerLeaf + 0.5);
1759                        //                      cout<<num<<" ";
1760
1761                        for (int i=0; i < num; i++)
1762                        {
1763                                Vector3 origin = GetBBox(leaf).GetRandomPoint();
1764                                /*Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
1765                                Vector3 direction = Vector3(sin(dirVector.x), sin(dirVector.y), cos(dirVector.x));
1766                                //cout<<"dir vector.x="<<dirVector.x<<"direction'.x="<<atan2(direction.x, direction.y)<<endl;
1767                                rays.push_back(SimpleRay(origin, direction));*/
1768                        }
1769
1770                }
1771                else
1772                {
1773                        VspKdInterior *in =
1774                                dynamic_cast<VspKdInterior *>(node);
1775               
1776                        tstack.push(in->GetFront());
1777                        tstack.push(in->GetBack());
1778                }
1779        }
1780
1781        return (int)rays.size();
1782}
1783
1784
1785float VspKdTree::GetAvgPvsSize()
1786{
1787        stack<VspKdNode *> tstack;
1788        tstack.push(mRoot);
1789
1790        int sumPvs = 0;
1791        int leaves = 0;
1792
1793        while (!tstack.empty())
1794        {
1795                VspKdNode *node = tstack.top();
1796                tstack.pop();
1797
1798                if (node->IsLeaf())
1799                {
1800                        VspKdLeaf *leaf = (VspKdLeaf *)node;
1801                        // update pvs size
1802                        leaf->UpdatePvsSize();
1803                        sumPvs += leaf->GetPvsSize();
1804                        leaves++;
1805                }
1806                else
1807                {
1808                        VspKdInterior *in = (VspKdInterior *)node;
1809                       
1810                        tstack.push(in->GetFront());
1811                        tstack.push(in->GetBack());
1812                }
1813        }
1814
1815        return sumPvs / (float)leaves;
1816}
1817
1818VspKdNode *VspKdTree::GetRoot() const
1819{
1820        return mRoot;
1821}
1822
1823AxisAlignedBox3 VspKdTree::GetBBox(VspKdNode *node) const
1824{
1825        if (node->mParent == NULL)
1826                return mBox;
1827
1828        if (!node->IsLeaf())
1829                return (dynamic_cast<VspKdInterior *>(node))->mBox;
1830
1831        if (node->mParent->mAxis >= 3)
1832                return node->mParent->mBox;
1833
1834        AxisAlignedBox3 box(node->mParent->mBox);
1835        if (node->mParent->GetFront() == node)
1836                box.SetMin(node->mParent->mAxis, node->mParent->mPosition);
1837        else
1838                box.SetMax(node->mParent->mAxis, node->mParent->mPosition);
1839
1840        return box;
1841}
1842
1843int     VspKdTree::GetRootPvsSize() const
1844{
1845        return GetPvsSize(mRoot, mBox);
1846}
1847
1848const VspKdStatistics &VspKdTree::GetStatistics() const
1849{
1850        return mStat;
1851}
1852
1853void VspKdTree::AddRays(VssRayContainer &add)
1854{
1855        VssRayContainer remove;
1856        UpdateRays(remove, add);
1857}
1858
1859// return memory usage in MB
1860float VspKdTree::GetMemUsage() const
1861{
1862        return
1863                (sizeof(VspKdTree) +
1864                 mStat.Leaves() * sizeof(VspKdLeaf) +
1865                 mStat.Interior() * sizeof(VspKdInterior) +
1866                 mStat.rayRefs * sizeof(RayInfo)) / (1024.0f * 1024.0f);
1867}
1868
1869float VspKdTree::GetRayMemUsage() const
1870{
1871        return mStat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f);
1872}
1873
1874
1875int VspKdTree::ComputePvsSize(VspKdNode *node,
1876                                                          const RayInfoContainer &globalRays) const
1877{
1878        int pvsSize = 0;
1879
1880        const AxisAlignedBox3 box = GetBBox(node);
1881
1882        RayInfoContainer::const_iterator it, it_end = globalRays.end();
1883
1884        // TODO
1885
1886        // warning: implicit conversion from VssRay to Ray
1887        for (it = globalRays.begin(); it != globalRays.end(); ++ it)
1888                pvsSize += box.GetMinMaxT(*(*it).mRay, NULL, NULL);
1889
1890        return pvsSize;
1891}
1892
1893
1894void VspKdTree::CollectLeaves(vector<VspKdLeaf *> &leaves) const
1895{
1896        stack<VspKdNode *> nodeStack;
1897        nodeStack.push(mRoot);
1898
1899        while (!nodeStack.empty())
1900        {
1901                VspKdNode *node = nodeStack.top();
1902
1903                nodeStack.pop();
1904
1905                if (node->IsLeaf())
1906                {
1907                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
1908                        leaves.push_back(leaf);
1909                }
1910                else
1911                {
1912                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
1913
1914                        nodeStack.push(interior->GetBack());
1915                        nodeStack.push(interior->GetFront());
1916                }
1917        }
1918}
1919
1920int VspKdTree::FindNeighbors(VspKdLeaf *n,
1921                                                         vector<VspKdLeaf *> &neighbors,
1922                                                         bool onlyUnmailed)
1923{
1924        stack<VspKdNode *> nodeStack;
1925
1926        nodeStack.push(mRoot);
1927
1928        AxisAlignedBox3 box = GetBBox(n);
1929
1930        while (!nodeStack.empty())
1931        {
1932                VspKdNode *node = nodeStack.top();
1933                nodeStack.pop();
1934
1935                if (node->IsLeaf())
1936                {
1937                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
1938
1939                        if (leaf != n && (!onlyUnmailed || !leaf->Mailed()))
1940                                neighbors.push_back(leaf);
1941                }
1942                else
1943                {
1944                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
1945
1946                        if (interior->mPosition > box.Max(interior->mAxis))
1947                                nodeStack.push(interior->mBack);
1948                        else
1949                        {
1950                                if (interior->mPosition < box.Min(interior->mAxis))
1951                                        nodeStack.push(interior->mFront);
1952                                else
1953                                {
1954                                        // random decision
1955                                        nodeStack.push(interior->mBack);
1956                                        nodeStack.push(interior->mFront);
1957                                }
1958                        }
1959                }
1960        }
1961
1962        return (int)neighbors.size();
1963}
1964
1965
1966void VspKdTree::SetViewCellsManager(ViewCellsManager *vcm)
1967{
1968        mViewCellsManager = vcm;
1969}
1970
1971
1972int VspKdTree::CastLineSegment(const Vector3 &origin,
1973                                                           const Vector3 &termination,
1974                                                           vector<ViewCell *> &viewcells)
1975{
1976        int hits = 0;
1977
1978        float mint = 0.0f, maxt = 1.0f;
1979        const Vector3 dir = termination - origin;
1980
1981        stack<LineTraversalData> tStack;
1982
1983        Intersectable::NewMail();
1984
1985        Vector3 entp = origin;
1986        Vector3 extp = termination;
1987
1988        VspKdNode *node = mRoot;
1989        VspKdNode *farChild;
1990
1991        float position;
1992        int axis;
1993
1994        while (1)
1995        {
1996                if (!node->IsLeaf())
1997                {
1998                        VspKdInterior *in = dynamic_cast<VspKdInterior *>(node);
1999                        position = in->mPosition;
2000                        axis = in->mAxis;
2001
2002                        if (entp[axis] <= position)
2003                        {
2004                                if (extp[axis] <= position)
2005                                {
2006                                        node = in->mBack;
2007                                        // cases N1,N2,N3,P5,Z2,Z3
2008                                        continue;
2009                                } else
2010                                {
2011                                        // case N4
2012                                        node = in->mBack;
2013                                        farChild = in->mFront;
2014                                }
2015                        }
2016                        else
2017                        {
2018                                if (position <= extp[axis])
2019                                {
2020                                        node = in->mFront;
2021                                        // cases P1,P2,P3,N5,Z1
2022                                        continue;
2023                                }
2024                                else
2025                                {
2026                                        node = in->mFront;
2027                                        farChild = in->mBack;
2028                                        // case P4
2029                                }
2030                        }
2031
2032                        // $$ modification 3.5.2004 - hints from Kamil Ghais
2033                        // case N4 or P4
2034                        float tdist = (position - origin[axis]) / dir[axis];
2035                        tStack.push(LineTraversalData(farChild, extp, maxt)); //TODO
2036                        extp = origin + dir * tdist;
2037                        maxt = tdist;
2038                }
2039                else
2040                {
2041                        // compute intersection with all objects in this leaf
2042                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
2043                        ViewCell *vc = leaf->GetViewCell();
2044
2045                        if (!vc->Mailed())
2046                        {
2047                                vc->Mail();
2048                                viewcells.push_back(vc);
2049                                ++ hits;
2050                        }
2051
2052                        if (1) //matt TODO: REMOVE LATER
2053                                leaf->mRays.push_back(RayInfo(new VssRay(origin, termination, NULL, NULL, 0)));
2054
2055                        // get the next node from the stack
2056                        if (tStack.empty())
2057                                break;
2058
2059                        entp = extp;
2060                        mint = maxt;
2061                       
2062                        LineTraversalData &s  = tStack.top();
2063                        node = s.mNode;
2064                        extp = s.mExitPoint;
2065                        maxt = s.mMaxT;
2066                        tStack.pop();
2067                }
2068        }
2069
2070        return hits;
2071}
2072
2073
2074void VspKdTree::GenerateViewCell(VspKdLeaf *leaf)
2075{
2076        RayInfoContainer::const_iterator it, it_end = leaf->GetRays().end();
2077
2078        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(mViewCellsManager->GenerateViewCell());
2079        leaf->SetViewCell(vc);
2080
2081        vc->SetVolume(GetBBox(leaf).GetVolume());
2082        vc->SetArea(GetBBox(leaf).SurfaceArea());
2083
2084        vc->mLeaves.push_back(leaf);
2085
2086        for (it = leaf->GetRays().begin(); it != it_end; ++ it)
2087        {
2088                VssRay *ray = (*it).mRay;
2089
2090                if (ray->mTerminationObject)
2091                  vc->GetPvs().AddSample(ray->mTerminationObject);
2092
2093                if (ray->mOriginObject)
2094                  vc->GetPvs().AddSample(ray->mOriginObject);
2095        }
2096}
2097
2098
2099bool VspKdTree::MergeViewCells(VspKdLeaf *l1, VspKdLeaf *l2)
2100{
2101        //-- change pointer to view cells of all leaves associated
2102        //-- with the previous view cells
2103        VspKdViewCell *fVc = l1->GetViewCell();
2104        VspKdViewCell *bVc = l2->GetViewCell();
2105
2106        VspKdViewCell *vc = dynamic_cast<VspKdViewCell *>(
2107                mViewCellsManager->MergeViewCells(*fVc, *bVc));
2108
2109        // if merge was unsuccessful
2110        if (!vc) return false;
2111
2112        // set new size of view cell
2113        vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
2114        // new area
2115        vc->SetArea(fVc->GetArea() + bVc->GetArea());
2116
2117        vector<VspKdLeaf *> fLeaves = fVc->mLeaves;
2118        vector<VspKdLeaf *> bLeaves = bVc->mLeaves;
2119
2120        vector<VspKdLeaf *>::const_iterator it;
2121
2122        //-- change view cells of all the other leaves the view cell belongs to
2123        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2124        {
2125                (*it)->SetViewCell(vc);
2126                vc->mLeaves.push_back(*it);
2127        }
2128
2129        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2130        {
2131                (*it)->SetViewCell(vc);
2132                vc->mLeaves.push_back(*it);
2133        }
2134
2135        vc->Mail();
2136
2137        // clean up old view cells
2138        DEL_PTR(fVc);
2139        DEL_PTR(bVc);
2140
2141        return true;
2142}
2143
2144void VspKdTree::CollectMergeCandidates()
2145{
2146        MergeCandidate::sOverallCost = 0;
2147        vector<VspKdLeaf *> leaves;
2148
2149        // collect the leaves, e.g., the "voxels" that will build the view cells
2150        CollectLeaves(leaves);
2151
2152        VspKdLeaf::NewMail();
2153
2154        vector<VspKdLeaf *>::const_iterator it, it_end = leaves.end();
2155
2156        // generate view cells
2157        for (it = leaves.begin(); it != it_end; ++ it)
2158                GenerateViewCell(*it);
2159
2160        // find merge candidates and push them into queue
2161        for (it = leaves.begin(); it != it_end; ++ it)
2162        {
2163                VspKdLeaf *leaf = *it;
2164
2165                // no leaf is part of two merge candidates
2166                if (!leaf->Mailed())
2167                {
2168                        leaf->Mail();
2169
2170                        vector<VspKdLeaf *> neighbors;
2171                        FindNeighbors(leaf, neighbors, true);
2172
2173                        vector<VspKdLeaf *>::const_iterator nit,
2174                                nit_end = neighbors.end();
2175
2176                        for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2177                        {
2178                                // TODO: test if at least one ray goes from one leaf to the other
2179                                MergeCandidate mc = MergeCandidate(leaf, *nit);
2180                                mMergeQueue.push(mc);
2181
2182                                MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
2183                                MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
2184                        }
2185                }
2186        }
2187}
2188
2189/*
2190void VspKdTree::CollectMergeCandidates(const vector<VspKdRay *> &rays)
2191{
2192        MergeCandidate::sOverallCost = 0;
2193
2194        vector<VspKdIntersection>::const_iterator iit;
2195
2196        for (int i = 0; i < (int)rays.size(); ++ i)
2197        { 
2198                //VspKdLeaf::NewMail();
2199
2200                VspKdRay *ray = rays[i];
2201         
2202                // traverse leaves stored in the rays and compare and merge consecutive
2203                // leaves (i.e., the neighbors in the tree)
2204                if (ray->intersections.size() < 2)
2205                        continue;
2206         
2207                iit = ray->intersections.begin();
2208
2209                BspLeaf *previousLeaf = (*iit).mLeaf;
2210       
2211                ++ iit;
2212               
2213                for (; iit != ray->intersections.end(); ++ iit)
2214                {
2215            BspLeaf *leaf = (*iit).mLeaf;
2216                       
2217                        // TODO: how to sort out doubles?
2218                        MergeCandidate mc = MergeCandidate(leaf, previousLeaf);
2219                        mMergeQueue.push(mc);
2220
2221                        MergeCandidate::sOverallCost += mc.GetLeaf1Cost();
2222                        MergeCandidate::sOverallCost += mc.GetLeaf2Cost();
2223
2224                        previousLeaf = leaf;
2225        }
2226        }
2227}
2228*/
2229
2230int VspKdTree::MergeLeaves()
2231{
2232        int merged = 0;
2233
2234        int vcSize = mStat.nodes / 2 + 1;
2235        // use priority queue to merge leaves
2236        while (!mMergeQueue.empty() && (vcSize > mMergeMinViewCells) &&
2237                   (mMergeQueue.top().GetMergeCost() <
2238                    mMergeMaxCostRatio * MergeCandidate::sOverallCost))
2239        {
2240                //Debug << "mergecost: " << mergeQueue.top().GetMergeCost() / MergeCandidate::sOverallCost << " " << mMergeMaxCostRatio << endl;
2241                MergeCandidate mc = mMergeQueue.top();
2242                mMergeQueue.pop();
2243
2244                // both view cells equal!
2245                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2246                        continue;
2247
2248                if (mc.Valid())
2249                {
2250                        ViewCell::NewMail();
2251                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2252
2253                        ++ merged;
2254                        -- vcSize;
2255                        // increase absolute merge cost
2256                        MergeCandidate::sOverallCost += mc.GetMergeCost();
2257                }
2258                // merge candidate not valid, because one of the leaves was already
2259                // merged with another one
2260                else
2261                {
2262                        // validate and reinsert into queue
2263                        mc.SetValid();
2264                        mMergeQueue.push(mc);
2265                        //Debug << "validate " << mc.GetMergeCost() << endl;
2266                }
2267        }
2268
2269        // collapse siblings belonging to the same view cell
2270        CollapseTree(mRoot);
2271        // revalidate leaves
2272        RepairVcLeafLists();
2273
2274        Debug << "merged " << merged << " of " << mStat.nodes / 2 + 1 << " leaves" << endl;
2275
2276        //TODO: should return sample contributions
2277        return merged;
2278}
2279
2280
2281void VspKdTree::RepairVcLeafLists()
2282{
2283        // list not valid anymore => clear
2284        stack<VspKdNode *> nodeStack;
2285        nodeStack.push(mRoot);
2286
2287        ViewCell::NewMail();
2288
2289        while (!nodeStack.empty())
2290        {
2291                VspKdNode *node = nodeStack.top();
2292                nodeStack.pop();
2293
2294                if (node->IsLeaf())
2295                {
2296                        VspKdLeaf *leaf = dynamic_cast<VspKdLeaf *>(node);
2297
2298                        VspKdViewCell *viewCell = leaf->GetViewCell();
2299
2300                        if (!viewCell->Mailed())
2301                        {
2302                                viewCell->mLeaves.clear();
2303                                viewCell->Mail();
2304                        }
2305
2306                        viewCell->mLeaves.push_back(leaf);
2307                }
2308                else
2309                {
2310                        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
2311
2312                        nodeStack.push(interior->GetFront());
2313                        nodeStack.push(interior->GetBack());
2314                }
2315        }
2316}
2317
2318
2319VspKdNode *VspKdTree::CollapseTree(VspKdNode *node)
2320{
2321    if (node->IsLeaf())
2322                return node;
2323
2324        VspKdInterior *interior = dynamic_cast<VspKdInterior *>(node);
2325
2326        VspKdNode *front = CollapseTree(interior->GetFront());
2327        VspKdNode *back = CollapseTree(interior->GetBack());
2328
2329        if (front->IsLeaf() && back->IsLeaf())
2330        {
2331                VspKdLeaf *frontLeaf = dynamic_cast<VspKdLeaf *>(front);
2332                VspKdLeaf *backLeaf = dynamic_cast<VspKdLeaf *>(back);
2333
2334                //-- collapse tree
2335                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
2336                {
2337                        VspKdViewCell *vc = frontLeaf->GetViewCell();
2338
2339                        VspKdLeaf *leaf = new VspKdLeaf(interior->GetParent(), 0);
2340                        leaf->SetViewCell(vc);
2341
2342                        // replace a link from node's parent
2343                        if (leaf->mParent)
2344                                leaf->mParent->ReplaceChildLink(node, leaf);
2345
2346                        delete interior;
2347
2348                        return leaf;
2349                }
2350        }
2351
2352        return node;
2353}
2354
2355
2356void VspKdTree::RefineViewCells()
2357{
2358}
2359
2360
2361/*********************************************************************/
2362/*                MergeCandidate implementation                      */
2363/*********************************************************************/
2364
2365
2366MergeCandidate::MergeCandidate(VspKdLeaf *l1, VspKdLeaf *l2):
2367mMergeCost(0),
2368mLeaf1(l1),
2369mLeaf2(l2),
2370mLeaf1Id(l1->GetViewCell()->mMailbox),
2371mLeaf2Id(l2->GetViewCell()->mMailbox)
2372{
2373        EvalMergeCost();
2374}
2375
2376float MergeCandidate::GetLeaf1Cost() const
2377{
2378        VspKdViewCell *vc = mLeaf1->GetViewCell();
2379        return vc->GetPvs().GetSize() * vc->GetVolume();
2380}
2381
2382float MergeCandidate::GetLeaf2Cost() const
2383{
2384        VspKdViewCell *vc = mLeaf2->GetViewCell();
2385        return vc->GetPvs().GetSize() * vc->GetVolume();
2386}
2387
2388void MergeCandidate::EvalMergeCost()
2389{
2390        //-- compute pvs difference
2391        VspKdViewCell *vc1 = mLeaf1->GetViewCell();
2392        VspKdViewCell *vc2 = mLeaf2->GetViewCell();
2393
2394        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
2395        const int vcPvs = diff1 + vc1->GetPvs().GetSize();
2396
2397        //-- compute ratio of old cost
2398        //-- (added size of left and right view cell times pvs size)
2399        //-- to new rendering cost (size of merged view cell times pvs size)
2400        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
2401       
2402        const float newCost =
2403                (float)vcPvs * (vc1->GetVolume() + vc2->GetVolume());
2404
2405        mMergeCost = newCost - oldCost;
2406
2407//      if (vcPvs > sMaxPvsSize) // strong penalty if pvs size too large
2408//              mMergeCost += 1.0;
2409}
2410
2411void MergeCandidate::SetLeaf1(VspKdLeaf *l)
2412{
2413        mLeaf1 = l;
2414}
2415
2416void MergeCandidate::SetLeaf2(VspKdLeaf *l)
2417{
2418        mLeaf2 = l;
2419}
2420
2421
2422VspKdLeaf *MergeCandidate::GetLeaf1()
2423{
2424        return mLeaf1;
2425}
2426
2427
2428VspKdLeaf *MergeCandidate::GetLeaf2()
2429{
2430        return mLeaf2;
2431}
2432
2433
2434bool MergeCandidate::Valid() const
2435{
2436        return
2437                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
2438                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
2439}
2440
2441
2442float MergeCandidate::GetMergeCost() const
2443{
2444        return mMergeCost;
2445}
2446
2447
2448void MergeCandidate::SetValid()
2449{
2450        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
2451        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
2452
2453        EvalMergeCost();
2454}
Note: See TracBrowser for help on using the repository browser.