Changeset 580 for trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

Timestamp:

02/01/06 19:29:59 (18 years ago)

Author:

mattausch

Message:

implemented variance
started implementing merge history

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp (modified) (40 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -25 +25 @@
 const float VspBspTree::sLeastRaySplitsTable[] = {0, 0, 1, 1, 0};
 /** Evaluates split plane classification with respect to the plane's
-        contribution for balanced rays.
+        contribution for  balanced rays.
 */
 const float VspBspTree::sBalancedRaysTable[] = {1, -1, 0, 0, 0};
 
-ViewCellsManager *BspMergeCandidate::sViewCellsManager = NULL;
-//int BspMergeCandidate::sMaxPvsSize = 0;
-//int BspMergeCandidate::sMinPvsSize = 0;
 
 int VspBspTree::sFrontId = 0;
@@ -37 +34 @@
 int VspBspTree::sFrontAndBackId = 0;
 
-float BspMergeCandidate::sOverallCost = 0;
-float BspMergeCandidate::sExpectedCost = 0;
-float BspMergeCandidate::sVariance = 0;
-float BspMergeCandidate::sRenderCostWeight = 0.5f;
-bool BspMergeCandidate::sUseArea = false;
-int BspMergeCandidate::sNumViewCells = 0;
-
-//int upperPvsLimit = 120;
-//int lowerPvsLimit = 5;
 
 
@@ -64 +52 @@
 
 
-// penalty for pvs durint merge
-inline float EvalPvsPenaltyForMerge(const int pvs, 
-                                                                        const int lower,
-                                                                        const int upper)
-{
-        // clamp to minmax values
-        if (pvs < lower)
-                return (float)lower;
-        if (pvs > upper)
-                return (float)upper;
-
-        return (float)pvs;
-}
 
 
@@ -90 +65 @@
 mViewCellsManager(NULL),
 mOutOfBoundsCell(NULL),
-mStoreRays(false)
+mStoreRays(false),
+mRenderCostWeight(0.5)
 {
         bool randomize = false;
@@ -126 +102 @@
         // if only the driving axis is used for axis aligned split
         environment->GetBoolValue("VspBspTree.splitUseOnlyDrivingAxis", mOnlyDrivingAxis);
-
-        //-- merge options
-        environment->GetIntValue("VspBspTree.PostProcess.minViewCells", mMergeMinViewCells);
-        environment->GetFloatValue("VspBspTree.PostProcess.maxCostRatio", mMergeMaxCostRatio);
-        environment->GetBoolValue("VspBspTree.PostProcess.useRaysForMerge", mUseRaysForMerge);
-
-
+        
         //-- termination criteria for axis aligned split
         environment->GetFloatValue("VspBspTree.Termination.AxisAligned.maxRayContribution", 
@@ -142 +112 @@
         environment->GetFloatValue("VspBspTree.maxStaticMemory", mMaxMemory);
 
-        environment->GetBoolValue("VspBspTree.Visualization.exportMergedViewCells", mExportMergedViewCells);
-        environment->GetBoolValue("VspBspTree.PostProcess.exportMergeStats", mExportMergeStats);
-        
-
-        mStats.open("bspStats.log");
+        environment->GetFloatValue("VspBspTree.Construction.renderCostWeight", mRenderCostWeight);
+
+
+
 
         //-- debug output
+
         Debug << "******* VSP BSP options ******** " << endl;
     Debug << "max depth: " << mTermMaxDepth << endl;
@@ -162 +132 @@
         Debug << "max plane candidates: " << mMaxRayCandidates << endl;
         Debug << "randomize: " << randomize << endl;
-        Debug << "minimum view cells: " << mMergeMinViewCells << endl;
+//      Debug << "minimum view cells: " << mMergeMinViewCells << endl;
         Debug << "using area for pvs: " << mUseAreaForPvs << endl;
+        Debug << "render cost weight: " << mRenderCostWeight << endl;
         Debug << "Split plane strategy: ";
 
@@ -195 +166 @@
         Debug << endl;
 }
+
 
 BspViewCell *VspBspTree::GetOutOfBoundsCell()
@@ -249 +221 @@
         return (int)mesh->mFaces.size();
 }
+
 
 int VspBspTree::AddToPolygonSoup(const ViewCellContainer &viewCells,
@@ -273 +246 @@
         return polysSize;
 }
+
 
 int VspBspTree::AddToPolygonSoup(const ObjectContainer &objects,
@@ -310 +284 @@
 }
 
+
 void VspBspTree::Construct(const VssRayContainer &sampleRays,
                                                    AxisAlignedBox3 *forcedBoundingBox)
@@ -366 +341 @@
         
         Debug << "maximal pvs (i.e., pvs still considered as valid) : " << mViewCellsManager->GetMaxPvsSize() << endl;
+
         //-- store rays
         for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
@@ -572 +548 @@
                 }
                 
-        viewCell->mLeaves.push_back(leaf);
+        viewCell->mLeaf = leaf;
 
                 if (mUseAreaForPvs)
@@ -589 +565 @@
         return newNode;
 }
-
-
 
 
@@ -752 +726 @@
 }
 
+
 void VspBspTree::SortSplitCandidates(const RayInfoContainer &rays, const int axis)
 {
@@ -780 +755 @@
         stable_sort(mSplitCandidates->begin(), mSplitCandidates->end());
 }
