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

Revision 2100, 60.5 KB checked in by mattausch, 17 years ago (diff)

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