Changeset 1287

Timestamp:

08/27/06 23:39:50 (18 years ago)

Author:

mattausch

Message:

implemented bv hierarchy

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• BvHierarchy.cpp (modified) (43 diffs)
• BvHierarchy.h (modified) (14 diffs)
• Environment.cpp (modified) (1 diff)
• Exporter.cpp (modified) (3 diffs)
• Exporter.h (modified) (2 diffs)
• HierarchyManager.cpp (modified) (14 diffs)
• HierarchyManager.h (modified) (4 diffs)
• Mesh.cpp (modified) (1 diff)
• OspTree.cpp (modified) (4 diffs)
• OspTree.h (modified) (2 diffs)
• Preprocessor.cpp (modified) (4 diffs)
• Preprocessor.h (modified) (1 diff)
• Preprocessor.vcproj (modified) (2 diffs)
• TestPreprocessor.vcproj (modified) (2 diffs)
• ViewCell.cpp (modified) (1 diff)
• ViewCellsManager.cpp (modified) (3 diffs)
• ViewCellsParser.cpp (modified) (20 diffs)
• ViewCellsParserXerces.h (modified) (2 diffs)
• VrmlExporter.cpp (modified) (1 diff)
• VspTree.cpp (modified) (1 diff)
• common.h (modified) (2 diffs)

GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.cpp

@@ -25 +25 @@
 
 static float debugVol = 0;
-int BvhNode::sMailId = 0;
+int BvhNode::sMailId = 2147483647;
 BvHierarchy *BvHierarchy::BvhSubdivisionCandidate::sBvHierarchy = NULL;
 
@@ -44 +44 @@
 
 BvhNode::BvhNode(const AxisAlignedBox3 &bbox):
-mBoundingBox(bbox)
+mParent(NULL), mBoundingBox(bbox)
 {
 }
@@ -91 +91 @@
 
 
-BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, BvhInterior *parent, const int numObjects):
+BvhLeaf::BvhLeaf(const AxisAlignedBox3 &bbox, 
+                                 BvhInterior *parent, 
+                                 const int numObjects):
 BvhNode(bbox, parent)
 {
@@ -115 +117 @@
 
 BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox):
-BvhNode(bbox)
+BvhNode(bbox), mFront(NULL), mBack(NULL)
 {
 }
@@ -121 +123 @@
 
 BvhInterior::BvhInterior(const AxisAlignedBox3 &bbox, BvhInterior *parent):
-BvhNode(bbox, parent)
+BvhNode(bbox, parent), mFront(NULL), mBack(NULL)
 {
 }
@@ -197 +199 @@
         Environment::GetSingleton()->GetIntValue("OspTree.Termination.maxLeaves", mTermMaxLeaves);
         Environment::GetSingleton()->GetIntValue("OspTree.Termination.minObjects", mTermMinObjects);
-        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinVolume);
+        Environment::GetSingleton()->GetFloatValue("OspTree.Termination.minProbability", mTermMinProbability);
         
         Environment::GetSingleton()->GetIntValue("OspTree.Termination.missTolerance", mTermMissTolerance);
@@ -233 +235 @@
 
     Debug << "max depth: " << mTermMaxDepth << endl;
-        Debug << "min probabiliy: " << mTermMinVolume<< endl;
+        Debug << "min probabiliy: " << mTermMinProbability<< endl;
         Debug << "min objects: " << mTermMinObjects << endl;
         Debug << "max cost ratio: " << mTermMaxCostRatio << endl;
@@ -278 +280 @@
         BvhInterior *node = new BvhInterior(tData.mBoundingBox, leaf->GetParent());
 
+        cout << "here55 " << tData.mBoundingBox << " | " << node->GetBoundingBox() << endl;
 
         //-- the front and back traversal data is filled with the new values
 
         frontData.mDepth = backData.mDepth = tData.mDepth + 1;
-                
-        // frontData.mRays = new RayInfoContainer();
-        // backData.mRays = new RayInfoContainer();
-
-        frontData.mBoundingBox = ComputeBoundingBox(frontObjects);
-        backData.mBoundingBox = ComputeBoundingBox(backObjects);
+
+        frontData.mBoundingBox = ComputeBoundingBox(frontObjects, &(tData.mBoundingBox));
+        backData.mBoundingBox = ComputeBoundingBox(backObjects, &(tData.mBoundingBox));
         //RemoveParentViewCellsPvs(leaf, *tData.mRays);
-
 
         /////////////
         //-- create front and back leaf
 
-        BvhLeaf *back = new BvhLeaf(backData.mBoundingBox, node, (int)backObjects.size());
-        BvhLeaf *front = new BvhLeaf(frontData.mBoundingBox, node, (int)frontObjects.size());
+        BvhLeaf *back = 
+                new BvhLeaf(backData.mBoundingBox, node, (int)backObjects.size());
+        BvhLeaf *front = 
+                new BvhLeaf(frontData.mBoundingBox, node, (int)frontObjects.size());
 
         BvhInterior *parent = leaf->GetParent();
@@ -333 +334 @@
         AssociateObjectsWithLeaf(front);
    
-
         // compute probability, i.e., volume of seen view cells
-        frontData.mVolume = frontData.mBoundingBox.GetVolume();
-        backData.mVolume =  backData.mBoundingBox.GetVolume();
+        frontData.mProbability = EvalViewCellsVolume(frontObjects);
+        backData.mProbability = EvalViewCellsVolume(backObjects);
 
         return node;
@@ -371 +371 @@
                 tBackData.mMaxCostMisses = maxCostMisses;
                 
+                // decrease the weighted average cost of the subdivisoin
                 mTotalCost -= sc->GetRenderCostDecrease();
 
                 // subdivision statistics
-                if (1) EvalSubdivisionStats(*sc);
+                if (1) PrintSubdivisionStats(*sc);
 
                 //-- push the new split candidates on the queue
                 
-                BvhSubdivisionCandidate *frontCandidate = new BvhSubdivisionCandidate(tFrontData);
-                BvhSubdivisionCandidate *backCandidate = new BvhSubdivisionCandidate(tBackData);
+                BvhSubdivisionCandidate *frontCandidate = 
+                        new BvhSubdivisionCandidate(tFrontData);
+                BvhSubdivisionCandidate *backCandidate = 
+                        new BvhSubdivisionCandidate(tBackData);
 
                 EvalSubdivisionCandidate(*frontCandidate);
@@ -416 +419 @@
 void BvHierarchy::EvalSubdivisionCandidate(BvhSubdivisionCandidate &splitCandidate)
 {
-        ObjectContainer frontObjects, backObjects;
-
         // compute best object partition
-        const float ratio =
-                SelectObjectPartition(splitCandidate.mParentData, frontObjects, backObjects);
-
+        const float ratio =     SelectObjectPartition(
+                                                        splitCandidate.mParentData, 
+                                                        splitCandidate.mFrontObjects, 
+                                                        splitCandidate.mBackObjects);
+        
         const bool success = ratio < mTermMaxCostRatio;
 
-        float oldRenderCost;
+        BvhLeaf *leaf = splitCandidate.mParentData.mNode;
+
+        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+
+        const float oldRenderCost = 
+                splitCandidate.mParentData.mProbability * (float)leaf->mObjects.size() / viewSpaceVol;
 
         // compute global decrease in render cost
-        const float renderCostDecr = EvalRenderCostDecrease(frontObjects, 
-                                                                                                                backObjects,
-                                                                                                                splitCandidate.mParentData,
-                                                                                                                oldRenderCost);
-
+        float newRenderCost = EvalRenderCost(splitCandidate.mParentData,
+                                                                             splitCandidate.mFrontObjects, 
+                                                                                 splitCandidate.mBackObjects);
+
+        newRenderCost /=  viewSpaceVol;
+
+        const float renderCostDecr = oldRenderCost - newRenderCost;
+
+        Debug << "!!render cost decr: " << renderCostDecr << endl;
         splitCandidate.SetRenderCostDecrease(renderCostDecr);
 
@@ -488 +500 @@
         }
 
-        if (data.mVolume <= mTermMinVolume)
+        if (data.mProbability <= mTermMinProbability)
                 ++ mBvhStats.minProbabilityNodes;
         
