source: trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp @ 557

Revision 557, 80.7 KB checked in by mattausch, 19 years ago (diff)

started implementing merge visualization !not working!!

Line 
1#include <stack>
2#include <time.h>
3#include <iomanip>
4
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"
17#include "ViewCellsManager.h"
18#include "Beam.h"
19
20//-- static members
21
22/** Evaluates split plane classification with respect to the plane's
23        contribution for a minimum number of ray splits.
24*/
25const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
26/** Evaluates split plane classification with respect to the plane's
27        contribution for balanced rays.
28*/
29const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
30
31int BspMergeCandidate::sMaxPvsSize = 0;
32
33int VspBspTree::sFrontId = 0;
34int VspBspTree::sBackId = 0;
35int VspBspTree::sFrontAndBackId = 0;
36
37float BspMergeCandidate::sOverallCost = 0;
38bool BspMergeCandidate::sUseArea = false;
39
40
41/********************************************************************/
42/*                  class VspBspTree implementation                 */
43/********************************************************************/
44
45
46VspBspTree::VspBspTree():
47mRoot(NULL),
48mUseAreaForPvs(false),
49mCostNormalizer(Limits::Small),
50mViewCellsManager(NULL),
51mOutOfBoundsCell(NULL),
52mStoreRays(false)
53{
54        bool randomize = false;
55        environment->GetBoolValue("VspBspTree.Construction.randomize", randomize);
56        if (randomize)
57                Randomize(); // initialise random generator for heuristics
58
59        //-- termination criteria for autopartition
60        environment->GetIntValue("VspBspTree.Termination.maxDepth", mTermMaxDepth);
61        environment->GetIntValue("VspBspTree.Termination.minPvs", mTermMinPvs);
62        environment->GetIntValue("VspBspTree.Termination.minRays", mTermMinRays);
63        environment->GetFloatValue("VspBspTree.Termination.minProbability", mTermMinProbability);
64        environment->GetFloatValue("VspBspTree.Termination.maxRayContribution", mTermMaxRayContribution);
65        environment->GetFloatValue("VspBspTree.Termination.minAccRayLenght", mTermMinAccRayLength);
66        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
67        environment->GetIntValue("VspBspTree.Termination.missTolerance", mTermMissTolerance);
68
69        //-- factors for bsp tree split plane heuristics
70        environment->GetFloatValue("VspBspTree.Factor.balancedRays", mBalancedRaysFactor);
71        environment->GetFloatValue("VspBspTree.Factor.pvs", mPvsFactor);
72        environment->GetFloatValue("VspBspTree.Termination.ct_div_ci", mCtDivCi);
73
74        //-- max cost ratio for early tree termination
75        environment->GetFloatValue("VspBspTree.Termination.maxCostRatio", mTermMaxCostRatio);
76
77        //-- partition criteria
78        environment->GetIntValue("VspBspTree.maxPolyCandidates", mMaxPolyCandidates);
79        environment->GetIntValue("VspBspTree.maxRayCandidates", mMaxRayCandidates);
80        environment->GetIntValue("VspBspTree.splitPlaneStrategy", mSplitPlaneStrategy);
81
82        environment->GetFloatValue("VspBspTree.Construction.epsilon", mEpsilon);
83        environment->GetIntValue("VspBspTree.maxTests", mMaxTests);
84
85        // maximum and minimum number of view cells
86        environment->GetIntValue("VspBspTree.Termination.maxViewCells", mMaxViewCells);
87
88        environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
89
90        //-- merge options
91        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
92        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
93        environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
94
95
96        //-- termination criteria for axis aligned split
97        environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution",
98                mTermMaxRayContriForAxisAligned);
99        environment->GetIntValue("VspBspTree.Termination.AxisAligned.minRays",
100                mTermMinRaysForAxisAligned);
101
102        //environment->GetFloatValue("VspBspTree.maxTotalMemory", mMaxTotalMemory);
103        environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
104
105       
106        mStats.open("bspStats.log");
107
108        //-- debug output
109        Debug << "******* VSP BSP options ******** " << endl;
110    Debug << "max depth: " << mTermMaxDepth << endl;
111        Debug << "min PVS: " << mTermMinPvs << endl;
112        Debug << "min probabiliy: " << mTermMinProbability << endl;
113        Debug << "min rays: " << mTermMinRays << endl;
114        Debug << "max ray contri: " << mTermMaxRayContribution << endl;
115        //Debug << "VSP BSP mininam accumulated ray lenght: ", mTermMinAccRayLength) << endl;
116        Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
117        Debug << "miss tolerance: " << mTermMissTolerance << endl;
118        Debug << "max view cells: " << mMaxViewCells << endl;
119        Debug << "max polygon candidates: " << mMaxPolyCandidates << endl;
120        Debug << "max plane candidates: " << mMaxRayCandidates << endl;
121        Debug << "randomize: " << randomize << endl;
122        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
123        Debug << "using area for pvs: " << mUseAreaForPvs << endl;
124        Debug << "Split plane strategy: ";
125        if (mSplitPlaneStrategy & RANDOM_POLYGON)
126        {
127                Debug << "random polygon ";
128        }
129        if (mSplitPlaneStrategy & AXIS_ALIGNED)
130        {
131                Debug << "axis aligned ";
132        }
133        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
134        {
135                mCostNormalizer += mLeastRaySplitsFactor;
136                Debug << "least ray splits ";
137        }
138        if (mSplitPlaneStrategy & BALANCED_RAYS)
139        {
140                mCostNormalizer += mBalancedRaysFactor;
141                Debug << "balanced rays ";
142        }
143        if (mSplitPlaneStrategy & PVS)
144        {
145                mCostNormalizer += mPvsFactor;
146                Debug << "pvs";
147        }
148
149
150        mSplitCandidates = new vector<SortableEntry>;
151
152        Debug << endl;
153}
154
155BspViewCell *VspBspTree::GetOutOfBoundsCell()
156{
157        return mOutOfBoundsCell;
158}
159
160
161BspViewCell *VspBspTree::GetOrCreateOutOfBoundsCell()
162{
163        if (!mOutOfBoundsCell)
164        {
165                mOutOfBoundsCell = new BspViewCell();
166                mOutOfBoundsCell->SetId(-1);
167                mOutOfBoundsCell->SetValid(false);
168        }
169
170        return mOutOfBoundsCell;
171}
172
173
174const BspTreeStatistics &VspBspTree::GetStatistics() const
175{
176        return mStat;
177}
178
179
180VspBspTree::~VspBspTree()
181{
182        DEL_PTR(mRoot);
183        DEL_PTR(mSplitCandidates);
184}
185
186int VspBspTree::AddMeshToPolygons(Mesh *mesh,
187                                                                  PolygonContainer &polys,
188                                                                  MeshInstance *parent)
189{
190        FaceContainer::const_iterator fi;
191
192        // copy the face data to polygons
193        for (fi = mesh->mFaces.begin(); fi != mesh->mFaces.end(); ++ fi)
194        {
195                Polygon3 *poly = new Polygon3((*fi), mesh);
196
197                if (poly->Valid(mEpsilon))
198                {
199                        poly->mParent = parent; // set parent intersectable
200                        polys.push_back(poly);
201                }
202                else
203                        DEL_PTR(poly);
204        }
205        return (int)mesh->mFaces.size();
206}
207
208int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
209                                                          PolygonContainer &polys,
210                                                          int maxObjects)
211{
212        int limit = (maxObjects > 0) ?
213                Min((int)viewCells.size(), maxObjects) : (int)viewCells.size();
214
215        int polysSize = 0;
216
217        for (int i = 0; i < limit; ++ i)
218        {
219                if (viewCells[i]->GetMesh()) // copy the mesh data to polygons
220                {
221                        mBox.Include(viewCells[i]->GetBox()); // add to BSP tree aabb
222                        polysSize +=
223                                AddMeshToPolygons(viewCells[i]->GetMesh(),
224                                                                  polys,
225                                                                  viewCells[i]);
226                }
227        }
228
229        return polysSize;
230}
231
232int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
233                                                                 PolygonContainer &polys,
234                                                                 int maxObjects)
235{
236        int limit = (maxObjects > 0) ?
237                Min((int)objects.size(), maxObjects) : (int)objects.size();
238
239        for (int i = 0; i < limit; ++i)
240        {
241                Intersectable *object = objects[i];//*it;
242                Mesh *mesh = NULL;
243
244                switch (object->Type()) // extract the meshes
245                {
246                case Intersectable::MESH_INSTANCE:
247                        mesh = dynamic_cast<MeshInstance *>(object)->GetMesh();
248                        break;
249                case Intersectable::VIEW_CELL:
250                        mesh = dynamic_cast<ViewCell *>(object)->GetMesh();
251                        break;
252                        // TODO: handle transformed mesh instances
253                default:
254                        Debug << "intersectable type not supported" << endl;
255                        break;
256                }
257
258        if (mesh) // copy the mesh data to polygons
259                {
260                        mBox.Include(object->GetBox()); // add to BSP tree aabb
261                        AddMeshToPolygons(mesh, polys, NULL);
262                }
263        }
264
265        return (int)polys.size();
266}
267
268void VspBspTree::Construct(const VssRayContainer &sampleRays,
269                                                   AxisAlignedBox3 *forcedBoundingBox)
270{
271    mStat.nodes = 1;
272        mBox.Initialize();      // initialise BSP tree bounding box
273
274        if (forcedBoundingBox)
275                mBox = *forcedBoundingBox;
276       
277        PolygonContainer polys;
278        RayInfoContainer *rays = new RayInfoContainer();
279
280        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
281
282        long startTime = GetTime();
283
284        cout << "Extracting polygons from rays ... ";
285
286        Intersectable::NewMail();
287
288        int numObj = 0;
289
290        //-- extract polygons intersected by the rays
291        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
292        {
293                VssRay *ray = *rit;
294
295                if ((mBox.IsInside(ray->mTermination) || !forcedBoundingBox) &&
296                        ray->mTerminationObject &&
297                        !ray->mTerminationObject->Mailed())
298                {
299                        ray->mTerminationObject->Mail();
300                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mTerminationObject);
301                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
302                        ++ numObj;
303                        //-- compute bounding box
304                        if (!forcedBoundingBox)
305                                mBox.Include(ray->mTermination);
306                }
307
308                if ((mBox.IsInside(ray->mOrigin) || !forcedBoundingBox) &&
309                        ray->mOriginObject &&
310                        !ray->mOriginObject->Mailed())
311                {
312                        ray->mOriginObject->Mail();
313                        MeshInstance *obj = dynamic_cast<MeshInstance *>(ray->mOriginObject);
314                        AddMeshToPolygons(obj->GetMesh(), polys, obj);
315                        ++ numObj;
316
317                        //-- compute bounding box
318                        if (!forcedBoundingBox)
319                                mBox.Include(ray->mOrigin);
320                }
321        }
322       
323        Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
324        //-- store rays
325        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
326        {
327                VssRay *ray = *rit;
328
329                float minT, maxT;
330
331                // TODO: not very efficient to implictly cast between rays types
332                if (mBox.GetRaySegment(*ray, minT, maxT))
333                {
334                        float len = ray->Length();
335
336                        if (!len)
337                                len = Limits::Small;
338
339                        rays->push_back(RayInfo(ray, minT / len, maxT / len));
340                }
341        }
342
343        if (mUseAreaForPvs)
344                mTermMinProbability *= mBox.SurfaceArea(); // normalize
345        else
346                mTermMinProbability *= mBox.GetVolume();
347
348        mStat.polys = (int)polys.size();
349
350        cout << "finished" << endl;
351
352        Debug << "\nPolygon extraction: " << (int)polys.size() << " polys extracted from "
353                  << (int)sampleRays.size() << " rays in "
354                  << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl << endl;
355
356        Construct(polys, rays);
357
358        // clean up polygons
359        CLEAR_CONTAINER(polys);
360}
361
362
363// return memory usage in MB
364float VspBspTree::GetMemUsage() const
365{
366        return
367                (sizeof(VspBspTree) +
368                 mStat.Leaves() * sizeof(BspLeaf) +
369                 mStat.Interior() * sizeof(BspInterior) +
370                 mStat.accumRays * sizeof(RayInfo)) / (1024.0f * 1024.0f);
371}
372
373
374
375void VspBspTree::Construct(const PolygonContainer &polys, RayInfoContainer *rays)
376{
377        VspBspTraversalStack tStack;
378
379        mRoot = new BspLeaf();
380
381        // constrruct root node geometry
382        BspNodeGeometry *geom = new BspNodeGeometry();
383        ConstructGeometry(mRoot, *geom);
384
385        const float prop = mUseAreaForPvs ? geom->GetArea() : geom->GetVolume();
386
387        VspBspTraversalData tData(mRoot,
388                                                          new PolygonContainer(polys),
389                                                          0,
390                                                          rays,
391                              ComputePvsSize(*rays),
392                                                          prop,
393                                                          geom);
394
395        tStack.push(tData);
396
397        mStat.Start();
398        cout << "Contructing vsp bsp tree ... \n";
399
400        long startTime = GetTime();     
401        // used for intermediate time measurements
402        long interTime = GetTime();     
403
404        mOutOfMemory = false;
405
406        int nleaves = 500;
407
408        while (!tStack.empty())
409        {
410                tData = tStack.top();
411            tStack.pop();               
412
413                if (0 && !mOutOfMemory)
414                {
415                        float mem = GetMemUsage();
416
417                        if (mem > mMaxMemory)
418                        {
419                                mOutOfMemory = true;
420                                Debug << "memory limit reached: " << mem << endl;
421                        }
422                }
423
424                        // subdivide leaf node
425                BspNode *r = Subdivide(tStack, tData);
426
427                if (r == mRoot)
428                        Debug << "VSP BSP tree construction time spent at root: "
429                                  << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
430
431                if (mStat.Leaves() >= nleaves)
432                {
433                        nleaves += 500;
434                               
435                        cout << "leaves=" << mStat.Leaves() << endl;
436                        Debug << "needed "
437                          << TimeDiff(interTime, GetTime())*1e-3 << " secs to create 500 leaves" << endl;
438                        interTime = GetTime();
439                }
440        }
441
442        Debug << "Used Memory: " << GetMemUsage() << " MB" << endl << endl;
443        cout << "finished\n";
444
445        mStat.Stop();
446}
447
448
449bool VspBspTree::TerminationCriteriaMet(const VspBspTraversalData &data) const
450{
451        return
452                (((int)data.mRays->size() <= mTermMinRays) ||
453                 (data.mPvs <= mTermMinPvs)   ||
454                 (data.mProbability <= mTermMinProbability) ||
455                 (mStat.Leaves() >= mMaxViewCells) ||
456                 (data.GetAvgRayContribution() > mTermMaxRayContribution) ||
457                 (data.mDepth >= mTermMaxDepth));
458}
459
460
461BspNode *VspBspTree::Subdivide(VspBspTraversalStack &tStack,
462                                                           VspBspTraversalData &tData)
463{
464        BspNode *newNode = tData.mNode;
465
466        if (!mOutOfMemory && !TerminationCriteriaMet(tData))
467        {
468                PolygonContainer coincident;
469
470                VspBspTraversalData tFrontData;
471                VspBspTraversalData tBackData;
472
473                // create new interior node and two leaf nodes
474                // or return leaf as it is (if maxCostRatio missed)
475                newNode = SubdivideNode(tData, tFrontData, tBackData, coincident);
476
477                if (!newNode->IsLeaf()) //-- continue subdivision
478                {
479                        // push the children on the stack
480                        tStack.push(tFrontData);
481                        tStack.push(tBackData);
482
483                        // delete old leaf node
484                        DEL_PTR(tData.mNode);
485                }
486        }
487
488        //-- terminate traversal and create new view cell
489        if (newNode->IsLeaf())
490        {
491                BspLeaf *leaf = dynamic_cast<BspLeaf *>(newNode);
492                BspViewCell *viewCell = new BspViewCell();
493               
494                leaf->SetViewCell(viewCell);
495       
496                //-- update pvs
497                int conSamp = 0;
498                float sampCon = 0.0f;
499                AddToPvs(leaf, *tData.mRays, sampCon, conSamp);
500
501                mStat.contributingSamples += conSamp;
502                mStat.sampleContributions +=(int) sampCon;
503
504                //-- store additional info
505                if (mStoreRays)
506                {
507                        RayInfoContainer::const_iterator it, it_end = tData.mRays->end();
508                        for (it = tData.mRays->begin(); it != it_end; ++ it)
509                                leaf->mVssRays.push_back((*it).mRay);
510                }
511               
512                if (!mViewCellsManager->CheckValid(viewCell))
513                {
514                        viewCell->SetValid(false);
515
516                        leaf->SetTreeValid(false);
517                        PropagateUpValidity(leaf);
518
519                        ++ mStat.invalidLeaves;
520                }
521               
522        viewCell->mLeaves.push_back(leaf);
523
524                if (mUseAreaForPvs)
525                        viewCell->SetArea(tData.mProbability);
526                else
527                        viewCell->SetVolume(tData.mProbability);
528
529                leaf->mProbability = tData.mProbability;
530
531                EvaluateLeafStats(tData);               
532        }
533
534        //-- cleanup
535        tData.Clear();
536
537        return newNode;
538}
539
540
541
542
543BspNode *VspBspTree::SubdivideNode(VspBspTraversalData &tData,
544                                                                   VspBspTraversalData &frontData,
545                                                                   VspBspTraversalData &backData,
546                                                                   PolygonContainer &coincident)
547{
548        BspLeaf *leaf = dynamic_cast<BspLeaf *>(tData.mNode);
549       
550        // select subdivision plane
551        Plane3 splitPlane;
552       
553        int maxCostMisses = tData.mMaxCostMisses;
554
555        const bool success =
556                SelectPlane(splitPlane, leaf, tData, frontData, backData);
557
558        if (!success)
559        {
560                ++ maxCostMisses;
561
562                if (maxCostMisses > mTermMissTolerance)
563                {
564                        // terminate branch because of max cost
565                        ++ mStat.maxCostNodes;
566            return leaf;
567                }
568        }
569
570        mStat.nodes += 2;
571
572        //-- subdivide further
573        BspInterior *interior = new BspInterior(splitPlane);
574
575#ifdef _DEBUG
576        Debug << interior << endl;
577#endif
578
579        //-- the front and back traversal data is filled with the new values
580        frontData.mDepth = tData.mDepth + 1;
581        frontData.mPolygons = new PolygonContainer();
582        frontData.mRays = new RayInfoContainer();
583       
584        backData.mDepth = tData.mDepth + 1;
585        backData.mPolygons = new PolygonContainer();
586        backData.mRays = new RayInfoContainer();
587       
588        // subdivide rays
589        SplitRays(interior->GetPlane(),
590                          *tData.mRays,
591                          *frontData.mRays,
592                          *backData.mRays);
593
594        // subdivide polygons
595        SplitPolygons(interior->GetPlane(),
596                                  *tData.mPolygons,
597                      *frontData.mPolygons,
598                                  *backData.mPolygons,
599                                  coincident);
600
601
602        // how often was max cost ratio missed in this branch?
603        frontData.mMaxCostMisses = maxCostMisses;
604        backData.mMaxCostMisses = maxCostMisses;
605
606        // compute pvs
607        frontData.mPvs = ComputePvsSize(*frontData.mRays);
608        backData.mPvs = ComputePvsSize(*backData.mRays);
609
610        // split front and back node geometry and compute area
611       
612        // if geometry was not already computed
613        if (!frontData.mGeometry && !backData.mGeometry)
614        {
615                frontData.mGeometry = new BspNodeGeometry();
616                backData.mGeometry = new BspNodeGeometry();
617
618                tData.mGeometry->SplitGeometry(*frontData.mGeometry,
619                                                                           *backData.mGeometry,
620                                                                           interior->GetPlane(),
621                                                                           mBox,
622                                                                           mEpsilon);
623               
624                if (mUseAreaForPvs)
625                {
626                        frontData.mProbability = frontData.mGeometry->GetArea();
627                        backData.mProbability = backData.mGeometry->GetArea();
628                }
629                else
630                {
631                        frontData.mProbability = frontData.mGeometry->GetVolume();
632                        backData.mProbability = backData.mGeometry->GetVolume();
633                }
634        }
635       
636
637        //-- create front and back leaf
638
639        BspInterior *parent = leaf->GetParent();
640
641        // replace a link from node's parent
642        if (parent)
643        {
644                parent->ReplaceChildLink(leaf, interior);
645                interior->SetParent(parent);
646        }
647        else // new root
648        {
649                mRoot = interior;
650        }
651
652        // and setup child links
653        interior->SetupChildLinks(new BspLeaf(interior), new BspLeaf(interior));
654
655        frontData.mNode = interior->GetFront();
656        backData.mNode = interior->GetBack();
657
658        //DEL_PTR(leaf);
659        return interior;
660}
661
662
663void VspBspTree::AddToPvs(BspLeaf *leaf,
664                                                  const RayInfoContainer &rays,
665                                                  float &sampleContributions,
666                                                  int &contributingSamples)
667{
668  sampleContributions = 0;
669  contributingSamples = 0;
670 
671  RayInfoContainer::const_iterator it, it_end = rays.end();
672 
673  ViewCell *vc = leaf->GetViewCell();
674 
675  // add contributions from samples to the PVS
676  for (it = rays.begin(); it != it_end; ++ it)
677        {
678          float sc = 0.0f;
679          VssRay *ray = (*it).mRay;
680          bool madeContrib = false;
681          float contribution;
682          if (ray->mTerminationObject) {
683                if (vc->GetPvs().AddSample(ray->mTerminationObject, ray->mPdf, contribution))
684                  madeContrib = true;
685                sc += contribution;
686          }
687         
688          if (ray->mOriginObject) {
689                if (vc->GetPvs().AddSample(ray->mOriginObject, ray->mPdf, contribution))
690                  madeContrib = true;
691                sc += contribution;
692          }
693         
694          sampleContributions += sc;
695          if (madeContrib)
696                  ++ contributingSamples;
697               
698          //leaf->mVssRays.push_back(ray);
699        }
700}
701
702void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
703{
704        mSplitCandidates->clear();
705
706        int requestedSize = 2 * (int)(rays.size());
707        // creates a sorted split candidates array
708        if (mSplitCandidates->capacity() > 500000 &&
709                requestedSize < (int)(mSplitCandidates->capacity()/10) )
710        {
711        delete mSplitCandidates;
712                mSplitCandidates = new vector<SortableEntry>;
713        }
714
715        mSplitCandidates->reserve(requestedSize);
716
717        // insert all queries
718        for(RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
719        {
720                bool positive = (*ri).mRay->HasPosDir(axis);
721                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax,
722                                                                                                  (*ri).ExtrapOrigin(axis), (*ri).mRay));
723
724                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
725                                                                                                  (*ri).ExtrapTermination(axis), (*ri).mRay));
726        }
727
728        stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
729}
730
731float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
732                                                                                  const AxisAlignedBox3 &box,
733                                                                                  const int pvsSize,
734                                                                                  const int &axis,
735                                          float &position)
736{
737        int raysBack;
738        int raysFront;
739        int pvsBack;
740        int pvsFront;
741
742        SortSplitCandidates(rays, axis);
743
744        // go through the lists, count the number of objects left and right
745        // and evaluate the following cost funcion:
746        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
747
748        int rl = 0, rr = (int)rays.size();
749        int pl = 0, pr = pvsSize;
750
751        float minBox = box.Min(axis);
752        float maxBox = box.Max(axis);
753        float sizeBox = maxBox - minBox;
754
755        float minBand = minBox + 0.1f*(maxBox - minBox);
756        float maxBand = minBox + 0.9f*(maxBox - minBox);
757
758        float sum = rr*sizeBox;
759        float minSum = 1e20f;
760
761        Intersectable::NewMail();
762
763        // set all object as belonging to the fron pvs
764        for(RayInfoContainer::const_iterator ri = rays.begin(); ri != rays.end(); ++ ri)
765        {
766                if ((*ri).mRay->IsActive())
767                {
768                        Intersectable *object = (*ri).mRay->mTerminationObject;
769
770                        if (object)
771                        {
772                                if (!object->Mailed())
773                                {
774                                        object->Mail();
775                                        object->mCounter = 1;
776                                }
777                                else
778                                        ++ object->mCounter;
779                        }
780                }
781        }
782
783        Intersectable::NewMail();
784
785        for (vector<SortableEntry>::const_iterator ci = mSplitCandidates->begin();
786                ci < mSplitCandidates->end(); ++ ci)
787        {
788                VssRay *ray;
789
790                switch ((*ci).type)
791                {
792                        case SortableEntry::ERayMin:
793                                {
794                                        ++ rl;
795                                        ray = (VssRay *) (*ci).ray;
796
797                                        Intersectable *object = ray->mTerminationObject;
798
799                                        if (object && !object->Mailed())
800                                        {
801                                                object->Mail();
802                                                ++ pl;
803                                        }
804                                        break;
805                                }
806                        case SortableEntry::ERayMax:
807                                {
808                                        -- rr;
809                                        ray = (VssRay *) (*ci).ray;
810
811                                        Intersectable *object = ray->mTerminationObject;
812
813                                        if (object)
814                                        {
815                                                if (-- object->mCounter == 0)
816                                                        -- pr;
817                                        }
818
819                                        break;
820                                }
821                }
822
823                // Note: sufficient to compare size of bounding boxes of front and back side?
824                if ((*ci).value > minBand && (*ci).value < maxBand)
825                {
826                        sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
827
828                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
829                        // cout<<"cost= "<<sum<<endl;
830
831                        if (sum < minSum)
832                        {
833                                minSum = sum;
834                                position = (*ci).value;
835
836                                raysBack = rl;
837                                raysFront = rr;
838
839                                pvsBack = pl;
840                                pvsFront = pr;
841
842                        }
843                }
844        }
845
846        float oldCost = (float)pvsSize;
847        float newCost = mCtDivCi + minSum / sizeBox;
848        float ratio = newCost / oldCost;
849
850        //Debug << "costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
851        //     <<"\t q=(" << queriesBack << "," << queriesFront << ")\t r=(" << raysBack << "," << raysFront << ")" << endl;
852
853        return ratio;
854}
855
856
857float VspBspTree::SelectAxisAlignedPlane(Plane3 &plane,
858                                                                                 const VspBspTraversalData &tData,
859                                                                                 int &axis,
860                                                                                 BspNodeGeometry **frontGeom,
861                                                                                 BspNodeGeometry **backGeom,
862                                                                                 float &pFront,
863                                                                                 float &pBack,
864                                                                                 const bool useKdSplit)
865{
866        const bool useCostHeuristics = false;
867
868        //-- regular split
869        float nPosition[3];
870        float nCostRatio[3];
871        float nProbFront[3];
872        float nProbBack[3];
873
874        BspNodeGeometry *nFrontGeom[3];
875        BspNodeGeometry *nBackGeom[3];
876
877        int bestAxis = -1;
878
879        // create bounding box of node geometry
880        AxisAlignedBox3 box;
881        box.Initialize();
882       
883        //TODO: for kd split geometry already is box
884        if (1)
885        {
886                PolygonContainer::const_iterator it, it_end = tData.mGeometry->mPolys.end();
887
888                for(it = tData.mGeometry->mPolys.begin(); it < it_end; ++ it)
889                        box.Include(*(*it));
890        }
891        else
892        {
893                RayInfoContainer::const_iterator ri, ri_end = tData.mRays->end();
894
895                for(ri = tData.mRays->begin(); ri < ri_end; ++ ri)
896                        box.Include((*ri).ExtrapTermination());
897        }
898
899        const int sAxis = box.Size().DrivingAxis();
900
901        for (axis = 0; axis < 3; ++ axis)
902        {
903                nFrontGeom[axis] = new BspNodeGeometry();
904                nBackGeom[axis] = new BspNodeGeometry();
905
906                if (!mOnlyDrivingAxis || (axis == sAxis))
907                {
908                        if (!useCostHeuristics)
909                        {
910                                nPosition[axis] = (box.Min()[axis] + box.Max()[axis]) * 0.5f;
911                                Vector3 normal(0,0,0); normal[axis] = 1.0f;
912
913                                // allows faster split because we have axis aligned kd tree boxes
914                                if (useKdSplit)
915                                {
916                                        nCostRatio[axis] = EvalAxisAlignedSplitCost(tData,
917                                                                                                                                box,
918                                                                                                                                axis,
919                                                                                                                                nPosition[axis],
920                                                                                                                                nProbFront[axis],
921                                                                                                                                nProbBack[axis]);
922                                       
923                                        Vector3 pos;
924                                       
925                                        pos = box.Max(); pos[axis] = nPosition[axis];
926                                        AxisAlignedBox3 bBox(box.Min(), pos);
927                                        bBox.ExtractPolys(nBackGeom[axis]->mPolys);
928                                       
929                                        pos = box.Min(); pos[axis] = nPosition[axis];
930                                        AxisAlignedBox3 fBox(pos, box.Max());
931                                        fBox.ExtractPolys(nFrontGeom[axis]->mPolys);
932                                }
933                                else
934                                {
935                                        nCostRatio[axis] = SplitPlaneCost(Plane3(normal, nPosition[axis]),
936                                                                                                          tData, *nFrontGeom[axis], *nBackGeom[axis],
937                                                                                                          nProbFront[axis], nProbBack[axis]);
938                                }
939                        }
940                        else
941                        {
942                                nCostRatio[axis] =
943                                        BestCostRatioHeuristics(*tData.mRays,
944                                                                                    box,
945                                                                                        tData.mPvs,
946                                                                                        axis,
947                                                                                        nPosition[axis]);
948                        }
949
950                        if (bestAxis == -1)
951                        {
952                                bestAxis = axis;
953                        }
954
955                        else if (nCostRatio[axis] < nCostRatio[bestAxis])
956                        {
957                                bestAxis = axis;
958                        }
959
960                }
961        }
962
963        //-- assign values
964        axis = bestAxis;
965        pFront = nProbFront[bestAxis];
966        pBack = nProbBack[bestAxis];
967
968        // assign best split nodes geometry
969        *frontGeom = nFrontGeom[bestAxis];
970        *backGeom = nBackGeom[bestAxis];
971
972        // and delete other geometry
973        delete nFrontGeom[(bestAxis + 1) % 3];
974        delete nBackGeom[(bestAxis + 2) % 3];
975
976        //-- split plane
977    Vector3 normal(0,0,0); normal[bestAxis] = 1;
978        plane = Plane3(normal, nPosition[bestAxis]);
979
980        return nCostRatio[bestAxis];
981}
982
983
984float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
985                                                                                   const AxisAlignedBox3 &box,
986                                                                                   const int axis,
987                                                                                   const float &position,                                                                                 
988                                                                                   float &pFront,
989                                                                                   float &pBack) const
990{
991        int pvsTotal = 0;
992        int pvsFront = 0;
993        int pvsBack = 0;
994       
995        // create unique ids for pvs heuristics
996        GenerateUniqueIdsForPvs();
997
998        const int pvsSize = data.mPvs;
999
1000        // this is the main ray classification loop!
1001        for(RayInfoContainer::iterator ri = data.mRays->begin();
1002                ri != data.mRays->end(); ++ ri)
1003        {
1004                if (!(*ri).mRay->IsActive())
1005                        continue;
1006
1007                // determine the side of this ray with respect to the plane
1008                float t;
1009                int side = (*ri).ComputeRayIntersection(axis, position, t);
1010       
1011                AddObjToPvs((*ri).mRay->mTerminationObject, side, pvsFront, pvsBack, pvsTotal);
1012                AddObjToPvs((*ri).mRay->mOriginObject, side, pvsFront, pvsBack, pvsTotal);
1013        }
1014
1015        //-- pvs heuristics
1016        float pOverall;
1017
1018        // -- simplified computation for mid split
1019       
1020       
1021        pOverall = data.mProbability;
1022
1023        if (!mUseAreaForPvs)
1024        {   // volume
1025                pBack = pFront = pOverall * 0.5f;
1026               
1027#if 0
1028                // box length substitute for probability
1029                const float minBox = box.Min(axis);
1030                const float maxBox = box.Max(axis);
1031
1032                pBack = position - minBox;
1033                pFront = maxBox - position;
1034                pOverall = maxBox - minBox;
1035#endif
1036        }
1037        else //-- area substitute for probability
1038        {
1039                const int axis2 = (axis + 1) % 3;
1040                const int axis3 = (axis + 2) % 3;
1041
1042                const float faceArea =
1043                        (box.Max(axis2) - box.Min(axis2)) *
1044                        (box.Max(axis3) - box.Min(axis3));
1045
1046                pBack = pFront = pOverall * 0.5f + faceArea;
1047        }
1048
1049        //Debug << axis << " " << pvsSize << " " << pvsBack << " " << pvsFront << endl;
1050        //Debug << pFront << " " << pBack << " " << pOverall << endl;
1051
1052        const float newCost = pvsBack * pBack + pvsFront * pFront;
1053        const float oldCost = (float)pvsSize * pOverall;
1054
1055        return  (mCtDivCi + newCost) / oldCost;
1056}
1057
1058
1059
1060bool VspBspTree::SelectPlane(Plane3 &bestPlane,
1061                                                         BspLeaf *leaf,
1062                                                         VspBspTraversalData &data,
1063                                                         VspBspTraversalData &frontData,
1064                                                         VspBspTraversalData &backData)
1065{
1066        // simplest strategy: just take next polygon
1067        if (mSplitPlaneStrategy & RANDOM_POLYGON)
1068        {
1069        if (!data.mPolygons->empty())
1070                {
1071                        const int randIdx =
1072                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
1073                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
1074
1075                        bestPlane = nextPoly->GetSupportingPlane();
1076                        return true;
1077                }
1078        }
1079
1080        //-- use heuristics to find appropriate plane
1081
1082        // intermediate plane
1083        Plane3 plane;
1084        float lowestCost = MAX_FLOAT;
1085       
1086        // decides if the first few splits should be only axisAligned
1087        const bool onlyAxisAligned  =
1088                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
1089                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
1090                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
1091       
1092        const int limit = onlyAxisAligned ? 0 :
1093                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
1094
1095        float candidateCost;
1096
1097        int maxIdx = (int)data.mPolygons->size();
1098
1099        for (int i = 0; i < limit; ++ i)
1100        {
1101                //-- assure that no index is taken twice
1102                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
1103                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
1104
1105                // swap candidate to the end to avoid testing same plane
1106                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
1107                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
1108
1109                // evaluate current candidate
1110                BspNodeGeometry fGeom, bGeom;
1111                float fArea, bArea;
1112                plane = poly->GetSupportingPlane();
1113                candidateCost = SplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
1114               
1115                if (candidateCost < lowestCost)
1116                {
1117                        bestPlane = plane;
1118                        lowestCost = candidateCost;
1119                }
1120        }
1121
1122        //-- evaluate axis aligned splits
1123        int axis;
1124        BspNodeGeometry *fGeom, *bGeom;
1125        float pFront, pBack;
1126
1127        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
1128                                                                                   &fGeom, &bGeom,
1129                                                                                   pFront, pBack,
1130                                                                                   onlyAxisAligned);     
1131
1132        if (candidateCost < lowestCost)
1133        {       
1134                bestPlane = plane;
1135                lowestCost = candidateCost;
1136
1137                // assign already computed values
1138                // we can do this because we always save the
1139                // computed values from the axis aligned splits
1140               
1141                frontData.mGeometry = fGeom;
1142                backData.mGeometry = bGeom;
1143       
1144                frontData.mProbability = pFront;
1145                backData.mProbability = pBack;
1146               
1147                //! error also computed if cost ratio is missed
1148                ++ mStat.splits[axis];
1149        }
1150        else
1151        {
1152                DEL_PTR(fGeom);
1153                DEL_PTR(bGeom);
1154        }
1155
1156#ifdef _DEBUG
1157        Debug << "plane lowest cost: " << lowestCost << endl;
1158#endif
1159
1160        // cost ratio miss
1161        if (lowestCost > mTermMaxCostRatio)
1162                return false;
1163
1164        return true;
1165}
1166
1167
1168Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
1169{
1170        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1171
1172        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
1173        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
1174
1175        const Vector3 pt = (maxPt + minPt) * 0.5;
1176        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
1177
1178        return Plane3(normal, pt);
1179}
1180
1181
1182Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
1183{
1184        Vector3 pt[3];
1185
1186        int idx[3];
1187        int cmaxT = 0;
1188        int cminT = 0;
1189        bool chooseMin = false;
1190
1191        for (int j = 0; j < 3; ++ j)
1192        {
1193                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
1194
1195                if (idx[j] >= (int)rays.size())
1196                {
1197                        idx[j] -= (int)rays.size();
1198
1199                        chooseMin = (cminT < 2);
1200                }
1201                else
1202                        chooseMin = (cmaxT < 2);
1203
1204                RayInfo rayInf = rays[idx[j]];
1205                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
1206        }
1207
1208        return Plane3(pt[0], pt[1], pt[2]);
1209}
1210
1211Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
1212{
1213        Vector3 pt[3];
1214
1215        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1216        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
1217
1218        // check if rays different
1219        if (idx1 == idx2)
1220                idx2 = (idx2 + 1) % (int)rays.size();
1221
1222        const RayInfo ray1 = rays[idx1];
1223        const RayInfo ray2 = rays[idx2];
1224
1225        // normal vector of the plane parallel to both lines
1226        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
1227
1228        // vector from line 1 to line 2
1229        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
1230
1231        // project vector on normal to get distance
1232        const float dist = DotProd(vd, norm);
1233
1234        // point on plane lies halfway between the two planes
1235        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
1236
1237        return Plane3(norm, planePt);
1238}
1239
1240
1241inline void VspBspTree::GenerateUniqueIdsForPvs()
1242{
1243        Intersectable::NewMail(); sBackId = ViewCell::sMailId;
1244        Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
1245        Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
1246}
1247
1248
1249float VspBspTree::SplitPlaneCost(const Plane3 &candidatePlane,
1250                                                                 const VspBspTraversalData &data,
1251                                                                 BspNodeGeometry &geomFront,
1252                                                                 BspNodeGeometry &geomBack,
1253                                                                 float &pFront,
1254                                                                 float &pBack) const
1255{
1256        float cost = 0;
1257
1258        float sumBalancedRays = 0;
1259        float sumRaySplits = 0;
1260
1261        int pvsFront = 0;
1262        int pvsBack = 0;
1263
1264        // probability that view point lies in back / front node
1265        float pOverall = 0;
1266        pFront = 0;
1267        pBack = 0;
1268
1269        int raysFront = 0;
1270        int raysBack = 0;
1271        int totalPvs = 0;
1272
1273        int limit;
1274        bool useRand;
1275
1276        // choose test rays randomly if too much
1277        if ((int)data.mRays->size() > mMaxTests)
1278        {
1279                useRand = true;
1280                limit = mMaxTests;
1281        }
1282        else
1283        {
1284                useRand = false;
1285                limit = (int)data.mRays->size();
1286        }
1287       
1288        for (int i = 0; i < limit; ++ i)
1289        {
1290                const int testIdx = useRand ?
1291                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
1292                RayInfo rayInf = (*data.mRays)[testIdx];
1293
1294                float t;
1295                VssRay *ray = rayInf.mRay;
1296                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
1297
1298        if (cf >= 0)
1299                        ++ raysFront;
1300                if (cf <= 0)
1301                        ++ raysBack;
1302
1303                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1304                {
1305                        sumBalancedRays += cf;
1306                }
1307
1308                if (mSplitPlaneStrategy & BALANCED_RAYS)
1309                {
1310                        if (cf == 0)
1311                                ++ sumRaySplits;
1312                }
1313
1314                if (mSplitPlaneStrategy & PVS)
1315                {
1316                        // find front and back pvs for origing and termination object
1317                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
1318                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
1319                }
1320        }
1321
1322        const float raysSize = (float)data.mRays->size() + Limits::Small;
1323
1324        if (mSplitPlaneStrategy & PVS)
1325        {
1326                // create unique ids for pvs heuristics
1327                GenerateUniqueIdsForPvs();
1328
1329                // construct child geometry with regard to the candidate split plane
1330                data.mGeometry->SplitGeometry(geomFront,
1331                                                                          geomBack,
1332                                                                          candidatePlane,
1333                                                                          mBox,
1334                                                                          mEpsilon);
1335
1336                pOverall = data.mProbability;
1337
1338                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
1339                {
1340                        pFront = geomFront.GetVolume();
1341                        pBack = pOverall - geomFront.GetVolume();
1342                }
1343                else
1344                {
1345                        pFront = geomFront.GetArea();
1346                        pBack = geomBack.GetArea();
1347                }
1348        }
1349
1350
1351        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
1352                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
1353
1354        if (mSplitPlaneStrategy & BALANCED_RAYS)
1355                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
1356
1357        // pvs criterium
1358        if (mSplitPlaneStrategy & PVS)
1359        {
1360                const float oldCost = pOverall * (float)totalPvs + Limits::Small;
1361                cost += mPvsFactor * (pvsFront * pFront + pvsBack * pBack) / oldCost;
1362        }
1363
1364#ifdef _DEBUG
1365        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
1366                  << " frontpvs: " << pvsFront << " pFront: " << pFront
1367                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
1368#endif
1369
1370        // normalize cost by sum of linear factors
1371        return cost / (float)mCostNormalizer;
1372}
1373
1374
1375void VspBspTree::AddObjToPvs(Intersectable *obj,
1376                                                         const int cf,
1377                                                         int &frontPvs,
1378                                                         int &backPvs,
1379                                                         int &totalPvs) const
1380{
1381        if (!obj)
1382                return;
1383       
1384        if ((obj->mMailbox != sFrontId) &&
1385                (obj->mMailbox != sBackId) &&
1386                (obj->mMailbox != sFrontAndBackId))
1387        {
1388                ++ totalPvs;
1389        }
1390
1391        // TODO: does this really belong to no pvs?
1392        //if (cf == Ray::COINCIDENT) return;
1393
1394        // object belongs to both PVS
1395        if (cf >= 0)
1396        {
1397                if ((obj->mMailbox != sFrontId) &&
1398                        (obj->mMailbox != sFrontAndBackId))
1399                {
1400                        ++ frontPvs;
1401               
1402                        if (obj->mMailbox == sBackId)
1403                                obj->mMailbox = sFrontAndBackId;
1404                        else
1405                                obj->mMailbox = sFrontId;
1406                }
1407        }
1408
1409        if (cf <= 0)
1410        {
1411                if ((obj->mMailbox != sBackId) &&
1412                        (obj->mMailbox != sFrontAndBackId))
1413                {
1414                        ++ backPvs;
1415               
1416                        if (obj->mMailbox == sFrontId)
1417                                obj->mMailbox = sFrontAndBackId;
1418                        else
1419                                obj->mMailbox = sBackId;
1420                }
1421        }
1422}
1423
1424
1425void VspBspTree::CollectLeaves(vector<BspLeaf *> &leaves,
1426                                                           const bool onlyUnmailed,
1427                                                           const int maxPvsSize) const
1428{
1429        stack<BspNode *> nodeStack;
1430        nodeStack.push(mRoot);
1431
1432        while (!nodeStack.empty())
1433        {
1434                BspNode *node = nodeStack.top();
1435                nodeStack.pop();
1436               
1437                if (node->IsLeaf())
1438                {
1439                        // test if this leaf is in valid view space
1440                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1441                        if (leaf->TreeValid() &&
1442                                (!onlyUnmailed || !leaf->Mailed()) &&
1443                                ((maxPvsSize < 0) || (leaf->GetViewCell()->GetPvs().GetSize() <= maxPvsSize)))
1444                        {
1445                                leaves.push_back(leaf);
1446                        }
1447                }
1448                else
1449                {
1450                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1451
1452                        nodeStack.push(interior->GetBack());
1453                        nodeStack.push(interior->GetFront());
1454                }
1455        }
1456}
1457
1458
1459AxisAlignedBox3 VspBspTree::GetBoundingBox() const
1460{
1461        return mBox;
1462}
1463
1464
1465BspNode *VspBspTree::GetRoot() const
1466{
1467        return mRoot;
1468}
1469
1470
1471void VspBspTree::EvaluateLeafStats(const VspBspTraversalData &data)
1472{
1473        // the node became a leaf -> evaluate stats for leafs
1474        BspLeaf *leaf = dynamic_cast<BspLeaf *>(data.mNode);
1475
1476        // store maximal and minimal depth
1477        if (data.mDepth > mStat.maxDepth)
1478                mStat.maxDepth = data.mDepth;
1479
1480        if (data.mPvs > mStat.maxPvs)
1481                mStat.maxPvs = data.mPvs;
1482       
1483        if (data.mDepth < mStat.minDepth)
1484                mStat.minDepth = data.mDepth;
1485
1486        if (data.mDepth >= mTermMaxDepth)
1487                ++ mStat.maxDepthNodes;
1488        // accumulate rays to compute rays /  leaf
1489        mStat.accumRays += (int)data.mRays->size();
1490
1491        if (data.mPvs < mTermMinPvs)
1492                ++ mStat.minPvsNodes;
1493
1494        if ((int)data.mRays->size() < mTermMinRays)
1495                ++ mStat.minRaysNodes;
1496
1497        if (data.GetAvgRayContribution() > mTermMaxRayContribution)
1498                ++ mStat.maxRayContribNodes;
1499
1500        if (data.mProbability <= mTermMinProbability)
1501                ++ mStat.minProbabilityNodes;
1502       
1503        // accumulate depth to compute average depth
1504        mStat.accumDepth += data.mDepth;
1505
1506#ifdef _DEBUG
1507        Debug << "BSP stats: "
1508                  << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
1509                  << "PVS: " << data.mPvs << " (min: " << mTermMinPvs << "), "
1510          //              << "Area: " << data.mArea << " (min: " << mTermMinArea << "), "
1511                  << "#rays: " << (int)data.mRays->size() << " (max: " << mTermMinRays << "), "
1512                  << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
1513                  << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
1514#endif
1515}
1516
1517int VspBspTree::CastRay(Ray &ray)
1518{
1519        int hits = 0;
1520
1521        stack<BspRayTraversalData> tStack;
1522
1523        float maxt, mint;
1524
1525        if (!mBox.GetRaySegment(ray, mint, maxt))
1526                return 0;
1527
1528        Intersectable::NewMail();
1529
1530        Vector3 entp = ray.Extrap(mint);
1531        Vector3 extp = ray.Extrap(maxt);
1532
1533        BspNode *node = mRoot;
1534        BspNode *farChild = NULL;
1535
1536        while (1)
1537        {
1538                if (!node->IsLeaf())
1539                {
1540                        BspInterior *in = dynamic_cast<BspInterior *>(node);
1541
1542                        Plane3 splitPlane = in->GetPlane();
1543                        const int entSide = splitPlane.Side(entp);
1544                        const int extSide = splitPlane.Side(extp);
1545
1546                        if (entSide < 0)
1547                        {
1548                                node = in->GetBack();
1549
1550                                if(extSide <= 0) // plane does not split ray => no far child
1551                                        continue;
1552
1553                                farChild = in->GetFront(); // plane splits ray
1554
1555                        } else if (entSide > 0)
1556                        {
1557                                node = in->GetFront();
1558
1559                                if (extSide >= 0) // plane does not split ray => no far child
1560                                        continue;
1561
1562                                farChild = in->GetBack(); // plane splits ray
1563                        }
1564                        else // ray and plane are coincident
1565                        {
1566                                // WHAT TO DO IN THIS CASE ?
1567                                //break;
1568                                node = in->GetFront();
1569                                continue;
1570                        }
1571
1572                        // push data for far child
1573                        tStack.push(BspRayTraversalData(farChild, extp, maxt));
1574
1575                        // find intersection of ray segment with plane
1576                        float t;
1577                        extp = splitPlane.FindIntersection(ray.GetLoc(), extp, &t);
1578                        maxt *= t;
1579
1580                } else // reached leaf => intersection with view cell
1581                {
1582                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1583
1584                        if (!leaf->GetViewCell()->Mailed())
1585                        {
1586                                //ray.bspIntersections.push_back(Ray::VspBspIntersection(maxt, leaf));
1587                                leaf->GetViewCell()->Mail();
1588                                ++ hits;
1589                        }
1590
1591                        //-- fetch the next far child from the stack
1592                        if (tStack.empty())
1593                                break;
1594
1595                        entp = extp;
1596                        mint = maxt; // NOTE: need this?
1597
1598                        if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
1599                                break;
1600
1601                        BspRayTraversalData &s = tStack.top();
1602
1603                        node = s.mNode;
1604                        extp = s.mExitPoint;
1605                        maxt = s.mMaxT;
1606
1607                        tStack.pop();
1608                }
1609        }
1610
1611        return hits;
1612}
1613
1614
1615void VspBspTree::CollectViewCells(ViewCellContainer &viewCells, bool onlyValid) const
1616{
1617        ViewCell::NewMail();
1618       
1619        CollectViewCells(mRoot, onlyValid, viewCells, true);
1620}
1621
1622
1623void VspBspTree::ValidateTree()
1624{
1625        stack<BspNode *> nodeStack;
1626
1627        if (!mRoot)
1628                return;
1629
1630        nodeStack.push(mRoot);
1631       
1632        const bool addToUnbounded = false;
1633
1634        while (!nodeStack.empty())
1635        {
1636                BspNode *node = nodeStack.top();
1637                nodeStack.pop();
1638               
1639                if (node->IsLeaf())
1640                {
1641                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
1642
1643                        if (!addToUnbounded && node->TreeValid())
1644                        {
1645                                BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1646                       
1647                                if (!mViewCellsManager->CheckValid(viewCell))
1648                                {
1649                                        vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
1650                                        for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
1651                                        {
1652                                                BspLeaf *l = *it;
1653                                               
1654                                                l->SetTreeValid(false);
1655                                                PropagateUpValidity(l);
1656                                               
1657                                                if (addToUnbounded)
1658                                                        l->SetViewCell(GetOrCreateOutOfBoundsCell());
1659
1660                                                ++ mStat.invalidLeaves;
1661                                        }
1662
1663                                        // add to unbounded view cell or set to invalid
1664                                        if (addToUnbounded)
1665                                        {
1666                                                GetOrCreateOutOfBoundsCell()->GetPvs().AddPvs(viewCell->GetPvs());
1667                                                DEL_PTR(viewCell);
1668                                        }
1669                                        else
1670                                        {
1671                                                viewCell->SetValid(false);
1672                                        }
1673                                }
1674                        }
1675                }
1676                else
1677                {
1678                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1679               
1680                        nodeStack.push(interior->GetFront());
1681                        nodeStack.push(interior->GetBack());
1682                }
1683        }
1684}
1685
1686
1687void VspBspTree::CollectViewCells(BspNode *root,
1688                                                                  bool onlyValid,
1689                                                                  ViewCellContainer &viewCells,
1690                                                                  bool onlyUnmailed) const
1691{
1692        stack<BspNode *> nodeStack;
1693
1694        if (!root)
1695                return;
1696
1697        nodeStack.push(root);
1698       
1699        while (!nodeStack.empty())
1700        {
1701                BspNode *node = nodeStack.top();
1702                nodeStack.pop();
1703               
1704                if (node->IsLeaf())
1705                {
1706                        if (!onlyValid ||node->TreeValid())
1707                        {
1708                                ViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
1709                       
1710                                if (!onlyUnmailed || !viewCell->Mailed())
1711                                {
1712                                        viewCell->Mail();
1713                                        viewCells.push_back(viewCell);
1714                                }
1715                        }
1716                }
1717                else
1718                {
1719                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
1720               
1721                        nodeStack.push(interior->GetFront());
1722                        nodeStack.push(interior->GetBack());
1723                }
1724        }
1725}
1726
1727
1728float VspBspTree::AccumulatedRayLength(const RayInfoContainer &rays) const
1729{
1730        float len = 0;
1731
1732        RayInfoContainer::const_iterator it, it_end = rays.end();
1733
1734        for (it = rays.begin(); it != it_end; ++ it)
1735                len += (*it).SegmentLength();
1736
1737        return len;
1738}
1739
1740
1741int VspBspTree::SplitRays(const Plane3 &plane,
1742                                                  RayInfoContainer &rays,
1743                                                  RayInfoContainer &frontRays,
1744                                                  RayInfoContainer &backRays)
1745{
1746        int splits = 0;
1747
1748        while (!rays.empty())
1749        {
1750                RayInfo bRay = rays.back();
1751                rays.pop_back();
1752
1753                VssRay *ray = bRay.mRay;
1754                float t;
1755
1756                // get classification and receive new t
1757                const int cf = bRay.ComputeRayIntersection(plane, t);
1758
1759                switch (cf)
1760                {
1761                case -1:
1762                        backRays.push_back(bRay);
1763                        break;
1764                case 1:
1765                        frontRays.push_back(bRay);
1766                        break;
1767                case 0:
1768                        {
1769                                //-- split ray
1770                                //-- test if start point behind or in front of plane
1771                                const int side = plane.Side(bRay.ExtrapOrigin());
1772
1773                                if (side <= 0)
1774                                {
1775                                        backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1776                                        frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1777                                }
1778                                else
1779                                {
1780                                        frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
1781                                        backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
1782                                }
1783                        }
1784                        break;
1785                default:
1786                        Debug << "Should not come here" << endl;
1787                        break;
1788                }
1789        }
1790
1791        return splits;
1792}
1793
1794
1795void VspBspTree::ExtractHalfSpaces(BspNode *n, vector<Plane3> &halfSpaces) const
1796{
1797        BspNode *lastNode;
1798
1799        do
1800        {
1801                lastNode = n;
1802
1803                // want to get planes defining geometry of this node => don't take
1804                // split plane of node itself
1805                n = n->GetParent();
1806
1807                if (n)
1808                {
1809                        BspInterior *interior = dynamic_cast<BspInterior *>(n);
1810                        Plane3 halfSpace = dynamic_cast<BspInterior *>(interior)->GetPlane();
1811
1812            if (interior->GetFront() != lastNode)
1813                                halfSpace.ReverseOrientation();
1814
1815                        halfSpaces.push_back(halfSpace);
1816                }
1817        }
1818        while (n);
1819}
1820
1821
1822void VspBspTree::ConstructGeometry(BspNode *n,
1823                                                                   BspNodeGeometry &geom) const
1824{
1825        vector<Plane3> halfSpaces;
1826        ExtractHalfSpaces(n, halfSpaces);
1827
1828        PolygonContainer candidatePolys;
1829
1830        // bounded planes are added to the polygons (reverse polygons
1831        // as they have to be outfacing
1832        for (int i = 0; i < (int)halfSpaces.size(); ++ i)
1833        {
1834                Polygon3 *p = GetBoundingBox().CrossSection(halfSpaces[i]);
1835
1836                if (p->Valid(mEpsilon))
1837                {
1838                        candidatePolys.push_back(p->CreateReversePolygon());
1839                        DEL_PTR(p);
1840                }
1841        }
1842
1843        // add faces of bounding box (also could be faces of the cell)
1844        for (int i = 0; i < 6; ++ i)
1845        {
1846                VertexContainer vertices;
1847
1848                for (int j = 0; j < 4; ++ j)
1849                        vertices.push_back(mBox.GetFace(i).mVertices[j]);
1850
1851                candidatePolys.push_back(new Polygon3(vertices));
1852        }
1853
1854        for (int i = 0; i < (int)candidatePolys.size(); ++ i)
1855        {
1856                // polygon is split by all other planes
1857                for (int j = 0; (j < (int)halfSpaces.size()) && candidatePolys[i]; ++ j)
1858                {
1859                        if (i == j) // polygon and plane are coincident
1860                                continue;
1861
1862                        VertexContainer splitPts;
1863                        Polygon3 *frontPoly, *backPoly;
1864
1865                        const int cf =
1866                                candidatePolys[i]->ClassifyPlane(halfSpaces[j],
1867                                                                                                 mEpsilon);
1868
1869                        switch (cf)
1870                        {
1871                                case Polygon3::SPLIT:
1872                                        frontPoly = new Polygon3();
1873                                        backPoly = new Polygon3();
1874
1875                                        candidatePolys[i]->Split(halfSpaces[j],
1876                                                                                         *frontPoly,
1877                                                                                         *backPoly,
1878                                                                                         mEpsilon);
1879
1880                                        DEL_PTR(candidatePolys[i]);
1881
1882                                        if (frontPoly->Valid(mEpsilon))
1883                                                candidatePolys[i] = frontPoly;
1884                                        else
1885                                                DEL_PTR(frontPoly);
1886
1887                                        DEL_PTR(backPoly);
1888                                        break;
1889                                case Polygon3::BACK_SIDE:
1890                                        DEL_PTR(candidatePolys[i]);
1891                                        break;
1892                                // just take polygon as it is
1893                                case Polygon3::FRONT_SIDE:
1894                                case Polygon3::COINCIDENT:
1895                                default:
1896                                        break;
1897                        }
1898                }
1899
1900                if (candidatePolys[i])
1901                        geom.mPolys.push_back(candidatePolys[i]);
1902        }
1903}
1904
1905
1906void VspBspTree::ConstructGeometry(BspViewCell *vc,
1907                                                                   BspNodeGeometry &vcGeom) const
1908{
1909        vector<BspLeaf *> leaves = vc->mLeaves;
1910        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
1911
1912        for (it = leaves.begin(); it != it_end; ++ it)
1913                ConstructGeometry(*it, vcGeom);
1914}
1915
1916
1917typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
1918
1919
1920int VspBspTree::FindNeighbors(BspNode *n, vector<BspLeaf *> &neighbors,
1921                                                   const bool onlyUnmailed) const
1922{
1923        stack<bspNodePair> nodeStack;
1924       
1925        BspNodeGeometry nodeGeom;
1926        ConstructGeometry(n, nodeGeom);
1927       
1928        // split planes from the root to this node
1929        // needed to verify that we found neighbor leaf
1930        // TODO: really needed?
1931        vector<Plane3> halfSpaces;
1932        ExtractHalfSpaces(n, halfSpaces);
1933
1934
1935        BspNodeGeometry *rgeom = new BspNodeGeometry();
1936        ConstructGeometry(mRoot, *rgeom);
1937
1938        nodeStack.push(bspNodePair(mRoot, rgeom));
1939
1940        Debug << "here77" << endl;
1941
1942        while (!nodeStack.empty())
1943        {
1944                BspNode *node = nodeStack.top().first;
1945                BspNodeGeometry *geom = nodeStack.top().second;
1946
1947                nodeStack.pop();
1948
1949                if (node->IsLeaf())
1950                {       
1951                        Debug << "here22" << endl;
1952                        // test if this leaf is in valid view space
1953                        if (node->TreeValid() &&
1954                                (node != n) &&
1955                                (!onlyUnmailed || !node->Mailed()))
1956                        {
1957                                Debug << "here" << endl;
1958                                bool isAdjacent = true;
1959#if 1
1960
1961                                // test all planes of current node if still adjacent
1962                                for (int i = 0; (i < halfSpaces.size()) && isAdjacent; ++ i)
1963                                {
1964                                        const int cf =
1965                                                Polygon3::ClassifyPlane(geom->mPolys,
1966                                                                                                halfSpaces[i],
1967                                                                                                mEpsilon);
1968
1969                                        if (cf == Polygon3::BACK_SIDE)
1970                                        {
1971                                                isAdjacent = false;
1972                                        }
1973                                }
1974#else // TODO: why is this wrong??
1975                                // test all planes of current node if still adjacent
1976                                for (int i = 0; (i < (int)nodeGeom.mPolys.size()) && isAdjacent; ++ i)
1977                                {
1978                                        Debug << "here33" << endl;
1979                                        Polygon3 *poly = nodeGeom.mPolys[i];
1980
1981                                        const int cf =
1982                                                Polygon3::ClassifyPlane(geom->mPolys,
1983                                                                                                poly->GetSupportingPlane(),
1984                                                                                                mEpsilon);
1985
1986                                        if (cf == Polygon3::BACK_SIDE)
1987                                        {
1988                                                isAdjacent = false;
1989                                        }
1990                                }
1991#endif
1992                                Debug << "here2" << endl;
1993                                // neighbor was found
1994                                if (isAdjacent)
1995                                        neighbors.push_back(dynamic_cast<BspLeaf *>(node));
1996                        }
1997                        else
1998                        {
1999                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
2000
2001                                const int cf = Polygon3::ClassifyPlane(nodeGeom.mPolys,
2002                                                                                                           interior->GetPlane(),
2003                                                                                                           mEpsilon);
2004                       
2005                                BspNode *front = interior->GetFront();
2006                                BspNode *back = interior->GetBack();
2007           
2008                                BspNodeGeometry *fGeom = new BspNodeGeometry();
2009                                BspNodeGeometry *bGeom = new BspNodeGeometry();
2010
2011                                geom->SplitGeometry(*fGeom,
2012                                                                        *bGeom,
2013                                                                        interior->GetPlane(),
2014                                                                        mBox,
2015                                                                        mEpsilon);
2016               
2017                                if (cf == Polygon3::FRONT_SIDE)
2018                                {
2019                                        nodeStack.push(bspNodePair(interior->GetFront(), fGeom));
2020                                        DEL_PTR(bGeom);
2021                                }
2022                                else
2023                                {
2024                                        if (cf == Polygon3::BACK_SIDE)
2025                                        {
2026                                                nodeStack.push(bspNodePair(interior->GetBack(), bGeom));
2027                                                DEL_PTR(fGeom);
2028                                        }
2029                                        else
2030                                        {       // random decision
2031                                                nodeStack.push(bspNodePair(front, fGeom));
2032                                                nodeStack.push(bspNodePair(back, bGeom));
2033                                        }
2034                                }
2035                        }
2036                }
2037
2038                DEL_PTR(geom);
2039        }
2040
2041        return (int)neighbors.size();
2042}
2043
2044
2045BspLeaf *VspBspTree::GetRandomLeaf(const Plane3 &halfspace)
2046{
2047    stack<BspNode *> nodeStack;
2048        nodeStack.push(mRoot);
2049
2050        int mask = rand();
2051
2052        while (!nodeStack.empty())
2053        {
2054                BspNode *node = nodeStack.top();
2055                nodeStack.pop();
2056
2057                if (node->IsLeaf())
2058                {
2059                        return dynamic_cast<BspLeaf *>(node);
2060                }
2061                else
2062                {
2063                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2064                        BspNode *next;
2065                        BspNodeGeometry geom;
2066
2067                        // todo: not very efficient: constructs full cell everytime
2068                        ConstructGeometry(interior, geom);
2069
2070                        const int cf =
2071                                Polygon3::ClassifyPlane(geom.mPolys, halfspace, mEpsilon);
2072
2073                        if (cf == Polygon3::BACK_SIDE)
2074                                next = interior->GetFront();
2075                        else
2076                                if (cf == Polygon3::FRONT_SIDE)
2077                                        next = interior->GetFront();
2078                        else
2079                        {
2080                                // random decision
2081                                if (mask & 1)
2082                                        next = interior->GetBack();
2083                                else
2084                                        next = interior->GetFront();
2085                                mask = mask >> 1;
2086                        }
2087
2088                        nodeStack.push(next);
2089                }
2090        }
2091
2092        return NULL;
2093}
2094
2095BspLeaf *VspBspTree::GetRandomLeaf(const bool onlyUnmailed)
2096{
2097        stack<BspNode *> nodeStack;
2098
2099        nodeStack.push(mRoot);
2100
2101        int mask = rand();
2102
2103        while (!nodeStack.empty())
2104        {
2105                BspNode *node = nodeStack.top();
2106                nodeStack.pop();
2107
2108                if (node->IsLeaf())
2109                {
2110                        if ( (!onlyUnmailed || !node->Mailed()) )
2111                                return dynamic_cast<BspLeaf *>(node);
2112                }
2113                else
2114                {
2115                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2116
2117                        // random decision
2118                        if (mask & 1)
2119                                nodeStack.push(interior->GetBack());
2120                        else
2121                                nodeStack.push(interior->GetFront());
2122
2123                        mask = mask >> 1;
2124                }
2125        }
2126
2127        return NULL;
2128}
2129
2130int VspBspTree::ComputePvsSize(const RayInfoContainer &rays) const
2131{
2132        int pvsSize = 0;
2133
2134        RayInfoContainer::const_iterator rit, rit_end = rays.end();
2135
2136        Intersectable::NewMail();
2137
2138        for (rit = rays.begin(); rit != rays.end(); ++ rit)
2139        {
2140                VssRay *ray = (*rit).mRay;
2141
2142                if (ray->mOriginObject)
2143                {
2144                        if (!ray->mOriginObject->Mailed())
2145                        {
2146                                ray->mOriginObject->Mail();
2147                                ++ pvsSize;
2148                        }
2149                }
2150                if (ray->mTerminationObject)
2151                {
2152                        if (!ray->mTerminationObject->Mailed())
2153                        {
2154                                ray->mTerminationObject->Mail();
2155                                ++ pvsSize;
2156                        }
2157                }
2158        }
2159
2160        return pvsSize;
2161}
2162
2163float VspBspTree::GetEpsilon() const
2164{
2165        return mEpsilon;
2166}
2167
2168
2169int VspBspTree::SplitPolygons(const Plane3 &plane,
2170                                                          PolygonContainer &polys,
2171                                                          PolygonContainer &frontPolys,
2172                                                          PolygonContainer &backPolys,
2173                                                          PolygonContainer &coincident) const
2174{
2175        int splits = 0;
2176
2177        while (!polys.empty())
2178        {
2179                Polygon3 *poly = polys.back();
2180                polys.pop_back();
2181
2182                // classify polygon
2183                const int cf = poly->ClassifyPlane(plane, mEpsilon);
2184
2185                switch (cf)
2186                {
2187                        case Polygon3::COINCIDENT:
2188                                coincident.push_back(poly);
2189                                break;
2190                        case Polygon3::FRONT_SIDE:
2191                                frontPolys.push_back(poly);
2192                                break;
2193                        case Polygon3::BACK_SIDE:
2194                                backPolys.push_back(poly);
2195                                break;
2196                        case Polygon3::SPLIT:
2197                                backPolys.push_back(poly);
2198                                frontPolys.push_back(poly);
2199                                ++ splits;
2200                                break;
2201                        default:
2202                Debug << "SHOULD NEVER COME HERE\n";
2203                                break;
2204                }
2205        }
2206
2207        return splits;
2208}
2209
2210
2211int VspBspTree::CastLineSegment(const Vector3 &origin,
2212                                                                const Vector3 &termination,
2213                                                                vector<ViewCell *> &viewcells)
2214{
2215        int hits = 0;
2216        stack<BspRayTraversalData> tStack;
2217
2218        float mint = 0.0f, maxt = 1.0f;
2219
2220        Intersectable::NewMail();
2221
2222        Vector3 entp = origin;
2223        Vector3 extp = termination;
2224
2225        BspNode *node = mRoot;
2226        BspNode *farChild = NULL;
2227
2228        float t;
2229        while (1)
2230        {
2231                if (!node->IsLeaf())
2232                {
2233                        BspInterior *in = dynamic_cast<BspInterior *>(node);
2234
2235                        Plane3 splitPlane = in->GetPlane();
2236                       
2237                        const int entSide = splitPlane.Side(entp);
2238                        const int extSide = splitPlane.Side(extp);
2239
2240                        if (entSide < 0)
2241                        {
2242                                node = in->GetBack();
2243                                // plane does not split ray => no far child
2244                                if (extSide <= 0)
2245                                        continue;
2246
2247                                farChild = in->GetFront(); // plane splits ray
2248                        }
2249                        else if (entSide > 0)
2250                        {
2251                                node = in->GetFront();
2252
2253                                if (extSide >= 0) // plane does not split ray => no far child
2254                                        continue;
2255
2256                                farChild = in->GetBack(); // plane splits ray
2257                        }
2258                        else // ray end point on plane
2259                        {       // NOTE: what to do if ray is coincident with plane?
2260                                if (extSide < 0)
2261                                        node = in->GetBack();
2262                                else
2263                                        node = in->GetFront();
2264                                                               
2265                                continue; // no far child
2266                        }
2267
2268                        // push data for far child
2269                        tStack.push(BspRayTraversalData(farChild, extp));
2270
2271                        // find intersection of ray segment with plane
2272                        extp = splitPlane.FindIntersection(origin, extp, &t);
2273                }
2274                else
2275                {
2276                        // reached leaf => intersection with view cell
2277                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2278
2279                        if (!leaf->GetViewCell()->Mailed())
2280                        {
2281                                viewcells.push_back(leaf->GetViewCell());
2282                                leaf->GetViewCell()->Mail();
2283                                ++ hits;
2284                        }
2285
2286                        //-- fetch the next far child from the stack
2287                        if (tStack.empty())
2288                                break;
2289
2290                        entp = extp;
2291                       
2292                        BspRayTraversalData &s = tStack.top();
2293
2294                        node = s.mNode;
2295                        extp = s.mExitPoint;
2296
2297                        tStack.pop();
2298                }
2299        }
2300
2301        return hits;
2302}
2303
2304int VspBspTree::TreeDistance(BspNode *n1, BspNode *n2) const
2305{
2306        std::deque<BspNode *> path1;
2307        BspNode *p1 = n1;
2308
2309        // create path from node 1 to root
2310        while (p1)
2311        {
2312                if (p1 == n2) // second node on path
2313                        return (int)path1.size();
2314
2315                path1.push_front(p1);
2316                p1 = p1->GetParent();
2317        }
2318
2319        int depth = n2->GetDepth();
2320        int d = depth;
2321
2322        BspNode *p2 = n2;
2323
2324        // compare with same depth
2325        while (1)
2326        {
2327                if ((d < (int)path1.size()) && (p2 == path1[d]))
2328                        return (depth - d) + ((int)path1.size() - 1 - d);
2329
2330                -- d;
2331                p2 = p2->GetParent();
2332        }
2333
2334        return 0; // never come here
2335}
2336
2337BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
2338{
2339        if (node->IsLeaf())
2340                return node;
2341
2342        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2343
2344        BspNode *front = CollapseTree(interior->GetFront(), collapsed);
2345        BspNode *back = CollapseTree(interior->GetBack(), collapsed);
2346
2347        if (front->IsLeaf() && back->IsLeaf())
2348        {
2349                BspLeaf *frontLeaf = dynamic_cast<BspLeaf *>(front);
2350                BspLeaf *backLeaf = dynamic_cast<BspLeaf *>(back);
2351
2352                //-- collapse tree
2353                if (frontLeaf->GetViewCell() == backLeaf->GetViewCell())
2354                {
2355                        BspViewCell *vc = frontLeaf->GetViewCell();
2356
2357                        BspLeaf *leaf = new BspLeaf(interior->GetParent(), vc);
2358                        leaf->SetTreeValid(frontLeaf->TreeValid());
2359
2360                        // replace a link from node's parent
2361                        if (leaf->GetParent())
2362                                leaf->GetParent()->ReplaceChildLink(node, leaf);
2363                        else
2364                                mRoot = leaf;
2365
2366                        ++ collapsed;
2367                        delete interior;
2368
2369                        return leaf;
2370                }
2371        }
2372
2373        return node;
2374}
2375
2376
2377int VspBspTree::CollapseTree()
2378{
2379        int collapsed = 0;
2380       
2381        (void)CollapseTree(mRoot, collapsed);
2382
2383        // revalidate leaves
2384        RepairViewCellsLeafLists();
2385
2386        return collapsed;
2387}
2388
2389
2390void VspBspTree::RepairViewCellsLeafLists()
2391{
2392        // list not valid anymore => clear
2393        stack<BspNode *> nodeStack;
2394        nodeStack.push(mRoot);
2395
2396        ViewCell::NewMail();
2397
2398        while (!nodeStack.empty())
2399        {
2400                BspNode *node = nodeStack.top();
2401                nodeStack.pop();
2402
2403                if (node->IsLeaf())
2404                {
2405                        BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2406
2407                        BspViewCell *viewCell = leaf->GetViewCell();
2408
2409                        if (!viewCell->Mailed())
2410                        {
2411                                viewCell->mLeaves.clear();
2412                                viewCell->Mail();
2413                        }
2414
2415                        viewCell->mLeaves.push_back(leaf);
2416                }
2417                else
2418                {
2419                        BspInterior *interior = dynamic_cast<BspInterior *>(node);
2420
2421                        nodeStack.push(interior->GetFront());
2422                        nodeStack.push(interior->GetBack());
2423                }
2424        }
2425}
2426
2427
2428typedef pair<BspNode *, BspNodeGeometry *> bspNodePair;
2429
2430
2431int VspBspTree::CastBeam(Beam &beam)
2432{
2433    stack<bspNodePair> nodeStack;
2434        BspNodeGeometry *rgeom = new BspNodeGeometry();
2435        ConstructGeometry(mRoot, *rgeom);
2436
2437        nodeStack.push(bspNodePair(mRoot, rgeom));
2438 
2439        ViewCell::NewMail();
2440
2441        while (!nodeStack.empty())
2442        {
2443                BspNode *node = nodeStack.top().first;
2444                BspNodeGeometry *geom = nodeStack.top().second;
2445                nodeStack.pop();
2446               
2447                AxisAlignedBox3 box;
2448                box.Initialize();
2449                geom->IncludeInBox(box);
2450
2451                const int side = beam.ComputeIntersection(box);
2452               
2453                switch (side)
2454                {
2455                case -1:
2456                        CollectViewCells(node, true, beam.mViewCells, true);
2457                        break;
2458                case 0:
2459                       
2460                        if (node->IsLeaf())
2461                        {
2462                                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
2463                       
2464                                if (!leaf->GetViewCell()->Mailed() && leaf->TreeValid())
2465                                {
2466                                        leaf->GetViewCell()->Mail();
2467                                        beam.mViewCells.push_back(leaf->GetViewCell());
2468                                }
2469                        }
2470                        else
2471                        {
2472                                BspInterior *interior = dynamic_cast<BspInterior *>(node);
2473                       
2474                                BspNode *first = interior->GetFront();
2475                                BspNode *second = interior->GetBack();
2476           
2477                                BspNodeGeometry *firstGeom = new BspNodeGeometry();
2478                                BspNodeGeometry *secondGeom = new BspNodeGeometry();
2479
2480                                geom->SplitGeometry(*firstGeom,
2481                                                                        *secondGeom,
2482                                                                        interior->GetPlane(),
2483                                                                        mBox,
2484                                                                        mEpsilon);
2485
2486                                // decide on the order of the nodes
2487                                if (DotProd(beam.mPlanes[0].mNormal,
2488                                        interior->GetPlane().mNormal) > 0)
2489                                {
2490                                        swap(first, second);
2491                                        swap(firstGeom, secondGeom);
2492                                }
2493
2494                                nodeStack.push(bspNodePair(first, firstGeom));
2495                                nodeStack.push(bspNodePair(second, secondGeom));
2496                        }
2497                       
2498                        break;
2499                default:
2500                        // default: cull
2501                        break;
2502                }
2503               
2504                DEL_PTR(geom);
2505               
2506        }
2507
2508        return (int)beam.mViewCells.size();
2509}
2510
2511
2512bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) //const
2513{
2514        //-- change pointer to view cells of all leaves associated
2515        //-- with the previous view cells
2516        BspViewCell *fVc = l1->GetViewCell();
2517        BspViewCell *bVc = l2->GetViewCell();
2518
2519        BspViewCell *vc = dynamic_cast<BspViewCell *>(
2520                mViewCellsManager->MergeViewCells(*fVc, *bVc));
2521
2522        // if merge was unsuccessful
2523        if (!vc) return false;
2524
2525        // set new size of view cell
2526        if (mUseAreaForPvs)
2527                vc->SetArea(fVc->GetArea() + bVc->GetArea());
2528        else
2529                vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
2530       
2531        vector<BspLeaf *> fLeaves = fVc->mLeaves;
2532        vector<BspLeaf *> bLeaves = bVc->mLeaves;
2533
2534        vector<BspLeaf *>::const_iterator it;
2535
2536        //-- change view cells of all the other leaves the view cell belongs to
2537        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
2538        {
2539                (*it)->SetViewCell(vc);
2540                vc->mLeaves.push_back(*it);
2541        }
2542
2543        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
2544        {
2545                (*it)->SetViewCell(vc);
2546                vc->mLeaves.push_back(*it);
2547        }
2548
2549        vc->Mail();
2550
2551        // clean up old view cells
2552        if (0)
2553        {
2554                DEL_PTR(fVc);
2555                DEL_PTR(bVc);
2556        }
2557        else // throw them into old view cells container
2558        {
2559                fVc->mMailbox = -1;
2560                bVc->mMailbox = -1;
2561
2562                mOldViewCells.push_back(fVc);
2563                mOldViewCells.push_back(bVc);
2564
2565                mNewViewCells.push_back(vc);
2566        }
2567
2568        return true;
2569}
2570
2571
2572void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
2573{
2574        mViewCellsManager = vcm;
2575}
2576
2577
2578int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
2579{
2580        BspLeaf::NewMail();
2581       
2582        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
2583
2584        int candidates = 0;
2585
2586        // find merge candidates and push them into queue
2587        for (it = leaves.begin(); it != it_end; ++ it)
2588        {
2589                BspLeaf *leaf = *it;
2590               
2591                /// create leaf pvs (needed for post processing
2592                leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
2593
2594                BspMergeCandidate::sOverallCost +=
2595                        leaf->mProbability * leaf->mPvs->GetSize();
2596
2597                // the same leaves must not be part of two merge candidates
2598                leaf->Mail();
2599                vector<BspLeaf *> neighbors;
2600                FindNeighbors(leaf, neighbors, true);
2601
2602                vector<BspLeaf *>::const_iterator nit, nit_end = neighbors.end();
2603
2604                // TODO: test if at least one ray goes from one leaf to the other
2605                for (nit = neighbors.begin(); nit != nit_end; ++ nit)
2606                {
2607                        if ((*nit)->GetViewCell() != leaf->GetViewCell())
2608                        {
2609                                mMergeQueue.push(BspMergeCandidate(leaf, *nit));
2610                                ++ candidates;
2611                        }
2612                }
2613        }
2614
2615        Debug << "found " << candidates << " new merge candidates" << endl;
2616
2617        return (int)leaves.size();
2618}
2619
2620
2621int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
2622{
2623        vector<BspRay *> bspRays;
2624
2625        ViewCell::NewMail();
2626        long startTime = GetTime();
2627        ConstructBspRays(bspRays, rays);
2628        Debug << (int)bspRays.size() << " bsp rays constructed in "
2629                  << TimeDiff(startTime, GetTime()) * 1e-3f << " secs" << endl;
2630
2631        map<BspLeaf *, vector<BspLeaf*> > neighborMap;
2632        vector<BspIntersection>::const_iterator iit;
2633
2634        int numLeaves = 0;
2635       
2636        BspLeaf::NewMail();
2637
2638        for (int i = 0; i < (int)bspRays.size(); ++ i)
2639        { 
2640                BspRay *ray = bspRays[i];
2641       
2642                // traverse leaves stored in the rays and compare and
2643                // merge consecutive leaves (i.e., the neighbors in the tree)
2644                if (ray->intersections.size() < 2)
2645                        continue;
2646         
2647                iit = ray->intersections.begin();
2648                BspLeaf *leaf = (*(iit ++)).mLeaf;
2649               
2650                // create leaf pvs (needed for post processing)
2651                if (!leaf->mPvs)
2652                {
2653                        leaf->mPvs =
2654                                new ObjectPvs(leaf->GetViewCell()->GetPvs());
2655
2656                        BspMergeCandidate::sOverallCost +=
2657                                leaf->mProbability * leaf->mPvs->GetSize();
2658                       
2659                        ++ numLeaves;
2660                }
2661               
2662                // traverse intersections
2663                // consecutive leaves are neighbors => add them to queue
2664                for (; iit != ray->intersections.end(); ++ iit)
2665                {
2666                        // next pair
2667                        BspLeaf *prevLeaf = leaf;
2668            leaf = (*iit).mLeaf;
2669
2670                        // view space not valid or same view cell
2671                        if (!leaf->TreeValid() || !prevLeaf->TreeValid() ||
2672                                (leaf->GetViewCell() == prevLeaf->GetViewCell()))
2673                                continue;
2674
2675            // create leaf pvs (needed for post processing)
2676                        if (!leaf->mPvs)
2677                        {
2678                                leaf->mPvs =
2679                                        new ObjectPvs(leaf->GetViewCell()->GetPvs());
2680                               
2681                                BspMergeCandidate::sOverallCost +=
2682                                        leaf->mProbability * leaf->mPvs->GetSize();
2683
2684                                ++ numLeaves;
2685                        }
2686               
2687                        vector<BspLeaf *> &neighbors = neighborMap[leaf];
2688                       
2689                        bool found = false;
2690
2691                        // both leaves inserted in queue already =>
2692                        // look if double pair already exists
2693                        if (leaf->Mailed() && prevLeaf->Mailed())
2694                        {
2695                                vector<BspLeaf *>::const_iterator it, it_end = neighbors.end();
2696                               
2697                for (it = neighbors.begin(); !found && (it != it_end); ++ it)
2698                                        if (*it == prevLeaf)
2699                                                found = true; // already in queue
2700                        }
2701               
2702                        if (!found)
2703                        {
2704                                // this pair is not in map already
2705                                // => insert into the neighbor map and the queue
2706                                neighbors.push_back(prevLeaf);
2707                                neighborMap[prevLeaf].push_back(leaf);
2708
2709                                leaf->Mail();
2710                                prevLeaf->Mail();
2711               
2712                                mMergeQueue.push(BspMergeCandidate(leaf, prevLeaf));
2713                        }
2714        }
2715        }
2716        Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
2717        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
2718        Debug << "leaves in queue: " << numLeaves << endl;
2719        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
2720
2721        CLEAR_CONTAINER(bspRays);
2722
2723        //-- collect the leaves which haven't been found by ray casting
2724        if (0)
2725        {
2726                cout << "finding additional merge candidates using geometry" << endl;
2727                vector<BspLeaf *> leaves;
2728                CollectLeaves(leaves, true);
2729                Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
2730                CollectMergeCandidates(leaves);
2731        }
2732
2733        return numLeaves;
2734}
2735
2736
2737void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
2738                                                                  const VssRayContainer &rays)
2739{
2740        VssRayContainer::const_iterator it, it_end = rays.end();
2741
2742        for (it = rays.begin(); it != rays.end(); ++ it)
2743        {
2744                VssRay *vssRay = *it;
2745                BspRay *ray = new BspRay(vssRay);
2746
2747                ViewCellContainer viewCells;
2748
2749                Ray hray(*vssRay);
2750                float tmin = 0, tmax = 1.0;
2751                // matt TODO: remove this!!
2752                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
2753                if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
2754                        continue;
2755
2756                Vector3 origin = hray.Extrap(tmin);
2757                Vector3 termination = hray.Extrap(tmax);
2758       
2759                // cast line segment to get intersections with bsp leaves
2760                CastLineSegment(origin, termination, viewCells);
2761
2762                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2763                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
2764                {
2765                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
2766                        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
2767                        //NOTE: not sorted!
2768                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
2769                        {
2770                                ray->intersections.push_back(BspIntersection(0, *it));
2771                        }
2772                }
2773
2774                bspRays.push_back(ray);
2775        }
2776}
2777
2778
2779int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
2780{
2781        BspMergeCandidate::sMaxPvsSize = mViewCellsManager->GetMaxPvsSize();
2782        BspMergeCandidate::sUseArea = mUseAreaForPvs;
2783
2784        // the current view cells are kept in this container
2785        ViewCellContainer viewCells;
2786        ViewCell::NewMail();
2787        CollectViewCells(mRoot, true, viewCells, true);
2788        ViewCell::NewMail();
2789
2790        MergeStatistics mergeStats;
2791        mergeStats.Start();
2792        // TODO: REMOVE LATER for performance!
2793        const bool showMergeStats = true;
2794        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mStat.maxPvs;
2795        long startTime = GetTime();
2796
2797        if (mUseRaysForMerge)
2798        {
2799                cout << "collecting merge candidates (rays) ... ";
2800                mergeStats.nodes = CollectMergeCandidates(rays);
2801                cout << "fininshed collecting candidates" << endl;
2802        }
2803        else
2804        {
2805                vector<BspLeaf *> leaves;
2806                CollectLeaves(leaves);
2807                mergeStats.nodes = CollectMergeCandidates(leaves);
2808        }
2809       
2810
2811        mergeStats.collectTime = TimeDiff(startTime, GetTime());
2812        mergeStats.candidates = (int)mMergeQueue.size();
2813        startTime = GetTime();
2814
2815        int nViewCells = mStat.Leaves() - mStat.invalidLeaves;
2816        int pass = 0;
2817        const int nextPass = 200;
2818
2819        cout << "starting merge ... ";
2820
2821        //-- use priority queue to merge leaf pairs
2822        while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
2823                   (mMergeQueue.top().GetMergeCost() <
2824                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
2825        {
2826                /*Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
2827                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost
2828                          << " max ratio: " << mMergeMaxCostRatio << endl;*/
2829                BspMergeCandidate mc = mMergeQueue.top();
2830                mMergeQueue.pop();
2831
2832                // both view cells equal!
2833                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
2834                        continue;
2835
2836                if (mc.Valid())
2837                {
2838                        ViewCell::NewMail();
2839                        const float mergeCost = mc.GetMergeCost();
2840
2841                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
2842                                               
2843                       
2844                        // increase absolute merge cost
2845                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
2846                       
2847
2848                        if (showMergeStats)
2849                        {
2850                                if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
2851                                        ++ mergeStats.siblings;
2852
2853                                const int dist =
2854                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
2855                                if (dist > mergeStats.maxTreeDist)
2856                                        mergeStats.maxTreeDist = dist;
2857                                mergeStats.accTreeDist += dist;
2858
2859
2860                                if (((mergeStats.merged % nextPass) == 0) || (nViewCells == mMergeMinViewCells))
2861                                {
2862                                        mStats
2863                                                << "#Pass\n" << pass ++ << endl
2864                                                << "#Merged\n" << mergeStats.merged << endl
2865                                                << "#Viewcells\n" << nViewCells << endl
2866                                                << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
2867                                                << "#CurrentCost\n" << mergeCost << endl
2868                                                << "#RelCost\n" << mc.GetMergeCost() / BspMergeCandidate::sOverallCost << endl
2869                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl;
2870
2871                                        cout << "exporting view cells ... ";
2872                                                               
2873                               
2874                                        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
2875
2876                                        Debug << "here2111 " << viewCells.size() << endl;
2877                                        for (int i = 0; i < viewCells.size(); ++ i)
2878                                        {
2879                                                while (!viewCells.empty() && (viewCells.back()->mMailbox == -1))
2880                                                {
2881                                                        Debug << "here244" << endl;
2882                                                        viewCells.pop_back();
2883                                                }
2884
2885                                                // already merged view cell, put it to end of vector
2886                                                if ((i < viewCells.size()) && (viewCells[i]->mMailbox == -1))
2887                                                {
2888                                                        Debug << "here2" << endl;
2889                                                        swap(viewCells[i], viewCells.back());
2890                                                }
2891                                        }
2892                               
2893                                        cout << "finished" << endl;
2894                                        // not part of any leaf
2895                                        CLEAR_CONTAINER(mOldViewCells);
2896
2897                                        int newVcSize = (int)mNewViewCells.size();
2898                                        // add new view cells to container
2899                                        while (!mNewViewCells.empty())
2900                                        {
2901                                                viewCells.push_back(mNewViewCells.back());
2902                                                mNewViewCells.pop_back();
2903                                        }
2904
2905                                        char s[64];
2906                                        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
2907                                        Exporter *exporter = Exporter::GetExporter(s);
2908                               
2909                                        if (exporter)
2910                                        {
2911                                                exporter->ExportGeometry(objects);
2912                                                Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
2913                                                ViewCellContainer::const_iterator it, it_end = viewCells.end();
2914               
2915                                                int i = (int)viewCells.size();
2916                                                for (it = viewCells.begin(); it != it_end; ++ it)
2917                                                {
2918                                                        Material m = RandomMaterial();
2919                                                        if (i-- == newVcSize)
2920                                                        {
2921                                                                m.mDiffuseColor.r = 1;
2922                                                                m.mDiffuseColor.g = 0;
2923                                                                m.mDiffuseColor.b = 0;
2924                                                        }
2925                                                        exporter->SetForcedMaterial(m);
2926                                                        mViewCellsManager->ExportVcGeometry(exporter, *it);
2927                                                }
2928                                       
2929                                                delete exporter;
2930                                        }
2931                                        cout << "finished " << endl;
2932                                }
2933                        }
2934
2935                        -- nViewCells;
2936                        ++ mergeStats.merged;
2937                }
2938                // merge candidate not valid, because one of the leaves was already
2939                // merged with another one => validate and reinsert into queue
2940                else
2941                {
2942                        mc.SetValid();
2943                        mMergeQueue.push(mc);
2944                }
2945        }
2946
2947
2948        cout << "finished merge" << endl;
2949        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
2950        mergeStats.Stop();
2951
2952        if (showMergeStats)
2953                Debug << mergeStats << endl << endl;
2954       
2955
2956        //TODO: should return sample contributions?
2957        return mergeStats.merged;
2958}
2959
2960
2961ViewCell *VspBspTree::GetViewCell(const Vector3 &point)
2962{
2963  if (mRoot == NULL)
2964        return NULL;
2965 
2966  stack<BspNode *> nodeStack;
2967  nodeStack.push(mRoot);
2968 
2969  ViewCell *viewcell = NULL;
2970 
2971  while (!nodeStack.empty())  {
2972        BspNode *node = nodeStack.top();
2973        nodeStack.pop();
2974       
2975        if (node->IsLeaf()) {
2976          viewcell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
2977          break;
2978        } else {
2979         
2980          BspInterior *interior = dynamic_cast<BspInterior *>(node);
2981               
2982          // random decision
2983          if (interior->GetPlane().Side(point) < 0)
2984                nodeStack.push(interior->GetBack());
2985          else
2986                nodeStack.push(interior->GetFront());
2987        }
2988  }
2989 
2990  return viewcell;
2991}
2992
2993
2994int VspBspTree::RefineViewCells(const VssRayContainer &rays)
2995{
2996        int shuffled = 0;
2997
2998        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
2999        BspLeaf::NewMail();
3000
3001        // Use priority queue of remaining leaf pairs
3002        // These candidates either share the same view cells or
3003        // are border leaves which share a boundary.
3004        // We test if they can be shuffled, i.e.,
3005        // either one leaf is made part of one view cell or the other
3006        // leaf is made part of the other view cell. It is tested if the
3007        // remaining view cells are "better" than the old ones.
3008        while (!mMergeQueue.empty())
3009        {
3010                BspMergeCandidate mc = mMergeQueue.top();
3011                mMergeQueue.pop();
3012
3013                // both view cells equal or already shuffled
3014                if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()) ||
3015                        (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
3016                        continue;
3017               
3018                // candidate for shuffling
3019                const bool wasShuffled =
3020                        ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
3021               
3022                //-- stats
3023                if (wasShuffled)
3024                        ++ shuffled;
3025        }
3026
3027        return shuffled;
3028}
3029
3030
3031inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
3032{
3033        return pvs1.AddPvs(pvs2);
3034}
3035
3036/*inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
3037{
3038        ObjectPvs pvs;
3039        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
3040        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
3041                if (*it != l)
3042                        pvs.AddPvs(*(*it)->mPvs);
3043        return pvs.GetSize();
3044}*/
3045
3046inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
3047{
3048        return pvs1.SubtractPvs(pvs2);
3049}
3050
3051
3052float VspBspTree::GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const
3053{
3054        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
3055        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
3056        const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
3057
3058        if (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())
3059                return 1e15f;
3060
3061        float p1, p2;
3062
3063    if (mUseAreaForPvs)
3064        {
3065                p1 = vc1->GetArea() - leaf->mProbability;
3066                p2 = vc2->GetArea() + leaf->mProbability;
3067        }
3068        else
3069        {
3070                p1 = vc1->GetVolume() - leaf->mProbability;
3071                p2 = vc2->GetVolume() + leaf->mProbability;
3072        }
3073
3074        const float cost1 = pvs1 * p1;
3075        const float cost2 = pvs2 * p2;
3076
3077        return cost1 + cost2;
3078}
3079
3080
3081void VspBspTree::ShuffleLeaf(BspLeaf *leaf,
3082                                                         BspViewCell *vc1,
3083                                                         BspViewCell *vc2) const
3084{
3085        // compute new pvs and area
3086        vc1->GetPvs().SubtractPvs(*leaf->mPvs);
3087        vc2->GetPvs().AddPvs(*leaf->mPvs);
3088       
3089        if (mUseAreaForPvs)
3090        {
3091                vc1->SetArea(vc1->GetArea() - leaf->mProbability);
3092                vc2->SetArea(vc2->GetArea() + leaf->mProbability);
3093        }
3094        else
3095        {
3096                vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
3097                vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
3098        }
3099
3100        /// add to second view cell
3101        vc2->mLeaves.push_back(leaf);
3102
3103        // erase leaf from old view cell
3104        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
3105
3106        for (; *it != leaf; ++ it);
3107        vc1->mLeaves.erase(it);
3108
3109        /*vc1->GetPvs().mEntries.clear();
3110        for (; it != vc1->mLeaves.end(); ++ it)
3111        {
3112                if (*it == leaf)
3113                        vc1->mLeaves.erase(it);
3114                else
3115                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
3116        }*/
3117
3118        leaf->SetViewCell(vc2); // finally change view cell
3119}
3120
3121
3122bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
3123{
3124        BspViewCell *vc1 = leaf1->GetViewCell();
3125        BspViewCell *vc2 = leaf2->GetViewCell();
3126
3127        float cost1;
3128        float cost2;
3129
3130        if (mUseAreaForPvs)
3131        {
3132                cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
3133                cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
3134        }
3135        else
3136        {
3137                cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
3138                cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
3139        }
3140
3141        const float oldCost = cost1 + cost2;
3142       
3143        float shuffledCost1 = Limits::Infinity;
3144        float shuffledCost2 = Limits::Infinity;
3145
3146        // the view cell should not be empty after the shuffle
3147        if (vc1->mLeaves.size() > 1)
3148                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
3149        if (vc2->mLeaves.size() > 1)
3150                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
3151
3152        // shuffling unsuccessful
3153        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
3154                return false;
3155       
3156        if (shuffledCost1 < shuffledCost2)
3157        {
3158                ShuffleLeaf(leaf1, vc1, vc2);
3159                leaf1->Mail();
3160        }
3161        else
3162        {
3163                ShuffleLeaf(leaf2, vc2, vc1);
3164                leaf2->Mail();
3165        }
3166
3167        return true;
3168}
3169
3170
3171bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
3172{
3173        BspNode *node = mRoot;
3174
3175        while (1)
3176        {
3177                // early exit
3178                if (node->TreeValid())
3179                        return true;
3180
3181                if (node->IsLeaf())
3182                        return false;
3183                       
3184                BspInterior *in = dynamic_cast<BspInterior *>(node);
3185                                       
3186                if (in->GetPlane().Side(viewPoint) <= 0)
3187                {
3188                        node = in->GetBack();
3189                }
3190                else
3191                {
3192                        node = in->GetFront();
3193                }
3194        }
3195
3196        // should never come here
3197        return false;
3198}
3199
3200
3201void VspBspTree::PropagateUpValidity(BspNode *node)
3202{
3203        while (!node->IsRoot() && node->GetParent()->TreeValid())
3204        {
3205                node = node->GetParent();
3206                node->SetTreeValid(false);
3207        }
3208}
3209
3210
3211bool VspBspTree::Export(ofstream &stream)
3212{
3213        ExportNode(mRoot, stream);
3214
3215        return true;
3216}
3217
3218
3219void VspBspTree::ExportNode(BspNode *node, ofstream &stream)
3220{
3221        if (node->IsLeaf())
3222        {
3223                BspLeaf *leaf = dynamic_cast<BspLeaf *>(node);
3224                       
3225                int id = -1;
3226                if (leaf->GetViewCell() != mOutOfBoundsCell)
3227                        id = leaf->GetViewCell()->GetId();
3228
3229                stream << "<Leaf viewCellId=\"" << id << "\" />" << endl;
3230        }
3231        else
3232        {
3233                BspInterior *interior = dynamic_cast<BspInterior *>(node);
3234       
3235                Plane3 plane = interior->GetPlane();
3236                stream << "<Interior plane=\"" << plane.mNormal.x << " "
3237                           << plane.mNormal.y << " " << plane.mNormal.z << " "
3238                           << plane.mD << "\">" << endl;
3239
3240                ExportNode(interior->GetBack(), stream);
3241                ExportNode(interior->GetFront(), stream);
3242
3243                stream << "</Interior>" << endl;
3244        }
3245}
3246
3247/************************************************************************/
3248/*                BspMergeCandidate implementation                      */
3249/************************************************************************/
3250
3251
3252BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
3253mMergeCost(0),
3254mLeaf1(l1),
3255mLeaf2(l2),
3256mLeaf1Id(l1->GetViewCell()->mMailbox),
3257mLeaf2Id(l2->GetViewCell()->mMailbox)
3258{
3259        EvalMergeCost();
3260}
3261
3262
3263float BspMergeCandidate::GetCost(ViewCell *vc) const
3264{
3265        if (sUseArea)
3266                return vc->GetPvs().GetSize() * vc->GetArea();
3267
3268        return vc->GetPvs().GetSize() * vc->GetVolume();
3269}
3270
3271
3272float BspMergeCandidate::GetLeaf1Cost() const
3273{
3274        BspViewCell *vc = mLeaf1->GetViewCell();
3275        return GetCost(vc);
3276}
3277
3278
3279float BspMergeCandidate::GetLeaf2Cost() const
3280{
3281        BspViewCell *vc = mLeaf2->GetViewCell();
3282        return GetCost(vc);
3283}
3284
3285
3286void BspMergeCandidate::EvalMergeCost()
3287{
3288        //-- compute pvs difference
3289        BspViewCell *vc1 = mLeaf1->GetViewCell();
3290        BspViewCell *vc2 = mLeaf2->GetViewCell();
3291
3292        const int diff1 = vc1->GetPvs().Diff(vc2->GetPvs());
3293        const int newPvs = diff1 + vc1->GetPvs().GetSize();
3294
3295        //-- compute ratio of old cost
3296        //   (i.e., added size of left and right view cell times pvs size)
3297        //   to new rendering cost (i.e, size of merged view cell times pvs size)
3298        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
3299
3300    const float newCost = sUseArea ?
3301                (float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
3302                (float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
3303
3304
3305        if (newPvs > sMaxPvsSize) // strong penalty if pvs size too large
3306        {
3307                mMergeCost = 1e15f;
3308        }
3309        else
3310        {
3311                mMergeCost = newCost - oldCost;
3312        }
3313}
3314
3315
3316void BspMergeCandidate::SetLeaf1(BspLeaf *l)
3317{
3318        mLeaf1 = l;
3319}
3320
3321
3322void BspMergeCandidate::SetLeaf2(BspLeaf *l)
3323{
3324        mLeaf2 = l;
3325}
3326
3327
3328BspLeaf *BspMergeCandidate::GetLeaf1()
3329{
3330        return mLeaf1;
3331}
3332
3333
3334BspLeaf *BspMergeCandidate::GetLeaf2()
3335{
3336        return mLeaf2;
3337}
3338
3339
3340bool BspMergeCandidate::Valid() const
3341{
3342        return
3343                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
3344                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
3345}
3346
3347
3348float BspMergeCandidate::GetMergeCost() const
3349{
3350        return mMergeCost;
3351}
3352
3353
3354void BspMergeCandidate::SetValid()
3355{
3356        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
3357        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
3358
3359        EvalMergeCost();
3360}
3361
3362
3363/************************************************************************/
3364/*                  MergeStatistics implementation                      */
3365/************************************************************************/
3366
3367
3368void MergeStatistics::Print(ostream &app) const
3369{
3370        app << "===== Merge statistics ===============\n";
3371
3372        app << setprecision(4);
3373
3374        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
3375
3376        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
3377
3378        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
3379
3380        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
3381
3382        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
3383
3384        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
3385        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
3386
3387        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
3388
3389        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
3390
3391        app << "===== END OF BspTree statistics ==========\n";
3392}
Note: See TracBrowser for help on using the repository browser.