source: GTP/trunk/Lib/Vis/Preprocessing/src/OspTree.cpp @ 2542

Revision 2542, 60.6 KB checked in by mattausch, 17 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "ViewCell.h"
6#include "Plane3.h"
7#include "OspTree.h"
8#include "Mesh.h"
9#include "common.h"
10#include "Environment.h"
11#include "Polygon3.h"
12#include "Ray.h"
13#include "AxisAlignedBox3.h"
14#include "Exporter.h"
15#include "Plane3.h"
16#include "ViewCellsManager.h"
17#include "Beam.h"
18#include "KdTree.h"
19#include "IntersectableWrapper.h"
20#include "VspTree.h"
21
22using namespace std;
23
24
25namespace GtpVisibilityPreprocessor {
26
27
28#define USE_FIXEDPOINT_T 0
29
30
31int MailablePvsData::sMailId = 1;
32int MailablePvsData::sReservedMailboxes = 1;
33
34
35        ////////////
36//-- static members
37
38OspTree *OspTree::OspSubdivisionCandidate::sOspTree = NULL;
39
40// variable for debugging volume contribution for heuristics
41static float debugVol;
42
43static bool ViewCellHasMultipleReferences(Intersectable *obj,
44                                                                                  ViewCell *vc,
45                                                                                  bool checkOnlyMailed)
46{
47        // no view cell pvs!!
48/*      MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
49
50        if (vdata)
51        {
52                // more than one view cell sees this object inside different kd cells
53                if (!checkOnlyMailed || !vdata->Mailed())
54                {
55                        if (checkOnlyMailed)
56                                vdata->Mail();
57                        //Debug << "sumpdf: " << vdata->mSumPdf << endl;
58                        if (vdata->mSumPdf > 1.5f)
59                                return true;
60                }
61        }*/
62
63        return false;
64}
65
66
67void OspTreeStatistics::Print(ostream &app) const
68{
69        app << "=========== OspTree statistics ===============\n";
70
71        app << setprecision(4);
72
73        app << "#N_CTIME  ( Construction time [s] )\n" << Time() << " \n";
74
75        app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
76
77        app << "#N_INTERIORS ( Number of interior nodes )\n" << Interior() << "\n";
78
79        app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
80
81        app << "#AXIS_ALIGNED_SPLITS (number of axis aligned splits)\n" << splits[0] + splits[1] + splits[2] << endl;
82
83        app << "#N_SPLITS ( Number of splits in axes x y z)\n";
84
85        for (int i = 0; i < 3; ++ i)
86                app << splits[i] << " ";
87        app << endl;
88
89        app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maximum depth )\n"
90                <<      maxDepthNodes * 100 / (double)Leaves() << endl;
91
92        app << "#N_PMINPVSLEAVES  ( Percentage of leaves with mininimal PVS )\n"
93                << minPvsNodes * 100 / (double)Leaves() << endl;
94
95        //app << "#N_PMINOBJECTREFLEAVES  ( Percentage of leaves with minimal number of object ref)\n"
96                //<< minObjectNodes * 100 / (double)Leaves() << endl;
97
98        app << "#N_MAXCOSTNODES  ( Percentage of leaves with terminated because of max cost ratio )\n"
99                << maxCostNodes * 100 / (double)Leaves() << endl;
100
101        app << "#N_PMINPROBABILITYLEAVES  ( Percentage of leaves with mininum probability )\n"
102                << minProbabilityNodes * 100 / (double)Leaves() << endl;
103
104        app << "#N_PMAXDEPTH ( Maximal reached depth )\n" << maxDepth << endl;
105
106        app << "#N_PMINDEPTH ( Minimal reached depth )\n" << minDepth << endl;
107
108        app << "#AVGDEPTH ( average depth )\n" << AvgDepth() << endl;
109
110        app << "#N_INVALIDLEAVES (number of invalid leaves )\n" << invalidLeaves << endl;
111
112        app << "#N_MAXOBJECTREFS  ( Max number of object refs / leaf )\n" <<
113                 maxObjectRefs << "\n";
114
115//      app << "#N_RAYS (number of rays / leaf)\n" << AvgRays() << endl;
116        //app << "#N_PVS: " << pvs << endl;
117
118        app << "========== END OF VspTree statistics ==========\n";
119}
120
121
122/******************************************************************/
123/*                  class VspNode implementation                  */
124/******************************************************************/
125
126
127/*******************************************************************/
128/*                  class OspTree implementation                   */
129/*******************************************************************/
130
131
132OspTree::OspTree():
133mRoot(NULL),
134mTimeStamp(1),
135mCopyFromKdTree(false)
136{
137        ReadEnvironment();
138        mSubdivisionCandidates = new vector<SortableEntry>;
139}
140
141
142OspTree::OspTree(const KdTree &kdTree)
143{
144        ReadEnvironment();
145
146        // copy values from kd tree
147        mCopyFromKdTree = true;
148        mBoundingBox = kdTree.GetBox();
149        mRoot = kdTree.GetRoot();
150
151        mSubdivisionCandidates = new vector<SortableEntry>;
152}
153
154
155OspTree::~OspTree()
156{
157        // delete kd intersectables
158        KdIntersectableMap::iterator it, it_end = mKdIntersectables.end();
159
160        for (it = mKdIntersectables.begin(); it != mKdIntersectables.end(); ++ it)
161        {
162                DEL_PTR((*it).second);
163        }
164
165        // delete hierarchy only if not using the hierarchy from
166        // some other kd tree (otherwise the other kd tree has to do the job)
167        if (!mCopyFromKdTree)
168                DEL_PTR(mRoot);
169
170        DEL_PTR(mSubdivisionCandidates);
171        mSubdivisionStats.close();
172}
173
174
175void OspTree::ReadEnvironment()
176{
177        bool randomize = false;
178        Environment::GetSingleton()->GetBoolValue("VspTree.Construction.randomize", randomize);
179        if (randomize)
180                Randomize(); // initialise random generator for heuristics
181
182        //-- termination criteria for autopartition
183        Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxDepth", mTermMaxDepth);
184        Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
185        Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
186        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinProbability);
187       
188        Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
189       
190        //-- max cost ratio for early tree termination
191        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.maxCostRatio", mTermMaxCostRatio);
192
193        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minGlobalCostRatio",
194                mTermMinGlobalCostRatio);
195       
196
197        //-- factors for bsp tree split plane heuristics
198        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.ct_div_ci", mCtDivCi);
199
200        //-- partition criteria
201        Environment::GetSingleton()->GetFloatValue("OspTree.Construction.epsilon", mEpsilon);
202
203        // if only the driving axis is used for axis aligned split
204        Environment::GetSingleton()->GetBoolValue("OspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
205        Environment::GetSingleton()->GetFloatValue("OspTree.maxStaticMemory", mMaxMemory);
206        Environment::GetSingleton()->GetBoolValue("OspTree.useCostHeuristics", mUseCostHeuristics);
207
208
209        char subdivisionStatsLog[100];
210        Environment::GetSingleton()->GetStringValue("OspTree.subdivisionStats", subdivisionStatsLog);
211        mSubdivisionStats.open(subdivisionStatsLog);
212
213        Environment::GetSingleton()->GetFloatValue("OspTree.Construction.splitBorder", mSplitBorder);
214        Environment::GetSingleton()->GetFloatValue(
215                "OspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
216       
217
218        //-- debug output
219
220        Debug << "******* OSP tree options ******** " << endl;
221
222    Debug << "max depth: " << mTermMaxDepth << endl;
223        Debug << "min probabiliy: " << mTermMinProbability << endl;
224        Debug << "min objects: " << mTermMinObjects << endl;
225        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
226        Debug << "miss tolerance: " << mTermMissTolerance << endl;
227        Debug << "max leaves: " << mTermMaxLeaves << endl;
228
229        Debug << "randomize: " << randomize << endl;
230
231        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
232        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
233        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
234        Debug << "max memory: " << mMaxMemory << endl;
235        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
236        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
237       
238        Debug << "split borders: " << mSplitBorder << endl;
239        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
240        Debug << endl;
241}
242
243
244void OspTree::SplitObjects(KdLeaf *parent,
245                                                   const AxisAlignedPlane& splitPlane,
246                                                   const ObjectContainer &objects,
247                                                   ObjectContainer &front,
248                                                   ObjectContainer &back)
249{
250        ObjectContainer::const_iterator oit, oit_end = objects.end();
251
252    for (oit = objects.begin(); oit != oit_end; ++ oit)
253        {
254                Intersectable *object = *oit;
255               
256                // initialise leaf references of objects
257                if (parent->IsRoot())
258                {
259                        // matt: no more parent ref
260                        //object->mReferences = 1;
261                }
262
263                // remove parent ref
264                // matt: no more parent ref
265                //-- object->mReferences;
266
267                // determine the side of this ray with respect to the plane
268                const AxisAlignedBox3 box = object->GetBox();
269
270                if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
271                {
272            front.push_back(object);
273                        // matt: no more ref
274                        //++ object->mReferences;
275                }
276
277                if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
278                {
279                        back.push_back(object);
280                        // matt: no more ref
281                        //++ object->mReferences;
282                }
283        }
284
285        mOspStats.objectRefs -= (int)objects.size();
286        mOspStats.objectRefs += (int)(back.size() + front.size());
287}
288
289
290KdInterior *OspTree::SubdivideNode(
291                                                                   const AxisAlignedPlane &splitPlane,
292                                                                   const OspTraversalData &tData,
293                                                                   OspTraversalData &frontData,
294                                                                   OspTraversalData &backData
295                                                                   )
296{
297        KdLeaf *leaf = tData.mNode;
298       
299        // two new leaves
300    mOspStats.nodes += 2;
301
302        // add the new nodes to the tree
303        KdInterior *node = new KdInterior(leaf->mParent);
304
305        const int axis = splitPlane.mAxis;
306        const float position = splitPlane.mPosition;
307
308        node->mAxis = axis;
309        node->mPosition = position;
310        node->mBox = tData.mBoundingBox;
311
312
313        //-- the front and back traversal data is filled with the new values
314
315        // bounding boxes: split front and back node geometry
316        tData.mBoundingBox.Split(splitPlane.mAxis, splitPlane.mPosition,
317                frontData.mBoundingBox, backData.mBoundingBox);
318
319        frontData.mDepth = backData.mDepth = tData.mDepth + 1;
320               
321        //-- subdivide rays
322        frontData.mRays = new RayInfoContainer();
323        backData.mRays = new RayInfoContainer();
324
325/*      SplitRays(splitPlane,
326                          *tData.mRays,
327                          *frontData.mRays,
328                          *backData.mRays);
329*/
330
331        //-- classify objects
332
333        int objectsBack = 0;
334        int objectsFront = 0;
335
336    ObjectContainer::const_iterator mi, mi_end = leaf->mObjects.end();
337
338        for ( mi = leaf->mObjects.begin(); mi != mi_end; ++ mi)
339        {
340                // determine the side of this ray with respect to the plane
341                const AxisAlignedBox3 box = (*mi)->GetBox();
342               
343                if (box.Max(axis) >= position)
344                        ++ objectsFront;
345   
346                if (box.Min(axis) < position)
347                        ++ objectsBack;
348        }
349
350
351        // TODO matt: compute pvs
352        //frontData.mPvs = objectsFront;
353        //backData.mPvs = objectsBack;
354
355        //CheckViewCellsPvs(leaf, *tData.mRays);
356        RemoveParentViewCellsPvs(leaf, *tData.mRays);
357
358
359        /////////////
360        //-- create front and back leaf
361
362        KdLeaf *back = new KdLeaf(node, objectsBack);
363        KdLeaf *front = new KdLeaf(node, objectsFront);
364
365        KdInterior *parent = leaf->mParent;
366
367        // replace a link from node's parent
368        if (parent)
369        {
370                parent->ReplaceChildLink(leaf, node);
371                node->mParent = parent;
372        }
373        else // new root
374        {
375                mRoot = node;
376        }
377
378        // and setup child links
379        node->SetupChildLinks(back, front);
380
381        SplitObjects(leaf, splitPlane, leaf->mObjects, front->mObjects, back->mObjects);
382       
383        FilterRays(front, *tData.mRays, *frontData.mRays);
384        FilterRays(back, *tData.mRays, *backData.mRays);
385
386        ++ mOspStats.splits[splitPlane.mAxis];
387
388        //-- eval view cells pvs
389       
390        // remove parent pvs update pvs of left and right leaves
391        // Note: It is necessary to update first left and then right pvs.
392        // We need to store the view cells seen by each object,
393        // but also if the view cells are seen as part of two different
394        // kd leaves, which is stored in the pdf component of the pvs entry.
395        // Because if an object is part of a view cell more than once,
396        // it cannot be removed from the pvs by splitting a kd node where
397        // the view cell sees only the other child of the node.
398        // This is important during the subdivision
399
400        //MailablePvsData::NewMail();
401        UpdateViewCellsPvs(front, *frontData.mRays);
402        UpdateViewCellsPvs(back, *backData.mRays);
403
404        ////////////////////////////////////
405
406
407        ProcessMultipleRefs(front);
408    ProcessMultipleRefs(back);
409
410        frontData.mNode = front;
411        backData.mNode = back;
412
413        // compute probability, i.e., volume of seen view cells
414        frontData.mProbability = EvalViewCellsVolume(front, *frontData.mRays);
415        backData.mProbability =  EvalViewCellsVolume(back, *backData.mRays);
416
417        //delete leaf;
418        return node;
419}
420
421
422KdNode *OspTree::Subdivide(SplitQueue &tQueue,
423                                                   SubdivisionCandidate *splitCandidate,
424                                                   const bool globalCriteriaMet)
425{
426        OspSubdivisionCandidate *sc = static_cast<OspSubdivisionCandidate *>(splitCandidate);
427        OspTraversalData &tData = sc->mParentData;
428
429        KdNode *newNode = tData.mNode;
430
431        if (!LocalTerminationCriteriaMet(tData) && !globalCriteriaMet)
432        {       
433                OspTraversalData tFrontData;
434                OspTraversalData tBackData;
435
436                //-- continue subdivision
437               
438                // create new interior node and two leaf node
439                const AxisAlignedPlane splitPlane = sc->mSplitPlane;
440               
441                newNode = SubdivideNode(splitPlane,
442                                                                tData,
443                                                                tFrontData,
444                                                                tBackData);
445       
446                const int maxCostMisses = sc->GetMaxCostMisses();
447
448        // how often was max cost ratio missed in this branch?
449                tFrontData.mMaxCostMisses = maxCostMisses;
450                tBackData.mMaxCostMisses = maxCostMisses;
451               
452                mTotalCost -= sc->GetRenderCostDecrease();
453
454                // subdivision statistics
455                if (1) EvalSubdivisionStats(*sc);
456
457                //-- push the new split candidates on the queue
458               
459                OspSubdivisionCandidate *frontCandidate = new OspSubdivisionCandidate(tFrontData);
460                OspSubdivisionCandidate *backCandidate = new OspSubdivisionCandidate(tBackData);
461
462                EvalSubdivisionCandidate(*frontCandidate);
463                EvalSubdivisionCandidate(*backCandidate);
464
465                tQueue.Push(frontCandidate);
466                tQueue.Push(backCandidate);
467
468                // delete old leaf node
469                DEL_PTR(tData.mNode);
470        }
471
472
473        //-- terminate traversal
474        if (newNode->IsLeaf())
475        {
476                EvaluateLeafStats(tData);
477       
478                const bool mStoreRays= true;
479
480                //-- store additional info
481                if (mStoreRays)
482                {
483                        KdLeaf *leaf = static_cast<KdLeaf *>(newNode);
484
485                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
486
487                        for (it = tData.mRays->begin(); it != it_end; ++ it)
488                        {
489                                (*it).mRay->Ref();                     
490                                leaf->mVssRays.push_back((*it).mRay);
491                        }
492                }
493        }
494       
495        //-- cleanup
496        tData.Clear();
497       
498        return newNode;
499}
500
501
502void OspTree::EvalSubdivisionCandidate(OspSubdivisionCandidate &splitCandidate)
503{
504        // compute locally best split plane
505        const float ratio = SelectSplitPlane(splitCandidate.mParentData,
506                                                                                 splitCandidate.mSplitPlane);
507
508        const bool success = ratio < mTermMaxCostRatio;
509        float oldRenderCost;
510
511        // compute global decrease in render cost
512        const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
513                                                                                                                splitCandidate.mParentData,
514                                                                                                                oldRenderCost);
515
516        splitCandidate.SetRenderCostDecrease(renderCostDecr);
517
518        const float pvsSizeIncr = 0; // todo
519#if 0
520        const float priority = (float)-data.mDepth;
521#else   
522        // take render cost of node into account
523        // otherwise danger of being stuck in a local minimum!!
524        const float factor = mRenderCostDecreaseWeight;
525        const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
526
527#endif
528
529        // compute global decrease in render cost
530        splitCandidate.SetPriority(priority);
531
532        splitCandidate.SetMaxCostMisses(success ?
533                splitCandidate.mParentData.mMaxCostMisses :
534                splitCandidate.mParentData.mMaxCostMisses + 1);
535}
536
537
538inline bool OspTree::LocalTerminationCriteriaMet(const OspTraversalData &data) const
539{
540        // matt: TODO
541        return (
542                //(data.mNode->mObjects.size() < mTermMinObjects) ||
543                //(data.mProbability <= mTermMinProbability) ||
544                (data.mDepth >= mTermMaxDepth)
545                 );
546}
547
548
549inline  bool OspTree::GlobalTerminationCriteriaMet(const OspTraversalData &data) const
550{
551        // matt: TODO
552        return (0
553                || (mOspStats.Leaves() >= mTermMaxLeaves)
554                //|| mOutOfMemory
555                || (mGlobalCostMisses >= mTermGlobalCostMissTolerance)
556                );
557}
558
559
560void OspTree::EvaluateLeafStats(const OspTraversalData &data)
561{
562        // the node became a leaf -> evaluate stats for leafs
563        KdLeaf *leaf = data.mNode;
564       
565        ++ mCreatedLeaves;
566
567        /*if (data.mPvs > mOspStats.maxPvs)
568        {
569                mOspStats.maxPvs = data.mPvs;
570        }
571
572        mOspStats.pvs += data.mPvs;
573
574        if (data.mDepth < mOspStats.minDepth)
575        {
576                mOspStats.minDepth = data.mDepth;
577        }*/
578       
579        if (data.mDepth >= mTermMaxDepth)
580        {
581        ++ mOspStats.maxDepthNodes;
582                //Debug << "new max depth: " << mVspStats.maxDepthNodes << endl;
583        }
584
585        if (data.mProbability <= mTermMinProbability)
586                ++ mOspStats.minProbabilityNodes;
587       
588        // accumulate depth to compute average depth
589        mOspStats.accumDepth += data.mDepth;
590 
591        //      if ((int)(leaf->mObjects.size()) < mTermMinCost)
592        //     ++ mOspStats.minCostNodes;
593 
594        if ((int)(leaf->mObjects.size()) > mOspStats.maxObjectRefs)
595                mOspStats.maxObjectRefs = (int)leaf->mObjects.size();
596
597#ifdef GTP_DEBUG
598        Debug << "BSP stats: "
599                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
600                  << "Prob: " << data.mProbability << " (min: " << mTermMinProbability << ")\n";
601#endif
602}
603
604
605float OspTree::EvalLocalCostHeuristics(const OspTraversalData &tData,
606                                                                           const AxisAlignedBox3 &box,
607                                                                           const int axis,
608                                                                           float &position,
609                                                                           int &objectsFront,
610                                                                           int &objectsBack)
611{
612        RayInfoContainer usedRays;
613        int mMaxTests = 500000; // HACK
614
615        if (mMaxTests < (int)tData.mRays->size())
616        {
617                GetRayInfoSets(*tData.mRays, mMaxTests, usedRays);
618        }
619        else
620        {
621                usedRays = *tData.mRays;
622        }
623
624        // go through the lists, count the number of objects left and right
625        // and evaluate the following cost funcion:
626        // C = ct_div_ci  + (ol + or)/queries
627       
628        const float minBox = box.Min(axis);
629        const float maxBox = box.Max(axis);
630        Debug << "min: " << minBox << " max: " << maxBox << endl;
631
632        const float sizeBox = maxBox - minBox;
633
634        float minBand = minBox + mSplitBorder * (maxBox - minBox);
635        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
636
637        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
638
639        //-- sort so we can use a sweep
640        SortSubdivisionCandidates(tData, axis, minBand, maxBand);
641
642        float totalVol = 0;
643        float voll = 0;
644        float volr = totalVol;
645
646        ViewCellContainer touchedViewCells;
647       
648        const float totalRenderCost = PrepareHeuristics(tData, touchedViewCells);
649        float renderCost = totalRenderCost;
650
651        /// this is kind of a reverse pvs
652        const int totalPvs = (int)tData.mNode->mObjects.size();
653       
654        int pvsl = 0;
655        int pvsr = totalPvs;
656
657        float sum = (float)totalVol * sizeBox;
658
659        Debug << "total render cost: " << renderCost / viewSpaceVol << endl;
660
661        /////////////////////////////////
662
663        // note: initialised to take mid split
664        // if no good split can be found,
665        position = minBox + 0.5f * sizeBox;
666       
667        // the relative cost ratio
668        float ratio = 99999999.0f;
669        bool splitPlaneFound = false;
670
671        float volBack = voll;
672        float volFront = volr;
673
674        int pvsBack = pvsl;
675        int pvsFront = pvsr;
676       
677        float minRenderCost = 1e20f;
678
679        debugVol = 0;
680
681
682
683        /////////////////////////////
684        // the sweep heuristics
685
686       
687        //-- traverse through events and find best split plane
688       
689        vector<SortableEntry>::const_iterator ci, ci_end = mSubdivisionCandidates->end();
690        //minRenderCost = RandomValue(0,viewSpaceVol);
691
692        for (ci = mSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
693        {
694                Intersectable *object = (*ci).mObject;
695
696                EvalHeuristicsContribution(tData.mNode,
697                                                                   *ci,
698                                                                   renderCost,
699                                                                   touchedViewCells
700                                                                  );
701
702                // Note: sufficient to compare size of bounding boxes of front and back side?
703                if (((*ci).mPos >= minBand) && ((*ci).mPos <= maxBand))
704                {
705                        float currentPos;
706                        Debug << "current min: " << minRenderCost / viewSpaceVol << endl;
707
708                        // HACK: current positition is BETWEEN visibility events
709                        if (1 && /*((*ci).mType == SortableEntry::BOX_INTERSECT) &&*/ ((ci + 1) != ci_end))
710                                currentPos = ((*ci).mPos + (*(ci + 1)).mPos) * 0.5f;
711                        else
712                                currentPos = (*ci).mPos;                       
713
714                        if (renderCost < minRenderCost)
715                        {
716                                splitPlaneFound = true;
717                                minRenderCost = renderCost;
718                                position = currentPos;
719                                Debug << "pos: " << position << endl;
720                        }
721                }
722        }
723//splitPlaneFound = true;
724        if (splitPlaneFound)
725        {
726                ratio = minRenderCost / totalRenderCost;
727        }
728#if GTP_DEBUG
729        Debug << "\n§§§§ eval local cost §§§§" << endl
730                  << "old rc: " << totalRenderCost / viewSpaceVol << " new rc: " << minRenderCost / viewSpaceVol << endl
731                  << "render cost decrease: " << (totalRenderCost - minRenderCost) / viewSpaceVol  << endl;
732#endif
733        return ratio;
734}
735
736
737void OspTree::SortSubdivisionCandidates(const OspTraversalData &tData,
738                                                                  const int axis,
739                                                                  float minBand,
740                                                                  float maxBand)
741
742{
743        mSubdivisionCandidates->clear();
744
745        RayInfoContainer *rays = tData.mRays;
746        KdLeaf *leaf = tData.mNode;
747
748        int requestedSize = 2 * (int)rays->size() + 2 * (int)leaf->mObjects.size();
749
750        // creates a sorted split candidates array
751        if (mSubdivisionCandidates->capacity() > 500000 &&
752                requestedSize < (int)(mSubdivisionCandidates->capacity() / 10) )
753        {
754        delete mSubdivisionCandidates;
755                mSubdivisionCandidates = new vector<SortableEntry>;
756        }
757
758        mSubdivisionCandidates->reserve(requestedSize);
759
760        float pos;
761
762        //-- insert ray queries
763        //-- we are intersested only in rays which intersect an object that
764        //-- is part of the kd node because they can induce a change in view cell
765        //-- volume on the left and the right part.
766        //-- Note that they cannot induce a change in pvs size!!
767
768        RayInfoContainer::const_iterator rit, rit_end = rays->end();
769
770        for (rit = rays->begin(); rit < rit_end; ++ rit)
771        {
772                VssRay *ray = (*rit).mRay;
773
774                const bool positive = ray->HasPosDir(axis);
775       
776                if (EndPointInsideNode(leaf, *ray, true))
777                {
778                        pos = ray->mTermination[axis];
779
780                        mSubdivisionCandidates->push_back(
781                                SortableEntry(SortableEntry::BOX_INTERSECT,
782                                                          pos,
783                                                          ray->mTerminationObject,
784                                                          ray)
785                                                          );
786                }
787
788                // if hitpoint with object is inside this node
789                if (EndPointInsideNode(leaf, *ray, false))
790                {
791                        pos = ray->mOrigin[axis];
792       
793                        mSubdivisionCandidates->push_back(
794                                SortableEntry(SortableEntry::BOX_INTERSECT,
795                                                          pos,
796                                                          ray->mOriginObject,
797                                                          ray)
798                                                          );
799                }
800        }
801
802
803        //-- insert object queries
804        //-- These queries can induce a change in pvs size.
805        //-- Note that they cannot induce a change in view cell volume, as
806        //-- there is no ray associated with these events!!
807
808        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
809
810    for (oit = leaf->mObjects.begin(); oit != leaf->mObjects.end(); ++ oit )
811        {
812                Intersectable *object = *oit;
813                const AxisAlignedBox3 box = object->GetBox();
814
815                mSubdivisionCandidates->push_back(
816                        SortableEntry(SortableEntry::BOX_MIN,
817                                                  box.Min(axis),
818                                                  object,
819                                                  NULL)
820                                                  );
821   
822   
823                mSubdivisionCandidates->push_back(
824                        SortableEntry(SortableEntry::BOX_MAX,
825                                                  box.Max(axis),
826                                                  object,
827                                                  NULL)
828                                                  );
829        }
830
831        stable_sort(mSubdivisionCandidates->begin(), mSubdivisionCandidates->end());
832}
833
834
835const OspTreeStatistics &OspTree::GetStatistics() const
836{
837        return mOspStats;
838}
839
840
841void OspTree::PrepareHeuristics(const VssRay &ray,
842                                                                ViewCellContainer &touchedViewCells)
843{
844        // collect view cells and set mail + counter
845        ViewCellContainer viewCells;
846        mVspTree->GetViewCells(ray, viewCells);
847       
848        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
849
850        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
851        {
852                ViewCell *vc = (*vit);
853
854                if (!vc->Mailed())
855                {
856                        vc->Mail(); // set as belonging to front leaf
857                        vc->mCounter = 0;
858                        touchedViewCells.push_back(vc);
859                }
860               
861                // view cell volume already added => just increase counter
862                ++ vc->mCounter;
863        }
864}
865
866
867float OspTree::PrepareHeuristics(const OspTraversalData &tData,
868                                                                 ViewCellContainer &touchedViewCells)
869{       
870        float renderCost = 0;
871
872        Intersectable::NewMail(3);
873        ViewCell::NewMail(3);
874        MailablePvsData::NewMail();
875
876        KdLeaf *leaf = tData.mNode;
877
878        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
879
880        for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
881        {
882                VssRay *ray = (*rit).mRay;
883        PrepareHeuristics(*ray, touchedViewCells);
884        }
885
886        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
887
888        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
889        {
890                Intersectable *obj = *oit;
891                obj->Mail(); // set as belonging to front leaf
892               
893                ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
894
895                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
896                {
897                        ViewCell *vc = *vit;
898                        // no view cel pvs!!
899                        /*MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
900
901                        if (!vdata) // should never happen
902                                continue;
903
904                        if (!vdata->Mailed())
905                        {
906                                vdata->Mail();
907                                renderCost += vc->GetVolume();
908                        }*/
909                }
910        }
911
912        return renderCost;
913}
914
915
916void OspTree::AddObjectContribution(KdLeaf *leaf,
917                                                  Intersectable *obj,
918                                                  ViewCellContainer &touchedViewCells,
919                                                  float &renderCost)
920{
921        //Debug << "add contri to obj: " << obj->mMailbox - Intersectable::sMailId << endl;
922        obj->Mail(2); // set as belonging to both leafs
923
924        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
925       
926        for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
927        {
928                ViewCell *vc = *vit;
929       
930                // if obj not previously associated with this view cell => increase render cost
931                if (vc->Mailed(1) && !ViewCellHasMultipleReferences(obj, vc, false))
932                {       
933                        //Debug << "add to rendercost: " << vc->GetVolume() / mVspTree->GetBoundingBox().GetVolume() << endl;
934                        renderCost += vc->GetVolume();
935                }
936        }
937}
938
939
940void OspTree::SubtractObjectContribution(KdLeaf *leaf,
941                                                                Intersectable * obj,
942                                                                ViewCellContainer &touchedViewCells,
943                                                                float &renderCost)
944{
945        //Debug << "subtract contri from obj: " << obj->mMailbox - Intersectable::sMailId << endl;
946    obj->Mail(1); // set as belonging to back leaf
947        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
948       
949        for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
950        {
951                ViewCell *vc = *vit;
952
953                // if obj was previously associated with this view cell but is not now
954                // => decrease render cost
955                if (vc->Mailed() &&     !ViewCellHasMultipleReferences(obj, vc, false))
956                {
957                        //Debug << "subtract from rendercost: " << vc->GetVolume() / mVspTree->GetBoundingBox().GetVolume() << endl;
958                        renderCost -= vc->GetVolume();
959                }
960        }
961}
962
963
964void OspTree::EvalRayContribution(KdLeaf *leaf,
965                                                                  const VssRay &ray,
966                                                                  float &renderCost)
967{
968        ViewCellContainer viewCells;
969
970        mVspTree->GetViewCells(ray, viewCells);
971
972        // classify view cells and compute volume contri accordingly
973        // possible view cell classifications:
974        // view cell mailed => view cell can be seen from left child node
975        // view cell counter > 0 view cell can be seen from right child node
976        // combined: view cell volume belongs to both nodes
977        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
978       
979        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
980        {
981                EvalViewCellContribution(leaf, *vit, renderCost);
982        }
983}
984
985
986void OspTree::EvalViewCellContribution(KdLeaf *leaf,
987                                                                           ViewCell *viewCell,
988                                                                           float &renderCost)
989{
990        //Debug << "**************" << endl;
991        //Debug << "vc contri: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " " << viewCell->mMailbox - ViewCell::sMailId << " counter: " << viewCell->mCounter << endl;
992
993        const float vol = viewCell->GetVolume();
994
995        if (viewCell->Mailed())
996        {
997                viewCell->Mail(2); // view cell can be seen from both nodes
998
999        // we now see view cell from both nodes => add contri
1000                ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1001
1002                for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1003                {
1004                        Intersectable *obj = *oit;
1005
1006                        // was render cost already added?
1007                        if (!ViewCellHasMultipleReferences(obj, viewCell, false) &&
1008                                obj->Mailed(1))
1009                        {
1010                                //Debug << "obj mail 1!! " << vol / mVspTree->GetBoundingBox().GetVolume() << endl;
1011                                renderCost += vol;
1012                        }
1013                }
1014        }
1015
1016        if (-- viewCell->mCounter == 0)
1017        {
1018                viewCell->Mail(1); // view cell can be seen from back node only
1019
1020                //MailablePvsData::NewMail();
1021                ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1022
1023                for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1024                {
1025                        Intersectable *obj = *oit;
1026
1027                        // can render cost be be reduced?
1028                        if (!ViewCellHasMultipleReferences(obj, viewCell, false) &&     obj->Mailed())
1029                        {
1030                                renderCost -= vol;
1031                        }
1032                }
1033        }
1034        //Debug << "new rc: " << renderCost / mVspTree->GetBoundingBox().GetVolume() << " counter2: " << viewCell->mCounter << endl;
1035        //Debug << "**************"<<endl;
1036}
1037
1038
1039void OspTree::EvalHeuristicsContribution(KdLeaf *leaf,
1040                                                                                 const SortableEntry &ci,
1041                                                                                 float &renderCost,
1042                                                                                 ViewCellContainer &touchedViewCells)
1043{
1044        Intersectable *obj = ci.mObject;
1045        VssRay *ray = ci.mRay;
1046
1047        // switch between different types of events
1048        switch (ci.mType)
1049        {
1050                case SortableEntry::BOX_MIN:
1051                        cout << "<";
1052                        AddObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost); 
1053                        break;
1054                       
1055                case SortableEntry::BOX_MAX:
1056                        cout << ">";
1057                        SubtractObjectContribution(leaf, ci.mObject, touchedViewCells, renderCost);
1058                        break;
1059
1060                // compute volume contribution from view cells
1061                case SortableEntry::BOX_INTERSECT:
1062                        cout << "i";
1063                        // process ray if the hit point with termination / origin object
1064                        // is inside this kd leaf
1065                        EvalRayContribution(leaf, *ray, renderCost);
1066                        break;
1067
1068                default:
1069                        cout << "should not come here" << endl;
1070                        break;
1071        }
1072
1073        //cout << "vol left: " << volLeft << " vol right " << volRight << endl;
1074}
1075
1076
1077void OspTree::SetViewCellsManager(ViewCellsManager *vcm)
1078{
1079        mViewCellsManager = vcm;
1080}
1081
1082
1083AxisAlignedBox3 OspTree::GetBoundingBox() const
1084{
1085        return mBoundingBox;
1086}
1087
1088
1089float OspTree::SelectSplitPlane(const OspTraversalData &tData,
1090                                                                AxisAlignedPlane &plane)
1091{
1092        float nPosition[3];
1093        float nCostRatio[3];
1094
1095        // create bounding box of node geometry
1096        AxisAlignedBox3 box = tData.mBoundingBox;
1097               
1098        int sAxis = 0;
1099        int bestAxis = -1;
1100
1101        if (mOnlyDrivingAxis)
1102        {
1103                sAxis = box.Size().DrivingAxis();
1104        }
1105       
1106
1107        // -- evaluate split cost for all three axis
1108        for (int axis = 0; axis < 3; ++ axis)
1109        {
1110                if (!mOnlyDrivingAxis || (axis == sAxis))
1111                {
1112                        if (1 || mUseCostHeuristics)
1113                        {
1114                                //-- place split plane using heuristics
1115                                int objectsFront, objectsBack;
1116
1117                                nCostRatio[axis] =
1118                                        EvalLocalCostHeuristics(tData,
1119                                                                           tData.mBoundingBox,
1120                                                                           axis,
1121                                                                           nPosition[axis],
1122                                                                           objectsFront,
1123                                                                           objectsBack);                       
1124                        }
1125                        /*      else
1126                        {
1127                                //-- split plane position is spatial median
1128
1129                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1130
1131                                nCostRatio[axis] = EvalLocalSplitCost(tData,
1132                                                                                                          box,
1133                                                                                                          axis,
1134                                                                                                          nPosition[axis],
1135                                                                                                          nProbFront[axis],
1136                                                                                                          nProbBack[axis]);
1137                        }*/
1138                                               
1139                        if (bestAxis == -1)
1140                        {
1141                                bestAxis = axis;
1142                        }
1143                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
1144                        {
1145                                bestAxis = axis;
1146                        }
1147                }
1148        }
1149
1150        //-- assign values
1151
1152        plane.mAxis = bestAxis;
1153        // split plane position
1154    plane.mPosition = nPosition[bestAxis];
1155
1156        Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
1157        return nCostRatio[bestAxis];
1158}
1159
1160
1161bool OspTree::EndPointInsideNode(KdLeaf *leaf,
1162                                                                 VssRay &ray,
1163                                                                 bool isTermination) const
1164{
1165        // test if the leaf where the hitpoint is located is the current leaf
1166        if (isTermination)
1167        {
1168                 return ray.mTerminationObject && (GetLeaf(ray.mTermination, ray.mTerminationNode) == leaf);
1169        }
1170        else
1171        {
1172                return false; // no origin object!
1173                return ray.mOriginObject && (GetLeaf(ray.mOrigin, ray.mOriginNode) == leaf);
1174        }
1175}
1176
1177
1178void OspTree::EvalSubdivisionStats(const SubdivisionCandidate &sc)
1179{
1180        const float costDecr = sc.GetRenderCostDecrease();
1181
1182        AddSubdivisionStats(mOspStats.Leaves(),
1183                                                costDecr,
1184                                                mTotalCost
1185                                                );
1186}
1187
1188
1189void OspTree::AddSubdivisionStats(const int leaves,
1190                                                                  const float renderCostDecr,
1191                                                                  const float totalRenderCost)
1192{
1193        mSubdivisionStats
1194                        << "#Leaves\n" << leaves << endl
1195                        << "#RenderCostDecrease\n" << renderCostDecr << endl
1196                        << "#TotalRenderCost\n" << totalRenderCost << endl;
1197                        //<< "#AvgRenderCost\n" << avgRenderCost << endl;
1198}
1199
1200
1201int OspTree::ClassifyRay(VssRay *ray,
1202                                                 KdLeaf *leaf,
1203                                                 const AxisAlignedPlane &plane) const
1204{
1205        const bool originInside = EndPointInsideNode(leaf, *ray, false);
1206    const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
1207
1208        const bool originGt = (ray->mOrigin[plane.mAxis] >= plane.mPosition);
1209        const bool originLt = (ray->mOrigin[plane.mAxis] <= plane.mPosition);
1210
1211        const bool terminationGt = (ray->mTermination[plane.mAxis] >= plane.mPosition);
1212        const bool terminationLt = (ray->mTermination[plane.mAxis] <= plane.mPosition);
1213
1214        // add view cell volume to front volume
1215        const bool addToFront =
1216                ((originInside && originGt) || (terminationInside && terminationGt));
1217
1218        // add view cell volume to back volume
1219        const bool addToBack =
1220                ((originInside && originLt/*!originGt*/) || (terminationInside && terminationLt/*terminationGt*/));
1221
1222        // classify ray with respect to the child nodes the view cells contribute
1223        if (addToFront && addToBack)
1224                return 0;
1225        else if (addToBack)
1226                return -1;
1227        else if (addToFront)
1228                return 1;
1229
1230        return -2;
1231}
1232
1233
1234int OspTree::ClassifyRays(const RayInfoContainer &rays,
1235                                                  KdLeaf *leaf,
1236                                                  const AxisAlignedPlane &plane,
1237                                                  RayInfoContainer &frontRays,
1238                                                  RayInfoContainer &backRays) const
1239{
1240        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1241
1242        for (rit = rays.begin(); rit < rit_end; ++ rit)
1243        {
1244                VssRay *ray = (*rit).mRay;
1245
1246                bool originGt = false;
1247                bool terminationGt = false;
1248               
1249                Intersectable *obj = ray->mOriginObject;
1250
1251                if (0 && obj)
1252                {
1253                        originGt = ray->mOrigin[plane.mAxis] >= plane.mPosition;
1254                }
1255
1256                obj = ray->mTerminationObject;
1257               
1258                if (obj)
1259                {
1260                        terminationGt = ray->mTermination[plane.mAxis] >= plane.mPosition;
1261                }
1262
1263                // either begin or end point on front side
1264                const bool addToFront = originGt || terminationGt;
1265
1266                // add view cell volume to back volume
1267                const bool addToBack = !originGt || !terminationGt;
1268       
1269                // classify ray with respect to the child nodes the view cells contribute
1270                if (addToFront)
1271                        frontRays.push_back(*rit);
1272                if (addToBack)
1273                        backRays.push_back(*rit);
1274        }
1275
1276        return 0;
1277}
1278
1279
1280float OspTree::EvalRenderCostDecrease(const AxisAlignedPlane &candidatePlane,
1281                                                                          const OspTraversalData &tData,
1282                                                                          float &normalizedOldRenderCost) const
1283{
1284        float pvsFront = 0;
1285        float pvsBack = 0;
1286
1287        // probability that view point lies in back / front node
1288        float pOverall = 0;
1289        float pFront = 0;
1290        float pBack = 0;
1291        float pFrontAndBack = 0;
1292
1293        Intersectable::NewMail(3);
1294        KdLeaf *leaf = tData.mNode;
1295
1296        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
1297        const int totalPvs = (int)leaf->mObjects.size();
1298       
1299        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1300
1301        // evaluate reverse pvs and view cell volume on left and right cell
1302        // note: should I take all leaf objects or rather the objects hit by rays?
1303        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1304        {
1305                int pvsContri = 0;
1306
1307                Intersectable *obj = *oit;
1308                const AxisAlignedBox3 box = obj->GetBox();
1309
1310                // test if box falls in left / right child node
1311                if (box.Max(candidatePlane.mAxis) >= candidatePlane.mPosition)
1312                {
1313                        ++ pvsFront;
1314                        obj->Mail();           
1315                }
1316
1317                if (box.Min(candidatePlane.mAxis) < candidatePlane.mPosition)
1318                {
1319                        ++ pvsBack;
1320
1321                        if (obj->Mailed())
1322                                obj->Mail(2);
1323                        else
1324                                obj->Mail(1);
1325                }
1326        }
1327
1328        ViewCellContainer touchedViewCells;
1329
1330        // sum up volume seen from the objects of left and right children
1331        // => the volume is the weight for the render cost equation
1332        ViewCell::NewMail(3);
1333
1334        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1335        //map<Intersectable *, ViewCellContainer> objectsMap;
1336
1337        for (rit = tData.mRays->begin(); rit < rit_end; ++ rit)
1338        {
1339                VssRay *ray = (*rit).mRay;
1340
1341                // add volume to volumes of left and / or right children
1342                // if one of the ray end points is inside
1343                const int classification = ClassifyRay(ray, leaf, candidatePlane);
1344
1345                ViewCellContainer viewCells;
1346                mVspTree->GetViewCells(*ray, viewCells);
1347                       
1348                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1349
1350                // traverse through view cells and classify them according
1351                // to them being seen from to back / front / front and back node
1352                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1353                {
1354                        ViewCell *vc = *vit;
1355
1356                        // if not previously mailed
1357                        if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
1358                        {
1359                                touchedViewCells.push_back(vc);
1360                        }
1361
1362                        // classify / mail the view cell
1363                        MailViewCell(vc, classification);
1364                }
1365        }
1366
1367        // evaluate view cells volume contribution
1368        // with respect to the mail box classification
1369        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1370
1371        for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1372        {
1373                AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
1374        }
1375
1376        //////////////////////////////////////////////
1377        //
1378        // evaluate contribution of objects which are part of other kd nodes
1379        // which are seen by the same view cell
1380        // These contributions cannot be reduced by splitting, because
1381        // the object would still be part of the pvs
1382
1383        float newRc = 0;
1384        float rc = 0;
1385
1386        MailablePvsData::NewMail();
1387        //ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1388
1389        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1390        {
1391                Intersectable *obj = *oit;
1392                ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
1393
1394                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
1395                {
1396                        ViewCell *vc = *vit;
1397                        // no more view cell pvs!!
1398                        /*MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
1399                        if (!vdata)
1400                        {
1401                                Debug << "error! should not come here" << endl;
1402                                continue;
1403                        }
1404
1405                        if (!vdata->Mailed())
1406                        {
1407                                vdata->Mail();
1408                                rc += vc->GetVolume();
1409
1410                                if ((vdata->mSumPdf > 1.5) ||
1411                                        vc->Mailed(2) ||
1412                                        obj->Mailed(2) ||
1413                                        (obj->Mailed() && vc->Mailed()) ||
1414                                        (obj->Mailed(1) && vc->Mailed(1))
1415                                        )
1416                                {
1417                                        newRc += vc->GetVolume();
1418                                }
1419                        }*/
1420                }
1421        }
1422
1423
1424        /////////////////////////////
1425        //-- pvs rendering heuristics
1426
1427        const float oldRenderCost = rc;
1428       
1429        // sum up the terms:
1430        // the view cells seeing
1431        // a) the left node are weighted by the #left node objects
1432        // b) the right node are weighted by the #right node objects
1433        // c) both nodes are weighted by the #parent node objects
1434        const float newRenderCost = newRc;
1435
1436
1437        // normalize volume with view space volume
1438        const float renderCostDecrease = (oldRenderCost - newRenderCost) / viewSpaceVol;
1439
1440        Debug << "\nrender cost decrease: " << endl
1441                  << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
1442                  << "render cost decrease: " << renderCostDecrease << endl;
1443
1444        normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
1445
1446               
1447        return renderCostDecrease;
1448}
1449
1450
1451void OspTree::ComputeBoundingBox(const ObjectContainer &objects)
1452{
1453        mBoundingBox.Initialize();
1454
1455        ObjectContainer::const_iterator oit, oit_end = objects.end();
1456
1457        //-- compute bounding box
1458        for (oit = objects.begin(); oit != oit_end; ++ oit)
1459        {
1460                Intersectable *obj = *oit;
1461
1462                // compute bounding box of view space
1463                mBoundingBox.Include(obj->GetBox());
1464        }
1465}
1466
1467
1468void OspTree::ProcessMultipleRefs(KdLeaf *leaf) const
1469{
1470        // find objects from multiple kd-leaves
1471        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1472
1473        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1474        {
1475                Intersectable *object = *oit;
1476               
1477                // matt: no more ref
1478                /*if (object->mReferences > 1)
1479                {
1480                        leaf->mMultipleObjects.push_back(object);
1481                }*/
1482        }
1483}
1484
1485
1486void OspTree::CollectLeaves(vector<KdLeaf *> &leaves) const
1487{
1488        stack<KdNode *> nodeStack;
1489        nodeStack.push(mRoot);
1490
1491        while (!nodeStack.empty())
1492        {
1493                KdNode *node = nodeStack.top();
1494                nodeStack.pop();
1495                if (node->IsLeaf())
1496                {
1497                        KdLeaf *leaf = (KdLeaf *)node;
1498                        leaves.push_back(leaf);
1499                }
1500                else
1501                {
1502                        KdInterior *interior = (KdInterior *)node;
1503                        nodeStack.push(interior->mBack);
1504                        nodeStack.push(interior->mFront);
1505                }
1506        }
1507}
1508
1509
1510AxisAlignedBox3 OspTree::GetBoundingBox(KdNode *node) const
1511{
1512        if (!node->mParent)
1513                return mBoundingBox;
1514
1515        if (!node->IsLeaf())
1516        {
1517                return (static_cast<KdInterior *>(node))->mBox;         
1518        }
1519
1520        KdInterior *parent = static_cast<KdInterior *>(node->mParent);
1521
1522        AxisAlignedBox3 box(parent->mBox);
1523
1524        if (parent->mFront == node)
1525                box.SetMin(parent->mAxis, parent->mPosition);
1526    else
1527                box.SetMax(parent->mAxis, parent->mPosition);
1528
1529        return box;
1530}
1531
1532
1533void OspTree::CollectViewCells(KdLeaf *leaf, ViewCellContainer &viewCells)
1534{
1535        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
1536
1537        ViewCell::NewMail();
1538
1539        // loop through all object and collect view cell pvs of this node
1540        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
1541        {
1542                Intersectable *obj = *oit;
1543                // no more view cell pvs!!
1544                /*ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
1545
1546                for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
1547                {
1548            ViewCell *vc = (*vit).first;
1549
1550                        if (!vc->Mailed())
1551                        {
1552                                vc->Mail();
1553                                viewCells.push_back(vc);
1554                        }
1555                }*/
1556        }
1557}
1558
1559
1560void OspTree::CollectDirtyCandidates(OspSubdivisionCandidate *sc,
1561                                                                         vector<SubdivisionCandidate *> &dirtyList,
1562                                                                         const bool onlyUnmailed)
1563{
1564        OspTraversalData &tData = sc->mParentData;
1565        KdLeaf *node = tData.mNode;
1566       
1567        ViewCell::NewMail();
1568        ViewCellContainer viewCells;
1569        ViewCellContainer tmpViewCells;
1570
1571        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1572
1573        // find all view cells associated with the rays, add them to view cells
1574        for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1575        {
1576                VssRay *ray = (*rit).mRay;
1577                mVspTree->GetViewCells(*ray, tmpViewCells);
1578
1579                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1580
1581                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1582                {
1583                        VspViewCell *vc = static_cast<VspViewCell *>(*vit);
1584
1585                        if (!vc->Mailed())
1586                        {
1587                                vc->Mail();
1588                                viewCells.push_back(vc);
1589                        }
1590                }
1591        }
1592
1593        // candidates that contain this view cells are thrown into dirty list
1594        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1595
1596        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1597        {
1598                VspViewCell *vc = static_cast<VspViewCell *>(*vit);
1599
1600                VspLeaf *leaf = vc->mLeaves[0];
1601
1602                SubdivisionCandidate *dsc = leaf->GetSubdivisionCandidate();
1603                if (dsc && (!onlyUnmailed || !dsc->Mailed()))
1604                {
1605                        dsc->Mail();
1606                        dirtyList.push_back(dsc);
1607                }
1608        }
1609}
1610
1611
1612KdNode *OspTree::GetRoot() const
1613{
1614        return mRoot;
1615}
1616
1617
1618KdLeaf *OspTree::GetLeaf(const Vector3 &pt, KdNode *node) const
1619{
1620        // start from root of tree
1621        if (node == NULL)
1622        {
1623                node = mRoot;
1624        }
1625
1626        stack<KdNode *> nodeStack;
1627        nodeStack.push(node);
1628 
1629        KdLeaf *leaf = NULL;
1630 
1631        while (!nodeStack.empty()) 
1632        {
1633                KdNode *node = nodeStack.top();
1634                nodeStack.pop();
1635       
1636                if (node->IsLeaf())
1637                {
1638                        leaf = static_cast<KdLeaf *>(node);
1639                }
1640                else   
1641                {       
1642                        // find point
1643                        KdInterior *interior = static_cast<KdInterior *>(node);
1644       
1645                        if (interior->mPosition > pt[interior->mAxis])
1646                        {
1647                                nodeStack.push(interior->mBack);
1648                        }
1649                        else
1650                        {
1651                                nodeStack.push(interior->mFront);
1652                        }
1653                }
1654        }
1655 
1656        return leaf;
1657}
1658
1659
1660void OspTree::PreprocessRays(KdLeaf *root,
1661                                                         const VssRayContainer &sampleRays,
1662                                                         RayInfoContainer &rays)
1663{
1664        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
1665        RayInfoContainer clippedRays;
1666
1667        long startTime = GetTime();
1668
1669        cout << "storing rays ... ";
1670
1671        Intersectable::NewMail();
1672
1673        //-- store rays and objects
1674        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
1675        {
1676                VssRay *ray = *rit;
1677
1678                float minT, maxT;
1679                static Ray hray;
1680
1681                hray.Init(*ray);
1682               
1683                // TODO: not very efficient to implictly cast between rays types
1684                if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
1685                {
1686                        float len = ray->Length();
1687                        if (!len)
1688                                len = Limits::Small;
1689
1690                        clippedRays.push_back(RayInfo(ray, minT / len, maxT / len));
1691
1692                        // HACK: reset nodes for the case we have used object kd tree for
1693                        // tree building.
1694                        ray->mOriginNode = NULL;
1695                        ray->mTerminationNode = NULL;
1696                }
1697        }
1698
1699        FilterRays(root, clippedRays, rays);
1700
1701        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1702}
1703
1704
1705
1706int OspTree::SplitRays(const AxisAlignedPlane &plane,
1707                                           RayInfoContainer &rays,
1708                                           RayInfoContainer &frontRays,
1709                                           RayInfoContainer &backRays) const
1710{
1711        int splits = 0;
1712
1713        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1714
1715        for (rit = rays.begin(); rit != rit_end; ++ rit)
1716        {
1717                RayInfo bRay = *rit;
1718               
1719                VssRay *ray = bRay.mRay;
1720                float t;
1721
1722                // get classification and receive new t
1723                //-- test if start point behind or in front of plane
1724                const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
1725                       
1726                if (side == 0)
1727                {
1728                        ++ splits;
1729
1730                        if (ray->HasPosDir(plane.mAxis))
1731                        {
1732                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1733                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1734                        }
1735                        else
1736                        {
1737                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1738                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1739                        }
1740                }
1741                else if (side == 1)
1742                {
1743                        frontRays.push_back(bRay);
1744                }
1745                else
1746                {
1747                        backRays.push_back(bRay);
1748                }
1749        }
1750
1751        return splits;
1752}
1753
1754
1755int OspTree::FilterRays(KdLeaf *leaf,
1756                                                const RayInfoContainer &rays,
1757                                                RayInfoContainer &filteredRays)
1758{
1759        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1760
1761        for (rit = rays.begin(); rit != rit_end; ++ rit)
1762        {
1763                VssRay *ray = (*rit).mRay;
1764
1765                // test if intersection point with one of the objects is inside this node
1766                const bool originInside = EndPointInsideNode(leaf, *ray, false);
1767        const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
1768
1769                if (originInside || terminationInside)
1770                {
1771                        filteredRays.push_back(ray);
1772                }
1773        }
1774
1775        return 0;
1776}
1777                                         
1778
1779int OspTree::CheckViewCellsPvs(KdLeaf *leaf,
1780                                                           const RayInfoContainer &rays) const
1781{
1782        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1783
1784        Intersectable::NewMail();
1785        ObjectContainer touchedObjects;
1786       
1787
1788        for (rit = rays.begin(); rit < rit_end; ++ rit)
1789        {
1790                VssRay *ray = (*rit).mRay;
1791
1792                if (ray->mTerminationObject)
1793                {
1794                        Intersectable *obj = ray->mTerminationObject;
1795
1796                        if (!obj->Mailed())
1797                        {
1798                                obj->Mail();
1799                                touchedObjects.push_back(obj);
1800                        }
1801                }
1802
1803                if (ray->mOriginObject)
1804                {
1805                        Intersectable *obj = ray->mOriginObject;
1806
1807                        if (!obj->Mailed())
1808                        {
1809                                obj->Mail();
1810                                touchedObjects.push_back(obj);
1811                        }
1812                }
1813        }
1814        Debug << "touched view cells: " << (int)touchedObjects.size() << endl;
1815        ObjectContainer::const_iterator it, it_end = touchedObjects.end();
1816        for (it = touchedObjects.begin(); it != it_end; ++ it)
1817        {
1818                // no more view cell pvs!!
1819                /*Debug << "\nobj: " << (*it) << " vc pvs size: " << (*it)->mViewCellPvs.GetSize() << endl << endl;
1820                ViewCellPvsMap::const_iterator mit, mit_end = (*it)->mViewCellPvs.mEntries.end();
1821
1822                for (mit = (*it)->mViewCellPvs.mEntries.begin(); mit != mit_end; ++ mit)
1823                {
1824                        Debug << "new sumpdf: " << (*mit).second.mSumPdf << endl;
1825                }*/
1826        }
1827
1828        return 0;
1829}
1830
1831
1832KdIntersectable *OspTree::GetOrCreateKdIntersectable(KdNode *node)
1833{
1834        //if (!node) return NULL;
1835
1836        // search nodes
1837        std::map<KdNode *, KdIntersectable *>::const_iterator it = mKdIntersectables.find(node);
1838
1839        if (it != mKdIntersectables.end())
1840        {
1841                return (*it).second;
1842        }
1843
1844        // not in map => create new entry
1845        KdIntersectable *kdObj = new KdIntersectable(node, GetBoundingBox(node));
1846        mKdIntersectables[node] = kdObj;
1847
1848        return kdObj;
1849}
1850
1851
1852/*
1853void OspTree::AddViewCellVolume(ViewCell *vc,
1854                                                                const int cf,
1855                                                                float &frontVol,
1856                                                                float &backVol,
1857                                                                float &totalVol) const
1858{
1859        //const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1860        const float vol = vc->GetVolume();
1861
1862        // view cell not found yet => new
1863        if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
1864        {
1865                totalVol += vol;
1866        }
1867
1868        if (cf >= 0) // front volume
1869        {
1870                if (!vc->Mailed() && !vc->Mailed(2))
1871                {
1872                        frontVol += vol;
1873               
1874                        // already in back volume => in both volumes
1875                        if (vc->Mailed(1))
1876                                vc->Mail(2);
1877                        else
1878                                vc->Mail();
1879                }
1880        }
1881
1882        if (cf <= 0) // back volume
1883        {
1884                if (!vc->Mailed(1) && !vc->Mailed(2))
1885                {
1886                        backVol += vol;
1887               
1888                        // already in front volume => in both volume
1889                        if (vc->Mailed())
1890                                vc->Mail(2);
1891                        else
1892                                vc->Mail(1);
1893                }
1894        }
1895}
1896*/
1897
1898
1899void OspTree::MailViewCell(ViewCell *vc, const int cf) const
1900{
1901        if (vc->Mailed(2)) // already classified
1902                return;
1903
1904        if (cf >= 0) // front volume
1905        {
1906                // already in back volume => in both volumes
1907                if (vc->Mailed(1))
1908                {
1909                        vc->Mail(2);
1910                }
1911                else
1912                {
1913                        vc->Mail();
1914                }
1915        }
1916
1917        if (cf <= 0) // back volume
1918        {
1919                // already in front volume => in both volume
1920                if (vc->Mailed())
1921                {
1922                        vc->Mail(2);
1923                }
1924                else
1925                {
1926                        vc->Mail(1);
1927                }
1928        }
1929}
1930
1931
1932void OspTree::AddViewCellVolumeContri(ViewCell *vc,
1933                                                                          float &frontVol,
1934                                                                          float &backVol,
1935                                                                          float &frontAndBackVol) const
1936{
1937        if (vc->Mailed())
1938        {
1939                frontVol += vc->GetVolume();
1940        }
1941        else if (vc->Mailed(1))
1942        {
1943                backVol += vc->GetVolume();
1944        }
1945        else if (vc->Mailed(2))
1946        {
1947                frontAndBackVol += vc->GetVolume();
1948        }
1949}
1950
1951
1952float OspTree::EvalViewCellsVolume(KdLeaf *leaf,
1953                                                                   const RayInfoContainer &rays) const
1954{
1955        float vol = 0;
1956        ViewCell::NewMail();
1957
1958        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1959
1960        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1961        {
1962                VssRay *ray = (*rit).mRay;
1963
1964                ViewCellContainer viewCells;
1965                mVspTree->GetViewCells(*ray, viewCells);
1966
1967                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1968                       
1969                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1970                {
1971                        ViewCell *vc = *vit;
1972
1973                        if (!vc->Mailed())
1974                        {
1975                                vc->Mail();
1976                                vol += vc->GetVolume();
1977                        }
1978                }               
1979        }
1980
1981        return vol;
1982}
1983
1984
1985bool OspTree::AddViewCellToObjectPvs(Intersectable *obj,
1986                                                                         ViewCell *vc,
1987                                                                         float &contribution,
1988                                                                         bool onlyUnmailed) const
1989{       
1990        contribution = 0; // todo
1991       
1992        // no more view cell pvs!!
1993        /*MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
1994        if (!vdata)
1995        {
1996                vdata = obj->mViewCellPvs.AddSample2(vc, 1);
1997        }
1998        else if (!onlyUnmailed || !vdata->Mailed())
1999        {
2000                obj->mViewCellPvs.AddSample(vc, 1);
2001        }
2002
2003        vdata->Mail();
2004        */
2005
2006        return true;
2007}
2008
2009
2010void OspTree::CollectTouchedViewCells(const RayInfoContainer &rays,
2011                                                                          ViewCellContainer &touchedViewCells) const
2012{
2013        ViewCell::NewMail();
2014       
2015        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2016
2017        for (rit = rays.begin(); rit != rit_end; ++ rit)
2018        {
2019                VssRay *ray = (*rit).mRay;
2020
2021                ViewCellContainer viewCells;
2022                mVspTree->GetViewCells(*ray, viewCells);
2023
2024                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2025
2026                // traverse through view cells and classify them according
2027                // to them being seen from to back / front / front and back node
2028                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2029                {
2030                        ViewCell *vc = *vit;
2031                        if (!vc->Mailed())
2032                        {
2033                                vc->Mail();
2034                                touchedViewCells.push_back(vc);
2035                        }
2036                }
2037        }
2038}
2039
2040
2041int OspTree::UpdateViewCellsPvs(KdLeaf *leaf,
2042                                                                const RayInfoContainer &rays) const
2043
2044{
2045        MailablePvsData::NewMail();
2046       
2047        ViewCellContainer touchedViewCells;
2048        CollectTouchedViewCells(rays, touchedViewCells);
2049
2050        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2051
2052        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
2053        {
2054                Intersectable *obj = *oit;
2055                ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2056
2057                // traverse through view cells and classify them according
2058                // to them being seen from to back / front / front and back node
2059                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2060                {
2061                        ViewCell *vc = *vit;
2062                        float contri;
2063                        AddViewCellToObjectPvs(obj, vc, contri, true);
2064                }
2065        }
2066
2067        return 0;
2068}
2069
2070
2071int OspTree::RemoveParentViewCellsPvs(KdLeaf *leaf,
2072                                                                          const RayInfoContainer &rays
2073                                                                          ) const
2074
2075{
2076        MailablePvsData::NewMail();
2077
2078        ViewCellContainer touchedViewCells;
2079        CollectTouchedViewCells(rays, touchedViewCells);
2080
2081        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2082
2083        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2084        {
2085                Intersectable *obj = *oit;
2086
2087                // traverse through view cells and classify them according
2088                // to them being seen from to back / front / front and back node
2089        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2090
2091                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2092                {
2093                        ViewCell *vc = *vit;
2094                       
2095                        /*MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
2096
2097                        if (vdata && !vdata->Mailed())
2098                        {
2099                                vdata->Mail();
2100                                obj->mViewCellPvs.RemoveSample(vc, 1);
2101                        }*/
2102                }
2103        }
2104
2105        return 0;
2106}
2107
2108
2109float OspTree::EvalRenderCost(const VssRayContainer &myrays)
2110{
2111        float rc = 0;
2112        float prop = mVspTree->GetBoundingBox().GetVolume();   
2113
2114        KdLeafContainer leaves;
2115        CollectLeaves(leaves);
2116
2117        ViewCellContainer vcleaves;
2118        mVspTree->CollectViewCells(vcleaves, false);
2119       
2120
2121        ViewCellContainer::const_iterator vit, vit_end = vcleaves.end();
2122
2123        for (vit = vcleaves.begin(); vit != vit_end; ++ vit)
2124        {
2125                ViewCell *vc = *vit;
2126                vc->GetPvs().Clear();
2127        }
2128
2129        KdLeafContainer::const_iterator kit, kit_end = leaves.end();
2130
2131        MailablePvsData::NewMail();
2132
2133        for (kit = leaves.begin(); kit != kit_end; ++ kit)
2134        {
2135                KdLeaf *leaf = *kit;
2136                float newCost = 0;
2137                float vol = 0;
2138
2139                ViewCell::NewMail();
2140                VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2141                ViewCellContainer touchedViewCells;
2142
2143                for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2144                {
2145                        VssRay *ray = *rit;
2146                       
2147                        // test if intersection point with one of the objects is inside this node
2148                        const bool originInside = EndPointInsideNode(leaf, *ray, false);
2149                        const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
2150
2151                        if (originInside || terminationInside)
2152                        {
2153                                ViewCellContainer viewCells;
2154                                mVspTree->GetViewCells(*ray, viewCells);
2155                       
2156                                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2157
2158                                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2159                                {
2160                                        ViewCell *vc = *vit;
2161
2162                                        // if not previously mailed
2163                                        if (!vc->Mailed())
2164                                        {
2165                                                vc->Mail();
2166                                                touchedViewCells.push_back(vc);
2167                                        }
2168
2169                        }
2170                        }
2171                }
2172               
2173                ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2174
2175                for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2176                {
2177                        Intersectable *obj = *oit;
2178                        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2179
2180                        for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2181                        {
2182                                ViewCell *vc = *vit;
2183                                /*PvsData *vdata = vc->GetPvs().Find(obj);
2184
2185                                if (!vdata)
2186                                {
2187                                        vc->GetPvs().AddSample(obj, 1);
2188                                        newCost += vc->GetVolume();
2189                                }
2190
2191                                MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
2192
2193                                if (!vdata || !vdata->Mailed())
2194                                {
2195                                        newCost += vc->GetVolume();
2196                                        if (!vdata)
2197                                                vdata = obj->mViewCellPvs.AddSample2(vc, 1);
2198                                        vdata->Mail();
2199                                }*/
2200                        }
2201                }
2202
2203                rc += newCost;
2204        }
2205
2206        return rc / prop;
2207}
2208
2209
2210float OspTree::EvalLeafCost(const OspTraversalData &tData)
2211{
2212        KdLeaf *leaf = tData.mNode;
2213
2214        float rc = 0;
2215        //float prop = mVspTree->GetBoundingBox().GetVolume(); 
2216        //float vol = 0;
2217        //ViewCell::NewMail();
2218       
2219        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2220        ViewCellContainer touchedViewCells;
2221
2222        for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2223        {
2224                VssRay *ray = (*rit).mRay;
2225                       
2226                // test if intersection point with one of the objects is inside this node
2227
2228                ViewCellContainer viewCells;
2229                mVspTree->GetViewCells(*ray, viewCells);
2230                       
2231                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2232
2233                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2234                {
2235                        ViewCell *vc = *vit;
2236
2237                        // if not previously mailed
2238                        if (!vc->Mailed())
2239                        {
2240                                vc->Mail();
2241                                touchedViewCells.push_back(vc);
2242                        }
2243                }
2244        }
2245
2246        // clear pvs of involved view cells
2247        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2248
2249        for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2250        {
2251                ViewCell *vc = *vit;
2252                vc->GetPvs().Clear();
2253        }
2254       
2255        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2256
2257        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2258        {
2259                Intersectable *obj = *oit;
2260
2261                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2262                {
2263                        ViewCell *vc = *vit;
2264                        /*PvsData *vdata = vc->GetPvs().Find(obj);
2265
2266                        if (!vdata)
2267                        {
2268                                vc->GetPvs().AddSample(obj, 1);
2269                                rc += vc->GetVolume();
2270                        }
2271                        */
2272                }
2273        }
2274       
2275        return rc;
2276}
2277
2278
2279bool OspTree::Export(OUT_STREAM &stream)
2280{
2281        ExportNode(mRoot, stream);
2282
2283        return true;
2284}
2285
2286
2287void OspTree::ExportNode(KdNode *node, OUT_STREAM &stream)
2288{
2289        if (node->IsLeaf())
2290        {
2291                KdLeaf *leaf = static_cast<KdLeaf *>(node);
2292
2293                stream << "<Leaf ";
2294                stream << "objects=\"";
2295               
2296                // export objects in kd leaves
2297                //if (mExportObjects) ExportObjects(leaf, stream);
2298               
2299                stream << "\" />" << endl;
2300        }
2301        else
2302        {       
2303                KdInterior *interior = static_cast<KdInterior *>(node);
2304       
2305                stream << "<Interior plane=\"" << interior->mPosition << " "
2306                           << interior->mAxis << "\">" << endl;
2307
2308                ExportNode(interior->mBack, stream);
2309                ExportNode(interior->mFront, stream);
2310
2311                stream << "</Interior>" << endl;
2312        }
2313}
2314
2315
2316struct KdObjectsTraversalData
2317{
2318        KdNode *node;
2319        ObjectContainer *objects;
2320};
2321
2322
2323void OspTree::InsertObjects(KdNode *node, const ObjectContainer &objects)
2324{
2325        stack<KdObjectsTraversalData> tStack;
2326
2327        while (!tStack.empty())
2328        {
2329                KdObjectsTraversalData tData = tStack.top();
2330        tStack.pop();
2331
2332                KdNode *node = tData.node;
2333               
2334                if (node->IsLeaf())
2335                {
2336                        KdLeaf *leaf = static_cast<KdLeaf *>(node);
2337
2338                        ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
2339
2340                        for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
2341                        {
2342                                leaf->mObjects.push_back(*oit);
2343                        }
2344                }
2345                else // interior
2346                {
2347                        KdObjectsTraversalData frontData, backData;
2348                        KdInterior *interior = static_cast<KdInterior *>(node);
2349
2350                        frontData.objects = new ObjectContainer();
2351                        backData.objects = new ObjectContainer();
2352
2353                        ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
2354                       
2355                    for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
2356                        {
2357                                Intersectable *object = *oit;
2358               
2359                                // determine the side of this ray with respect to the plane
2360                                const AxisAlignedBox3 box = object->GetBox();
2361
2362                                if (box.Max(interior->mAxis) >= interior->mPosition)
2363                                {
2364                                        frontData.objects->push_back(object);
2365                                }
2366
2367                                if (box.Min(interior->mAxis) < interior->mPosition)
2368                                {
2369                                        backData.objects->push_back(object);
2370                                }
2371                        }
2372
2373                        tStack.push(backData);
2374                        tStack.push(frontData);
2375                }
2376
2377                DEL_PTR(tData.objects);
2378        }
2379}
2380
2381
2382void OspTree::PrepareConstruction(SplitQueue &tQueue,
2383                                                                  const VssRayContainer &sampleRays,
2384                                                                  const ObjectContainer &objects,
2385                                                                  RayInfoContainer &rays)
2386{
2387        // store pointer to this tree
2388        OspSubdivisionCandidate::sOspTree = this;
2389        mOspStats.nodes = 1;
2390       
2391        // compute bounding box from objects
2392        ComputeBoundingBox(objects);
2393
2394        mTermMinProbability *= mBoundingBox.GetVolume();
2395        mGlobalCostMisses = 0;
2396
2397        //-- create new root
2398        KdLeaf *kdleaf = new KdLeaf(NULL, 0);
2399        kdleaf->mObjects = objects;
2400        mRoot = kdleaf;
2401       
2402        // get clipped rays
2403        PreprocessRays(kdleaf, sampleRays, rays);
2404
2405        // probabilty is voume of all "seen" view cells
2406#if 1
2407        const float prop = EvalViewCellsVolume(kdleaf, rays);
2408#else
2409        const float prop = GetBoundingBox().GetVolume();
2410#endif
2411
2412        //-- add first candidate for object space partition
2413
2414        // create osp traversal data
2415        OspTraversalData oData(kdleaf, 0, &rays, 0, prop, mBoundingBox);
2416
2417        //-- first split candidate
2418        OspSubdivisionCandidate *oSubdivisionCandidate =
2419                new OspSubdivisionCandidate(oData);
2420
2421        UpdateViewCellsPvs(kdleaf, rays);
2422
2423        EvalSubdivisionCandidate(*oSubdivisionCandidate);
2424
2425        mTotalCost = (float)objects.size() * prop /
2426                mVspTree->GetBoundingBox().GetVolume();
2427
2428        EvalSubdivisionStats(*oSubdivisionCandidate);
2429
2430        tQueue.Push(oSubdivisionCandidate);
2431}
2432
2433
2434bool OspTree::AddLeafToPvs(KdLeaf *leaf,
2435                                                   ViewCell *vc,
2436                                                   const float pdf,
2437                                                   float &contribution)
2438{
2439        // add kd intersecable to pvs
2440        KdIntersectable *kdObj = GetOrCreateKdIntersectable(leaf);
2441       
2442        return vc->AddPvsSample(kdObj, pdf, contribution);
2443}
2444
2445
2446}
Note: See TracBrowser for help on using the repository browser.