@@ -502 +514 @@
 
 
+float BvHierarchy::EvalLocalObjectPartition(const BvhTraversalData &tData,
+                                                                                        const int axis,
+                                                                                        ObjectContainer &objectsFront,
+                                                                                        ObjectContainer &objectsBack)
+{
+        const float maxBox = tData.mBoundingBox.Max(axis);
+        const float minBox = tData.mBoundingBox.Min(axis);
+
+        float midPoint = (maxBox + minBox) * 0.5f;
+
+        ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
+        
+        for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *obj = *oit;
+                AxisAlignedBox3 box = obj->GetBox();
+                const float objMid = (box.Max(axis) + box.Min(axis)) * 0.5;
+                // object mailed => belongs to back objects
+                if (objMid < midPoint) 
+                        objectsBack.push_back(obj);
+                else
+                        objectsFront.push_back(obj);
+        }
+
+        const float oldRenderCost = tData.mProbability * (float)tData.mNode->mObjects.size();
+        const float newRenderCost = 
+                EvalRenderCost(tData, objectsFront, objectsBack);
+
+        const float ratio = newRenderCost / oldRenderCost;
+        return ratio;
+}
+
+
 float BvHierarchy::EvalLocalCostHeuristics(const BvhTraversalData &tData,
                                                                                    const int axis,
@@ -507 +552 @@
                                                                                    ObjectContainer &objectsBack)
 {
-        // the relative cost ratio
-        float ratio = 99999999.0f;
+        // prepare the heuristics by setting mailboxes and counters.
+        const float totalVol = PrepareHeuristics(tData, axis);
 
         // go through the lists, count the number of objects left and right
-        // and evaluate the following cost funcion:
-        // C = ct_div_ci  + (ol + or)/queries
-        
-        const float minBox = tData.mBoundingBox.Min(axis);
-        const float maxBox = tData.mBoundingBox.Max(axis);
-
-        const float sizeBox = maxBox - minBox;
-
-        float minBand = minBox + mSplitBorder * (maxBox - minBox);
-        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
-
-        //-- sort so we can use a sweep
-        SortSubdivisionCandidates(tData, axis, minBand, maxBand);
-
-        float totalVol = PrepareHeuristics(tData);
-        float voll = 0;
-        float volr = totalVol;
-
-        /// this is kind of a reverse pvs
-        const int totalObjects = (int)tData.mNode->mObjects.size();
-        
-        int objectsl = 0;
-        int objectsr = totalObjects;
-
-        float sum = (float)totalVol * objectsr;
-
-
-        bool splitPlaneFound = false;
+        // and evaluate the cost funcion
+
+        // local helper variables
+        float volLeft = 0;
+        float volRight = totalVol;
+
+        int nObjectsLeft = 0;
+
+        const int nTotalObjects = (int)tData.mNode->mObjects.size();
+        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+
+        vector<SortableEntry>::const_iterator currentPos =
+                mSubdivisionCandidates->begin();
 
         /////////////////////////////////
         // the parameters for the current optimum
 
-        float volBack = voll;
-        float volFront = volr;
-
-        int nObjectsBack = objectsl;
-        int nObjectsFront = objectsr;
-        
-        float minSum = 1e20f;
-
-        /////////////////////////////
-
-        debugVol = 0;
-        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+        float volBack = volLeft;
+        float volFront = volRight;
+
+        float newRenderCost = nTotalObjects * totalVol;
+
 
         /////////////////////////////
         // the sweep heuristics
-
-        // mail the objects on the left side
-        Intersectable::NewMail();
         
         //-- traverse through events and find best split plane
-        vector<SortableEntry>::const_iterator ci, ci_end = mSubdivisionCandidates->end();
-
-        for (ci = mSubdivisionCandidates->begin(); ci != ci_end; ++ ci)
-        {
-                Intersectable *object = (*ci).mObject;
-
-                EvalHeuristicsContribution(tData.mNode, *ci, voll, volr, objectsl);
-                objectsr = totalObjects - objectsl;
-
-                // Note: sufficient to compare size of bounding boxes of front and back side?
-
-                if (((*ci).mPos >= minBand) && ((*ci).mPos <= maxBand))
+
+        vector<SortableEntry>::const_iterator cit, cit_end = mSubdivisionCandidates->end();
+
+        for (cit = mSubdivisionCandidates->begin(); cit != cit_end; ++ cit)
+        {
+                Intersectable *object = (*cit).mObject;
+                
+                // evaluate change in l and r volume
+                // voll = view cells that see only left node (i.e., left pvs)
+                // volr = view cells that see only right node (i.e., right pvs)
+                EvalHeuristicsContribution(object, volLeft, volRight);
+
+                ++ nObjectsLeft;
+                
+                const int nObjectsRight = nTotalObjects - nObjectsLeft;
+
+                // view cells that see both child nodes
+                //const float volLeftAndRight = totalVol - volLeft - volRight;
+
+                // the heuristics
+            const float sum = volLeft * (float)nObjectsLeft + 
+                                                  volRight * (float)nObjectsRight;
+                //                                volLeftAndRight * (float)nTotalObjects;
+
+                if (sum < newRenderCost)
                 {
-                        // voll = view cells that see only left node (i.e., left pvs)
-                        // volr = view cells that see only right node (i.e., right pvs)
-                        // rest = view cells that see both nodes (i.e., total pvs)
-            sum = voll * objectsl + volr * objectsr + (totalVol - voll - volr) * totalObjects;
-
-                        float currentPos;
-                        
-                        // HACK: current positition is BETWEEN visibility events
-                        if (1 && ((ci + 1) != ci_end))
-                                currentPos = ((*ci).mPos + (*(ci + 1)).mPos) * 0.5f;
-                        else
-                                currentPos = (*ci).mPos;                        
-
-                        if ((totalVol - voll - volr - debugVol) / viewSpaceVol > 0.0001)
-                                Debug << "front and back volume: " << (totalVol - voll - volr) / viewSpaceVol << " error: " << (totalVol - voll - volr - debugVol) / viewSpaceVol << endl;
-#if 0                           
-                        Debug << "pos: " << currentPos 
-                                 << "\t (pvsl: " << pvsl << ", pvsr: " << pvsr << ")"
-                                 << "\t (voll: " << voll << ", volr: " << volr << ")"
-                                 << "\t (vcl: " << vcl << ", vcr: " << vcr << ", nvc: " << numViewCells << ")"
-                                 << "\t sum: " << sum << endl;
-                                
-#endif
-                        if (sum < minSum)
-                        {
-                                splitPlaneFound = true;
-
-                                minSum = sum;
-
-                                nObjectsBack = objectsl;
-                                nObjectsFront = objectsr;
-                                
-                                volBack = voll;
-                                volFront = volr;
-                        }
+                        newRenderCost = sum;
+
+                        volBack = volLeft;
+                        volFront = volRight;
+
+                        // objects belongs to left side now
+                        for (; currentPos != (cit + 1); ++ currentPos);
                 }
         }
-        
-        //-- compute cost
-        const float frontAndBackVol = totalVol - volFront - volBack;
-
-        const float oldRenderCost = (float)totalObjects * totalVol + Limits::Small;
-        const float newRenderCost = (float)nObjectsFront * volFront + 
-                                                                (float)nObjectsBack * volBack +
-                                                                (float)totalObjects * frontAndBackVol;
-
-        if (splitPlaneFound)
-        {
-                ratio = newRenderCost / oldRenderCost;
-        }
-
-        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" 
-        //        << position << " t=" << (position - minBox) / (maxBox - minBox)
-        //      << "\t pb=(" << volBack << ")\t pf=(" << volFront << ")" << endl;
+
+        //-- assign object to front and back volume
+
+        // belongs to back bv
+        for (cit = mSubdivisionCandidates->begin(); cit != currentPos; ++ cit)
+                objectsBack.push_back((*cit).mObject);
+        
+        // belongs to front bv
+        for (cit = currentPos; cit != cit_end; ++ cit)
+                objectsFront.push_back((*cit).mObject);
+
+        tData.mNode->mObjects.end();
+
+        const float oldRenderCost = (float)nTotalObjects * totalVol + Limits::Small;
+        // the relative cost ratio
+        const float ratio = newRenderCost / oldRenderCost;
 
         Debug << "\n§§§§ eval local cost §§§§" << endl
-                  << "back pvs: " << nObjectsBack << " front pvs: " << nObjectsFront << " total pvs: " << totalObjects << endl 
+                  << "back pvs: " << (int)objectsBack.size() << " front pvs: " << objectsFront.size() << " total pvs: " << nTotalObjects << endl 
                   << "back p: " << volBack / viewSpaceVol << " front p " << volFront / viewSpaceVol << " p: " << totalVol / viewSpaceVol << endl
                   << "old rc: " << oldRenderCost / viewSpaceVol << " new rc: " << newRenderCost / viewSpaceVol << endl
                   << "render cost decrease: " << oldRenderCost / viewSpaceVol - newRenderCost / viewSpaceVol << endl;
 
-        if (oldRenderCost < newRenderCost)
-                Debug << "\nwarning!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
-
-        // assign objects
-        ObjectContainer::const_iterator oit, oit_end = tData.mNode->mObjects.end();
-
-        for (oit = tData.mNode->mObjects.begin(); oit != oit_end; ++ oit)
-        {
-                Intersectable *obj = *oit;
-
-                if (obj->Mailed()) // belongs to back objects
-                        objectsBack.push_back(obj);
-                else
-                        objectsFront.push_back(obj);
-        }
-
         return ratio;
 }
@@ -658 +646 @@
 
 void BvHierarchy::SortSubdivisionCandidates(const BvhTraversalData &tData,
-                                                                          const int axis, 
-                                                                          float minBand, 
-                                                                          float maxBand)
-
+                                                                                        const int axis)                                                                                 
 {
         mSubdivisionCandidates->clear();
@@ -669 +654 @@
 
         // compute requested size
-        int requestedSize = 0;
-        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
-        for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
-                requestedSize += 2 + (int)(*oit)->mVssRays.size() * 2;
+        const int requestedSize = (int)leaf->mObjects.size() * 2;
         
         // creates a sorted split candidates array
@@ -683 +665 @@
 
         mSubdivisionCandidates->reserve(requestedSize);
-
-        float pos;
 
         //-- insert object queries
@@ -691 +671 @@
         //-- there is no ray associated with these events!!
 
+        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
         for (oit = leaf->mObjects.begin(); oit < oit_end; ++ oit)
         {
@@ -696 +678 @@
                 
                 Intersectable *object = *oit;
-                const AxisAlignedBox3 box = object->GetBox();
-
-                mSubdivisionCandidates->push_back(
-                        SortableEntry(SortableEntry::OBJECT,
-                                                  box.Min(axis),
-                                                  object,
-                                                  NULL)
-                                                  );
-
-
-                //-- insert ray queries
-                //-- we are intersested only in rays which intersect an object that
-                //-- is part of the kd node because they can induce a change in view cell
-                //-- volume on the left and the right part. 
-                //-- Note that they cannot induce a change in pvs size!!
-                
-                VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
-
-                for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
-                {
-                        VssRay *ray = (*rit);
-                        const bool positive = ray->HasPosDir(axis);
-        
-                        pos = ray->mTermination[axis];
-
-                        mSubdivisionCandidates->push_back(
-                                SortableEntry(SortableEntry::VIEWCELLS, 
-                                pos, 
-                                ray->mTerminationObject, 
-                                ray)
-                                );
-                }
+                const AxisAlignedBox3 &box = object->GetBox();
+                const float midPt = (box.Min(axis) + box.Max(axis)) * 0.5f;
+
+                mSubdivisionCandidates->push_back(SortableEntry(object, midPt));
         }
 
@@ -740 +694 @@
 
 
-void BvHierarchy::EvalRayContribution(const VssRay &ray, 
-                                                                          float &volLeft, 
-                                                                          float &volRight)
-{
+float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData, const int axis)
+{       
+        //-- sort so we can use a sweep from right to left
+        SortSubdivisionCandidates(tData, axis);
+
+        float vol = 0;
+        BvhLeaf *leaf = tData.mNode;
+
+        // collect and mark the view cells as belonging to front pvs
         ViewCellContainer viewCells;
-        mVspTree->GetViewCells(ray, viewCells);
+        CollectViewCells(tData.mNode->mObjects, viewCells, true);
+
+    ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+        {
+                vol += (*vit)->GetVolume();
+        }
+
+        // mail view cells on the left side
+        ViewCell::NewMail();
+        
+        // mail the objects on the left side
+        Intersectable::NewMail();
+
+        return vol;
+}
+///////////////////////////////////////////////////////////
+
+
+void BvHierarchy::EvalHeuristicsContribution(Intersectable *obj,
+                                                                                         float &volLeft, 
+                                                                                         float &volRight)
+{
+        // collect all view cells associated with this objects 
+        // (also multiple times, if they are pierced by several rays)
+
+        ViewCellContainer viewCells;
+        
+        const bool useMailboxing = false;
+        CollectViewCells(obj, viewCells, useMailboxing);
+
 
         /// classify view cells and compute volume contri accordingly
@@ -766 +756 @@
 
                         // we now see view cell from both nodes 
-                        // => remove ref to right child node
-                        volRight -= vol;
-                        debugVol += vol;
+                        // => add volume to left node
+                        volLeft += vol;
+                        //volRight -= vol;
                 }
 
@@ -775 +765 @@
                 {
                         // view cell was previously seen from both nodes  =>
-                        // contributes only to left node now
-                        volLeft += vol;
-                        debugVol -= vol;
+                        // remove volume from right node
+                        volRight -= vol;
                 }
         }
