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

Revision 1528, 59.9 KB checked in by mattausch, 18 years ago (diff)

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