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

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