-}
-
-
-float BvHierarchy::PrepareHeuristics(const VssRay &ray)
-{
-        float vol = 0;
-
-        ViewCellContainer viewCells;
-        mVspTree->GetViewCells(ray, viewCells);
-        
-        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-
-        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
-        {
-                ViewCell *vc = (*vit);
-
-                if (!vc->Mailed())
-                {
-                        //Debug << "single vol: "<< vc->GetVolume() << endl;
-                        vc->Mail();
-                        vc->mCounter = 0;
-                        vol += vc->GetVolume();
-                }
-                
-                // view cell volume already added => just increase counter
-                ++ vc->mCounter;
-        }
-
-        return vol;
-}
-
-
-float BvHierarchy::PrepareHeuristics(const BvhTraversalData &tData)
-{       
-        float vol = 0;
-        debugVol = 0;
-        
-        ViewCell::NewMail();
-
-        BvhLeaf *leaf = tData.mNode;
-
-        VssRayContainer rays;
-        CollectRays(leaf->mObjects, rays);
-
-        VssRayContainer::const_iterator rit, rit_end = rays.end();
-
-        for (rit = rays.begin(); rit < rit_end; ++ rit)
-        {
-                VssRay *ray = (*rit);
-
-                const float volContri = PrepareHeuristics(*ray);
-
-                // if hitpoint with one of the objects is inside this node, we
-                // evaluate the volume of the view cells seen by this ray
-                if (ray->mTerminationObject)
-                {
-            vol += volContri;
-                }
-
-                // count double if both hit points are within the kd node
-                if (0 && ray->mOriginObject)
-                {
-                        vol += volContri;
-                }
-        }
-
-        return vol;
-}
-///////////////////////////////////////////////////////////
-
-
-void BvHierarchy::EvalHeuristicsContribution(BvhLeaf *leaf,
-                                                                                         const SortableEntry &ci,
-                                                                                         float &volLeft, 
-                                                                                         float &volRight, 
-                                                                                         int &objectsLeft)
-{
-        Intersectable *obj = ci.mObject;
-        VssRay *ray = ci.mRay;
-
-        // switch between different types of events
-        switch (ci.mType) 
-        {
-                case SortableEntry::OBJECT:
-                        cout << "o";
-                        ci.mObject->Mail();
-                        ++ objectsLeft;
-                        break;
-
-                // compute volume contribution from view cells
-                case SortableEntry::VIEWCELLS:
-                        cout << "v";
-                        // process ray if the hit point with termination / origin object 
-                        // is inside this kd leaf
-                        EvalRayContribution(*ray, volLeft, volRight);
-                        break;
-
-                default:
-                        cout << "should not come here" << endl;
-                        break;
-        }
-        //cout << "vol left: " << volLeft << " vol right " << volRight << endl;
 }
 
@@ -923 +810 @@
                 if (!mOnlyDrivingAxis || (axis == sAxis))
                 {
-                        if (1 || mUseCostHeuristics)
+                        if (mUseCostHeuristics)
                         {
                                 //-- partition objects using heuristics
-                                
                                 nCostRatio[axis] =
                                         EvalLocalCostHeuristics(
@@ -932 +818 @@
                                                                                         axis,
                                                                                         nFrontObjects[axis],
-                                                                                        nBackObjects[axis]);                    
+                                                                                        nBackObjects[axis]);
                         }
+                        else
+                        {
+                                nCostRatio[axis] =
+                                        EvalLocalObjectPartition(
+                                                                                         tData,
+                                                                                         axis,
+                                                                                         nFrontObjects[axis],
+                                                                                         nBackObjects[axis]);
+                        }
+
                         if (bestAxis == -1)
                         {
@@ -946 +842 @@
 
         //-- assign values
-        
+
         frontObjects = nFrontObjects[bestAxis];
-        backObjects = nFrontObjects[bestAxis];
+        backObjects = nBackObjects[bestAxis];
 
         Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
@@ -977 +873 @@
 
 
-void BvHierarchy::EvalSubdivisionStats(const SubdivisionCandidate &sc)
-{
-        const float costDecr = sc.GetRenderCostDecrease();
-
-        AddSubdivisionStats(mBvhStats.Leaves(),
-                                                costDecr,
-                                                mTotalCost
-                                                );
-}
-
-
-void BvHierarchy::AddSubdivisionStats(const int leaves,
-                                                                          const float renderCostDecr,
-                                                                          const float totalRenderCost)
-{
+void BvHierarchy::PrintSubdivisionStats(const SubdivisionCandidate &sc)
+{
+        const float costDecr = sc.GetRenderCostDecrease();      
+
         mSubdivisionStats 
-                        << "#Leaves\n" << leaves << endl
-                        << "#RenderCostDecrease\n" << renderCostDecr << endl 
-                        << "#TotalRenderCost\n" << totalRenderCost << endl;
+                        << "#Leaves\n" << mBvhStats.Leaves()
+                        << "#RenderCostDecrease\n" << costDecr << endl 
+                        << "#TotalRenderCost\n" << mTotalCost << endl;
                         //<< "#AvgRenderCost\n" << avgRenderCost << endl;
 }
@@ -1029 +914 @@
 
 
-void BvHierarchy::MailViewCells(const ObjectContainer &objects, 
-                                                                const bool isFront,
-                                                                ViewCellContainer &collectedViewCells) const
-{
-        VssRayContainer rays;
-        CollectRays(objects, rays);
-        
-        VssRayContainer::const_iterator rit, rit_end = rays.end();
-
-        for (rit = rays.begin(); rit < rit_end; ++ rit)
-        {
-                VssRay *ray = (*rit);
-
-                // view cell is assigned to left and / or right child
-                ViewCellContainer viewCells;
-                mVspTree->GetViewCells(*ray, viewCells);
-                        
-                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-
-                // mail view cell
-                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+void BvHierarchy::ClassifyViewCells(const ViewCellContainer &viewCells, 
+                                                                        const bool isFront) const
+{
+        int mailed = 0;
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+        // mail view cell
+        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+        {
+                ViewCell *vc = *vit;
+
+                if (isFront)
                 {
-                        ViewCell *vc = *vit;
-
-                        if (!vc->Mailed() && !vc->Mailed(1) && !vc->Mailed(2))
-                                collectedViewCells.push_back(vc);
-
-                        if (isFront)
+                        if (!vc->Mailed())
                         {
-                                if (!vc->Mailed())
-                                        vc->Mail();
+                                vc->Mail();
+                                //Debug << " " << vc->mMailBox << endl;
+                                ++ mailed;
                         }
-                        else
+                }
+                else
+                {
+                        if (vc->Mailed())
                         {
-                                if (!vc->Mailed())
-                                        vc->Mail(1);
-                                else
-                                        vc->Mail(2);
+                                vc->Mail(2);
+                                //Debug << " " << vc->mMailBox << endl;
+                                ++ mailed;
                         }
-                }                               
-        }
-}
-
-
-float BvHierarchy::EvalRenderCostDecrease(const ObjectContainer &objectsFront,
+                        else if (!vc->Mailed(1) && !vc->Mailed(2))
+                        {
+                                vc->Mail(1);
+                                //Debug << " " << vc->mMailBox << endl;
+                                ++ mailed;
+                        }
+
+                }
+        }                               
+
+        Debug << "mailed " << mailed << " view cells " << endl;
+}
+
+
+float BvHierarchy::EvalRenderCost(const BvhTraversalData &tData,
+                                                                  const ObjectContainer &objectsFront,
+                                                                  const ObjectContainer &objectsBack) const
+{
+        BvhLeaf *leaf = tData.mNode;
+
+        // probability that view point lies in a view cell which sees this node
+        const float pFront = EvalViewCellsVolume(objectsFront);
+        const float pBack = EvalViewCellsVolume(objectsBack);
+                
+        const int totalObjects = (int)leaf->mObjects.size();
+        const int nObjectsFront = (int)objectsFront.size();
+        const int nObjectsBack = (int)objectsBack.size();
+
+        //-- pvs rendering heuristics
+        const float newRenderCost = nObjectsFront * pFront + 
+                                                                nObjectsBack * pBack;
+
+        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+        Debug << "\n***** eval render cost *********\n" 
+                  << "back p: " << pBack / viewSpaceVol << " front p " << pFront / viewSpaceVol << endl
+                  << "new rc: " << newRenderCost / viewSpaceVol << endl;
+                 
+
+        return newRenderCost;
+}
+
+
+/*float BvHierarchy::EvalRenderCostDecrease(const BvhTraversalData &tData,
+                                                                                  const ObjectContainer &objectsFront,
                                                                                   const ObjectContainer &objectsBack,
-                                                                                  const BvhTraversalData &tData,
                                                                                   float &normalizedOldRenderCost) const
 {
-        // probability that view point lies in back / front node
+        BvhLeaf *leaf = tData.mNode;
+
+        // probability that view point lies in a view cell which sees this node
         float pOverall = 0;
         float pFront = 0;
@@ -1085 +998 @@
 
         const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
-
-        BvhLeaf *leaf = tData.mNode;
-        
+        
+        ViewCellContainer collectedViewCells;
+        ViewCellContainer viewCellsFront, viewCellsBack;
+
+        // the view cells seen from the front bv
+        
+    CollectViewCells(objectsFront, viewCellsFront);
+        // the view cells seen from the back bv
+        CollectViewCells(objectsBack, viewCellsBack);
+        // the view cells seen from both bvs
+        // note: could be evaluated simpler
+        CollectViewCells(leaf->mObjects, collectedViewCells);
+
+
         // sum up volume seen from the objects of left and right children
         // => the volume is the weight for the render cost equation
+        
         ViewCell::NewMail(3);
-
-        ViewCellContainer collectedViewCells;
-        MailViewCells(objectsFront, true, collectedViewCells);
-        MailViewCells(objectsBack, false, collectedViewCells);
+        ClassifyViewCells(viewCellsFront, true);
+        ClassifyViewCells(viewCellsBack, false);
 
         ViewCellContainer::const_iterator vit, vit_end = collectedViewCells.end();
@@ -1101 +1024 @@
         for (vit = collectedViewCells.begin(); vit != vit_end; ++ vit)
         {
-                AddViewCellVolumeContri(*vit, pFront, pBack, pFrontAndBack);
+                ViewCell *vc = *vit;
+                if (vc->Mailed())
+                        pFront += vc->GetVolume();
+                else if (vc->Mailed(1))
+                        pBack += vc->GetVolume();
+                else if (vc->Mailed(2))
+                        pFrontAndBack += vc->GetVolume();
         }
 
@@ -1113 +1042 @@
         //-- pvs rendering heuristics
         const float oldRenderCost = pOverall * totalObjects;
-        const float newRenderCost = nObjectsFront * pFront + nObjectsBack * pBack + totalObjects * pFrontAndBack;
+        const float newRenderCost = nObjectsFront * pFront + 
+                                                                nObjectsBack * pBack + 
+                                                                totalObjects * pFrontAndBack;
 
         // normalize volume with view space volume
@@ -1127 +1058 @@
         normalizedOldRenderCost = oldRenderCost / viewSpaceVol;
 
-        if (oldRenderCost < newRenderCost * 0.99)
-                Debug << "\nwarning2!!:\n" << "old rc: " << oldRenderCost * viewSpaceVol << " new rc: " << newRenderCost * viewSpaceVol << endl;
-        
         return renderCostDecrease;
-}
-
-
-AxisAlignedBox3 BvHierarchy::ComputeBoundingBox(const ObjectContainer &objects)
-{
+}*/
+
+
+AxisAlignedBox3 BvHierarchy::ComputeBoundingBox(const ObjectContainer &objects,
+                                                                                                const AxisAlignedBox3 *parentBox)
+{
+        if (parentBox && objects.empty())
+                return *parentBox;
+
         AxisAlignedBox3 box;
         box.Initialize();
@@ -1147 +1079 @@
 
                 // compute bounding box of view space
-                mBoundingBox.Include(obj->GetBox());
-        }
+                box.Include(obj->GetBox());
+        }
+
         return box;
-        
 }
 
