Changeset 1074

Timestamp:

07/05/06 08:43:09 (18 years ago)

Author:

mattausch

Message:

wked on view space object space partition

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• Environment.cpp (modified) (4 diffs)
• Intersectable.h (modified) (2 diffs)
• KdTree.cpp (modified) (4 diffs)
• KdTree.h (modified) (2 diffs)
• ViewCellsManager.cpp (modified) (10 diffs)
• ViewCellsManager.h (modified) (2 diffs)
• VrmlExporter.cpp (modified) (1 diff)
• VspBspTree.cpp (modified) (1 diff)
• VspOspTree.cpp (modified) (28 diffs)
• VspOspTree.h (modified) (3 diffs)
• VssPreprocessor.cpp (modified) (3 diffs)

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

@@ -1990 +1990 @@
                                         optFloat,
                                         "vsp_bsp_construction_min_band=",
-                                        "0.1");
+                                        "0.01");
 
         RegisterOption("VspBspTree.Construction.maxBand",
                                         optFloat,
                                         "vsp_bsp_construction_min_band=",
-                                        "0.9");
+                                        "0.99");
 
         RegisterOption("VspBspTree.Construction.useDrivingAxisForMaxCost",
@@ -2120 +2120 @@
                                         "0.001");
 
-        
         RegisterOption("VspTree.Termination.maxRayContribution",
                         optFloat,
@@ -2147 +2146 @@
                                         "0.0001");
 
-        RegisterOption("VspTree.useSplitCostQueue",
-                optBool,
-                "vsp_use_split_cost_queue=",
-                "true");
-
         RegisterOption("VspTree.Termination.globalCostMissTolerance",
                                         optInt,
@@ -2200 +2194 @@
                                         optFloat,
                                         "vsp_construction_min_band=",
-                                        "0.1");
+                                        "0.01");
 
         RegisterOption("VspTree.Construction.maxBand",
                                         optFloat,
-                                        "vsp_construction_min_band=",
-                                        "0.9");
+                                        "vsp_construction_max_band=",
+                                        "0.99");
+
+        RegisterOption("VspTree.pvsCountMethod",
+                                        optInt,
+                                        "vsp_pvs_count_method=",
+                                        "1");
+
 
         //////////////////////////////////////////////////////////////////////////////////

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

@@ -4 +4 @@
 #include "AxisAlignedBox3.h"
 #include "Pvs.h"
+#include <set>
 
 namespace GtpVisibilityPreprocessor {
@@ -28 +29 @@
   
   /// kd leaves that this intersectable belongs to
-  std::vector<KdLeaf *> mKdLeaves;
+  set<KdLeaf *> mKdLeaves;
 
   enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEW_CELL, OGRE_MESH_INSTANCE };

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

@@ -90 +90 @@
         mBox.Include((*mi)->GetBox());
   }
+
+        ProcessLeafObjects(leaf, NULL);
 
   cout <<"KdTree Root Box:"<<mBox<<endl;
@@ -281 +283 @@
   KdLeaf *front = new KdLeaf(node, objectsFront);
 
+ 
   // replace a link from node's parent
   if (  leaf->mParent )
@@ -304 +307 @@
   }
   
+   ProcessLeafObjects(back, leaf);
+    ProcessLeafObjects(front, leaf);
+
   delete leaf;
   return node;
@@ -1087 +1093 @@
 }
 
-}
+
+void KdTree::ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const
+{
+        ObjectContainer::const_iterator oit, oit_end = leaf->mObjects.end();
+
+        for (oit = leaf->mObjects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *object = *oit;
+
+                if (parent)
+                {
+                        set<KdLeaf *>::iterator kdit = object->mKdLeaves.find(parent);
+
+                        // remove parent leaf
+                        if (kdit != object->mKdLeaves.end())
+                                object->mKdLeaves.erase(kdit);
+                }
+
+                object->mKdLeaves.insert(leaf);
+
+                if (object->mKdLeaves.size() > 1)
+                        leaf->mMultipleObjects.push_back(object);
+        }
+}
+
+
+}

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

@@ -191 +191 @@
   /** Objects that are part of several leaves.
   */
-  ObjectMap mMultipleObjects;
+  ObjectContainer mMultipleObjects;
 
   /// universal counter
@@ -530 +530 @@
               );
 
+
+  /** does some post processing on the objects that are contained
+  in this leaf.
+  */
+  void ProcessLeafObjects(KdLeaf *leaf, KdLeaf *parent) const;
 
   int mTermMaxNodes;

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

@@ -454 +454 @@
         bool dirSamples = (mSamplingType == Preprocessor::DIRECTION_BASED_DISTRIBUTION);
 
