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

Revision 1694, 60.2 KB checked in by bittner, 18 years ago (diff)

obj exporter, vienna.obj + kdf added
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#if _DEBUG
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#endif
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                                                                         const bool onlyUnmailed)
1551{
1552        OspTraversalData &tData = sc->mParentData;
1553        KdLeaf *node = tData.mNode;
1554       
1555        ViewCell::NewMail();
1556        ViewCellContainer viewCells;
1557        ViewCellContainer tmpViewCells;
1558
1559        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
1560
1561        // find all view cells associated with the rays, add them to view cells
1562        for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
1563        {
1564                VssRay *ray = (*rit).mRay;
1565                mVspTree->GetViewCells(*ray, tmpViewCells);
1566
1567                ViewCellContainer::const_iterator vit, vit_end = tmpViewCells.end();
1568
1569                for (vit = tmpViewCells.begin(); vit != vit_end; ++ vit)
1570                {
1571                        VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1572
1573                        if (!vc->Mailed())
1574                        {
1575                                vc->Mail();
1576                                viewCells.push_back(vc);
1577                        }
1578                }
1579        }
1580
1581        // andidates holding this view cells are thrown into dirty list
1582        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1583
1584        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1585        {
1586                VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
1587
1588                VspLeaf *leaf = vc->mLeaves[0];
1589
1590                SubdivisionCandidate *dsc = leaf->GetSubdivisionCandidate();
1591                if (dsc && (!onlyUnmailed || !dsc->Mailed()))
1592                {
1593                        dsc->Mail();
1594                        dirtyList.push_back(dsc);
1595                }
1596        }
1597}
1598
1599
1600KdNode *OspTree::GetRoot() const
1601{
1602        return mRoot;
1603}
1604
1605
1606KdLeaf *OspTree::GetLeaf(const Vector3 &pt, KdNode *node) const
1607{
1608        // start from root of tree
1609        if (node == NULL)
1610        {
1611                node = mRoot;
1612        }
1613
1614        stack<KdNode *> nodeStack;
1615        nodeStack.push(node);
1616 
1617        KdLeaf *leaf = NULL;
1618 
1619        while (!nodeStack.empty()) 
1620        {
1621                KdNode *node = nodeStack.top();
1622                nodeStack.pop();
1623       
1624                if (node->IsLeaf())
1625                {
1626                        leaf = dynamic_cast<KdLeaf *>(node);
1627                }
1628                else   
1629                {       
1630                        // find point
1631                        KdInterior *interior = dynamic_cast<KdInterior *>(node);
1632       
1633                        if (interior->mPosition > pt[interior->mAxis])
1634                        {
1635                                nodeStack.push(interior->mBack);
1636                        }
1637                        else
1638                        {
1639                                nodeStack.push(interior->mFront);
1640                        }
1641                }
1642        }
1643 
1644        return leaf;
1645}
1646
1647
1648void OspTree::PreprocessRays(KdLeaf *root,
1649                                                         const VssRayContainer &sampleRays,
1650                                                         RayInfoContainer &rays)
1651{
1652        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
1653        RayInfoContainer clippedRays;
1654
1655        long startTime = GetTime();
1656
1657        cout << "storing rays ... ";
1658
1659        Intersectable::NewMail();
1660
1661        //-- store rays and objects
1662        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
1663        {
1664                VssRay *ray = *rit;
1665
1666                float minT, maxT;
1667                static Ray hray;
1668
1669                hray.Init(*ray);
1670               
1671                // TODO: not very efficient to implictly cast between rays types
1672                if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
1673                {
1674                        float len = ray->Length();
1675                        if (!len)
1676                                len = Limits::Small;
1677
1678                        clippedRays.push_back(RayInfo(ray, minT / len, maxT / len));
1679
1680                        // HACK: reset nodes for the case we have used object kd tree for
1681                        // tree building.
1682                        ray->mOriginNode = NULL;
1683                        ray->mTerminationNode = NULL;
1684                }
1685        }
1686
1687        FilterRays(root, clippedRays, rays);
1688
1689        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
1690}
1691
1692
1693
1694int OspTree::SplitRays(const AxisAlignedPlane &plane,
1695                                           RayInfoContainer &rays,
1696                                           RayInfoContainer &frontRays,
1697                                           RayInfoContainer &backRays) const
1698{
1699        int splits = 0;
1700
1701        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1702
1703        for (rit = rays.begin(); rit != rit_end; ++ rit)
1704        {
1705                RayInfo bRay = *rit;
1706               
1707                VssRay *ray = bRay.mRay;
1708                float t;
1709
1710                // get classification and receive new t
1711                //-- test if start point behind or in front of plane
1712                const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
1713                       
1714                if (side == 0)
1715                {
1716                        ++ splits;
1717
1718                        if (ray->HasPosDir(plane.mAxis))
1719                        {
1720                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1721                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1722                        }
1723                        else
1724                        {
1725                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1726                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1727                        }
1728                }
1729                else if (side == 1)
1730                {
1731                        frontRays.push_back(bRay);
1732                }
1733                else
1734                {
1735                        backRays.push_back(bRay);
1736                }
1737        }
1738
1739        return splits;
1740}
1741
1742
1743int OspTree::FilterRays(KdLeaf *leaf,
1744                                                const RayInfoContainer &rays,
1745                                                RayInfoContainer &filteredRays)
1746{
1747        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1748
1749        for (rit = rays.begin(); rit != rit_end; ++ rit)
1750        {
1751                VssRay *ray = (*rit).mRay;
1752
1753                // test if intersection point with one of the objects is inside this node
1754                const bool originInside = EndPointInsideNode(leaf, *ray, false);
1755        const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
1756
1757                if (originInside || terminationInside)
1758                {
1759                        filteredRays.push_back(ray);
1760                }
1761        }
1762
1763        return 0;
1764}
1765                                         
1766
1767int OspTree::CheckViewCellsPvs(KdLeaf *leaf,
1768                                                           const RayInfoContainer &rays) const
1769{
1770        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1771
1772        Intersectable::NewMail();
1773        ObjectContainer touchedObjects;
1774       
1775
1776        for (rit = rays.begin(); rit < rit_end; ++ rit)
1777        {
1778                VssRay *ray = (*rit).mRay;
1779
1780                if (ray->mTerminationObject)
1781                {
1782                        Intersectable *obj = ray->mTerminationObject;
1783
1784                        if (!obj->Mailed())
1785                        {
1786                                obj->Mail();
1787                                touchedObjects.push_back(obj);
1788                        }
1789                }
1790
1791                if (ray->mOriginObject)
1792                {
1793                        Intersectable *obj = ray->mOriginObject;
1794
1795                        if (!obj->Mailed())
1796                        {
1797                                obj->Mail();
1798                                touchedObjects.push_back(obj);
1799                        }
1800                }
1801        }
1802        Debug << "touched view cells: " << (int)touchedObjects.size() << endl;
1803        ObjectContainer::const_iterator it, it_end = touchedObjects.end();
1804        for (it = touchedObjects.begin(); it != it_end; ++ it)
1805        {
1806                Debug << "\nobj: " << (*it) << " vc pvs size: " << (*it)->mViewCellPvs.GetSize() << endl << endl;
1807                ViewCellPvsMap::const_iterator mit, mit_end = (*it)->mViewCellPvs.mEntries.end();
1808
1809                for (mit = (*it)->mViewCellPvs.mEntries.begin(); mit != mit_end; ++ mit)
1810                {
1811                        Debug << "new sumpdf: " << (*mit).second.mSumPdf << endl;
1812                }
1813        }
1814
1815        return 0;
1816}
1817
1818
1819KdIntersectable *OspTree::GetOrCreateKdIntersectable(KdNode *node)
1820{
1821        //if (!node) return NULL;
1822
1823        // search nodes
1824        std::map<KdNode *, KdIntersectable *>::const_iterator it = mKdIntersectables.find(node);
1825
1826        if (it != mKdIntersectables.end())
1827        {
1828                return (*it).second;
1829        }
1830
1831        // not in map => create new entry
1832        KdIntersectable *kdObj = new KdIntersectable(node, GetBoundingBox(node));
1833        mKdIntersectables[node] = kdObj;
1834
1835        return kdObj;
1836}
1837
1838
1839/*
1840void OspTree::AddViewCellVolume(ViewCell *vc,
1841                                                                const int cf,
1842                                                                float &frontVol,
1843                                                                float &backVol,
1844                                                                float &totalVol) const
1845{
1846        //const float renderCost = mViewCellsManager->SimpleRay &raynderCost(obj);
1847        const float vol = vc->GetVolume();
1848
1849        // view cell not found yet => new
1850        if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
1851        {
1852                totalVol += vol;
1853        }
1854
1855        if (cf >= 0) // front volume
1856        {
1857                if (!vc->Mailed() && !vc->Mailed(2))
1858                {
1859                        frontVol += vol;
1860               
1861                        // already in back volume => in both volumes
1862                        if (vc->Mailed(1))
1863                                vc->Mail(2);
1864                        else
1865                                vc->Mail();
1866                }
1867        }
1868
1869        if (cf <= 0) // back volume
1870        {
1871                if (!vc->Mailed(1) && !vc->Mailed(2))
1872                {
1873                        backVol += vol;
1874               
1875                        // already in front volume => in both volume
1876                        if (vc->Mailed())
1877                                vc->Mail(2);
1878                        else
1879                                vc->Mail(1);
1880                }
1881        }
1882}
1883*/
1884
1885
1886void OspTree::MailViewCell(ViewCell *vc, const int cf) const
1887{
1888        if (vc->Mailed(2)) // already classified
1889                return;
1890
1891        if (cf >= 0) // front volume
1892        {
1893                // already in back volume => in both volumes
1894                if (vc->Mailed(1))
1895                {
1896                        vc->Mail(2);
1897                }
1898                else
1899                {
1900                        vc->Mail();
1901                }
1902        }
1903
1904        if (cf <= 0) // back volume
1905        {
1906                // already in front volume => in both volume
1907                if (vc->Mailed())
1908                {
1909                        vc->Mail(2);
1910                }
1911                else
1912                {
1913                        vc->Mail(1);
1914                }
1915        }
1916}
1917
1918
1919void OspTree::AddViewCellVolumeContri(ViewCell *vc,
1920                                                                          float &frontVol,
1921                                                                          float &backVol,
1922                                                                          float &frontAndBackVol) const
1923{
1924        if (vc->Mailed())
1925        {
1926                frontVol += vc->GetVolume();
1927        }
1928        else if (vc->Mailed(1))
1929        {
1930                backVol += vc->GetVolume();
1931        }
1932        else if (vc->Mailed(2))
1933        {
1934                frontAndBackVol += vc->GetVolume();
1935        }
1936}
1937
1938
1939float OspTree::EvalViewCellsVolume(KdLeaf *leaf,
1940                                                                   const RayInfoContainer &rays) const
1941{
1942        float vol = 0;
1943        ViewCell::NewMail();
1944
1945        RayInfoContainer::const_iterator rit, rit_end = rays.end();
1946
1947        for (rit = rays.begin(); rit != rays.end(); ++ rit)
1948        {
1949                VssRay *ray = (*rit).mRay;
1950
1951                ViewCellContainer viewCells;
1952                mVspTree->GetViewCells(*ray, viewCells);
1953
1954                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
1955                       
1956                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
1957                {
1958                        ViewCell *vc = *vit;
1959
1960                        if (!vc->Mailed())
1961                        {
1962                                vc->Mail();
1963                                vol += vc->GetVolume();
1964                        }
1965                }               
1966        }
1967
1968        return vol;
1969}
1970
1971
1972bool OspTree::AddViewCellToObjectPvs(Intersectable *obj,
1973                                                                         ViewCell *vc,
1974                                                                         float &contribution,
1975                                                                         bool onlyUnmailed) const
1976{       
1977        contribution = 0; // todo
1978        MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
1979
1980        if (!vdata)
1981        {
1982                vdata = obj->mViewCellPvs.AddSample2(vc, 1);
1983        }
1984        else if (!onlyUnmailed || !vdata->Mailed())
1985        {
1986                obj->mViewCellPvs.AddSample(vc, 1);
1987        }
1988        vdata->Mail();
1989
1990        return true;
1991}
1992
1993
1994void OspTree::CollectTouchedViewCells(const RayInfoContainer &rays,
1995                                                                          ViewCellContainer &touchedViewCells) const
1996{
1997        ViewCell::NewMail();
1998       
1999        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2000
2001        for (rit = rays.begin(); rit != rit_end; ++ rit)
2002        {
2003                VssRay *ray = (*rit).mRay;
2004
2005                ViewCellContainer viewCells;
2006                mVspTree->GetViewCells(*ray, viewCells);
2007
2008                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2009
2010                // traverse through view cells and classify them according
2011                // to them being seen from to back / front / front and back node
2012                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2013                {
2014                        ViewCell *vc = *vit;
2015                        if (!vc->Mailed())
2016                        {
2017                                vc->Mail();
2018                                touchedViewCells.push_back(vc);
2019                        }
2020                }
2021        }
2022}
2023
2024
2025int OspTree::UpdateViewCellsPvs(KdLeaf *leaf,
2026                                                                const RayInfoContainer &rays) const
2027
2028{
2029        MailablePvsData::NewMail();
2030       
2031        ViewCellContainer touchedViewCells;
2032        CollectTouchedViewCells(rays, touchedViewCells);
2033
2034        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2035
2036        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
2037        {
2038                Intersectable *obj = *oit;
2039                ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2040
2041                // traverse through view cells and classify them according
2042                // to them being seen from to back / front / front and back node
2043                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2044                {
2045                        ViewCell *vc = *vit;
2046                        float contri;
2047                        AddViewCellToObjectPvs(obj, vc, contri, true);
2048                }
2049        }
2050
2051        return 0;
2052}
2053
2054
2055int OspTree::RemoveParentViewCellsPvs(KdLeaf *leaf,
2056                                                                          const RayInfoContainer &rays
2057                                                                          ) const
2058
2059{
2060        MailablePvsData::NewMail();
2061
2062        ViewCellContainer touchedViewCells;
2063        CollectTouchedViewCells(rays, touchedViewCells);
2064
2065        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2066
2067        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2068        {
2069                Intersectable *obj = *oit;
2070
2071                // traverse through view cells and classify them according
2072                // to them being seen from to back / front / front and back node
2073        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2074
2075                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2076                {
2077                        ViewCell *vc = *vit;
2078                       
2079                        MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
2080
2081                        if (vdata && !vdata->Mailed())
2082                        {
2083                                vdata->Mail();
2084                                obj->mViewCellPvs.RemoveSample(vc, 1);
2085                        }
2086                }
2087        }
2088
2089        return 0;
2090}
2091
2092
2093float OspTree::EvalRenderCost(const VssRayContainer &myrays)
2094{
2095        float rc = 0;
2096        float prop = mVspTree->GetBoundingBox().GetVolume();   
2097
2098        KdLeafContainer leaves;
2099        CollectLeaves(leaves);
2100
2101        ViewCellContainer vcleaves;
2102        mVspTree->CollectViewCells(vcleaves, false);
2103       
2104
2105        ViewCellContainer::const_iterator vit, vit_end = vcleaves.end();
2106
2107        for (vit = vcleaves.begin(); vit != vit_end; ++ vit)
2108        {
2109                ViewCell *vc = *vit;
2110                vc->GetPvs().Clear();
2111        }
2112
2113        KdLeafContainer::const_iterator kit, kit_end = leaves.end();
2114
2115        MailablePvsData::NewMail();
2116
2117        for (kit = leaves.begin(); kit != kit_end; ++ kit)
2118        {
2119                KdLeaf *leaf = *kit;
2120                float newCost = 0;
2121                float vol = 0;
2122
2123                ViewCell::NewMail();
2124                VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2125                ViewCellContainer touchedViewCells;
2126
2127                for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2128                {
2129                        VssRay *ray = *rit;
2130                       
2131                        // test if intersection point with one of the objects is inside this node
2132                        const bool originInside = EndPointInsideNode(leaf, *ray, false);
2133                        const bool terminationInside = EndPointInsideNode(leaf, *ray, true);
2134
2135                        if (originInside || terminationInside)
2136                        {
2137                                ViewCellContainer viewCells;
2138                                mVspTree->GetViewCells(*ray, viewCells);
2139                       
2140                                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2141
2142                                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2143                                {
2144                                        ViewCell *vc = *vit;
2145
2146                                        // if not previously mailed
2147                                        if (!vc->Mailed())
2148                                        {
2149                                                vc->Mail();
2150                                                touchedViewCells.push_back(vc);
2151                                        }
2152
2153                        }
2154                        }
2155                }
2156               
2157                ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2158
2159                for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2160                {
2161                        Intersectable *obj = *oit;
2162                        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2163
2164                        for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2165                        {
2166                                ViewCell *vc = *vit;
2167                                PvsData *vdata = vc->GetPvs().Find(obj);
2168
2169                                if (!vdata)
2170                                {
2171                                        vc->GetPvs().AddSample(obj, 1);
2172                                        newCost += vc->GetVolume();
2173                                }
2174
2175/*                              MailablePvsData *vdata = obj->mViewCellPvs.Find(vc);
2176
2177                                if (!vdata || !vdata->Mailed())
2178                                {
2179                                        newCost += vc->GetVolume();
2180                                        if (!vdata)
2181                                                vdata = obj->mViewCellPvs.AddSample2(vc, 1);
2182                                        vdata->Mail();
2183                                }*/
2184                        }
2185                }
2186
2187                rc += newCost;
2188        }
2189
2190        return rc / prop;
2191}
2192
2193
2194float OspTree::EvalLeafCost(const OspTraversalData &tData)
2195{
2196        KdLeaf *leaf = tData.mNode;
2197
2198        float rc = 0;
2199        //float prop = mVspTree->GetBoundingBox().GetVolume(); 
2200        //float vol = 0;
2201        //ViewCell::NewMail();
2202       
2203        RayInfoContainer::const_iterator rit, rit_end = tData.mRays->end();
2204        ViewCellContainer touchedViewCells;
2205
2206        for (rit = tData.mRays->begin(); rit != rit_end; ++ rit)
2207        {
2208                VssRay *ray = (*rit).mRay;
2209                       
2210                // test if intersection point with one of the objects is inside this node
2211
2212                ViewCellContainer viewCells;
2213                mVspTree->GetViewCells(*ray, viewCells);
2214                       
2215                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2216
2217                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2218                {
2219                        ViewCell *vc = *vit;
2220
2221                        // if not previously mailed
2222                        if (!vc->Mailed())
2223                        {
2224                                vc->Mail();
2225                                touchedViewCells.push_back(vc);
2226                        }
2227                }
2228        }
2229
2230        // clear pvs of involved view cells
2231        ViewCellContainer::const_iterator vit, vit_end = touchedViewCells.end();
2232
2233        for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2234        {
2235                ViewCell *vc = *vit;
2236                vc->GetPvs().Clear();
2237        }
2238       
2239        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
2240
2241        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
2242        {
2243                Intersectable *obj = *oit;
2244
2245                for (vit = touchedViewCells.begin(); vit != vit_end; ++ vit)
2246                {
2247                        ViewCell *vc = *vit;
2248                        PvsData *vdata = vc->GetPvs().Find(obj);
2249
2250                        if (!vdata)
2251                        {
2252                                vc->GetPvs().AddSample(obj, 1);
2253                                rc += vc->GetVolume();
2254                                //prop += vc->GetVolume();
2255                        }
2256                }
2257        }
2258       
2259        return rc;
2260}
2261
2262
2263bool OspTree::Export(OUT_STREAM &stream)
2264{
2265        ExportNode(mRoot, stream);
2266
2267        return true;
2268}
2269
2270
2271void OspTree::ExportNode(KdNode *node, OUT_STREAM &stream)
2272{
2273        if (node->IsLeaf())
2274        {
2275                KdLeaf *leaf = dynamic_cast<KdLeaf *>(node);
2276
2277                stream << "<Leaf ";
2278                stream << "objects=\"";
2279               
2280                // export objects in kd leaves
2281                //if (mExportObjects) ExportObjects(leaf, stream);
2282               
2283                stream << "\" />" << endl;
2284        }
2285        else
2286        {       
2287                KdInterior *interior = dynamic_cast<KdInterior *>(node);
2288       
2289                stream << "<Interior plane=\"" << interior->mPosition << " "
2290                           << interior->mAxis << "\">" << endl;
2291
2292                ExportNode(interior->mBack, stream);
2293                ExportNode(interior->mFront, stream);
2294
2295                stream << "</Interior>" << endl;
2296        }
2297}
2298
2299
2300struct KdObjectsTraversalData
2301{
2302        KdNode *node;
2303        ObjectContainer *objects;
2304};
2305
2306
2307void OspTree::InsertObjects(KdNode *node, const ObjectContainer &objects)
2308{
2309        stack<KdObjectsTraversalData> tStack;
2310
2311        while (!tStack.empty())
2312        {
2313                KdObjectsTraversalData tData = tStack.top();
2314        tStack.pop();
2315
2316                KdNode *node = tData.node;
2317               
2318                if (node->IsLeaf())
2319                {
2320                        KdLeaf *leaf = dynamic_cast<KdLeaf *>(node);
2321
2322                        ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
2323
2324                        for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
2325                        {
2326                                leaf->mObjects.push_back(*oit);
2327                        }
2328                }
2329                else // interior
2330                {
2331                        KdObjectsTraversalData frontData, backData;
2332                        KdInterior *interior = dynamic_cast<KdInterior *>(node);
2333
2334                        frontData.objects = new ObjectContainer();
2335                        backData.objects = new ObjectContainer();
2336
2337                        ObjectContainer::const_iterator oit, oit_end = tData.objects->end();
2338                       
2339                    for (oit = tData.objects->begin(); oit != oit_end; ++ oit)
2340                        {
2341                                Intersectable *object = *oit;
2342               
2343                                // determine the side of this ray with respect to the plane
2344                                const AxisAlignedBox3 box = object->GetBox();
2345
2346                                if (box.Max(interior->mAxis) >= interior->mPosition)
2347                                {
2348                                        frontData.objects->push_back(object);
2349                                }
2350
2351                                if (box.Min(interior->mAxis) < interior->mPosition)
2352                                {
2353                                        backData.objects->push_back(object);
2354                                }
2355                        }
2356
2357                        tStack.push(backData);
2358                        tStack.push(frontData);
2359                }
2360
2361                DEL_PTR(tData.objects);
2362        }
2363}
2364
2365
2366SubdivisionCandidate * OspTree::PrepareConstruction(const VssRayContainer &sampleRays,
2367                                                                                                        const ObjectContainer &objects,
2368                                                                                                        RayInfoContainer &rays)
2369{
2370        // store pointer to this tree
2371        OspSubdivisionCandidate::sOspTree = this;
2372        mOspStats.nodes = 1;
2373       
2374        // compute bounding box from objects
2375        ComputeBoundingBox(objects);
2376
2377        mTermMinProbability *= mBoundingBox.GetVolume();
2378        mGlobalCostMisses = 0;
2379
2380        //-- create new root
2381        KdLeaf *kdleaf = new KdLeaf(NULL, 0);
2382        kdleaf->mObjects = objects;
2383        mRoot = kdleaf;
2384       
2385        // get clipped rays
2386        PreprocessRays(kdleaf, sampleRays, rays);
2387
2388        // probabilty is voume of all "seen" view cells
2389#if 1
2390        const float prop = EvalViewCellsVolume(kdleaf, rays);
2391#else
2392        const float prop = GetBoundingBox().GetVolume();
2393#endif
2394
2395        //-- add first candidate for object space partition
2396
2397        // create osp traversal data
2398        OspTraversalData oData(kdleaf, 0, &rays, 0, prop, mBoundingBox);
2399
2400        //-- first split candidate
2401        OspSubdivisionCandidate *oSubdivisionCandidate =
2402                new OspSubdivisionCandidate(oData);
2403
2404        UpdateViewCellsPvs(kdleaf, rays);
2405
2406        EvalSubdivisionCandidate(*oSubdivisionCandidate);
2407
2408        mTotalCost = (float)objects.size() * prop /
2409                mVspTree->GetBoundingBox().GetVolume();
2410
2411        EvalSubdivisionStats(*oSubdivisionCandidate);
2412
2413        return oSubdivisionCandidate;
2414}
2415
2416
2417bool OspTree::AddLeafToPvs(KdLeaf *leaf,
2418                                                   ViewCell *vc,
2419                                                   const float pdf,
2420                                                   float &contribution)
2421{
2422        // add kd intersecable to pvs
2423        KdIntersectable *kdObj = GetOrCreateKdIntersectable(leaf);
2424       
2425        return vc->AddPvsSample(kdObj, pdf, contribution);
2426}
2427
2428
2429}
Note: See TracBrowser for help on using the repository browser.