source: GTP/trunk/Lib/Vis/Preprocessing/src/VspBspTree.cpp @ 1449

Revision 1449, 98.1 KB checked in by mattausch, 18 years ago (diff)
RevLine 
[478]1#include <stack>
2#include <time.h>
3#include <iomanip>
4
[463]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"
[478]17#include "ViewCellsManager.h"
[532]18#include "Beam.h"
[463]19
[1077]20
21
[863]22namespace GtpVisibilityPreprocessor {
[860]23
[1077]24
[639]25#define USE_FIXEDPOINT_T 0
[1020]26#define COUNT_ORIGIN_OBJECTS 1
[590]27
[1020]28       
[463]29//-- static members
[508]30
[482]31int VspBspTree::sFrontId = 0;
[463]32int VspBspTree::sBackId = 0;
33int VspBspTree::sFrontAndBackId = 0;
34
[1020]35
36
[697]37typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
[463]38
[557]39
[579]40// pvs penalty can be different from pvs size
[882]41inline static float EvalPvsPenalty(const int pvs,
42                                                                   const int lower,
43                                                                   const int upper)
[579]44{
45        // clamp to minmax values
46        if (pvs < lower)
47                return (float)lower;
48        if (pvs > upper)
49                return (float)upper;
[578]50
[579]51        return (float)pvs;
52}
[463]53
[557]54
[579]55
56
[601]57/******************************************************************************/
58/*                       class VspBspTree implementation                      */
59/******************************************************************************/
[579]60
61
[1004]62VspBspTree::VspBspTree():
[463]63mRoot(NULL),
[547]64mUseAreaForPvs(false),
[478]65mCostNormalizer(Limits::Small),
66mViewCellsManager(NULL),
[497]67mOutOfBoundsCell(NULL),
[643]68mStoreRays(false),
[605]69mRenderCostWeight(0.5),
[610]70mUseRandomAxis(false),
[650]71mTimeStamp(1)
[463]72{
[486]73        bool randomize = false;
[1004]74        Environment::GetSingleton()->GetBoolValue("VspBspTree.Construction.randomize", randomize);
[1011]75        if (randomize) Randomize(); // initialise random generator for heuristics
[463]76
77        //-- termination criteria for autopartition
[1004]78        Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
79        Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
80        Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
81        Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
82        Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
83        Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
[1023]84       
[1004]85        Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
86        Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
[666]87
[564]88        //-- max cost ratio for early tree termination
[1004]89        Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
[610]90
[1004]91        Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.minGlobalCostRatio", mTermMinGlobalCostRatio);
92        Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
[610]93
[463]94        //-- factors for bsp tree split plane heuristics
[1004]95        Environment::GetSingleton()->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
96        Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
[463]97
[482]98
[463]99        //-- partition criteria
[1004]100        Environment::GetSingleton()->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
101        Environment::GetSingleton()->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
102        Environment::GetSingleton()->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
[463]103
[1004]104        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
105        Environment::GetSingleton()->GetIntValue("VspBspTree.maxTests", mMaxTests);
[463]106
[564]107        // if only the driving axis is used for axis aligned split
[1004]108        Environment::GetSingleton()->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
[580]109       
[508]110        //-- termination criteria for axis aligned split
[1004]111        Environment::GetSingleton()->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
[665]112                                                                mTermMaxRayContriForAxisAligned);
[1004]113        Environment::GetSingleton()->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
[665]114                                                         mTermMinRaysForAxisAligned);
[487]115
[1004]116        //Environment::GetSingleton()->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
117        Environment::GetSingleton()->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
[508]118
[1004]119        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
[1020]120        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.renderCostDecreaseWeight", mRenderCostDecreaseWeight);
[1004]121        Environment::GetSingleton()->GetBoolValue("VspBspTree.usePolygonSplitIfAvailable", mUsePolygonSplitIfAvailable);
[547]122
[1004]123        Environment::GetSingleton()->GetBoolValue("VspBspTree.useCostHeuristics", mUseCostHeuristics);
124        Environment::GetSingleton()->GetBoolValue("VspBspTree.useSplitCostQueue", mUseSplitCostQueue);
125        Environment::GetSingleton()->GetBoolValue("VspBspTree.simulateOctree", mCirculatingAxis);
126        Environment::GetSingleton()->GetBoolValue("VspBspTree.useRandomAxis", mUseRandomAxis);
127        Environment::GetSingleton()->GetIntValue("VspBspTree.nodePriorityQueueType", mNodePriorityQueueType);
[580]128
[676]129       
[660]130        char subdivisionStatsLog[100];
[1004]131        Environment::GetSingleton()->GetStringValue("VspBspTree.subdivisionStats", subdivisionStatsLog);
[660]132        mSubdivisionStats.open(subdivisionStatsLog);
[612]133
[1004]134        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.minBand", mMinBand);
135        Environment::GetSingleton()->GetFloatValue("VspBspTree.Construction.maxBand", mMaxBand);
[1006]136        Environment::GetSingleton()->GetBoolValue("VspBspTree.Construction.useDrivingAxisForMaxCost", mUseDrivingAxisIfMaxCostViolated);
[801]137
[478]138        //-- debug output
[580]139
[473]140        Debug << "******* VSP BSP options ******** " << endl;
141    Debug << "max depth: " << mTermMaxDepth << endl;
142        Debug << "min PVS: " << mTermMinPvs << endl;
[547]143        Debug << "min probabiliy: " << mTermMinProbability << endl;
[473]144        Debug << "min rays: " << mTermMinRays << endl;
145        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
146        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
147        Debug << "miss tolerance: " << mTermMissTolerance << endl;
148        Debug << "max view cells: " << mMaxViewCells << endl;
149        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
[663]150        //Debug << "max plane candidates: " << mMaxRayCandidates << endl;
[486]151        Debug << "randomize: " << randomize << endl;
[582]152
[551]153        Debug << "using area for pvs: " << mUseAreaForPvs << endl;
[580]154        Debug << "render cost weight: " << mRenderCostWeight << endl;
[663]155        Debug << "min global cost ratio: " << mTermMinGlobalCostRatio << endl;
156        Debug << "global cost miss tolerance: " << mTermGlobalCostMissTolerance << endl;
157        Debug << "only driving axis: " << mOnlyDrivingAxis << endl;
158        Debug << "max memory: " << mMaxMemory << endl;
159        Debug << "use poly split if available: " << mUsePolygonSplitIfAvailable << endl;
160        Debug << "use cost heuristics: " << mUseCostHeuristics << endl;
161        Debug << "use split cost queue: " << mUseSplitCostQueue << endl;
162        Debug << "subdivision stats log: " << subdivisionStatsLog << endl;
[664]163        Debug << "use random axis: " << mUseRandomAxis << endl;
[735]164        Debug << "priority queue type: " << mNodePriorityQueueType << endl;
[822]165        Debug << "circulating axis: " << mCirculatingAxis << endl;
[801]166        Debug << "minband: " << mMinBand << endl;
167        Debug << "maxband: " << mMaxBand << endl;
[1006]168        Debug << "use driving axis for max cost: " << mUseDrivingAxisIfMaxCostViolated << endl;
[1020]169        Debug << "render cost decrease weight: " << mRenderCostDecreaseWeight << endl;
[663]170
[463]171        Debug << "Split plane strategy: ";
[564]172
[463]173        if (mSplitPlaneStrategy & RANDOM_POLYGON)
[474]174        {
[463]175                Debug << "random polygon ";
[474]176        }
[463]177        if (mSplitPlaneStrategy & AXIS_ALIGNED)
[472]178        {
[463]179                Debug << "axis aligned ";
[472]180        }
[665]181        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
[472]182        {
[474]183                mCostNormalizer += mLeastRaySplitsFactor;
[463]184                Debug << "least ray splits ";
[472]185        }
[463]186        if (mSplitPlaneStrategy & BALANCED_RAYS)
[472]187        {
[474]188                mCostNormalizer += mBalancedRaysFactor;
[463]189                Debug << "balanced rays ";
[472]190        }
[463]191        if (mSplitPlaneStrategy & PVS)
[472]192        {
[474]193                mCostNormalizer += mPvsFactor;
[463]194                Debug << "pvs";
[665]195        }
[482]196
[489]197
[1233]198        mLocalSubdivisionCandidates = new vector<SortableEntry>;
[463]199
200        Debug << endl;
201}
[580]202
[1027]203
[508]204BspViewCell *VspBspTree::GetOutOfBoundsCell()
205{
206        return mOutOfBoundsCell;
207}
[463]208
[508]209
[489]210BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
211{
212        if (!mOutOfBoundsCell)
[508]213        {
[489]214                mOutOfBoundsCell = new BspViewCell();
[508]215                mOutOfBoundsCell->SetId(-1);
[547]216                mOutOfBoundsCell->SetValid(false);
[508]217        }
[547]218
[489]219        return mOutOfBoundsCell;
220}
221
222
[482]223const BspTreeStatistics &VspBspTree::GetStatistics() const
[463]224{
[574]225        return mBspStats;
[463]226}
227
228
229VspBspTree::~VspBspTree()
230{
231        DEL_PTR(mRoot);
[1233]232        DEL_PTR(mLocalSubdivisionCandidates);
[463]233}
234
[579]235
[482]236int VspBspTree::AddMeshToPolygons(Mesh *mesh,
237                                                                  PolygonContainer &polys,
[463]238                                                                  MeshInstance *parent)
239{
240        FaceContainer::const_iterator fi;
[482]241
[463]242        // copy the face data to polygons
243        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
244        {
245                Polygon3 *poly = new Polygon3((*fi), mesh);
[482]246
[463]247                if (poly->Valid(mEpsilon))
248                {
249                        poly->mParent = parent; // set parent intersectable
250                        polys.push_back(poly);
251                }
252                else
253                        DEL_PTR(poly);
254        }
255        return (int)mesh->mFaces.size();
256}
257
[580]258
[482]259int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
[882]260                                                                 PolygonContainer &polys,
261                                                                 int maxObjects)
[463]262{
[482]263        int limit = (maxObjects > 0) ?
[463]264                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
[482]265
[463]266        int polysSize = 0;
267
268        for (int i = 0; i < limit; ++ i)
269        {
270                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
271                {
272                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
[482]273                        polysSize +=
274                                AddMeshToPolygons(viewCells[i]->GetMesh(),
275                                                                  polys,
[463]276                                                                  viewCells[i]);
277                }
278        }
279
280        return polysSize;
281}
282
[580]283
[482]284int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
285                                                                 PolygonContainer &polys,
[463]286                                                                 int maxObjects)
287{
[482]288        int limit = (maxObjects > 0) ?
[463]289                Min((int)objects.size(), maxObjects) : (int)objects.size();
[482]290
[463]291        for (int i = 0; i < limit; ++i)
292        {
293                Intersectable *object = objects[i];//*it;
294                Mesh *mesh = NULL;
295
296                switch (object->Type()) // extract the meshes
297                {
298                case Intersectable::MESH_INSTANCE:
299                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
300                        break;
301                case Intersectable::VIEW_CELL:
302                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
303                        break;
[1001]304                case Intersectable::TRANSFORMED_MESH_INSTANCE:
305                        {
306                                TransformedMeshInstance *mi = dynamic_cast<TransformedMeshInstance *>(object);
307
[1002]308                                if (!mi->GetMesh())     
[1001]309                                        break;
[1002]310                                mesh = new Mesh();
311                                mi->GetTransformedMesh(*mesh);
312                               
[1001]313                break;
314                        }
[463]315                default:
316                        Debug << "intersectable type not supported" << endl;
317                        break;
318                }
[482]319
[463]320        if (mesh) // copy the mesh data to polygons
321                {
322                        mBox.Include(object->GetBox()); // add to BSP tree aabb
[485]323                        AddMeshToPolygons(mesh, polys, NULL);
[1001]324
325                        // cleanup
326                        if (object->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
327                                DEL_PTR(mesh);
[463]328                }
329        }
330
331        return (int)polys.size();
332}
333
[580]334
[1027]335void VspBspTree::ComputeBoundingBox(const VssRayContainer &sampleRays,
336                                                                        AxisAlignedBox3 *forcedBoundingBox)
337{
338        if (forcedBoundingBox)
339        {
340                mBox = *forcedBoundingBox;
341        }
342        else // compute vsp tree bounding box
343        {
344                mBox.Initialize();
345
346                VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
347
348                //-- compute bounding box
349        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
350                {
351                        VssRay *ray = *rit;
352
353                        // compute bounding box of view space
354                        mBox.Include(ray->GetTermination());
355                        mBox.Include(ray->GetOrigin());
356                }
357        }
358}
359
360
[483]361void VspBspTree::Construct(const VssRayContainer &sampleRays,
362                                                   AxisAlignedBox3 *forcedBoundingBox)
[463]363{
[1027]364        // Compute the bounding box from the rays
365        ComputeBoundingBox(sampleRays, forcedBoundingBox);
[484]366       
[463]367        PolygonContainer polys;
368        RayInfoContainer *rays = new RayInfoContainer();
369
[1027]370        //-- extract polygons from rays if there are polygon candidates
371        if (mMaxPolyCandidates)
372        {
373                int numObj = 0;
[463]374
[1027]375                Intersectable::NewMail();
[463]376
[1027]377        cout << "Extracting polygons from rays ... ";
[463]378
[1027]379                long startTime = GetTime();
[463]380
[1027]381        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
[542]382
[1027]383                //-- extract polygons intersected by the rays
384                for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
[463]385                {
[1027]386                        VssRay *ray = *rit;
387                        Intersectable *obj = ray->mTerminationObject;
[1002]388
[1027]389                        if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
390                                obj && !obj->Mailed())
[1002]391                        {
[1027]392                                obj->Mail();
393
394                                // transformed mesh instance and mesh instance handle mesh differently
395                                if (obj->Type() == Intersectable::TRANSFORMED_MESH_INSTANCE)
396                                {
397                                        Mesh mesh;
[1002]398                               
[1027]399                                        TransformedMeshInstance *tmobj =
400                                                dynamic_cast<TransformedMeshInstance *>(obj);
[1002]401                               
[1027]402                                        tmobj->GetTransformedMesh(mesh);
403                                        AddMeshToPolygons(&mesh, polys, tmobj);
404                                }
405                                else // MeshInstance
406                                {
407                                        MeshInstance *mobj = dynamic_cast<MeshInstance *>(obj);
408                                        AddMeshToPolygons(mobj->GetMesh(), polys, mobj);
409                                }
410
411                                ++ numObj;
412
413                                //-- compute bounding box
414                                if (!forcedBoundingBox)
415                                        mBox.Include(ray->mTermination);
[1002]416                        }
[1027]417
418                        if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
419                                ray->mOriginObject &&
420                                !ray->mOriginObject->Mailed())
421                        {               
422                                ray->mOriginObject->Mail();
423                                MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
424                                AddMeshToPolygons(obj->GetMesh(), polys, obj);
425                               
426                                ++ numObj;
[1002]427                        }
[1027]428                }
[1002]429
[1027]430                // throw out unnecessary polygons
431                PreprocessPolygons(polys);
[648]432
[1027]433                cout << "finished" << endl;
[463]434
[1027]435                Debug << "\n" << (int)polys.size() << " polys extracted from "
436                  << (int)sampleRays.size() << " rays in "
437                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
[463]438        }
[535]439       
[1027]440        Debug << "maximal pvs (i.e., pvs still considered as valid): "
[653]441                  << mViewCellsManager->GetMaxPvsSize() << endl;
[580]442
[1027]443        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
444
[463]445        //-- store rays
446        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
447        {
448                VssRay *ray = *rit;
[482]449
[463]450                float minT, maxT;
451
[564]452                static Ray hray;
453                hray.Init(*ray);
[562]454
[483]455                // TODO: not very efficient to implictly cast between rays types
[564]456                if (mBox.GetRaySegment(hray, minT, maxT))
[463]457                {
458                        float len = ray->Length();
[482]459
460                        if (!len)
[463]461                                len = Limits::Small;
[482]462
[463]463                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
464                }
465        }
466
[587]467        // normalize
[547]468        if (mUseAreaForPvs)
[587]469                mTermMinProbability *= mBox.SurfaceArea();
[547]470        else
471                mTermMinProbability *= mBox.GetVolume();
472
[648]473
[1027]474        mBspStats.nodes = 1;
[574]475        mBspStats.polys = (int)polys.size();
[1449]476        mBspStats.mGlobalCostMisses = 0;
[654]477
[463]478
[655]479        // use split cost priority queue
480        if (mUseSplitCostQueue)
481        {
[654]482                ConstructWithSplitQueue(polys, rays);
[655]483        }
[654]484        else
[655]485        {
[654]486                Construct(polys, rays);
[655]487        }
[463]488
489        // clean up polygons
490        CLEAR_CONTAINER(polys);
491}
492
[508]493
[612]494// TODO: return memory usage in MB
[656]495float VspBspTree::GetMemUsage() const
[508]496{
[656]497        return (float)
498                 (sizeof(VspBspTree) +
499                  mBspStats.Leaves() * sizeof(BspLeaf) +
500                  mCreatedViewCells * sizeof(BspViewCell) +
[1189]501                  mBspStats.pvs * sizeof(PvsData) +
[656]502                  mBspStats.Interior() * sizeof(BspInterior) +
503                  mBspStats.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
[508]504}
505
506
[463]507void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
508{
[600]509        VspBspTraversalQueue tQueue;
[463]510
[1016]511        /// create new vsp tree
[463]512        mRoot = new BspLeaf();
513
514        // constrruct root node geometry
515        BspNodeGeometry *geom = new BspNodeGeometry();
516        ConstructGeometry(mRoot, *geom);
517
[1016]518        /// we use the overall probability as normalizer
519        /// either the overall area or the volume
[547]520        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
521
[1020]522        /// first traversal data
[482]523        VspBspTraversalData tData(mRoot,
524                                                          new PolygonContainer(polys),
[463]525                                                          0,
[482]526                                                          rays,
527                              ComputePvsSize(*rays),
[547]528                                                          prop,
[463]529                                                          geom);
[663]530
[1302]531        // evaluate the priority of this traversal data
[664]532        EvalPriority(tData);
[663]533
[578]534        // first node is kd node, i.e. an axis aligned box
[710]535        if (1)
[578]536        tData.mIsKdNode = true;
537        else
538                tData.mIsKdNode = false;
[562]539
[600]540        tQueue.push(tData);
[463]541
[609]542
[605]543        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
[607]544        mTotalPvsSize = tData.mPvs;
545       
[1020]546        // first subdivison statistics
547        AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
548   
[574]549        mBspStats.Start();
[667]550        cout << "Constructing vsp bsp tree ... \n";
[463]551
[1016]552        const long startTime = GetTime();       
553        // used for intermediate time measurements and progress
554        long interTime = GetTime();
555
[664]556        int nLeaves = 500;
557        int nViewCells = 500;
[587]558
[542]559        mOutOfMemory = false;
[612]560        mCreatedViewCells = 0;
561       
[600]562        while (!tQueue.empty())
[463]563        {
[600]564                tData = tQueue.top();
565            tQueue.pop();               
[463]566
[508]567                if (0 && !mOutOfMemory)
568                {
569                        float mem = GetMemUsage();
[478]570
[508]571                        if (mem > mMaxMemory)
572                        {
573                                mOutOfMemory = true;
574                                Debug << "memory limit reached: " << mem << endl;
575                        }
576                }
577
[587]578                // subdivide leaf node
[1016]579                const BspNode *r = Subdivide(tQueue, tData);
[463]580
581                if (r == mRoot)
[482]582                        Debug << "VSP BSP tree construction time spent at root: "
[542]583                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
584
[654]585                if (mBspStats.Leaves() >= nLeaves)
[542]586                {
[612]587                        nLeaves += 500;
588
[574]589                        cout << "leaves=" << mBspStats.Leaves() << endl;
[542]590                        Debug << "needed "
[587]591                                  << TimeDiff(interTime, GetTime())*1e-3
[612]592                                  << " secs to create 500 view cells" << endl;
[542]593                        interTime = GetTime();
594                }
[612]595
[664]596                if (mCreatedViewCells >= nViewCells)
[612]597                {
598                        nViewCells += 500;
599
600                        cout << "generated " << mCreatedViewCells << " viewcells" << endl;
601                }
[463]602        }
603
[542]604        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
[1020]605        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
[463]606
[574]607        mBspStats.Stop();
[463]608}
609
[508]610
[653]611
[654]612void VspBspTree::ConstructWithSplitQueue(const PolygonContainer &polys,
[653]613                                                                                          RayInfoContainer *rays)
614{
615        VspBspSplitQueue tQueue;
616
617        mRoot = new BspLeaf();
618
619        // constrruct root node geometry
620        BspNodeGeometry *geom = new BspNodeGeometry();
621        ConstructGeometry(mRoot, *geom);
622
623        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
624
625        VspBspTraversalData tData(mRoot,
626                                                          new PolygonContainer(polys),
627                                                          0,
628                                                          rays,
629                              ComputePvsSize(*rays),
630                                                          prop,
631                                                          geom);
632
[663]633
[1076]634        // first node is kd node, i.e. an axis aligned box
635        if (1)
636        tData.mIsKdNode = true;
637        else
638                tData.mIsKdNode = false;
639
[660]640        // compute first split candidate
[1233]641        VspBspSubdivisionCandidate splitCandidate;
[1145]642        splitCandidate.mParentData = tData;
[653]643
[1233]644        EvalSubdivisionCandidate(splitCandidate);
[1145]645
[653]646        tQueue.push(splitCandidate);
647
648        mTotalCost = tData.mPvs * tData.mProbability / mBox.GetVolume();
649        mTotalPvsSize = tData.mPvs;
650       
[1020]651        // first subdivison statistics
652        AddSubdivisionStats(1, 0, 0, mTotalCost, (float)mTotalPvsSize);
653   
654    mBspStats.Start();
[667]655        cout << "Constructing vsp bsp tree ... \n";
[653]656
657        long startTime = GetTime();     
[666]658        int nLeaves = 500;
659        int nViewCells = 500;
[653]660
661        // used for intermediate time measurements and progress
662        long interTime = GetTime();     
663
664        mOutOfMemory = false;
665
666        mCreatedViewCells = 0;
667       
668        while (!tQueue.empty())
669        {
670                splitCandidate = tQueue.top();
671            tQueue.pop();               
672
[654]673                // cost ratio of cost decrease / totalCost
[1288]674                float costRatio = splitCandidate.mRenderCostDecr / mTotalCost;
[654]675
[655]676                //Debug << "cost ratio: " << costRatio << endl;
[654]677                if (costRatio < mTermMinGlobalCostRatio)
[1449]678                {
679                        ++ mBspStats.mGlobalCostMisses;
680                }
681
[653]682                if (0 && !mOutOfMemory)
683                {
684                        float mem = GetMemUsage();
685                        if (mem > mMaxMemory)
686                        {
687                                mOutOfMemory = true;
688                                Debug << "memory limit reached: " << mem << endl;
689                        }
690                }
691
692                // subdivide leaf node
693                BspNode *r = Subdivide(tQueue, splitCandidate);
694
695                if (r == mRoot)
[1449]696                {
[653]697                        Debug << "VSP BSP tree construction time spent at root: "
698                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
[1449]699                }
[653]700
[654]701                if (mBspStats.Leaves() >= nLeaves)
[653]702                {
703                        nLeaves += 500;
704
705                        cout << "leaves=" << mBspStats.Leaves() << endl;
706                        Debug << "needed "
707                                  << TimeDiff(interTime, GetTime())*1e-3
708                                  << " secs to create 500 view cells" << endl;
709                        interTime = GetTime();
710                }
711
712                if (mCreatedViewCells == nViewCells)
713                {
714                        nViewCells += 500;
715                        cout << "generated " << mCreatedViewCells << " viewcells" << endl;
716                }
717        }
718
719        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
720        cout << "finished\n";
721
722        mBspStats.Stop();
723}
724
725
[654]726bool VspBspTree::LocalTerminationCriteriaMet(const VspBspTraversalData &data) const
[463]727{
[482]728        return
[463]729                (((int)data.mRays->size() <= mTermMinRays) ||
[473]730                 (data.mPvs <= mTermMinPvs)   ||
[547]731                 (data.mProbability <= mTermMinProbability) ||
[535]732                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
[463]733                 (data.mDepth >= mTermMaxDepth));
734}
735
[508]736
[1020]737void VspBspTree::AddSubdivisionStats(const int viewCells,
738                                                                         const float renderCostDecr,
739                                                                         const float splitCandidateCost,
740                                                                         const float totalRenderCost,
741                                                                         const float avgRenderCost)
742{
743        mSubdivisionStats
744                        << "#ViewCells\n" << viewCells << endl
745                        << "#RenderCostDecrease\n" << renderCostDecr << endl
[1233]746                        << "#SubdivisionCandidateCost\n" << splitCandidateCost << endl
[1020]747                        << "#TotalRenderCost\n" << totalRenderCost << endl
748                        << "#AvgRenderCost\n" << avgRenderCost << endl;
749}
750
751
[654]752bool VspBspTree::GlobalTerminationCriteriaMet(const VspBspTraversalData &data) const
753{
754        return
[1302]755                (0
756                || mOutOfMemory
[654]757                || (mBspStats.Leaves() >= mMaxViewCells)
[1449]758                || (mBspStats.mGlobalCostMisses >= mTermGlobalCostMissTolerance)
[654]759                 );
760}
761
762
[600]763BspNode *VspBspTree::Subdivide(VspBspTraversalQueue &tQueue,
[463]764                                                           VspBspTraversalData &tData)
765{
[473]766        BspNode *newNode = tData.mNode;
767
[654]768        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
[473]769        {
770                PolygonContainer coincident;
[482]771
[473]772                VspBspTraversalData tFrontData;
773                VspBspTraversalData tBackData;
[612]774
[473]775                // create new interior node and two leaf nodes
776                // or return leaf as it is (if maxCostRatio missed)
[653]777                int splitAxis;
778                bool splitFurther = true;
779                int maxCostMisses = tData.mMaxCostMisses;
780               
781                Plane3 splitPlane;
782                BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
[726]783               
784                // choose next split plane
[653]785                if (!SelectPlane(splitPlane, leaf, tData, tFrontData, tBackData, splitAxis))
[473]786                {
[653]787                        ++ maxCostMisses;
788
789                        if (maxCostMisses > mTermMissTolerance)
790                        {
791                                // terminate branch because of max cost
792                                ++ mBspStats.maxCostNodes;
793                                splitFurther = false;
794                        }
795                }
796       
[726]797                // if this a valid split => subdivide this node further
[1193]798
799                if (splitFurther)
[653]800                {
801                        newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
802
803                        if (splitAxis < 3)
804                                ++ mBspStats.splits[splitAxis];
805                        else
806                                ++ mBspStats.polySplits;
807
[822]808                        // if it was a kd node (i.e., a box) and the split axis is axis aligned, it is still a kd node
[710]809                        tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
[1076]810                       
[726]811                        tFrontData.mAxis = tBackData.mAxis = splitAxis;
[663]812
[653]813                        // how often was max cost ratio missed in this branch?
814                        tFrontData.mMaxCostMisses = maxCostMisses;
815                        tBackData.mMaxCostMisses = maxCostMisses;
816
[664]817                        EvalPriority(tFrontData);
818                        EvalPriority(tBackData);
[663]819
[726]820                        // evaluate subdivision stats
[600]821                        if (1)
[1145]822                                EvalSubdivisionStats(tData, tFrontData, tBackData);
823                       
[605]824
[473]825                        // push the children on the stack
[600]826                        tQueue.push(tFrontData);
827                        tQueue.push(tBackData);
[473]828
829                        // delete old leaf node
[482]830                        DEL_PTR(tData.mNode);
[473]831                }
832        }
[482]833
[478]834        //-- terminate traversal and create new view cell
[473]835        if (newNode->IsLeaf())
[463]836        {
[473]837                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
[1020]838               
[547]839                BspViewCell *viewCell = new BspViewCell();
[463]840                leaf->SetViewCell(viewCell);
[487]841       
842                //-- update pvs
[556]843                int conSamp = 0;
844                float sampCon = 0.0f;
845                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
[487]846
[1002]847                // update scalar pvs size lookup
[1160]848                ObjectPvs &pvs = viewCell->GetPvs();
[1168]849                mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
[1002]850       
[752]851
[574]852                mBspStats.contributingSamples += conSamp;
[1047]853                mBspStats.sampleContributions += (int)sampCon;
[487]854
855                //-- store additional info
[478]856                if (mStoreRays)
857                {
858                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
859                        for (it = tData.mRays->begin(); it != it_end; ++ it)
[639]860                        {
861                                (*it).mRay->Ref();                     
[478]862                                leaf->mVssRays.push_back((*it).mRay);
[639]863                        }
[478]864                }
[612]865
[564]866                // should I check here?
[1027]867                if (0 && !mViewCellsManager->CheckValidity(viewCell, 0,
868                        mViewCellsManager->GetMaxPvsSize()))
[547]869                {
870                        viewCell->SetValid(false);
871                        leaf->SetTreeValid(false);
872                        PropagateUpValidity(leaf);
[463]873
[574]874                        ++ mBspStats.invalidLeaves;
[547]875                }
876               
[580]877        viewCell->mLeaf = leaf;
[547]878
879                if (mUseAreaForPvs)
880                        viewCell->SetArea(tData.mProbability);
881                else
882                        viewCell->SetVolume(tData.mProbability);
883
884                leaf->mProbability = tData.mProbability;
885
[1020]886                // finally evaluate stats until this leaf
[1027]887                if (0)
888                        EvaluateLeafStats(tData);               
[463]889        }
[482]890
[473]891        //-- cleanup
[478]892        tData.Clear();
[463]893
[472]894        return newNode;
[463]895}
896
[1027]897
898// subdivide node using a split plane queue
[653]899BspNode *VspBspTree::Subdivide(VspBspSplitQueue &tQueue,
[1233]900                                                           VspBspSubdivisionCandidate &splitCandidate)
[653]901{
902        VspBspTraversalData &tData = splitCandidate.mParentData;
903
904        BspNode *newNode = tData.mNode;
905
[654]906        if (!LocalTerminationCriteriaMet(tData) && !GlobalTerminationCriteriaMet(tData))
[666]907        {       
[653]908                PolygonContainer coincident;
909
910                VspBspTraversalData tFrontData;
911                VspBspTraversalData tBackData;
912
913                //-- continue subdivision
[726]914               
[653]915                // create new interior node and two leaf node
916                const Plane3 splitPlane = splitCandidate.mSplitPlane;
[654]917                               
[653]918                newNode = SubdivideNode(splitPlane, tData, tFrontData, tBackData, coincident);
[666]919       
[660]920                const int splitAxis = splitCandidate.mSplitAxis;
921                const int maxCostMisses = splitCandidate.mMaxCostMisses;
922
[654]923                if (splitAxis < 3)
924                        ++ mBspStats.splits[splitAxis];
925                else
926                        ++ mBspStats.polySplits;
[653]927
[710]928                tFrontData.mIsKdNode = tBackData.mIsKdNode = (tData.mIsKdNode && (splitAxis < 3));
[726]929                tFrontData.mAxis = tBackData.mAxis = splitAxis;
930
[654]931                // how often was max cost ratio missed in this branch?
932                tFrontData.mMaxCostMisses = maxCostMisses;
933                tBackData.mMaxCostMisses = maxCostMisses;
[664]934                       
[1020]935                // statistics
[653]936                if (1)
937                {
938                        float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
939                        float cBack = (float)tBackData.mPvs * tBackData.mProbability;
[675]940                        float cData = (float)tData.mPvs * tData.mProbability;
[653]941
[675]942                       
[653]943                        float costDecr =
944                                (cFront + cBack - cData) / mBox.GetVolume();
945
946                        mTotalCost += costDecr;
947                        mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
948
[1020]949                        AddSubdivisionStats(mBspStats.Leaves(),
950                                                                -costDecr, 
951                                                                splitCandidate.GetPriority(),
952                                                                mTotalCost,
953                                                                (float)mTotalPvsSize / (float)mBspStats.Leaves());
[653]954                }
955
[666]956       
[653]957                //-- push the new split candidates on the stack
[1233]958                VspBspSubdivisionCandidate frontCandidate;
[1145]959                frontCandidate.mParentData = tFrontData;
960
[1233]961                VspBspSubdivisionCandidate backCandidate;
[1145]962                backCandidate.mParentData = tBackData;
[653]963
[1233]964                EvalSubdivisionCandidate(frontCandidate);
965                EvalSubdivisionCandidate(backCandidate);
[654]966       
[653]967                tQueue.push(frontCandidate);
968                tQueue.push(backCandidate);
[666]969       
[653]970                // delete old leaf node
971                DEL_PTR(tData.mNode);
972        }
973
[654]974
[653]975        //-- terminate traversal and create new view cell
976        if (newNode->IsLeaf())
977        {
978                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
[1020]979
[653]980                BspViewCell *viewCell = new BspViewCell();
[710]981        leaf->SetViewCell(viewCell);
[653]982               
983                //-- update pvs
984                int conSamp = 0;
985                float sampCon = 0.0f;
986                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
987
[1002]988                // update scalar pvs size value
[1160]989                ObjectPvs &pvs = viewCell->GetPvs();
[1168]990                mViewCellsManager->UpdateScalarPvsSize(viewCell, pvs.CountObjectsInPvs(), pvs.GetSize());
[752]991
[653]992                mBspStats.contributingSamples += conSamp;
993                mBspStats.sampleContributions +=(int) sampCon;
994
995                //-- store additional info
996                if (mStoreRays)
997                {
998                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
999                        for (it = tData.mRays->begin(); it != it_end; ++ it)
1000                        {
1001                                (*it).mRay->Ref();                     
1002                                leaf->mVssRays.push_back((*it).mRay);
1003                        }
1004                }
1005
[1020]1006               
[653]1007                viewCell->mLeaf = leaf;
1008
1009                if (mUseAreaForPvs)
1010                        viewCell->SetArea(tData.mProbability);
1011                else
1012                        viewCell->SetVolume(tData.mProbability);
1013
[675]1014        leaf->mProbability = tData.mProbability;
[653]1015
[1020]1016                // finally evaluate stats until this leaf
[1027]1017                if (0)
1018                        EvaluateLeafStats(tData);               
[653]1019        }
1020
1021        //-- cleanup
1022        tData.Clear();
1023
1024        return newNode;
1025}
1026
1027
[664]1028void VspBspTree::EvalPriority(VspBspTraversalData &tData) const
1029{
[735]1030    switch (mNodePriorityQueueType)
1031        {
1032        case BREATH_FIRST:
[734]1033                tData.mPriority = (float)-tData.mDepth;
[735]1034                break;
1035        case DEPTH_FIRST:
[734]1036                tData.mPriority = (float)tData.mDepth;
[735]1037                break;
1038        default:
[734]1039                tData.mPriority = tData.mPvs * tData.mProbability;
[735]1040                //Debug << "priority: " << tData.mPriority << endl;
1041                break;
1042        }
[664]1043}
1044
1045
[1233]1046void VspBspTree::EvalSubdivisionCandidate(VspBspSubdivisionCandidate &splitCandidate)
[1145]1047{
1048        VspBspTraversalData frontData;
1049        VspBspTraversalData backData;
1050       
1051        BspLeaf *leaf = dynamic_cast<BspLeaf *>(splitCandidate.mParentData.mNode);
1052       
1053        // compute locally best split plane
[1288]1054    const bool costRatioViolated =
1055                SelectPlane(splitCandidate.mSplitPlane,
1056                                        leaf,
1057                                        splitCandidate.mParentData,
1058                                        frontData,
1059                                        backData,
1060                                        splitCandidate.mSplitAxis);
[652]1061
[1288]1062        // max cost threshold violated?
1063        splitCandidate.mMaxCostMisses = costRatioViolated ?
1064                splitCandidate.mParentData.mMaxCostMisses :
1065                splitCandidate.mParentData.mMaxCostMisses + 1;
1066
[1145]1067        float oldRenderCost;
1068
1069        // compute global decrease in render cost
1070        const float renderCostDecr = EvalRenderCostDecrease(splitCandidate.mSplitPlane,
1071                                                                                                                splitCandidate.mParentData,
1072                                                                                                                oldRenderCost);
1073
1074        splitCandidate.mRenderCostDecr = renderCostDecr;
1075
1076        // TODO: geometry could be reused
1077        delete frontData.mGeometry;
1078        delete backData.mGeometry;
1079
1080        // set priority for queue
1081#if 0
1082        const float priority = (float)-data.mDepth;
1083#else   
1084
1085        // take render cost of node into account
1086        // otherwise danger of being stuck in a local minimum!!
1087        const float factor = mRenderCostDecreaseWeight;
1088        const float priority = factor * renderCostDecr + (1.0f - factor) * oldRenderCost;
1089#endif
1090       
1091        splitCandidate.mPriority = priority;
1092}
1093
1094
1095void VspBspTree::EvalSubdivisionStats(const VspBspTraversalData &tData,
1096                                                                          const VspBspTraversalData &tFrontData,
1097                                                                          const VspBspTraversalData &tBackData)
1098{
1099        const float cFront = (float)tFrontData.mPvs * tFrontData.mProbability;
1100        const float cBack = (float)tBackData.mPvs * tBackData.mProbability;
1101        const float cData = (float)tData.mPvs * tData.mProbability;
1102       
1103        const float costDecr =
1104                (cFront + cBack - cData) / mBox.GetVolume();
1105
1106        mTotalCost += costDecr;
1107        mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
1108
1109        AddSubdivisionStats(mBspStats.Leaves(),
1110                                                -costDecr,
1111                                                0,
1112                                                mTotalCost,
1113                                                (float)mTotalPvsSize / (float)mBspStats.Leaves());
1114}
1115
1116
[653]1117BspInterior *VspBspTree::SubdivideNode(const Plane3 &splitPlane,
1118                                                                           VspBspTraversalData &tData,
1119                                                                           VspBspTraversalData &frontData,
1120                                                                           VspBspTraversalData &backData,
1121                                                                           PolygonContainer &coincident)
[463]1122{
1123        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
[508]1124       
[473]1125        //-- the front and back traversal data is filled with the new values
1126        frontData.mDepth = tData.mDepth + 1;
[508]1127        frontData.mPolygons = new PolygonContainer();
[473]1128        frontData.mRays = new RayInfoContainer();
[508]1129       
[473]1130        backData.mDepth = tData.mDepth + 1;
[508]1131        backData.mPolygons = new PolygonContainer();
[473]1132        backData.mRays = new RayInfoContainer();
[508]1133       
[653]1134
1135        //-- subdivide rays
[652]1136        SplitRays(splitPlane,
[482]1137                          *tData.mRays,
1138                          *frontData.mRays,
[463]1139                          *backData.mRays);
[482]1140
[463]1141
[472]1142        // compute pvs
[463]1143        frontData.mPvs = ComputePvsSize(*frontData.mRays);
1144        backData.mPvs = ComputePvsSize(*backData.mRays);
1145
[508]1146        // split front and back node geometry and compute area
[547]1147       
1148        // if geometry was not already computed
[602]1149        if (!frontData.mGeometry && !backData.mGeometry)
[463]1150        {
[547]1151                frontData.mGeometry = new BspNodeGeometry();
1152                backData.mGeometry = new BspNodeGeometry();
[482]1153
[547]1154                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
1155                                                                           *backData.mGeometry,
[652]1156                                                                           splitPlane,
[547]1157                                                                           mBox,
[679]1158                                                                           //0.0f);
1159                                                                           mEpsilon);
[508]1160               
[547]1161                if (mUseAreaForPvs)
1162                {
1163                        frontData.mProbability = frontData.mGeometry->GetArea();
1164                        backData.mProbability = backData.mGeometry->GetArea();
[508]1165                }
[547]1166                else
1167                {
1168                        frontData.mProbability = frontData.mGeometry->GetVolume();
[654]1169                        backData.mProbability = tData.mProbability - frontData.mProbability;
[676]1170
[744]1171                        // should never come here: wrong volume !!!
[676]1172                        if (0)
1173                        {
[744]1174                                if (frontData.mProbability < -0.00001)
1175                                        Debug << "fatal error f: " << frontData.mProbability << endl;
1176                                if (backData.mProbability < -0.00001)
1177                                        Debug << "fatal error b: " << backData.mProbability << endl;
1178
1179                                // clamp because of precision issues
[676]1180                                if (frontData.mProbability < 0) frontData.mProbability = 0;
1181                                if (backData.mProbability < 0) backData.mProbability = 0;
1182                        }
[547]1183                }
[463]1184        }
[663]1185
[547]1186       
[652]1187    // subdivide polygons
1188        SplitPolygons(splitPlane,
1189                                  *tData.mPolygons,
1190                      *frontData.mPolygons,
1191                                  *backData.mPolygons,
1192                                  coincident);
[463]1193
[652]1194
1195
[653]1196        ///////////////////////////////////////
1197        // subdivide further
[652]1198
[711]1199        // store maximal and minimal depth
1200        if (tData.mDepth > mBspStats.maxDepth)
1201        {
1202                Debug << "max depth increases to " << tData.mDepth << " at " << mBspStats.Leaves() << " leaves" << endl;
1203                mBspStats.maxDepth = tData.mDepth;
1204        }
1205
[652]1206        mBspStats.nodes += 2;
1207
[711]1208   
[652]1209        BspInterior *interior = new BspInterior(splitPlane);
1210
1211#ifdef _DEBUG
1212        Debug << interior << endl;
1213#endif
1214
[711]1215
[463]1216        //-- create front and back leaf
1217
1218        BspInterior *parent = leaf->GetParent();
1219
1220        // replace a link from node's parent
[487]1221        if (parent)
[463]1222        {
1223                parent->ReplaceChildLink(leaf, interior);
1224                interior->SetParent(parent);
1225        }
1226        else // new root
1227        {
1228                mRoot = interior;
1229        }
1230
1231        // and setup child links
1232        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
[482]1233
[463]1234        frontData.mNode = interior->GetFront();
1235        backData.mNode = interior->GetBack();
[473]1236
[650]1237        interior->mTimeStamp = mTimeStamp ++;
[652]1238       
[711]1239
[463]1240        //DEL_PTR(leaf);
1241        return interior;
1242}
1243
[508]1244
[463]1245void VspBspTree::AddToPvs(BspLeaf *leaf,
[482]1246                                                  const RayInfoContainer &rays,
[556]1247                                                  float &sampleContributions,
[463]1248                                                  int &contributingSamples)
1249{
[1002]1250        sampleContributions = 0;
1251        contributingSamples = 0;
[556]1252 
[1002]1253        RayInfoContainer::const_iterator it, it_end = rays.end();
[556]1254 
[1002]1255        ViewCellLeaf *vc = leaf->GetViewCell();
[556]1256 
[1002]1257        // add contributions from samples to the PVS
1258        for (it = rays.begin(); it != it_end; ++ it)
[463]1259        {
[1002]1260                float sc = 0.0f;
1261                VssRay *ray = (*it).mRay;
1262
1263                bool madeContrib = false;
1264                float contribution;
1265
1266                if (ray->mTerminationObject)
1267                {
1268                        if (vc->AddPvsSample(ray->mTerminationObject, ray->mPdf, contribution))
1269                                madeContrib = true;
1270                        sc += contribution;
1271                }
[556]1272         
[1006]1273                // only count termination objects?
[1020]1274                if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject)
[1002]1275                {
1276                        if (vc->AddPvsSample(ray->mOriginObject, ray->mPdf, contribution))
1277                                madeContrib = true;
[1020]1278
[1002]1279                        sc += contribution;
1280                }
[556]1281               
[1047]1282                sampleContributions += sc;
1283               
1284                if (madeContrib)
1285                        ++ contributingSamples;
[463]1286        }
1287}
1288
[580]1289
[1233]1290void VspBspTree::SortSubdivisionCandidates(const RayInfoContainer &rays,
[710]1291                                                                         const int axis,
1292                                                                         float minBand,
1293                                                                         float maxBand)
[463]1294{
[1233]1295        mLocalSubdivisionCandidates->clear();
[463]1296
[480]1297        int requestedSize = 2 * (int)(rays.size());
1298        // creates a sorted split candidates array
[1233]1299        if (mLocalSubdivisionCandidates->capacity() > 500000 &&
1300                requestedSize < (int)(mLocalSubdivisionCandidates->capacity() / 10) )
[480]1301        {
[1233]1302        delete mLocalSubdivisionCandidates;
1303                mLocalSubdivisionCandidates = new vector<SortableEntry>;
[480]1304        }
[463]1305
[1233]1306        mLocalSubdivisionCandidates->reserve(requestedSize);
[480]1307
[710]1308        if (0)
[1137]1309        {       // float values => don't compare with exact values
[710]1310                minBand += Limits::Small;
1311                maxBand -= Limits::Small;
1312        }
1313
[480]1314        // insert all queries
[612]1315        for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
[473]1316        {
[612]1317                const bool positive = (*ri).mRay->HasPosDir(axis);
[1137]1318                float pos = (*ri).ExtrapOrigin(axis);
1319
[710]1320                // clamp to min / max band
1321                if (0) ClipValue(pos, minBand, maxBand);
1322               
[1233]1323                mLocalSubdivisionCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
[810]1324                                                                        pos, (*ri).mRay));
[480]1325
[710]1326                pos = (*ri).ExtrapTermination(axis);
[1137]1327
[710]1328                // clamp to min / max band
1329                if (0) ClipValue(pos, minBand, maxBand);
1330
[1233]1331                mLocalSubdivisionCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
[810]1332                                                                        pos, (*ri).mRay));
[473]1333        }
[480]1334
[1233]1335        stable_sort(mLocalSubdivisionCandidates->begin(), mLocalSubdivisionCandidates->end());
[463]1336}
1337
[580]1338
[480]1339float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
1340                                                                                  const AxisAlignedBox3 &box,
1341                                                                                  const int pvsSize,
[710]1342                                                                                  const int axis,
[480]1343                                          float &position)
[463]1344{
[1149]1345        RayInfoContainer usedRays;
[1147]1346
[1149]1347        if (mMaxTests < rays.size())
[1147]1348        {
[1149]1349                GetRayInfoSets(rays, mMaxTests, usedRays);
[1147]1350        }
1351        else
[1149]1352        {
[1147]1353                usedRays = rays;
[1149]1354        }
[1147]1355
[710]1356        const float minBox = box.Min(axis);
1357        const float maxBox = box.Max(axis);
[822]1358
[710]1359        const float sizeBox = maxBox - minBox;
[480]1360
[801]1361        const float minBand = minBox + mMinBand * sizeBox;
1362        const float maxBand = minBox + mMaxBand * sizeBox;
[710]1363
[1233]1364        SortSubdivisionCandidates(usedRays, axis, minBand, maxBand);
[710]1365
[463]1366        // go through the lists, count the number of objects left and right
1367        // and evaluate the following cost funcion:
[480]1368        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
1369
[810]1370        int pvsl = 0;
1371        int pvsr = pvsSize;
[480]1372
[612]1373        int pvsBack = pvsl;
1374        int pvsFront = pvsr;
1375
1376        float sum = (float)pvsSize * sizeBox;
[463]1377        float minSum = 1e20f;
1378
[822]1379       
[710]1380        // if no border can be found, take mid split
1381        position = minBox + 0.5f * sizeBox;
[822]1382       
1383        // the relative cost ratio
[1074]1384        float ratio = 99999999.0f;
[822]1385        bool splitPlaneFound = false;
[710]1386
[480]1387        Intersectable::NewMail();
1388
[1147]1389        RayInfoContainer::const_iterator ri, ri_end = usedRays.end();
[612]1390
1391        // set all object as belonging to the front pvs
[1149]1392        for(ri = usedRays.begin(); ri != ri_end; ++ ri)
[463]1393        {
[612]1394                Intersectable *oObject = (*ri).mRay->mOriginObject;
1395                Intersectable *tObject = (*ri).mRay->mTerminationObject;
1396
[1020]1397                if (COUNT_ORIGIN_OBJECTS && oObject)
[463]1398                {
[612]1399                        if (!oObject->Mailed())
[482]1400                        {
[612]1401                                oObject->Mail();
1402                                oObject->mCounter = 1;
[482]1403                        }
[612]1404                        else
1405                        {
1406                                ++ oObject->mCounter;
1407                        }
[463]1408                }
[1020]1409
[612]1410                if (tObject)
1411                {
1412                        if (!tObject->Mailed())
1413                        {
1414                                tObject->Mail();
1415                                tObject->mCounter = 1;
1416                        }
1417                        else
1418                        {
1419                                ++ tObject->mCounter;
1420                        }
1421                }
[480]1422        }
1423
1424        Intersectable::NewMail();
1425
[1233]1426        vector<SortableEntry>::const_iterator ci, ci_end = mLocalSubdivisionCandidates->end();
[612]1427
[1233]1428        for (ci = mLocalSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
[480]1429        {
1430                VssRay *ray;
[612]1431                ray = (*ci).ray;
1432               
1433                Intersectable *oObject = ray->mOriginObject;
1434                Intersectable *tObject = ray->mTerminationObject;
1435               
[480]1436
1437                switch ((*ci).type)
[463]1438                {
[480]1439                        case SortableEntry::ERayMin:
1440                                {
[1020]1441                                        if (COUNT_ORIGIN_OBJECTS && oObject && !oObject->Mailed())
[480]1442                                        {
[612]1443                                                oObject->Mail();
1444                                                ++ pvsl;
[480]1445                                        }
[1020]1446
[612]1447                                        if (tObject && !tObject->Mailed())
1448                                        {
1449                                                tObject->Mail();
1450                                                ++ pvsl;
1451                                        }
[1020]1452
[480]1453                                        break;
1454                                }
1455                        case SortableEntry::ERayMax:
1456                                {
[1020]1457                                        if (COUNT_ORIGIN_OBJECTS && oObject)
[612]1458                                        {
1459                                                if (-- oObject->mCounter == 0)
1460                                                        -- pvsr;
1461                                        }
[463]1462
[612]1463                                        if (tObject)
[480]1464                                        {
[612]1465                                                if (-- tObject->mCounter == 0)
1466                                                        -- pvsr;
[480]1467                                        }
1468
1469                                        break;
1470                                }
1471                }
[822]1472               
1473               
[1020]1474                // Note: we compare size of bounding boxes of front and back side because
1475                // of efficiency reasons (otherwise a new geometry would have to be computed
1476                // in each step and incremential evaluation would be difficult.
1477                // but then errors happen if the geometry is not an axis aligned box
1478                // (i.e., if a geometry aligned split was taken before)
1479                // question: is it sufficient to make this approximation?
[710]1480                if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
[480]1481                {
[612]1482                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
[480]1483
[1147]1484                        float currentPos;
1485                       
1486                        // HACK: current positition is BETWEEN visibility events
[1149]1487                        if (0 && ((ci + 1) != ci_end))
1488                        {
[1147]1489                                currentPos = ((*ci).value + (*(ci + 1)).value) * 0.5f;
[1149]1490                        }
[1147]1491                        else
[1149]1492                currentPos = (*ci).value;                       
[1147]1493
[822]1494                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
1495                        //Debug << "cost= " << sum << endl;
[480]1496
1497                        if (sum < minSum)
[463]1498                        {
[822]1499                                splitPlaneFound = true;
1500
[463]1501                                minSum = sum;
[1147]1502                                position = currentPos;
[710]1503                               
[612]1504                                pvsBack = pvsl;
1505                                pvsFront = pvsr;
[463]1506                        }
1507                }
1508        }
[710]1509       
[612]1510        // -- compute cost
1511        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
1512        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
1513
1514        const float pOverall = sizeBox;
1515
1516        const float pBack = position - minBox;
1517        const float pFront = maxBox - position;
1518       
1519        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
1520    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
1521        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
1522       
1523        const float oldRenderCost = penaltyOld * pOverall;
1524        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
1525
[822]1526        if (splitPlaneFound)
1527        {
1528                ratio = mPvsFactor * newRenderCost / (oldRenderCost + Limits::Small);
1529        }
1530        //if (axis != 1)
1531        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
1532         //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
[612]1533
[480]1534        return ratio;
[463]1535}
1536
[480]1537
[482]1538float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
[491]1539                                                                                 const VspBspTraversalData &tData,
[495]1540                                                                                 int &axis,
[508]1541                                                                                 BspNodeGeometry **frontGeom,
1542                                                                                 BspNodeGeometry **backGeom,
[547]1543                                                                                 float &pFront,
1544                                                                                 float &pBack,
[710]1545                                                                                 const bool isKdNode)
[463]1546{
[508]1547        float nPosition[3];
1548        float nCostRatio[3];
[547]1549        float nProbFront[3];
1550        float nProbBack[3];
[508]1551
1552        BspNodeGeometry *nFrontGeom[3];
1553        BspNodeGeometry *nBackGeom[3];
1554
[822]1555        // set to NULL, so I can find out which gemetry was stored
[612]1556        for (int i = 0; i < 3; ++ i)
1557        {
1558                nFrontGeom[i] = NULL;
1559                nBackGeom[i] = NULL;
1560        }
1561
[545]1562        // create bounding box of node geometry
[463]1563        AxisAlignedBox3 box;
[710]1564               
[562]1565        //TODO: for kd split geometry already is box => only take minmax vertices
[551]1566        if (1)
[1147]1567        {       // get bounding box from geometry
[710]1568                tData.mGeometry->GetBoundingBox(box);
[509]1569        }
1570        else
1571        {
[710]1572                box.Initialize();
[509]1573                RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
[480]1574
[509]1575                for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
1576                        box.Include((*ri).ExtrapTermination());
1577        }
[663]1578
[1147]1579
[663]1580        int sAxis = 0;
[822]1581        int bestAxis;
1582
[837]1583        // if max cost ratio is exceeded, take split along longest axis instead
1584        const float maxCostRatioForArbitraryAxis = 0.9f;
1585
[1006]1586        if (mUseDrivingAxisIfMaxCostViolated)
[822]1587                bestAxis = box.Size().DrivingAxis();
1588        else
1589                bestAxis = -1;
1590
[978]1591#if 0
1592        // maximum cost ratio for axis to be valid:
[822]1593        // if exceeded, spatial mid split is used instead
[978]1594        const maxCostRatioForHeur = 0.99f;
1595#endif
[822]1596
[978]1597        // if we use some kind of specialised fixed axis
[837]1598    const bool useSpecialAxis =
1599                mOnlyDrivingAxis || mUseRandomAxis || mCirculatingAxis;
[663]1600
[801]1601        if (mUseRandomAxis)
[663]1602                sAxis = Random(3);
[801]1603        else if (mCirculatingAxis)
[726]1604                sAxis = (tData.mAxis + 1) % 3;
[822]1605        else if (mOnlyDrivingAxis)
[801]1606                sAxis = box.Size().DrivingAxis();
1607
[664]1608               
[670]1609        //Debug << "use special axis: " << useSpecialAxis << endl;
1610        //Debug << "axis: " << sAxis << " drivingaxis: " << box.Size().DrivingAxis();
[1076]1611       
[822]1612        for (axis = 0; axis < 3 ; ++ axis)
[480]1613        {
[663]1614                if (!useSpecialAxis || (axis == sAxis))
[463]1615                {
[822]1616                        if (mUseCostHeuristics)
[480]1617                        {
[1106]1618                                //-- place split plane using heuristics
[822]1619                                nCostRatio[axis] =
1620                                        BestCostRatioHeuristics(*tData.mRays,
1621                                                                                    box,
1622                                                                                        tData.mPvs,
1623                                                                                        axis,
1624                                                                                        nPosition[axis]);                       
1625                        }
[1106]1626                        else
[1147]1627                        {       //-- split plane position is spatial median
[822]1628
[480]1629                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
[543]1630                                Vector3 normal(0,0,0); normal[axis] = 1.0f;
[1076]1631                               
[547]1632                                // allows faster split because we have axis aligned kd tree boxes
[822]1633                                if (isKdNode)
[542]1634                                {
1635                                        nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
1636                                                                                                                                box,
1637                                                                                                                                axis,
[547]1638                                                                                                                                nPosition[axis],
1639                                                                                                                                nProbFront[axis],
1640                                                                                                                                nProbBack[axis]);
[542]1641                                       
[543]1642                                        Vector3 pos;
[542]1643                                       
[710]1644                                        // create back geometry from box
[1047]1645                                        // NOTE: the geometry is returned from the function so we
1646                                        // don't have to recompute it when possible
[543]1647                                        pos = box.Max(); pos[axis] = nPosition[axis];
[547]1648                                        AxisAlignedBox3 bBox(box.Min(), pos);
[710]1649                                        PolygonContainer fPolys;
1650                                        bBox.ExtractPolys(fPolys);
1651
1652                                        nBackGeom[axis] = new BspNodeGeometry(fPolys);
1653       
[822]1654                                        //-- create front geometry from box
[542]1655                                        pos = box.Min(); pos[axis] = nPosition[axis];
[547]1656                                        AxisAlignedBox3 fBox(pos, box.Max());
[710]1657
1658                                        PolygonContainer bPolys;
1659                                        fBox.ExtractPolys(bPolys);
1660                                        nFrontGeom[axis] = new BspNodeGeometry(bPolys);
[542]1661                                }
1662                                else
1663                                {
[710]1664                                        nFrontGeom[axis] = new BspNodeGeometry();
1665                                        nBackGeom[axis] = new BspNodeGeometry();
1666
[573]1667                                        nCostRatio[axis] =
1668                                                EvalSplitPlaneCost(Plane3(normal, nPosition[axis]),
1669                                                                                   tData, *nFrontGeom[axis], *nBackGeom[axis],
1670                                                                                   nProbFront[axis], nProbBack[axis]);
[542]1671                                }
[480]1672                        }
[822]1673                                               
[978]1674                       
[1006]1675                        if (mUseDrivingAxisIfMaxCostViolated)
[480]1676                        {
[978]1677                                // we take longest axis split if cost ratio exceeds threshold
1678                                if (nCostRatio[axis] < min(maxCostRatioForArbitraryAxis, nCostRatio[bestAxis]))
[822]1679                                {
1680                                        bestAxis = axis;
1681                                }
[1072]1682                                /*else if (nCostRatio[axis] < nCostRatio[bestAxis])
1683                                {
[978]1684                                        Debug << "taking split along longest axis (" << bestAxis << ") instead of  (" << axis << ")" << endl;
[1072]1685                                }*/
1686
[978]1687                        }
1688                        else
1689                        {
1690                                if (bestAxis == -1)
[822]1691                                {
1692                                        bestAxis = axis;
1693                                }
[978]1694                                else if (nCostRatio[axis] < nCostRatio[bestAxis])
[822]1695                                {
1696                                        bestAxis = axis;
1697                                }
[978]1698                        }
[463]1699                }
1700        }
1701
[495]1702        //-- assign values
[1072]1703
[495]1704        axis = bestAxis;
[547]1705        pFront = nProbFront[bestAxis];
1706        pBack = nProbBack[bestAxis];
[495]1707
[508]1708        // assign best split nodes geometry
1709        *frontGeom = nFrontGeom[bestAxis];
1710        *backGeom = nBackGeom[bestAxis];
[542]1711
[508]1712        // and delete other geometry
[612]1713        DEL_PTR(nFrontGeom[(bestAxis + 1) % 3]);
1714        DEL_PTR(nBackGeom[(bestAxis + 2) % 3]);
[495]1715
[508]1716        //-- split plane
1717    Vector3 normal(0,0,0); normal[bestAxis] = 1;
[480]1718        plane = Plane3(normal, nPosition[bestAxis]);
[508]1719
[822]1720        //Debug << "best axis: " << bestAxis << " pos " << nPosition[bestAxis] << endl;
[1072]1721
[480]1722        return nCostRatio[bestAxis];
[463]1723}
1724
[480]1725
[508]1726bool VspBspTree::SelectPlane(Plane3 &bestPlane,
1727                                                         BspLeaf *leaf,
[652]1728                                                         VspBspTraversalData &data,                                                     
[508]1729                                                         VspBspTraversalData &frontData,
[612]1730                                                         VspBspTraversalData &backData,
1731                                                         int &splitAxis)
[491]1732{
[810]1733        // HACK matt: subdivide regularily to certain depth
[1072]1734        if (data.mDepth < 0)    // question matt: why depth < 0 ?
[801]1735        {
[1072]1736                cout << "depth: " << data.mDepth << endl;
1737
[801]1738                // return axis aligned split
1739                AxisAlignedBox3 box;
1740                box.Initialize();
1741       
1742                // create bounding box of region
1743                data.mGeometry->GetBoundingBox(box);
1744       
1745                const int axis = box.Size().DrivingAxis();
1746                const Vector3 position = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
1747
1748                Vector3 norm(0,0,0); norm[axis] = 1.0f;
1749                bestPlane = Plane3(norm, position);
1750                splitAxis = axis;
[1072]1751
[801]1752                return true;
1753        }
1754
[508]1755        // simplest strategy: just take next polygon
1756        if (mSplitPlaneStrategy & RANDOM_POLYGON)
[491]1757        {
[508]1758        if (!data.mPolygons->empty())
1759                {
1760                        const int randIdx =
1761                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
1762                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
[491]1763
[508]1764                        bestPlane = nextPoly->GetSupportingPlane();
1765                        return true;
1766                }
[491]1767        }
1768
[508]1769        //-- use heuristics to find appropriate plane
[491]1770
[508]1771        // intermediate plane
1772        Plane3 plane;
1773        float lowestCost = MAX_FLOAT;
[517]1774       
1775        // decides if the first few splits should be only axisAligned
[508]1776        const bool onlyAxisAligned  =
1777                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
1778                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1779                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
1780       
1781        const int limit = onlyAxisAligned ? 0 :
1782                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
[491]1783
[508]1784        float candidateCost;
[491]1785
[508]1786        int maxIdx = (int)data.mPolygons->size();
[491]1787
[508]1788        for (int i = 0; i < limit; ++ i)
[491]1789        {
[562]1790                // the already taken candidates are stored behind maxIdx
1791                // => assure that no index is taken twice
[508]1792                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
1793                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
[491]1794
[508]1795                // swap candidate to the end to avoid testing same plane
1796                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
1797                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
[491]1798
[508]1799                // evaluate current candidate
1800                BspNodeGeometry fGeom, bGeom;
1801                float fArea, bArea;
1802                plane = poly->GetSupportingPlane();
[573]1803                candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
[491]1804               
[508]1805                if (candidateCost < lowestCost)
[491]1806                {
[508]1807                        bestPlane = plane;
1808                        lowestCost = candidateCost;
[491]1809                }
1810        }
1811
[1006]1812
[508]1813        //-- evaluate axis aligned splits
[1006]1814       
[508]1815        int axis;
1816        BspNodeGeometry *fGeom, *bGeom;
[547]1817        float pFront, pBack;
[491]1818
[653]1819        candidateCost = 99999999.0f;
[491]1820
[1006]1821        // as a variant, we take axis aligned split only if there is
1822        // more polygon available to guide the split
[653]1823        if (!mUsePolygonSplitIfAvailable || data.mPolygons->empty())
1824        {
1825                candidateCost = SelectAxisAlignedPlane(plane,
1826                                                                                           data,
1827                                                                                           axis,
1828                                                                                           &fGeom,
1829                                                                                           &bGeom,
1830                                                                                           pFront,
1831                                                                                           pBack,
1832                                                                                           data.mIsKdNode);     
1833        }
1834
[612]1835        splitAxis = 3;
[562]1836
[508]1837        if (candidateCost < lowestCost)
1838        {       
1839                bestPlane = plane;
1840                lowestCost = candidateCost;
[612]1841                splitAxis = axis;
[653]1842       
[542]1843                // assign already computed values
1844                // we can do this because we always save the
[562]1845                // computed values from the axis aligned splits         
[653]1846
[612]1847                if (fGeom && bGeom)
1848                {
1849                        frontData.mGeometry = fGeom;
1850                        backData.mGeometry = bGeom;
[547]1851       
[612]1852                        frontData.mProbability = pFront;
1853                        backData.mProbability = pBack;
1854                }
[508]1855        }
1856        else
[463]1857        {
[508]1858                DEL_PTR(fGeom);
1859                DEL_PTR(bGeom);
[463]1860        }
[678]1861   
[679]1862#ifdef _DEBUG
[508]1863        Debug << "plane lowest cost: " << lowestCost << endl;
[679]1864#endif
[508]1865
[801]1866        // exeeded relative max cost ratio
[508]1867        if (lowestCost > mTermMaxCostRatio)
[611]1868        {
[508]1869                return false;
[611]1870        }
[508]1871
1872        return true;
[463]1873}
1874
[480]1875
[473]1876Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
[482]1877{
[473]1878        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
[482]1879
[473]1880        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
1881        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
1882
1883        const Vector3 pt = (maxPt + minPt) * 0.5;
1884        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
1885
1886        return Plane3(normal, pt);
1887}
1888
[480]1889
[473]1890Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
[482]1891{
[473]1892        Vector3 pt[3];
[482]1893
[473]1894        int idx[3];
1895        int cmaxT = 0;
1896        int cminT = 0;
1897        bool chooseMin = false;
1898
1899        for (int j = 0; j < 3; ++ j)
1900        {
1901                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
[482]1902
[473]1903                if (idx[j] >= (int)rays.size())
1904                {
1905                        idx[j] -= (int)rays.size();
[482]1906
[473]1907                        chooseMin = (cminT < 2);
1908                }
1909                else
1910                        chooseMin = (cmaxT < 2);
1911
1912                RayInfo rayInf = rays[idx[j]];
1913                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
[482]1914        }
[473]1915
1916        return Plane3(pt[0], pt[1], pt[2]);
1917}
1918
[580]1919
[473]1920Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
[482]1921{
[473]1922        Vector3 pt[3];
[482]1923
[473]1924        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1925        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1926
1927        // check if rays different
1928        if (idx1 == idx2)
1929                idx2 = (idx2 + 1) % (int)rays.size();
1930
1931        const RayInfo ray1 = rays[idx1];
1932        const RayInfo ray2 = rays[idx2];
1933
1934        // normal vector of the plane parallel to both lines
1935        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
1936
1937        // vector from line 1 to line 2
[479]1938        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
[482]1939
[473]1940        // project vector on normal to get distance
1941        const float dist = DotProd(vd, norm);
1942
1943        // point on plane lies halfway between the two planes
1944        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
1945
1946        return Plane3(norm, planePt);
1947}
1948
[495]1949
[463]1950inline void VspBspTree::GenerateUniqueIdsForPvs()
1951{
[580]1952        Intersectable::NewMail(); sBackId = Intersectable::sMailId;
1953        Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
1954        Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
[463]1955}
1956
[495]1957
[652]1958float VspBspTree::EvalRenderCostDecrease(const Plane3 &candidatePlane,
[1145]1959                                                                                 const VspBspTraversalData &data,
1960                                                                                 float &normalizedOldRenderCost) const
[652]1961{
[729]1962        float pvsFront = 0;
1963        float pvsBack = 0;
1964        float totalPvs = 0;
[652]1965
1966        // probability that view point lies in back / front node
1967        float pOverall = data.mProbability;
1968        float pFront = 0;
1969        float pBack = 0;
1970
1971
1972        // create unique ids for pvs heuristics
1973        GenerateUniqueIdsForPvs();
1974       
1975        for (int i = 0; i < data.mRays->size(); ++ i)
1976        {
1977                RayInfo rayInf = (*data.mRays)[i];
1978
1979                float t;
1980                VssRay *ray = rayInf.mRay;
1981                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1982
1983                // find front and back pvs for origing and termination object
1984                AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
[1020]1985
1986                if (COUNT_ORIGIN_OBJECTS)
1987                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
[652]1988        }
1989
1990
1991        BspNodeGeometry geomFront;
1992        BspNodeGeometry geomBack;
1993
1994        // construct child geometry with regard to the candidate split plane
1995        data.mGeometry->SplitGeometry(geomFront,
1996                                                                  geomBack,
1997                                                                  candidatePlane,
1998                                                                  mBox,
[679]1999                                                                  //0.0f);
2000                                                                  mEpsilon);
[652]2001
2002        if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
2003        {
2004                pFront = geomFront.GetVolume();
2005                pBack = pOverall - pFront;
[675]2006
[729]2007                // something is wrong with the volume
[1027]2008                if (0 && ((pFront < 0.0) || (pBack < 0.0)))
[676]2009                {
[752]2010                        Debug << "ERROR in volume:\n"
2011                                  << "volume f :" << pFront << " b: " << pBack << " p: " << pOverall
2012                                  << ", real volume f: " << pFront << " b: " << geomBack.GetVolume()
2013                                  << ", #polygons f: " << geomFront.Size() << " b: " << geomBack.Size() << " p: " << data.mGeometry->Size() << endl;
[676]2014                }
[652]2015        }
2016        else
2017        {
2018                pFront = geomFront.GetArea();
2019                pBack = geomBack.GetArea();
2020        }
2021       
2022
2023        // -- pvs rendering heuristics
[1020]2024
2025        // upper and lower bounds
[652]2026        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
2027        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
2028
[1020]2029        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
2030    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
2031        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[652]2032                       
2033        const float oldRenderCost = pOverall * penaltyOld;
2034        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
2035
[752]2036        const float renderCostDecrease = (oldRenderCost - newRenderCost) / mBox.GetVolume();
2037       
[1006]2038        // take render cost of node into account to avoid being stuck in a local minimum
[1145]2039        normalizedOldRenderCost = oldRenderCost / mBox.GetVolume();
[1006]2040       
[1145]2041        return renderCostDecrease;
[652]2042}
2043
2044
[573]2045float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
2046                                                                         const VspBspTraversalData &data,
2047                                                                         BspNodeGeometry &geomFront,
2048                                                                         BspNodeGeometry &geomBack,
2049                                                                         float &pFront,
2050                                                                         float &pBack) const
[463]2051{
[729]2052        float totalPvs = 0;
2053        float pvsFront = 0;
2054        float pvsBack = 0;
[652]2055       
[1006]2056        // overall probability is used as normalizer
[463]2057        float pOverall = 0;
[1006]2058
2059        // probability that view point lies in back / front node
[547]2060        pFront = 0;
2061        pBack = 0;
[463]2062
[1020]2063        int numTests; // the number of tests
[508]2064
[1020]2065        // if random samples shold be taken instead of testing all the rays
2066        bool useRand;
[463]2067
2068        if ((int)data.mRays->size() > mMaxTests)
2069        {
2070                useRand = true;
[1020]2071                numTests = mMaxTests;
[463]2072        }
2073        else
2074        {
2075                useRand = false;
[1020]2076                numTests = (int)data.mRays->size();
[463]2077        }
[508]2078       
[1020]2079        // create unique ids for pvs heuristics
2080        GenerateUniqueIdsForPvs();
2081
2082        for (int i = 0; i < numTests; ++ i)
[463]2083        {
[508]2084                const int testIdx = useRand ?
2085                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
[463]2086                RayInfo rayInf = (*data.mRays)[testIdx];
2087
2088                float t;
[508]2089                VssRay *ray = rayInf.mRay;
[463]2090                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
2091
[652]2092                // find front and back pvs for origing and termination object
2093                AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
[1020]2094
2095                if (COUNT_ORIGIN_OBJECTS)
2096                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
[652]2097        }
[508]2098
[652]2099        // construct child geometry with regard to the candidate split plane
[679]2100        bool splitSuccessFull = data.mGeometry->SplitGeometry(geomFront,
2101                                                                                                                  geomBack,
2102                                                                                                                  candidatePlane,
2103                                                                                                                  mBox,
2104                                                                                                                  //0.0f);
2105                                                                                                                  mEpsilon);
[675]2106
[652]2107        pOverall = data.mProbability;
[463]2108
[652]2109        if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
2110        {
2111                pFront = geomFront.GetVolume();
2112                pBack = pOverall - pFront;
[675]2113               
[729]2114                // HACK: precision issues possible for unbalanced split => don't take this split!
[685]2115                if (1 &&
[682]2116                        (!splitSuccessFull || (pFront <= 0) || (pBack <= 0) ||
2117                        !geomFront.Valid() || !geomBack.Valid()))
[676]2118                {
[752]2119                        //Debug << "error f: " << pFront << " b: " << pBack << endl;
[1027]2120
2121                        // high penalty for degenerated / wrong split
[711]2122                        return 99999.9f;
[676]2123                }
[463]2124        }
[652]2125        else
[542]2126        {
[652]2127                pFront = geomFront.GetArea();
2128                pBack = geomBack.GetArea();
[542]2129        }
[652]2130       
[542]2131
[580]2132        // -- pvs rendering heuristics
[652]2133        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
2134        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
[580]2135
[652]2136        // only render cost heuristics or combined with standard deviation
[752]2137        const float penaltyOld = EvalPvsPenalty((int)totalPvs, lowerPvsLimit, upperPvsLimit);
2138    const float penaltyFront = EvalPvsPenalty((int)pvsFront, lowerPvsLimit, upperPvsLimit);
2139        const float penaltyBack = EvalPvsPenalty((int)pvsBack, lowerPvsLimit, upperPvsLimit);
[579]2140                       
[652]2141        const float oldRenderCost = pOverall * penaltyOld;
2142        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
[579]2143
[652]2144        float oldCost, newCost;
[580]2145
[652]2146        // only render cost
2147        if (1)
2148        {
2149                oldCost = oldRenderCost;
2150                newCost = newRenderCost;
2151        }
2152        else // also considering standard deviation
2153        {
2154                // standard deviation is difference of back and front pvs
2155                const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
[580]2156
[652]2157                const float newDeviation = 0.5f *
2158                        fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
[580]2159
[652]2160                const float oldDeviation = penaltyOld;
[580]2161
[652]2162                newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
2163                oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
2164        }
[580]2165
[1020]2166        const float cost = mPvsFactor * newCost / (oldCost + Limits::Small);
[607]2167               
[463]2168
2169#ifdef _DEBUG
[474]2170        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
[508]2171                  << " frontpvs: " << pvsFront << " pFront: " << pFront
2172                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
[600]2173        Debug << "cost: " << cost << endl;
[463]2174#endif
[482]2175
[652]2176        return cost;
[463]2177}
2178
[508]2179
[697]2180int VspBspTree::ComputeBoxIntersections(const AxisAlignedBox3 &box,
2181                                                                                ViewCellContainer &viewCells) const
2182{
2183        stack<bspNodePair> nodeStack;
2184        BspNodeGeometry *rgeom = new BspNodeGeometry();
2185
2186        ConstructGeometry(mRoot, *rgeom);
2187
2188        nodeStack.push(bspNodePair(mRoot, rgeom));
2189 
2190        ViewCell::NewMail();
2191
2192        while (!nodeStack.empty())
2193        {
2194                BspNode *node = nodeStack.top().first;
2195                BspNodeGeometry *geom = nodeStack.top().second;
2196                nodeStack.pop();
2197
2198                const int side = geom->ComputeIntersection(box);
2199               
2200                switch (side)
2201                {
2202                case -1:
2203                        // node geometry is contained in box
2204                        CollectViewCells(node, true, viewCells, true);
2205                        break;
2206
2207                case 0:
2208                        if (node->IsLeaf())
2209                        {
2210                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2211                       
2212                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2213                                {
2214                                        leaf->GetViewCell()->Mail();
2215                                        viewCells.push_back(leaf->GetViewCell());
2216                                }
2217                        }
2218                        else
2219                        {
2220                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
2221                       
2222                                BspNode *first = interior->GetFront();
2223                                BspNode *second = interior->GetBack();
2224           
2225                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
2226                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
2227
2228                                geom->SplitGeometry(*firstGeom,
2229                                                                        *secondGeom,
2230                                                                        interior->GetPlane(),
2231                                                                        mBox,
2232                                                                        //0.0000001f);
2233                                                                        mEpsilon);
2234
2235                                nodeStack.push(bspNodePair(first, firstGeom));
2236                                nodeStack.push(bspNodePair(second, secondGeom));
2237                        }
2238                       
2239                        break;
2240                default:
2241                        // default: cull
2242                        break;
2243                }
2244               
2245                DEL_PTR(geom);
2246               
2247        }
2248
2249        return (int)viewCells.size();
2250}
2251
2252
[580]2253float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
2254                                                                                   const AxisAlignedBox3 &box,
2255                                                                                   const int axis,
2256                                                                                   const float &position,                                                                                 
2257                                                                                   float &pFront,
2258                                                                                   float &pBack) const
2259{
[729]2260        float pvsTotal = 0;
2261        float pvsFront = 0;
2262        float pvsBack = 0;
[580]2263       
2264        // create unique ids for pvs heuristics
2265        GenerateUniqueIdsForPvs();
2266
2267        const int pvsSize = data.mPvs;
[726]2268
[580]2269        RayInfoContainer::const_iterator rit, rit_end = data.mRays->end();
2270
2271        // this is the main ray classification loop!
2272        for(rit = data.mRays->begin(); rit != rit_end; ++ rit)
2273        {
2274                // determine the side of this ray with respect to the plane
2275                float t;
2276                const int side = (*rit).ComputeRayIntersection(axis, position, t);
2277       
2278                AddObjToPvs((*rit).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
[1020]2279
2280                if (COUNT_ORIGIN_OBJECTS)
2281                        AddObjToPvs((*rit).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
[580]2282        }
2283
[1020]2284
[580]2285        //-- pvs heuristics
2286
[1020]2287        float pOverall = data.mProbability;
[580]2288
[1020]2289        // note: we use a simplified computation assuming that we always do a
2290        // spatial mid split   
2291       
[580]2292        if (!mUseAreaForPvs)
[1020]2293        {   
2294                // volume
[580]2295                pBack = pFront = pOverall * 0.5f;
2296#if 0
2297                // box length substitute for probability
2298                const float minBox = box.Min(axis);
2299                const float maxBox = box.Max(axis);
2300
2301                pBack = position - minBox;
2302                pFront = maxBox - position;
2303                pOverall = maxBox - minBox;
2304#endif
2305        }
2306        else //-- area substitute for probability
2307        {
2308                const int axis2 = (axis + 1) % 3;
2309                const int axis3 = (axis + 2) % 3;
2310
2311                const float faceArea =
2312                        (box.Max(axis2) - box.Min(axis2)) *
2313                        (box.Max(axis3) - box.Min(axis3));
2314
2315                pBack = pFront = pOverall * 0.5f + faceArea;
2316        }
2317
2318#ifdef _DEBUG
[1302]2319        Debug << "axis: " << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
2320        Debug << "p: " << pFront << " " << pBack << " " << pOverall << endl;
[580]2321#endif
2322
2323       
2324        const float newCost = pvsBack * pBack + pvsFront * pFront;
2325        const float oldCost = (float)pvsSize * pOverall + Limits::Small;
2326
2327        return  (mCtDivCi + newCost) / oldCost;
2328}
2329
2330
[1076]2331inline void VspBspTree::AddObjToPvs(Intersectable *obj,
2332                                                                                 const int cf,
2333                                                                                 float &frontPvs,
2334                                                                                 float &backPvs,
2335                                                                                 float &totalPvs) const
[463]2336{
2337        if (!obj)
2338                return;
[1076]2339#if 0
[744]2340        const float renderCost = mViewCellsManager->EvalRenderCost(obj);
[1076]2341#else
2342        const int renderCost = 1;
2343#endif
[654]2344        // new object
[508]2345        if ((obj->mMailbox != sFrontId) &&
2346                (obj->mMailbox != sBackId) &&
2347                (obj->mMailbox != sFrontAndBackId))
2348        {
[744]2349                totalPvs += renderCost;
[508]2350        }
2351
[463]2352        // TODO: does this really belong to no pvs?
2353        //if (cf == Ray::COINCIDENT) return;
2354
2355        // object belongs to both PVS
2356        if (cf >= 0)
2357        {
[482]2358                if ((obj->mMailbox != sFrontId) &&
[463]2359                        (obj->mMailbox != sFrontAndBackId))
2360                {
[744]2361                        frontPvs += renderCost;
[508]2362               
[463]2363                        if (obj->mMailbox == sBackId)
[482]2364                                obj->mMailbox = sFrontAndBackId;
[463]2365                        else
[482]2366                                obj->mMailbox = sFrontId;
[463]2367                }
2368        }
[482]2369
[463]2370        if (cf <= 0)
2371        {
2372                if ((obj->mMailbox != sBackId) &&
2373                        (obj->mMailbox != sFrontAndBackId))
2374                {
[744]2375                        backPvs += renderCost;
[508]2376               
[463]2377                        if (obj->mMailbox == sFrontId)
[482]2378                                obj->mMailbox = sFrontAndBackId;
[463]2379                        else
[482]2380                                obj->mMailbox = sBackId;
[463]2381                }
2382        }
2383}
2384
[491]2385
[503]2386void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
2387                                                           const bool onlyUnmailed,
2388                                                           const int maxPvsSize) const
[463]2389{
2390        stack<BspNode *> nodeStack;
2391        nodeStack.push(mRoot);
[482]2392
2393        while (!nodeStack.empty())
[463]2394        {
2395                BspNode *node = nodeStack.top();
2396                nodeStack.pop();
[489]2397               
[482]2398                if (node->IsLeaf())
[463]2399                {
[490]2400                        // test if this leaf is in valid view space
[503]2401                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2402                        if (leaf->TreeValid() &&
[508]2403                                (!onlyUnmailed || !leaf->Mailed()) &&
[1168]2404                                ((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().CountObjectsInPvs() <= maxPvsSize)))
[490]2405                        {
2406                                leaves.push_back(leaf);
2407                        }
[482]2408                }
2409                else
[463]2410                {
2411                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2412
2413                        nodeStack.push(interior->GetBack());
2414                        nodeStack.push(interior->GetFront());
2415                }
2416        }
2417}
2418
[489]2419
[463]2420AxisAlignedBox3 VspBspTree::GetBoundingBox() const
2421{
2422        return mBox;
2423}
2424
[489]2425
[463]2426BspNode *VspBspTree::GetRoot() const
2427{
2428        return mRoot;
2429}
2430
[489]2431
[463]2432void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
2433{
2434        // the node became a leaf -> evaluate stats for leafs
2435        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
2436
2437
[574]2438        if (data.mPvs > mBspStats.maxPvs)
[711]2439        {
[574]2440                mBspStats.maxPvs = data.mPvs;
[711]2441        }
2442
[656]2443        mBspStats.pvs += data.mPvs;
2444
[574]2445        if (data.mDepth < mBspStats.minDepth)
[711]2446        {
[574]2447                mBspStats.minDepth = data.mDepth;
[711]2448        }
[656]2449       
[463]2450        if (data.mDepth >= mTermMaxDepth)
[711]2451        {
[744]2452        ++ mBspStats.maxDepthNodes;
2453                //Debug << "new max depth: " << mBspStats.maxDepthNodes << endl;
[711]2454        }
[611]2455
[508]2456        // accumulate rays to compute rays /  leaf
[574]2457        mBspStats.accumRays += (int)data.mRays->size();
[463]2458
[437]2459        if (data.mPvs < mTermMinPvs)
[574]2460                ++ mBspStats.minPvsNodes;
[437]2461
2462        if ((int)data.mRays->size() < mTermMinRays)
[574]2463                ++ mBspStats.minRaysNodes;
[437]2464
2465        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
[574]2466                ++ mBspStats.maxRayContribNodes;
[482]2467
[547]2468        if (data.mProbability <= mTermMinProbability)
[574]2469                ++ mBspStats.minProbabilityNodes;
[508]2470       
[474]2471        // accumulate depth to compute average depth
[574]2472        mBspStats.accumDepth += data.mDepth;
[463]2473
[612]2474        ++ mCreatedViewCells;
[656]2475
[463]2476#ifdef _DEBUG
2477        Debug << "BSP stats: "
2478                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
2479                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
[1027]2480                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
[1168]2481                  << "#pvs: " << leaf->GetViewCell()->GetPvs().CountObjectsInPvs() << "), "
[463]2482                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
2483#endif
2484}
2485
[612]2486
[463]2487int VspBspTree::CastRay(Ray &ray)
2488{
2489        int hits = 0;
[482]2490
[600]2491        stack<BspRayTraversalData> tQueue;
[482]2492
[463]2493        float maxt, mint;
2494
2495        if (!mBox.GetRaySegment(ray, mint, maxt))
2496                return 0;
2497
2498        Intersectable::NewMail();
[600]2499        ViewCell::NewMail();
[1012]2500
[463]2501        Vector3 entp = ray.Extrap(mint);
2502        Vector3 extp = ray.Extrap(maxt);
[482]2503
[463]2504        BspNode *node = mRoot;
2505        BspNode *farChild = NULL;
[482]2506
[463]2507        while (1)
2508        {
[482]2509                if (!node->IsLeaf())
[463]2510                {
2511                        BspInterior *in = dynamic_cast<BspInterior *>(node);
2512
2513                        Plane3 splitPlane = in->GetPlane();
2514                        const int entSide = splitPlane.Side(entp);
2515                        const int extSide = splitPlane.Side(extp);
2516
2517                        if (entSide < 0)
2518                        {
2519                                node = in->GetBack();
2520
2521                                if(extSide <= 0) // plane does not split ray => no far child
2522                                        continue;
[482]2523
[463]2524                                farChild = in->GetFront(); // plane splits ray
2525
2526                        } else if (entSide > 0)
2527                        {
2528                                node = in->GetFront();
2529
2530                                if (extSide >= 0) // plane does not split ray => no far child
2531                                        continue;
2532
[482]2533                                farChild = in->GetBack(); // plane splits ray
[463]2534                        }
2535                        else // ray and plane are coincident
2536                        {
[1012]2537                                // matt: WHAT TO DO IN THIS CASE ?
[463]2538                                //break;
2539                                node = in->GetFront();
2540                                continue;
2541                        }
2542
2543                        // push data for far child
[600]2544                        tQueue.push(BspRayTraversalData(farChild, extp, maxt));
[463]2545
2546                        // find intersection of ray segment with plane
2547                        float t;
2548                        extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
2549                        maxt *= t;
[1047]2550                }
2551                else // reached leaf => intersection with view cell
[463]2552                {
2553                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
[482]2554
[463]2555                        if (!leaf->GetViewCell()->Mailed())
2556                        {
2557                                //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
2558                                leaf->GetViewCell()->Mail();
2559                                ++ hits;
2560                        }
[482]2561
[463]2562                        //-- fetch the next far child from the stack
[600]2563                        if (tQueue.empty())
[463]2564                                break;
[482]2565
[463]2566                        entp = extp;
2567                        mint = maxt; // NOTE: need this?
2568
2569                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
2570                                break;
2571
[600]2572                        BspRayTraversalData &s = tQueue.top();
[463]2573
2574                        node = s.mNode;
2575                        extp = s.mExitPoint;
2576                        maxt = s.mMaxT;
2577
[600]2578                        tQueue.pop();
[463]2579                }
2580        }
2581
2582        return hits;
2583}
2584
[532]2585
[1072]2586void VspBspTree::CollectViewCells(ViewCellContainer &viewCells,
2587                                                                  bool onlyValid) const
[463]2588{
[532]2589        ViewCell::NewMail();
[551]2590       
2591        CollectViewCells(mRoot, onlyValid, viewCells, true);
[532]2592}
2593
2594
[574]2595void VspBspTree::CollapseViewCells()
[542]2596{
[590]2597// TODO
[728]2598#if HAS_TO_BE_REDONE
[542]2599        stack<BspNode *> nodeStack;
2600
2601        if (!mRoot)
2602                return;
2603
2604        nodeStack.push(mRoot);
2605       
2606        while (!nodeStack.empty())
2607        {
2608                BspNode *node = nodeStack.top();
2609                nodeStack.pop();
2610               
2611                if (node->IsLeaf())
[574]2612        {
2613                        BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
[542]2614
[574]2615                        if (!viewCell->GetValid())
[542]2616                        {
2617                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
[580]2618       
2619                                ViewCellContainer leaves;
[590]2620                                mViewCellsTree->CollectLeaves(viewCell, leaves);
[580]2621
2622                                ViewCellContainer::const_iterator it, it_end = leaves.end();
2623
2624                                for (it = leaves.begin(); it != it_end; ++ it)
[542]2625                                {
[580]2626                                        BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
[574]2627                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
2628                                        ++ mBspStats.invalidLeaves;
2629                                }
[542]2630
[574]2631                                // add to unbounded view cell
2632                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
2633                                DEL_PTR(viewCell);
2634                        }
2635                }
2636                else
2637                {
2638                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2639               
2640                        nodeStack.push(interior->GetFront());
2641                        nodeStack.push(interior->GetBack());
2642                }
2643        }
[542]2644
[574]2645        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
[590]2646#endif
[574]2647}
2648
2649
[639]2650void VspBspTree::CollectRays(VssRayContainer &rays)
2651{
2652        vector<BspLeaf *> leaves;
2653
2654        vector<BspLeaf *>::const_iterator lit, lit_end = leaves.end();
2655
2656        for (lit = leaves.begin(); lit != lit_end; ++ lit)
2657        {
2658                BspLeaf *leaf = *lit;
2659                VssRayContainer::const_iterator rit, rit_end = leaf->mVssRays.end();
2660
2661                for (rit = leaf->mVssRays.begin(); rit != rit_end; ++ rit)
2662                        rays.push_back(*rit);
2663        }
2664}
2665
2666
[574]2667void VspBspTree::ValidateTree()
2668{
2669        stack<BspNode *> nodeStack;
2670
2671        if (!mRoot)
2672                return;
2673
2674        nodeStack.push(mRoot);
2675       
2676        mBspStats.invalidLeaves = 0;
2677        while (!nodeStack.empty())
2678        {
2679                BspNode *node = nodeStack.top();
2680                nodeStack.pop();
2681               
2682                if (node->IsLeaf())
2683                {
2684                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2685
2686                        if (!leaf->GetViewCell()->GetValid())
2687                                ++ mBspStats.invalidLeaves;
2688
2689                        // validity flags don't match => repair
2690                        if (leaf->GetViewCell()->GetValid() != leaf->TreeValid())
2691                        {
2692                                leaf->SetTreeValid(leaf->GetViewCell()->GetValid());
2693                                PropagateUpValidity(leaf);
[542]2694                        }
2695                }
2696                else
2697                {
2698                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2699               
2700                        nodeStack.push(interior->GetFront());
2701                        nodeStack.push(interior->GetBack());
2702                }
2703        }
[562]2704
[574]2705        Debug << "invalid leaves: " << mBspStats.invalidLeaves << endl;
[542]2706}
2707
[547]2708
[574]2709
[547]2710void VspBspTree::CollectViewCells(BspNode *root,
2711                                                                  bool onlyValid,
[532]2712                                                                  ViewCellContainer &viewCells,
2713                                                                  bool onlyUnmailed) const
2714{
[498]2715        stack<BspNode *> nodeStack;
[463]2716
[538]2717        if (!root)
[508]2718                return;
[463]2719
[538]2720        nodeStack.push(root);
[498]2721       
2722        while (!nodeStack.empty())
2723        {
2724                BspNode *node = nodeStack.top();
2725                nodeStack.pop();
2726               
2727                if (node->IsLeaf())
2728                {
[564]2729                        if (!onlyValid || node->TreeValid())
[498]2730                        {
[882]2731                                ViewCellLeaf *leafVc = dynamic_cast<BspLeaf *>(node)->GetViewCell();
[727]2732
2733                                ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leafVc);
[590]2734                                               
[532]2735                                if (!onlyUnmailed || !viewCell->Mailed())
[498]2736                                {
2737                                        viewCell->Mail();
2738                                        viewCells.push_back(viewCell);
2739                                }
2740                        }
2741                }
2742                else
2743                {
2744                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
[508]2745               
[498]2746                        nodeStack.push(interior->GetFront());
2747                        nodeStack.push(interior->GetBack());
2748                }
2749        }
[590]2750
[463]2751}
2752
2753
[648]2754void VspBspTree::PreprocessPolygons(PolygonContainer &polys)
2755{
2756        // preprocess: throw out polygons coincident to the view space box (not needed)
2757        PolygonContainer boxPolys;
[1027]2758       
2759        mBox.ExtractPolys(boxPolys);
[648]2760        vector<Plane3> boxPlanes;
2761
2762        PolygonContainer::iterator pit, pit_end = boxPolys.end();
2763
2764        // extract planes of box
2765        // TODO: can be done more elegantly than first extracting polygons
2766        // and take their planes
2767        for (pit = boxPolys.begin(); pit != pit_end; ++ pit)
2768        {
2769                boxPlanes.push_back((*pit)->GetSupportingPlane());
2770        }
2771
2772        pit_end = polys.end();
2773
2774        for (pit = polys.begin(); pit != pit_end; ++ pit)
2775        {
2776                vector<Plane3>::const_iterator bit, bit_end = boxPlanes.end();
2777               
2778                for (bit = boxPlanes.begin(); (bit != bit_end) && (*pit); ++ bit)
2779                {
2780                        const int cf = (*pit)->ClassifyPlane(*bit, mEpsilon);
2781
2782                        if (cf == Polygon3::COINCIDENT)
2783                        {
2784                                DEL_PTR(*pit);
2785                                //Debug << "coincident!!" << endl;
2786                        }
2787                }
2788        }
2789
[1002]2790        // remove deleted entries after swapping them to end of vector
[648]2791        for (int i = 0; i < (int)polys.size(); ++ i)
2792        {
2793                while (!polys[i] && (i < (int)polys.size()))
2794                {
2795                        swap(polys[i], polys.back());
2796                        polys.pop_back();
2797                }
[1027]2798        }
[648]2799}
2800
2801
[463]2802float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
2803{
2804        float len = 0;
2805
2806        RayInfoContainer::const_iterator it, it_end = rays.end();
2807
2808        for (it = rays.begin(); it != it_end; ++ it)
2809                len += (*it).SegmentLength();
2810
2811        return len;
2812}
2813
[479]2814
[463]2815int VspBspTree::SplitRays(const Plane3 &plane,
[482]2816                                                  RayInfoContainer &rays,
2817                                                  RayInfoContainer &frontRays,
[639]2818                                                  RayInfoContainer &backRays) const
[463]2819{
2820        int splits = 0;
2821
[574]2822        RayInfoContainer::const_iterator it, it_end = rays.end();
2823
2824        for (it = rays.begin(); it != it_end; ++ it)
[463]2825        {
[574]2826                RayInfo bRay = *it;
2827               
[463]2828                VssRay *ray = bRay.mRay;
[473]2829                float t;
[463]2830
[485]2831                // get classification and receive new t
[463]2832                const int cf = bRay.ComputeRayIntersection(plane, t);
[482]2833
[463]2834                switch (cf)
2835                {
2836                case -1:
2837                        backRays.push_back(bRay);
2838                        break;
2839                case 1:
2840                        frontRays.push_back(bRay);
2841                        break;
[482]2842                case 0:
2843                        {
[485]2844                                //-- split ray
[639]2845                                //   test if start point behind or in front of plane
[485]2846                                const int side = plane.Side(bRay.ExtrapOrigin());
2847
[1011]2848                                ++ splits;
2849
[485]2850                                if (side <= 0)
2851                                {
2852                                        backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2853                                        frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2854                                }
2855                                else
2856                                {
2857                                        frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
2858                                        backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
2859                                }
[463]2860                        }
2861                        break;
2862                default:
[485]2863                        Debug << "Should not come here" << endl;
[463]2864                        break;
2865                }
2866        }
2867
2868        return splits;
2869}
2870
[479]2871
[463]2872void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
2873{
2874        BspNode *lastNode;
2875
2876        do
2877        {
2878                lastNode = n;
2879
2880                // want to get planes defining geometry of this node => don't take
2881                // split plane of node itself
2882                n = n->GetParent();
[482]2883
[463]2884                if (n)
2885                {
2886                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
2887                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
2888
[683]2889            if (interior->GetBack() != lastNode)
[463]2890                                halfSpace.ReverseOrientation();
2891
2892                        halfSpaces.push_back(halfSpace);
2893                }
2894        }
2895        while (n);
2896}
2897
[485]2898
[482]2899void VspBspTree::ConstructGeometry(BspNode *n,
[503]2900                                                                   BspNodeGeometry &geom) const
[463]2901{
[437]2902        vector<Plane3> halfSpaces;
2903        ExtractHalfSpaces(n, halfSpaces);
2904
2905        PolygonContainer candidatePolys;
[678]2906        vector<Plane3> candidatePlanes;
[437]2907
[719]2908        vector<Plane3>::const_iterator pit, pit_end = halfSpaces.end();
2909
[683]2910        // bounded planes are added to the polygons
[719]2911        for (pit = halfSpaces.begin(); pit != pit_end; ++ pit)
[437]2912        {
[719]2913                Polygon3 *p = GetBoundingBox().CrossSection(*pit);
[482]2914
[448]2915                if (p->Valid(mEpsilon))
[437]2916                {
[683]2917                        candidatePolys.push_back(p);
[719]2918                        candidatePlanes.push_back(*pit);
[437]2919                }
2920        }
2921
2922        // add faces of bounding box (also could be faces of the cell)
2923        for (int i = 0; i < 6; ++ i)
2924        {
2925                VertexContainer vertices;
[482]2926
[437]2927                for (int j = 0; j < 4; ++ j)
2928                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
2929
[678]2930                Polygon3 *poly = new Polygon3(vertices);
2931
2932                candidatePolys.push_back(poly);
2933                candidatePlanes.push_back(poly->GetSupportingPlane());
[437]2934        }
2935
2936        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
2937        {
2938                // polygon is split by all other planes
2939                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
2940                {
2941                        if (i == j) // polygon and plane are coincident
2942                                continue;
2943
2944                        VertexContainer splitPts;
2945                        Polygon3 *frontPoly, *backPoly;
2946
[482]2947                        const int cf =
[448]2948                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
2949                                                                                                 mEpsilon);
[482]2950
[437]2951                        switch (cf)
2952                        {
2953                                case Polygon3::SPLIT:
2954                                        frontPoly = new Polygon3();
2955                                        backPoly = new Polygon3();
2956
[482]2957                                        candidatePolys[i]->Split(halfSpaces[j],
2958                                                                                         *frontPoly,
[448]2959                                                                                         *backPoly,
2960                                                                                         mEpsilon);
[437]2961
2962                                        DEL_PTR(candidatePolys[i]);
2963
[683]2964                                        if (backPoly->Valid(mEpsilon))
2965                                                candidatePolys[i] = backPoly;
[437]2966                                        else
[683]2967                                                DEL_PTR(backPoly);
[437]2968
[683]2969                                        // outside, don't need this
2970                                        DEL_PTR(frontPoly);
[437]2971                                        break;
[683]2972                                // polygon outside of halfspace
2973                                case Polygon3::FRONT_SIDE:
[437]2974                                        DEL_PTR(candidatePolys[i]);
2975                                        break;
2976                                // just take polygon as it is
[683]2977                                case Polygon3::BACK_SIDE:
[437]2978                                case Polygon3::COINCIDENT:
2979                                default:
2980                                        break;
2981                        }
2982                }
[482]2983
[437]2984                if (candidatePolys[i])
[678]2985                {
2986                        geom.Add(candidatePolys[i], candidatePlanes[i]);
2987                        //      geom.mPolys.push_back(candidates[i]);
2988                }
[437]2989        }
[463]2990}
2991
[485]2992
[582]2993void VspBspTree::ConstructGeometry(ViewCell *vc,
[503]2994                                                                   BspNodeGeometry &vcGeom) const
[589]2995{
[580]2996        ViewCellContainer leaves;
[590]2997       
2998        mViewCellsTree->CollectLeaves(vc, leaves);
[463]2999
[580]3000        ViewCellContainer::const_iterator it, it_end = leaves.end();
3001
[463]3002        for (it = leaves.begin(); it != it_end; ++ it)
[580]3003        {
3004                BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
[590]3005               
[580]3006                ConstructGeometry(l, vcGeom);
3007        }
[463]3008}
3009
[485]3010
[482]3011int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
[562]3012                                                          const bool onlyUnmailed) const
[463]3013{
[551]3014        stack<bspNodePair> nodeStack;
3015       
3016        BspNodeGeometry nodeGeom;
3017        ConstructGeometry(n, nodeGeom);
[801]3018//      const float eps = 0.5f;
[752]3019        const float eps = 0.01f;
[500]3020        // split planes from the root to this node
3021        // needed to verify that we found neighbor leaf
[557]3022        // TODO: really needed?
[463]3023        vector<Plane3> halfSpaces;
3024        ExtractHalfSpaces(n, halfSpaces);
3025
[551]3026
3027        BspNodeGeometry *rgeom = new BspNodeGeometry();
3028        ConstructGeometry(mRoot, *rgeom);
3029
3030        nodeStack.push(bspNodePair(mRoot, rgeom));
3031
[482]3032        while (!nodeStack.empty())
[463]3033        {
[551]3034                BspNode *node = nodeStack.top().first;
3035                BspNodeGeometry *geom = nodeStack.top().second;
[562]3036       
[463]3037                nodeStack.pop();
3038
[557]3039                if (node->IsLeaf())
[562]3040                {
[557]3041                        // test if this leaf is in valid view space
3042                        if (node->TreeValid() &&
3043                                (node != n) &&
3044                                (!onlyUnmailed || !node->Mailed()))
3045                        {
3046                                bool isAdjacent = true;
[551]3047
[570]3048                                if (1)
[557]3049                                {
[562]3050                                        // test all planes of current node if still adjacent
3051                                        for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
3052                                        {
3053                                                const int cf =
[678]3054                                                        Polygon3::ClassifyPlane(geom->GetPolys(),
[562]3055                                                                                                        halfSpaces[i],
[752]3056                                                                                                        eps);
[482]3057
[683]3058                                                if (cf == Polygon3::FRONT_SIDE)
[562]3059                                                {
3060                                                        isAdjacent = false;
3061                                                }
[557]3062                                        }
3063                                }
[562]3064                                else
[557]3065                                {
[562]3066                                        // TODO: why is this wrong??
3067                                        // test all planes of current node if still adjacent
[678]3068                                        for (int i = 0; (i < nodeGeom.Size()) && isAdjacent; ++ i)
[562]3069                                        {
[678]3070                                                Polygon3 *poly = nodeGeom.GetPolys()[i];
[555]3071
[562]3072                                                const int cf =
[678]3073                                                        Polygon3::ClassifyPlane(geom->GetPolys(),
[562]3074                                                                                                        poly->GetSupportingPlane(),
[752]3075                                                                                                        eps);
[557]3076
[683]3077                                                if (cf == Polygon3::FRONT_SIDE)
[562]3078                                                {
3079                                                        isAdjacent = false;
3080                                                }
[557]3081                                        }
[570]3082                                }
[557]3083                                // neighbor was found
3084                                if (isAdjacent)
[562]3085                                {       
[551]3086                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
[562]3087                                }
[463]3088                        }
[562]3089                }
3090                else
3091                {
3092                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
[482]3093
[678]3094                        const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
[562]3095                                                                                                   interior->GetPlane(),
[752]3096                                                                                                   eps);
[551]3097                       
[562]3098                        BspNode *front = interior->GetFront();
3099                        BspNode *back = interior->GetBack();
[551]3100           
[562]3101                        BspNodeGeometry *fGeom = new BspNodeGeometry();
3102                        BspNodeGeometry *bGeom = new BspNodeGeometry();
[463]3103
[562]3104                        geom->SplitGeometry(*fGeom,
3105                                                                *bGeom,
3106                                                                interior->GetPlane(),
3107                                                                mBox,
[675]3108                                                                //0.0000001f);
[752]3109                                                                eps);
[551]3110               
[683]3111                        if (cf == Polygon3::BACK_SIDE)
[562]3112                        {
[683]3113                                nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
3114                                DEL_PTR(fGeom);
[562]3115                        }
3116                        else
3117                        {
[683]3118                                if (cf == Polygon3::FRONT_SIDE)
[551]3119                                {
[683]3120                                        nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
3121                                        DEL_PTR(bGeom);
[551]3122                                }
[482]3123                                else
[562]3124                                {       // random decision
3125                                        nodeStack.push(bspNodePair(front, fGeom));
3126                                        nodeStack.push(bspNodePair(back, bGeom));
[463]3127                                }
[551]3128                        }
[463]3129                }
[562]3130       
[551]3131                DEL_PTR(geom);
[463]3132        }
[482]3133
[463]3134        return (int)neighbors.size();
3135}
3136
[489]3137
[600]3138
[710]3139int VspBspTree::FindApproximateNeighbors(BspNode *n,
3140                                                                                 vector<BspLeaf *> &neighbors,
[600]3141                                                                                 const bool onlyUnmailed) const
3142{
3143        stack<bspNodePair> nodeStack;
3144       
3145        BspNodeGeometry nodeGeom;
3146        ConstructGeometry(n, nodeGeom);
3147       
[752]3148        float eps = 0.01f;
[600]3149        // split planes from the root to this node
3150        // needed to verify that we found neighbor leaf
3151        // TODO: really needed?
3152        vector<Plane3> halfSpaces;
3153        ExtractHalfSpaces(n, halfSpaces);
3154
3155
3156        BspNodeGeometry *rgeom = new BspNodeGeometry();
3157        ConstructGeometry(mRoot, *rgeom);
3158
3159        nodeStack.push(bspNodePair(mRoot, rgeom));
3160
3161        while (!nodeStack.empty())
3162        {
3163                BspNode *node = nodeStack.top().first;
3164                BspNodeGeometry *geom = nodeStack.top().second;
3165       
3166                nodeStack.pop();
3167
3168                if (node->IsLeaf())
3169                {
3170                        // test if this leaf is in valid view space
3171                        if (node->TreeValid() &&
3172                                (node != n) &&
3173                                (!onlyUnmailed || !node->Mailed()))
3174                        {
3175                                bool isAdjacent = true;
3176
3177                                // neighbor was found
3178                                if (isAdjacent)
3179                                {       
3180                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
3181                                }
3182                        }
3183                }
3184                else
3185                {
3186                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3187
[678]3188                        const int cf = Polygon3::ClassifyPlane(nodeGeom.GetPolys(),
[600]3189                                                                                                   interior->GetPlane(),
[752]3190                                                                                                   eps);
[600]3191                       
3192                        BspNode *front = interior->GetFront();
3193                        BspNode *back = interior->GetBack();
3194           
3195                        BspNodeGeometry *fGeom = new BspNodeGeometry();
3196                        BspNodeGeometry *bGeom = new BspNodeGeometry();
3197
3198                        geom->SplitGeometry(*fGeom,
3199                                                                *bGeom,
3200                                                                interior->GetPlane(),
3201                                                                mBox,
[675]3202                                                                //0.0000001f);
[752]3203                                                                eps);
[600]3204               
[683]3205                        if (cf == Polygon3::BACK_SIDE)
[600]3206                        {
[683]3207                                nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
3208                                DEL_PTR(fGeom);
[710]3209                                }
[600]3210                        else
3211                        {
[683]3212                                if (cf == Polygon3::FRONT_SIDE)
[600]3213                                {
[683]3214                                        nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
3215                                        DEL_PTR(bGeom);
[600]3216                                }
3217                                else
3218                                {       // random decision
3219                                        nodeStack.push(bspNodePair(front, fGeom));
3220                                        nodeStack.push(bspNodePair(back, bGeom));
3221                                }
3222                        }
3223                }
3224       
3225                DEL_PTR(geom);
3226        }
3227
3228        return (int)neighbors.size();
3229}
3230
3231
3232
[463]3233BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
3234{
3235    stack<BspNode *> nodeStack;
3236        nodeStack.push(mRoot);
[482]3237
[463]3238        int mask = rand();
[482]3239
3240        while (!nodeStack.empty())
[463]3241        {
3242                BspNode *node = nodeStack.top();
3243                nodeStack.pop();
[482]3244
3245                if (node->IsLeaf())
[463]3246                {
3247                        return dynamic_cast<BspLeaf *>(node);
[482]3248                }
3249                else
[463]3250                {
3251                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3252                        BspNode *next;
[503]3253                        BspNodeGeometry geom;
[482]3254
[463]3255                        // todo: not very efficient: constructs full cell everytime
[498]3256                        ConstructGeometry(interior, geom);
[463]3257
[503]3258                        const int cf =
[678]3259                                Polygon3::ClassifyPlane(geom.GetPolys(), halfspace, mEpsilon);
[463]3260
3261                        if (cf == Polygon3::BACK_SIDE)
3262                                next = interior->GetFront();
3263                        else
3264                                if (cf == Polygon3::FRONT_SIDE)
3265                                        next = interior->GetFront();
[482]3266                        else
[463]3267                        {
3268                                // random decision
3269                                if (mask & 1)
3270                                        next = interior->GetBack();
3271                                else
3272                                        next = interior->GetFront();
3273                                mask = mask >> 1;
3274                        }
3275
3276                        nodeStack.push(next);
3277                }
3278        }
[482]3279
[463]3280        return NULL;
3281}
3282
[694]3283
[463]3284BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
3285{
3286        stack<BspNode *> nodeStack;
[482]3287
[463]3288        nodeStack.push(mRoot);
3289
3290        int mask = rand();
[482]3291
3292        while (!nodeStack.empty())
[463]3293        {
3294                BspNode *node = nodeStack.top();
3295                nodeStack.pop();
[482]3296
3297                if (node->IsLeaf())
[463]3298                {
3299                        if ( (!onlyUnmailed || !node->Mailed()) )
3300                                return dynamic_cast<BspLeaf *>(node);
3301                }
[482]3302                else
[463]3303                {
3304                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3305
3306                        // random decision
3307                        if (mask & 1)
3308                                nodeStack.push(interior->GetBack());
3309                        else
3310                                nodeStack.push(interior->GetFront());
3311
3312                        mask = mask >> 1;
3313                }
3314        }
[482]3315
[463]3316        return NULL;
3317}
3318
[694]3319
[463]3320int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
3321{
3322        int pvsSize = 0;
3323
3324        RayInfoContainer::const_iterator rit, rit_end = rays.end();
3325
3326        Intersectable::NewMail();
3327
3328        for (rit = rays.begin(); rit != rays.end(); ++ rit)
3329        {
3330                VssRay *ray = (*rit).mRay;
[482]3331
[1020]3332                if (COUNT_ORIGIN_OBJECTS && ray->mOriginObject)
[463]3333                {
3334                        if (!ray->mOriginObject->Mailed())
3335                        {
3336                                ray->mOriginObject->Mail();
3337                                ++ pvsSize;
3338                        }
3339                }
[1020]3340
[463]3341                if (ray->mTerminationObject)
3342                {
3343                        if (!ray->mTerminationObject->Mailed())
3344                        {
3345                                ray->mTerminationObject->Mail();
3346                                ++ pvsSize;
3347                        }
3348                }
3349        }
3350
3351        return pvsSize;
3352}
3353
[694]3354
[463]3355float VspBspTree::GetEpsilon() const
3356{
3357        return mEpsilon;
3358}
3359
3360
3361int VspBspTree::SplitPolygons(const Plane3 &plane,
[482]3362                                                          PolygonContainer &polys,
3363                                                          PolygonContainer &frontPolys,
3364                                                          PolygonContainer &backPolys,
[463]3365                                                          PolygonContainer &coincident) const
3366{
3367        int splits = 0;
3368
[574]3369        PolygonContainer::const_iterator it, it_end = polys.end();
3370
3371        for (it = polys.begin(); it != polys.end(); ++ it)     
[463]3372        {
[574]3373                Polygon3 *poly = *it;
[463]3374
3375                // classify polygon
3376                const int cf = poly->ClassifyPlane(plane, mEpsilon);
3377
3378                switch (cf)
3379                {
3380                        case Polygon3::COINCIDENT:
3381                                coincident.push_back(poly);
[482]3382                                break;
3383                        case Polygon3::FRONT_SIDE:
[463]3384                                frontPolys.push_back(poly);
3385                                break;
3386                        case Polygon3::BACK_SIDE:
3387                                backPolys.push_back(poly);
3388                                break;
3389                        case Polygon3::SPLIT:
3390                                backPolys.push_back(poly);
3391                                frontPolys.push_back(poly);
3392                                ++ splits;
3393                                break;
3394                        default:
3395                Debug << "SHOULD NEVER COME HERE\n";
3396                                break;
3397                }
3398        }
3399
3400        return splits;
3401}
[466]3402
3403
[469]3404int VspBspTree::CastLineSegment(const Vector3 &origin,
3405                                                                const Vector3 &termination,
[882]3406                                                                ViewCellContainer &viewcells)
[466]3407{
[469]3408        int hits = 0;
[719]3409        stack<BspRayTraversalData> tStack;
[482]3410
[469]3411        float mint = 0.0f, maxt = 1.0f;
[482]3412
[1291]3413        //ViewCell::NewMail();
[482]3414
[469]3415        Vector3 entp = origin;
3416        Vector3 extp = termination;
[482]3417
[469]3418        BspNode *node = mRoot;
3419        BspNode *farChild = NULL;
[482]3420
[485]3421        float t;
[752]3422        const float thresh = 1e-6f; // matt: change this to adjustable value
[694]3423       
[482]3424        while (1)
[469]3425        {
[482]3426                if (!node->IsLeaf())
[469]3427                {
3428                        BspInterior *in = dynamic_cast<BspInterior *>(node);
[482]3429
[469]3430                        Plane3 splitPlane = in->GetPlane();
[485]3431                       
[666]3432                        const int entSide = splitPlane.Side(entp, thresh);
3433                        const int extSide = splitPlane.Side(extp, thresh);
[482]3434
[485]3435                        if (entSide < 0)
[469]3436                        {
[666]3437                                node = in->GetBack();
3438                               
3439                                // plane does not split ray => no far child
3440                                if (extSide <= 0)
3441                                        continue;
3442 
3443                                farChild = in->GetFront(); // plane splits ray
[485]3444                        }
3445                        else if (entSide > 0)
[469]3446                        {
[666]3447                                node = in->GetFront();
[482]3448
[666]3449                                if (extSide >= 0) // plane does not split ray => no far child
3450                                        continue;
[482]3451
3452                                farChild = in->GetBack(); // plane splits ray
[469]3453                        }
[694]3454                        else // one of the ray end points is on the plane
[1020]3455                        {       
3456                                // NOTE: what to do if ray is coincident with plane?
[485]3457                                if (extSide < 0)
3458                                        node = in->GetBack();
[694]3459                                else //if (extSide > 0)
[485]3460                                        node = in->GetFront();
[694]3461                                //else break; // coincident => count no intersections
3462
[485]3463                                continue; // no far child
[469]3464                        }
[482]3465
[469]3466                        // push data for far child
[719]3467                        tStack.push(BspRayTraversalData(farChild, extp));
[482]3468
[469]3469                        // find intersection of ray segment with plane
3470                        extp = splitPlane.FindIntersection(origin, extp, &t);
[485]3471                }
3472                else
[469]3473                {
3474                        // reached leaf => intersection with view cell
3475                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
[666]3476                        ViewCell *viewCell;
3477                       
[1020]3478                        // question: always contribute to leaf or to currently active view cell?
[708]3479                        if (0)
3480                                viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
3481                        else
3482                                viewCell = leaf->GetViewCell();
[482]3483
[590]3484                        if (!viewCell->Mailed())
[469]3485                        {
[590]3486                                viewcells.push_back(viewCell);
3487                                viewCell->Mail();
[469]3488                                ++ hits;
3489                        }
[482]3490
[469]3491                        //-- fetch the next far child from the stack
[719]3492                        if (tStack.empty())
[469]3493                                break;
[482]3494
[469]3495                        entp = extp;
[485]3496                       
[719]3497                        const BspRayTraversalData &s = tStack.top();
[482]3498
[469]3499                        node = s.mNode;
3500                        extp = s.mExitPoint;
[482]3501
[719]3502                        tStack.pop();
[469]3503                }
[466]3504        }
[487]3505
[469]3506        return hits;
[466]3507}
[478]3508
[576]3509
3510
3511
[485]3512int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
[482]3513{
3514        std::deque<BspNode *> path1;
3515        BspNode *p1 = n1;
[479]3516
[482]3517        // create path from node 1 to root
3518        while (p1)
3519        {
3520                if (p1 == n2) // second node on path
3521                        return (int)path1.size();
3522
3523                path1.push_front(p1);
3524                p1 = p1->GetParent();
3525        }
3526
3527        int depth = n2->GetDepth();
3528        int d = depth;
3529
3530        BspNode *p2 = n2;
3531
3532        // compare with same depth
3533        while (1)
3534        {
3535                if ((d < (int)path1.size()) && (p2 == path1[d]))
3536                        return (depth - d) + ((int)path1.size() - 1 - d);
3537
3538                -- d;
3539                p2 = p2->GetParent();
3540        }
3541
3542        return 0; // never come here
3543}
3544
[580]3545
[501]3546BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
[479]3547{
[590]3548// TODO
[728]3549#if HAS_TO_BE_REDONE
[495]3550        if (node->IsLeaf())
[479]3551                return node;
3552
[492]3553        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3554
[501]3555        BspNode *front = CollapseTree(interior->GetFront(), collapsed);
3556        BspNode *back = CollapseTree(interior->GetBack(), collapsed);
[492]3557
[479]3558        if (front->IsLeaf() && back->IsLeaf())
3559        {
3560                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
3561                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
3562
3563                //-- collapse tree
3564                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
3565                {
3566                        BspViewCell *vc = frontLeaf->GetViewCell();
3567
3568                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
[489]3569                        leaf->SetTreeValid(frontLeaf->TreeValid());
[482]3570
[479]3571                        // replace a link from node's parent
3572                        if (leaf->GetParent())
3573                                leaf->GetParent()->ReplaceChildLink(node, leaf);
[517]3574                        else
3575                                mRoot = leaf;
3576
[501]3577                        ++ collapsed;
[479]3578                        delete interior;
3579
3580                        return leaf;
3581                }
3582        }
[590]3583#endif
[495]3584        return node;
3585}
3586
3587
[501]3588int VspBspTree::CollapseTree()
[495]3589{
[501]3590        int collapsed = 0;
[580]3591        //TODO
[728]3592#if HAS_TO_BE_REDONE
[501]3593        (void)CollapseTree(mRoot, collapsed);
[517]3594
[485]3595        // revalidate leaves
[517]3596        RepairViewCellsLeafLists();
[580]3597#endif
[501]3598        return collapsed;
[479]3599}
3600
3601
[517]3602void VspBspTree::RepairViewCellsLeafLists()
[492]3603{
[590]3604// TODO
[728]3605#if HAS_TO_BE_REDONE
[479]3606        // list not valid anymore => clear
[492]3607        stack<BspNode *> nodeStack;
3608        nodeStack.push(mRoot);
3609
3610        ViewCell::NewMail();
3611
3612        while (!nodeStack.empty())
3613        {
3614                BspNode *node = nodeStack.top();
3615                nodeStack.pop();
3616
3617                if (node->IsLeaf())
3618                {
3619                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
3620
3621                        BspViewCell *viewCell = leaf->GetViewCell();
[590]3622
[492]3623                        if (!viewCell->Mailed())
3624                        {
3625                                viewCell->mLeaves.clear();
3626                                viewCell->Mail();
3627                        }
[580]3628       
[492]3629                        viewCell->mLeaves.push_back(leaf);
[590]3630
[492]3631                }
3632                else
3633                {
3634                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3635
3636                        nodeStack.push(interior->GetFront());
3637                        nodeStack.push(interior->GetBack());
3638                }
[479]3639        }
[590]3640// TODO
3641#endif
[479]3642}
3643
3644
[532]3645int VspBspTree::CastBeam(Beam &beam)
3646{
3647    stack<bspNodePair> nodeStack;
3648        BspNodeGeometry *rgeom = new BspNodeGeometry();
3649        ConstructGeometry(mRoot, *rgeom);
3650
3651        nodeStack.push(bspNodePair(mRoot, rgeom));
3652 
3653        ViewCell::NewMail();
3654
3655        while (!nodeStack.empty())
3656        {
3657                BspNode *node = nodeStack.top().first;
3658                BspNodeGeometry *geom = nodeStack.top().second;
3659                nodeStack.pop();
3660               
3661                AxisAlignedBox3 box;
[697]3662                geom->GetBoundingBox(box);
[532]3663
[535]3664                const int side = beam.ComputeIntersection(box);
[532]3665               
3666                switch (side)
3667                {
3668                case -1:
[547]3669                        CollectViewCells(node, true, beam.mViewCells, true);
[532]3670                        break;
3671                case 0:
[535]3672                       
[532]3673                        if (node->IsLeaf())
3674                        {
[535]3675                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
3676                       
[532]3677                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
[535]3678                                {
3679                                        leaf->GetViewCell()->Mail();
[532]3680                                        beam.mViewCells.push_back(leaf->GetViewCell());
[535]3681                                }
[532]3682                        }
3683                        else
3684                        {
3685                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
[535]3686                       
[538]3687                                BspNode *first = interior->GetFront();
3688                                BspNode *second = interior->GetBack();
[535]3689           
3690                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
3691                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
3692
[538]3693                                geom->SplitGeometry(*firstGeom,
3694                                                                        *secondGeom,
3695                                                                        interior->GetPlane(),
3696                                                                        mBox,
[675]3697                                                                        //0.0000001f);
[538]3698                                                                        mEpsilon);
[535]3699
[532]3700                                // decide on the order of the nodes
3701                                if (DotProd(beam.mPlanes[0].mNormal,
3702                                        interior->GetPlane().mNormal) > 0)
3703                                {
3704                                        swap(first, second);
[535]3705                                        swap(firstGeom, secondGeom);
[532]3706                                }
3707
[535]3708                                nodeStack.push(bspNodePair(first, firstGeom));
3709                                nodeStack.push(bspNodePair(second, secondGeom));
[532]3710                        }
[535]3711                       
[532]3712                        break;
[538]3713                default:
[532]3714                        // default: cull
[538]3715                        break;
[532]3716                }
[538]3717               
[532]3718                DEL_PTR(geom);
[535]3719               
[532]3720        }
3721
[538]3722        return (int)beam.mViewCells.size();
[532]3723}
3724
3725
[485]3726void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
[478]3727{
[485]3728        mViewCellsManager = vcm;
3729}
3730
3731
[580]3732int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
3733                                                                           vector<MergeCandidate> &candidates)
[485]3734{
[478]3735        BspLeaf::NewMail();
[508]3736       
[478]3737        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
3738
[580]3739        int numCandidates = 0;
[509]3740
[478]3741        // find merge candidates and push them into queue
3742        for (it = leaves.begin(); it != it_end; ++ it)
3743        {
3744                BspLeaf *leaf = *it;
[485]3745               
3746                // the same leaves must not be part of two merge candidates
3747                leaf->Mail();
[650]3748               
[485]3749                vector<BspLeaf *> neighbors;
[710]3750               
3751                // appoximate neighbor search has slightl relaxed constraints
[694]3752                if (1)
[650]3753                        FindNeighbors(leaf, neighbors, true);
3754                else
3755                        FindApproximateNeighbors(leaf, neighbors, true);
[710]3756
[485]3757                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
3758
3759                // TODO: test if at least one ray goes from one leaf to the other
3760                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
[508]3761                {
3762                        if ((*nit)->GetViewCell() != leaf->GetViewCell())
[509]3763                        {
[580]3764                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
[564]3765
[1006]3766                                if (!leaf->GetViewCell()->GetPvs().Empty() ||
[710]3767                                        !(*nit)->GetViewCell()->GetPvs().Empty() ||
[676]3768                    leaf->IsSibling(*nit))
3769                                {
3770                                        candidates.push_back(mc);
3771                                }
3772
[580]3773                                ++ numCandidates;
3774                                if ((numCandidates % 1000) == 0)
[566]3775                                {
[580]3776                                        cout << "collected " << numCandidates << " merge candidates" << endl;
[566]3777                                }
[509]3778                        }
[485]3779                }
3780        }
3781
[580]3782        Debug << "merge queue: " << (int)candidates.size() << endl;
3783        Debug << "leaves in queue: " << numCandidates << endl;
3784       
[508]3785
[485]3786        return (int)leaves.size();
3787}
3788
3789
[580]3790int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays,
3791                                                                           vector<MergeCandidate> &candidates)
[485]3792{
[547]3793        ViewCell::NewMail();
[503]3794        long startTime = GetTime();
[574]3795       
[485]3796        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
[574]3797        ViewCellContainer::const_iterator iit;
[485]3798
[503]3799        int numLeaves = 0;
[485]3800       
3801        BspLeaf::NewMail();
3802
[574]3803        for (int i = 0; i < (int)rays.size(); ++ i)
[485]3804        { 
[574]3805                VssRay *ray = rays[i];
[547]3806       
[485]3807                // traverse leaves stored in the rays and compare and
3808                // merge consecutive leaves (i.e., the neighbors in the tree)
[574]3809                if (ray->mViewCells.size() < 2)
[485]3810                        continue;
[580]3811//TODO viewcellhierarchy
[574]3812                iit = ray->mViewCells.begin();
3813                BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
[580]3814                BspLeaf *leaf = bspVc->mLeaf;
[485]3815               
3816                // traverse intersections
[489]3817                // consecutive leaves are neighbors => add them to queue
[574]3818                for (; iit != ray->mViewCells.end(); ++ iit)
[485]3819                {
[489]3820                        // next pair
3821                        BspLeaf *prevLeaf = leaf;
[574]3822                        bspVc = dynamic_cast<BspViewCell *>(*iit);
[580]3823            leaf = bspVc->mLeaf;
[489]3824
[508]3825                        // view space not valid or same view cell
3826                        if (!leaf->TreeValid() || !prevLeaf->TreeValid() ||
3827                                (leaf->GetViewCell() == prevLeaf->GetViewCell()))
[489]3828                                continue;
3829
[580]3830                vector<BspLeaf *> &neighbors = neighborMap[leaf];
[485]3831                       
3832                        bool found = false;
[478]3833
[485]3834                        // both leaves inserted in queue already =>
3835                        // look if double pair already exists
3836                        if (leaf->Mailed() && prevLeaf->Mailed())
[478]3837                        {
[485]3838                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
3839                               
3840                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
3841                                        if (*it == prevLeaf)
3842                                                found = true; // already in queue
3843                        }
[547]3844               
[485]3845                        if (!found)
3846                        {
[564]3847                                // this pair is not in map yet
[485]3848                                // => insert into the neighbor map and the queue
3849                                neighbors.push_back(prevLeaf);
3850                                neighborMap[prevLeaf].push_back(leaf);
[478]3851
[485]3852                                leaf->Mail();
3853                                prevLeaf->Mail();
[547]3854               
[580]3855                                MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
3856                               
3857                                candidates.push_back(mc);
[564]3858
[580]3859                                if (((int)candidates.size() % 1000) == 0)
[564]3860                                {
[580]3861                                        cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
[564]3862                                }
[478]3863                        }
[485]3864        }
3865        }
[564]3866
[485]3867        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
[580]3868        Debug << "merge queue: " << (int)candidates.size() << endl;
[503]3869        Debug << "leaves in queue: " << numLeaves << endl;
[485]3870
[580]3871
[503]3872        //-- collect the leaves which haven't been found by ray casting
[542]3873        if (0)
3874        {
[551]3875                cout << "finding additional merge candidates using geometry" << endl;
[542]3876                vector<BspLeaf *> leaves;
[547]3877                CollectLeaves(leaves, true);
[542]3878                Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
[580]3879                CollectMergeCandidates(leaves, candidates);
[542]3880        }
[503]3881
3882        return numLeaves;
[485]3883}
3884
3885
3886
3887
[879]3888ViewCell *VspBspTree::GetViewCell(const Vector3 &point, const bool active)
[492]3889{
[879]3890        if (mRoot == NULL)
3891                return NULL;
3892
3893        stack<BspNode *> nodeStack;
3894        nodeStack.push(mRoot);
[492]3895 
[882]3896        ViewCellLeaf *viewcell = NULL;
[492]3897 
[879]3898        while (!nodeStack.empty()) 
3899        {
3900                BspNode *node = nodeStack.top();
3901                nodeStack.pop();
[492]3902       
[879]3903                if (node->IsLeaf())
3904                {
3905                        viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
3906                        break;
3907                }
3908                else   
3909                {       
3910                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3911       
3912                        // random decision
3913                        if (interior->GetPlane().Side(point) < 0)
3914                                nodeStack.push(interior->GetBack());
3915                        else
3916                                nodeStack.push(interior->GetFront());
3917                }
[492]3918        }
3919 
[879]3920        if (active)
3921                return mViewCellsTree->GetActiveViewCell(viewcell);
3922        else
3923                return viewcell;
[492]3924}
3925
3926
[487]3927bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
3928{
3929        BspNode *node = mRoot;
[485]3930
[487]3931        while (1)
3932        {
3933                // early exit
3934                if (node->TreeValid())
3935                        return true;
3936
3937                if (node->IsLeaf())
3938                        return false;
3939                       
3940                BspInterior *in = dynamic_cast<BspInterior *>(node);
[490]3941                                       
3942                if (in->GetPlane().Side(viewPoint) <= 0)
[487]3943                {
3944                        node = in->GetBack();
3945                }
3946                else
3947                {
3948                        node = in->GetFront();
3949                }
3950        }
3951
3952        // should never come here
3953        return false;
3954}
3955
3956
3957void VspBspTree::PropagateUpValidity(BspNode *node)
3958{
[574]3959        const bool isValid = node->TreeValid();
3960
3961        // propagative up invalid flag until only invalid nodes exist over this node
3962        if (!isValid)
[487]3963        {
[574]3964                while (!node->IsRoot() && node->GetParent()->TreeValid())
3965                {
3966                        node = node->GetParent();
3967                        node->SetTreeValid(false);
3968                }
[487]3969        }
[574]3970        else
3971        {
3972                // propagative up valid flag until one of the subtrees is invalid
3973                while (!node->IsRoot() && !node->TreeValid())
3974                {
3975            node = node->GetParent();
3976                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
3977                       
3978                        // the parent is valid iff both leaves are valid
3979                        node->SetTreeValid(interior->GetBack()->TreeValid() &&
3980                                                           interior->GetFront()->TreeValid());
3981                }
3982        }
[487]3983}
3984
[1201]3985
3986bool VspBspTree::Export(OUT_STREAM &stream)
[503]3987{
[508]3988        ExportNode(mRoot, stream);
[487]3989
[503]3990        return true;
3991}
3992
[1201]3993
3994void VspBspTree::ExportNode(BspNode *node, OUT_STREAM &stream)
[508]3995{
3996        if (node->IsLeaf())
[503]3997        {
[508]3998                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
[590]3999                ViewCell *viewCell = mViewCellsTree->GetActiveViewCell(leaf->GetViewCell());
4000
[508]4001                int id = -1;
[590]4002                if (viewCell != mOutOfBoundsCell)
4003                        id = viewCell->GetId();
[503]4004
[508]4005                stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
[503]4006        }
[508]4007        else
[503]4008        {
[508]4009                BspInterior *interior = dynamic_cast<BspInterior *>(node);
4010       
4011                Plane3 plane = interior->GetPlane();
4012                stream << "<Interior plane=\"" << plane.mNormal.x << " "
4013                           << plane.mNormal.y << " " << plane.mNormal.z << " "
4014                           << plane.mD << "\">" << endl;
[503]4015
[508]4016                ExportNode(interior->GetBack(), stream);
4017                ExportNode(interior->GetFront(), stream);
[503]4018
[508]4019                stream << "</Interior>" << endl;
[503]4020        }
4021}
[860]4022
4023}
Note: See TracBrowser for help on using the repository browser.