source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 601

Revision 601, 72.2 KB checked in by mattausch, 18 years ago (diff)
Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
5#include "Plane3.h"
6#include "VspBspTree.h"
7#include "Mesh.h"
8#include "common.h"
9#include "ViewCell.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 "ViewCellBsp.h"
17#include "ViewCellsManager.h"
18#include "Beam.h"
19
20
21//-- static members
22
23/** Evaluates split plane classification with respect to the plane's
24        contribution for a minimum number of ray splits.
25*/
26const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
27/** Evaluates split plane classification with respect to the plane's
28        contribution for  balanced rays.
29*/
30const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
31
32
33int VspBspTree::sFrontId = 0;
34int VspBspTree::sBackId = 0;
35int VspBspTree::sFrontAndBackId = 0;
36
37
38
39
40// pvs penalty can be different from pvs size
41inline float EvalPvsPenalty(const int pvs,
42                                                        const int lower,
43                                                        const int upper)
44{
45        // clamp to minmax values
46        if (pvs < lower)
47                return (float)lower;
48        if (pvs > upper)
49                return (float)upper;
50
51        return (float)pvs;
52}
53
54
55
56
57/******************************************************************************/
58/*                       class VspBspTree implementation                      */
59/******************************************************************************/
60
61
62VspBspTree::VspBspTree():
63mRoot(NULL),
64mUseAreaForPvs(false),
65mCostNormalizer(Limits::Small),
66mViewCellsManager(NULL),
67mOutOfBoundsCell(NULL),
68mStoreRays(false),
69mRenderCostWeight(0.5)
70{
71        bool randomize = false;
72        environment->GetBoolValue("VspBspTree.Construction.randomize", randomize);
73        if (randomize)
74                Randomize(); // initialise random generator for heuristics
75
76        //-- termination criteria for autopartition
77        environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
78        environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
79        environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
80        environment->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
81        environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
82        environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
83        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
84        environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
85        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
86        //-- max cost ratio for early tree termination
87        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
88mTermMinPolygons = 25;
89        //-- factors for bsp tree split plane heuristics
90        environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
91        environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
92        environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
93
94
95        //-- partition criteria
96        environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
97        environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
98        environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
99
100        environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
101        environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
102
103        // if only the driving axis is used for axis aligned split
104        environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
105       
106        //-- termination criteria for axis aligned split
107        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
108                mTermMaxRayContriForAxisAligned);
109        environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
110                mTermMinRaysForAxisAligned);
111
112        //environment->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
113        environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
114
115        environment->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
116
117
118        mSubdivisionStats.open("subdivisionStats.log");
119
120
121        //-- debug output
122
123        Debug << "******* VSP BSP options ******** " << endl;
124    Debug << "max depth: " << mTermMaxDepth << endl;
125        Debug << "min PVS: " << mTermMinPvs << endl;
126        Debug << "min probabiliy: " << mTermMinProbability << endl;
127        Debug << "min rays: " << mTermMinRays << endl;
128        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
129        //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
130        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
131        Debug << "miss tolerance: " << mTermMissTolerance << endl;
132        Debug << "max view cells: " << mMaxViewCells << endl;
133        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
134        Debug << "max plane candidates: " << mMaxRayCandidates << endl;
135        Debug << "randomize: " << randomize << endl;
136
137        Debug << "using area for pvs: " << mUseAreaForPvs << endl;
138        Debug << "render cost weight: " << mRenderCostWeight << endl;
139        Debug << "Split plane strategy: ";
140
141        if (mSplitPlaneStrategy & RANDOM_POLYGON)
142        {
143                Debug << "random polygon ";
144        }
145        if (mSplitPlaneStrategy & AXIS_ALIGNED)
146        {
147                Debug << "axis aligned ";
148        }
149        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
150        {
151                mCostNormalizer += mLeastRaySplitsFactor;
152                Debug << "least ray splits ";
153        }
154        if (mSplitPlaneStrategy & BALANCED_RAYS)
155        {
156                mCostNormalizer += mBalancedRaysFactor;
157                Debug << "balanced rays ";
158        }
159        if (mSplitPlaneStrategy & PVS)
160        {
161                mCostNormalizer += mPvsFactor;
162                Debug << "pvs";
163        }
164
165
166        mSplitCandidates = new vector<SortableEntry>;
167
168        Debug << endl;
169}
170
171
172BspViewCell *VspBspTree::GetOutOfBoundsCell()
173{
174        return mOutOfBoundsCell;
175}
176
177
178BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
179{
180        if (!mOutOfBoundsCell)
181        {
182                mOutOfBoundsCell = new BspViewCell();
183                mOutOfBoundsCell->SetId(-1);
184                mOutOfBoundsCell->SetValid(false);
185        }
186
187        return mOutOfBoundsCell;
188}
189
190
191const BspTreeStatistics &VspBspTree::GetStatistics() const
192{
193        return mBspStats;
194}
195
196
197VspBspTree::~VspBspTree()
198{
199        DEL_PTR(mRoot);
200        DEL_PTR(mSplitCandidates);
201}
202
203
204int VspBspTree::AddMeshToPolygons(Mesh *mesh,
205                                                                  PolygonContainer &polys,
206                                                                  MeshInstance *parent)
207{
208        FaceContainer::const_iterator fi;
209
210        // copy the face data to polygons
211        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
212        {
213                Polygon3 *poly = new Polygon3((*fi), mesh);
214
215                if (poly->Valid(mEpsilon))
216                {
217                        poly->mParent = parent; // set parent intersectable
218                        polys.push_back(poly);
219                }
220                else
221                        DEL_PTR(poly);
222        }
223        return (int)mesh->mFaces.size();
224}
225
226
227int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
228                                                          PolygonContainer &polys,
229                                                          int maxObjects)
230{
231        int limit = (maxObjects > 0) ?
232                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
233
234        int polysSize = 0;
235
236        for (int i = 0; i < limit; ++ i)
237        {
238                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
239                {
240                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
241                        polysSize +=
242                                AddMeshToPolygons(viewCells[i]->GetMesh(),
243                                                                  polys,
244                                                                  viewCells[i]);
245                }
246        }
247
248        return polysSize;
249}
250
251
252int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
253                                                                 PolygonContainer &polys,
254                                                                 int maxObjects)
255{
256        int limit = (maxObjects > 0) ?
257                Min((int)objects.size(), maxObjects) : (int)objects.size();
258
259        for (int i = 0; i < limit; ++i)
260        {
261                Intersectable *object = objects[i];//*it;
262                Mesh *mesh = NULL;
263
264                switch (object->Type()) // extract the meshes
265                {
266                case Intersectable::MESH_INSTANCE:
267                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
268                        break;
269                case Intersectable::VIEW_CELL:
270                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
271                        break;
272                        // TODO: handle transformed mesh instances
273                default:
274                        Debug << "intersectable type not supported" << endl;
275                        break;
276                }
277
278        if (mesh) // copy the mesh data to polygons
279                {
280                        mBox.Include(object->GetBox()); // add to BSP tree aabb
281                        AddMeshToPolygons(mesh, polys, NULL);
282                }
283        }
284
285        return (int)polys.size();
286}
287
288
289void VspBspTree::Construct(const VssRayContainer &sampleRays,
290                                                   AxisAlignedBox3 *forcedBoundingBox)
291{
292        mBspStats.nodes = 1;
293        mBox.Initialize();      // initialise BSP tree bounding box
294
295        if (forcedBoundingBox)
296                mBox = *forcedBoundingBox;
297       
298        PolygonContainer polys;
299        RayInfoContainer *rays = new RayInfoContainer();
300
301        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
302
303        long startTime = GetTime();
304
305        cout << "Extracting polygons from rays ... ";
306
307        Intersectable::NewMail();
308
309        int numObj = 0;
310
311        //-- extract polygons intersected by the rays
312        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
313        {
314                VssRay *ray = *rit;
315
316                if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
317                        ray->mTerminationObject &&
318                        !ray->mTerminationObject->Mailed())
319                {
320                        ray->mTerminationObject->Mail();
321                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
322                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
323                        ++ numObj;
324                        //-- compute bounding box
325                        if (!forcedBoundingBox)
326                                mBox.Include(ray->mTermination);
327                }
328
329                if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
330                        ray->mOriginObject &&
331                        !ray->mOriginObject->Mailed())
332                {
333                        ray->mOriginObject->Mail();
334                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
335                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
336                        ++ numObj;
337
338                        //-- compute bounding box
339                        if (!forcedBoundingBox)
340                                mBox.Include(ray->mOrigin);
341                }
342        }
343       
344        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
345
346        //-- store rays
347        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
348        {
349                VssRay *ray = *rit;
350
351                float minT, maxT;
352
353                static Ray hray;
354                hray.Init(*ray);
355
356                // TODO: not very efficient to implictly cast between rays types
357                if (mBox.GetRaySegment(hray, minT, maxT))
358                {
359                        float len = ray->Length();
360
361                        if (!len)
362                                len = Limits::Small;
363
364                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
365                }
366        }
367
368        // normalize
369        if (mUseAreaForPvs)
370                mTermMinProbability *= mBox.SurfaceArea();
371        else
372                mTermMinProbability *= mBox.GetVolume();
373
374        mBspStats.polys = (int)polys.size();
375
376        cout << "finished" << endl;
377
378        Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
379                  << (int)sampleRays.size() << " rays in "
380                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
381
382        Construct(polys, rays);
383
384        // clean up polygons
385        CLEAR_CONTAINER(polys);
386}
387
388
389// return memory usage in MB
390float VspBspTree::GetMemUsage(/*const VspBspTraversalQueue &tstack*/) const
391{
392        return
393                (sizeof(VspBspTree) +
394                 (float)mBspStats.Leaves() * sizeof(BspLeaf) +
395                 // the nodes in the stack is the minimal additional number of leaves
396                 //(float)tstack.size() * sizeof(BspLeaf) +
397                 mBspStats.Interior() * sizeof(BspInterior) +
398                 mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
399}
400
401
402
403void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
404{
405        VspBspTraversalQueue tQueue;
406
407        mRoot = new BspLeaf();
408
409        // constrruct root node geometry
410        BspNodeGeometry *geom = new BspNodeGeometry();
411        ConstructGeometry(mRoot, *geom);
412
413        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
414
415        Debug << "herevol: " << geom->GetVolume() << endl;
416        Debug << "herevol:: " << mBox.GetVolume() << endl;
417
418        VspBspTraversalData tData(mRoot,
419                                                          new PolygonContainer(polys),
420                                                          0,
421                                                          rays,
422                              ComputePvsSize(*rays),
423                                                          prop,
424                                                          geom);
425
426        // first node is kd node, i.e. an axis aligned box
427        if (1)
428        tData.mIsKdNode = true;
429        else
430                tData.mIsKdNode = false;
431
432        tQueue.push(tData);
433
434        mTotalCost = tData.GetCost() / mBox.GetVolume();
435
436        Debug << "**volume** " << mBox.GetVolume() << endl;
437
438        mSplits = 0;
439        mSubdivisionStats
440                        << "#Nodes\n" << ++ mSplits << endl
441                        << "#RenderCostDecrease\n0\n" << endl
442                        << "#TotalRenderCost\n" << mTotalCost << endl;
443
444        Debug << "total cost: " << mTotalCost << endl;
445       
446       
447        mBspStats.Start();
448        cout << "Contructing vsp bsp tree ... \n";
449
450        long startTime = GetTime();     
451
452        // used for intermediate time measurements and progress
453        long interTime = GetTime();     
454
455        mOutOfMemory = false;
456
457        int nleaves = 500;
458
459        while (!tQueue.empty())
460        {
461                tData = tQueue.top();
462            tQueue.pop();               
463
464                if (0 && !mOutOfMemory)
465                {
466                        float mem = GetMemUsage();
467
468                        if (mem > mMaxMemory)
469                        {
470                                mOutOfMemory = true;
471                                Debug << "memory limit reached: " << mem << endl;
472                        }
473                }
474
475                // subdivide leaf node
476                BspNode *r = Subdivide(tQueue, tData);
477
478                if (r == mRoot)
479                        Debug << "VSP BSP tree construction time spent at root: "
480                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
481
482                if (mBspStats.Leaves() >= nleaves)
483                {
484                        nleaves += 500;
485                               
486                        cout << "leaves=" << mBspStats.Leaves() << endl;
487                        Debug << "needed "
488                                  << TimeDiff(interTime, GetTime())*1e-3
489                                  << " secs to create 500 leaves" << endl;
490                        interTime = GetTime();
491                }
492        }
493
494        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
495        cout << "finished\n";
496
497        mBspStats.Stop();
498}
499
500
501bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
502{
503        return
504                (((int)data.mRays->size() <= mTermMinRays) ||
505                 (data.mPvs <= mTermMinPvs)   ||
506                 (data.mProbability <= mTermMinProbability) ||
507                 (mBspStats.Leaves() >= mMaxViewCells) ||
508#if 0
509                 (((int)data.mPolygons->size() <= mTermMinPolygons) && !data.mPolygons->empty())||
510#endif
511                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
512                 (data.mDepth >= mTermMaxDepth));
513}
514
515
516BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
517                                                           VspBspTraversalData &tData)
518{
519        BspNode *newNode = tData.mNode;
520
521        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
522        {
523                PolygonContainer coincident;
524
525                VspBspTraversalData tFrontData;
526                VspBspTraversalData tBackData;
527
528                // create new interior node and two leaf nodes
529                // or return leaf as it is (if maxCostRatio missed)
530                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
531
532                if (!newNode->IsLeaf()) //-- continue subdivision
533                {
534                        if (1)
535                        {
536                                float costDecr =
537                                        (tFrontData.GetCost() + tBackData.GetCost() - tData.GetCost()) / mBox.GetVolume();
538                                mTotalCost += costDecr;
539
540                                mSubdivisionStats
541                                                << "#Nodes\n" << ++ mSplits << endl
542                                                << "#RenderCostDecrease\n" << -costDecr << endl
543                                                << "#TotalRenderCost\n" << mTotalCost << endl;
544                        }
545
546                        // push the children on the stack
547                        tQueue.push(tFrontData);
548                        tQueue.push(tBackData);
549
550                        // delete old leaf node
551                        DEL_PTR(tData.mNode);
552                }
553        }
554
555        //-- terminate traversal and create new view cell
556        if (newNode->IsLeaf())
557        {
558                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
559                BspViewCell *viewCell = new BspViewCell();
560               
561                leaf->SetViewCell(viewCell);
562       
563                //-- update pvs
564                int conSamp = 0;
565                float sampCon = 0.0f;
566                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
567
568                mBspStats.contributingSamples += conSamp;
569                mBspStats.sampleContributions +=(int) sampCon;
570
571                //-- store additional info
572                if (mStoreRays)
573                {
574                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
575                        for (it = tData.mRays->begin(); it != it_end; ++ it)
576                                leaf->mVssRays.push_back((*it).mRay);
577                }
578                // should I check here?
579                if (0 && !mViewCellsManager->CheckValidity(viewCell, 0, mViewCellsManager->GetMaxPvsSize()))
580                {
581                        viewCell->SetValid(false);
582                        leaf->SetTreeValid(false);
583                        PropagateUpValidity(leaf);
584
585                        ++ mBspStats.invalidLeaves;
586                }
587               
588        viewCell->mLeaf = leaf;
589
590                if (mUseAreaForPvs)
591                        viewCell->SetArea(tData.mProbability);
592                else
593                        viewCell->SetVolume(tData.mProbability);
594
595                leaf->mProbability = tData.mProbability;
596
597                EvaluateLeafStats(tData);               
598        }
599
600        //-- cleanup
601        tData.Clear();
602
603        return newNode;
604}
605
606
607BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
608                                                                   VspBspTraversalData &frontData,
609                                                                   VspBspTraversalData &backData,
610                                                                   PolygonContainer &coincident)
611{
612        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
613       
614        // select subdivision plane
615        Plane3 splitPlane;
616       
617        int maxCostMisses = tData.mMaxCostMisses;
618
619        const bool success =
620                SelectPlane(splitPlane, leaf, tData, frontData, backData);
621
622        if (!success)
623        {
624                ++ maxCostMisses;
625
626                if (maxCostMisses > mTermMissTolerance)
627                {
628                        // terminate branch because of max cost
629                        ++ mBspStats.maxCostNodes;
630            return leaf;
631                }
632        }
633
634        mBspStats.nodes += 2;
635
636        //-- subdivide further
637        BspInterior *interior = new BspInterior(splitPlane);
638
639#ifdef _DEBUG
640        Debug << interior << endl;
641#endif
642
643        //-- the front and back traversal data is filled with the new values
644        frontData.mDepth = tData.mDepth + 1;
645        frontData.mPolygons = new PolygonContainer();
646        frontData.mRays = new RayInfoContainer();
647       
648        backData.mDepth = tData.mDepth + 1;
649        backData.mPolygons = new PolygonContainer();
650        backData.mRays = new RayInfoContainer();
651       
652        // subdivide rays
653        SplitRays(interior->GetPlane(),
654                          *tData.mRays,
655                          *frontData.mRays,
656                          *backData.mRays);
657
658        // subdivide polygons
659        SplitPolygons(interior->GetPlane(),
660                                  *tData.mPolygons,
661                      *frontData.mPolygons,
662                                  *backData.mPolygons,
663                                  coincident);
664
665
666        // how often was max cost ratio missed in this branch?
667        frontData.mMaxCostMisses = maxCostMisses;
668        backData.mMaxCostMisses = maxCostMisses;
669
670        // compute pvs
671        frontData.mPvs = ComputePvsSize(*frontData.mRays);
672        backData.mPvs = ComputePvsSize(*backData.mRays);
673
674        // split front and back node geometry and compute area
675       
676        // if geometry was not already computed
677        if (1)//!frontData.mGeometry && !backData.mGeometry)
678        {
679                frontData.mGeometry = new BspNodeGeometry();
680                backData.mGeometry = new BspNodeGeometry();
681
682                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
683                                                                           *backData.mGeometry,
684                                                                           interior->GetPlane(),
685                                                                           mBox,
686                                                                           mEpsilon);
687               
688                if (mUseAreaForPvs)
689                {
690                        frontData.mProbability = frontData.mGeometry->GetArea();
691                        backData.mProbability = backData.mGeometry->GetArea();
692                }
693                else
694                {
695                        //Debug << "here2" << endl;
696                        frontData.mProbability = frontData.mGeometry->GetVolume();
697                        backData.mProbability = tData.mProbability - frontData.mProbability;
698                        //backData.mProbability = backData.mGeometry->GetVolume();
699                }
700        }
701       
702
703        //-- create front and back leaf
704
705        BspInterior *parent = leaf->GetParent();
706
707        // replace a link from node's parent
708        if (parent)
709        {
710                parent->ReplaceChildLink(leaf, interior);
711                interior->SetParent(parent);
712        }
713        else // new root
714        {
715                mRoot = interior;
716        }
717
718        // and setup child links
719        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
720
721        frontData.mNode = interior->GetFront();
722        backData.mNode = interior->GetBack();
723
724        //DEL_PTR(leaf);
725        return interior;
726}
727
728
729void VspBspTree::AddToPvs(BspLeaf *leaf,
730                                                  const RayInfoContainer &rays,
731                                                  float &sampleContributions,
732                                                  int &contributingSamples)
733{
734  sampleContributions = 0;
735  contributingSamples = 0;
736 
737  RayInfoContainer::const_iterator it, it_end = rays.end();
738 
739  ViewCell *vc = leaf->GetViewCell();
740 
741  // add contributions from samples to the PVS
742  for (it = rays.begin(); it != it_end; ++ it)
743        {
744          float sc = 0.0f;
745          VssRay *ray = (*it).mRay;
746          bool madeContrib = false;
747          float contribution;
748          if (ray->mTerminationObject) {
749                if (vc->GetPvs().AddSample(ray->mTerminationObject, ray->mPdf, contribution))
750                  madeContrib = true;
751                sc += contribution;
752          }
753         
754          if (ray->mOriginObject) {
755                if (vc->GetPvs().AddSample(ray->mOriginObject, ray->mPdf, contribution))
756                  madeContrib = true;
757                sc += contribution;
758          }
759         
760          sampleContributions += sc;
761          if (madeContrib)
762                  ++ contributingSamples;
763               
764          //leaf->mVssRays.push_back(ray);
765        }
766}
767
768
769void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
770{
771        mSplitCandidates->clear();
772
773        int requestedSize = 2 * (int)(rays.size());
774        // creates a sorted split candidates array
775        if (mSplitCandidates->capacity() > 500000 &&
776                requestedSize < (int)(mSplitCandidates->capacity()/10) )
777        {
778        delete mSplitCandidates;
779                mSplitCandidates = new vector<SortableEntry>;
780        }
781
782        mSplitCandidates->reserve(requestedSize);
783
784        // insert all queries
785        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
786        {
787                bool positive = (*ri).mRay->HasPosDir(axis);
788                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
789                                                                                                  (*ri).ExtrapOrigin(axis), (*ri).mRay));
790
791                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
792                                                                                                  (*ri).ExtrapTermination(axis), (*ri).mRay));
793        }
794
795        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
796}
797
798
799float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
800                                                                                  const AxisAlignedBox3 &box,
801                                                                                  const int pvsSize,
802                                                                                  const int &axis,
803                                          float &position)
804{
805        int raysBack;
806        int raysFront;
807        int pvsBack;
808        int pvsFront;
809
810        SortSplitCandidates(rays, axis);
811
812        // go through the lists, count the number of objects left and right
813        // and evaluate the following cost funcion:
814        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
815
816        int rl = 0, rr = (int)rays.size();
817        int pl = 0, pr = pvsSize;
818
819        float minBox = box.Min(axis);
820        float maxBox = box.Max(axis);
821        float sizeBox = maxBox - minBox;
822
823        float minBand = minBox + 0.1f*(maxBox - minBox);
824        float maxBand = minBox + 0.9f*(maxBox - minBox);
825
826        float sum = rr*sizeBox;
827        float minSum = 1e20f;
828
829        Intersectable::NewMail();
830
831        // set all object as belonging to the fron pvs
832        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
833        {
834                if ((*ri).mRay->IsActive())
835                {
836                        Intersectable *object = (*ri).mRay->mTerminationObject;
837
838                        if (object)
839                        {
840                                if (!object->Mailed())
841                                {
842                                        object->Mail();
843                                        object->mCounter = 1;
844                                }
845                                else
846                                        ++ object->mCounter;
847                        }
848                }
849        }
850
851        Intersectable::NewMail();
852
853        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
854                ci < mSplitCandidates->end(); ++ ci)
855        {
856                VssRay *ray;
857
858                switch ((*ci).type)
859                {
860                        case SortableEntry::ERayMin:
861                                {
862                                        ++ rl;
863                                        ray = (VssRay *) (*ci).ray;
864
865                                        Intersectable *object = ray->mTerminationObject;
866
867                                        if (object && !object->Mailed())
868                                        {
869                                                object->Mail();
870                                                ++ pl;
871                                        }
872                                        break;
873                                }
874                        case SortableEntry::ERayMax:
875                                {
876                                        -- rr;
877                                        ray = (VssRay *) (*ci).ray;
878
879                                        Intersectable *object = ray->mTerminationObject;
880
881                                        if (object)
882                                        {
883                                                if (-- object->mCounter == 0)
884                                                        -- pr;
885                                        }
886
887                                        break;
888                                }
889                }
890
891                // Note: sufficient to compare size of bounding boxes of front and back side?
892                if ((*ci).value > minBand && (*ci).value < maxBand)
893                {
894                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
895
896                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
897                        // cout<<"cost= "<<sum<<endl;
898
899                        if (sum < minSum)
900                        {
901                                minSum = sum;
902                                position = (*ci).value;
903
904                                raysBack = rl;
905                                raysFront = rr;
906
907                                pvsBack = pl;
908                                pvsFront = pr;
909
910                        }
911                }
912        }
913
914        float oldCost = (float)pvsSize;
915        float newCost = mCtDivCi + minSum / sizeBox;
916        float ratio = newCost / oldCost;
917
918        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
919        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
920
921        return ratio;
922}
923
924
925float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
926                                                                                 const VspBspTraversalData &tData,
927                                                                                 int &axis,
928                                                                                 BspNodeGeometry **frontGeom,
929                                                                                 BspNodeGeometry **backGeom,
930                                                                                 float &pFront,
931                                                                                 float &pBack,
932                                                                                 const bool useKdSplit)
933{
934        const bool useCostHeuristics = false;
935
936        //-- regular split
937        float nPosition[3];
938        float nCostRatio[3];
939        float nProbFront[3];
940        float nProbBack[3];
941
942        BspNodeGeometry *nFrontGeom[3];
943        BspNodeGeometry *nBackGeom[3];
944
945        int bestAxis = -1;
946
947        // create bounding box of node geometry
948        AxisAlignedBox3 box;
949        box.Initialize();
950       
951        //TODO: for kd split geometry already is box => only take minmax vertices
952        if (1)
953        {
954                PolygonContainer::const_iterator it, it_end = tData.mGeometry->mPolys.end();
955
956                for(it = tData.mGeometry->mPolys.begin(); it < it_end; ++ it)
957                        box.Include(*(*it));
958        }
959        else
960        {
961                RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
962
963                for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
964                        box.Include((*ri).ExtrapTermination());
965        }
966
967        const int sAxis = box.Size().DrivingAxis();
968
969        for (axis = 0; axis < 3; ++ axis)
970        {
971                nFrontGeom[axis] = new BspNodeGeometry();
972                nBackGeom[axis] = new BspNodeGeometry();
973
974                if (!mOnlyDrivingAxis || (axis == sAxis))
975                {
976                        if (!useCostHeuristics)
977                        {
978                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
979                                Vector3 normal(0,0,0); normal[axis] = 1.0f;
980
981                                // allows faster split because we have axis aligned kd tree boxes
982                                if (useKdSplit)
983                                {
984                                        nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
985                                                                                                                                box,
986                                                                                                                                axis,
987                                                                                                                                nPosition[axis],
988                                                                                                                                nProbFront[axis],
989                                                                                                                                nProbBack[axis]);
990                                       
991                                        Vector3 pos;
992                                       
993                                        pos = box.Max(); pos[axis] = nPosition[axis];
994                                        AxisAlignedBox3 bBox(box.Min(), pos);
995                                        bBox.ExtractPolys(nBackGeom[axis]->mPolys);
996                                       
997                                        pos = box.Min(); pos[axis] = nPosition[axis];
998                                        AxisAlignedBox3 fBox(pos, box.Max());
999                                        fBox.ExtractPolys(nFrontGeom[axis]->mPolys);
1000                                }
1001                                else
1002                                {
1003                                        nCostRatio[axis] =
1004                                                EvalSplitPlaneCost(Plane3(normal, nPosition[axis]),
1005                                                                                   tData, *nFrontGeom[axis], *nBackGeom[axis],
1006                                                                                   nProbFront[axis], nProbBack[axis]);
1007                                }
1008                        }
1009                        else
1010                        {
1011                                nCostRatio[axis] =
1012                                        BestCostRatioHeuristics(*tData.mRays,
1013                                                                                    box,
1014                                                                                        tData.mPvs,
1015                                                                                        axis,
1016                                                                                        nPosition[axis]);
1017                        }
1018
1019                        if (bestAxis == -1)
1020                        {
1021                                bestAxis = axis;
1022                        }
1023
1024                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
1025                        {
1026                                bestAxis = axis;
1027                        }
1028
1029                }
1030        }
1031
1032        //-- assign values
1033        axis = bestAxis;
1034        pFront = nProbFront[bestAxis];
1035        pBack = nProbBack[bestAxis];
1036
1037        // assign best split nodes geometry
1038        *frontGeom = nFrontGeom[bestAxis];
1039        *backGeom = nBackGeom[bestAxis];
1040
1041        // and delete other geometry
1042        delete nFrontGeom[(bestAxis + 1) % 3];
1043        delete nBackGeom[(bestAxis + 2) % 3];
1044
1045        //-- split plane
1046    Vector3 normal(0,0,0); normal[bestAxis] = 1;
1047        plane = Plane3(normal, nPosition[bestAxis]);
1048
1049        return nCostRatio[bestAxis];
1050}
1051
1052
1053bool VspBspTree::SelectPlane(Plane3 &bestPlane,
1054                                                         BspLeaf *leaf,
1055                                                         VspBspTraversalData &data,
1056                                                         VspBspTraversalData &frontData,
1057                                                         VspBspTraversalData &backData)
1058{
1059        // simplest strategy: just take next polygon
1060        if (mSplitPlaneStrategy & RANDOM_POLYGON)
1061        {
1062        if (!data.mPolygons->empty())
1063                {
1064                        const int randIdx =
1065                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
1066                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
1067
1068                        bestPlane = nextPoly->GetSupportingPlane();
1069                        return true;
1070                }
1071        }
1072
1073        //-- use heuristics to find appropriate plane
1074
1075        // intermediate plane
1076        Plane3 plane;
1077        float lowestCost = MAX_FLOAT;
1078       
1079        // decides if the first few splits should be only axisAligned
1080        const bool onlyAxisAligned  =
1081                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
1082                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1083                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
1084       
1085        const int limit = onlyAxisAligned ? 0 :
1086                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1087
1088        float candidateCost;
1089
1090        int maxIdx = (int)data.mPolygons->size();
1091
1092        for (int i = 0; i < limit; ++ i)
1093        {
1094                // the already taken candidates are stored behind maxIdx
1095                // => assure that no index is taken twice
1096                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
1097                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
1098
1099                // swap candidate to the end to avoid testing same plane
1100                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
1101                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
1102
1103                // evaluate current candidate
1104                BspNodeGeometry fGeom, bGeom;
1105                float fArea, bArea;
1106                plane = poly->GetSupportingPlane();
1107                candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
1108               
1109                if (candidateCost < lowestCost)
1110                {
1111                        bestPlane = plane;
1112                        lowestCost = candidateCost;
1113                }
1114        }
1115
1116        //-- evaluate axis aligned splits
1117        int axis;
1118        BspNodeGeometry *fGeom, *bGeom;
1119        float pFront, pBack;
1120
1121        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
1122                                                                                   &fGeom, &bGeom,
1123                                                                                   pFront, pBack,
1124                                                                                   data.mIsKdNode);     
1125
1126        bool isAxisAlignedSplit = false;
1127
1128        if (candidateCost < lowestCost)
1129        {       
1130                bestPlane = plane;
1131                lowestCost = candidateCost;
1132
1133                // assign already computed values
1134                // we can do this because we always save the
1135                // computed values from the axis aligned splits         
1136                frontData.mGeometry = fGeom;
1137                backData.mGeometry = bGeom;
1138       
1139                frontData.mProbability = pFront;
1140                backData.mProbability = pBack;
1141               
1142                //! error also computed if cost ratio is missed
1143                ++ mBspStats.splits[axis];
1144                isAxisAlignedSplit = true;
1145        }
1146        else
1147        {
1148                DEL_PTR(fGeom);
1149                DEL_PTR(bGeom);
1150        }
1151
1152        frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
1153
1154#ifdef _DEBUG
1155        Debug << "plane lowest cost: " << lowestCost << endl;
1156#endif
1157
1158        // cost ratio miss
1159        if (lowestCost > mTermMaxCostRatio)
1160                return false;
1161
1162        return true;
1163}
1164
1165
1166Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
1167{
1168        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1169
1170        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
1171        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
1172
1173        const Vector3 pt = (maxPt + minPt) * 0.5;
1174        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
1175
1176        return Plane3(normal, pt);
1177}
1178
1179
1180Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
1181{
1182        Vector3 pt[3];
1183
1184        int idx[3];
1185        int cmaxT = 0;
1186        int cminT = 0;
1187        bool chooseMin = false;
1188
1189        for (int j = 0; j < 3; ++ j)
1190        {
1191                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
1192
1193                if (idx[j] >= (int)rays.size())
1194                {
1195                        idx[j] -= (int)rays.size();
1196
1197                        chooseMin = (cminT < 2);
1198                }
1199                else
1200                        chooseMin = (cmaxT < 2);
1201
1202                RayInfo rayInf = rays[idx[j]];
1203                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
1204        }
1205
1206        return Plane3(pt[0], pt[1], pt[2]);
1207}
1208
1209
1210Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
1211{
1212        Vector3 pt[3];
1213
1214        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1215        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1216
1217        // check if rays different
1218        if (idx1 == idx2)
1219                idx2 = (idx2 + 1) % (int)rays.size();
1220
1221        const RayInfo ray1 = rays[idx1];
1222        const RayInfo ray2 = rays[idx2];
1223
1224        // normal vector of the plane parallel to both lines
1225        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
1226
1227        // vector from line 1 to line 2
1228        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
1229
1230        // project vector on normal to get distance
1231        const float dist = DotProd(vd, norm);
1232
1233        // point on plane lies halfway between the two planes
1234        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
1235
1236        return Plane3(norm, planePt);
1237}
1238
1239
1240inline void VspBspTree::GenerateUniqueIdsForPvs()
1241{
1242        Intersectable::NewMail(); sBackId = Intersectable::sMailId;
1243        Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
1244        Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
1245}
1246
1247
1248float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
1249                                                                         const VspBspTraversalData &data,
1250                                                                         BspNodeGeometry &geomFront,
1251                                                                         BspNodeGeometry &geomBack,
1252                                                                         float &pFront,
1253                                                                         float &pBack) const
1254{
1255        float cost = 0;
1256
1257        float sumBalancedRays = 0;
1258        float sumRaySplits = 0;
1259
1260        int pvsFront = 0;
1261        int pvsBack = 0;
1262
1263        // probability that view point lies in back / front node
1264        float pOverall = 0;
1265        pFront = 0;
1266        pBack = 0;
1267
1268        int raysFront = 0;
1269        int raysBack = 0;
1270        int totalPvs = 0;
1271
1272        int limit;
1273        bool useRand;
1274
1275        // choose test rays randomly if too much
1276        if ((int)data.mRays->size() > mMaxTests)
1277        {
1278                useRand = true;
1279                limit = mMaxTests;
1280        }
1281        else
1282        {
1283                useRand = false;
1284                limit = (int)data.mRays->size();
1285        }
1286       
1287        for (int i = 0; i < limit; ++ i)
1288        {
1289                const int testIdx = useRand ?
1290                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
1291                RayInfo rayInf = (*data.mRays)[testIdx];
1292
1293                float t;
1294                VssRay *ray = rayInf.mRay;
1295                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1296
1297        if (0)
1298                {
1299                        if (cf >= 0)
1300                                ++ raysFront;
1301                        if (cf <= 0)
1302                                ++ raysBack;
1303                }
1304
1305                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1306                {
1307                        sumBalancedRays += cf;
1308                }
1309
1310                if (mSplitPlaneStrategy & BALANCED_RAYS)
1311                {
1312                        if (cf == 0)
1313                                ++ sumRaySplits;
1314                }
1315
1316                if (mSplitPlaneStrategy & PVS)
1317                {
1318                        // find front and back pvs for origing and termination object
1319                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1320                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1321                }
1322        }
1323
1324        const float raysSize = (float)data.mRays->size() + Limits::Small;
1325
1326        if (mSplitPlaneStrategy & PVS)
1327        {
1328                // create unique ids for pvs heuristics
1329                GenerateUniqueIdsForPvs();
1330
1331                // construct child geometry with regard to the candidate split plane
1332                data.mGeometry->SplitGeometry(geomFront,
1333                                                                          geomBack,
1334                                                                          candidatePlane,
1335                                                                          mBox,
1336                                                                          mEpsilon);
1337
1338                pOverall = data.mProbability;
1339
1340                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
1341                {
1342                        pFront = geomFront.GetVolume();
1343                        //pBack = pOverall - geomFront.GetVolume();
1344                        pBack = geomBack.GetVolume();
1345
1346                        /*Debug << "volume: " << data.mGeometry->GetVolume() << endl;
1347                        Debug << "volum1: " << geomFront.GetVolume() << endl;
1348                        Debug << "volum2: " << geomBack.GetVolume() << endl;
1349                        Debug << "sum_: " << geomFront.GetVolume() + geomBack.GetVolume() << endl;*/
1350                }
1351                else
1352                {
1353                        pFront = geomFront.GetArea();
1354                        pBack = geomBack.GetArea();
1355                }
1356        }
1357
1358
1359        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1360                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1361
1362        if (mSplitPlaneStrategy & BALANCED_RAYS)
1363                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
1364
1365        // -- pvs rendering heuristics
1366        if (mSplitPlaneStrategy & PVS)
1367        {
1368                const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1369                const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1370
1371                // only render cost heuristics or combined with standard deviation
1372                if (1)
1373                {
1374                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
1375                const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1376                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1377                       
1378                        const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
1379                        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1380
1381                        float oldCost, newCost;
1382
1383                        // only render cost
1384                        if (1)
1385                        {
1386                                oldCost = oldRenderCost;
1387                                newCost = newRenderCost;
1388                        }
1389                        else // also considering standard deviation
1390                        {
1391                                // standard deviation is difference of back and front pvs
1392                                const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
1393
1394                                const float newDeviation = 0.5f *
1395                                        fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
1396
1397                const float oldDeviation = penaltyOld + Limits::Small;
1398
1399                                newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
1400                                oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
1401                        }
1402
1403                        cost += mPvsFactor * newCost / oldCost;
1404                }
1405        }
1406
1407#ifdef _DEBUG
1408        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
1409                  << " frontpvs: " << pvsFront << " pFront: " << pFront
1410                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
1411        Debug << "cost: " << cost << endl;
1412#endif
1413
1414       
1415        // normalize cost by sum of linear factors
1416        if(0)
1417                return cost / (float)mCostNormalizer;
1418        else
1419                return cost;
1420}
1421
1422
1423float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
1424                                                                                   const AxisAlignedBox3 &box,
1425                                                                                   const int axis,
1426                                                                                   const float &position,                                                                                 
1427                                                                                   float &pFront,
1428                                                                                   float &pBack) const
1429{
1430        int pvsTotal = 0;
1431        int pvsFront = 0;
1432        int pvsBack = 0;
1433       
1434        // create unique ids for pvs heuristics
1435        GenerateUniqueIdsForPvs();
1436
1437        const int pvsSize = data.mPvs;
1438
1439        RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
1440
1441        // this is the main ray classification loop!
1442        for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
1443        {
1444                //if (!(*rit).mRay->IsActive()) continue;
1445
1446                // determine the side of this ray with respect to the plane
1447                float t;
1448                const int side = (*rit).ComputeRayIntersection(axis, position, t);
1449       
1450                AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1451                AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1452        }
1453
1454        //-- pvs heuristics
1455        float pOverall;
1456
1457        //-- compute heurstics
1458        //   we take simplified computation for mid split
1459               
1460        pOverall = data.mProbability;
1461
1462        if (!mUseAreaForPvs)
1463        {   // volume
1464                pBack = pFront = pOverall * 0.5f;
1465               
1466#if 0
1467                // box length substitute for probability
1468                const float minBox = box.Min(axis);
1469                const float maxBox = box.Max(axis);
1470
1471                pBack = position - minBox;
1472                pFront = maxBox - position;
1473                pOverall = maxBox - minBox;
1474#endif
1475        }
1476        else //-- area substitute for probability
1477        {
1478                const int axis2 = (axis + 1) % 3;
1479                const int axis3 = (axis + 2) % 3;
1480
1481                const float faceArea =
1482                        (box.Max(axis2) - box.Min(axis2)) *
1483                        (box.Max(axis3) - box.Min(axis3));
1484
1485                pBack = pFront = pOverall * 0.5f + faceArea;
1486        }
1487
1488#ifdef _DEBUG
1489        Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1490        Debug << pFront << " " << pBack << " " << pOverall << endl;
1491#endif
1492
1493       
1494        const float newCost = pvsBack * pBack + pvsFront * pFront;
1495        const float oldCost = (float)pvsSize * pOverall + Limits::Small;
1496
1497        return  (mCtDivCi + newCost) / oldCost;
1498}
1499
1500
1501void VspBspTree::AddObjToPvs(Intersectable *obj,
1502                                                         const int cf,
1503                                                         int &frontPvs,
1504                                                         int &backPvs,
1505                                                         int &totalPvs) const
1506{
1507        if (!obj)
1508                return;
1509       
1510        if ((obj->mMailbox != sFrontId) &&
1511                (obj->mMailbox != sBackId) &&
1512                (obj->mMailbox != sFrontAndBackId))
1513        {
1514                ++ totalPvs;
1515        }
1516
1517        // TODO: does this really belong to no pvs?
1518        //if (cf == Ray::COINCIDENT) return;
1519
1520        // object belongs to both PVS
1521        if (cf >= 0)
1522        {
1523                if ((obj->mMailbox != sFrontId) &&
1524                        (obj->mMailbox != sFrontAndBackId))
1525                {
1526                        ++ frontPvs;
1527               
1528                        if (obj->mMailbox == sBackId)
1529                                obj->mMailbox = sFrontAndBackId;
1530                        else
1531                                obj->mMailbox = sFrontId;
1532                }
1533        }
1534
1535        if (cf <= 0)
1536        {
1537                if ((obj->mMailbox != sBackId) &&
1538                        (obj->mMailbox != sFrontAndBackId))
1539                {
1540                        ++ backPvs;
1541               
1542                        if (obj->mMailbox == sFrontId)
1543                                obj->mMailbox = sFrontAndBackId;
1544                        else
1545                                obj->mMailbox = sBackId;
1546                }
1547        }
1548}
1549
1550
1551void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
1552                                                           const bool onlyUnmailed,
1553                                                           const int maxPvsSize) const
1554{
1555        stack<BspNode *> nodeStack;
1556        nodeStack.push(mRoot);
1557
1558        while (!nodeStack.empty())
1559        {
1560                BspNode *node = nodeStack.top();
1561                nodeStack.pop();
1562               
1563                if (node->IsLeaf())
1564                {
1565                        // test if this leaf is in valid view space
1566                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1567                        if (leaf->TreeValid() &&
1568                                (!onlyUnmailed || !leaf->Mailed()) &&
1569                                ((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
1570                        {
1571                                leaves.push_back(leaf);
1572                        }
1573                }
1574                else
1575                {
1576                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1577
1578                        nodeStack.push(interior->GetBack());
1579                        nodeStack.push(interior->GetFront());
1580                }
1581        }
1582}
1583
1584
1585AxisAlignedBox3 VspBspTree::GetBoundingBox() const
1586{
1587        return mBox;
1588}
1589
1590
1591BspNode *VspBspTree::GetRoot() const
1592{
1593        return mRoot;
1594}
1595
1596
1597void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
1598{
1599        // the node became a leaf -> evaluate stats for leafs
1600        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1601
1602        // store maximal and minimal depth
1603        if (data.mDepth > mBspStats.maxDepth)
1604                mBspStats.maxDepth = data.mDepth;
1605
1606        if (data.mPvs > mBspStats.maxPvs)
1607                mBspStats.maxPvs = data.mPvs;
1608       
1609        if (data.mDepth < mBspStats.minDepth)
1610                mBspStats.minDepth = data.mDepth;
1611
1612        if (data.mDepth >= mTermMaxDepth)
1613                ++ mBspStats.maxDepthNodes;
1614        // accumulate rays to compute rays /  leaf
1615        mBspStats.accumRays += (int)data.mRays->size();
1616
1617        if (data.mPvs < mTermMinPvs)
1618                ++ mBspStats.minPvsNodes;
1619
1620        if ((int)data.mRays->size() < mTermMinRays)
1621                ++ mBspStats.minRaysNodes;
1622
1623        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1624                ++ mBspStats.maxRayContribNodes;
1625
1626        if (data.mProbability <= mTermMinProbability)
1627                ++ mBspStats.minProbabilityNodes;
1628       
1629        // accumulate depth to compute average depth
1630        mBspStats.accumDepth += data.mDepth;
1631
1632#ifdef _DEBUG
1633        Debug << "BSP stats: "
1634                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1635                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1636          //              << "Area: " << data.mProbability << " (min: " << mTermMinProbability << "), "
1637                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1638                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1639                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1640#endif
1641}
1642
1643int VspBspTree::CastRay(Ray &ray)
1644{
1645        int hits = 0;
1646
1647        stack<BspRayTraversalData> tQueue;
1648
1649        float maxt, mint;
1650
1651        if (!mBox.GetRaySegment(ray, mint, maxt))
1652                return 0;
1653
1654        Intersectable::NewMail();
1655        ViewCell::NewMail();
1656        Vector3 entp = ray.Extrap(mint);
1657        Vector3 extp = ray.Extrap(maxt);
1658
1659        BspNode *node = mRoot;
1660        BspNode *farChild = NULL;
1661
1662        while (1)
1663        {
1664                if (!node->IsLeaf())
1665                {
1666                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1667
1668                        Plane3 splitPlane = in->GetPlane();
1669                        const int entSide = splitPlane.Side(entp);
1670                        const int extSide = splitPlane.Side(extp);
1671
1672                        if (entSide < 0)
1673                        {
1674                                node = in->GetBack();
1675
1676                                if(extSide <= 0) // plane does not split ray => no far child
1677                                        continue;
1678
1679                                farChild = in->GetFront(); // plane splits ray
1680
1681                        } else if (entSide > 0)
1682                        {
1683                                node = in->GetFront();
1684
1685                                if (extSide >= 0) // plane does not split ray => no far child
1686                                        continue;
1687
1688                                farChild = in->GetBack(); // plane splits ray
1689                        }
1690                        else // ray and plane are coincident
1691                        {
1692                                // WHAT TO DO IN THIS CASE ?
1693                                //break;
1694                                node = in->GetFront();
1695                                continue;
1696                        }
1697
1698                        // push data for far child
1699                        tQueue.push(BspRayTraversalData(farChild, extp, maxt));
1700
1701                        // find intersection of ray segment with plane
1702                        float t;
1703                        extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1704                        maxt *= t;
1705
1706                } else // reached leaf => intersection with view cell
1707                {
1708                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1709
1710                        if (!leaf->GetViewCell()->Mailed())
1711                        {
1712                                //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
1713                                leaf->GetViewCell()->Mail();
1714                                ++ hits;
1715                        }
1716
1717                        //-- fetch the next far child from the stack
1718                        if (tQueue.empty())
1719                                break;
1720
1721                        entp = extp;
1722                        mint = maxt; // NOTE: need this?
1723
1724                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1725                                break;
1726
1727                        BspRayTraversalData &s = tQueue.top();
1728
1729                        node = s.mNode;
1730                        extp = s.mExitPoint;
1731                        maxt = s.mMaxT;
1732
1733                        tQueue.pop();
1734                }
1735        }
1736
1737        return hits;
1738}
1739
1740
1741void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1742{
1743        ViewCell::NewMail();
1744       
1745        CollectViewCells(mRoot, onlyValid, viewCells, true);
1746}
1747
1748
1749void VspBspTree::CollapseViewCells()
1750{
1751// TODO
1752#if VC_HISTORY
1753        stack<BspNode *> nodeStack;
1754
1755        if (!mRoot)
1756                return;
1757
1758        nodeStack.push(mRoot);
1759       
1760        while (!nodeStack.empty())
1761        {
1762                BspNode *node = nodeStack.top();
1763                nodeStack.pop();
1764               
1765                if (node->IsLeaf())
1766        {
1767                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1768
1769                        if (!viewCell->GetValid())
1770                        {
1771                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1772       
1773                                ViewCellContainer leaves;
1774                                mViewCellsTree->CollectLeaves(viewCell, leaves);
1775
1776                                ViewCellContainer::const_iterator it, it_end = leaves.end();
1777
1778                                for (it = leaves.begin(); it != it_end; ++ it)
1779                                {
1780                                        BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
1781                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
1782                                        ++ mBspStats.invalidLeaves;
1783                                }
1784
1785                                // add to unbounded view cell
1786                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1787                                DEL_PTR(viewCell);
1788                        }
1789                }
1790                else
1791                {
1792                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1793               
1794                        nodeStack.push(interior->GetFront());
1795                        nodeStack.push(interior->GetBack());
1796                }
1797        }
1798
1799        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
1800#endif
1801}
1802
1803
1804void VspBspTree::ValidateTree()
1805{
1806        stack<BspNode *> nodeStack;
1807
1808        if (!mRoot)
1809                return;
1810
1811        nodeStack.push(mRoot);
1812       
1813        mBspStats.invalidLeaves = 0;
1814        while (!nodeStack.empty())
1815        {
1816                BspNode *node = nodeStack.top();
1817                nodeStack.pop();
1818               
1819                if (node->IsLeaf())
1820                {
1821                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1822
1823                        if (!leaf->GetViewCell()->GetValid())
1824                                ++ mBspStats.invalidLeaves;
1825
1826                        // validity flags don't match => repair
1827                        if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
1828                        {
1829                                leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
1830                                PropagateUpValidity(leaf);
1831                        }
1832                }
1833                else
1834                {
1835                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1836               
1837                        nodeStack.push(interior->GetFront());
1838                        nodeStack.push(interior->GetBack());
1839                }
1840        }
1841
1842        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
1843}
1844
1845
1846
1847void VspBspTree::CollectViewCells(BspNode *root,
1848                                                                  bool onlyValid,
1849                                                                  ViewCellContainer &viewCells,
1850                                                                  bool onlyUnmailed) const
1851{
1852        stack<BspNode *> nodeStack;
1853
1854        if (!root)
1855                return;
1856
1857        nodeStack.push(root);
1858       
1859        while (!nodeStack.empty())
1860        {
1861                BspNode *node = nodeStack.top();
1862                nodeStack.pop();
1863               
1864                if (node->IsLeaf())
1865                {
1866                        if (!onlyValid || node->TreeValid())
1867                        {
1868                                ViewCell *viewCell =
1869                                        mViewCellsTree->GetActiveViewCell(dynamic_cast<BspLeaf *>(node)->GetViewCell());
1870                                               
1871                                if (!onlyUnmailed || !viewCell->Mailed())
1872                                {
1873                                        viewCell->Mail();
1874                                        viewCells.push_back(viewCell);
1875                                }
1876                        }
1877                }
1878                else
1879                {
1880                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1881               
1882                        nodeStack.push(interior->GetFront());
1883                        nodeStack.push(interior->GetBack());
1884                }
1885        }
1886
1887}
1888
1889
1890float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1891{
1892        float len = 0;
1893
1894        RayInfoContainer::const_iterator it, it_end = rays.end();
1895
1896        for (it = rays.begin(); it != it_end; ++ it)
1897                len += (*it).SegmentLength();
1898
1899        return len;
1900}
1901
1902
1903int VspBspTree::SplitRays(const Plane3 &plane,
1904                                                  RayInfoContainer &rays,
1905                                                  RayInfoContainer &frontRays,
1906                                                  RayInfoContainer &backRays)
1907{
1908        int splits = 0;
1909
1910        RayInfoContainer::const_iterator it, it_end = rays.end();
1911
1912        for (it = rays.begin(); it != it_end; ++ it)
1913        {
1914                RayInfo bRay = *it;
1915               
1916                VssRay *ray = bRay.mRay;
1917                float t;
1918
1919                // get classification and receive new t
1920                const int cf = bRay.ComputeRayIntersection(plane, t);
1921
1922                switch (cf)
1923                {
1924                case -1:
1925                        backRays.push_back(bRay);
1926                        break;
1927                case 1:
1928                        frontRays.push_back(bRay);
1929                        break;
1930                case 0:
1931                        {
1932                                //-- split ray
1933                                //-- test if start point behind or in front of plane
1934                                const int side = plane.Side(bRay.ExtrapOrigin());
1935
1936                                if (side <= 0)
1937                                {
1938                                        backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1939                                        frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1940                                }
1941                                else
1942                                {
1943                                        frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1944                                        backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1945                                }
1946                        }
1947                        break;
1948                default:
1949                        Debug << "Should not come here" << endl;
1950                        break;
1951                }
1952        }
1953
1954        return splits;
1955}
1956
1957
1958void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1959{
1960        BspNode *lastNode;
1961
1962        do
1963        {
1964                lastNode = n;
1965
1966                // want to get planes defining geometry of this node => don't take
1967                // split plane of node itself
1968                n = n->GetParent();
1969
1970                if (n)
1971                {
1972                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
1973                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1974
1975            if (interior->GetFront() != lastNode)
1976                                halfSpace.ReverseOrientation();
1977
1978                        halfSpaces.push_back(halfSpace);
1979                }
1980        }
1981        while (n);
1982}
1983
1984
1985void VspBspTree::ConstructGeometry(BspNode *n,
1986                                                                   BspNodeGeometry &geom) const
1987{
1988        vector<Plane3> halfSpaces;
1989        ExtractHalfSpaces(n, halfSpaces);
1990
1991        PolygonContainer candidatePolys;
1992
1993        // bounded planes are added to the polygons (reverse polygons
1994        // as they have to be outfacing
1995        for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1996        {
1997                Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1998
1999                if (p->Valid(mEpsilon))
2000                {
2001                        candidatePolys.push_back(p->CreateReversePolygon());
2002                        DEL_PTR(p);
2003                }
2004        }
2005
2006        // add faces of bounding box (also could be faces of the cell)
2007        for (int i = 0; i < 6; ++ i)
2008        {
2009                VertexContainer vertices;
2010
2011                for (int j = 0; j < 4; ++ j)
2012                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
2013
2014                candidatePolys.push_back(new Polygon3(vertices));
2015        }
2016
2017        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2018        {
2019                // polygon is split by all other planes
2020                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
2021                {
2022                        if (i == j) // polygon and plane are coincident
2023                                continue;
2024
2025                        VertexContainer splitPts;
2026                        Polygon3 *frontPoly, *backPoly;
2027
2028                        const int cf =
2029                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
2030                                                                                                 mEpsilon);
2031
2032                        switch (cf)
2033                        {
2034                                case Polygon3::SPLIT:
2035                                        frontPoly = new Polygon3();
2036                                        backPoly = new Polygon3();
2037
2038                                        candidatePolys[i]->Split(halfSpaces[j],
2039                                                                                         *frontPoly,
2040                                                                                         *backPoly,
2041                                                                                         mEpsilon);
2042
2043                                        DEL_PTR(candidatePolys[i]);
2044
2045                                        if (frontPoly->Valid(mEpsilon))
2046                                                candidatePolys[i] = frontPoly;
2047                                        else
2048                                                DEL_PTR(frontPoly);
2049
2050                                        DEL_PTR(backPoly);
2051                                        break;
2052                                case Polygon3::BACK_SIDE:
2053                                        DEL_PTR(candidatePolys[i]);
2054                                        break;
2055                                // just take polygon as it is
2056                                case Polygon3::FRONT_SIDE:
2057                                case Polygon3::COINCIDENT:
2058                                default:
2059                                        break;
2060                        }
2061                }
2062
2063                if (candidatePolys[i])
2064                        geom.mPolys.push_back(candidatePolys[i]);
2065        }
2066}
2067
2068
2069void VspBspTree::ConstructGeometry(ViewCell *vc,
2070                                                                   BspNodeGeometry &vcGeom) const
2071{
2072        ViewCellContainer leaves;
2073       
2074        mViewCellsTree->CollectLeaves(vc, leaves);
2075
2076        ViewCellContainer::const_iterator it, it_end = leaves.end();
2077
2078        for (it = leaves.begin(); it != it_end; ++ it)
2079        {
2080                BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
2081               
2082                ConstructGeometry(l, vcGeom);
2083        }
2084}
2085
2086
2087typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
2088
2089
2090int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
2091                                                          const bool onlyUnmailed) const
2092{
2093        stack<bspNodePair> nodeStack;
2094       
2095        BspNodeGeometry nodeGeom;
2096        ConstructGeometry(n, nodeGeom);
2097       
2098        // split planes from the root to this node
2099        // needed to verify that we found neighbor leaf
2100        // TODO: really needed?
2101        vector<Plane3> halfSpaces;
2102        ExtractHalfSpaces(n, halfSpaces);
2103
2104
2105        BspNodeGeometry *rgeom = new BspNodeGeometry();
2106        ConstructGeometry(mRoot, *rgeom);
2107
2108        nodeStack.push(bspNodePair(mRoot, rgeom));
2109
2110        while (!nodeStack.empty())
2111        {
2112                BspNode *node = nodeStack.top().first;
2113                BspNodeGeometry *geom = nodeStack.top().second;
2114       
2115                nodeStack.pop();
2116
2117                if (node->IsLeaf())
2118                {
2119                        // test if this leaf is in valid view space
2120                        if (node->TreeValid() &&
2121                                (node != n) &&
2122                                (!onlyUnmailed || !node->Mailed()))
2123                        {
2124                                bool isAdjacent = true;
2125
2126                                if (1)
2127                                {
2128                                        // test all planes of current node if still adjacent
2129                                        for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
2130                                        {
2131                                                const int cf =
2132                                                        Polygon3::ClassifyPlane(geom->mPolys,
2133                                                                                                        halfSpaces[i],
2134                                                                                                        mEpsilon);
2135
2136                                                if (cf == Polygon3::BACK_SIDE)
2137                                                {
2138                                                        isAdjacent = false;
2139                                                }
2140                                        }
2141                                }
2142                                else
2143                                {
2144                                        // TODO: why is this wrong??
2145                                        // test all planes of current node if still adjacent
2146                                        for (int i = 0; (i < (int)nodeGeom.mPolys.size()) && isAdjacent; ++ i)
2147                                        {
2148                                                Polygon3 *poly = nodeGeom.mPolys[i];
2149
2150                                                const int cf =
2151                                                        Polygon3::ClassifyPlane(geom->mPolys,
2152                                                                                                        poly->GetSupportingPlane(),
2153                                                                                                        mEpsilon);
2154
2155                                                if (cf == Polygon3::BACK_SIDE)
2156                                                {
2157                                                        isAdjacent = false;
2158                                                }
2159                                        }
2160                                }
2161                                // neighbor was found
2162                                if (isAdjacent)
2163                                {       
2164                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2165                                }
2166                        }
2167                }
2168                else
2169                {
2170                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2171
2172                        const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
2173                                                                                                   interior->GetPlane(),
2174                                                                                                   mEpsilon);
2175                       
2176                        BspNode *front = interior->GetFront();
2177                        BspNode *back = interior->GetBack();
2178           
2179                        BspNodeGeometry *fGeom = new BspNodeGeometry();
2180                        BspNodeGeometry *bGeom = new BspNodeGeometry();
2181
2182                        geom->SplitGeometry(*fGeom,
2183                                                                *bGeom,
2184                                                                interior->GetPlane(),
2185                                                                mBox,
2186                                                                mEpsilon);
2187               
2188                        if (cf == Polygon3::FRONT_SIDE)
2189                        {
2190                                nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
2191                                DEL_PTR(bGeom);
2192                        }
2193                        else
2194                        {
2195                                if (cf == Polygon3::BACK_SIDE)
2196                                {
2197                                        nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
2198                                        DEL_PTR(fGeom);
2199                                }
2200                                else
2201                                {       // random decision
2202                                        nodeStack.push(bspNodePair(front, fGeom));
2203                                        nodeStack.push(bspNodePair(back, bGeom));
2204                                }
2205                        }
2206                }
2207       
2208                DEL_PTR(geom);
2209        }
2210
2211        return (int)neighbors.size();
2212}
2213
2214
2215
2216int VspBspTree::FindApproximateNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
2217                                                                                 const bool onlyUnmailed) const
2218{
2219        stack<bspNodePair> nodeStack;
2220       
2221        BspNodeGeometry nodeGeom;
2222        ConstructGeometry(n, nodeGeom);
2223       
2224        // split planes from the root to this node
2225        // needed to verify that we found neighbor leaf
2226        // TODO: really needed?
2227        vector<Plane3> halfSpaces;
2228        ExtractHalfSpaces(n, halfSpaces);
2229
2230
2231        BspNodeGeometry *rgeom = new BspNodeGeometry();
2232        ConstructGeometry(mRoot, *rgeom);
2233
2234        nodeStack.push(bspNodePair(mRoot, rgeom));
2235
2236        while (!nodeStack.empty())
2237        {
2238                BspNode *node = nodeStack.top().first;
2239                BspNodeGeometry *geom = nodeStack.top().second;
2240       
2241                nodeStack.pop();
2242
2243                if (node->IsLeaf())
2244                {
2245                        // test if this leaf is in valid view space
2246                        if (node->TreeValid() &&
2247                                (node != n) &&
2248                                (!onlyUnmailed || !node->Mailed()))
2249                        {
2250                                bool isAdjacent = true;
2251
2252                                // neighbor was found
2253                                if (isAdjacent)
2254                                {       
2255                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
2256                                }
2257                        }
2258                }
2259                else
2260                {
2261                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2262
2263                        const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
2264                                                                                                   interior->GetPlane(),
2265                                                                                                   mEpsilon);
2266                       
2267                        BspNode *front = interior->GetFront();
2268                        BspNode *back = interior->GetBack();
2269           
2270                        BspNodeGeometry *fGeom = new BspNodeGeometry();
2271                        BspNodeGeometry *bGeom = new BspNodeGeometry();
2272
2273                        geom->SplitGeometry(*fGeom,
2274                                                                *bGeom,
2275                                                                interior->GetPlane(),
2276                                                                mBox,
2277                                                                mEpsilon);
2278               
2279                        if (cf == Polygon3::FRONT_SIDE)
2280                        {
2281                                nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
2282                                DEL_PTR(bGeom);
2283                        }
2284                        else
2285                        {
2286                                if (cf == Polygon3::BACK_SIDE)
2287                                {
2288                                        nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
2289                                        DEL_PTR(fGeom);
2290                                }
2291                                else
2292                                {       // random decision
2293                                        nodeStack.push(bspNodePair(front, fGeom));
2294                                        nodeStack.push(bspNodePair(back, bGeom));
2295                                }
2296                        }
2297                }
2298       
2299                DEL_PTR(geom);
2300        }
2301
2302        return (int)neighbors.size();
2303}
2304
2305
2306
2307BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
2308{
2309    stack<BspNode *> nodeStack;
2310        nodeStack.push(mRoot);
2311
2312        int mask = rand();
2313
2314        while (!nodeStack.empty())
2315        {
2316                BspNode *node = nodeStack.top();
2317                nodeStack.pop();
2318
2319                if (node->IsLeaf())
2320                {
2321                        return dynamic_cast<BspLeaf *>(node);
2322                }
2323                else
2324                {
2325                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2326                        BspNode *next;
2327                        BspNodeGeometry geom;
2328
2329                        // todo: not very efficient: constructs full cell everytime
2330                        ConstructGeometry(interior, geom);
2331
2332                        const int cf =
2333                                Polygon3::ClassifyPlane(geom.mPolys, halfspace, mEpsilon);
2334
2335                        if (cf == Polygon3::BACK_SIDE)
2336                                next = interior->GetFront();
2337                        else
2338                                if (cf == Polygon3::FRONT_SIDE)
2339                                        next = interior->GetFront();
2340                        else
2341                        {
2342                                // random decision
2343                                if (mask & 1)
2344                                        next = interior->GetBack();
2345                                else
2346                                        next = interior->GetFront();
2347                                mask = mask >> 1;
2348                        }
2349
2350                        nodeStack.push(next);
2351                }
2352        }
2353
2354        return NULL;
2355}
2356
2357BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
2358{
2359        stack<BspNode *> nodeStack;
2360
2361        nodeStack.push(mRoot);
2362
2363        int mask = rand();
2364
2365        while (!nodeStack.empty())
2366        {
2367                BspNode *node = nodeStack.top();
2368                nodeStack.pop();
2369
2370                if (node->IsLeaf())
2371                {
2372                        if ( (!onlyUnmailed || !node->Mailed()) )
2373                                return dynamic_cast<BspLeaf *>(node);
2374                }
2375                else
2376                {
2377                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2378
2379                        // random decision
2380                        if (mask & 1)
2381                                nodeStack.push(interior->GetBack());
2382                        else
2383                                nodeStack.push(interior->GetFront());
2384
2385                        mask = mask >> 1;
2386                }
2387        }
2388
2389        return NULL;
2390}
2391
2392int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
2393{
2394        int pvsSize = 0;
2395
2396        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2397
2398        Intersectable::NewMail();
2399
2400        for (rit = rays.begin(); rit != rays.end(); ++ rit)
2401        {
2402                VssRay *ray = (*rit).mRay;
2403
2404                if (ray->mOriginObject)
2405                {
2406                        if (!ray->mOriginObject->Mailed())
2407                        {
2408                                ray->mOriginObject->Mail();
2409                                ++ pvsSize;
2410                        }
2411                }
2412                if (ray->mTerminationObject)
2413                {
2414                        if (!ray->mTerminationObject->Mailed())
2415                        {
2416                                ray->mTerminationObject->Mail();
2417                                ++ pvsSize;
2418                        }
2419                }
2420        }
2421
2422        return pvsSize;
2423}
2424
2425float VspBspTree::GetEpsilon() const
2426{
2427        return mEpsilon;
2428}
2429
2430
2431int VspBspTree::SplitPolygons(const Plane3 &plane,
2432                                                          PolygonContainer &polys,
2433                                                          PolygonContainer &frontPolys,
2434                                                          PolygonContainer &backPolys,
2435                                                          PolygonContainer &coincident) const
2436{
2437        int splits = 0;
2438
2439        PolygonContainer::const_iterator it, it_end = polys.end();
2440
2441        for (it = polys.begin(); it != polys.end(); ++ it)     
2442        {
2443                Polygon3 *poly = *it;
2444
2445                // classify polygon
2446                const int cf = poly->ClassifyPlane(plane, mEpsilon);
2447
2448                switch (cf)
2449                {
2450                        case Polygon3::COINCIDENT:
2451                                coincident.push_back(poly);
2452                                break;
2453                        case Polygon3::FRONT_SIDE:
2454                                frontPolys.push_back(poly);
2455                                break;
2456                        case Polygon3::BACK_SIDE:
2457                                backPolys.push_back(poly);
2458                                break;
2459                        case Polygon3::SPLIT:
2460                                backPolys.push_back(poly);
2461                                frontPolys.push_back(poly);
2462                                ++ splits;
2463                                break;
2464                        default:
2465                Debug << "SHOULD NEVER COME HERE\n";
2466                                break;
2467                }
2468        }
2469
2470        return splits;
2471}
2472
2473
2474int VspBspTree::CastLineSegment(const Vector3 &origin,
2475                                                                const Vector3 &termination,
2476                                                                vector<ViewCell *> &viewcells)
2477{
2478        int hits = 0;
2479        stack<BspRayTraversalData> tQueue;
2480
2481        float mint = 0.0f, maxt = 1.0f;
2482
2483        Intersectable::NewMail();
2484        ViewCell::NewMail();
2485
2486        Vector3 entp = origin;
2487        Vector3 extp = termination;
2488
2489        BspNode *node = mRoot;
2490        BspNode *farChild = NULL;
2491
2492        float t;
2493        while (1)
2494        {
2495                if (!node->IsLeaf())
2496                {
2497                        BspInterior *in = dynamic_cast<BspInterior *>(node);
2498
2499                        Plane3 splitPlane = in->GetPlane();
2500                       
2501                        const int entSide = splitPlane.Side(entp);
2502                        const int extSide = splitPlane.Side(extp);
2503
2504                        if (entSide < 0)
2505                        {
2506                          node = in->GetBack();
2507                          // plane does not split ray => no far child
2508                          if (extSide <= 0)
2509                                continue;
2510                         
2511                          farChild = in->GetFront(); // plane splits ray
2512                        }
2513                        else if (entSide > 0)
2514                        {
2515                          node = in->GetFront();
2516
2517                          if (extSide >= 0) // plane does not split ray => no far child
2518                                continue;
2519
2520                                farChild = in->GetBack(); // plane splits ray
2521                        }
2522                        else // ray end point on plane
2523                        {       // NOTE: what to do if ray is coincident with plane?
2524                                if (extSide < 0)
2525                                        node = in->GetBack();
2526                                else
2527                                        node = in->GetFront();
2528                                                               
2529                                continue; // no far child
2530                        }
2531
2532                        // push data for far child
2533                        tQueue.push(BspRayTraversalData(farChild, extp));
2534
2535                        // find intersection of ray segment with plane
2536                        extp = splitPlane.FindIntersection(origin, extp, &t);
2537                }
2538                else
2539                {
2540                        // reached leaf => intersection with view cell
2541                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2542
2543                        ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
2544                        if (!viewCell->Mailed())
2545                        {
2546                                viewcells.push_back(viewCell);
2547                                viewCell->Mail();
2548                                ++ hits;
2549                        }
2550
2551                        //-- fetch the next far child from the stack
2552                        if (tQueue.empty())
2553                                break;
2554
2555                        entp = extp;
2556                       
2557                        BspRayTraversalData &s = tQueue.top();
2558
2559                        node = s.mNode;
2560                        extp = s.mExitPoint;
2561
2562                        tQueue.pop();
2563                }
2564        }
2565
2566        return hits;
2567}
2568
2569
2570
2571
2572int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
2573{
2574        std::deque<BspNode *> path1;
2575        BspNode *p1 = n1;
2576
2577        // create path from node 1 to root
2578        while (p1)
2579        {
2580                if (p1 == n2) // second node on path
2581                        return (int)path1.size();
2582
2583                path1.push_front(p1);
2584                p1 = p1->GetParent();
2585        }
2586
2587        int depth = n2->GetDepth();
2588        int d = depth;
2589
2590        BspNode *p2 = n2;
2591
2592        // compare with same depth
2593        while (1)
2594        {
2595                if ((d < (int)path1.size()) && (p2 == path1[d]))
2596                        return (depth - d) + ((int)path1.size() - 1 - d);
2597
2598                -- d;
2599                p2 = p2->GetParent();
2600        }
2601
2602        return 0; // never come here
2603}
2604
2605
2606BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
2607{
2608// TODO
2609#if VC_HISTORY
2610        if (node->IsLeaf())
2611                return node;
2612
2613        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2614
2615        BspNode *front = CollapseTree(interior->GetFront(), collapsed);
2616        BspNode *back = CollapseTree(interior->GetBack(), collapsed);
2617
2618        if (front->IsLeaf() && back->IsLeaf())
2619        {
2620                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
2621                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
2622
2623                //-- collapse tree
2624                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
2625                {
2626                        BspViewCell *vc = frontLeaf->GetViewCell();
2627
2628                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
2629                        leaf->SetTreeValid(frontLeaf->TreeValid());
2630
2631                        // replace a link from node's parent
2632                        if (leaf->GetParent())
2633                                leaf->GetParent()->ReplaceChildLink(node, leaf);
2634                        else
2635                                mRoot = leaf;
2636
2637                        ++ collapsed;
2638                        delete interior;
2639
2640                        return leaf;
2641                }
2642        }
2643#endif
2644        return node;
2645}
2646
2647
2648int VspBspTree::CollapseTree()
2649{
2650        int collapsed = 0;
2651        //TODO
2652#if VC_HISTORY
2653        (void)CollapseTree(mRoot, collapsed);
2654
2655        // revalidate leaves
2656        RepairViewCellsLeafLists();
2657#endif
2658        return collapsed;
2659}
2660
2661
2662void VspBspTree::RepairViewCellsLeafLists()
2663{
2664// TODO
2665#if VC_HISTORY
2666        // list not valid anymore => clear
2667        stack<BspNode *> nodeStack;
2668        nodeStack.push(mRoot);
2669
2670        ViewCell::NewMail();
2671
2672        while (!nodeStack.empty())
2673        {
2674                BspNode *node = nodeStack.top();
2675                nodeStack.pop();
2676
2677                if (node->IsLeaf())
2678                {
2679                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2680
2681                        BspViewCell *viewCell = leaf->GetViewCell();
2682
2683                        if (!viewCell->Mailed())
2684                        {
2685                                viewCell->mLeaves.clear();
2686                                viewCell->Mail();
2687                        }
2688       
2689                        viewCell->mLeaves.push_back(leaf);
2690
2691                }
2692                else
2693                {
2694                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2695
2696                        nodeStack.push(interior->GetFront());
2697                        nodeStack.push(interior->GetBack());
2698                }
2699        }
2700// TODO
2701#endif
2702}
2703
2704
2705typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
2706
2707
2708int VspBspTree::CastBeam(Beam &beam)
2709{
2710    stack<bspNodePair> nodeStack;
2711        BspNodeGeometry *rgeom = new BspNodeGeometry();
2712        ConstructGeometry(mRoot, *rgeom);
2713
2714        nodeStack.push(bspNodePair(mRoot, rgeom));
2715 
2716        ViewCell::NewMail();
2717
2718        while (!nodeStack.empty())
2719        {
2720                BspNode *node = nodeStack.top().first;
2721                BspNodeGeometry *geom = nodeStack.top().second;
2722                nodeStack.pop();
2723               
2724                AxisAlignedBox3 box;
2725                box.Initialize();
2726                geom->IncludeInBox(box);
2727
2728                const int side = beam.ComputeIntersection(box);
2729               
2730                switch (side)
2731                {
2732                case -1:
2733                        CollectViewCells(node, true, beam.mViewCells, true);
2734                        break;
2735                case 0:
2736                       
2737                        if (node->IsLeaf())
2738                        {
2739                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2740                       
2741                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2742                                {
2743                                        leaf->GetViewCell()->Mail();
2744                                        beam.mViewCells.push_back(leaf->GetViewCell());
2745                                }
2746                        }
2747                        else
2748                        {
2749                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
2750                       
2751                                BspNode *first = interior->GetFront();
2752                                BspNode *second = interior->GetBack();
2753           
2754                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
2755                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
2756
2757                                geom->SplitGeometry(*firstGeom,
2758                                                                        *secondGeom,
2759                                                                        interior->GetPlane(),
2760                                                                        mBox,
2761                                                                        mEpsilon);
2762
2763                                // decide on the order of the nodes
2764                                if (DotProd(beam.mPlanes[0].mNormal,
2765                                        interior->GetPlane().mNormal) > 0)
2766                                {
2767                                        swap(first, second);
2768                                        swap(firstGeom, secondGeom);
2769                                }
2770
2771                                nodeStack.push(bspNodePair(first, firstGeom));
2772                                nodeStack.push(bspNodePair(second, secondGeom));
2773                        }
2774                       
2775                        break;
2776                default:
2777                        // default: cull
2778                        break;
2779                }
2780               
2781                DEL_PTR(geom);
2782               
2783        }
2784
2785        return (int)beam.mViewCells.size();
2786}
2787
2788
2789void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2790{
2791        mViewCellsManager = vcm;
2792}
2793
2794
2795int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
2796                                                                           vector<MergeCandidate> &candidates)
2797{
2798        BspLeaf::NewMail();
2799       
2800        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2801
2802        int numCandidates = 0;
2803
2804        // find merge candidates and push them into queue
2805        for (it = leaves.begin(); it != it_end; ++ it)
2806        {
2807                BspLeaf *leaf = *it;
2808               
2809                // the same leaves must not be part of two merge candidates
2810                leaf->Mail();
2811                vector<BspLeaf *> neighbors;
2812                FindNeighbors(leaf, neighbors, true);
2813                //FindApproximateNeighbors(leaf, neighbors, true);
2814                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
2815
2816                // TODO: test if at least one ray goes from one leaf to the other
2817                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2818                {
2819                        if ((*nit)->GetViewCell() != leaf->GetViewCell())
2820                        {
2821                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
2822                                candidates.push_back(mc);
2823
2824                                ++ numCandidates;
2825                                if ((numCandidates % 1000) == 0)
2826                                {
2827                                        cout << "collected " << numCandidates << " merge candidates" << endl;
2828                                }
2829                        }
2830                }
2831        }
2832
2833        Debug << "merge queue: " << (int)candidates.size() << endl;
2834        Debug << "leaves in queue: " << numCandidates << endl;
2835       
2836
2837        return (int)leaves.size();
2838}
2839
2840
2841int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays,
2842                                                                           vector<MergeCandidate> &candidates)
2843{
2844        ViewCell::NewMail();
2845        long startTime = GetTime();
2846       
2847        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
2848        ViewCellContainer::const_iterator iit;
2849
2850        int numLeaves = 0;
2851       
2852        BspLeaf::NewMail();
2853
2854        for (int i = 0; i < (int)rays.size(); ++ i)
2855        { 
2856                VssRay *ray = rays[i];
2857       
2858                // traverse leaves stored in the rays and compare and
2859                // merge consecutive leaves (i.e., the neighbors in the tree)
2860                if (ray->mViewCells.size() < 2)
2861                        continue;
2862//TODO viewcellhierarchy
2863                iit = ray->mViewCells.begin();
2864                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
2865                BspLeaf *leaf = bspVc->mLeaf;
2866               
2867                // traverse intersections
2868                // consecutive leaves are neighbors => add them to queue
2869                for (; iit != ray->mViewCells.end(); ++ iit)
2870                {
2871                        // next pair
2872                        BspLeaf *prevLeaf = leaf;
2873                        bspVc = dynamic_cast<BspViewCell *>(*iit);
2874            leaf = bspVc->mLeaf;
2875
2876                        // view space not valid or same view cell
2877                        if (!leaf->TreeValid() || !prevLeaf->TreeValid() ||
2878                                (leaf->GetViewCell() == prevLeaf->GetViewCell()))
2879                                continue;
2880
2881                vector<BspLeaf *> &neighbors = neighborMap[leaf];
2882                       
2883                        bool found = false;
2884
2885                        // both leaves inserted in queue already =>
2886                        // look if double pair already exists
2887                        if (leaf->Mailed() && prevLeaf->Mailed())
2888                        {
2889                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
2890                               
2891                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
2892                                        if (*it == prevLeaf)
2893                                                found = true; // already in queue
2894                        }
2895               
2896                        if (!found)
2897                        {
2898                                // this pair is not in map yet
2899                                // => insert into the neighbor map and the queue
2900                                neighbors.push_back(prevLeaf);
2901                                neighborMap[prevLeaf].push_back(leaf);
2902
2903                                leaf->Mail();
2904                                prevLeaf->Mail();
2905               
2906                                MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
2907                               
2908                                candidates.push_back(mc);
2909
2910                                if (((int)candidates.size() % 1000) == 0)
2911                                {
2912                                        cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
2913                                }
2914                        }
2915        }
2916        }
2917
2918        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
2919        Debug << "merge queue: " << (int)candidates.size() << endl;
2920        Debug << "leaves in queue: " << numLeaves << endl;
2921
2922
2923        //-- collect the leaves which haven't been found by ray casting
2924        if (0)
2925        {
2926                cout << "finding additional merge candidates using geometry" << endl;
2927                vector<BspLeaf *> leaves;
2928                CollectLeaves(leaves, true);
2929                Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
2930                CollectMergeCandidates(leaves, candidates);
2931        }
2932
2933        return numLeaves;
2934}
2935
2936
2937
2938
2939ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
2940{
2941  if (mRoot == NULL)
2942        return NULL;
2943 
2944  stack<BspNode *> nodeStack;
2945  nodeStack.push(mRoot);
2946 
2947  ViewCell *viewcell = NULL;
2948 
2949  while (!nodeStack.empty())  {
2950        BspNode *node = nodeStack.top();
2951        nodeStack.pop();
2952       
2953        if (node->IsLeaf()) {
2954          viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
2955          break;
2956        } else {
2957         
2958          BspInterior *interior = dynamic_cast<BspInterior *>(node);
2959               
2960          // random decision
2961          if (interior->GetPlane().Side(point) < 0)
2962                nodeStack.push(interior->GetBack());
2963          else
2964                nodeStack.push(interior->GetFront());
2965        }
2966  }
2967 
2968  return viewcell;
2969}
2970
2971
2972bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
2973{
2974        BspNode *node = mRoot;
2975
2976        while (1)
2977        {
2978                // early exit
2979                if (node->TreeValid())
2980                        return true;
2981
2982                if (node->IsLeaf())
2983                        return false;
2984                       
2985                BspInterior *in = dynamic_cast<BspInterior *>(node);
2986                                       
2987                if (in->GetPlane().Side(viewPoint) <= 0)
2988                {
2989                        node = in->GetBack();
2990                }
2991                else
2992                {
2993                        node = in->GetFront();
2994                }
2995        }
2996
2997        // should never come here
2998        return false;
2999}
3000
3001
3002void VspBspTree::PropagateUpValidity(BspNode *node)
3003{
3004        const bool isValid = node->TreeValid();
3005
3006        // propagative up invalid flag until only invalid nodes exist over this node
3007        if (!isValid)
3008        {
3009                while (!node->IsRoot() && node->GetParent()->TreeValid())
3010                {
3011                        node = node->GetParent();
3012                        node->SetTreeValid(false);
3013                }
3014        }
3015        else
3016        {
3017                // propagative up valid flag until one of the subtrees is invalid
3018                while (!node->IsRoot() && !node->TreeValid())
3019                {
3020            node = node->GetParent();
3021                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3022                       
3023                        // the parent is valid iff both leaves are valid
3024                        node->SetTreeValid(interior->GetBack()->TreeValid() &&
3025                                                           interior->GetFront()->TreeValid());
3026                }
3027        }
3028}
3029
3030
3031bool VspBspTree::Export(ofstream &stream)
3032{
3033        ExportNode(mRoot, stream);
3034
3035        return true;
3036}
3037
3038
3039void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
3040{
3041        if (node->IsLeaf())
3042        {
3043                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
3044                ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
3045
3046                int id = -1;
3047                if (viewCell != mOutOfBoundsCell)
3048                        id = viewCell->GetId();
3049
3050                stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
3051        }
3052        else
3053        {
3054                BspInterior *interior = dynamic_cast<BspInterior *>(node);
3055       
3056                Plane3 plane = interior->GetPlane();
3057                stream << "<Interior plane=\"" << plane.mNormal.x << " "
3058                           << plane.mNormal.y << " " << plane.mNormal.z << " "
3059                           << plane.mD << "\">" << endl;
3060
3061                ExportNode(interior->GetBack(), stream);
3062                ExportNode(interior->GetFront(), stream);
3063
3064                stream << "</Interior>" << endl;
3065        }
3066}
Note: See TracBrowser for help on using the repository browser.