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

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