-        // -- the main loop
+        //-- do some more sampling
         while (numSamples < n)
         {
@@ -490 +490 @@
         }
 
-        
         //-- post processing
         VssRayContainer postProcessSamples;
 
-        //-- construction rays 
+        cout << "casting " << mPostProcessSamples << " post processing samples ... ";
+
+        // cast post processing samples rays  (storing the view cells if wanted)
         CastPassSamples(mPostProcessSamples,
                                         mSamplingType, 
                                         postProcessSamples);
 
+        cout << "finished" << endl;
 
         // stats before post processing (i.e., merge)
@@ -542 +544 @@
 
         //-- visualization
+
         if (mShowVisualization)
         {
@@ -1727 +1730 @@
 {
         mViewSpaceBox = box;
-        Debug << "here111 " << mViewSpaceBox << endl;
+        
         // hack: create clip plane relative to new view space box
         CreateClipPlane();
@@ -4853 +4856 @@
         mMaxPvsSize = (int)(mMaxPvsRatio * (float)objects.size());
 
-        Debug << "here125 view space box " << mViewSpaceBox << endl;
-
-        // if view cells were already constructed
+        // skip rest if view cells were already constructed
         if (ViewCellsConstructed())
                 return 0;
@@ -5277 +5278 @@
 
         //-- export single view cells
-        ExportBspPvs(objects, visRays);
-}
-
-
-void VspOspViewCellsManager::ExportBspPvs(const ObjectContainer &objects,
-                                                                                  const VssRayContainer &rays)
+        ExportPvs(objects, visRays);
+}
+
+
+void VspOspViewCellsManager::ExportPvs(const ObjectContainer &objects,
+                                                                           const VssRayContainer &rays)
 {
         int leafOut;
@@ -5315 +5316 @@
                 if (sortViewCells) // largest view cell pvs first
                         vc = mViewCells[i];
-                else
+                else // random view cell
                         vc = mViewCells[(int)RandomValue(0, (float)mViewCells.size() - 1)];
 
@@ -5328 +5329 @@
 
                 //-- export the sample rays
-                if (mExportRays)
+                if (1 || mExportRays)
                 {
                         // output rays stored with the view cells during subdivision
@@ -5408 +5409 @@
 
 
-                //-- export pvs
                 if (1)
-                {
+                {       //-- export pvs
                         ObjectPvsMap::const_iterator oit,
                                 oit_end = pvs.mEntries.end();
@@ -5416 +5416 @@
                         Intersectable::NewMail();
 
-                        // output PVS of view cell
+                        vector<KdLeaf *> kdLeaves;
+
+                        KdLeaf::NewMail();
+
+                        m.mDiffuseColor = RgbColor(1, 0, 0);
+                        exporter->SetForcedMaterial(m);
+
+                        // find kd nodes
                         for (oit = pvs.mEntries.begin(); oit != oit_end; ++ oit)
-                        {               
-                                Intersectable *intersect = (*oit).first;
-
-                                if (!intersect->Mailed())
+                        {       
+                                // "original" pvs
+                                Intersectable *obj = (*oit).first;
+
+                                if (1 && !obj->Mailed())
                                 {
-                                        m = RandomMaterial();
-                                        exporter->SetForcedMaterial(m);
-
-                                        exporter->ExportIntersectable(intersect);
-                                        intersect->Mail();
+                                        exporter->ExportIntersectable(obj);
+                                        obj->Mail();
+                                }                                       
+
+                                // collect kd leaves
+                                set<KdLeaf *>::const_iterator kdit, kdit_end = obj->mKdLeaves.end();
+
+                                for (kdit = obj->mKdLeaves.begin(); kdit != kdit_end; ++ kdit)
+                                {
+                                        KdLeaf *kdleaf = *kdit;
+
+                                        if (!kdleaf->Mailed())
+                                        {
+                                                kdleaf->Mail();
+                                                kdLeaves.push_back(kdleaf);
+                                        }
                                 }
                         }
-                }
-                
-                if (0)
-                {   // export scene geometry
-                        m.mDiffuseColor = RgbColor(1, 0, 0);
+
+                        m.mDiffuseColor = RgbColor(0, 0, 1);
                         exporter->SetForcedMaterial(m);
 
-                        exporter->ExportGeometry(objects);
-                }
-
+                        // export kd node pvs
+                        Intersectable::NewMail();
+
+                        vector<KdLeaf *>::const_iterator kdit, kdit_end = kdLeaves.end();
+
+                        for (kdit = kdLeaves.begin(); kdit != kdit_end; ++ kdit)
+                        {
+                                KdLeaf *kdleaf = *kdit;
+
+                                //-- export kd node
+                                /*exporter->SetWireframe();
+                                exporter->ExportBox(mKdTree->GetBox(kdleaf));
+                                exporter->SetFilled();*/
+
+                                ObjectContainer::const_iterator oit, oit_end = kdleaf->mObjects.end();
+
+                for (oit = kdleaf->mObjects.begin(); oit != oit_end; ++ oit)
+                                {       
+                                        Intersectable *obj = *oit;
+
+                                        if (!obj->Mailed())
+                                        {
+                                                exporter->ExportIntersectable(obj);
+                                                obj->Mail();                                    
+                                        }                               
+                                }
+                        }
+                }
+        
                 DEL_PTR(exporter);
                 cout << "finished" << endl;

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

@@ -1001 +1001 @@
         */
         void ExportViewCellGeometry(Exporter *exporter, 
-                                                                ViewCell *vc,
-                                                                const AxisAlignedPlane *clipPlane = NULL) const;
-
-        int ComputeBoxIntersections(const AxisAlignedBox3 &box, ViewCellContainer &viewCells) const;
+                ViewCell *vc,
+                const AxisAlignedPlane *clipPlane = NULL) const;
+
+        int ComputeBoxIntersections(const AxisAlignedBox3 &box, 
+                ViewCellContainer &viewCells) const;
         
         void CollectViewCells();
@@ -1019 +1020 @@
         void UpdatePvsForEvaluation(ViewCell *root, ObjectPvs &pvs);
 
-        /** Exports visualization of the BSP PVS.
-        */
-        void ExportBspPvs(const ObjectContainer &objects,
-                                          const VssRayContainer &rays);
+        /** Exports visualization of the PVS.
+        */
+        void ExportPvs(const ObjectContainer &objects,
+                const VssRayContainer &rays);
 
 

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

@@ -101 +101 @@
   stream << "}" << endl; // end material
   stream << "}" << endl; // end appearance
-  Debug << "here8" << endl;
+ 
   stream << "geometry IndexedLineSet { coordIndex [" << endl;
 

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

@@ -1321 +1321 @@
         
         // the relative cost ratio
-        float ratio = /*Limits::Infinity;*/99999999.0f;
+        float ratio = 99999999.0f;
         bool splitPlaneFound = false;
 

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

@@ -274 +274 @@
 {
         DEL_PTR(mPvs);
+        CLEAR_CONTAINER(mVssRays);
 }
 
@@ -349 +350 @@
         Environment::GetSingleton()->GetIntValue("VspTree.Termination.globalCostMissTolerance", mTermGlobalCostMissTolerance);
 
-        // HACK//mTermMinPolygons = 25;
-
         //-- factors for bsp tree split plane heuristics
         Environment::GetSingleton()->GetFloatValue("VspTree.Termination.ct_div_ci", mCtDivCi);
@@ -366 +365 @@
         Environment::GetSingleton()->GetBoolValue("VspTree.simulateOctree", mCirculatingAxis);
         
+        Environment::GetSingleton()->GetIntValue("VspTree.pvsCountMethod", mPvsCountMethod);
 
         char subdivisionStatsLog[100];
@@ -398 +398 @@
         Debug << "minband: " << mMinBand << endl;
         Debug << "maxband: " << mMaxBand << endl;
+        Debug << "pvs count method: " << mPvsCountMethod << endl;
         
 
@@ -650 +651 @@
         splitCandidate.mMaxCostMisses = success ? tData.mMaxCostMisses : tData.mMaxCostMisses + 1;
 
-        Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
+        //Debug << "p: " << tData.mNode << " depth: " << tData.mDepth << endl;
 }
 
@@ -674 +675 @@
                           *backData.mRays);
 
