Changeset 1135

Timestamp:

07/17/06 09:59:26 (18 years ago)

Author:

mattausch

Message:

uaing rays for osp

Location:

GTP/trunk/Lib/Vis/Preprocessing

Files:

• scripts/Preprocessor.vcproj (modified) (1 diff)
• src/Intersectable.h (modified) (2 diffs)
• src/Preprocessor.cpp (modified) (4 diffs)
• src/ViewCell.cpp (modified) (1 diff)
• src/ViewCellsManager.cpp (modified) (2 diffs)
• src/VspOspTree.cpp (modified) (45 diffs)
• src/VspOspTree.h (modified) (18 diffs)

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

@@ -206 +206 @@
                         </File>
                         <File
+                                RelativePath="..\src\KdIntersectable.cpp">
+                        </File>
+                        <File
+                                RelativePath="..\src\KdIntersectable.h">
+                        </File>
+                        <File
                                 RelativePath="..\src\KdTree.cpp">
                         </File>

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

@@ -33 +33 @@
   //set<KdLeaf *> mKdLeaves;
 
-  enum { MESH_INSTANCE, TRANSFORMED_MESH_INSTANCE, SPHERE, VIEW_CELL, OGRE_MESH_INSTANCE };
+  /// # of object references
+  int mObjectRefs;
+
+  enum { MESH_INSTANCE, 
+                 TRANSFORMED_MESH_INSTANCE, 
+                 SPHERE, 
+                 VIEW_CELL, 
+                 OGRE_MESH_INSTANCE,
+                 KD_INTERSECTABLE
+                };
   
-  Intersectable():mMailbox(0) {}
+  Intersectable():mMailbox(0), mObjectRefs(0) {}
 
         void SetId(const int id) { mId = id; }
@@ -88 +97 @@
 };
 
+
 }
 

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

@@ -39 +39 @@
                 for (int j = 0; j < n; ++ j)
                 {
-                        const Vector3 scale2((float)j * 0.8 / n + 0.1,  0.05, (float)i * 0.8  / (float)n + 0.1);
+                        const Vector3 scale2((float)j * 0.8f / n + 0.1f,  0.05f, (float)i * 0.8f  / (float)n + 0.1f);
                 
                         const Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());
@@ -58 +58 @@
                 for (int j = 0; j < n; ++ j)
                 {
-                        const Vector3 scale2(0.15, (float)j * 0.8 / n + 0.1, (float)i * 0.8  / (float)n + 0.1);
+                        const Vector3 scale2(0.15f, (float)j * 0.8f / n + 0.1f, (float)i * 0.8f  / (float)n + 0.1f);
                 
                         Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());
                 
-                        Vector3 boxSize = sceneBox.Size() * Vector3(0.0025, 0.01, 0.0025);
+                        Vector3 boxSize = sceneBox.Size() * Vector3(0.0025f, 0.01f, 0.0025f);
                         AxisAlignedBox3 box(pt2, pt2 + boxSize);
                         Mesh *mesh = CreateMeshFromBox(box);
@@ -75 +75 @@
         for (int i = 0; i < n; ++ i)
         {
-                const Vector3 scale2(2, 0.2, (float)i * 0.8  / (float)n + 0.1);
+                const Vector3 scale2(2, 0.2f, (float)i * 0.8f  / (float)n + 0.1f);
                 
                 Vector3 pt2 = sceneBox.Min() + scale2 * (sceneBox.Max() - sceneBox.Min());
                 
                 //Vector3 boxSize = sceneBox.Size() * Vector3(0.0025, 0.01, 0.0025);
-                Vector3 boxSize = sceneBox.Size() * Vector3(0.005, 0.02, 0.005);
-
-                AxisAlignedBox3 box(pt2 + 0.1, pt2 + boxSize);
+                Vector3 boxSize = sceneBox.Size() * Vector3(0.005f, 0.02f, 0.005f);
+
+                AxisAlignedBox3 box(pt2 + 0.1f, pt2 + boxSize);
                 Mesh *mesh = CreateMeshFromBox(box);
 
@@ -97 +97 @@
         if (1)
         {
-                const Vector3 scale(1.0, 0.0, 0);
+                const Vector3 scale(1.0f, 0.0, 0);
 
                 Vector3 pt = sceneBox.Min() + scale * (sceneBox.Max() - sceneBox.Min());

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

@@ -265 +265 @@
 {
         const bool result = mKdPvs.AddSample(sample, pdf, contribution);
-
         return result;
 }

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

@@ -5490 +5490 @@
                                         obj->Mail();
                                 }                                       
-
+        // TODO matt§§
+#if TODO
                                 // collect kd leaves
                                 //KdLeaf =
@@ -5505 +5506 @@
                                         }
                                 }
