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

Revision 1576, 60.0 KB checked in by mattausch, 18 years ago (diff)

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