-        Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
+        //Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
         //-- compute pvs
         frontData.mPvs = ComputePvsSize(*frontData.mRays);
@@ -778 +779 @@
                 
                 // warning: rays get never deleted!
-                if (0) leaf->mVssRays.push_back(new VssRay(*ray));
+                if (1) leaf->mVssRays.push_back(new VssRay(*ray));
         }
 }
@@ -804 +805 @@
         float pos;
 
-        if (0)
-        {
-                // float values => don't compare with exact values
-                minBand += Limits::Small;
-                maxBand -= Limits::Small;
-        }
-
         // insert all queries
         for (RayInfoContainer::const_iterator ri = rays.begin(); ri < rays.end(); ++ ri)
@@ -818 +812 @@
                 pos = (*ri).ExtrapOrigin(axis);
                 
-                if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
                                                                         pos, (*ri).mRay));
 
                 pos = (*ri).ExtrapTermination(axis);
-
-                if (0) ClipValue(pos, minBand, maxBand); // clamp to min / max band
 
                 mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
@@ -860 +851 @@
 
 
-void VspTree::PrepareHeuristics(const RayInfoContainer &rays)
+int VspTree::PrepareHeuristics(Intersectable *object)
+{
+        set<KdLeaf *>::const_iterator kit, kit_end = object->mKdLeaves.end();
+        
+        int pvsSize = 0;
+
+        for (kit = object->mKdLeaves.begin(); kit != kit_end; ++ kit)
+        {
+                KdLeaf *node = dynamic_cast<KdLeaf *>(*kit);
+
+                if (!node->Mailed())
+                {
+                        node->Mail();
+                        node->mCounter = 1;
+
+                        //Debug << "here5 "<<(int)node->mObjects.size() <<" "<< node->mMultipleObjects.size()<< " " <<(int)node->mObjects.size() - node->mMultipleObjects.size()<<endl;
+                        // add objects without the objects which are in several kd leaves
+                        pvsSize += (int)(node->mObjects.size() - node->mMultipleObjects.size());
+                }
+                else
+                {
+                        ++ node->mCounter;
+                }
+
+                //-- the objects belonging to several leaves must be handled seperately
+                ObjectContainer::const_iterator oit, oit_end = node->mMultipleObjects.end();
+
+                for (oit = node->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = *oit;
+                                                
+                        if (!object->Mailed())
+                        {
+                                //Debug << "here233: " << object->mKdLeaves.size() << endl;
+                                object->Mail();
+                                object->mCounter = 1;
+
+                                ++ pvsSize;
+                        }
+                        else
+                        {
+                                ++ object->mCounter;
+                        }
+                }
+        }
+
+        return pvsSize;
+}
+
+
+int VspTree::PrepareHeuristics(const RayInfoContainer &rays)
 {       
-        ObjectContainer objects;
-
-        // Collect all pvs that can be seen from the view cell
-        CollectPvs(rays, objects);
-
-        // adjust kd node info table
-        // for each object the entry must be updated 
-        // which belongs to the same kd nodes
-        ObjectContainer::const_iterator oit, oit_end = objects.end();
-
-        for (oit = objects.begin(); oit != oit_end; ++ oit)
-        {
-                Intersectable *obj = *oit;
-                // TODO
-                //UpdateKdNodeInfo(obj);
-        }
+        Intersectable::NewMail();
+        KdNode::NewMail();
+
+        int pvsSize = 0;
+
+        RayInfoContainer::const_iterator ri, ri_end = rays.end();
+
+        //-- set all kd nodes as belonging to the front pvs
+
+        for (ri = rays.begin(); ri != ri_end; ++ ri)
+        {
+                Intersectable *oObject = (*ri).mRay->mOriginObject;
+
+                if (oObject)
+                {
+                        if (mPvsCountMethod == PER_OBJECT)
+                        {
+                                if (!oObject->Mailed())
+                                {
+                                        oObject->Mail();
+                                        oObject->mCounter = 1;
+                                        ++ pvsSize;
+                                }
+                                else
+                                {
+                                        ++ oObject->mCounter;
+                                }
+                        }
+                        else
+                        {
+                                pvsSize += PrepareHeuristics(oObject);  
+                        }       
+                }
+
+                Intersectable *tObject = (*ri).mRay->mTerminationObject;
+
+                if (tObject)
+                {
+                        if (mPvsCountMethod == PER_OBJECT)
+                        {
+                                if (!tObject->Mailed())
+                                {
+                                        tObject->Mail();
+                                        tObject->mCounter = 1;
+                                        ++ pvsSize;
+                                }
+                                else
+                                {
+                                        ++ tObject->mCounter;
+                                }
+                        }
+                        else
+                        {
+                                pvsSize += PrepareHeuristics(tObject);  
+                        }       
+                }
+        }
+
+        return pvsSize;
 }
 
