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

Revision 472, 53.3 KB checked in by mattausch, 19 years ago (diff)

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