@@ -1163 +1095 @@
                 BvhNode *node = nodeStack.top();
                 nodeStack.pop();
+
                 if (node->IsLeaf()) 
                 {
@@ -1185 +1118 @@
 
 
-void BvHierarchy::CollectViewCells(BvhLeaf *leaf, ViewCellContainer &viewCells)
-{
-        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
-
+void BvHierarchy::CollectViewCells(const ObjectContainer &objects, 
+                                                                   ViewCellContainer &viewCells,
+                                                                   const bool setCounter) const
+{
         ViewCell::NewMail();
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
 
         // loop through all object and collect view cell pvs of this node
-        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
-        {
-                Intersectable *obj = *oit;
-
-                ViewCellPvsMap::const_iterator vit, vit_end = obj->mViewCellPvs.mEntries.end();
-
-                for (vit = obj->mViewCellPvs.mEntries.begin(); vit != vit_end; ++ vit)
-                {
-            ViewCell *vc = (*vit).first;
-
-                        if (!vc->Mailed())
-                        {
-                                vc->Mail();
-                                viewCells.push_back(vc);
-                        }
-                }
-        }
-}
-
-
-void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc, 
-                                                                                 vector<SubdivisionCandidate *> &dirtyList)
-{
-        BvhTraversalData &tData = sc->mParentData;
-        BvhLeaf *node = tData.mNode;
-        
-        ViewCell::NewMail();
-
-        ViewCellContainer viewCells;
-        ViewCellContainer tmpViewCells;
-
-        VssRayContainer rays;
-        CollectRays(node->mObjects, rays);
-
-        VssRayContainer::const_iterator rit, rit_end = rays.end();
-
-        // find all view cells associated with the rays, add them to view cells
-        for (rit = rays.begin(); rit != rit_end; ++ rit)
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+        {
+                CollectViewCells(*oit, viewCells, true, setCounter);
+        }
+}
+
+
+void BvHierarchy::CollectViewCells(Intersectable *obj, 
+                                                                   ViewCellContainer &viewCells,
+                                                                   const bool useMailBoxing,
+                                                                   const bool setCounter) const
+{
+        VssRayContainer::const_iterator rit, rit_end = obj->mVssRays.end();
+
+        for (rit = obj->mVssRays.begin(); rit < rit_end; ++ rit)
         {
                 VssRay *ray = (*rit);
+                ViewCellContainer tmpViewCells;
+        
                 mVspTree->GetViewCells(*ray, tmpViewCells);
 
@@ -1240 +1153 @@
                         VspViewCell *vc = dynamic_cast<VspViewCell *>(*vit);
 
-                        if (!vc->Mailed())
+                        // store view cells
+                        if (!useMailBoxing || !vc->Mailed())
                         {
-                                vc->Mail();
+                                if (useMailBoxing)
+                                {
+                                        vc->Mail();
+                                        if (setCounter)
+                                                vc->mCounter = 0;
+                                }
+                                
                                 viewCells.push_back(vc);
                         }
+                        
+                        if (setCounter)
+                        {
+                                ++ vc->mCounter;
+                        }
                 }
         }
-
-
-        // split candidates holding this view cells 
-        // are thrown into dirty list
+}
+
+
+void BvHierarchy::CollectDirtyCandidates(BvhSubdivisionCandidate *sc, 
+                                                                                 vector<SubdivisionCandidate *> &dirtyList)
+{
+        BvhTraversalData &tData = sc->mParentData;
+        BvhLeaf *node = tData.mNode;
+        
+        ViewCellContainer viewCells;
+        CollectViewCells(node->mObjects, viewCells);
+
+        // split candidates handling 
+        // these view cells  are thrown into dirty list
         ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
 
@@ -1358 +1293 @@
 
 
-void BvHierarchy::AddViewCellVolumeContri(ViewCell *vc,
-                                                                                  float &frontVol,
-                                                                                  float &backVol,
-                                                                                  float &frontAndBackVol) const
-{
-        if (vc->Mailed())
-        {
-                frontVol += vc->GetVolume();
-        }
-        else if (vc->Mailed(1))
-        {
-                backVol += vc->GetVolume();
-        }
-        else if (vc->Mailed(2))
-        {
-                frontAndBackVol += vc->GetVolume();
-        }
-}
-
 /*
 int BvHierarchy::UpdateViewCellsPvs(BvhLeaf *leaf, 
@@ -1469 +1385 @@
         {
                 BvhLeaf *leaf = dynamic_cast<BvhLeaf *>(node);
-
+                const AxisAlignedBox3 box = leaf->GetBoundingBox();
                 stream << "<Leaf"
-                           << " min=\"" << leaf->GetBoundingBox().Min()
-                           << " max=\"" << leaf->GetBoundingBox().Max() 
+                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
+                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z << "\""
                            << " objects=\"";
                 
@@ -1483 +1399 @@
         {       
                 BvhInterior *interior = dynamic_cast<BvhInterior *>(node);
-        
+                const AxisAlignedBox3 box = interior->GetBoundingBox();
+
                 stream << "<Interior"
-                           << " min=\"" << interior->GetBoundingBox().Min()
-                           << " max=\"" << interior->GetBoundingBox().Max()
+                           << " min=\"" << box.Min().x << " " << box.Min().y << " " << box.Min().z << "\""
+                           << " max=\"" << box.Max().x << " " << box.Max().y << " " << box.Max().z
                            << "\">" << endl;
 
@@ -1497 +1414 @@
 
 
-float BvHierarchy::EvalViewCellsVolume(BvhLeaf *leaf) const
+float BvHierarchy::EvalViewCellsVolume(const ObjectContainer &objects) const
 {
         float vol = 0;
 
-        VssRayContainer rays;
-        CollectRays(leaf->mObjects, rays);
-
-        ViewCell::NewMail();
-
-        VssRayContainer::const_iterator rit, rit_end = rays.end();
-
-        for (rit = rays.begin(); rit < rit_end; ++ rit)
-        {
-                VssRay *ray = (*rit);
-        
-                ViewCellContainer viewCells;
-                mVspTree->GetViewCells(*ray, viewCells);
-        
-                ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
-
-                for (vit = viewCells.begin(); vit != vit_end; ++ vit)
-                {
-                        ViewCell *vc = (*vit);
-
-                        if (!vc->Mailed())
-                        {
-                                //Debug << "single vol: "<< vc->GetVolume() << endl;
-                                vc->Mail();
-                                vol += vc->GetVolume();
-                        }
-                }
+        ViewCellContainer viewCells;
+        CollectViewCells(objects, viewCells);
+
+        ViewCellContainer::const_iterator vit, vit_end = viewCells.end();
+
+        for (vit = viewCells.begin(); vit != vit_end; ++ vit)
+        {
+                vol += (*vit)->GetVolume();
         }
 
@@ -1535 +1433 @@
 
 SubdivisionCandidate *BvHierarchy::PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                                                           ObjectContainer &objects,
-                                                                                                           AxisAlignedBox3 *forcedObjectSpace
-                                                                                                           //, RayInfoContainer &rays
+                                                                                                           const ObjectContainer &objects
+                                                                                                           //,AxisAlignedBox3 *forcedObjectSpace
                                                                                                            )
 {
+        // note matt: we assume that we have objects sorted by their id
+
         // store pointer to this tree
         BvhSubdivisionCandidate::sBvHierarchy = this;
@@ -1545 +1444 @@
 
         // compute bounding box from objects
-        if (forcedObjectSpace)
-                mBoundingBox = *forcedObjectSpace;
-        else
-                mBoundingBox = ComputeBoundingBox(objects);
-
-        mTermMinVolume *= mBoundingBox.GetVolume();
+        mBoundingBox = ComputeBoundingBox(objects);
+
+        mTermMinProbability *= mBoundingBox.GetVolume();
         mGlobalCostMisses = 0;
-
-        // sort objects by id in order to have sorted objects in
-        // the leaf nodes
-        stable_sort(objects.begin(), objects.end(), ilt);
-
+        
         //-- create new root
 
@@ -1569 +1461 @@
 
         //-- add first candidate for object space partition
+        
+        // probabilty is voume of all "seen" view cells
+#if 1
+        const float prop = EvalViewCellsVolume(bvhleaf->mObjects);
+#else
+        const float prop = GetBoundingBox().GetVolume();
+#endif
 
         // create osp traversal data
-        BvhTraversalData oData(bvhleaf, 0, mBoundingBox.GetVolume());
+        BvhTraversalData oData(bvhleaf, 0, mBoundingBox, prop);
 
         //-- first split candidate
@@ -1581 +1480 @@
         EvalSubdivisionCandidate(*oSubdivisionCandidate);
 
-// probabilty is voume of all "seen" view cells
-#if 1
-        const float prop = EvalViewCellsVolume(bvhleaf);
-#else
-        const float prop = GetBoundingBox().GetVolume();
-#endif
-        mTotalCost = (float)objects.size() * prop / 
-                mVspTree->GetBoundingBox().GetVolume();
-
-        EvalSubdivisionStats(*oSubdivisionCandidate);
+        const float viewSpaceVol = mVspTree->GetBoundingBox().GetVolume();
+        mTotalCost = (float)objects.size() * prop / viewSpaceVol;
+
+        PrintSubdivisionStats(*oSubdivisionCandidate);
 
         return oSubdivisionCandidate;

GTP/trunk/Lib/Vis/Preprocessing/src/BvHierarchy.h

@@ -261 +261 @@
         /// universal counter
         int mCounter;
+
+
 protected:
 
@@ -289 +291 @@
                 /// current depth
                 int mDepth;
-                /// rays piercing this node
-                //RayInfoContainer *mRays;
-                /// the volume of this node
-                float mVolume;
+                /// the probability that this node is seen
+                float mProbability;
                 /// the bounding box of the node
                 AxisAlignedBox3 mBoundingBox;
@@ -305 +305 @@
                 BvhTraversalData():
                 mNode(NULL),
-                //mRays(NULL),
                 mDepth(0),
-                mVolume(0.0),
+                mProbability(0.0),
                 mMaxCostMisses(0), 
                 mPriority(0),
@@ -315 +314 @@
                 BvhTraversalData(BvhLeaf *node, 
                                                  const int depth,
-                         //RayInfoContainer *rays,
+                                                 const AxisAlignedBox3 &box,
                                                  const float v):
                 mNode(node), 
                 mDepth(depth),
-                //mRays(rays),
-                mVolume(v),
+                mBoundingBox(box),
+                mProbability(v),
                 mMaxCostMisses(0),
                 mPriority(0),
@@ -326 +325 @@
                 {}
 
-                BvhTraversalData(
-                        const int depth
-                        //,RayInfoContainer *rays
-                        ): 
-                mNode(NULL), 
-                mDepth(depth),
-                //mRays(rays),
-                mVolume(0),
-                mMaxCostMisses(0),
-                mAxis(0)
-                {}
 
                 /** Returns cost of the traversal data.
@@ -531 +519 @@
         bool GlobalTerminationCriteriaMet(const BvhTraversalData &data) const;
 
-        // --------------------------------------------------------------
-        // For sorting objects
-        // --------------------------------------------------------------
+        /** For sorting the objects during the heuristics
+        */
         struct SortableEntry
         {
-                /** There is a 3th "event" for rays which intersect a
-                        box in the middle. These "events" don't induce a change in
-                        pvs size, but may induce a change in view cell volume.
-                */
-                enum EType 
-                {
-                        OBJECT,
-                        VIEWCELLS
-                };
-
-                int mType;
+                Intersectable *mObject;
                 float mPos;
 
-                VssRay *mRay;
-                Intersectable *mObject;
-
                 SortableEntry() {}
 
-                SortableEntry(
-                        const int type,
-                        const float pos,
-                        Intersectable *obj,
-                        VssRay *ray):
-                mType(type),  
-                mPos(pos), 
-                mObject(obj),
-                mRay(ray)
+                SortableEntry(Intersectable *obj, const float pos): 
+                mObject(obj), mPos(pos)
                 {}
 
@@ -571 +538 @@
         };
  
-        /** faster evaluation of split plane cost for kd axis aligned cells.
-        */
-        float EvalLocalSplitCost(const BvhTraversalData &data,
-                                                         const AxisAlignedBox3 &box,
-                                                         const int axis,
-                                                         const float &position,
-                                                         float &pFront,
-                                                         float &pBack) const;
+        /** Evaluate balanced object partition.
+        */
+        float EvalLocalObjectPartition(
+                const BvhTraversalData &tData,
+                const int axis,
+                ObjectContainer &objectsFront,
+                ObjectContainer &objectsBack);
 
         /** Computes priority of the traversal data and stores it in tData.
@@ -584 +550 @@
         void EvalPriority(BvhTraversalData &tData) const;
 
-        /** Evaluates render cost decrease of next split.
-        */
-        float EvalRenderCostDecrease(
+        /** Evaluates render cost of next split.
+        */
+        float EvalRenderCost(
+                const BvhTraversalData &tData,
                 const ObjectContainer &objectsLeft,
-                const ObjectContainer &objectsRight,
-                const BvhTraversalData &tData,
-                float &normalizedOldRenderCost) const;
+                const ObjectContainer &objectsRight) const;
 
         /** Evaluates tree stats in the BSP tree leafs.
@@ -658 +623 @@
         void SortSubdivisionCandidates(
                 const BvhTraversalData &data,
-                const int axis, 
-                float minBand, 
-                float maxBand);
+                const int axis);
 
         /** Computes best cost for axis aligned planes.
@@ -670 +633 @@
                 ObjectContainer &objectsFBack);
 
-        /** Evaluate the volume of view cells seeing the left and right child cell.
-        */
-        void EvalRayContribution(const VssRay &ray, float &volLeft, float &volRight);
-
-
-        /** Evaluates the influence on the pvs of the event.
-                @param ve the visibility event
-                @param pvsLeft updates the left pvs
-                @param rightPvs updates the right pvs
+        /** Evaluates the contribution to the front and back volume
+                when this object is changing sides in the bvs.
+
+                @param object the object
+                @param volLeft updates the left pvs
+                @param volPvs updates the right pvs
         */
         void EvalHeuristicsContribution(
-                BvhLeaf *leaf,
-                const SortableEntry &ci,
+                Intersectable *obj,
                 float &volLeft, 
-                float &volRight,
-                int &objectsLeft);
+                float &volRight);
 
         /** Prepares objects for the cost heuristics.
                 @returns sum of volume of associated view cells
         */