@@ -910 +994 @@
 float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
                                                                            const AxisAlignedBox3 &box,
-                                                                           const int pvsSize,
+                                                                           int pvsSize,
                                                                            const int axis,
                                                                            float &position)
@@ -942 +1026 @@
         
         // the relative cost ratio
-        float ratio = /*Limits::Infinity;*/99999999.0f;
+        float ratio = 99999999.0f;
         bool splitPlaneFound = false;
 
@@ -1061 +1145 @@
         const float pFront = maxBox - position;
 
-        /*const float pOverall = box.GetVolume();
-
-        AxisAlignedBox3 bbox;
-        AxisAlignedBox3 fbox;
-
-        box.Split(axis, position, bbox, fbox);
-
-        const float pBack = fbox.GetVolume();
-        const float pFront = bbox.GetVolume();*/
-
+        
         const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
     const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
@@ -1090 +1165 @@
 
 
-void VspTree::EvalPvsIncr(ObjectMap &multipleObjects,
-                                                  KdLeaf *leaf, 
-                                                  const SortableEntry &ci,
+void VspTree::RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const
+{
+        // leaf falls out of right pvs
+        if (-- leaf->mCounter == 0)
+        {
+                pvs -= ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
+        }
+
+        //-- handle objects which are in several kd leaves separately 
+        ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+
+        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+        {
+                Intersectable *object = *oit;
+
+                if (-- object->mCounter == 0)
+                {
+                        -- pvs;
+                }
+        }
+}
+
+
+void VspTree::AddContriToPvs(KdLeaf *leaf, int &pvs) const
+{
+        if (!leaf->Mailed())
+        {
+                leaf->Mail();
+
+                // add objects without objects which are part of several kd leaves
+                pvs += ((int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size());
+
+                //-- handle objects of several kd leaves separately
+                ObjectContainer::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
+
+                for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
+                {
+                        Intersectable *object = *oit;
+
+                        // object not previously in left pvs
+                        if (!object->Mailed())
+                        {
+                                object->Mail();
+                                ++ pvs;
+                        }
+                }
+        }                                       
+}
+
+
+void VspTree::EvalPvsIncr(const SortableEntry &ci,
                                                   int &pvsLeft,
                                                   int &pvsRight) const
 {
-        int pvsSize = 0;
-
-        if (ci.type == SortableEntry::ERayMin)
-        {
-                if (!leaf->Mailed())
-                {
-                        leaf->Mail();
-                        pvsLeft += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
-
-                        // add duplicates
-                        ObjectMap::const_iterator oit, oit_end = leaf->mMultipleObjects.end();
-
-                        for (oit = leaf->mMultipleObjects.begin(); oit != oit_end; ++ oit)
-                        {
-                                const int id = (*oit).first;
-                                Intersectable *object = (*oit).second;
-
-                                if (multipleObjects[id] != object) // object not previously in pvs
+        VssRay *ray = ci.ray;
+
+        Intersectable *oObject = ray->mOriginObject;
+        Intersectable *tObject = ray->mTerminationObject;
+
+        if (oObject)
+        {       
+                if (mPvsCountMethod == PER_OBJECT)
+                {
+                        if (ci.type == SortableEntry::ERayMin)
+                        {
+                                if (!oObject->Mailed())
                                 {
-                                        multipleObjects[id] = object;
+                                        oObject->Mail();
                                         ++ pvsLeft;
                                 }
-
-                        }
-                }                                       
-        }
-        else if (ci.type == SortableEntry::ERayMax)
-        {
-                if (-- leaf->mCounter == 0)
-                        pvsRight += (int)leaf->mObjects.size() - (int)leaf->mMultipleObjects.size();
-        }
-}
-
-
-float VspTree::EvalKdCostHeuristics(const RayInfoContainer &rays,
-                                                                        const AxisAlignedBox3 &box,
-                                                                        const int pvsSize,
-                                                                        const int axis,
-                                                                        float &position)
+                        }
+                        else if (ci.type == SortableEntry::ERayMax)
+                        {
+                                if (-- oObject->mCounter == 0)
+                                        -- pvsRight;
+                        }
+                }
+                else // per kd node
+                {
+                        set<KdLeaf *>::const_iterator kit, kit_end = oObject->mKdLeaves.end();
+
+                        for (kit = oObject->mKdLeaves.begin(); kit != kit_end; ++ kit)
+                        {
+                                KdLeaf *node = dynamic_cast<KdLeaf *>(*kit);
+
+                                // add contributions of the kd nodes
+                                if (ci.type == SortableEntry::ERayMin)
+                                {
+                                        AddContriToPvs(node, pvsLeft);
+                                }
+                                else if (ci.type == SortableEntry::ERayMax)
+                                {
+                                        RemoveContriFromPvs(node, pvsRight);
+                                }
+                        }
+                }
+                        
+
+        }
+        
+        if (tObject)
+        {       
+                if (mPvsCountMethod == PER_OBJECT)
+                {
+                        if (ci.type == SortableEntry::ERayMin)
+                        {
+                                if (!tObject->Mailed())
+                                {
+                                        tObject->Mail();
+                                        ++ pvsLeft;
+                                }
+                        }
+                        else if (ci.type == SortableEntry::ERayMax)
+                        {
+                                if (-- tObject->mCounter == 0)
+                                        -- pvsRight;
+                        }
+                }
+                else // per kd node
+                {
+                        set<KdLeaf *>::const_iterator kit, kit_end = tObject->mKdLeaves.end();
+
+                        for (kit = tObject->mKdLeaves.begin(); kit != kit_end; ++ kit)
+                        {
+                                KdLeaf *node = dynamic_cast<KdLeaf *>(*kit);
+
+                                if (ci.type == SortableEntry::ERayMin)
+                                {
+                                        AddContriToPvs(node, pvsLeft);
+                                }
+                                else if (ci.type == SortableEntry::ERayMax)
+                                {
+                                        RemoveContriFromPvs(node, pvsRight);
+                                }
+                        }
+                }
+        }
+}
+
+
+/*
+float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
+                                                                           const AxisAlignedBox3 &box,
+                                                                           int pvsSize,
+                                                                           const int axis,
+                                                                           float &position)
 {
         const float minBox = box.Min(axis);
@@ -1145 +1321 @@
 
         SortSplitCandidates(rays, axis, minBand, maxBand);
+
+        // prepare the heuristics sweep 
+        // (note: returns pvs size, so there would be no need 
+        // to give pvs size as argument)
+        pvsSize = PrepareHeuristics(rays);
+
+        Debug << "here45 pvs: " << pvsSize << endl;
 
         // go through the lists, count the number of objects left and right
@@ -1164 +1347 @@
         
         // the relative cost ratio
-        float ratio = /*Limits::Infinity;*/99999999.0f;
+        float ratio = 99999999.0f;
         bool splitPlaneFound = false;
 
         Intersectable::NewMail();
-        KdNode::NewMail();
-
-        RayInfoContainer::const_iterator ri, ri_end = rays.end();
-
-        //-- set all kd nodes as belonging to the front pvs
-
-        for (ri = rays.begin(); ri != ri_end; ++ ri)
-        {
-                Intersectable *oObject = (*ri).mRay->mOriginObject;
-
-                if (oObject)
-                {
-                        KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
-                
-                        for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
-                        {
-                                KdNode *node = (*kit).first;
-
-                                if (!node->Mailed())
-                                {
-                                        node->Mail();
-                                        //node->mCounter = 1;
-                                }
-                                else
-                                {
-                                        //++ node->mCounter;
-                                }
-                        }       
-                }
-
-                Intersectable *tObject = (*ri).mRay->mTerminationObject;
-
-                if (tObject)
-                {
-                        KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
-                
-                        for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
-                        {
-                                KdNode *node = (*kit).first;
-
-                                if (!node->Mailed())
-                                {
-                                        node->Mail();
-                                        //node->mCounter = 1;
-                                }
-                                else
-                                {
-                                        //++ node->mCounter;
-                                }
-                        }       
-                }
-        }
-
-        Intersectable::NewMail();
+        KdLeaf::NewMail();
+
 
         vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
 
-        ObjectMap multipleObjectsLeft, multipleObjectsRight;
-
-
-        // -- traverse through visibility events
+Debug << "****************" << endl;
+        //-- traverse through visibility events
 
         for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
         {
-                VssRay *ray;
-                ray = (*ci).ray;
-                
-                Intersectable *oObject = ray->mOriginObject;
-                
-                KdPvsMap::const_iterator kit, kit_end = oObject->mKdPvs.mEntries.end();
-
-                if (oObject)
-                {       
-                        for (kit = oObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
-                        {
-                KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first);
-
-                                EvalPvsIncr(multipleObjectsLeft, node, *ci, pvsl, pvsr);
-                        }
-                }
-
-                Intersectable *tObject = ray->mOriginObject;
-
-                if (tObject)
-                {       
-                        for (kit = tObject->mKdPvs.mEntries.begin(); kit != kit_end; ++ kit)
-                        {
-                                KdLeaf *node = dynamic_cast<KdLeaf *>((*kit).first);
-
-                                EvalPvsIncr(multipleObjectsRight, node, *ci, pvsl, pvsr);
-                        }
-                }
-
+                EvalPvsIncr(*ci, pvsl, pvsr);
 
                 // Note: sufficient to compare size of bounding boxes of front and back side?
@@ -1267 +1368 @@
                         sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
 
-                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
-                        //Debug << "cost= " << sum << endl;
+                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << "\t cost= " << sum << endl;
 
                         if (sum < minSum)
@@ -1304 +1404 @@
                 ratio = newRenderCost / oldRenderCost;
         }
+        
         //if (axis != 1)
-        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
-         //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
+        Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
+              <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
 
         return ratio;
-}
-
-
-#if TODO
-
-float VspTree::EvalLocalCostHeuristicsNonIncremential(const RayInfoContainer &rays,
-                                                                                                          const AxisAlignedBox3 &box,
-                                                                                                          const int pvsSize,
-                                                                                                          const int axis,
-                                                                                                          float &position)
-{
-        const float minBox = box.Min(axis);
-        const float maxBox = box.Max(axis);
-
-        const float sizeBox = maxBox - minBox;
-
-        const float minBand = minBox + mMinBand * sizeBox;
-        const float maxBand = minBox + mMaxBand * sizeBox;
-
-        SortSplitCandidates(rays, axis, minBand, maxBand);
-
-        // go through the lists, count the number of objects left and right
-        // and evaluate the following cost funcion:
-        // C = ct_div_ci  + (ql*rl + qr*rr)/queries
-
-        int pvsl = 0;
-        int pvsr = pvsSize;
-
-        int pvsBack = pvsl;
-        int pvsFront = pvsr;
-
-        float sum = (float)pvsSize * sizeBox;
-        float minSum = 1e20f;
-
-        
-        // if no good split can be found, take mid split
-        position = minBox + 0.5f * sizeBox;
-        
-        // the relative cost ratio
-        float ratio = /*Limits::Infinity;*/99999999.0f;
-        bool splitPlaneFound = false;
-
-        Intersectable::NewMail();
-
-        RayInfoContainer::const_iterator ri, ri_end = rays.end();
-
-        //-- set all object as belonging to the front pvs
-
-        for(ri = rays.begin(); ri != ri_end; ++ ri)
-        {
-                // Note: sufficient to compare size of bounding boxes of front and back side?
-                if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
-                {
-                        sum = pvsl * ((*ci).value - minBox) + pvsr * (maxBox - (*ci).value);
-
-                        //Debug  << "pos=" << (*ci).value << "\t pvs=(" <<  pvsl << "," << pvsr << ")" << endl;
-                        //Debug << "cost= " << sum << endl;
-
-                        if (sum < minSum)
-                        {
-                                splitPlaneFound = true;
-
-                                minSum = sum;
-                                position = (*ci).value;
-                                
-                                pvsBack = pvsl;
-                                pvsFront = pvsr;
-                        }
-                }
-        }
-
-        
-        // -- compute cost
-
-        const int lowerPvsLimit = mViewCellsManager->GetMinPvsSize();
-        const int upperPvsLimit = mViewCellsManager->GetMaxPvsSize();
-
-        const float pOverall = sizeBox;
-        const float pBack = position - minBox;
-        const float pFront = maxBox - position;
-
-        
-        const float penaltyOld = EvalPvsPenalty(pvsSize, lowerPvsLimit, upperPvsLimit);
-    const float penaltyFront = EvalPvsPenalty(pvsFront, lowerPvsLimit, upperPvsLimit);
-        const float penaltyBack = EvalPvsPenalty(pvsBack, lowerPvsLimit, upperPvsLimit);
-        
-        const float oldRenderCost = penaltyOld * pOverall + Limits::Small;
-        const float newRenderCost = penaltyFront * pFront + penaltyBack * pBack;
-
-        if (splitPlaneFound)
-        {
-                ratio = newRenderCost / oldRenderCost;
-        }
-        //if (axis != 1)
-        //Debug << "axis=" << axis << " costRatio=" << ratio << " pos=" << position << " t=" << (position - minBox) / (maxBox - minBox)
-         //    <<"\t pb=(" << pvsBack << ")\t pf=(" << pvsFront << ")" << endl;
-
-        return ratio;
-}
-#endif
+}*/
 
 
@@ -1427 +1429 @@
         int bestAxis = -1;
 
