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

Revision 1727, 98.1 KB checked in by mattausch, 18 years ago (diff)

implemented several accelleration svhemes for the gradient method

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