+#endif
                         }
 

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

@@ -47 +47 @@
 
 
-
 void VspTreeStatistics::Print(ostream &app) const
 {
@@ -443 +442 @@
 
 
-void VspTree::PrepareConstruction(const VssRayContainer &sampleRays,
-                                                                  AxisAlignedBox3 *forcedBoundingBox) 
-{
-        // store pointer to this tree
-        VspSplitCandidate::sVspTree = this;
-
-        mVspStats.nodes = 1;
-        
+void VspTree::ComputeBoundingBox(const RayInfoContainer &rays,
+                                                                 AxisAlignedBox3 *forcedBoundingBox) 
+{       
         if (forcedBoundingBox)
         {
@@ -459 +453 @@
                 mBoundingBox.Initialize();
 
-                VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+                RayInfoContainer::const_iterator rit, rit_end = rays.end();
 
                 //-- compute bounding box
-        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
-                {
-                        VssRay *ray = *rit;
+        for (rit = rays.begin(); rit != rit_end; ++ rit)
+                {
+                        VssRay *ray = (*rit).mRay;
 
                         // compute bounding box of view space
@@ -471 +465 @@
                 }
         }
-
-        mTermMinProbability *= mBoundingBox.GetVolume();
-        mGlobalCostMisses = 0;
 }
 
@@ -697 +688 @@
 
         frontData.mDepth = tData.mDepth + 1;
+        backData.mDepth = tData.mDepth + 1;
+
         frontData.mRays = new RayInfoContainer();
-        
-        backData.mDepth = tData.mDepth + 1;
         backData.mRays = new RayInfoContainer();
-        
+
         //-- subdivide rays
         SplitRays(splitPlane,
@@ -707 +698 @@
                           *frontData.mRays,
                           *backData.mRays);
-
         
         //Debug << "f: " << frontData.mRays->size() << " b: " << backData.mRays->size() << "d: " << tData.mRays->size() << endl;
@@ -889 +879 @@
 
                         // potentially visible kd cells
-                        const bool termination = true;
-                        vc->AddKdPvsSample(GetKdLeaf(ray, termination));
+                        KdLeaf *leaf = 
+                                mOspTree->GetLeaf(ray->mTermination, ray->mTerminationNode);
+                        float kdcontri;
+                        vc->AddKdPvsSample(leaf, 1, kdcontri);
                 }
 
@@ -903 +895 @@
 
                         sc += contribution;
-
+        
                         // potentially visible kd cells
-                        const bool termination = false;
-                        vc->AddKdPvsSample(GetKdLeaf(ray, termination));
-                }
-
+                        const bool origin = true;
+                        KdLeaf *leaf =
+                                mOspTree->GetLeaf(ray->mOrigin, ray->mOriginNode);
+                        float kdcontri;
+                        vc->AddKdPvsSample(leaf, 1, kdcontri);
+                }
 
                 if (madeContrib)
@@ -987 +981 @@
 
 int VspTree::PrepareHeuristics(Intersectable *object)
-{
+{       
+        int pvsSize = 0;
+        // TODO matt§§
+#if TODO
         set<KdLeaf *>::const_iterator kit, kit_end = object->mKdLeaves.end();
-        
-        int pvsSize = 0;
 
         for (kit = object->mKdLeaves.begin(); kit != kit_end; ++ kit)
@@ -1029 +1024 @@
                 }
         }
-
+#endif
         return pvsSize;
 }
@@ -1177 +1172 @@
                 else // per kd node
                 {
+        // TODO matt§§
+#if TODO
                         set<KdLeaf *>::const_iterator kit, kit_end = oObject->mKdLeaves.end();
 
@@ -1193 +1190 @@
                                 }
                         }
+#endif
                 }
                         
@@ -1218 +1216 @@
                 else // per kd node
                 {
+                        // TODO matt§§
+#if TODO
                         set<KdLeaf *>::const_iterator kit, kit_end = tObject->mKdLeaves.end();
                         
@@ -1233 +1233 @@
                                 }
                         }