-        //mOnlyDrivingAxis = true;
-
         // if we use some kind of specialised fixed axis
     const bool useSpecialAxis = 
                 mOnlyDrivingAxis || mCirculatingAxis;
-        Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
+        //Debug << "data: " << tData.mBoundingBox << " pvs " << tData.mPvs << endl;
         if (mCirculatingAxis)
         {
@@ -1481 +1481 @@
                         else if (nCostRatio[axis] < nCostRatio[bestAxis])
                         {
-                                Debug << "old: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
                                 bestAxis = axis;
-                                
-                                Debug << "new: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
                         } 
                 }
@@ -1499 +1496 @@
         pBack = nProbBack[bestAxis];
 
-
-        Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
+        //Debug << "val: " << nCostRatio[bestAxis] << " axis: " << bestAxis << endl;
         return nCostRatio[bestAxis];
 }
@@ -1779 +1775 @@
         ++ mCreatedViewCells;
 
-//#ifdef _DEBUG
+#ifdef _DEBUG
         Debug << "BSP stats: "
                   << "Depth: " << data.mDepth << " (max: " << mTermMaxDepth << "), "
@@ -1786 +1782 @@
                   << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "), "
                   << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
-//#endif
+#endif
 }
 
@@ -3035 +3031 @@
 {
         SplitCandidate *splitCandidate = mTQueue.top();
-        Debug << "priority: " << splitCandidate->GetPriority() << endl;
+        //Debug << "priority: " << splitCandidate->GetPriority() << endl;
         mTQueue.pop();
 
@@ -3089 +3085 @@
                                                                         0,
                                                                         &rays,
-                                                                        (int)objects.size(),
-                                                                        //mVspTree.ComputePvsSize(rays),
+                                                                        //(int)objects.size(),
+                                                                        mVspTree.ComputePvsSize(rays),
                                                                         prop,
                                                                         mVspTree.mBoundingBox);