+
 
 float VspBspTree::BestCostRatioHeuristics(const RayInfoContainer &rays,
@@ -1035 +1011 @@
 
 
+bool VspBspTree::SelectPlane(Plane3 &bestPlane,
+                                                         BspLeaf *leaf,
+                                                         VspBspTraversalData &data,
+                                                         VspBspTraversalData &frontData,
+                                                         VspBspTraversalData &backData)
+{
+        // simplest strategy: just take next polygon
+        if (mSplitPlaneStrategy & RANDOM_POLYGON)
+        {
+        if (!data.mPolygons->empty())
+                {
+                        const int randIdx = 
+                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
+                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
+
+                        bestPlane = nextPoly->GetSupportingPlane();
+                        return true;
+                }
+        }
+
+        //-- use heuristics to find appropriate plane
+
+        // intermediate plane
+        Plane3 plane;
+        float lowestCost = MAX_FLOAT;
+        
+        // decides if the first few splits should be only axisAligned
+        const bool onlyAxisAligned  = 
+                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
+                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
+                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
+        
+        const int limit = onlyAxisAligned ? 0 : 
+                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
+
+        float candidateCost;
+
+        int maxIdx = (int)data.mPolygons->size();
+
+        for (int i = 0; i < limit; ++ i)
+        {
+                // the already taken candidates are stored behind maxIdx
+                // => assure that no index is taken twice
+                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
+                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
+
+                // swap candidate to the end to avoid testing same plane
+                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
+                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
+
+                // evaluate current candidate
+                BspNodeGeometry fGeom, bGeom;
+                float fArea, bArea;
+                plane = poly->GetSupportingPlane();
+                candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
+                
+                if (candidateCost < lowestCost)
+                {
+                        bestPlane = plane;
+                        lowestCost = candidateCost;
+                }
+        }
+
+        //-- evaluate axis aligned splits
+        int axis;
+        BspNodeGeometry *fGeom, *bGeom;
+        float pFront, pBack;
+
+        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
+                                                                                   &fGeom, &bGeom, 
+                                                                                   pFront, pBack,
+                                                                                   data.mIsKdNode);      
+
+        bool isAxisAlignedSplit = false;
+
+        if (candidateCost < lowestCost)
+        {       
+                bestPlane = plane;
+                lowestCost = candidateCost;
+
+                // assign already computed values
+                // we can do this because we always save the
+                // computed values from the axis aligned splits         
+                frontData.mGeometry = fGeom;
+                backData.mGeometry = bGeom;
+        
+                frontData.mProbability = pFront;
+                backData.mProbability = pBack;
+                
+                //! error also computed if cost ratio is missed
+                ++ mBspStats.splits[axis];
+                isAxisAlignedSplit = true;
+        }
+        else
+        {
+                DEL_PTR(fGeom);
+                DEL_PTR(bGeom);
+        }
+
+        frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
+
+#ifdef _DEBUG
+        Debug << "plane lowest cost: " << lowestCost << endl;
+#endif
+
+        // cost ratio miss
+        if (lowestCost > mTermMaxCostRatio)
+                return false;
+
+        return true;
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
+{
+        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
+        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
+
+        const Vector3 pt = (maxPt + minPt) * 0.5;
+        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
+
+        return Plane3(normal, pt);
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
+{
+        Vector3 pt[3];
+
+        int idx[3];
+        int cmaxT = 0;
+        int cminT = 0;
+        bool chooseMin = false;
+
+        for (int j = 0; j < 3; ++ j)
+        {
+                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
+
+                if (idx[j] >= (int)rays.size())
+                {
+                        idx[j] -= (int)rays.size();
+
+                        chooseMin = (cminT < 2);
+                }
+                else
+                        chooseMin = (cmaxT < 2);
+
+                RayInfo rayInf = rays[idx[j]];
+                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
+        }
+
+        return Plane3(pt[0], pt[1], pt[2]);
+}
+
+
+Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
+{
+        Vector3 pt[3];
+
+        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
+
+        // check if rays different
+        if (idx1 == idx2)
+                idx2 = (idx2 + 1) % (int)rays.size();
+
+        const RayInfo ray1 = rays[idx1];
+        const RayInfo ray2 = rays[idx2];
+
+        // normal vector of the plane parallel to both lines
+        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
+
+        // vector from line 1 to line 2
+        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
+
+        // project vector on normal to get distance
+        const float dist = DotProd(vd, norm);
+
+        // point on plane lies halfway between the two planes
+        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
+
+        return Plane3(norm, planePt);
+}
+
+
+inline void VspBspTree::GenerateUniqueIdsForPvs()
+{
+        Intersectable::NewMail(); sBackId = Intersectable::sMailId;
+        Intersectable::NewMail(); sFrontId = Intersectable::sMailId;
+        Intersectable::NewMail(); sFrontAndBackId = Intersectable::sMailId;
+}
+
+
+float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
+                                                                         const VspBspTraversalData &data,
+                                                                         BspNodeGeometry &geomFront,
+                                                                         BspNodeGeometry &geomBack,
+                                                                         float &pFront,
+                                                                         float &pBack) const
+{
+        float cost = 0;
+
+        float sumBalancedRays = 0;
+        float sumRaySplits = 0;
+
+        int pvsFront = 0;
+        int pvsBack = 0;
+
+        // probability that view point lies in back / front node
+        float pOverall = 0;
+        pFront = 0;
+        pBack = 0;
+
+        int raysFront = 0;
+        int raysBack = 0;
+        int totalPvs = 0;
+
+        int limit;
+        bool useRand;
+
+        // choose test rays randomly if too much
+        if ((int)data.mRays->size() > mMaxTests)
+        {
+                useRand = true;
+                limit = mMaxTests;
+        }
+        else
+        {
+                useRand = false;
+                limit = (int)data.mRays->size();
+        }
+        
+        for (int i = 0; i < limit; ++ i)
+        {
+                const int testIdx = useRand ? 
+                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
+                RayInfo rayInf = (*data.mRays)[testIdx];
+
+                float t;
+                VssRay *ray = rayInf.mRay;
+                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
+
+        if (0)
+                {
+                        if (cf >= 0)
+                                ++ raysFront;
+                        if (cf <= 0)
+                                ++ raysBack;
+                }
+
+                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+                {
+                        sumBalancedRays += cf;
+                }
+
+                if (mSplitPlaneStrategy & BALANCED_RAYS)
+                {
+                        if (cf == 0)
+                                ++ sumRaySplits;
+                }
+
+                if (mSplitPlaneStrategy & PVS)
+                {
+                        // find front and back pvs for origing and termination object
+                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
+                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
+                }
+        }
+
+        const float raysSize = (float)data.mRays->size() + Limits::Small;
+
+        if (mSplitPlaneStrategy & PVS)
+        {
+                // create unique ids for pvs heuristics
+                GenerateUniqueIdsForPvs();
+
+                // construct child geometry with regard to the candidate split plane
+                data.mGeometry->SplitGeometry(geomFront,
+                                                                          geomBack,
+                                                                          candidatePlane,
+                                                                          mBox,
+                                                                          mEpsilon);
+
+                pOverall = data.mProbability;
+
+                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
+                {
+                        pFront = geomFront.GetVolume();
+                        pBack = pOverall - geomFront.GetVolume();
+                }
+                else
+                {
+                        pFront = geomFront.GetArea();
+                        pBack = geomBack.GetArea();
+                }
+        }
+
+
+        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
+                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
+
+        if (mSplitPlaneStrategy & BALANCED_RAYS)
+                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
+
+        // -- pvs rendering heuristics
+        if (mSplitPlaneStrategy & PVS)
+        {
+                const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
+                const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
+
+                // only render cost heuristics or combined with standard deviation
+                if (1)
+                {
+                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
+                const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+                        
+                        const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
+                        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
+
+                        float oldCost, newCost;
+
+                        if (1)
+                        {
+                                oldCost = oldRenderCost;
+                                newCost = newRenderCost;
+                        }
+                        else
+                        {
+                                // standard deviation is difference of back and front pvs
+                                const float expectedCost = 0.5f * (penaltyFront + penaltyBack);
+
+                                const float newDeviation = 0.5f * 
+                                        fabs(penaltyFront - expectedCost) + fabs(penaltyBack - expectedCost);
+
+                const float oldDeviation = penaltyOld + Limits::Small;
+
+                                newCost = mRenderCostWeight * newRenderCost + (1.0f - mRenderCostWeight) * newDeviation;
+                                oldCost = mRenderCostWeight * oldRenderCost + (1.0f - mRenderCostWeight) * oldDeviation;
+                        }
+
+                        cost += mPvsFactor * newCost / oldCost;
+                }
+                else
+                {
+                        //-- compute weighted sum of expected render cost and standard deviation
+                        
+                        //-- first compute expected render cost         
+                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
+                const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
+                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
+                        
+                        const float renderCostFront = penaltyFront * pFront;
+                        const float renderCostBack = penaltyBack * pBack;
+
+                        const float oldRenderCost = pOverall * (float)penaltyOld + Limits::Small;
+                        const float newRenderCost = renderCostFront + renderCostBack;
+
+
+                        //-- compute standard deviation
+                        const float expectedCost = 0.5f * (renderCostBack + renderCostFront);
+
+                        const float devFront = fabs(renderCostFront - expectedCost);
+                        
+                        const float devBack = fabs(renderCostBack - expectedCost);
+
+                        const float newDev = 0.5f * (devFront + devBack);
+                        const float oldDev = oldRenderCost * oldRenderCost;
+
+                        const float newCost = newRenderCost * mRenderCostWeight + newDev * (1.0f - mRenderCostWeight);
+                        const float oldCost = oldRenderCost * mRenderCostWeight + oldDev * (1.0f - mRenderCostWeight);
+
+                        cost += mPvsFactor * newCost / oldCost;
+
+                        // also try to equalize render differences between front and back pvs
+                        //const float oldCost = pOverall + Limits::Small;
+                        //float newCost = (float)abs(pvsFront - pvsBack);
+                        
+                }
+        }
+
+#ifdef _DEBUG
+        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
+                  << " frontpvs: " << pvsFront << " pFront: " << pFront
+                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
+#endif
+
+        // normalize cost by sum of linear factors
+        if(0)
+                return cost / (float)mCostNormalizer;
+        else
+                return cost;
+}
+
+
 float VspBspTree::EvalAxisAlignedSplitCost(const VspBspTraversalData &data,
                                                                                    const AxisAlignedBox3 &box,
@@ -1110 +1483 @@
 
         return  (mCtDivCi + newCost) / oldCost;
-}
-
-
-
-bool VspBspTree::SelectPlane(Plane3 &bestPlane,
-                                                         BspLeaf *leaf,
-                                                         VspBspTraversalData &data,
-                                                         VspBspTraversalData &frontData,
-                                                         VspBspTraversalData &backData)
-{
-        // simplest strategy: just take next polygon
-        if (mSplitPlaneStrategy & RANDOM_POLYGON)
-        {
-        if (!data.mPolygons->empty())
-                {
-                        const int randIdx = 
-                                (int)RandomValue(0, (Real)((int)data.mPolygons->size() - 1));
-                        Polygon3 *nextPoly = (*data.mPolygons)[randIdx];
-
-                        bestPlane = nextPoly->GetSupportingPlane();
-                        return true;
-                }
-        }
-
-        //-- use heuristics to find appropriate plane
-
-        // intermediate plane
-        Plane3 plane;
-        float lowestCost = MAX_FLOAT;
-        
-        // decides if the first few splits should be only axisAligned
-        const bool onlyAxisAligned  = 
-                (mSplitPlaneStrategy & AXIS_ALIGNED) &&
-                ((int)data.mRays->size() > mTermMinRaysForAxisAligned) &&
-                ((int)data.GetAvgRayContribution() < mTermMaxRayContriForAxisAligned);
-        
-        const int limit = onlyAxisAligned ? 0 : 
-                Min((int)data.mPolygons->size(), mMaxPolyCandidates);
-
-        float candidateCost;
-
-        int maxIdx = (int)data.mPolygons->size();
-
-        for (int i = 0; i < limit; ++ i)
-        {
-                // the already taken candidates are stored behind maxIdx
-                // => assure that no index is taken twice
-                const int candidateIdx = (int)RandomValue(0, (Real)(-- maxIdx));
-                Polygon3 *poly = (*data.mPolygons)[candidateIdx];
-
-                // swap candidate to the end to avoid testing same plane
-                std::swap((*data.mPolygons)[maxIdx], (*data.mPolygons)[candidateIdx]);
-                //Polygon3 *poly = (*data.mPolygons)[(int)RandomValue(0, (int)polys.size() - 1)];
-
-                // evaluate current candidate
-                BspNodeGeometry fGeom, bGeom;
-                float fArea, bArea;
-                plane = poly->GetSupportingPlane();
-                candidateCost = EvalSplitPlaneCost(plane, data, fGeom, bGeom, fArea, bArea);
-                
-                if (candidateCost < lowestCost)
-                {
-                        bestPlane = plane;
-                        lowestCost = candidateCost;
-                }
-        }
-
-        //-- evaluate axis aligned splits
-        int axis;
-        BspNodeGeometry *fGeom, *bGeom;
-        float pFront, pBack;
-
-        candidateCost = SelectAxisAlignedPlane(plane, data, axis,
-                                                                                   &fGeom, &bGeom, 
-                                                                                   pFront, pBack,
-                                                                                   data.mIsKdNode);      
-
-        bool isAxisAlignedSplit = false;
-
-        if (candidateCost < lowestCost)
-        {       
-                bestPlane = plane;
-                lowestCost = candidateCost;
-
-                // assign already computed values
-                // we can do this because we always save the
-                // computed values from the axis aligned splits         
-                frontData.mGeometry = fGeom;
-                backData.mGeometry = bGeom;
-        
-                frontData.mProbability = pFront;
-                backData.mProbability = pBack;
-                
-                //! error also computed if cost ratio is missed
-                ++ mBspStats.splits[axis];
-                isAxisAlignedSplit = true;
-        }
-        else
-        {
-                DEL_PTR(fGeom);
-                DEL_PTR(bGeom);
-        }
-
-        frontData.mIsKdNode = backData.mIsKdNode = (data.mIsKdNode && isAxisAlignedSplit);
-
-#ifdef _DEBUG
-        Debug << "plane lowest cost: " << lowestCost << endl;
-#endif
-
-        // cost ratio miss
-        if (lowestCost > mTermMaxCostRatio)
-                return false;
-
-        return true;
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane(const RayInfoContainer &rays) const
-{
-        const int candidateIdx = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-        const Vector3 minPt = rays[candidateIdx].ExtrapOrigin();
-        const Vector3 maxPt = rays[candidateIdx].ExtrapTermination();
-
-        const Vector3 pt = (maxPt + minPt) * 0.5;
-        const Vector3 normal = Normalize(rays[candidateIdx].mRay->GetDir());
-
-        return Plane3(normal, pt);
-}
-
-
-Plane3 VspBspTree::ChooseCandidatePlane2(const RayInfoContainer &rays) const
-{
-        Vector3 pt[3];
-
-        int idx[3];
-        int cmaxT = 0;
-        int cminT = 0;
-        bool chooseMin = false;
-
-        for (int j = 0; j < 3; ++ j)
-        {
-                idx[j] = (int)RandomValue(0, (Real)((int)rays.size() * 2 - 1));
-
-                if (idx[j] >= (int)rays.size())
-                {
-                        idx[j] -= (int)rays.size();
-
-                        chooseMin = (cminT < 2);
-                }
-                else
-                        chooseMin = (cmaxT < 2);
-
-                RayInfo rayInf = rays[idx[j]];
-                pt[j] = chooseMin ? rayInf.ExtrapOrigin() : rayInf.ExtrapTermination();
-        }
-
-        return Plane3(pt[0], pt[1], pt[2]);
-}
-
-Plane3 VspBspTree::ChooseCandidatePlane3(const RayInfoContainer &rays) const
-{
-        Vector3 pt[3];
-
-        int idx1 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-        int idx2 = (int)RandomValue(0, (Real)((int)rays.size() - 1));
-
-        // check if rays different
-        if (idx1 == idx2)
-                idx2 = (idx2 + 1) % (int)rays.size();
-
-        const RayInfo ray1 = rays[idx1];
-        const RayInfo ray2 = rays[idx2];
-
-        // normal vector of the plane parallel to both lines
-        const Vector3 norm = Normalize(CrossProd(ray1.mRay->GetDir(), ray2.mRay->GetDir()));
-
-        // vector from line 1 to line 2
-        const Vector3 vd = ray2.ExtrapOrigin() - ray1.ExtrapOrigin();
-
-        // project vector on normal to get distance
-        const float dist = DotProd(vd, norm);
-
-        // point on plane lies halfway between the two planes
-        const Vector3 planePt = ray1.ExtrapOrigin() + norm * dist * 0.5;
-
-        return Plane3(norm, planePt);
-}
-
-
-inline void VspBspTree::GenerateUniqueIdsForPvs()
-{
-        Intersectable::NewMail(); sBackId = ViewCell::sMailId;
-        Intersectable::NewMail(); sFrontId = ViewCell::sMailId;
-        Intersectable::NewMail(); sFrontAndBackId = ViewCell::sMailId;
-}
-
-
-float VspBspTree::EvalSplitPlaneCost(const Plane3 &candidatePlane,
-                                                                         const VspBspTraversalData &data,
-                                                                         BspNodeGeometry &geomFront,
-                                                                         BspNodeGeometry &geomBack,
-                                                                         float &pFront,
-                                                                         float &pBack) const
-{
-        float cost = 0;
-
-        float sumBalancedRays = 0;
-        float sumRaySplits = 0;
-
-        int pvsFront = 0;
-        int pvsBack = 0;
-
-        // probability that view point lies in back / front node
-        float pOverall = 0;
-        pFront = 0;
-        pBack = 0;
-
-        int raysFront = 0;
-        int raysBack = 0;
-        int totalPvs = 0;
-
-        int limit;
-        bool useRand;
-
-        // choose test rays randomly if too much
-        if ((int)data.mRays->size() > mMaxTests)
-        {
-                useRand = true;
-                limit = mMaxTests;
-        }
-        else
-        {
-                useRand = false;
-                limit = (int)data.mRays->size();
-        }
-        
-        for (int i = 0; i < limit; ++ i)
-        {
-                const int testIdx = useRand ? 
-                        (int)RandomValue(0, (Real)((int)data.mRays->size() - 1)) : i;
-                RayInfo rayInf = (*data.mRays)[testIdx];
-
-                float t;
-                VssRay *ray = rayInf.mRay;
-                const int cf = rayInf.ComputeRayIntersection(candidatePlane, t);
-
-        if (0)
-                {
-                        if (cf >= 0)
-                                ++ raysFront;
-                        if (cf <= 0)
-                                ++ raysBack;
-                }
-
-                if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                {
-                        sumBalancedRays += cf;
-                }
-
-                if (mSplitPlaneStrategy & BALANCED_RAYS)
-                {
-                        if (cf == 0)
-                                ++ sumRaySplits;
-                }
-
-                if (mSplitPlaneStrategy & PVS)
-                {
-                        // find front and back pvs for origing and termination object
-                        AddObjToPvs(ray->mTerminationObject, cf, pvsFront, pvsBack, totalPvs);
-                        AddObjToPvs(ray->mOriginObject, cf, pvsFront, pvsBack, totalPvs);
-                }
-        }
-
-        const float raysSize = (float)data.mRays->size() + Limits::Small;
-
-        if (mSplitPlaneStrategy & PVS)
-        {
-                // create unique ids for pvs heuristics
-                GenerateUniqueIdsForPvs();
-
-                // construct child geometry with regard to the candidate split plane
-                data.mGeometry->SplitGeometry(geomFront,
-                                                                          geomBack,
-                                                                          candidatePlane,
-                                                                          mBox,
-                                                                          mEpsilon);
-
-                pOverall = data.mProbability;
-
-                if (!mUseAreaForPvs) // use front and back cell areas to approximate volume
-                {
-                        pFront = geomFront.GetVolume();
-                        pBack = pOverall - geomFront.GetVolume();
-                }
-                else
-                {
-                        pFront = geomFront.GetArea();
-                        pBack = geomBack.GetArea();
-                }
-        }
-
-
-        if (mSplitPlaneStrategy & LEAST_RAY_SPLITS)
-                cost += mLeastRaySplitsFactor * sumRaySplits / raysSize;
-
-        if (mSplitPlaneStrategy & BALANCED_RAYS)
-                cost += mBalancedRaysFactor * fabs(sumBalancedRays) / raysSize;
-
-        // pvs criterium
-        if (mSplitPlaneStrategy & PVS)
-        {
-                if (1)
-                {
-                        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
-                        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
-                        
-                        const float penaltyOld = EvalPvsPenalty(totalPvs, lowerPvsLimit, upperPvsLimit);
-            
-                        const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-                        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
-                        
-                        const float oldCost = pOverall * (float)penaltyOld + Limits::Small;
-                        cost += mPvsFactor * (penaltyFront * pFront + penaltyBack * pBack) / oldCost;
-
-                }
-                else
-                {
-                        // try to equalize render differences
-                        //const float oldCost = pOverall * (float)totalPvs + Limits::Small;
-                        //float newCost = fabs(pvsFront * pFront - pvsBack * pBack);
-                        const float oldCost = pOverall + Limits::Small;
-                        float newCost = (float)abs(pvsFront - pvsBack);
-
-                        cost += mPvsFactor * newCost / oldCost;
-                }
-        }
-
-#ifdef _DEBUG
-        Debug << "totalpvs: " << data.mPvs << " ptotal: " << pOverall
-                  << " frontpvs: " << pvsFront << " pFront: " << pFront
-                  << " backpvs: " << pvsBack << " pBack: " << pBack << endl << endl;
-#endif
-
-        // normalize cost by sum of linear factors
-        if(0)
-                return cost / (float)mCostNormalizer;
-        else
-                return cost;
 }
 
@@ -1731 +1755 @@
                         {
                                 BspViewCell *viewCell = dynamic_cast<BspLeaf *>(node)->GetViewCell();
-                        
-                                vector<BspLeaf *>::const_iterator it, it_end = viewCell->mLeaves.end();
-                                for (it = viewCell->mLeaves.begin();it != it_end; ++ it)
+        
+                                ViewCellContainer leaves;
+                                mViewCellsManager->GetViewCellsTree()->CollectLeaves(viewCell, leaves);
+
+                                ViewCellContainer::const_iterator it, it_end = leaves.end();
+
+                                for (it = leaves.begin(); it != it_end; ++ it)
                                 {
-                                        BspLeaf *l = *it;
+                                        BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
                                         l->SetViewCell(GetOrCreateOutOfBoundsCell());
                                         ++ mBspStats.invalidLeaves;
@@ -2024 +2052 @@
                                                                    BspNodeGeometry &vcGeom) const
 {
-        vector<BspLeaf *> leaves = vc->mLeaves;
-        vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
+        ViewCellContainer leaves;
+        mViewCellsManager->GetViewCellsTree()->CollectLeaves(vc, leaves);
+
+        ViewCellContainer::const_iterator it, it_end = leaves.end();
 
         for (it = leaves.begin(); it != it_end; ++ it)
-                ConstructGeometry(*it, vcGeom);
+        {
+                BspLeaf *l = dynamic_cast<BspViewCell *>(*it)->mLeaf;
+                ConstructGeometry(l, vcGeom);
+        }
 }
 
@@ -2456 +2489 @@
 }
 
+
 BspNode *VspBspTree::CollapseTree(BspNode *node, int &collapsed)
 {
@@ -2499 +2533 @@
 {
         int collapsed = 0;
-        
+        //TODO
+#if VC_HISTORY
         (void)CollapseTree(mRoot, collapsed);
 
         // revalidate leaves
         RepairViewCellsLeafLists();
-
+#endif
         return collapsed;
 }
@@ -2527 +2562 @@
 
                         BspViewCell *viewCell = leaf->GetViewCell();
-
+        // TODO
+#if VC_HISTORY
                         if (!viewCell->Mailed())
                         {
@@ -2533 +2569 @@
                                 viewCell->Mail();
                         }
-
+        
                         viewCell->mLeaves.push_back(leaf);
+// TODO
+#endif
                 }
                 else
@@ -2631 +2669 @@
 
 
-bool VspBspTree::MergeViewCells(BspLeaf *l1, BspLeaf *l2) //const
-{
-        //-- change pointer to view cells of all leaves associated
-        //-- with the previous view cells
-        BspViewCell *fVc = l1->GetViewCell();
-        BspViewCell *bVc = l2->GetViewCell();
-
-        BspViewCell *vc = dynamic_cast<BspViewCell *>(
-                mViewCellsManager->MergeViewCells(*fVc, *bVc));
-
-        // if merge was unsuccessful
-        if (!vc) return false;
-
-        // set new size of view cell
-        if (mUseAreaForPvs)
-                vc->SetArea(fVc->GetArea() + bVc->GetArea());
-        else
-                vc->SetVolume(fVc->GetVolume() + bVc->GetVolume());
-        
-        vector<BspLeaf *> fLeaves = fVc->mLeaves;
-        vector<BspLeaf *> bLeaves = bVc->mLeaves;
-
-        vector<BspLeaf *>::const_iterator it;
-
-        //-- change view cells of all the other leaves the view cell belongs to
-        for (it = fLeaves.begin(); it != fLeaves.end(); ++ it)
-        {
-                (*it)->SetViewCell(vc);
-                vc->mLeaves.push_back(*it);
-        }
-
-        for (it = bLeaves.begin(); it != bLeaves.end(); ++ it)
-        {
-                (*it)->SetViewCell(vc);
-                vc->mLeaves.push_back(*it);
-        }
-
-        // important so other merge candidates sharing this view cell
-        // are notified that the merge cost must be updated!!
-        vc->Mail();
-
-        //-- clean up old view cells
-        if (mExportMergedViewCells)
-        {
-                DEL_PTR(fVc);
-                DEL_PTR(bVc);
-        }
-        else 
-        {
-                // old view cells container needed for visualization
-                //fVc->mMailbox = -1;
-                //bVc->mMailbox = -1;
-                fVc->SetId(-2);
-                bVc->SetId(-2);
-
-                mOldViewCells.push_back(fVc);
-                mOldViewCells.push_back(bVc);
-                
-                mNewViewCells.push_back(vc);
-        }
-
-        return true;
-}
-
-
 void VspBspTree::SetViewCellsManager(ViewCellsManager *vcm)
 {
@@ -2702 +2675 @@
 
 
-int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves)
+int VspBspTree::CollectMergeCandidates(const vector<BspLeaf *> leaves,
+                                                                           vector<MergeCandidate> &candidates)
 {
         BspLeaf::NewMail();
@@ -2708 +2682 @@
         vector<BspLeaf *>::const_iterator it, it_end = leaves.end();
 
-        int candidates = 0;
+        int numCandidates = 0;
 
         // find merge candidates and push them into queue
@@ -2714 +2688 @@
         {
                 BspLeaf *leaf = *it;
-                
-                /// create leaf pvs (needed for post processing)
-                leaf->mPvs = new ObjectPvs(leaf->GetViewCell()->GetPvs());
-
-                //const float rc = leaf->mProbability * (float)leaf->mPvs->GetSize();
-                //BspMergeCandidate::sOverallCost += rc;
                 
                 // the same leaves must not be part of two merge candidates
@@ -2733 +2701 @@
                         if ((*nit)->GetViewCell() != leaf->GetViewCell())
                         {
-                                BspMergeCandidate mc(leaf, *nit);
-                                mc.EvalMergeCost();
-
-                                mMergeQueue.push(mc);
-                                ++ candidates;
-                                if ((candidates % 1000) == 0)
+                                MergeCandidate mc(leaf->GetViewCell(), (*nit)->GetViewCell());
+                                candidates.push_back(mc);
+
+                                ++ numCandidates;
+                                if ((numCandidates % 1000) == 0)
                                 {
-                                        cout << "collected " << candidates << " merge candidates" << endl;
+                                        cout << "collected " << numCandidates << " merge candidates" << endl;
                                 }
                         }
@@ -2746 +2713 @@
         }
 
-        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
-        Debug << "leaves in queue: " << candidates << endl;
-        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
-
+        Debug << "merge queue: " << (int)candidates.size() << endl;
+        Debug << "leaves in queue: " << numCandidates << endl;
+        
 
         return (int)leaves.size();
@@ -2755 +2721 @@
 
 
-int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays)
+int VspBspTree::CollectMergeCandidates(const VssRayContainer &rays, 
+                                                                           vector<MergeCandidate> &candidates)
 {
         ViewCell::NewMail();
@@ -2775 +2742 @@
                 if (ray->mViewCells.size() < 2)
                         continue;
-          
+//TODO viewcellhierarchy
                 iit = ray->mViewCells.begin();
                 BspViewCell *bspVc = dynamic_cast<BspViewCell *>(*(iit ++));
-                BspLeaf *leaf = bspVc->mLeaves[0];
-                
-                // create leaf pvs (needed for post processing)
-                if (!leaf->mPvs)
-                {
-                        leaf->mPvs = 
-                                new ObjectPvs(leaf->GetViewCell()->GetPvs());
-
-                        //BspMergeCandidate::sOverallCost += 
-                        //      leaf->mProbability * leaf->mPvs->GetSize();
-                        
-                        ++ numLeaves;
-                }
+                BspLeaf *leaf = bspVc->mLeaf;
                 
                 // traverse intersections 
@@ -2799 +2754 @@
                         BspLeaf *prevLeaf = leaf;
                         bspVc = dynamic_cast<BspViewCell *>(*iit);
-            leaf = bspVc->mLeaves[0];
+            leaf = bspVc->mLeaf;
 
                         // view space not valid or same view cell
@@ -2806 +2761 @@
                                 continue;
 
-            // create leaf pvs (needed for post processing)
-                        if (!leaf->mPvs)
-                        {
-                                leaf->mPvs = 
-                                        new ObjectPvs(leaf->GetViewCell()->GetPvs());
-                                
-                                //BspMergeCandidate::sOverallCost += 
-                                //      leaf->mProbability * leaf->mPvs->GetSize();
-
-                                ++ numLeaves;
-                        }
-                
-                        vector<BspLeaf *> &neighbors = neighborMap[leaf];
+                vector<BspLeaf *> &neighbors = neighborMap[leaf];
                         
                         bool found = false;
@@ -2843 +2786 @@
                                 prevLeaf->Mail();
                 
-                                BspMergeCandidate mc(leaf, prevLeaf);
-                                mc.EvalMergeCost();
-
-                                mMergeQueue.push(mc);
-
-                                if (((int)mMergeQueue.size() % 1000) == 0)
+                                MergeCandidate mc(leaf->GetViewCell(), prevLeaf->GetViewCell());
+                                
+                                candidates.push_back(mc);
+
+                                if (((int)candidates.size() % 1000) == 0)
                                 {
-                                        cout << "collected " << (int)mMergeQueue.size() << " merge candidates" << endl;
+                                        cout << "collected " << (int)candidates.size() << " merge candidates" << endl;
                                 }
                         }
@@ -2857 +2799 @@
 
         Debug << "neighbormap size: " << (int)neighborMap.size() << endl;
-        Debug << "mergequeue: " << (int)mMergeQueue.size() << endl;
+        Debug << "merge queue: " << (int)candidates.size() << endl;
         Debug << "leaves in queue: " << numLeaves << endl;
-        Debug << "overall cost: " << BspMergeCandidate::sOverallCost << endl;
+
 
         //-- collect the leaves which haven't been found by ray casting
@@ -2868 +2810 @@
                 CollectLeaves(leaves, true);
                 Debug << "found " << (int)leaves.size() << " new leaves" << endl << endl;
-                CollectMergeCandidates(leaves);
+                CollectMergeCandidates(leaves, candidates);
         }
 
@@ -2875 +2817 @@
 
 
-void VspBspTree::ConstructBspRays(vector<BspRay *> &bspRays,
-                                                                  const VssRayContainer &rays)
-{
-        VssRayContainer::const_iterator it, it_end = rays.end();
-
-        for (it = rays.begin(); it != rays.end(); ++ it)
-        {
-                VssRay *vssRay = *it;
-                BspRay *ray = new BspRay(vssRay);
-
-                ViewCellContainer viewCells;
-
-                Ray hray(*vssRay);
-                float tmin = 0, tmax = 1.0;
-                // matt TODO: remove this!!
-                //hray.Init(ray.GetOrigin(), ray.GetDir(), Ray::LINE_SEGMENT);
-                if (!mBox.GetRaySegment(hray, tmin, tmax) || (tmin > tmax))
-                        continue;
-
-                Vector3 origin = hray.Extrap(tmin);
-                Vector3 termination = hray.Extrap(tmax);
-        
-                // cast line segment to get intersections with bsp leaves
-                CastLineSegment(origin, termination, viewCells);
-
-                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
-                {
-                        BspViewCell *vc = dynamic_cast<BspViewCell *>(*vit);
-                        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
-                        //NOTE: not sorted!
-                        for (it = vc->mLeaves.begin(); it != it_end; ++ it)
-                        {
-                                ray->intersections.push_back(BspIntersection(0, *it));
-                        }
-                }
-
-                bspRays.push_back(ray);
-        }
-}
-
-
-#if 1
-int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-        BspMergeCandidate::sViewCellsManager = mViewCellsManager;
-        BspMergeCandidate::sUseArea = mUseAreaForPvs;
-
-
-        //-- compute statistics values of initial view cells
-        mViewCellsManager->EvaluateRenderStatistics(BspMergeCandidate::sOverallCost, 
-                                                                                                BspMergeCandidate::sExpectedCost,
-                                                                                                BspMergeCandidate::sVariance);
-
-
-        //BspMergeCandidate::sExpectedCost = 
-        //      BspMergeCandidate::sOverallCost / BspMergeCandidate::sNumViewCells;
-
-
-        ViewCellsManager::PvsStatistics pvsStats;
-        mViewCellsManager->GetPvsStatistics(pvsStats);
-
-        static float expectedValue = pvsStats.avgPvs;
-        
-        // the current view cells are kept in this container
-        ViewCellContainer viewCells;
-        if (mExportMergedViewCells)
-        {
-                ViewCell::NewMail();
-                CollectViewCells(mRoot, true, viewCells, true);
-        }
-
-
-        ViewCell::NewMail();
-
-        MergeStatistics mergeStats;
-        mergeStats.Start();
-        
-        long startTime = GetTime();
-
-        cout << "collecting merge candidates ... " << endl;
-        
-        if (mUseRaysForMerge)
-        {
-                mergeStats.nodes = CollectMergeCandidates(rays);
-        }
-        else
-        {
-                vector<BspLeaf *> leaves;
-                CollectLeaves(leaves);
-                mergeStats.nodes = CollectMergeCandidates(leaves);
-        }
-        
-        cout << "fininshed collecting candidates" << endl;
-
-        mergeStats.collectTime = TimeDiff(startTime, GetTime());
-        mergeStats.candidates = (int)mMergeQueue.size();
-        startTime = GetTime();
-
-        // frequency stats are updated
-        const int statsOut = 100;
-
-        // number of view cells withouth the invalid ones
-        BspMergeCandidate::sNumViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
-
-        // passes are needed for statistics, because we don't want to record
-        // every merge
-        const int maxMergesPerPass = 100;
-        int pass = 0;
-
-        // maximal ratio of old expected render cost to expected render
-        // when the the render queue has to be reset.
-        const float ercMaxRatio = 0.7f;
-        
-        cout << "actual merge starts now ... " << endl;
-
-        
-        
-        //-- use priority queue to merge leaf pairs
-
-
-        while (!mMergeQueue.empty() && 
-                   (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
-                   (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-        {
-
-                int mergedPerPass = 0;
-                const float oldExpectedCost = BspMergeCandidate::sExpectedCost;
-                
-//#ifdef _DEBUG
-                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-                          << " max ratio: " << mMergeMaxCostRatio << endl
-                          << " expected value: " << oldExpectedCost << endl;
-//#endif
-
-                while (!mMergeQueue.empty() && 
-                           (BspMergeCandidate::sNumViewCells > mMergeMinViewCells) &&
-                           (ercMaxRatio > oldExpectedCost / BspMergeCandidate::sExpectedCost) &&
-                           (mMergeQueue.top().GetMergeCost() < mMergeMaxCostRatio * BspMergeCandidate::sOverallCost) &&
-                           (maxMergesPerPass < mergedPerPass));
-                {
-                                Debug << "erc max ratio" << ercMaxRatio << endl;
-
-                                BspMergeCandidate mc = mMergeQueue.top();
-                                mMergeQueue.pop();
-
-                                // both view cells equal!
-                                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-                                        continue;
-
-                                if (mc.Valid())
-                                {
-                                        ViewCell::NewMail();
-                                        const float currentMergeCost = mc.GetMergeCost();
-
-                                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-                                        
-                                        -- BspMergeCandidate::sNumViewCells;
-                                        ++ mergeStats.merged;
-                                        ++ mergedPerPass;
-
-                                        // increase absolute merge cost
-                                        BspMergeCandidate::sOverallCost += mc.GetRenderCost();
-                                        BspMergeCandidate::sVariance = mc.GetVarianceIncr();
-
-                                        BspMergeCandidate::sExpectedCost = 
-                                                BspMergeCandidate::sOverallCost / (float)BspMergeCandidate::sNumViewCells;
-
-                                        // stats
-                                        if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-                                                ++ mergeStats.siblings;
-
-                                        if (0)
-                                        {
-                                                const int dist = 
-                                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-                                                if (dist > mergeStats.maxTreeDist)
-                                                        mergeStats.maxTreeDist = dist;
-                                                mergeStats.accTreeDist += dist;
-                                        }
-
-                                        if ((mergeStats.merged % statsOut) == 0)
-                                        {
-                                                cout << "merged " << mergeStats.merged << " view cells" << endl;
-
-                                                mStats 
-                                                        << "#Pass\n" << pass << endl
-                                                        << "#Merged\n" << mergeStats.merged << endl 
-                                                        << "#Viewcells\n" << BspMergeCandidate::sNumViewCells << endl 
-                                                        << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
-                                                        << "#CurrentCost\n" << currentMergeCost << endl
-                                                        << "#RelativeCost\n" << currentMergeCost / BspMergeCandidate::sOverallCost << endl
-                                                        << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
-                                                        << "#MergedSiblings\n" << mergeStats.siblings << endl
-                                                        << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl
-                                                        << "#ExpectedCost\n" << BspMergeCandidate::sExpectedCost << endl
-                                                        << "#RatioExpectedCost\n" << oldExpectedCost / BspMergeCandidate::sExpectedCost << endl
-                                                        << "#variance\n" << BspMergeCandidate::sVariance << endl;
-
-                                                if (mExportMergedViewCells)
-                                                        ExportMergedViewCells(viewCells, objects, BspMergeCandidate::sNumViewCells);
-                                        }
-                                }
-                                else
-                                { 
-
-                                        // merge candidate not valid, because one of the leaves was already
-                                        // merged with another one => validate and reinsert into queue
-                                        mc.SetValid();
-                                        mMergeQueue.push(mc);
-                                }
-                }
-        
-
-                ++ pass;
-        }
-
-        mergeStats.overallCost = BspMergeCandidate::sOverallCost;
-
-        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
-        mergeStats.Stop();
-
-        Debug << mergeStats << endl << endl;
-        
-        // delete the view cells which were already merged
-        CLEAR_CONTAINER(mOldViewCells);
-        
-
-        //TODO: should return sample contributions?
-        return mergeStats.merged;
-}
-
-#else
-
-int VspBspTree::MergeViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-        BspMergeCandidate::sViewCellsManager = mViewCellsManager;
-        BspMergeCandidate::sUseArea = mUseAreaForPvs;
-
-        ViewCellsManager::PvsStatistics pvsStats;
-        mViewCellsManager->GetPvsStatistics(pvsStats);
-
-        static float expectedValue = pvsStats.avgPvs;
-        // the current view cells are kept in this container
-        ViewCellContainer viewCells;
-        if (mExportMergedViewCells)
-        {
-                ViewCell::NewMail();
-                CollectViewCells(mRoot, true, viewCells, true);
-        }
-        ViewCell::NewMail();
-
-        MergeStatistics mergeStats;
-        mergeStats.Start();
-        
-        //BspMergeCandidate::sOverallCost = mBox.SurfaceArea() * mBspStats.maxPvs;
-        long startTime = GetTime();
-
-        cout << "collecting merge candidates ... " << endl;
-        
-        if (mUseRaysForMerge)
-        {
-                mergeStats.nodes = CollectMergeCandidates(rays);
-        }
-        else
-        {
-                vector<BspLeaf *> leaves;
-                CollectLeaves(leaves);
-                mergeStats.nodes = CollectMergeCandidates(leaves);
-        }
-        
-        cout << "fininshed collecting candidates" << endl;
-
-        mergeStats.collectTime = TimeDiff(startTime, GetTime());
-        mergeStats.candidates = (int)mMergeQueue.size();
-        startTime = GetTime();
-
-        
-        // number of view cells withouth the invalid ones
-        int nViewCells = mBspStats.Leaves() - mBspStats.invalidLeaves;
-        BspMergeCandidate::sExpectedCost = BspMergeCandidate::sOverallCost / (float)nViewCells;
-
-        // passes are needed for statistics, because we don't want to record
-        // every merge
-        const int mergesPerPass = 100;
-        
-        int nextPass = 0;
-    int pass = 0;
-        
-        
-        Debug << "stats: " << nextStats << " " << statsIncr << endl;
-        cout << "actual merge starts now ... " << endl;
-
-        //-- use priority queue to merge leaf pairs
-        while (!mMergeQueue.empty() && (nViewCells > mMergeMinViewCells) &&
-                   (mMergeQueue.top().GetMergeCost() <
-                    mMergeMaxCostRatio * BspMergeCandidate::sOverallCost))
-        {
-#ifdef _DEBUG
-                Debug << "abs mergecost: " << mMergeQueue.top().GetMergeCost() << " rel mergecost: "
-                          << mMergeQueue.top().GetMergeCost() / BspMergeCandidate::sOverallCost 
-                          << " max ratio: " << mMergeMaxCostRatio << endl;
-#endif
-
-                BspMergeCandidate mc = mMergeQueue.top();
-                mMergeQueue.pop();
-
-
-                // both view cells equal!
-                if (mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell())
-                        continue;
-
-                if (mc.Valid())
-                {
-                        ViewCell::NewMail();
-                        const float mergeCost = mc.GetMergeCost();
-
-                        MergeViewCells(mc.GetLeaf1(), mc.GetLeaf2());
-                                        
-                        // increase absolute merge cost
-                        BspMergeCandidate::sOverallCost += mc.GetMergeCost();
-                        
-
-                        -- nViewCells;
-                        ++ mergeStats.merged;
-
-                        if ((mergeStats.merged % 500) == 0)
-                                cout << "merged " << mergeStats.merged << " view cells" << endl;
-
-                        // stats and visualizations
-                        if (mExportMergeStats)
-                        {
-                                if (mc.GetLeaf1()->IsSibling(mc.GetLeaf2()))
-                                        ++ mergeStats.siblings;
-
-                                if (0)
-                                const int dist = 
-                                        TreeDistance(mc.GetLeaf1(), mc.GetLeaf2());
-                                if (dist > mergeStats.maxTreeDist)
-                                        mergeStats.maxTreeDist = dist;
-                                mergeStats.accTreeDist += dist;
-
-                                if ((mergeStats.merged == nextPass) || (nViewCells == mMergeMinViewCells))
-                                {
-                                        nextPass += mergesPerPass;
-
-                                        mStats 
-                                                << "#Pass\n" << pass ++ << endl
-                                                << "#Merged\n" << mergeStats.merged << endl 
-                                                << "#Viewcells\n" << nViewCells << endl 
-                                                << "#OverallCost\n" << BspMergeCandidate::sOverallCost << endl
-                                                << "#CurrentCost\n" << mergeCost << endl
-                                                << "#RelativeCost\n" << mergeCost / BspMergeCandidate::sOverallCost << endl
-                                                << "#CurrentPvs\n" << mc.GetLeaf1()->GetViewCell()->GetPvs().GetSize() << endl
-                                                << "#MergedSiblings\n" << mergeStats.siblings << endl
-                                                << "#AvgTreeDist\n" << mergeStats.AvgTreeDist() << endl;
-
-                                                if (mExportMergedViewCells)
-                                                        ExportMergedViewCells(viewCells, objects, nViewCells);
-                                }
-                        }
-                }
-                // merge candidate not valid, because one of the leaves was already
-                // merged with another one => validate and reinsert into queue
-                else
-                { 
-                        mc.SetValid();
-                        mMergeQueue.push(mc);
-                }
-        }
-
-        mergeStats.overallCost = BspMergeCandidate::sOverallCost;
-
-        mergeStats.mergeTime = TimeDiff(startTime, GetTime());
-        mergeStats.Stop();
-
-        Debug << mergeStats << endl << endl;
-        
-        // delete the view cells which were already merged
-        CLEAR_CONTAINER(mOldViewCells);
-        
-
-        //TODO: should return sample contributions?
-        return mergeStats.merged;
-}
-#endif
 
 
@@ -3297 +2852 @@
 
 
-void VspBspTree::ExportMergedViewCells(ViewCellContainer &viewCells, 
-                                                                           const ObjectContainer &objects,
-                                                                           const int nViewCells)
-{
-        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-                                        
-        // find all already merged view cells and remove them from view cells
-        int i = 0;
-
-        while (1)
-        {
-                //while (!viewCells.empty() && (viewCells.back()->mMailbox == -1))
-                while (!viewCells.empty() && (viewCells.back()->GetId() == -2))
-                {
-                        //DEL_PTR(viewCells.back());
-                        viewCells.pop_back();
-                }
-                // all merged view cells have been found
-                if (i >= viewCells.size()) 
-                        break;
-
-                // already merged view cell, put it to end of vector
-                //if (viewCells[i]->mMailbox == -1)
-                if (viewCells[i]->GetId() == -2)
-                        swap(viewCells[i], viewCells.back());
-                
-                ++ i;
-        }
-
-        int newVcSize = 0;
-        // add new view cells to container only if they don't have been 
-        // merged in the mean time
-        while (!mNewViewCells.empty())
-        {
-                if (mNewViewCells.back()->GetId() != -2)
-                {
-                        viewCells.push_back(mNewViewCells.back());
-                        ++ newVcSize;
-                }
-
-                mNewViewCells.pop_back();
-        }
-
-        char s[64];
-        sprintf(s, "merged_viewcells%07d.x3d", nViewCells);
-        Exporter *exporter = Exporter::GetExporter(s);
-
-        if (exporter)
-        {
-                cout << "exporting " << nViewCells << " merged view cells ... ";
-                exporter->ExportGeometry(objects);
-                //Debug << "vc size " << (int)viewCells.size() << " merge queue size: " << (int)mMergeQueue.size() << endl;
-                ViewCellContainer::const_iterator it, it_end = viewCells.end();
-
-                int i = 0;
-                for (it = viewCells.begin(); it != it_end; ++ it)
-                {
-                        Material m;
-                        // assign special material to new view cells
-                        // new view cells are on the back of container
-                        if (i ++ >= (viewCells.size() - newVcSize))
-                        {
-                                //m = RandomMaterial();
-                                m.mDiffuseColor.r = RandomValue(0.5f, 1.0f);
-                                m.mDiffuseColor.g = RandomValue(0.5f, 1.0f);
-                                m.mDiffuseColor.b = RandomValue(0.5f, 1.0f);
-                        }
-                        else
-                        {
-                                float col = RandomValue(0.1f, 0.4f);
-                                m.mDiffuseColor.r = col;
-                                m.mDiffuseColor.g = col;
-                                m.mDiffuseColor.b = col;
-                        }
-
-                        exporter->SetForcedMaterial(m);
-                        mViewCellsManager->ExportVcGeometry(exporter, *it);
-                }
-                delete exporter;
-                cout << "finished" << endl;
-        }
-
-        // delete the view cells which were merged
-        CLEAR_CONTAINER(mOldViewCells);
-        // remove the new view cells
-        mNewViewCells.clear();
-}
-
-
-int VspBspTree::RefineViewCells(const VssRayContainer &rays, const ObjectContainer &objects)
-{
-        Debug << "refining " << (int)mMergeQueue.size() << " candidates " << endl;
-        
-        BspLeaf::NewMail();
-
-        // Use priority queue of remaining leaf pairs 
-        // The candidates either share the same view cells or
-        // are border leaves which share a boundary.
-        // We test if they can be shuffled, i.e.,
-        // either one leaf is made part of one view cell or the other
-        // leaf is made part of the other view cell. It is tested if the
-        // remaining view cells are "better" than the old ones.
-        //
-        // repeat the merging test numPasses times. For example, it could be
-        // that a shuffle only makes sense if another pair was shuffled before.
-        // Therefore we keep two queues and shift the merge candidates between
-        // those two queues until numPasses is reached
-        
-        queue<BspMergeCandidate> queue1;
-        queue<BspMergeCandidate> queue2;
-
-        queue<BspMergeCandidate> *shuffleQueue = &queue1;
-        queue<BspMergeCandidate> *backQueue = &queue2;
-
-        while (!mMergeQueue.empty())
-        {
-                BspMergeCandidate mc = mMergeQueue.top();
-                shuffleQueue->push(mc);
-                mMergeQueue.pop();
-        }
-
-        const int numPasses = 5;
-        int pass = 0;
-        int passShuffled = 0;
-        int shuffled = 0;
-
-        BspLeaf::NewMail();
-
-        do
-        {
-                passShuffled = 0;
-                while (!shuffleQueue->empty())
-                {
-                        BspMergeCandidate mc = shuffleQueue->front();
-                        shuffleQueue->pop();
-
-                        // both view cells equal or already shuffled
-                        if ((mc.GetLeaf1()->GetViewCell() == mc.GetLeaf2()->GetViewCell()))// ||
-                        //      (mc.GetLeaf1()->Mailed()) || (mc.GetLeaf2()->Mailed()))
-                                continue;
-                
-                        // candidate for shuffling
-                        const bool wasShuffled = 
-                                ShuffleLeaves(mc.GetLeaf1(), mc.GetLeaf2());
-                
-                        if (wasShuffled)
-                                ++ passShuffled;
-                        else
-                                backQueue->push(mc);
-                }
-
-                // now the back queue is the current shuffle queue
-                swap(shuffleQueue, backQueue);
-                shuffled += passShuffled;
-                Debug << "shuffled in pass: " << passShuffled << endl;
-        }
-        while (((++ pass) < numPasses) && passShuffled);
-
-        while (!shuffleQueue->empty())
-        {
-                shuffleQueue->pop();
-        }
-
-        return shuffled;
-}
-
-
-inline int AddedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
-{
-        return pvs1.AddPvs(pvs2);
-}
-
-
-// recomputes pvs size minus pvs of leaf l
-#if 0
-inline int SubtractedPvsSize(BspViewCell *vc, BspLeaf *l, const ObjectPvs &pvs2)
-{
-        ObjectPvs pvs;
-        vector<BspLeaf *>::const_iterator it, it_end = vc->mLeaves.end();
-        for (it = vc->mLeaves.begin(); it != vc->mLeaves.end(); ++ it)
-                if (*it != l)
-                        pvs.AddPvs(*(*it)->mPvs);
-        return pvs.GetSize();
-}
-#endif
-
-// computes pvs1 minus pvs2
-inline int SubtractedPvsSize(ObjectPvs pvs1, const ObjectPvs &pvs2)
-{
-        return pvs1.SubtractPvs(pvs2);
-}
-
-
-float VspBspTree::GetShuffledVcCost(BspLeaf *leaf, BspViewCell *vc1, BspViewCell *vc2) const
-{
-        //const int pvs1 = SubtractedPvsSize(vc1, leaf, *leaf->mPvs);
-        const int pvs1 = SubtractedPvsSize(vc1->GetPvs(), *leaf->mPvs);
-        const int pvs2 = AddedPvsSize(vc2->GetPvs(), *leaf->mPvs);
-
-        // don't shuffle leaves with pvs > max
-        if (pvs1 + pvs2 > mViewCellsManager->GetMaxPvsSize())
-                return 1e15f;
-
-#if 1
-        float p1, p2;
-
-    if (mUseAreaForPvs)
-        {
-                p1 = vc1->GetArea() - leaf->mProbability;
-                p2 = vc2->GetArea() + leaf->mProbability;
-        }
-        else
-        {
-                p1 = vc1->GetVolume() - leaf->mProbability;
-                p2 = vc2->GetVolume() + leaf->mProbability;
-        }
-
-        const float cost1 = pvs1 * p1;
-        const float cost2 = pvs2 * p2;
-#else
-        const float cost1 = pvs1;
-        const float cost2 = pvs2;
-#endif
-
-        return cost1 + cost2;
-}
-
-
-void VspBspTree::ShuffleLeaf(BspLeaf *leaf, 
-                                                         BspViewCell *vc1, 
-                                                         BspViewCell *vc2) const
-{
-        // compute new pvs and area
-        vc1->GetPvs().SubtractPvs(*leaf->mPvs);
-        vc2->GetPvs().AddPvs(*leaf->mPvs);
-        
-        if (mUseAreaForPvs)
-        {
-                vc1->SetArea(vc1->GetArea() - leaf->mProbability);
-                vc2->SetArea(vc2->GetArea() + leaf->mProbability);
-        }
-        else
-        {
-                vc1->SetVolume(vc1->GetVolume() - leaf->mProbability);
-                vc2->SetVolume(vc2->GetVolume() + leaf->mProbability);
-        }
-
-        /// add to second view cell
-        vc2->mLeaves.push_back(leaf);
-
-        // erase leaf from old view cell
-        vector<BspLeaf *>::iterator it = vc1->mLeaves.begin();
-
-        for (; *it != leaf; ++ it);
-        vc1->mLeaves.erase(it);
-
-        /*vc1->GetPvs().mEntries.clear();
-        for (; it != vc1->mLeaves.end(); ++ it)
-        {
-                if (*it == leaf)
-                        vc1->mLeaves.erase(it);
-                else
-                        vc1->GetPvs().AddPvs(*(*it)->mPvs);
-        }*/
-
-        leaf->SetViewCell(vc2); // finally change view cell
-}
-
-
-bool VspBspTree::ShuffleLeaves(BspLeaf *leaf1, BspLeaf *leaf2) const
-{
-        BspViewCell *vc1 = leaf1->GetViewCell();
-        BspViewCell *vc2 = leaf2->GetViewCell();
-
-        float cost1, cost2;
-
-#if 1
-        if (mUseAreaForPvs)
-        {
-                cost1 = vc1->GetPvs().GetSize() * vc1->GetArea();
-                cost2 = vc2->GetPvs().GetSize() * vc2->GetArea();
-        }
-        else
-        {
-                cost1 = vc1->GetPvs().GetSize() * vc1->GetVolume();
-                cost2 = vc2->GetPvs().GetSize() * vc2->GetVolume();
-        }
-#else
-        cost1 = vc1->GetPvs().GetSize(); 
-        cost2 = vc2->GetPvs().GetSize(); 
-#endif
-
-        const float oldCost = cost1 + cost2;
-        
-        float shuffledCost1 = Limits::Infinity;
-        float shuffledCost2 = Limits::Infinity;
-
-        // the view cell should not be empty after the shuffle
-        if (vc1->mLeaves.size() > 1)
-                shuffledCost1 = GetShuffledVcCost(leaf1, vc1, vc2);
-        if (vc2->mLeaves.size() > 1)
-                shuffledCost2 = GetShuffledVcCost(leaf2, vc2, vc1);
-
-        // shuffling unsuccessful
-        if ((oldCost <= shuffledCost1) && (oldCost <= shuffledCost2))
-                return false;
-        
-        if (shuffledCost1 < shuffledCost2)
-        {
-                ShuffleLeaf(leaf1, vc1, vc2);
-                leaf1->Mail();
-        }
-        else
-        {
-                ShuffleLeaf(leaf2, vc2, vc1);
-                leaf2->Mail();
-        }
-
-        return true;
-}
-
-
 bool VspBspTree::ViewPointValid(const Vector3 &viewPoint) const
 {
@@ -3713 +2946 @@
         }
 }
-
-
-/**************************************************************************/
-/*                  BspMergeCandidate implementation                      */
-/**************************************************************************/
-
-
-BspMergeCandidate::BspMergeCandidate(BspLeaf *l1, BspLeaf *l2):
-mRenderCost(0),
-mVarianceIncr(0),
-mLeaf1(l1),
-mLeaf2(l2),
-mLeaf1Id(l1->GetViewCell()->mMailbox),
-mLeaf2Id(l2->GetViewCell()->mMailbox)
-{
-        //EvalMergeCost();
-}
-
-
-float BspMergeCandidate::GetRenderCost(ViewCell *vc) const
-{
-        if (sUseArea)
-                return vc->GetPvs().GetSize() * vc->GetArea();
-
-        return vc->GetPvs().GetSize() * vc->GetVolume();
-}
-
-
-float BspMergeCandidate::GetLeaf1Cost() const
-{
-        BspViewCell *vc = mLeaf1->GetViewCell();
-
-        return GetRenderCost(vc);
-}
-
-
-float BspMergeCandidate::GetLeaf2Cost() const
-{
-        BspViewCell *vc = mLeaf2->GetViewCell();
-
-        return GetRenderCost(vc);
-}
-
-
-int ComputeMergedPvsSize(const ObjectPvs &pvs1, const ObjectPvs &pvs2)
-{
-        int pvs = pvs1.GetSize();
-
-        // compute new pvs size
-        ObjectPvsMap::const_iterator it, it_end =  pvs1.mEntries.end();
-
-        Intersectable::NewMail();
-
-        for (it = pvs1.mEntries.begin(); it != it_end; ++ it)
-        {
-                (*it).first->Mail();
-        }
-
-        it_end = pvs2.mEntries.end();
-
-        for (it = pvs2.mEntries.begin(); it != it_end; ++ it)
-        {
-                Intersectable *obj = (*it).first;
-                if (!obj->Mailed())
-                        ++ pvs;
-        }
-
-        return pvs;
-}
-
-
-
-void BspMergeCandidate::EvalMergeCost()
-{
-        //-- compute pvs difference
-        BspViewCell *vc1 = mLeaf1->GetViewCell();
-        BspViewCell *vc2 = mLeaf2->GetViewCell();
-
-        const int newPvs = ComputeMergedPvsSize(vc1->GetPvs(), vc2->GetPvs());
-        const float newPenalty = 
-                EvalPvsPenalty(newPvs, 
-                                           sViewCellsManager->GetMinPvsSize(),
-                                           sViewCellsManager->GetMaxPvsSize());
-
-        //-- compute ratio of old cost
-        //   (i.e., added size of left and right view cell times pvs size)
-        //   to new rendering cost (i.e, size of merged view cell times pvs size)
-        const float oldCost = GetLeaf1Cost() + GetLeaf2Cost();
-
-    const float newCost = sUseArea ? 
-                (float)newPvs * (vc1->GetArea() + vc2->GetArea()) :
-                (float)newPvs * (vc1->GetVolume() + vc2->GetVolume());
-
-
-        if (newPvs > sViewCellsManager->GetMaxPvsSize()) // strong penalty if pvs size too large
-        {
-                mRenderCost = 1e15;
-        }
-        else
-        {
-                mRenderCost = newCost - oldCost;
-        }
-
-        // merge cost also takes variance into account
-
-        const float oldVar1 = GetLeaf1Variance();
-        const float oldVar2 = GetLeaf2Variance();
-
-        const float newVar = (sExpectedCost - mRenderCost) * (sExpectedCost - mRenderCost);
-
-        mVarianceIncr = (newVar - oldVar1 - oldVar2) / sNumViewCells;
-        //mMergeCost = mRenderCost + fabs(newPenalty - BspMergeCandidate::sExpectedCost) ;
-}
-
-
-void BspMergeCandidate::SetLeaf1(BspLeaf *l)
-{
-        mLeaf1 = l;
-}
-
-
-void BspMergeCandidate::SetLeaf2(BspLeaf *l)
-{
-        mLeaf2 = l;
-}
-
-
-BspLeaf *BspMergeCandidate::GetLeaf1() const
-{
-        return mLeaf1;
-}
-
-
-BspLeaf *BspMergeCandidate::GetLeaf2() const
-{
-        return mLeaf2;
-}
-
-
-bool BspMergeCandidate::Valid() const
-{
-        return
-                (mLeaf1->GetViewCell()->mMailbox == mLeaf1Id) &&
-                (mLeaf2->GetViewCell()->mMailbox == mLeaf2Id);
-}
-
-
-float BspMergeCandidate::GetMergeCost() const
-{
-        return mRenderCost * sRenderCostWeight + mVarianceIncr * (1.0f - sRenderCostWeight);
-}
-
-
-float BspMergeCandidate::GetRenderCost() const
-{
-        return mRenderCost;
-}
-
-
-float BspMergeCandidate::GetVarianceIncr() const
-{
-        return mVarianceIncr;
-}
-
-float BspMergeCandidate::GetLeaf1Variance() const
-{
-        const float leafCost = GetLeaf1Cost();
-        
-        return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
-}
-
-
-float BspMergeCandidate::GetLeaf2Variance() const
-{
-        const float leafCost = GetLeaf2Cost();
-        
-        return (sExpectedCost - leafCost) * (sExpectedCost - leafCost);
-}
-
-
-void BspMergeCandidate::SetValid()
-{
-        mLeaf1Id = mLeaf1->GetViewCell()->mMailbox;
-        mLeaf2Id = mLeaf2->GetViewCell()->mMailbox;
-
-        EvalMergeCost();
-}
-
-
-/************************************************************************/
-/*                    MergeStatistics implementation                    */
-/************************************************************************/
-
-
-void MergeStatistics::Print(ostream &app) const
-{
-        app << "===== Merge statistics ===============\n";
-
-        app << setprecision(4);
-
-        app << "#N_CTIME ( Overall time [s] )\n" << Time() << " \n";
-
-        app << "#N_CCTIME ( Collect candidates time [s] )\n" << collectTime * 1e-3f << " \n";
-
-        app << "#N_MTIME ( Merge time [s] )\n" << mergeTime * 1e-3f << " \n";
-
-        app << "#N_NODES ( Number of nodes before merge )\n" << nodes << "\n";
-
-        app << "#N_CANDIDATES ( Number of merge candidates )\n" << candidates << "\n";
-
-        app << "#N_MERGEDSIBLINGS ( Number of merged siblings )\n" << siblings << "\n";
-
-        app << "#OVERALLCOST ( overall merge cost )\n" << overallCost << "\n";
-
-        app << "#N_MERGEDNODES ( Number of merged nodes )\n" << merged << "\n";
-
-        app << "#MAX_TREEDIST ( Maximal distance in tree of merged leaves )\n" << maxTreeDist << "\n";
-
-        app << "#AVG_TREEDIST ( Average distance in tree of merged leaves )\n" << AvgTreeDist() << "\n";
-
-        app << "===== END OF BspTree statistics ==========\n";
-}