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

Revision 2627, 98.7 KB checked in by bittner, 17 years ago (diff)

commit before merge with vlastimil

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