@@ -3132 +3128 @@
         cout << "Constructing view space / object space tree ... \n";
         const long startTime = GetTime();       
-
+        
+        int i = 0;
         while (!FinishedConstruction())
         {
@@ -3140 +3137 @@
                         GlobalTerminationCriteriaMet(splitCandidate);
 
-                Debug << "cost: " << splitCandidate->GetPriority();
+                cout << "view cells: " << i ++ << endl;
 
                 // cost ratio of cost decrease / totalCost
@@ -3168 +3165 @@
         }
 
-        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << "secs" << endl;
+        cout << "finished in " << TimeDiff(startTime, GetTime())*1e-3 << " secs" << endl;
 
         mVspTree.mVspStats.Stop();

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

@@ -883 +883 @@
 
         /** Prepares objects for SAH.
-        */
-        void PrepareHeuristics(const RayInfoContainer &rays);
+                @returns pvs size of the ray container
+        */
+        int PrepareHeuristics(const RayInfoContainer &rays);
+
+        int PrepareHeuristics(Intersectable *object);
 
         /** Computes pvs increase with respect to the previous pvs for SAH.
@@ -898 +901 @@
         float EvalLocalCostHeuristics(const RayInfoContainer &rays,
                                                                   const AxisAlignedBox3 &box,
-                                                                  const int pvsSize,
+                                                                  int pvsSize,
                                                                   const int axis,
                                                                   float &position);
 
-        float EvalKdCostHeuristics(const RayInfoContainer &rays,
-                                                           const AxisAlignedBox3 &box,
-                                                           const int pvsSize,
-                                                           const int axis,
-                                                           float &position);
-         void EvalPvsIncr(ObjectMap &multipleObjects,
-                                          KdLeaf *leaf, 
-                                          const SortableEntry &ci,
+        /** Evaluates the influence on the pvs of the visibility event ve.
+                @param ve the visibility event
+                @param pvsLeft updates the left pvs
+                @param rightPvs updates the right pvs
+        */
+        void EvalPvsIncr(const SortableEntry &ve,
                                           int &pvsLeft,
                                           int &pvsRight) const;
 