-        float PrepareHeuristics(const BvhTraversalData &tData);
-
-        /** Prepares heuristics for a particular ray.
-        */
-        float PrepareHeuristics(const VssRay &ray);
-
-        void AddViewCellVolumeContri(
-                ViewCell *vc, 
-                float &frontVol, 
-                float &backVol,
-                float &frontAndBackVol) const;
-
-        
+        float PrepareHeuristics(const BvhTraversalData &tData, const int axis);
+        
+
         ////////////////////////////////////////////////
 
@@ -708 +656 @@
         /** Prepares construction for vsp and osp trees.
         */
-        AxisAlignedBox3 ComputeBoundingBox(const ObjectContainer &objects);
-
-        void CollectDirtyCandidates(BvhSubdivisionCandidate *sc,
+        AxisAlignedBox3 ComputeBoundingBox(
+                const ObjectContainer &objects, 
+                const AxisAlignedBox3 *parentBox = NULL);
+
+        void CollectDirtyCandidates(
+                BvhSubdivisionCandidate *sc,
                 vector<SubdivisionCandidate *> &dirtyList);
 
-        /** Collect view cells which see this kd leaf.
-        */
-        void CollectViewCells(BvhLeaf *leaf, ViewCellContainer &viewCells);
+        /** Collect view cells which see this bvh leaf.
+        */
+        void CollectViewCells(
+                const ObjectContainer &objects, 
+                ViewCellContainer &viewCells,
+                const bool setCounter = false) const;
+
+        /** Collects view cells which see an object.
+        */
+        void CollectViewCells(
+                Intersectable *object, 
+                ViewCellContainer &viewCells, 
+                const bool useMailBoxing,
+                const bool setCounter = false) const;
 
         /** Rays will be clipped to the bounding box.
@@ -724 +686 @@
                 RayInfoContainer &rays);
 
-
-        void EvalSubdivisionStats(const SubdivisionCandidate &tData);
+        /** Print the subdivision stats in the subdivison log.
+        */
+        void PrintSubdivisionStats(const SubdivisionCandidate &tData);
 
         void AddSubdivisionStats(
@@ -734 +697 @@
         void AssociateObjectsWithRays(const VssRayContainer &rays);
 
-        //float EvalViewCellsVolume(BvhLeaf *leaf) const;
-        
-/*      int RemoveParentViewCellsPvs(BvhLeaf *leaf, const RayInfoContainer &rays) const;
-        int UpdateViewCellsPvs(BvhLeaf *leaf, const RayInfoContainer &rays) const;
-        bool AddViewCellToObjectPvs(
-                Intersectable *obj,
-                ViewCell *vc, 
-                float &contribution,
-                bool onlyMailed) const;
-*/
-
         bool IsObjectInLeaf(BvhLeaf *, Intersectable *object) const;
 
-        void MailViewCells(
-                const ObjectContainer &objects, 
-                const bool isFront,
-                ViewCellContainer &collectedViewCells) const;
-
-        SubdivisionCandidate *PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                                          ObjectContainer &objects,
-                                                                                          AxisAlignedBox3 *forcedObjectSpace
-                                                                                          //, RayInfoContainer &rays
-                                                                                          );
-
-        float EvalViewCellsVolume(BvhLeaf *leaf) const;
+        /** Classifies view cells using the mail id.
+                0 = front bv, 1 = back bv, 2 = both bvs
+        */
+        void ClassifyViewCells(
+                const ViewCellContainer &objects, 
+                const bool isFront) const;
+
+        SubdivisionCandidate *PrepareConstruction(
+                const VssRayContainer &sampleRays,
+                const ObjectContainer &objects
+                //,AxisAlignedBox3 *forcedObjectSpace
+                );
+
+        float EvalViewCellsVolume(const ObjectContainer &objects) const;
 
 
 protected:
-
         
         /// pointer to the hierarchy of view cells
@@ -790 +743 @@
         int mTermMaxDepth;
         /// mininum probability
-        float mTermMinVolume;
+        float mTermMinProbability;
         /// minimal number of objects
         int mTermMinObjects;

GTP/trunk/Lib/Vis/Preprocessing/src/Environment.cpp

@@ -2311 +2311 @@
                 optBool,
                 "osp_use_cost_heuristics=",
-                "false");
+                "true");
 
         RegisterOption("OspTree.subdivisionStats",

GTP/trunk/Lib/Vis/Preprocessing/src/Exporter.cpp

@@ -4 +4 @@
 #include "KdTree.h"
 #include "KdIntersectable.h"
+#include "BvHierarchy.h"
 
 
@@ -67 +68 @@
                 }
 
-                ExportGeometry(leaf->mObjects); 
+                if (0) ExportGeometry(leaf->mObjects);  
         }
 
@@ -102 +103 @@
 
 
+bool Exporter::ExportBvHierarchy(const BvHierarchy &bvHierarchy, 
+                                                                 const int maxPvs)
+{
+        vector<BvhLeaf *> leaves;
+        bvHierarchy.CollectLeaves(leaves);
+
+        mUseForcedMaterial = true;
+
+        vector<BvhLeaf *>::const_iterator it, it_end = leaves.end();
+
+        Material white; 
+        white.mDiffuseColor.r = 1;
+        white.mDiffuseColor.g = 1;
+        white.mDiffuseColor.b = 1;
+        int objSize = 0;
+
+        for (it = leaves.begin(); it != it_end; ++ it)
+        {
+                BvhLeaf *leaf = *it;
+
+                SetWireframe();
+                SetForcedMaterial(white);
+                ExportBox(leaf->GetBoundingBox());
+                
+                SetFilled();
+
+                if (maxPvs) // color code pvs
+                {
+                        mForcedMaterial.mDiffuseColor.b = 1.0f;
+                        const float importance = (float)leaf->mObjects.size() / (float)maxPvs;
+
+                        mForcedMaterial.mDiffuseColor.r = importance;
+                        mForcedMaterial.mDiffuseColor.g = 1.0f - mForcedMaterial.mDiffuseColor.r;
+                }
+                else
+                {
+                        SetForcedMaterial(RandomMaterial());
+                }
+
+                if (1) 
+                {
+                        SetFilled();
+                        ExportGeometry(leaf->mObjects);
+                        objSize += leaf->mObjects.size();
+                }
+        }
+
+        return true;
 }