-                }
-        }
-}
-
-
-float VspTree::EvalLocalCostHeuristics(const RayInfoContainer &rays,
+#endif
+                }
+        }
+}
+
+
+float VspTree::EvalLocalCostHeuristics(const VspTraversalData &tData,
                                                                            const AxisAlignedBox3 &box,
-                                                                           int pvsSize,
                                                                            const int axis,
                                                                            float &position)
 {
+        RayInfoContainer *rays = tData.mRays;
+        int pvsSize = tData.mPvs;
+
         const float minBox = box.Min(axis);
         const float maxBox = box.Max(axis);
@@ -1252 +1255 @@
         const float maxBand = minBox + mMaxBand * sizeBox;
 
-        SortSplitCandidates(rays, axis, minBand, maxBand);
+        SortSplitCandidates(*rays, axis, minBand, maxBand);
 
         // prepare the sweep
         // (note: returns pvs size, so there would be no need 
         // to give pvs size as argument)
-        pvsSize = PrepareHeuristics(rays);
+        pvsSize = PrepareHeuristics(*rays);
 
         // go through the lists, count the number of objects left and right
@@ -1385 +1388 @@
                                 //-- place split plane using heuristics
                                 nCostRatio[axis] =
-                                        EvalLocalCostHeuristics(*tData.mRays,
+                                        EvalLocalCostHeuristics(tData,
                                                                                         box,
-                                                                                        tData.mPvs,
                                                                                         axis,
                                                                                         nPosition[axis]);                       
@@ -2453 +2455 @@
                 const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
                         
-
-#if 1
                 if (side == 0)
                 {
@@ -2478 +2478 @@
                         backRays.push_back(bRay);
                 }
-#else
-                if (side == 0)
-                {
-                        ++ splits;
-
-                        if (ray->HasPosDir(plane.mAxis))
-                        {
-                                backRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
-                                frontRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
-                        }
-                        else
-                        {
-                                frontRays.push_back(RayInfo(ray, bRay.GetMaxT(), t));
-                                backRays.push_back(RayInfo(ray, t, bRay.GetMinT()));
-                        }
-                }
-                else if (side == 1)
-                {
-                        backRays.push_back(bRay);
-                }
-                else
-                {
-                        frontRays.push_back(bRay);
-                        
-                }
-#endif
         }
 
@@ -2582 +2556 @@
 
 
-
-
 void VspTree::CollectDirtyCandidates(VspSplitCandidate *sc, 
                                                                          vector<SplitCandidate *> &dirtyList)
@@ -2598 +2570 @@
         {
                 Intersectable *obj = (*oit).first;
-
+        // TODO matt§§
+#if TODO
                 set<KdLeaf *>::const_iterator kit, kit_end = obj->mKdLeaves.end();
-
+        
                 for (kit = obj->mKdLeaves.begin(); kit != kit_end; ++ kit)
                 {
@@ -2611 +2584 @@
                         }
                 }
-        }
+#endif
+        }
+}
+
+
+void VspTree::ProcessRays(const VssRayContainer &sampleRays,
+                                                  RayInfoContainer &rays)
+{
+        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+        long startTime = GetTime();
+
+        cout << "storing rays ... ";
+
+        Intersectable::NewMail();
+
+        //-- store rays and objects
+        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+        {
+                VssRay *ray = *rit;
+                float minT, maxT;
+                static Ray hray;
+
+                hray.Init(*ray);
+                
+                // TODO: not very efficient to implictly cast between rays types
+                if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
+                {
+                        float len = ray->Length();
+
+                        if (!len)
+                                len = Limits::Small;
+
+                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
+                }
+        }
+
+        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
 }
 
@@ -2707 +2717 @@
     for (oit = objects.begin(); oit != oit_end; ++ oit) 
         {
+                Intersectable *object = *oit;
+
                 // determine the side of this ray with respect to the plane
-                const AxisAlignedBox3 box = (*oit)->GetBox();
+                const AxisAlignedBox3 box = object->GetBox();
 
                 if (box.Max(splitPlane.mAxis) >= splitPlane.mPosition)
-            front.push_back(*oit);
-    
+                {
+            front.push_back(object);
+                        ++ object->mObjectRefs;
+                }
+
                 if (box.Min(splitPlane.mAxis) < splitPlane.mPosition)
-                        back.push_back(*oit);
+                {
+                        back.push_back(object);
+                        ++ object->mObjectRefs;
+                }
+
+                // remove parent reference
+                -- object->mObjectRefs;
         }
 
@@ -2755 +2776 @@
         // TODO matt: compute pvs
         frontData.mPvs = 999; // ComputePvsSize(*frontData.mRays);
-        backData.mPvs = -999; //ComputePvsSize(*backData.mRays);
+        backData.mPvs = 999; //ComputePvsSize(*backData.mRays);
 
         frontData.mProbability = frontData.mBoundingBox.GetVolume();
 
