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

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