+
+
+}

GTP/trunk/Lib/Vis/Preprocessing/src/Exporter.h

@@ -29 +29 @@
 class OspTree;
 class KdIntersectable;
-
+class BvHierarchy;
 
 class Exporter
@@ -149 +149 @@
 
   void ExportKdIntersectable(const KdIntersectable &kdObj);
+  bool ExportBvHierarchy(const BvHierarchy &bvHierarchy, const int maxPvs);
 };
  

GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.cpp

@@ -135 +135 @@
 
         SubdivisionCandidate *osc = 
-                mOspTree->PrepareConstruction(sampleRays, objects, forcedViewSpace, objectSpaceRays);
+                mOspTree->PrepareConstruction(sampleRays, objects, objectSpaceRays);
 
         mTQueue.Push(osc);
@@ -145 +145 @@
         const float costDecr = tData.GetRenderCostDecrease();
 
-        //mTotalCost -= costDecr;
-        //mTotalPvsSize += tFrontData.mPvs + tBackData.mPvs - tData.mPvs;
-
-        AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
-                                                costDecr,
-                                                mTotalCost
-                                                );
+        switch (mObjectSpaceSubdivisonType)
+        {
+        case KD_BASED_OBJ_SUBDIV:
+                AddSubdivisionStats(mOspTree->mOspStats.Leaves() + mVspTree->mVspStats.Leaves(),
+                                                        costDecr,
+                                                        mTotalCost
+                                                        );
+                break;
+        case BV_BASED_OBJ_SUBDIV:
+                AddSubdivisionStats(mBvHierarchy->mBvhStats.Leaves() + mVspTree->mVspStats.Leaves(),
+                                                        costDecr,
+                                                        mTotalCost
+                                                        );
+                break;
+        default:
+                AddSubdivisionStats(mVspTree->mVspStats.Leaves(),
+                                                        costDecr,
+                                                        mTotalCost
+                                                        );
+                break;
+        }
 }
 
@@ -198 +212 @@
 
 
-bool HierarchyManager::SubdivideSubdivisionCandidate(SubdivisionCandidate *sc)
+bool HierarchyManager::ApplySubdivisionCandidate(SubdivisionCandidate *sc)
 {
         const bool globalTerminationCriteriaMet = 
@@ -211 +225 @@
         else
         {
-                KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
+                if (mObjectSpaceSubdivisonType == KD_BASED_OBJ_SUBDIV)
+                {
+                        KdNode *n = mOspTree->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
+                }
+                else if (mObjectSpaceSubdivisonType == BV_BASED_OBJ_SUBDIV)
+                {
+                        BvhNode *n = mBvHierarchy->Subdivide(mTQueue, sc, globalTerminationCriteriaMet);
+                }
         }
         
@@ -241 +262 @@
                 //-- subdivide leaf node
 
-                if (SubdivideSubdivisionCandidate(splitCandidate))
+                if (ApplySubdivisionCandidate(splitCandidate))
                 {
                         // subdivision successful
@@ -249 +270 @@
                         // for view space splits, this would be object space splits
                         // and other way round
-                        if (repair)
-                                RepairQueue();
+                        if (repair) RepairQueue();
 
                         cout << "candidate: " << splitCandidate->Type() << ", priority: " << splitCandidate->GetPriority() << endl;
@@ -455 +475 @@
 
 
-void HierarchyManager::ExportObjectSpaceHierarchyForViz(const ObjectContainer &objects) const
+void HierarchyManager::ExportObjectSpaceHierarchy(Exporter *exporter,
+                                                                                                  const ObjectContainer &objects) const
 {
         switch (mObjectSpaceSubdivisonType)
@@ -461 +482 @@
         case KD_BASED_OBJ_SUBDIV:
                 {
-                        ExportOspTreeForViz(objects);
-                        break;
-                }
-        case BV_BASED_OBJ_SUBDIV:
-                {
-                        ExportBvhForViz(objects);
+                        ExportOspTree(exporter, objects);
+                        break;
+                }
+        case BV_BASED_OBJ_SUBDIV:
+                {
+                        ExportBvHierarchy(exporter, objects);
                         break;
                 }
@@ -475 +496 @@
 
 
-void HierarchyManager::ExportBvhForViz(const ObjectContainer &objects) const
-{
-}
-
-
-void HierarchyManager::ExportOspTreeForViz(const ObjectContainer &objects) const
-{
-        //-- export final object partition
-        Exporter *exporter = Exporter::GetExporter("final_object_partition.wrl");
-                
-        if (exporter)
-        {
-                cout << "exporting object space partition ... ";
-
-                if (1) exporter->ExportGeometry(objects);
+void HierarchyManager::ExportBvHierarchy(Exporter *exporter, 
+                                                                                 const ObjectContainer &objects) const
+{
+        exporter->SetWireframe();
+        exporter->ExportBvHierarchy(*mBvHierarchy, 0);
+}
+
+
+void HierarchyManager::ExportOspTree(Exporter *exporter, 
+                                                                         const ObjectContainer &objects) const
+{
+        if (0) exporter->ExportGeometry(objects);
                         
-#if 0           
-                // export rays
-                exporter->ExportRays(visRays, RgbColor(0, 1, 0));
-#endif
-                exporter->SetWireframe();
-        
-                const int colorCode = 0;
-                const int maxPvs = 0;//mOspTree.GetStatistics().maxPvs;
-
-                exporter->ExportOspTree(*mOspTree, 0);
-                delete exporter;
-
-                cout << "finished" << endl;
-        }
+        exporter->SetWireframe();
+        const int maxPvs = 0;//mOspTree.GetStatistics().maxPvs;
+
+        exporter->ExportOspTree(*mOspTree, 0);
 }
 
@@ -561 +569 @@
         case KD_BASED_OBJ_SUBDIV:
                 {
-                        ConstructOspTree(sampleRays, objects, forcedViewSpace);
-                        break;
-                }
-        case BV_BASED_OBJ_SUBDIV:
-                {
-                        ConstructBvHierarchy(sampleRays, objects, forcedViewSpace);
+                        ConstructOspTree(sampleRays, objects);
+                        break;
+                }
+        case BV_BASED_OBJ_SUBDIV:
+                {
+                        ConstructBvHierarchy(sampleRays, objects);
                         break;
                 }
@@ -576 +584 @@
 
 void HierarchyManager::ConstructBvHierarchy(const VssRayContainer &sampleRays,
-                                                                                        const ObjectContainer &objects,
-                                                                                        AxisAlignedBox3 *forcedViewSpace) 
+                                                                                        const ObjectContainer &objects
+                                                                                        //,AxisAlignedBox3 *forcedViewSpace
+                                                                                        ) 
 
 {
@@ -583 +592 @@
         cout << "starting bv hierarchy construction ... " << endl;
 
+        //ObjectContainer obj = objects;
+
+        // compute first candidate
+        SubdivisionCandidate *sc =
+                mBvHierarchy->PrepareConstruction(sampleRays, objects);
+
+        mTotalCost = mBvHierarchy->mTotalCost;
+        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
+        
+    mTQueue.Push(sc);
+
+        mBvHierarchy->mBvhStats.Reset();
+        mBvHierarchy->mBvhStats.Start();
+
+        const long startTime = GetTime();
+        const bool repairQueue = false;
+
+        // process object space candidates
+        RunConstruction(repairQueue);
+        
+        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+
+        mBvHierarchy->mBvhStats.Stop();
+}
+
+
+void HierarchyManager::ConstructOspTree(const VssRayContainer &sampleRays,
+                                                                                const ObjectContainer &objects) 
+
+{
+        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
+
+        Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
+        cout << "starting osp tree construction ... " << endl;
+
         // start with one big kd cell - all objects can be seen from everywhere
         // note: only true for view space = object space
 
-        ObjectContainer obj = objects;
-
         // compute first candidate
-        SubdivisionCandidate *sc =
-                mBvHierarchy->PrepareConstruction(sampleRays, obj, forcedViewSpace);
-
+        SubdivisionCandidate *osc =
+                mOspTree->PrepareConstruction(sampleRays, objects, *objectSpaceRays);
+
+        mTotalCost = mOspTree->mTotalCost;
         Debug << "reseting cost, new total cost: " << mTotalCost << endl;
-        mTotalCost = mOspTree->mTotalCost;
-
-    mTQueue.Push(sc);
+        
+    mTQueue.Push(osc);
 
         mOspTree->mOspStats.Reset();
@@ -602 +644 @@
         const long startTime = GetTime();
         const bool repairQueue = false;
-
+        
         // process object space candidates
         RunConstruction(repairQueue);
@@ -618 +660 @@
 }
 
-
-void HierarchyManager::ConstructOspTree(const VssRayContainer &sampleRays,
-                                                                                const ObjectContainer &objects,
-                                                                                AxisAlignedBox3 *forcedViewSpace) 
-
-{
-        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
-
-        Debug << "\n$$$$$$$$$ osp tree construction $$$$$$$$$$\n" << endl;
-        cout << "starting osp tree construction ... " << endl;
-
-        // start with one big kd cell - all objects can be seen from everywhere
-        // note: only true for view space = object space
-
-        // compute first candidate
-        SubdivisionCandidate *osc =
-                mOspTree->PrepareConstruction(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
-
-        Debug << "reseting cost, new total cost: " << mTotalCost << endl;
-        mTotalCost = mOspTree->mTotalCost;
-
-    mTQueue.Push(osc);
-
-        mOspTree->mOspStats.Reset();
-        mOspTree->mOspStats.Start();
-
-        const long startTime = GetTime();
-        const bool repairQueue = false;
-        
-        // process object space candidates
-        RunConstruction(repairQueue);
-        
-        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
-
-        mOspTree->mOspStats.Stop();
-
-        //////////////////////////
-        // matt: only for debugging purpose
-
-        const float rc = mOspTree->EvalRenderCost(sampleRays);
-
-        Debug << "My render cost evalulation: " << rc << endl;
-}
-
-}
+}

GTP/trunk/Lib/Vis/Preprocessing/src/HierarchyManager.h

@@ -40 +40 @@
 class KdTreeStatistics;
 class BvHierarchy;
-
+class Exporter;
 
 #if 0
@@ -154 +154 @@
         VspTree *GetVspTree() { return mVspTree; }
 
-        void ExportObjectSpaceHierarchyForViz(const ObjectContainer &objects) const;
+        void ExportObjectSpaceHierarchy(
+                Exporter *exporter, 
+                const ObjectContainer &objects) const;
 
 
@@ -172 +174 @@
 
         void RunConstruction(const bool repair);
-        bool SubdivideSubdivisionCandidate(SubdivisionCandidate *sc);
+        bool ApplySubdivisionCandidate(SubdivisionCandidate *sc);
 
         bool FinishedConstruction() const;
@@ -199 +201 @@
         void CollectObjectSpaceDirtyList(SubdivisionCandidateContainer &dirtyList);
                 
-        void ExportOspTreeForViz(const ObjectContainer &objects) const;
-        void ExportBvhForViz(const ObjectContainer &objects) const;
+        void ExportOspTree(Exporter *exporter, const ObjectContainer &objects) const;
+        void ExportBvHierarchy(Exporter *exporter, const ObjectContainer &objects) const;
+
 
         void ConstructBvHierarchy(
                 const VssRayContainer &sampleRays,
-                const ObjectContainer &objects,
-                AxisAlignedBox3 *forcedViewSpace);
+                const ObjectContainer &objects);
 
         void ConstructOspTree(
                 const VssRayContainer &sampleRays,
-                const ObjectContainer &objects,
-                AxisAlignedBox3 *forcedViewSpace);
+                const ObjectContainer &objects);
 
 protected:

