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

Revision 1077, 97.0 KB checked in by mattausch, 18 years ago (diff)

worked on object space /view space partitioning

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