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

Revision 465, 52.8 KB checked in by mattausch, 19 years ago (diff)

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