GTP/trunk/Lib/Vis/Preprocessing/src/Mesh.cpp

@@ -9 +9 @@
 bool MeshDebug = false;
 
-int Intersectable::sMailId = 21843194198;
+int Intersectable::sMailId = 2147483647;
 int Intersectable::sReservedMailboxes = 1;
 

GTP/trunk/Lib/Vis/Preprocessing/src/OspTree.cpp

@@ -397 +397 @@
         backData.mNode = back;
 
-
         // compute probability, i.e., volume of seen view cells
         frontData.mProbability = EvalViewCellsVolume(front, *frontData.mRays);
         backData.mProbability =  EvalViewCellsVolume(back, *backData.mRays);
-
 
         //delete leaf;
@@ -1648 +1646 @@
 
 
-void OspTree::ComputeBoundingBox(const ObjectContainer &objects,
-                                                                 AxisAlignedBox3 *forcedBoundingBox) 
-{
-        if (forcedBoundingBox)
-        {
-                mBoundingBox = *forcedBoundingBox;
-        }
-        else // compute vsp tree bounding box
-        {
-                mBoundingBox.Initialize();
-
-                ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-                //-- compute bounding box
-        for (oit = objects.begin(); oit != oit_end; ++ oit)
-                {
-                        Intersectable *obj = *oit;
-
-                        // compute bounding box of view space
-                        mBoundingBox.Include(obj->GetBox());
-                }
+void OspTree::ComputeBoundingBox(const ObjectContainer &objects) 
+{
+        mBoundingBox.Initialize();
+
+        ObjectContainer::const_iterator oit, oit_end = objects.end();
+
+        //-- compute bounding box
+        for (oit = objects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *obj = *oit;
+
+                // compute bounding box of view space
+                mBoundingBox.Include(obj->GetBox());
         }
 }
@@ -2657 +2647 @@
 SubdivisionCandidate * OspTree::PrepareConstruction(const VssRayContainer &sampleRays,
                                                                                                         const ObjectContainer &objects,
-                                                                                                        AxisAlignedBox3 *forcedObjectSpace,
                                                                                                         RayInfoContainer &rays)
 {
@@ -2665 +2654 @@
         
         // compute bounding box from objects
-        ComputeBoundingBox(objects, forcedObjectSpace);
+        ComputeBoundingBox(objects);
 
         mTermMinProbability *= mBoundingBox.GetVolume();

GTP/trunk/Lib/Vis/Preprocessing/src/OspTree.h

@@ -627 +627 @@
                 @returns pvs size of the node
         */
-        float PrepareHeuristics(const OspTraversalData &tData, ViewCellContainer &touchedViewCells);
+        float PrepareHeuristics(
+                const OspTraversalData &tData, 
+                ViewCellContainer &touchedViewCells);
 
         /** Prepares heuristics for a particular ray.
         */
-        void PrepareHeuristics(const VssRay &ray, ViewCellContainer &touchedViewCells);
+        void PrepareHeuristics(
+                const VssRay &ray, 
+                ViewCellContainer &touchedViewCells);
 
         /** Prepares construction for vsp and osp trees.
         */
-        void ComputeBoundingBox(const ObjectContainer &objects,
-                                                        AxisAlignedBox3 *forcedBoundingBox);
+        void ComputeBoundingBox(const ObjectContainer &objects);
 
         void CollectDirtyCandidates(OspSubdivisionCandidate *sc,
@@ -727 +730 @@
                 const VssRayContainer &sampleRays,
                 const ObjectContainer &objects,
-                AxisAlignedBox3 *forcedObjectSpace,
                 RayInfoContainer &rays);
 

GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.cpp

@@ -18 +18 @@
 #include "BvHierarchy.h"
 #include "HierarchyManager.h"
+#include "VssRay.h"
+
 
 #ifdef GTP_INTERNAL
@@ -483 +485 @@
                 const bool ishack = true;
 
-                if (ishack)
-                {
+                /*if (ishack)
                         mHierarchyManager = new HierarchyManager(mVspTree, mKdTree);
-                }
                 else
-                {
                         mHierarchyManager = new HierarchyManager(mVspTree, HierarchyManager::KD_BASED_OBJ_SUBDIV);
-                }
+                */
+                mHierarchyManager = new HierarchyManager(mVspTree, HierarchyManager::BV_BASED_OBJ_SUBDIV);
 
                 mViewCellsManager = new VspOspViewCellsManager(vcTree, mHierarchyManager);
@@ -831 +831 @@
                                                                 objectB,
                                                                 objectA,
-                                                                probability,
-                                                                mPass);
+                                                                mPass,
+                                                                probability
+                                                                );
 
                         vssRays.push_back(vssRay);
@@ -844 +845 @@
                                                                 objectA,
                                                                 objectB,
-                                                                probability,
-                                                                mPass);
+                                                                mPass,
+                                                                probability
+                                                                );
 
                         vssRays.push_back(vssRay);

GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.h

@@ -28 +28 @@
 class BvHierarchy;
 class Intersectable;
