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

Revision 462, 52.6 KB checked in by mattausch, 19 years ago (diff)

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