-
-        // classify objects
+        
+        //-- subdivide rays
+        frontData.mRays = new RayInfoContainer();
+        backData.mRays = new RayInfoContainer();
+
+        SplitRays(splitPlane,
+                          *tData.mRays,
+                          *frontData.mRays,
+                          *backData.mRays);
+
+
+        //-- classify objects
         int objectsBack = 0;
         int objectsFront = 0;
@@ -2951 +2982 @@
 
 
-float OspTree::EvalLocalCostHeuristics(KdLeaf *node,
+float OspTree::EvalLocalCostHeuristics(const OspTraversalData &tData,
                                                                            const AxisAlignedBox3 &box,
                                                                            const int axis,
@@ -2958 +2989 @@
                                                                            int &objectsBack)
 {
-        // sort so we can use a sweep
-        SortSplitCandidates(node, 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
         
-        float totalVol = PrepareHeuristics(node->mObjects);
+        const float minBox = box.Min(axis);
+        const float maxBox = box.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
+        SortSplitCandidates(tData, axis, minBand, maxBand);
+
+        float totalVol = PrepareHeuristics(tData.mNode->mObjects);
         float voll = 0;
         float volr = totalVol;
   
-        const int totalPvs = (int)node->mObjects.size();
-
-        const float minBox = box.Min(axis);
-        const float maxBox = box.Max(axis);
-
-        const float sizeBox = maxBox - minBox;
+        const int totalPvs = tData.mNode->mObjects.size();
+
                                 
         // if no good split can be found, take mid split
@@ -2982 +3017 @@
         float ratio = 99999999.0f;
         bool splitPlaneFound = false;
-  
-        float minBand = minBox + mSplitBorder * (maxBox - minBox);
-        float maxBand = minBox + (1.0f - mSplitBorder) * (maxBox - minBox);
-
+   
     float minSum = 1e20f;
 
@@ -2993 +3025 @@
         float sum = (float)totalVol * sizeBox;
 
+        int currentPvs = 0;
+
+        Intersectable::NewMail();
+
+        //-- traverse through visibility events
+
         vector<SortableEntry>::const_iterator ci, ci_end = mSplitCandidates->end();
 
-
-        //-- traverse through visibility events
-        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci)
-        {
+        for (ci = mSplitCandidates->begin(); ci != ci_end; ++ ci, ++ currentPvs)
+        {
+                Intersectable *object = (*ci).mObject;
+
+                // new object in this node -> add to the pvs
+                if (!object->Mailed())
+                {
+                        object->Mail();
+                        ++ currentPvs;
+                }
+
                 EvalViewCellVolumeIncr(*ci, voll, volr);
 
@@ -3005 +3050 @@
 
                 // Note: sufficient to compare size of bounding boxes of front and back side?
-                if (((*ci).value >= minBand) && ((*ci).value <= maxBand))
+                if (((*ci).mPos >= minBand) && ((*ci).mPos <= maxBand))
                 {
                         //sum = costl * ((*ci).value - minBox) + costr * (maxBox - (*ci).value);
-                        sum = voll * (*ci).value +volr * (totalPvs - (*ci).value);
-
-                        cout << "pos=" << (*ci).value << "\t volt=(" <<  voll << "," 
+                        sum = voll * currentPvs + volr * (totalPvs - currentPvs);
+
+                        cout << "pos=" << currentPvs << "\t volt=(" <<  voll << "," 
                                  << volr << ")" << "\t volt= " << sum << endl;
 
@@ -3018 +3063 @@
 
                                 minSum = sum;
-                                pvsBack = (*ci).value;
+                                pvsBack = currentPvs;
                                 
                                 volBack = voll;
@@ -3057 +3102 @@
 
 
-void OspTree::SortSplitCandidates(KdLeaf *node, const int axis)
+void OspTree::SortSplitCandidates(const OspTraversalData &tData,
+                                                                  const int axis, 
+                                                                  float minBand, 
+                                                                  float maxBand)
+
 {
         mSplitCandidates->clear();
 
-        int requestedSize = 2 * (int)node->mObjects.size();
-        
+        RayInfoContainer *rays = tData.mRays;
+        KdLeaf *leaf = tData.mNode;
+
+        int requestedSize = 2 * (int)rays->size();
+
         // creates a sorted split candidates array
         if (mSplitCandidates->capacity() > 500000 &&
-                requestedSize < (int)(mSplitCandidates->capacity()/10)) 
-        {
-                delete mSplitCandidates;
-                mSplitCandidates = new vector<SortableEntry>;
+                requestedSize < (int)(mSplitCandidates->capacity() / 10) )
+        {
+        delete mSplitCandidates;
+                mSplitCandidates = new vector<SortableEntry>;
         }
 
         mSplitCandidates->reserve(requestedSize);
-        
-        ObjectContainer::const_iterator mi, mi_end = node->mObjects.end();
-
-        // insert all queries 
-        int pvs = 0;
-        for(mi = node->mObjects.begin(); mi != mi_end; ++ mi, ++ pvs) 
-        {
-                AxisAlignedBox3 box = (*mi)->GetBox();
-
-                // only first event should be sufficient
-                // but maybe introduces problems with symmetry ...
-                mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MIN,
-                                        pvs, *mi));
-
-                //mSplitCandidates->push_back(SortableEntry(SortableEntry::BOX_MAX,
-                //                      pvs, *mi));
+
+        float pos;
+
+        //-- insert all queries
+        for (RayInfoContainer::const_iterator ri = rays->begin(); ri < rays->end(); ++ ri)
+        {
+                const bool positive = (*ri).mRay->HasPosDir(axis);
+                                
+                pos = (*ri).ExtrapOrigin(axis);
+        
+
+                //if (mOspTree->GetLeaf() == leaf)
+
+        /*      mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
+                                                                        pos, (*ri).mRay));
+
+                pos = (*ri).ExtrapTermination(axis);
+
+                mSplitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin, 
+                                                                        pos, (*ri).mRay));*/
         }
 
@@ -3144 +3200 @@
         Intersectable *obj = ci.mObject;
 
-        switch (ci.type) 
+        switch (ci.mType) 
         {
                 case SortableEntry::BOX_MIN:
@@ -3356 +3412 @@
 
 
-void OspTree::PrepareConstruction(const ObjectContainer &objects,
-                                                                  AxisAlignedBox3 *forcedBoundingBox) 
-{
-        // store pointer to this tree
-        OspSplitCandidate::sOspTree = this;
-
-        mOspStats.nodes = 1;
-        
+void OspTree::ComputeBoundingBox(const ObjectContainer &objects,
+                                                                 AxisAlignedBox3 *forcedBoundingBox) 
+{
         if (forcedBoundingBox)
         {
@@ -3384 +3435 @@
                 }
         }
-
-        mTermMinProbability *= mBoundingBox.GetVolume();
-        mGlobalCostMisses = 0;
-}
+}
+
 
 #if DEPRECATED
@@ -3583 +3632 @@
 
 
+KdNode *OspTree::GetRoot() const
+{
+        return mRoot;
+}
+
+
 KdLeaf *OspTree::GetLeaf(const Vector3 &pt, KdNode *node) const
 {
         if (node == NULL)
+        {
                 node = mRoot;
+        }
 
         stack<KdNode *> nodeStack;
@@ -3608 +3665 @@
                         // random decision
                         if (interior->mPosition < pt[interior->mAxis])
+                        {
                                 nodeStack.push(interior->mBack);
+                        }
                         else
+                        {
                                 nodeStack.push(interior->mFront);
+                        }
                 }
         }
@@ -3618 +3679 @@
 
 
-KdNode *OspTree::GetRoot() const
-{
-        return mRoot;
-}
+void OspTree::ProcessRays(const VssRayContainer &sampleRays,
+                                                  RayInfoContainer &rays)
+{
+        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
+
+        long startTime = GetTime();
+
+        cout << "storing rays ... ";
+
+        Intersectable::NewMail();
+
+        //-- store rays and objects
+        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
+        {
+                VssRay *ray = *rit;
+                float minT, maxT;
+                static Ray hray;
+
+                hray.Init(*ray);
+                
+                // TODO: not very efficient to implictly cast between rays types
+                if (GetBoundingBox().GetRaySegment(hray, minT, maxT))
+                {
+                        float len = ray->Length();
+
+                        if (!len)
+                                len = Limits::Small;
+
+                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
+                }
+        }
+
+        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
+}
+
+
+
+int OspTree::SplitRays(const AxisAlignedPlane &plane,
+                                           RayInfoContainer &rays,
+                                           RayInfoContainer &frontRays,
+                                           RayInfoContainer &backRays) const
+{
+        int splits = 0;
+
+        RayInfoContainer::const_iterator rit, rit_end = rays.end();
+
+        for (rit = rays.begin(); rit != rit_end; ++ rit)
+        {
+                RayInfo bRay = *rit;
+                
+                VssRay *ray = bRay.mRay;
+                float t;
+
+                // get classification and receive new t
+                //-- test if start point behind or in front of plane
+                const int side = bRay.ComputeRayIntersection(plane.mAxis, plane.mPosition, t);
+                        
+                if (side == 0)
+                {
+                        ++ splits;
+
+                        if (ray->HasPosDir(plane.mAxis))
+                        {
+                                backRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+                                frontRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                        }
+                        else
+                        {
+                                frontRays.push_back(RayInfo(ray, bRay.GetMinT(), t));
+                                backRays.push_back(RayInfo(ray, t, bRay.GetMaxT()));
+                        }
+                }
+                else if (side == 1)
+                {
+                        frontRays.push_back(bRay);
+                }
+                else
+                {
+                        backRays.push_back(bRay);
+                }
+        }
+
+        return splits;
+}
+
+
 
 
@@ -3650 +3793 @@
 
 
-void HierarchyManager::ProcessRays(const VssRayContainer &sampleRays,
-                                                                   RayInfoContainer &rays)
-{
-        VssRayContainer::const_iterator rit, rit_end = sampleRays.end();
-
-        long startTime = GetTime();
-
-        cout << "storing rays ... ";
-
-        Intersectable::NewMail();
-
-        //-- store rays and objects
-        for (rit = sampleRays.begin(); rit != rit_end; ++ rit)
-        {
-                VssRay *ray = *rit;
-                float minT, maxT;
-                static Ray hray;
-
-                hray.Init(*ray);
-                
-                // TODO: not very efficient to implictly cast between rays types
-                if (mVspTree.GetBoundingBox().GetRaySegment(hray, minT, maxT))
-                {
-                        float len = ray->Length();
-
-                        if (!len)
-                                len = Limits::Small;
-
-                        rays.push_back(RayInfo(ray, minT / len, maxT / len));
-                }
-        }
-
-        cout << "finished in " << TimeDiff(startTime, GetTime()) * 1e-3 << " secs" << endl;
-}
-
-
 SplitCandidate *HierarchyManager::PrepareVsp(const VssRayContainer &sampleRays,
                                                                                          AxisAlignedBox3 *forcedViewSpace,
-                                                                                         RayInfoContainer &rays
-                                                                                         )
-{
+                                                                                         RayInfoContainer &rays)
+{
+        // get clipped rays
+        mVspTree.ProcessRays(sampleRays, rays);
+
+        // store pointer to this tree
+        VspTree::VspSplitCandidate::sVspTree = &mVspTree;
+        mVspTree.mVspStats.nodes = 1;
+
         // prepare bounding box
-        mVspTree.PrepareConstruction(sampleRays, forcedViewSpace);
-
-        // get clipped rays
-        ProcessRays(sampleRays, rays);
+        mVspTree.ComputeBoundingBox(rays, forcedViewSpace);
+
+        mVspTree.mTermMinProbability *= mBoundingBox.GetVolume();
+        mVspTree.mGlobalCostMisses = 0;
+
 
         const int pvsSize = mVspTree.ComputePvsSize(rays);
@@ -3740 +3854 @@
 
 
-SplitCandidate * HierarchyManager::PrepareOsp(const ObjectContainer &objects,
-                                                                                          AxisAlignedBox3 *forcedViewSpace)
-{
-        mOspTree.PrepareConstruction(objects, forcedViewSpace);
+SplitCandidate * HierarchyManager::PrepareOsp(const VssRayContainer &sampleRays,
+                                                                                          const ObjectContainer &objects,
+                                                                                          AxisAlignedBox3 *forcedObjectSpace,
+                                                                                          RayInfoContainer &rays)
+{
+        // get clipped rays
+        mOspTree.ProcessRays(sampleRays, rays);
+
+        // store pointer to this tree
+        OspTree::OspSplitCandidate::sOspTree = &mOspTree;
+        mOspTree.mOspStats.nodes = 1;
+        
+        mOspTree.ComputeBoundingBox(objects, forcedObjectSpace);
+
+        mOspTree.mTermMinProbability *= mBoundingBox.GetVolume();
+        mGlobalCostMisses = 0;
+
 
         // add first candidate for view space partition
@@ -3759 +3886 @@
         OspTree::OspTraversalData oData(kdleaf,
                                                                         0,
+                                                                        &rays,
                                                                         pvsSize,
                                                                         prop,
@@ -3778 +3906 @@
                                                                                    const ObjectContainer &objects,
                                                                                    AxisAlignedBox3 *forcedViewSpace,
-                                                                                   RayInfoContainer &rays)
-{
-        mTQueue.Push(PrepareVsp(sampleRays, forcedViewSpace, rays));
-        mTQueue.Push(PrepareOsp(objects, forcedViewSpace));
+                                                                                   RayInfoContainer &viewSpaceRays,
+                                                                                   RayInfoContainer &objectSpaceRays)
+{
+        SplitCandidate *vsc = 
+                PrepareVsp(sampleRays, forcedViewSpace, viewSpaceRays);
+        mTQueue.Push(vsc);
+
+        SplitCandidate *osc = 
+                PrepareOsp(sampleRays, objects, forcedViewSpace, objectSpaceRays);
+
+        mTQueue.Push(osc);
 }
 
@@ -3796 +3931 @@
                                                                   AxisAlignedBox3 *forcedViewSpace)
 {
-        RayInfoContainer *rays = new RayInfoContainer();
+        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
+        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
 
         // makes no sense otherwise because only one kd cell available
@@ -3803 +3939 @@
         mVspTree.mPvsCountMethod = VspTree::PER_OBJECT;
 
-        mTQueue.Push(PrepareVsp(sampleRays, forcedViewSpace, *rays));
+        mTQueue.Push(PrepareVsp(sampleRays, forcedViewSpace, *viewSpaceRays));
 
         long startTime = GetTime();
@@ -3844 +3980 @@
 
         //-- object space partition
-    mTQueue.Push(PrepareOsp(objects, forcedViewSpace));
+        SplitCandidate *osc =
+                PrepareOsp(sampleRays, objects, forcedViewSpace, *objectSpaceRays);
+
+    mTQueue.Push(osc);
+
 
         i = 0;
@@ -3884 +4024 @@
                                                                  AxisAlignedBox3 *forcedViewSpace)
 {
-        RayInfoContainer *rays = new RayInfoContainer();
-        
+        RayInfoContainer *objectSpaceRays = new RayInfoContainer();
+        RayInfoContainer *viewSpaceRays = new RayInfoContainer();
+
         // prepare vsp and osp trees for traversal
-        PrepareConstruction(sampleRays, objects, forcedViewSpace, *rays);
+        PrepareConstruction(sampleRays, objects, forcedViewSpace, *viewSpaceRays, *objectSpaceRays);
 
         mVspTree.mVspStats.Reset();
@@ -3930 +4071 @@
                 }
 
-                // reevaluate affected candidates
+                // reevaluate candidates affected by the split
+                // for view space splits, this would be object space splits
+                // and other way round
                 RepairQueue();
 

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

@@ -549 +549 @@
                 }
 
-                // deletes contents and sets them to NULL
+                /// deletes contents and sets them to NULL
                 void Clear()
                 {
@@ -748 +748 @@
         */
         void AddViewCellReferences(ViewCell *vc) const;
-
 
 
@@ -794 +793 @@
                                                          float &pBack) const;
 
-        void PrepareConstruction(const VssRayContainer &sampleRays,
-                                                         AxisAlignedBox3 *forcedBoundingBox);
+        void ComputeBoundingBox(const RayInfoContainer &rays,
+                AxisAlignedBox3 *forcedBoundingBox);
 
         /** Evaluates candidate for splitting.
@@ -901 +900 @@
         /** Computes best cost for axis aligned planes.
         */
-        float EvalLocalCostHeuristics(const RayInfoContainer &rays,
+        float EvalLocalCostHeuristics(const VspTraversalData &data,
                                                                   const AxisAlignedBox3 &box,
-                                                                  int pvsSize,
                                                                   const int axis,
                                                                   float &position);
@@ -1010 +1008 @@
         KdNode *GetKdNode(VssRay &ray, const bool termination) const;
 
+        void ProcessRays(const VssRayContainer &sampleRays,
+                RayInfoContainer &rays);
 
 protected:
 
         int mPvsCountMethod;
+
         enum {PER_OBJECT, PER_KDLEAF};
 
@@ -1030 +1031 @@
         /// box around the whole view domain
         AxisAlignedBox3 mBoundingBox;
+
 
 
@@ -1123 +1125 @@
                 int mDepth;
                 /// rays piercing this node
-                //RayInfoContainer *mRays;
+                RayInfoContainer *mRays;
                 /// the probability that this node contains view point
                 float mProbability;
@@ -1140 +1142 @@
                 OspTraversalData():
                 mNode(NULL),
+                mRays(NULL),
                 mDepth(0),
                 mPvs(0),
@@ -1149 +1152 @@
                 
                 OspTraversalData(KdLeaf *node, 
-                                                 const int depth, 
+                                                 const int depth,
+                         RayInfoContainer *rays,
                                                  const int pvs,
                                                  const float p,
                                                  const AxisAlignedBox3 &box):
                 mNode(node), 
-                mDepth(depth), 
+                mDepth(depth),
+                mRays(rays),
                 mPvs(pvs),
                 mProbability(p),
@@ -1164 +1169 @@
 
                 OspTraversalData(const int depth, 
-                                                 const AxisAlignedBox3 &box): 
+                        RayInfoContainer *rays,
+                        const AxisAlignedBox3 &box): 
                 mNode(NULL), 
-                mDepth(depth), 
+                mDepth(depth),
+                mRays(rays),
                 mPvs(0),
                 mProbability(0),
@@ -1182 +1189 @@
                 }
 
-                // deletes contents and sets them to NULL
+                /// deletes contents and sets them to NULL
                 void Clear()
                 {
+                        DEL_PTR(mRays);
                 }
+
 
                 friend bool operator<(const OspTraversalData &a, const OspTraversalData &b)
@@ -1342 +1351 @@
         int ComputePvsSize(const ObjectContainer &objects) const;
 
-
         KdLeaf *GetLeaf(const Vector3 &pt, KdNode *node) const;
 
@@ -1355 +1363 @@
         // For sorting objects
         // --------------------------------------------------------------
-        struct  SortableEntry
+        struct SortableEntry
         {
-                enum
+                enum EType 
                 {
-                        BOX_MIN,
-                        BOX_MAX
+                        ERayMin,
+                        ERayMax
                 };
 
-                int type;
-                float value;
+                int mType;
+                //int mPvs;
+                float mPos;
+
                 Intersectable *mObject;
 
                 SortableEntry() {}
 
-                SortableEntry(const int t, const float v, Intersectable *obj):
-                type(t), value(v), mObject(obj) 
+                SortableEntry(const int type, 
+                        //const float pvs, 
+                        const float pos,
+                        Intersectable *obj):
+                mType(type), 
+                //mPvs(pvs), 
+                mPos(pos), 
+                mObject(obj) 
                 {}
 
                 bool operator<(const SortableEntry &b) const 
                 {
-                        return value < b.value;
+                        return mPos < b.mPos;
                 }
         };
@@ -1467 +1483 @@
                 @param axis the current split axis
         */
-        void SortSplitCandidates(KdLeaf *node, const int axis);
+        void SortSplitCandidates(const OspTraversalData &data,
+                                                         const int axis, 
+                                                         float minBand, 
+                                                         float maxBand);
 
         /** Computes best cost for axis aligned planes.
         */
-        float EvalLocalCostHeuristics(KdLeaf *node,
+        float EvalLocalCostHeuristics(const OspTraversalData &data,
                 const AxisAlignedBox3 &box,
                 const int axis,
@@ -1570 +1589 @@
         /** Prepares construction for vsp and osp trees.
         */
-        void PrepareConstruction(const ObjectContainer &objects,
+        void ComputeBoundingBox(const ObjectContainer &objects,
                 AxisAlignedBox3 *forcedBoundingBox);
 
@@ -1580 +1599 @@
         void CollectViewCells(KdLeaf *leaf, 
                 ViewCellContainer &viewCells);
+
+        void ProcessRays(const VssRayContainer &sampleRays,
+                RayInfoContainer &rays);
 
 
@@ -1721 +1743 @@
 
         void PrepareConstruction(const VssRayContainer &sampleRays,
-                                                         const ObjectContainer &objects,
-                                                         AxisAlignedBox3 *forcedViewSpace,
-                                                         RayInfoContainer &rays);
+                const ObjectContainer &objects,
+                AxisAlignedBox3 *forcedViewSpace,
+                RayInfoContainer &viewSpaceRays,
+                RayInfoContainer &objectSpaceRays);
 
         bool FinishedConstruction();
@@ -1733 +1756 @@
         void CollectDirtyCandidates(vector<SplitCandidate *> &dirtyList);
 
-        SplitCandidate * PrepareVsp(const VssRayContainer &sampleRays,
-                AxisAlignedBox3 *forcedViewSpace,
-                RayInfoContainer &rays);
-
-        SplitCandidate * PrepareOsp(const ObjectContainer &objects, 
-                AxisAlignedBox3 *forcedViewSpace);
-
-        void ProcessRays(const VssRayContainer &sampleRays,
+        SplitCandidate *PrepareVsp(const VssRayContainer &sampleRays,
+                                                           AxisAlignedBox3 *forcedViewSpace,
+                                                           RayInfoContainer &rays);
+
+        SplitCandidate *PrepareOsp(const VssRayContainer &sampleRays,
+                const ObjectContainer &objects,
+                AxisAlignedBox3 *forcedObjectSpace,
                 RayInfoContainer &rays);