+class VssRay;
 
 /** Namespace for the external visibility preprocessor

GTP/trunk/Lib/Vis/Preprocessing/src/Preprocessor.vcproj

@@ -27 +27 @@
                                 RuntimeTypeInfo="TRUE"
                                 UsePrecompiledHeader="0"
+                                BrowseInformation="1"
                                 WarningLevel="3"
                                 Detect64BitPortabilityProblems="TRUE"
@@ -68 +69 @@
                                 OmitFramePointers="TRUE"
                                 EnableFiberSafeOptimizations="TRUE"
-                                OptimizeForProcessor="3"
+                                OptimizeForProcessor="0"
                                 OptimizeForWindowsApplication="TRUE"
                                 AdditionalIncludeDirectories="..\include;..\src;..\..\..\..\..\..\NonGTP\Devil\include;..\..\..\..\..\..\NonGTP\Zlib\include;..\..\..\..\..\..\NonGTP\Xerces;..\..\..\..\..\..\NonGTP\Boost"

GTP/trunk/Lib/Vis/Preprocessing/src/TestPreprocessor.vcproj

@@ -26 +26 @@
                                 RuntimeLibrary="3"
                                 UsePrecompiledHeader="0"
+                                BrowseInformation="1"
                                 WarningLevel="3"
                                 Detect64BitPortabilityProblems="TRUE"
@@ -75 +76 @@
                                 EnableIntrinsicFunctions="TRUE"
                                 FavorSizeOrSpeed="1"
-                                OptimizeForProcessor="3"
+                                OptimizeForProcessor="0"
                                 OptimizeForWindowsApplication="TRUE"
                                 AdditionalIncludeDirectories="..\include;..\..\..\..\..\..\NonGTP\Boost;..\..\..\..\..\..\NonGTP\Devil\include;..\..\..\..\..\..\NonGTP\Zlib\include;..\..\..\..\..\..\NonGTP\Xerces;..\..\MultiLevelRayTracing"

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCell.cpp

@@ -32 +32 @@
                                            myless<vector<ViewCell *>::value_type> > TraversalQueue;
 
-int ViewCell::sMailId = 0;//21843194198;
+int ViewCell::sMailId = 2147483647;
 int ViewCell::sReservedMailboxes = 1;
 

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsManager.cpp

@@ -5101 +5101 @@
                         cout << "exporting view cells after post process ... ";
 
-                        if (0)
-                        {
-                                // export view space box
-                                exporter->SetWireframe();
-                                exporter->ExportBox(mViewSpaceBox);
-                                exporter->SetFilled();
-                        }
-
                         if (mExportGeometry)
                         {
@@ -5120 +5112 @@
                         }
 
-                        //exporter->SetFilled();
-
                         // HACK: export without clip plane
                         const bool b = mUseClipPlaneForViz;
@@ -5137 +5127 @@
         }
 
-        mHierarchyManager->ExportObjectSpaceHierarchyForViz(objects);
-        
-        //-- export single view cells
+        if (1)
+        {
+                // export final object partition
+                Exporter *exporter = Exporter::GetExporter("final_object_partition.wrl");
+
+                if (exporter)
+                {
+                        cout << "exporting object space hierarchy ... ";
+                        mHierarchyManager->ExportObjectSpaceHierarchy(exporter, objects);
+                
+                        delete exporter;
+                        cout << "finished" << endl;
+                }
+        }
+        
+        // export pvss of some view cell
         ExportPvs(objects, visRays);
 }

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsParser.cpp

@@ -159 +159 @@
         if (mObjectSpaceHierarchyType == OSP)
         {
+                // for a spatial subdivision, it is not necessary to store
+                // the objects with the leaves, they can be classified now
                 mHierarchyManager->mOspTree->InsertObjects(
                         mHierarchyManager->mOspTree->mRoot, *mObjects);
         }
+        else
+                cout << "here209" << endl;
+
 }
 
@@ -279 +284 @@
 
 
-void ViewCellsParseHandlers::StartHierarchy(AttributeList&  attributes)
-{
-        int len = attributes.getLength();
-  
-        for (int i = 0; i < len; ++ i) 
-        {
-                string attrName(StrX(attributes.getName(i)).LocalForm());
-                
-                if (attrName == "name") 
-                {
-                        StrX attrValue(attributes.getValue(i));
-                        
-                        const char *ptr = attrValue.LocalForm();
-                        
-                        // the view cells manager is created here
-                        //CreateViewCellsManager(ptr);
-                }
-        }
-}
-
-
 void ViewCellsParseHandlers::StartBspElement(string element,
                                                                                          AttributeList& attributes)
@@ -437 +421 @@
                 // create new view cells hierarchy
                 mViewCellsTree = new ViewCellsTree();
-        }
-
-        // decides about the view cells manager type
-        if (element == "Hierarchy")
-        {
-                cout << "parsing view cells manager type" << endl;
-                StartHierarchy(attributes);
         }
 
@@ -688 +665 @@
                 const char *ptr = attrValue.LocalForm();
 
-
                 if (attrName == "id")
                 {
@@ -711 +687 @@
 void ViewCellsParseHandlers::StartBspLeaf(AttributeList& attributes)
 {
-        BspLeaf * leaf = 
-                new BspLeaf(dynamic_cast<BspInterior *>(mCurrentBspNode), NULL);
+        BspLeaf * leaf;
 
         if (mCurrentBspNode) // replace front or (if not NULL) back child
         {
-                dynamic_cast<BspInterior *>(mCurrentBspNode)->ReplaceChildLink(NULL, leaf);
+                BspInterior *interior = dynamic_cast<BspInterior *>(mCurrentBspNode);
+
+                leaf = new BspLeaf(interior);
+                interior->ReplaceChildLink(NULL, leaf);
         }
         else
         {
+                leaf = new BspLeaf();
                 mVspBspTree->mRoot = leaf;
         }
@@ -797 +776 @@
         if (mCurrentBspNode) // replace NULL child of parent with current node
         {
-                BspInterior *current = dynamic_cast<BspInterior *>(mCurrentBspNode);
-
-                current->ReplaceChildLink(NULL, interior);
-                interior->SetParent(current);
+                BspInterior *parent = dynamic_cast<BspInterior *>(mCurrentBspNode);
+
+                parent->ReplaceChildLink(NULL, interior);
+                interior->SetParent(parent);
         }
         else
@@ -856 +835 @@
 void ViewCellsParseHandlers::CreateViewSpaceHierarchy()
 {
-        ViewCellContainer::iterator it, it_end = mViewCells.end();
-        cout << "\n====================" << endl << endl;
-        for (it = mViewCells.begin(); it != it_end; ++ it)
-        {
-                cout << (*it)->GetId() << " ";
-        }
-cout << endl;
         if (mViewSpaceHierarchyType == BSP)
         {
@@ -936 +908 @@
                 }
         }
-        cout << "************************" << endl;
-        it_end = mViewCells.end();
-        for (it = mViewCells.begin(); it != it_end; ++ it)
-        {
-                cout << (*it)->GetId() << " ";
-        }
-        cout << endl;
-        cout << "\nview space box: " << mViewSpaceBox << endl;
+        //cout << "\nview space box: " << mViewSpaceBox << endl;
 }
 
@@ -992 +957 @@
 void ViewCellsParseHandlers::StartVspLeaf(AttributeList& attributes)
 {
-        VspLeaf * leaf = 
-                new VspLeaf(dynamic_cast<VspInterior *>(mCurrentVspNode), NULL);
-
+        VspLeaf * leaf;
+                
         if (mCurrentVspNode) // replace front or (if not NULL) back child
         {
-                dynamic_cast<VspInterior *>(mCurrentVspNode)->ReplaceChildLink(NULL, leaf);
+                VspInterior *interior = dynamic_cast<VspInterior *>(mCurrentVspNode);
+                leaf = new VspLeaf(interior);
+                interior->ReplaceChildLink(NULL, leaf);
         }
         else
         {
+                leaf = new VspLeaf();
                 mVspTree->mRoot = leaf;
         }
@@ -1029 +996 @@
                 dummyVc.SetId(viewCellId);
 
-                cout << "\nsearching view cell with id " << viewCellId << endl;
+                //cout << "\nsearching view cell with id " << viewCellId << endl;
 
                 ViewCellContainer::iterator vit =
@@ -1087 +1054 @@
                 AxisAlignedBox3 frontBox, backBox;
 
-                parent->GetBoundingBox().Split(parent->GetPlane().mAxis, parent->GetPlane().mPosition, frontBox, backBox);
+                parent->GetBoundingBox().Split(
+                        parent->GetPlane().mAxis, 
+                        parent->GetPlane().mPosition, 
+                        frontBox, 
+                        backBox);
+
                 if (parent->GetFront() == interior)
                         interior->SetBoundingBox(frontBox);
@@ -1134 +1106 @@
 
                 parent->mBox.Split(parent->mAxis, parent->mPosition, frontBox, backBox);
+
                 if (parent->mFront == interior)
                         interior->mBox = frontBox;
@@ -1180 +1153 @@
                 if (attrName == "min") 
                 {
-                        sscanf(ptr, "%f %f %f", &minBox);
+                        sscanf(ptr, "%f %f %f", &minBox.x, &minBox.y, &minBox.z);
                 }
                 if (attrName == "max") 
                 {
-                        sscanf(ptr, "%f %f %f", &maxBox);
+                        sscanf(ptr, "%f %f %f", &maxBox.x, &maxBox.y, &maxBox.z);
                 }
                 if (attrName == "objects")
@@ -1192 +1165 @@
         }
 
-        BvhLeaf * leaf = 
-                new BvhLeaf(AxisAlignedBox3(minBox, maxBox), 
-                                        dynamic_cast<BvhInterior *>(mCurrentBvhNode), (int)objects.size());
+        AxisAlignedBox3 box = AxisAlignedBox3(minBox, maxBox);
+
+        BvhLeaf *leaf;
+
+        if (mCurrentBvhNode) // replace front or (if not NULL) back child
+        {
+                BvhInterior *interior = dynamic_cast<BvhInterior *>(mCurrentBvhNode);
+                leaf = new BvhLeaf(box, interior, (int)objects.size());
+                interior->ReplaceChildLink(NULL, leaf);
+        }
+        else
+        {
+                leaf = new BvhLeaf(box, NULL, (int)objects.size());
+                mHierarchyManager->mBvHierarchy->mRoot = leaf;
+        }
 
         leaf->mObjects = objects;
-
-        if (mCurrentBvhNode) // replace front or (if not NULL) back child
-        {
-                dynamic_cast<BvhInterior *>(mCurrentBvhNode)->ReplaceChildLink(NULL, leaf);
-        }
-        else
-        {
-                mHierarchyManager->mBvHierarchy->mRoot = leaf;
-        }
 }
 
@@ -1219 +1195 @@
         {
                 const int index = strtol(ptr, &endptr, 10);
-
                 if (ptr == endptr) break;
 
                 objIndices.push_back(index);
-
                 ptr = endptr;
         }
@@ -1239 +1213 @@
 
                 ObjectContainer::iterator oit =
-                        lower_bound(mObjects->begin(), mObjects->end(), (Intersectable *)&dummyInst, ilt);      
+                        lower_bound(mObjects->begin(), 
+                                                mObjects->end(), 
+                                                (Intersectable *)&dummyInst, 
+                                                ilt);   
                                                         
                 if ((oit != mObjects->end()) && ((*oit)->GetId() == objId))
@@ -1260 +1237 @@
         for (int i = 0; i < len; ++ i) 
         {
+                cout << "here5" << endl;
                 string attrName(StrX(attributes.getName(i)).LocalForm());
                 StrX attrValue(attributes.getValue(i));
@@ -1265 +1243 @@
 
                 if (attrName == "min") 
-                {
-                        sscanf(ptr, "%f %f %f", &minBox);
+                {cout << "here6" << endl;
+                        sscanf(ptr, "%f %f %f", &minBox.x, &minBox.y, &minBox.z);
                 }
                 if (attrName == "max") 
-                {
-                        sscanf(ptr, "%f %f %f", &maxBox);
+                {cout << "here7" << endl;
+                        sscanf(ptr, "%f %f %f", &maxBox.x, &maxBox.y, &maxBox.z);
                 }
         }
@@ -1278 +1256 @@
         if (mCurrentBvhNode) // replace NULL child of parent with current node
         {
+                cout << "here8" << endl;
                 BvhInterior *parent = dynamic_cast<BvhInterior *>(mCurrentBvhNode);
                 parent->ReplaceChildLink(NULL, interior);
@@ -1283 +1262 @@
         }
         else
-        {
-                mBvHierarchy->mRoot = interior;
-        }
-
+        {cout << "here18" << endl;
+                mHierarchyManager->mBvHierarchy->mRoot = interior;
+        }
+cout << "here28" << endl;
         mCurrentBvhNode = interior;
 }

GTP/trunk/Lib/Vis/Preprocessing/src/ViewCellsParserXerces.h

@@ -77 +77 @@
   VspBspTree *mVspBspTree;
   HierarchyManager *mHierarchyManager;
-  BvHierarchy *mBvHierarchy;
+  //vHierarchy *mBvHierarchy;
 
   BspTree *mBspTree;
@@ -129 +129 @@
   void EndViewCells();
   void EndBoundingBoxes();
-        
-  void StartHierarchy(AttributeList& attributes);
 
   void StartBspElement(string element, AttributeList& attributes);

GTP/trunk/Lib/Vis/Preprocessing/src/VrmlExporter.cpp

@@ -1181 +1181 @@
         }
 
-        // hack: all object exported as one mesh
+        ///////////////////////////////////
+        // method 2 (hacky)
+        // all object exported as one mesh
         PolygonContainer polys;
 
         for (oit = objects.begin(); oit != oit_end; ++ oit)
         {
-                polys.push_back(new Polygon3(dynamic_cast<MeshInstance *>(*oit)->GetMesh()->mVertices));
+                MeshInstance *mi = dynamic_cast<MeshInstance *>(*oit);
+                polys.push_back(new Polygon3(mi->GetMesh()->mVertices));
         }
 

GTP/trunk/Lib/Vis/Preprocessing/src/VspTree.cpp

@@ -2854 +2854 @@
 void VspTree::GetViewCells(const VssRay &ray, ViewCellContainer &viewCells)
 {
-#if 0 
+#if 1 
         // use view cells manager to compute view cells
-        mViewCellsManager->ComputeSampleContribution(ray, false, true);
-        viewCells = ray.mViewCells;
-        ray.mViewCells.clear();
-        
+        VssRay vcRay(ray);
+
+        mViewCellsManager->ComputeSampleContribution(vcRay, false, true);
+        viewCells = vcRay.mViewCells;
 #else
         static Ray hray;

GTP/trunk/Lib/Vis/Preprocessing/src/common.h

@@ -269 +269 @@
 
 
-
+/*inline int
+RandomValue(int a, int b)
+{
+        int range = abs(a - b);
+        return (rand() * range) / RAND_MAX + ((a < b) ? a : b);
+}*/
 
 inline Real sqr(Real a)
@@ -275 +280 @@
   return a*a;
 }
+
 
 template <class T>