+        void RemoveContriFromPvs(KdLeaf *leaf, int &pvs) const;
+        void AddContriToPvs(KdLeaf *leaf, int &pvs) const;
 
         /** Subdivides the rays into front and back rays according to the split plane.
@@ -989 +992 @@
 
 protected:
+
+        int mPvsCountMethod;
+        enum {PER_OBJECT, PER_KDLEAF};
 
         ViewCellsManager *mViewCellsManager;

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

@@ -314 +314 @@
   Exporter *exporter = NULL;
   exporter = Exporter::GetExporter(filename);
-  //    exporter->SetWireframe();
-  //    exporter->ExportKdTree(*mKdTree);
+  exporter->SetWireframe();
+  exporter->ExportKdTree(*mKdTree);
   exporter->SetFilled();
   exporter->ExportScene(mSceneGraph->mRoot);
@@ -623 +623 @@
   if (!mLoadViewCells)
   {
-           Debug << "here923 " << vbox << endl;
           mViewCellsManager->SetViewSpaceBox(vbox);
           // construct view cells using it's own set of samples
@@ -746 +745 @@
   vssTree->Construct(mVssRays, mViewSpaceBox);
   cout<<"VssTree root PVS size = "<<vssTree->GetRootPvsSize()<<endl;
+
+  ExportRays("kdtree.x3d", mVssRays, 10);
 
   if (0)