Changeset 410

Timestamp:

11/14/05 21:29:57 (19 years ago)

Author:

mattausch

Message:

 

Location:

trunk/VUT/GtpVisibilityPreprocessor

Files:

• scripts/Preprocessor.vcproj (modified) (1 diff)
• scripts/default.env (modified) (5 diffs)
• src/Preprocessor.cpp (modified) (1 diff)
• src/RenderSimulator.cpp (modified) (1 diff)
• src/SamplingPreprocessor.cpp (modified) (1 diff)
• src/ViewCellBsp.cpp (modified) (6 diffs)
• src/VspKdTree.cpp (modified) (24 diffs)
• src/VspKdTree.h (modified) (6 diffs)
• src/VssRay.h (modified) (2 diffs)
• src/default.env (modified) (1 diff)

trunk/VUT/GtpVisibilityPreprocessor/scripts/Preprocessor.vcproj

@@ -261 +261 @@
                         </File>
                         <File
+                                RelativePath="..\src\Statistics.h">
+                        </File>
+                        <File
                                 RelativePath="..\src\Triangle3.cpp">
                         </File>

trunk/VUT/GtpVisibilityPreprocessor/scripts/default.env

@@ -23 +23 @@
 }
 
+Preprocessor {
+#       type sampling
+        type vss
+}
+
 Unigraphics {
                 meshGrouping 1
@@ -88 +93 @@
         #       input fromViewCells
         #       input fromSceneGeometry
-                samples 100000
+                samples 200000
                 sideTolerance 0.005
         }
@@ -126 +131 @@
         #splitPlaneStrategy 130
         
-        splitPlaneStrategy 1
+        splitPlaneStrategy 1024
         
         maxPolyCandidates 50
@@ -138 +143 @@
                 minPvs 35
                 minArea 0.01
-                maxRayContribution 0.05
+                maxRayContribution 0.005
                 #maxAccRayLength 100
                 
@@ -166 +171 @@
 Simulation {
         objRenderCost 1.0
-        vcOverhead 0.05
+        vcOverhead 1.0
+        moveSpeed 1.0
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ -87 +87 @@
         environment->GetFloatValue("Simulation.moveSpeed", moveSpeed);
 
+        Debug << "render simulator using render cost=" << objRenderCost << ", vc overhead=" << vcOverhead << ", move speed=" << moveSpeed << endl;
         if (ViewCell::sHierarchy = ViewCell::BSP)
                 mRenderSimulator = new BspViewCellRenderSimulator(objRenderCost, vcOverhead, moveSpeed, mBspTree);

trunk/VUT/GtpVisibilityPreprocessor/src/RenderSimulator.cpp

@@ -48 +48 @@
         for (it = viewCells.begin(); it != it_end; ++ it)
         {
+                // compute view cell area
                 mBspTree->ConstructGeometry(dynamic_cast<BspViewCell *>(*it), geom);
+                const float area = Polygon3::GetArea(geom);
                 CLEAR_CONTAINER(geom);
 
-                const float area = Polygon3::GetArea(geom);
                 // area substitute for view point probability
                 float pInVc = area;

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -479 +479 @@
                                                                                         passContributingSamples,
                                                                                         passSampleContributions);
+
+                                                //mVspKdTree->Construct(mSampleRays, mBoundingBox);
                                         }
+                                        /*else if (ViewCell::sHierarchy == ViewCell::VSPKD)
+                                        {
+                                                ProcessVspKdViewCells(ray,
+                                                                                          reverseSample ? NULL : object,
+                                                                                          faceIndex,
+                                                                                          passContributingSamples,
+                                                                                          passSampleContributions);
+                                        }*/
                                 }
                         } else {

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -1144 +1144 @@
         }
         
-        Debug << "lowest: " << lowestCost << endl;
-
-        //limit = maxRaysCandidates > 0 ? Min((int)rays.size(), maxRayCandidates) : (int)rays.size();   
+        //Debug << "lowest: " << lowestCost << endl;
+
+        //-- choose candidate planes extracted from rays
+        // we currently use two methods
+        // 1) take 3 ray endpoints, where two are minimum and one a maximum
+        //    point or the other way round
+        // 2) take plane normal as plane normal and the midpoint of the ray.
+        //    PROBLEM: does not resemble any point where visibility is likely to change
         const BoundedRayContainer *rays = data.mRays;
 
@@ -1175 +1180 @@
         }
 
-        Debug << "lowest: " << lowestCost << endl;
+        //Debug << "lowest: " << lowestCost << endl;
                 
         for (int i = 0; i < sMaxRayCandidates / 2; ++ i)
@@ -1208 +1213 @@
                 if (candidateCost < lowestCost)
                 {
-                        Debug << "choose ray plane 2: " << candidateCost << endl;
+                        //Debug << "choose ray plane 2: " << candidateCost << endl;
                         bestPlane = plane;
                         
@@ -1215 +1220 @@
         }       
 
+#ifdef _DEBUG
         Debug << "plane lowest cost: " << lowestCost << endl;
+#endif
         return bestPlane;
 }
@@ -1763 +1770 @@
         mStat.accumDepth += data.mDepth;
         
-//#ifdef _DEBUG
+#ifdef _DEBUG
         Debug << "BSP stats: "
                   << "Depth: " << data.mDepth << " (max: " << sTermMaxDepth << "), "
@@ -1772 +1779 @@
                   << "#pvs: " << leaf->GetViewCell()->GetPvs().GetSize() << "=, "
                   << "#avg ray contrib (pvs): " << (float)data.mPvs / (float)data.mRays->size() << endl;
-//#endif
+#endif
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -141 +141 @@
   app << "#N_RAYS ( Number of rays )\n"
       << rays <<endl;
-
-        app << "#N_INITPVS ( Initial PVS size )\n"
+  
+  app << "#N_INITPVS ( Initial PVS size )\n"
       << initialPvsSize <<endl;
   
@@ -370 +370 @@
                                            int &pvsFront)
 {
-
-  int minDirDepth = 6;
-  int axis;
+        int minDirDepth = 6;
+        int axis;
         float costRatio;
         
-  if (splitType == ESplitRegular) {
+        if (splitType == ESplitRegular) {
                 costRatio = BestCostRatioRegular(leaf,
-                                                                                                                                                 axis,
-                                                                                                                                                 position,
-                                                                                                                                                 raysBack,
-                                                                                                                                                 raysFront,
-                                                                                                                                                 pvsBack,
-                                                                                                                                                 pvsFront
-                                                                                                                                                 );
-
-        } else {
-    if (splitType == ESplitHeuristic)
-      costRatio = BestCostRatioHeuristic(leaf,
-                                                                                                                                                                 axis,
-                                                                                                                                                                 position,
-                                                                                                                                                                 raysBack,
-                                                                                                                                                                 raysFront,
-                                                                                                                                                                 pvsBack,
-                                                                                                                                                                 pvsFront
-                                                                                                                                                                 );
+                                                                                 axis,
+                                                                                 position,
+                                                                                 raysBack,
+                                                                                 raysFront,
+                                                                                 pvsBack,
+                                                                                 pvsFront);
+
+        } 
+        else 
+        {
+                if (splitType == ESplitHeuristic)
+                        costRatio = BestCostRatioHeuristic(leaf,
+                                                                                           axis,        
+                                                                                           position,
+                                                                                           raysBack,
+                                                                                           raysFront,
+                                                                                           pvsBack,
+                                                                                           pvsFront);
                 else {
-                        cerr<<"VspKdTree: Unknown split heuristics\n";
+                        cerr << "VspKdTree: Unknown split heuristics\n";
                         exit(1);
                 }
   }
 
-        if (costRatio > termMaxCostRatio) {
+        if (costRatio > termMaxCostRatio) 
+        {
                 //              cout<<"Too big cost ratio "<<costRatio<<endl;
                 return -1;
@@ -421 +421 @@
 
 float
-VspKdTree::EvalCostRatio(
-                                                                                         VspKdTreeLeaf *leaf,
-                                                                                         const int axis,
-                                                                                         const float position,
-                                                                                         int &raysBack,
-                                                                                         int &raysFront,
-                                                                                         int &pvsBack,
-                                                                                         int &pvsFront
-                                                                                         )
+VspKdTree::EvalCostRatio(VspKdTreeLeaf *leaf,
+                                                 const int axis,
+                                                 const float position,
+                                                 int &raysBack,
+                                                 int &raysFront,
+                                                 int &pvsBack,
+                                                 int &pvsFront)
 {
         raysBack = 0;
@@ -448 +446 @@
     // this is the main ray classification loop!
     for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                                ri != leaf->rays.end();
-                                ri++)
-      if ((*ri).mRay->IsActive()) {
+                ri != leaf->rays.end(); ri++)
+                if ((*ri).mRay->IsActive()) 
+                {
+                        // determine the side of this ray with respect to the plane
+                        int side = (*ri).ComputeRayIntersection(axis, position, (*ri).mRay->mT);
+                        //                              (*ri).mRay->mSide = side;
+                        
+                        if (side <= 0)
+                                raysBack ++;
                                 
-                                // determine the side of this ray with respect to the plane
-                                int side = (*ri).ComputeRayIntersection(axis, position, (*ri).mRay->mT);
-                                //                              (*ri).mRay->mSide = side;
+                        if (side >= 0)
+                                raysFront++;
                                 
-                                if (side <= 0)
-                                        raysBack++;
-                                
-                                if (side >= 0)
-                                        raysFront++;
-                                
-                                AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
-      }
+                        AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
+                }
                 
                 AxisAlignedBox3 box = GetBBox(leaf);
@@ -475 +472 @@
 
                 newCost = ct_div_ci + sum/sizeBox;
-                
-  } else {
-                
+        } 
+        else 
+        {
                 // directional split
-    for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                                ri != leaf->rays.end();
-                                ri++)
-      if ((*ri).mRay->IsActive()) {
-                                
+                for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
+                        ri != leaf->rays.end(); ++ ri)
+                        if ((*ri).mRay->IsActive()) 
+                        {
                                 // determine the side of this ray with respect to the plane
                                 int side;
@@ -499 +495 @@
                                 //                              (*ri).mRay->mSide = side;
                                 AddObject2Pvs((*ri).mRay->mTerminationObject, side, pvsBack, pvsFront);
-
-      }
-                
-                AxisAlignedBox3 box = GetDirBBox(leaf);
-                
-                float minBox = box.Min(axis-3);
-                float maxBox = box.Max(axis-3);
-                float sizeBox = maxBox - minBox;
-                
-                //              float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
-                float sum =
-                        pvsBack*(position - minBox) +
-                        pvsFront*(maxBox - position);
+                        }
+        
+                        AxisAlignedBox3 box = GetDirBBox(leaf);
+                
+                        float minBox = box.Min(axis - 3);
+                        float maxBox = box.Max(axis - 3);
+                        float sizeBox = maxBox - minBox;
+                
+                        // float sum = raysBack*(position - minBox) + raysFront*(maxBox - position);
+                        float sum =     pvsBack*(position - minBox) + pvsFront*(maxBox - position);
                 //              float sum = pvsBack + pvsFront;
                 newCost = ct_div_ci + sum/sizeBox;
-  }
+        }
 
         //      cout<<axis<<" "<<pvsSize<<" "<<pvsBack<<" "<<pvsFront<<endl;
         //  float oldCost = leaf->rays.size();
         float oldCost = pvsSize;
-  float ratio = newCost/oldCost;
+        
+        float ratio = newCost / oldCost;
         //      cout<<"ratio="<<ratio<<endl;
         return ratio;
@@ -525 +519 @@
 
 float
-VspKdTree::BestCostRatioRegular(
-                                                                                                                        VspKdTreeLeaf *leaf,
-                                                                                                                        int &axis,
-                                                                                                                        float &position,
-                                                                                                                        int &raysBack,
-                                                                                                                        int &raysFront,
-                                                                                                                        int &pvsBack,
-                                                                                                                        int &pvsFront
-                                                                                                                        )
+VspKdTree::BestCostRatioRegular(VspKdTreeLeaf *leaf,
+                                                                int &axis,
+                                                                float &position,
+                                                                int &raysBack,
+                                                                int &raysFront,
+                                                                int &pvsBack,
+                                                                int &pvsFront)
 {
         int nRaysBack[6], nRaysFront[6];
@@ -543 +535 @@
         AxisAlignedBox3 sBox = GetBBox(leaf);
         AxisAlignedBox3 dBox = GetDirBBox(leaf);
+
         // int sAxis = box.Size().DrivingAxis();
         int sAxis = sBox.Size().DrivingAxis();
@@ -549 +542 @@
         bool onlyDrivingAxis = true; 
 
-        for (axis = 0; axis < 6; axis++) {
-                if (!onlyDrivingAxis || axis == sAxis || axis == dAxis) {
+        for (axis = 0; axis < 6; ++ axis) 
+        {
+                if (!onlyDrivingAxis || axis == sAxis || axis == dAxis) 
+                {
                         if (axis < 3)
                                 nPosition[axis] = (sBox.Min()[axis] + sBox.Max()[axis])*0.5f;
@@ -557 +552 @@
                         
                         nCostRatio[axis] = EvalCostRatio(leaf,
-                                                                                                                                                         axis,
-                                                                                                                                                         nPosition[axis],
-                                                                                                                                                         nRaysBack[axis],
-                                                                                                                                                         nRaysFront[axis],
-                                                                                                                                                         nPvsBack[axis],
-                                                                                                                                                         nPvsFront[axis]
-                                                                                                                                                         );
+                                                                                         axis,
+                                                                                         nPosition[axis],
+                                                                                         nRaysBack[axis],
+                                                                                         nRaysFront[axis],
+                                                                                         nPvsBack[axis],
+                                                                                         nPvsFront[axis]);
                         
-                        if ( bestAxis == -1)
+                        if (bestAxis == -1)
                                 bestAxis = axis;
                         else
-                                if ( nCostRatio[axis] < nCostRatio[bestAxis] )
+                                if (nCostRatio[axis] < nCostRatio[bestAxis])
                                         bestAxis = axis;
                 }
@@ -585 +579 @@
 }
 
-float
-VspKdTree::BestCostRatioHeuristic(
-                                                                                                                                VspKdTreeLeaf *leaf,
-                                                                                                                                int &axis,
-                                                                                                                                float &position,
-                                                                                                                                int &raysBack,
-                                                                                                                                int &raysFront,
-                                                                                                                                int &pvsBack,
-                                                                                                                                int &pvsFront
-                                                                                                                                )
+float VspKdTree::BestCostRatioHeuristic(VspKdTreeLeaf *leaf,
+                                                                                int &axis,
+                                                                                float &position,
+                                                                                int &raysBack,
+                                                                                int &raysFront,
+                                                                                int &pvsBack,
+                                                                                int &pvsFront)
 {
         AxisAlignedBox3 box = GetBBox(leaf);
@@ -622 +613 @@
         // set all object as belonging to the fron pvs
         for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                        ri != leaf->rays.end();
-                        ri++)
-                if ((*ri).mRay->IsActive()) {
+                ri != leaf->rays.end(); ++ ri)
+        {
+                if ((*ri).mRay->IsActive())
+                {
                         Intersectable *object = (*ri).mRay->mTerminationObject;
+                        
                         if (object)
-                                if (!object->Mailed()) {
+                                if (!object->Mailed()) 
+                                {
                                         object->Mail();
                                         object->mCounter = 1;
-                                } else
-                                        object->mCounter++;
-                }
+                                } 
+                                else
+                                        ++ object->mCounter;
+                }
+        }
         
         Intersectable::NewMail();
         
-        for(vector<SortableEntry>::const_iterator ci = splitCandidates->begin();
-                        ci < splitCandidates->end();
-                        ci++) {
+        for (vector<SortableEntry>::const_iterator ci = splitCandidates->begin();
+                ci < splitCandidates->end(); ++ ci) 
+        {
                 VssRay *ray;
-                switch ((*ci).type) {
-                case SortableEntry::ERayMin: {
-                        rl++;
-                        ray = (VssRay *) (*ci).data;
-                        Intersectable *object = ray->mTerminationObject;
-                        if (object && !object->Mailed()) {
-                                object->Mail();
-                                pl++;
-                        }
-                        break;
-                }
-                case SortableEntry::ERayMax: {
-                        rr--;
-                        ray = (VssRay *) (*ci).data;
-                        Intersectable *object = ray->mTerminationObject;
-                        if (object) {
-                                if (--object->mCounter == 0)
-                                        pr--;
-                        }
-                        break;
-                }
-                }
-                if ((*ci).value > minBand && (*ci).value < maxBand) {
                         
+                switch ((*ci).type) 
+                {
+                        case SortableEntry::ERayMin: 
+                                {
+                                        ++ rl;
+                                        ray = (VssRay *) (*ci).data;
+                                        Intersectable *object = ray->mTerminationObject;
+                                        if (object && !object->Mailed()) 
+                                        {
+                                                object->Mail();
+                                                ++ pl;
+                                        }
+                                        break;
+                                }
+                        case SortableEntry::ERayMax: 
+                                {
+                                        -- rr;
+                                        
+                                        ray = (VssRay *) (*ci).data;
+                                        Intersectable *object = ray->mTerminationObject;
+                                        
+                                        if (object)
+                                        {
+                                                if (-- object->mCounter == 0)
+                                                -- pr;
+                                        }
+                                                
+                                        break;
+                                }
+                }
+                        
+                if ((*ci).value > minBand && (*ci).value < maxBand) 
+                {
                         sum = pl*((*ci).value - minBox) + pr*(maxBox - (*ci).value);
+                
+                        //  cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+                        // cout<<"cost= "<<sum<<endl;
                         
-                        //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
-                        //      cout<<"cost= "<<sum<<endl;
-                        
-                        if (sum < minSum) {
+                        if (sum < minSum) 
+                        {
                                 minSum = sum;
                                 position = (*ci).value;
-                                
+                        
                                 raysBack = rl;
                                 raysFront = rr;
-                                
+                        
                                 pvsBack = pl;
                                 pvsFront = pr;
                                 
-      }
-    }
-  }
-  
-  float oldCost = leaf->GetPvsSize();
-  float newCost = ct_div_ci + minSum/sizeBox;
-  float ratio = newCost/oldCost;
-  
-  //  cout<<"===================="<<endl;
-  //  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
-  //      <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl;
+                        }
+                }
+        }
+
+        float oldCost = leaf->GetPvsSize();
+        float newCost = ct_div_ci + minSum / sizeBox;
+        float ratio = newCost / oldCost;
+  
+        //  cout<<"===================="<<endl;
+        //  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
+        //      <<"\t q=("<<queriesBack<<","<<queriesFront<<")\t r=("<<raysBack<<","<<raysFront<<")"<<endl;
+        
         return ratio;
 }
 
-void
-VspKdTree::SortSplitCandidates(
-                                                                                                                 VspKdTreeLeaf *node,
-                                                                                                                 const int axis
-                                                                                                                 )
-{
-  
-  splitCandidates->clear();
-  
-  int requestedSize = 2*(node->rays.size());
-  // creates a sorted split candidates array
-  if (splitCandidates->capacity() > 500000 &&
-      requestedSize < (int)(splitCandidates->capacity()/10) ) {
-    
-    delete splitCandidates;
-    splitCandidates = new vector<SortableEntry>;
-  }
-  
-  splitCandidates->reserve(requestedSize);
-
-  // insert all queries 
-  for(VspKdTreeNode::RayInfoContainer::const_iterator ri = node->rays.begin();
-      ri < node->rays.end();
-      ri++) {
-    bool positive = (*ri).mRay->HasPosDir(axis);
-    splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin :
-                                                                                                                                                                                 SortableEntry::ERayMax,
-                                                                                                                                                                                 (*ri).ExtrapOrigin(axis),
-                                                                                                                                                                                 (void *)&*ri)
-                                                                                                                         );
-                
-    splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax :
-                                                                                                                                                                                 SortableEntry::ERayMin,
-                                                                                                                                                                                 (*ri).ExtrapTermination(axis),
-                                                                                                                                                                                 (void *)&*ri)
-                                                                                                                         );
-  }
-        
-  stable_sort(splitCandidates->begin(), splitCandidates->end());
-}
-
-
-void
-VspKdTree::EvaluateLeafStats(const TraversalData &data)
-{
-
-  // the node became a leaf -> evaluate stats for leafs
-  VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.node;
-
-  if (data.depth >= termMaxDepth)
-    stat.maxDepthNodes++;
+void VspKdTree::SortSplitCandidates(VspKdTreeLeaf *node,
+                                                                        const int axis)
+{
+        splitCandidates->clear();
+  
+        int requestedSize = 2*(node->rays.size());
+        // creates a sorted split candidates array
+        if (splitCandidates->capacity() > 500000 &&
+                requestedSize < (int)(splitCandidates->capacity()/10) ) 
+        {
+        delete splitCandidates;
+                splitCandidates = new vector<SortableEntry>;
+        }
+  
+        splitCandidates->reserve(requestedSize);
+
+        // insert all queries 
+        for(VspKdTreeNode::RayInfoContainer::const_iterator ri = node->rays.begin();
+                ri < node->rays.end(); ++ ri) 
+        {
+                bool positive = (*ri).mRay->HasPosDir(axis);
+                splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMin : SortableEntry::ERayMax, 
+                                                                                                 (*ri).ExtrapOrigin(axis), (void *)&*ri));
+                
+                splitCandidates->push_back(SortableEntry(positive ? SortableEntry::ERayMax : SortableEntry::ERayMin,
+                                                                                                 (*ri).ExtrapTermination(axis), (void *)&*ri));
+        }
+        
+        stable_sort(splitCandidates->begin(), splitCandidates->end());
+}
+
+
+void VspKdTree::EvaluateLeafStats(const TraversalData &data)
+{
+        // the node became a leaf -> evaluate stats for leafs
+        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.node;
+
+        if (data.depth >= termMaxDepth)
+                ++ stat.maxDepthNodes;
   
         //  if ( (int)(leaf->rays.size()) < termMinCost)
         //    stat.minCostNodes++;
-        if ( leaf->GetPvsSize() < termMinPvs)
-                stat.minPvsNodes++;
-
-        if ( leaf->GetPvsSize() < termMinRays)
-                stat.minRaysNodes++;
-
-        if (0 && leaf->GetAvgRayContribution() > termMaxRayContribution )
-                stat.maxRayContribNodes++;
-        
-        if (SqrMagnitude(data.bbox.Size()) <= termMinSize) {
-                stat.minSizeNodes++;
-        }
-
-        if ( (int)(leaf->rays.size()) > stat.maxRayRefs)
-    stat.maxRayRefs = leaf->rays.size();
-
-}
-
-
-
-VspKdTreeNode *
-VspKdTree::SubdivideNode(
-                                                                                         VspKdTreeLeaf *leaf,
-                                                                                         const AxisAlignedBox3 &box,
-                                                                                         AxisAlignedBox3 &backBBox,
-                                                                                         AxisAlignedBox3 &frontBBox
-                                                                                         )
-{
-  
-  if ( (leaf->GetPvsSize() < termMinPvs) || (leaf->rays.size() < termMinRays) ||
+        if (leaf->GetPvsSize() < termMinPvs)
+                ++ stat.minPvsNodes;
+
+        if (leaf->GetPvsSize() < termMinRays)
+                ++ stat.minRaysNodes;
+
+        if (0 && leaf->GetAvgRayContribution() > termMaxRayContribution)
+                ++ stat.maxRayContribNodes;
+        
+        if (SqrMagnitude(data.bbox.Size()) <= termMinSize) 
+                ++ stat.minSizeNodes;
+
+        if ((int)(leaf->rays.size()) > stat.maxRayRefs)
+                stat.maxRayRefs = leaf->rays.size();
+}
+
+
+
+VspKdTreeNode *VspKdTree::SubdivideNode(VspKdTreeLeaf *leaf,
+                                                                                const AxisAlignedBox3 &box,
+                                                                                AxisAlignedBox3 &backBBox,
+                                                                                AxisAlignedBox3 &frontBBox)
+{
+        if ( (leaf->GetPvsSize() < termMinPvs) || (leaf->rays.size() < termMinRays) ||
         // (leaf->GetAvgRayContribution() > termMaxRayContribution ) ||
        (leaf->depth >= termMaxDepth) || SqrMagnitude(box.Size()) <= termMinSize ) 
-  {
+        {
 
 #if 0
@@ -792 +782 @@
         
         float position;
-        
         // first count ray sides
-  int raysBack;
-  int raysFront;
+        int raysBack;
+        int raysFront;
         int pvsBack;
         int pvsFront;
         
-  // select subdivision axis
-  int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
+        // select subdivision axis
+        int axis = SelectPlane( leaf, box, position, raysBack, raysFront, pvsBack, pvsFront);
 
         //      cout<<"rays back="<<raysBack<<" rays front="<<raysFront<<" pvs back="<<pvsBack<<" pvs front="<<
         //              pvsFront<<endl;
 
-  if (axis == -1) {
-    return leaf;
-  }
-  
-  stat.nodes+=2;
-  stat.splits[axis]++;
-
-  // add the new nodes to the tree
-  VspKdTreeInterior *node = new VspKdTreeInterior(leaf->parent);
-
-  node->axis = axis;
-  node->position = position;
-  node->bbox = box;
-  node->dirBBox = GetDirBBox(leaf);
-  
-  backBBox = box;
-  frontBBox = box;
-
-  VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack);
+        if (axis == -1) 
+        {
+                return leaf;
+        }
+  
+        stat.nodes += 2;
+        ++ stat.splits[axis];
+
+        // add the new nodes to the tree
+        VspKdTreeInterior *node = new VspKdTreeInterior(leaf->parent);
+
+        node->axis = axis;
+        node->position = position;
+        node->bbox = box;
+        node->dirBBox = GetDirBBox(leaf);
+  
+        backBBox = box;
+        frontBBox = box;
+
+        VspKdTreeLeaf *back = new VspKdTreeLeaf(node, raysBack);
         back->SetPvsSize(pvsBack);
-  VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront);
+        VspKdTreeLeaf *front = new VspKdTreeLeaf(node, raysFront);
         front->SetPvsSize(pvsFront);
 
-  // replace a link from node's parent
-  if (  leaf->parent )
-    leaf->parent->ReplaceChildLink(leaf, node);
-  // and setup child links
-  node->SetupChildLinks(back, front);
-        
-  if (axis <= VspKdTreeNode::SPLIT_Z) {
+        // replace a link from node's parent
+        if (leaf->parent)
+                leaf->parent->ReplaceChildLink(leaf, node);
+        // and setup child links
+        node->SetupChildLinks(back, front);
+        
+        if (axis <= VspKdTreeNode::SPLIT_Z) 
+        {
                 backBBox.SetMax(axis, position);
-    frontBBox.SetMin(axis, position);
+                frontBBox.SetMin(axis, position);
                 
                 for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                                ri != leaf->rays.end();
-                                ri++) {
-      if ((*ri).mRay->IsActive()) {
-                                
+                                ri != leaf->rays.end(); ri++) 
+                {
+                        if ((*ri).mRay->IsActive()) 
+                        {
                                 // first unref ray from the former leaf
                                 (*ri).mRay->Unref();
@@ -849 +840 @@
                                 int side = node->ComputeRayIntersection(*ri, (*ri).mRay->mT);
 
-                                if (side == 0) {
-                                        if ((*ri).mRay->HasPosDir(axis)) {
+                                if (side == 0) 
+                                {
+                                        if ((*ri).mRay->HasPosDir(axis)) 
+                                        {
                                                 back->AddRay(VspKdTreeNode::RayInfo((*ri).mRay,
-                                                                                                                                                                                        (*ri).mMinT,
-                                                                                                                                                                                        (*ri).mRay->mT)
-                                                                                                 );
+                                                                                                                        (*ri).mMinT,
+                                                                                                                        (*ri).mRay->mT));
                                                 front->AddRay(VspKdTreeNode::RayInfo((*ri).mRay,
-                                                                                                                                                                                         (*ri).mRay->mT,
-                                                                                                                                                                                         (*ri).mMaxT));
-                                        } else {
+                                                                                                                         (*ri).mRay->mT,
+                                                                                                                         (*ri).mMaxT));
+                                        } 
+                                        else 
+                                        {
                                                 back->AddRay(VspKdTreeNode::RayInfo((*ri).mRay,
-                                                                                                                                                                                        (*ri).mRay->mT,
-                                                                                                                                                                                        (*ri).mMaxT));
+                                                                                                                        (*ri).mRay->mT,
+                                                                                                                        (*ri).mMaxT));
                                                 front->AddRay(VspKdTreeNode::RayInfo((*ri).mRay,
-                                                                                                                                                                                         (*ri).mMinT,
-                                                                                                                                                                                         (*ri).mRay->mT));
+                                                                                                                         (*ri).mMinT,
+                                                                                                                         (*ri).mRay->mT));
                                         }
-                                } else
+                                } 
+                                else
                                         if (side == 1) 
                                                 front->AddRay(*ri);
                                         else
                                                 back->AddRay(*ri);
-      } else
+                        } else
                                 (*ri).mRay->Unref();
-    }
-  } else {
-    // rays front/back
+                }
+        } 
+        else 
+        {
+                // rays front/back
     
-    
-    for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                                ri != leaf->rays.end();
-                                ri++) {
-      if ((*ri).mRay->IsActive()) {
+        for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
+                        ri != leaf->rays.end(); ++ ri) 
+                {
+                        if ((*ri).mRay->IsActive()) 
+                        {
                                 // first unref ray from the former leaf
                                 (*ri).mRay->Unref();
@@ -894 +891 @@
                                         front->AddRay(*ri);
                                 else
-                                        back->AddRay(*ri);
-                                
-      } else
+                                        back->AddRay(*ri);              
+                        } 
+                        else
                                 (*ri).mRay->Unref();
-    }
-  }
-        
-  // update stats
-  stat.rayRefs -= leaf->rays.size();
-  stat.rayRefs += raysBack + raysFront;
-
-  
-  delete leaf;
-  return node;
-}
-
-
-
-
-
-
-int
-VspKdTree::ReleaseMemory(const int time)
-{
-  stack<VspKdTreeNode *> tstack;
-  
-  // find a node in the tree which subtree will be collapsed
-  int maxAccessTime = time - accessTimeThreshold;
-  int released;
-
-  tstack.push(root);
-
-  while (!tstack.empty()) {
-    VspKdTreeNode *node = tstack.top();
-    tstack.pop();
+                }
+        }
+        
+        // update stats
+        stat.rayRefs -= leaf->rays.size();
+        stat.rayRefs += raysBack + raysFront;
+
+        delete leaf;
+        return node;
+}
+
+int VspKdTree::ReleaseMemory(const int time)
+{
+        stack<VspKdTreeNode *> tstack;
+
+        // find a node in the tree which subtree will be collapsed
+        int maxAccessTime = time - accessTimeThreshold;
+        int released;
+
+        tstack.push(root);
+
+        while (!tstack.empty()) 
+        {
+                VspKdTreeNode *node = tstack.top();
+                tstack.pop();
     
- 
-    if (!node->IsLeaf()) {
-      VspKdTreeInterior *in = (VspKdTreeInterior *)node;
-      //      cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
-      if (in->depth >= minCollapseDepth &&
-          in->lastAccessTime <= maxAccessTime) {
-        released = CollapseSubtree(node, time);
-        break;
-      }
-      
-      if (in->back->GetAccessTime() <  
-          in->front->GetAccessTime()) {
-        tstack.push(in->front);
-        tstack.push(in->back);
-      } else {
-        tstack.push(in->back);
-        tstack.push(in->front);
-      }
-    }
-  }
-
-  while (tstack.empty()) {
-    // could find node to collaps...
-    //    cout<<"Could not find a node to release "<<endl;
-    break;
-  }
-  
-  return released;
-}
-
-
-
-
-VspKdTreeNode *
-VspKdTree::SubdivideLeaf(
-                                                                                         VspKdTreeLeaf *leaf,
-                                                                                         const float sizeThreshold
-                                                                                         )
-{
-  VspKdTreeNode *node = leaf;
-
-  AxisAlignedBox3 leafBBox = GetBBox(leaf);
+                if (!node->IsLeaf()) 
+                {
+                        VspKdTreeInterior *in = (VspKdTreeInterior *)node;
+                        // cout<<"depth="<<(int)in->depth<<" time="<<in->lastAccessTime<<endl;
+                        if (in->depth >= minCollapseDepth && in->lastAccessTime <= maxAccessTime) 
+                        {
+                                released = CollapseSubtree(node, time);
+                                break;
+                        }
+                        if (in->back->GetAccessTime() <  in->front->GetAccessTime()) 
+                        {
+                                tstack.push(in->front);
+                                tstack.push(in->back);
+                        } 
+                        else 
+                        {
+                                tstack.push(in->back);
+                                tstack.push(in->front);
+                        }
+                }
+        }
+
+        while (tstack.empty()) 
+        {
+                // could find node to collaps...
+                // cout<<"Could not find a node to release "<<endl;
+                break;
+        }
+  
+        return released;
+}
+
+
+
+
+VspKdTreeNode *VspKdTree::SubdivideLeaf(VspKdTreeLeaf *leaf,
+                                                                                const float sizeThreshold)
+{
+        VspKdTreeNode *node = leaf;
+
+        AxisAlignedBox3 leafBBox = GetBBox(leaf);
 
         static int pass = 0;
-        pass ++;
-        
-  // check if we should perform a dynamic subdivision of the leaf
-  if (
-                        //      leaf->rays.size() > (unsigned)termMinCost &&
-                        (leaf->GetPvsSize() >= termMinPvs) &&
-      SqrMagnitude(leafBBox.Size()) > sizeThreshold) {
-    
-                // memory check and realese...
-    if (GetMemUsage() > maxTotalMemory) {
-      ReleaseMemory( pass );
-    }
-    
-    AxisAlignedBox3 backBBox, frontBBox;
-
-    // subdivide the node
-    node =
-      SubdivideNode(leaf,
-                                                                                leafBBox,
-                                                                                backBBox,
-                                                                                frontBBox
-                                                                                );
-  }
-  return node;
+        ++ pass;
+        
+        // check if we should perform a dynamic subdivision of the leaf
+        if (// leaf->rays.size() > (unsigned)termMinCost &&
+                (leaf->GetPvsSize() >= termMinPvs) && 
+                (SqrMagnitude(leafBBox.Size()) > sizeThreshold) )
+        {
+        // memory check and realese...
+                if (GetMemUsage() > maxTotalMemory) 
+                        ReleaseMemory(pass);
+                
+                AxisAlignedBox3 backBBox, frontBBox;
+
+                // subdivide the node
+                node = SubdivideNode(leaf, leafBBox, backBBox, frontBBox);
+        }
+        return node;
 }
 
@@ -1004 +987 @@
 void
 VspKdTree::UpdateRays(VssRayContainer &remove,
-                                                                                VssRayContainer &add
-                                                                                )
-{
-  VspKdTreeLeaf::NewMail();
-
-  // schedule rays for removal
-  for(VssRayContainer::const_iterator ri = remove.begin();
-      ri != remove.end();
-      ri++) {
-    (*ri)->ScheduleForRemoval();
-  }
-
-  int inactive=0;
-
-  for(VssRayContainer::const_iterator ri = remove.begin();
-      ri != remove.end();
-      ri++) {
-    if ((*ri)->ScheduledForRemoval())
-//      RemoveRay(*ri, NULL, false);
-// !!! BUG - with true it does not work correctly - aggreated delete
-      RemoveRay(*ri, NULL, true);
-    else
-      inactive++;
-  }
-
-
-  //  cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
-  
-  for(VssRayContainer::const_iterator ri = add.begin();
-      ri != add.end();
-      ri++) {
-    AddRay(*ri);
-  }
-  
-
-}
-
-
-void
-VspKdTree::RemoveRay(VssRay *ray,
-                                                                         vector<VspKdTreeLeaf *> *affectedLeaves,
-                                                                         const bool removeAllScheduledRays
-                                                                         )
-{
-        
-  stack<RayTraversalData> tstack;
-
-  tstack.push(RayTraversalData(root, VspKdTreeNode::RayInfo(ray)));
-  
-  RayTraversalData data;
-
-  // cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
-
-  while (!tstack.empty()) {
-    data = tstack.top();
-    tstack.pop();
-
-    if (!data.node->IsLeaf()) {
-      // split the set of rays in two groups intersecting the
-      // two subtrees
-
-      TraverseInternalNode(data, tstack);
+                                          VssRayContainer &add)
+{
+        VspKdTreeLeaf::NewMail();
+
+        // schedule rays for removal
+        for(VssRayContainer::const_iterator ri = remove.begin();
+                ri != remove.end(); ++ ri) 
+        {
+                (*ri)->ScheduleForRemoval();  
+        }
+
+        int inactive = 0;
+
+        for (VssRayContainer::const_iterator ri = remove.begin(); ri != remove.end(); ++ ri) 
+        {
+                if ((*ri)->ScheduledForRemoval())
+                        //      RemoveRay(*ri, NULL, false);
+                        // !!! BUG - with true it does not work correctly - aggreated delete
+                        RemoveRay(*ri, NULL, true);
+                else
+                        ++ inactive;
+        }
+
+        //  cout<<"all/inactive"<<remove.size()<<"/"<<inactive<<endl;
+  
+        for(VssRayContainer::const_iterator ri = add.begin(); ri != add.end(); ++ ri) 
+        {
+                AddRay(*ri);
+        }
+}
+
+
+void VspKdTree::RemoveRay(VssRay *ray,
+                                                  vector<VspKdTreeLeaf *> *affectedLeaves,
+                                                  const bool removeAllScheduledRays)
+{
+        stack<RayTraversalData> tstack;
+
+        tstack.push(RayTraversalData(root, VspKdTreeNode::RayInfo(ray)));
+  
+        RayTraversalData data;
+
+        // cout<<"Number of ray refs = "<<ray->RefCount()<<endl;
+        while (!tstack.empty()) 
+        {
+                data = tstack.top();
+                tstack.pop();
+
+                if (!data.node->IsLeaf()) 
+                {
+                        // split the set of rays in two groups intersecting the
+                        // two subtrees
+
+                        TraverseInternalNode(data, tstack);
+        } 
+                else 
+                {
+                        // remove the ray from the leaf
+                        // find the ray in the leaf and swap it with the last ray...
+                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.node;
       
-    } else {
-      // remove the ray from the leaf
-      // find the ray in the leaf and swap it with the last ray...
-      VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.node;
+                        if (!leaf->Mailed()) 
+                        {
+                                leaf->Mail();
+                                
+                                if (affectedLeaves)
+                                        affectedLeaves->push_back(leaf);
+        
+                                if (removeAllScheduledRays) 
+                                {
+                                        int tail = leaf->rays.size() - 1;
+
+                                        for (int i=0; i < (int)(leaf->rays.size()); ++ i) 
+                                        {
+                                                if (leaf->rays[i].mRay->ScheduledForRemoval()) 
+                                                {
+                                                        // find a ray to replace it with
+                                                        while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) 
+                                                        {
+                                                                ++ stat.removedRayRefs;
+                                                                leaf->rays[tail].mRay->Unref();
+                                                                leaf->rays.pop_back();
+                                                                
+                                                                -- tail;
+                                                        }
+                                                        
+                                                        if (tail < i)
+                                                                break;
+              
+                                                        ++ stat.removedRayRefs;
+              
+                                                        leaf->rays[i].mRay->Unref();
+                                                        leaf->rays[i] = leaf->rays[tail];
+                                                        leaf->rays.pop_back();
+                                                        -- tail;
+                                                }
+                                        }
+                                }
+                        }
       
-      if (!leaf->Mailed()) {
-        leaf->Mail();
-        if (affectedLeaves)
-          affectedLeaves->push_back(leaf);
-        
-        if (removeAllScheduledRays) {
-          int tail = leaf->rays.size()-1;
-
-          for (int i=0; i < (int)(leaf->rays.size()); i++) {
-            if (leaf->rays[i].mRay->ScheduledForRemoval()) {
-              // find a ray to replace it with
-              while (tail >= i && leaf->rays[tail].mRay->ScheduledForRemoval()) {
-                stat.removedRayRefs++;
-                leaf->rays[tail].mRay->Unref();
-                leaf->rays.pop_back();
-                tail--;
-              }
-
-              if (tail < i)
-                break;
-              
-              stat.removedRayRefs++;
-              leaf->rays[i].mRay->Unref();
-              leaf->rays[i] = leaf->rays[tail];
-              leaf->rays.pop_back();
-              tail--;
-            }
-          }
-        }
-      }
-      
-      if (!removeAllScheduledRays)
-        for (int i=0; i < (int)leaf->rays.size(); i++) {
-          if (leaf->rays[i].mRay == ray) {
-            stat.removedRayRefs++;
-            ray->Unref();
-            leaf->rays[i] = leaf->rays[leaf->rays.size()-1];
-            leaf->rays.pop_back();
-            // check this ray again
-            break;
-          }
-        }
-      
-    }
-  }
-
-  if (ray->RefCount() != 0) {
-    cerr<<"Error: Number of remaining refs = "<<ray->RefCount()<<endl;
-    exit(1);
-  }
-  
-}
-
-
-void
-VspKdTree::AddRay(VssRay *ray)
-{
-
-  stack<RayTraversalData> tstack;
-  
-  tstack.push(RayTraversalData(root, VspKdTreeNode::RayInfo(ray)));
-  
-  RayTraversalData data;
-  
-  while (!tstack.empty()) {
-    data = tstack.top();
-    tstack.pop();
-
-    if (!data.node->IsLeaf()) {
-      TraverseInternalNode(data, tstack);
-    } else {
-      // remove the ray from the leaf
-      // find the ray in the leaf and swap it with the last ray...
-      VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.node;
-      leaf->AddRay(data.rayData);
-      stat.addedRayRefs++;
-    }
-  }
-}
-
-void
-VspKdTree::TraverseInternalNode(
-                                                                                                                        RayTraversalData &data,
-                                                                                                                        stack<RayTraversalData> &tstack)
-{
-  VspKdTreeInterior *in =  (VspKdTreeInterior *) data.node;
-  
-  if (in->axis <= VspKdTreeNode::SPLIT_Z) {
-
-    // determine the side of this ray with respect to the plane
-    int side = in->ComputeRayIntersection(data.rayData,
-                                                                                                                                                                        data.rayData.mRay->mT);
+                        if (!removeAllScheduledRays)
+                                for (int i=0; i < (int)leaf->rays.size(); i++) 
+                                {
+                                        if (leaf->rays[i].mRay == ray) 
+                                        {
+                                                ++ stat.removedRayRefs;
+                                                ray->Unref();
+                                                leaf->rays[i] = leaf->rays[leaf->rays.size() - 1];
+                                                leaf->rays.pop_back();
+                                            // check this ray again
+                                                break;
+                                        }
+                                }
+                }
+        }
+
+        if (ray->RefCount() != 0) 
+        {
+                cerr << "Error: Number of remaining refs = " << ray->RefCount() << endl;
+                exit(1);
+        }
+
+}
+
+void VspKdTree::AddRay(VssRay *ray)
+{
+        stack<RayTraversalData> tstack;
+  
+        tstack.push(RayTraversalData(root, VspKdTreeNode::RayInfo(ray)));
+  
+        RayTraversalData data;
+  
+        while (!tstack.empty()) 
+        {
+                data = tstack.top();
+                tstack.pop();
+
+                if (!data.node->IsLeaf()) 
+                {
+                        TraverseInternalNode(data, tstack);
+                } 
+                else 
+                {
+                        // remove the ray from the leaf
+                        // find the ray in the leaf and swap it with the last ray...
+                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)data.node;
+                        leaf->AddRay(data.rayData);
+                        ++ stat.addedRayRefs;
+                }
+        }
+}
+
+void VspKdTree::TraverseInternalNode(RayTraversalData &data, 
+                                                                         stack<RayTraversalData> &tstack)
+{
+        VspKdTreeInterior *in =  (VspKdTreeInterior *) data.node;
+  
+        if (in->axis <= VspKdTreeNode::SPLIT_Z) 
+        {
+            // determine the side of this ray with respect to the plane
+                int side = in->ComputeRayIntersection(data.rayData, data.rayData.mRay->mT);
     
-  
-    if (side == 0) {
-      if (data.rayData.mRay->HasPosDir(in->axis)) {
-                                tstack.push(RayTraversalData(in->back,
-                                                                                                                                                 VspKdTreeNode::RayInfo(data.rayData.mRay,
-                                                                                                                                                                                                                                        data.rayData.mMinT,
-                                                                                                                                                                                                                                        data.rayData.mRay->mT))
-                                                                                );
+      if (side == 0) 
+          {
+                if (data.rayData.mRay->HasPosDir(in->axis)) 
+                {
+                        tstack.push(RayTraversalData(in->back, 
+                                                VspKdTreeNode::RayInfo(data.rayData.mRay, data.rayData.mMinT, 
+                                                                                           data.rayData.mRay->mT)));
                                 
-                                tstack.push(RayTraversalData(in->front,
-                                                                                                                                                 VspKdTreeNode::RayInfo(data.rayData.mRay,
-                                                                                                                                                                                                                                        data.rayData.mRay->mT,
-                                                                                                                                                                                                                                        data.rayData.mMaxT
-                                                                                                                                                                                                                                        ))
-                                                                                );
-        
-      } else {
-                                tstack.push(RayTraversalData(in->back,
-                                                                                                                                                 VspKdTreeNode::RayInfo(data.rayData.mRay,
-                                                                                                                                                                                                                                        data.rayData.mRay->mT,
-                                                                                                                                                                                                                                        data.rayData.mMaxT
-                                                                                                                                                                                                                                        ))
-                                                                                );
-                                
-                                tstack.push(RayTraversalData(in->front,
-                                                                                                                                                 VspKdTreeNode::RayInfo(data.rayData.mRay,
-                                                                                                                                                                                                                                        data.rayData.mMinT,
-                                                                                                                                                                                                                                        data.rayData.mRay->mT))
-                                                                                );
-                                
-                                
-      }
-    } else
-      if (side == 1)
-                                tstack.push(RayTraversalData(in->front, data.rayData));
-      else
-                                tstack.push(RayTraversalData(in->back, data.rayData));
-  } 
-  else {
-    // directional split
+                        tstack.push(RayTraversalData(in->front,
+                                                VspKdTreeNode::RayInfo(data.rayData.mRay, data.rayData.mRay->mT, 
+                                                                                           data.rayData.mMaxT)));
+        
+                } 
+                else 
+                {
+                        tstack.push(RayTraversalData(in->back,
+                                                                                 VspKdTreeNode::RayInfo(data.rayData.mRay,
+                                                                                                                                data.rayData.mRay->mT,
+                                                                                                                                data.rayData.mMaxT)));
+                        tstack.push(RayTraversalData(in->front,
+                                                                                 VspKdTreeNode::RayInfo(data.rayData.mRay,
+                                                                                                                                data.rayData.mMinT,
+                                                                                                                                data.rayData.mRay->mT)));
+                }
+          } 
+          else
+          if (side == 1)
+                          tstack.push(RayTraversalData(in->front, data.rayData));
+                  else
+                          tstack.push(RayTraversalData(in->back, data.rayData));
+        } 
+        else 
+        {
+                // directional split
                 if (data.rayData.mRay->GetDirParametrization(in->axis - 3) > in->position)
                         tstack.push(RayTraversalData(in->front, data.rayData));
                 else
                         tstack.push(RayTraversalData(in->back, data.rayData));
-  }
-}
-
-
-int
-VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time)
-{
-  // first count all rays in the subtree
-  // use mail 1 for this purpose
-  stack<VspKdTreeNode *> tstack;
-  int rayCount = 0;
-  int totalRayCount = 0;
-  int collapsedNodes = 0;
+        }
+}
+
+
+int VspKdTree::CollapseSubtree(VspKdTreeNode *sroot, const int time)
+{
+        // first count all rays in the subtree
+        // use mail 1 for this purpose
+        stack<VspKdTreeNode *> tstack;
+        
+        int rayCount = 0;
+        int totalRayCount = 0;
+        int collapsedNodes = 0;
 
 #if DEBUG_COLLAPSE
-  cout<<"Collapsing subtree"<<endl;
-  cout<<"acessTime="<<sroot->GetAccessTime()<<endl;
-  cout<<"depth="<<(int)sroot->depth<<endl;
+        cout<<"Collapsing subtree"<<endl;
+        cout<<"acessTime="<<sroot->GetAccessTime()<<endl;
+        cout<<"depth="<<(int)sroot->depth<<endl;
 #endif
 
-//    tstat.collapsedSubtrees++;
-//    tstat.collapseDepths += (int)sroot->depth;
-//    tstat.collapseAccessTimes += time - sroot->GetAccessTime();
-  
-  tstack.push(sroot);
-  VssRay::NewMail();
-        
-  while (!tstack.empty()) {
-    collapsedNodes++;
-    VspKdTreeNode *node = tstack.top();
-    tstack.pop();
-
-    if (node->IsLeaf()) {
-      VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node;
-      for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                                        ri != leaf->rays.end();
-                                        ri++) {
+        // tstat.collapsedSubtrees++;
+        // tstat.collapseDepths += (int)sroot->depth;
+        // tstat.collapseAccessTimes += time - sroot->GetAccessTime();
+        tstack.push(sroot);
+        VssRay::NewMail();
+        
+        while (!tstack.empty()) 
+        {
+                ++ collapsedNodes;
+                
+                VspKdTreeNode *node = tstack.top();
+                tstack.pop();
+                if (node->IsLeaf()) 
+                {
+                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node;
+                        
+                        for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
+                                        ri != leaf->rays.end(); ++ ri) 
+                        {
+                                ++ totalRayCount;
                                 
-                                totalRayCount++;
-                                if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed()) {
+                                if ((*ri).mRay->IsActive() && !(*ri).mRay->Mailed()) 
+                                {
                                         (*ri).mRay->Mail();
-                                        rayCount++;
+                                        ++ rayCount;
                                 }
-      }
-    } else {
-      tstack.push(((VspKdTreeInterior *)node)->back);
-      tstack.push(((VspKdTreeInterior *)node)->front);
-    }
-  }
-  
-  VssRay::NewMail();
-
-  // create a new node that will hold the rays
-  VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf( sroot->parent, rayCount );
-  if (  newLeaf->parent )
-    newLeaf->parent->ReplaceChildLink(sroot, newLeaf);
-  
-
-  tstack.push( sroot );
-
-  while (!tstack.empty()) {
-
-    VspKdTreeNode *node = tstack.top();
-    tstack.pop();
-
-    if (node->IsLeaf()) {
-      VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node;
-      
-      for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                                        ri != leaf->rays.end();
-                                        ri++) {
-                                
-                                // unref this ray from the old node
-                                
-                                if ((*ri).mRay->IsActive()) {
+                        }
+                } 
+                else 
+                {
+                        tstack.push(((VspKdTreeInterior *)node)->back);
+                        tstack.push(((VspKdTreeInterior *)node)->front);
+                }
+        }
+  
+        VssRay::NewMail();
+
+        // create a new node that will hold the rays
+        VspKdTreeLeaf *newLeaf = new VspKdTreeLeaf(sroot->parent, rayCount);
+        
+        if (newLeaf->parent)
+                newLeaf->parent->ReplaceChildLink(sroot, newLeaf);
+
+        tstack.push(sroot);
+
+        while (!tstack.empty()) 
+        {
+                VspKdTreeNode *node = tstack.top();
+                tstack.pop();
+
+                if (node->IsLeaf()) 
+                {
+                        VspKdTreeLeaf *leaf = (VspKdTreeLeaf *) node;
+
+                        for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
+                                        ri != leaf->rays.end(); ++ ri) 
+                        {
+                                // unref this ray from the old node             
+                                if ((*ri).mRay->IsActive()) 
+                                {
                                         (*ri).mRay->Unref();
-                                        if (!(*ri).mRay->Mailed()) {
+                                        if (!(*ri).mRay->Mailed()) 
+                                        {
                                                 (*ri).mRay->Mail();
                                                 newLeaf->AddRay(*ri);
                                         }
-                                } else
+                                } 
+                                else
                                         (*ri).mRay->Unref();
-                                
-      }
-    } else {
-      tstack.push(((VspKdTreeInterior *)node)->back);
-      tstack.push(((VspKdTreeInterior *)node)->front);
-    }
-  }
-  
-  // delete the node and all its children
-  delete sroot;
-  
-//   for(VspKdTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin();
-//       ri != newLeaf->rays.end();
-//       ri++)
-//     (*ri).ray->UnMail(2);
-
+                        }
+                } 
+                else 
+                {
+                        tstack.push(((VspKdTreeInterior *)node)->back);
+                        tstack.push(((VspKdTreeInterior *)node)->front);
+                }
+        }
+  
+        // delete the node and all its children
+        delete sroot;
+  
+        // for(VspKdTreeNode::SRayContainer::iterator ri = newLeaf->rays.begin();
+    //      ri != newLeaf->rays.end(); ++ ri)
+        //     (*ri).ray->UnMail(2);
 
 #if DEBUG_COLLAPSE
-  cout<<"Total memory before="<<GetMemUsage()<<endl;
+        cout<<"Total memory before="<<GetMemUsage()<<endl;
 #endif
 
-  stat.nodes -= collapsedNodes - 1;
-  stat.rayRefs -= totalRayCount - rayCount;
+        stat.nodes -= collapsedNodes - 1;
+        stat.rayRefs -= totalRayCount - rayCount;
   
 #if DEBUG_COLLAPSE
-  cout<<"collapsed nodes"<<collapsedNodes<<endl;
-  cout<<"collapsed rays"<<totalRayCount - rayCount<<endl;
-  cout<<"Total memory after="<<GetMemUsage()<<endl;
-  cout<<"================================"<<endl;
+        cout << "collapsed nodes" << collapsedNodes << endl;
+        cout << "collapsed rays" << totalRayCount - rayCount << endl;
+        cout << "Total memory after=" << GetMemUsage() << endl;
+        cout << "================================" << endl;
 #endif
 
         //  tstat.collapsedNodes += collapsedNodes;
         //  tstat.collapsedRays += totalRayCount - rayCount;
-    
-  return totalRayCount - rayCount;
-}
-
-
-int
-VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const
+    return totalRayCount - rayCount;
+}
+
+
+int VspKdTree::GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const
 {
         stack<VspKdTreeNode *> tstack;
-  tstack.push(root);
+        tstack.push(root);
 
         Intersectable::NewMail();
         int pvsSize = 0;
         
-  while (!tstack.empty()) {
-    VspKdTreeNode *node = tstack.top();
-    tstack.pop();
+        while (!tstack.empty()) 
+        {
+                VspKdTreeNode *node = tstack.top();
+                tstack.pop();
     
- 
-    if (node->IsLeaf()) {
+          if (node->IsLeaf()) 
+                {
                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
-                        for(VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
-                                        ri != leaf->rays.end();
-                                        ri++)
-                                if ((*ri).mRay->IsActive()) {
+                        for (VspKdTreeNode::RayInfoContainer::iterator ri = leaf->rays.begin();
+                                ri != leaf->rays.end(); ++ ri)
+                        {
+                                if ((*ri).mRay->IsActive()) 
+                                {
                                         Intersectable *object;
 #if BIDIRECTIONAL_RAY
                                         object = (*ri).mRay->mOriginObject;
-                                        if (object && !object->Mailed()) {
-                                                pvsSize++;
+                                        
+                                        if (object && !object->Mailed()) 
+                                        {
+                                                ++ pvsSize;
                                                 object->Mail();
                                         }
 #endif
                                         object = (*ri).mRay->mTerminationObject;
-                                        if (object && !object->Mailed()) {
-                                                pvsSize++;
+                                        if (object && !object->Mailed()) 
+                                        {
+                                                ++ pvsSize;
                                                 object->Mail();
                                         }
                                 }
-                } else {
+                        } 
+                }
+                else 
+                {
                         VspKdTreeInterior *in = (VspKdTreeInterior *)node;
-                        if (in->axis < 3) {
-                                if (box.Max(in->axis) >= in->position )
+        
+                        if (in->axis < 3) 
+                        {
+                                if (box.Max(in->axis) >= in->position)
                                         tstack.push(in->front);
                                 
-                                if (box.Min(in->axis) <= in->position )
+                                if (box.Min(in->axis) <= in->position)
                                         tstack.push(in->back);
-                        } else {
+                        } 
+                        else 
+                        {
                                 // both nodes for directional splits
                                 tstack.push(in->front);
@@ -1378 +1372 @@
                 }
         }
+
         return pvsSize;
 }
 
-void
-VspKdTree::GetRayContributionStatistics(
-                                                                                                                                                        float &minRayContribution,
-                                                                                                                                                        float &maxRayContribution,
-                                                                                                                                                        float &avgRayContribution
-                                                                                                                                                        )
+void VspKdTree::GetRayContributionStatistics(float &minRayContribution,
+                                                                                         float &maxRayContribution,
+                                                                                         float &avgRayContribution)
 {
         stack<VspKdTreeNode *> tstack;
-  tstack.push(root);
+        tstack.push(root);
         
         minRayContribution = 1.0f;
         maxRayContribution = 0.0f;
+
         float sumRayContribution = 0.0f;
         int leaves = 0;
 
-  while (!tstack.empty()) {
-    VspKdTreeNode *node = tstack.top();
-    tstack.pop();
-                
-    if (node->IsLeaf()) {
+        while (!tstack.empty()) 
+        {
+                VspKdTreeNode *node = tstack.top();
+                tstack.pop();
+                if (node->IsLeaf()) 
+                {
                         leaves++;
                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
                         float c = leaf->GetAvgRayContribution();
+
                         if (c > maxRayContribution)
                                 maxRayContribution = c;
@@ -1410 +1405 @@
                         sumRayContribution += c;
                         
-                } else {
+                } 
+                else {
                         VspKdTreeInterior *in = (VspKdTreeInterior *)node;
                         // both nodes for directional splits
@@ -1424 +1420 @@
 
 
-int
-VspKdTree::GenerateRays(const float ratioPerLeaf,
-                                                                                        SimpleRayContainer &rays)
+int VspKdTree::GenerateRays(const float ratioPerLeaf,
+                                                        SimpleRayContainer &rays)
 {
         stack<VspKdTreeNode *> tstack;
-  tstack.push(root);
-        
-  while (!tstack.empty()) {
-    VspKdTreeNode *node = tstack.top();
-    tstack.pop();
-                
-    if (node->IsLeaf()) {
+        tstack.push(root);
+        
+        while (!tstack.empty()) 
+        {
+                VspKdTreeNode *node = tstack.top();
+                tstack.pop();
+                
+                if (node->IsLeaf()) 
+                {
                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
                         float c = leaf->GetAvgRayContribution();
@@ -1441 +1438 @@
                         //                      cout<<num<<" ";
 
-                        for (int i=0; i < num; i++) {
+                        for (int i=0; i < num; i++) 
+                        {
                                 Vector3 origin = GetBBox(leaf).GetRandomPoint();
                                 Vector3 dirVector = GetDirBBox(leaf).GetRandomPoint();
@@ -1449 +1447 @@
                         }
                         
-                } else {
+                } 
+                else 
+                {
                         VspKdTreeInterior *in = (VspKdTreeInterior *)node;
                         // both nodes for directional splits
@@ -1461 +1461 @@
 
 
-float
-VspKdTree::GetAvgPvsSize()
+float VspKdTree::GetAvgPvsSize()
 {
         stack<VspKdTreeNode *> tstack;
-  tstack.push(root);
+        tstack.push(root);
 
         int sumPvs = 0;
         int leaves = 0;
-  while (!tstack.empty()) {
-    VspKdTreeNode *node = tstack.top();
-    tstack.pop();
-                
-    if (node->IsLeaf()) {
+        
+        while (!tstack.empty()) 
+        {
+                VspKdTreeNode *node = tstack.top();
+                tstack.pop();
+                
+                if (node->IsLeaf()) 
+                {
                         VspKdTreeLeaf *leaf = (VspKdTreeLeaf *)node;
                         // update pvs size
@@ -1479 +1481 @@
                         sumPvs += leaf->GetPvsSize();
                         leaves++;
-                } else {
+                } 
+                else 
+                {
                         VspKdTreeInterior *in = (VspKdTreeInterior *)node;
                         // both nodes for directional splits
@@ -1487 +1491 @@
         }
 
-
-        return sumPvs/(float)leaves;
-}
+        return sumPvs / (float)leaves;
+}

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -374 +374 @@
 // KD-tree node - leaf node
 // --------------------------------------------------------------
-class VspKdTreeLeaf :
-  public VspKdTreeNode
+class VspKdTreeLeaf : public VspKdTreeNode
 {
 private:
         int mPvsSize;
 public:
-  static int mailID;
-  int mailbox;
-  
-  RayInfoContainer rays;
+        static int mailID;
+        int mailbox;
+  
+        RayInfoContainer rays;
         bool mValidPvs;
         
-  VspKdTreeLeaf(VspKdTreeInterior *p,
-                                                        const int nRays
-                                                        ):VspKdTreeNode(p), rays(), mPvsSize(0), mValidPvs(false) {
-    rays.reserve(nRays);
-  }
-  
-  virtual ~VspKdTreeLeaf() { }
-
-  virtual int Type() const  { return ELeaf; }
-
-  virtual void Print(ostream &s) const {
-    s<<endl<<"L: r="<<rays.size()<<endl;
-  };
-  
-  void AddRay(const RayInfo &data) {
+        VspKdTreeLeaf(VspKdTreeInterior *p,     const int nRays):
+        VspKdTreeNode(p), rays(), mPvsSize(0), mValidPvs(false) 
+        {
+                rays.reserve(nRays);
+        }
+        
+        virtual ~VspKdTreeLeaf() { }
+
+        virtual int Type() const  
+        { 
+                return ELeaf; 
+        }
+
+        virtual void Print(ostream &s) const 
+        {
+                s << endl << "L: r = " << rays.size() << endl;
+        };
+  
+        void AddRay(const RayInfo &data) 
+        {
                 mValidPvs = false;
-    rays.push_back(data);
-    data.mRay->Ref();
-  }
-        
-        int GetPvsSize() const {
+                rays.push_back(data);
+                data.mRay->Ref();
+        }
+        
+        int GetPvsSize() const 
+        {
                 return mPvsSize;
         }
-        void SetPvsSize(const int s) {
+        void SetPvsSize(const int s) 
+        {
                 mPvsSize = s;
         }
 
-        void
-        UpdatePvsSize();
-
-  void Mail() { mailbox = mailID; }
-  static void NewMail() { mailID++; }
-  bool Mailed() const { return mailbox == mailID; }
-  
-  bool Mailed(const int mail) {
-    return mailbox >= mailID + mail;
-  }
-
-        float GetAvgRayContribution() const {
+        void UpdatePvsSize();
+
+        void Mail() 
+        { 
+                mailbox = mailID; 
+        }
+  
+        static void NewMail() 
+        { 
+                ++ mailID; 
+        }
+  
+        bool Mailed() const 
+        { 
+                return mailbox == mailID; 
+        }
+  
+        bool Mailed(const int mail) 
+        {
+                return mailbox >= mailID + mail;
+        }
+
+        float GetAvgRayContribution() const 
+        {
                 return GetPvsSize()/((float)rays.size() + Limits::Small);
         }
 
-        float GetSqrRayContribution() const {
+        float GetSqrRayContribution() const 
+        {
                 return sqr(GetPvsSize()/((float)rays.size() + Limits::Small));
         }
@@ -435 +454 @@
 
 // Inline functions
-inline
-VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p):
-  parent(p), axis(-1), depth(p ? p->depth + 1 : 0) {}
+inline VspKdTreeNode::VspKdTreeNode(VspKdTreeInterior *p):
+parent(p), axis(-1), depth(p ? p->depth + 1 : 0) 
+{}
 
 
@@ -446 +465 @@
 class VspKdTree
 {
-  struct TraversalData
-  {  
-    VspKdTreeNode *node;
-    AxisAlignedBox3 bbox;
-    int depth;
-    float priority;
+        struct TraversalData
+        {  
+                VspKdTreeNode *node;
+                AxisAlignedBox3 bbox;
+                int depth;
+                float priority;
+        
+                TraversalData() {}
+
+                TraversalData(VspKdTreeNode *n, const float p):
+                node(n), priority(p)
+                {}
+
+                TraversalData(VspKdTreeNode *n, const AxisAlignedBox3 &b, const int d):
+                node(n), bbox(b), depth(d) {}
     
-    TraversalData() {}
-
-    TraversalData(VspKdTreeNode *n, const float p):
-      node(n), priority(p)
-    {}
-
-    TraversalData(VspKdTreeNode *n,
-                   const AxisAlignedBox3 &b,
-                   const int d):
-      node(n), bbox(b), depth(d) {}
+                // comparator for the 
+                struct less_priority : public binary_function<const TraversalData, const TraversalData, bool> 
+                {
+                        bool operator()(const TraversalData a, const TraversalData b) 
+                        {
+                                return a.priority < b.priority;
+                        }
+                };
+
+                //    ~TraversalData() {}
+                //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
     
-                
-    // comparator for the 
-    struct less_priority : public
-    binary_function<const TraversalData, const TraversalData, bool> {
-                        
-      bool operator()(const TraversalData a, const TraversalData b) {
-                                return a.priority < b.priority;
-      }
-      
-    };
-
-    //    ~TraversalData() {}
-    //    TraversalData(const TraversalData &s):node(s.node), bbox(s.bbox), depth(s.depth) {}
-    
-    friend bool operator<(const TraversalData &a,
-                                                                                                        const TraversalData &b) {
-      //      return a.node->queries.size() < b.node->queries.size();
-      VspKdTreeLeaf *leafa = (VspKdTreeLeaf *) a.node;
-      VspKdTreeLeaf *leafb = (VspKdTreeLeaf *) b.node;
+                friend bool operator<(const TraversalData &a, const TraversalData &b) 
+                {
+                        // return a.node->queries.size() < b.node->queries.size();
+                        VspKdTreeLeaf *leafa = (VspKdTreeLeaf *) a.node;
+                        VspKdTreeLeaf *leafb = (VspKdTreeLeaf *) b.node;
 #if 0
                         return
@@ -503 +518 @@
 #if 0
                         return
-                                leafa->GetPvsSize()/(leafa->rays.size()+1)
+                                leafa->GetPvsSize() / (float)(leafa->rays.size() + 1)
                                 >
-                                leafb->GetPvsSize()/(leafb->rays.size()+1);
+                                leafb->GetPvsSize() / (float)(leafb->rays.size() + 1);
 #endif
 #if 0
                         return
-                                leafa->GetPvsSize()*leafa->rays.size()
+                                leafa->GetPvsSize() * (float)leafa->rays.size()
                                 <
-                                leafb->GetPvsSize()*leafb->rays.size();
+                                leafb->GetPvsSize() * (float)leafb->rays.size();
 #endif
     }
@@ -518 +533 @@
   // simplified data for ray traversal only...
 
-  struct RayTraversalData {
-    
-    VspKdTreeNode::RayInfo rayData;
-    VspKdTreeNode *node;
-    
-    RayTraversalData() {}
-    RayTraversalData(VspKdTreeNode *n,
-                                                                                 const VspKdTreeNode::RayInfo &data):
-      rayData(data), node(n) {}
+  struct RayTraversalData 
+  {
+          VspKdTreeNode::RayInfo rayData;
+          VspKdTreeNode *node;
+      
+          RayTraversalData() {}
+          
+          RayTraversalData(VspKdTreeNode *n, const VspKdTreeNode::RayInfo &data):
+          rayData(data), node(n) {}
   };
         
 public:
-  /////////////////////////////
-  // The core pointer
-  VspKdTreeNode *root;
-  
-  /////////////////////////////
-  // Basic properties
-
-  // total number of nodes of the tree
-  int nodes;
-  // axis aligned bounding box of the scene
-  AxisAlignedBox3 bbox;
-
-  // axis aligned bounding box of directions
-  AxisAlignedBox3 dirBBox;
-  
-  /////////////////////////////
-  // Construction parameters
-
-  // epsilon used for the construction
-  float epsilon;
-
-  // ratio between traversal and intersection costs
-  float ct_div_ci;
-  // max depth of the tree
-  int termMaxDepth;
-  // minimal ratio of the volume of the cell and the query volume
-  float termMinSize;
+        
+        /////////////////////////////
+        // The core pointer
+        VspKdTreeNode *root;
+  
+        /////////////////////////////
+        // Basic properties
+
+        // total number of nodes of the tree
+        int nodes;
+        
+        // axis aligned bounding box of the scene
+        AxisAlignedBox3 bbox;
+
+        // axis aligned bounding box of directions
+        AxisAlignedBox3 dirBBox;
+  
+        /////////////////////////////
+        // Construction parameters
+
+        // epsilon used for the construction
+        float epsilon;
+
+        // ratio between traversal and intersection costs
+        float ct_div_ci;
+        
+        // max depth of the tree
+        int termMaxDepth;
+        // minimal ratio of the volume of the cell and the query volume
+        float termMinSize;
 
         // minimal pvs per node to still get subdivided
-  int termMinPvs;
+        int termMinPvs;
 
         // minimal ray number per node to still get subdivided
-  int termMinRays;
-        
-  // maximal cost ration to subdivide a node
-  float termMaxCostRatio;
+        int termMinRays;
+        
+        // maximal cost ration to subdivide a node
+        float termMaxCostRatio;
         
         // maximal contribution per ray to subdivide the node
         float termMaxRayContribution;
 
-        
-  // randomized construction
-  bool randomize;
-
-  // type of the splitting to use fo rthe tree construction
-  enum {ESplitRegular, ESplitHeuristic };
-  int splitType;
-        
-  // maximal size of the box on which the refdir splitting can be performed
-  // (relative to the scene bbox
-  float refDirBoxMaxSize;
-  
-  // maximum alovable memory in MB
-  float maxTotalMemory;
-
-  // maximum alovable memory for static kd tree in MB
-  float maxStaticMemory;
-
-  // this is used during the construction depending
-  // on the type of the tree and queries...
-  float maxMemory;
-
-
-  // minimal acess time for collapse
-  int accessTimeThreshold;
+        // randomized construction
+        bool randomize;
+
+        // type of the splitting to use for the tree construction
+        enum {ESplitRegular, ESplitHeuristic };
+        int splitType;
+        
+        // maximal size of the box on which the refdir splitting can be performed
+        // (relative to the scene bbox
+        float refDirBoxMaxSize;
+  
+        // maximum alovable memory in MB
+        float maxTotalMemory;
+
+        // maximum alovable memory for static kd tree in MB
+        float maxStaticMemory;
+
+        // this is used during the construction depending
+        // on the type of the tree and queries...
+        float maxMemory;
+
+        // minimal acess time for collapse
+        int accessTimeThreshold;
 
         // minimal depth at which to perform collapse
-  int minCollapseDepth;
-
-  
-  // reusable array of split candidates
-  vector<SortableEntry> *splitCandidates;
-  /////////////////////////////
-
-  VspKdStatistics stat;
-        
-  
-  VspKdTree();
-  virtual ~VspKdTree();
-
-  virtual void
-  Construct(
-                                                VssRayContainer &rays,
-                                                AxisAlignedBox3 *forcedBoundingBox = NULL
-                                                );
-        
-  // incemental construction
-  virtual void UpdateRays(VssRayContainer &remove,
-                                                                                                        VssRayContainer &add
-                                                                                                        );
-
-        virtual void AddRays(
-                                                                                         VssRayContainer &add
-                                                                                         )
+        int minCollapseDepth;
+        
+        // reusable array of split candidates
+        vector<SortableEntry> *splitCandidates;
+        
+        /////////////////////////////
+        VspKdStatistics stat;
+        
+        VspKdTree();
+        virtual ~VspKdTree();
+
+        virtual void Construct(VssRayContainer &rays,
+                                                   AxisAlignedBox3 *forcedBoundingBox = NULL);
+        
+        // incemental construction
+        virtual void UpdateRays(VssRayContainer &remove, VssRayContainer &add);
+
+        virtual void AddRays(VssRayContainer &add)
         {
                 VssRayContainer remove;
@@ -629 +636 @@
         }
 
-  
-        
-  VspKdTreeNode *
-  Locate(const Vector3 &v);
-        
-  VspKdTreeNode *
-  SubdivideNode(VspKdTreeLeaf *leaf,
-                                                                const AxisAlignedBox3 &box,
-                                                                AxisAlignedBox3 &backBox,
-                                                                AxisAlignedBox3 &frontBox
-                                                                );
-        
-  VspKdTreeNode *
-  Subdivide(const TraversalData &tdata);
-        
-  int
-  SelectPlane(VspKdTreeLeaf *leaf,
-                                                        const AxisAlignedBox3 &box,
-                                                        float &position,
-                                                        int &raysBack,
-                                                        int &raysFront,
-                                                        int &pvsBack,
-                                                        int &pvsFront
-                                                        );
-
-  void
-  SortSplitCandidates(
-                                                                                        VspKdTreeLeaf *node,
-                                                                                        const int axis
-                                                                                        );
-        
-  
-  // return memory usage in MB
-  float GetMemUsage() const {
-    return 
-      (sizeof(VspKdTree) +
-       stat.Leaves()*sizeof(VspKdTreeLeaf) +
-       stat.Interior()*sizeof(VspKdTreeInterior) +
-       stat.rayRefs*sizeof(VspKdTreeNode::RayInfo))/(1024.0f*1024.0f);
-  }
-        
-  float GetRayMemUsage() const {
-    return 
-      stat.rays*(sizeof(VssRay))/(1024.0f*1024.0f);
-  }
-  
-        float
-        BestCostRatioHeuristic(
-                                                                                                 VspKdTreeLeaf *node,
-                                                                                                 int &axis,
-                                                                                                 float &position,
-                                                                                                 int &raysBack,
-                                                                                                 int &raysFront,
-                                                                                                 int &pvsBack,
-                                                                                                 int &pvsFront
-                                                                                                 );
-
-        float
-        BestCostRatioRegular(
-                                                                                         VspKdTreeLeaf *node,
-                                                                                         int &axis,
-                                                                                         float &position,
-                                                                                         int &raysBack,
-                                                                                         int &raysFront,
-                                                                                         int &pvsBack,
-                                                                                         int &pvsFront
-
-                                                                                         );
-        
-        float
-        EvalCostRatio(
-                                                                VspKdTreeLeaf *node,
-                                                                const int axis,
-                                                                const float position,
-                                                                int &raysBack,
-                                                                int &raysFront,
-                                                                int &pvsBack,
-                                                                int &pvsFront
-                                                                );
-
-  AxisAlignedBox3 GetBBox(const VspKdTreeNode *node) {
-    if (node->parent == NULL)
-      return bbox;
-
-    if (!node->IsLeaf())
-      return ((VspKdTreeInterior *)node)->bbox;
-
-    if (node->parent->axis >= 3)
-      return node->parent->bbox;
+        VspKdTreeNode *Locate(const Vector3 &v);
+        
+        VspKdTreeNode *SubdivideNode(VspKdTreeLeaf *leaf,
+                                                                 const AxisAlignedBox3 &box,
+                                                                 AxisAlignedBox3 &backBox,
+                                                                 AxisAlignedBox3 &frontBox);
+        
+        VspKdTreeNode *Subdivide(const TraversalData &tdata);
+        
+        int SelectPlane(VspKdTreeLeaf *leaf,
+                                        const AxisAlignedBox3 &box,
+                                        float &position,
+                                        int &raysBack,
+                                        int &raysFront,
+                                        int &pvsBack,
+                                        int &pvsFront);
+
+        void SortSplitCandidates(VspKdTreeLeaf *node,
+                                                         const int axis);
+        
+  
+        // return memory usage in MB
+        float GetMemUsage() const 
+        {
+                return 
+                        (sizeof(VspKdTree) + 
+                         stat.Leaves() * sizeof(VspKdTreeLeaf) +
+                         stat.Interior() * sizeof(VspKdTreeInterior) +
+                         stat.rayRefs * sizeof(VspKdTreeNode::RayInfo)) / (1024.0f*1024.0f);
+        }
+        
+        float GetRayMemUsage() const 
+        {
+                return stat.rays * (sizeof(VssRay))/(1024.0f * 1024.0f);
+        }
+  
+        float BestCostRatioHeuristic(VspKdTreeLeaf *node,
+                                                                 int &axis,
+                                                                 float &position,
+                                                                 int &raysBack,
+                                                                 int &raysFront,
+                                                                 int &pvsBack,
+                                                                 int &pvsFront);
+
+        float BestCostRatioRegular(VspKdTreeLeaf *node, 
+                                                           int &axis,
+                                                           float &position,
+                                                           int &raysBack,
+                                                           int &raysFront,
+                                                           int &pvsBack,
+                                                           int &pvsFront);
+        
+        float EvalCostRatio(VspKdTreeLeaf *node,
+                                                const int axis,
+                                                const float position,
+                                                int &raysBack,
+                                                int &raysFront,
+                                                int &pvsBack,
+                                                int &pvsFront);
+
+        AxisAlignedBox3 GetBBox(const VspKdTreeNode *node) 
+        {
+                if (node->parent == NULL)
+                        return bbox;
+
+                if (!node->IsLeaf())
+                        return ((VspKdTreeInterior *)node)->bbox;
+
+                if (node->parent->axis >= 3)
+                        return node->parent->bbox;
       
-    AxisAlignedBox3 box(node->parent->bbox);
-    if (node->parent->front == node)
-      box.SetMin(node->parent->axis, node->parent->position);
-    else
-      box.SetMax(node->parent->axis, node->parent->position);
-    return box;
-  }
-
-  AxisAlignedBox3 GetDirBBox(const VspKdTreeNode *node) {
-
-    if (node->parent == NULL)
-      return dirBBox;
+                AxisAlignedBox3 box(node->parent->bbox);
+                if (node->parent->front == node)
+                        box.SetMin(node->parent->axis, node->parent->position);
+                else
+                        box.SetMax(node->parent->axis, node->parent->position);
+                return box;
+        }
+
+        AxisAlignedBox3 GetDirBBox(const VspKdTreeNode *node) 
+        {
+                if (node->parent == NULL)
+                        return dirBBox;
+                if (!node->IsLeaf())
+                        return ((VspKdTreeInterior *)node)->dirBBox;
+                if (node->parent->axis < 3)
+                        return node->parent->dirBBox;
     
-    if (!node->IsLeaf() )
-      return ((VspKdTreeInterior *)node)->dirBBox;
-
-    if (node->parent->axis < 3)
-      return node->parent->dirBBox;
-    
-    AxisAlignedBox3 dBBox(node->parent->dirBBox);
-
-    if (node->parent->front == node)
-      dBBox.SetMin(node->parent->axis - 3, node->parent->position);
-    else
-      dBBox.SetMax(node->parent->axis - 3, node->parent->position);
-    return dBBox;
-  }
-  
-  int
-  ReleaseMemory(const int time);
-
-  int
-  CollapseSubtree(VspKdTreeNode *node, const int time);
-
-  void
-  CountAccess(VspKdTreeInterior *node, const long time) {
-    node->accesses++;
-    node->lastAccessTime = time;
-  }
-
-  VspKdTreeNode *
-  SubdivideLeaf(
-                                                                VspKdTreeLeaf *leaf,
-                                                                const float SAThreshold
-                                                                );
-
-  void
-  RemoveRay(VssRay *ray,
-                                                vector<VspKdTreeLeaf *> *affectedLeaves,
-                                                const bool removeAllScheduledRays
-                                                );
-
-  void
-  AddRay(VssRay *ray);
-        
-  void
-  TraverseInternalNode(
-                                                                                         RayTraversalData &data,
-                                                                                         stack<RayTraversalData> &tstack);
-
-        void
-  EvaluateLeafStats(const TraversalData &data);
-
-
-        int
-        GetRootPvsSize() const {
+                AxisAlignedBox3 dBBox(node->parent->dirBBox);
+
+                if (node->parent->front == node)
+                        dBBox.SetMin(node->parent->axis - 3, node->parent->position);
+                else
+                        dBBox.SetMax(node->parent->axis - 3, node->parent->position);
+                return dBBox;
+        }
+  
+        int     ReleaseMemory(const int time);
+
+        int     CollapseSubtree(VspKdTreeNode *node, const int time);
+        
+        void CountAccess(VspKdTreeInterior *node, const long time) 
+        {
+                ++ node->accesses;
+                node->lastAccessTime = time;
+        }
+
+        VspKdTreeNode * SubdivideLeaf(VspKdTreeLeaf *leaf,
+                                                                  const float SAThreshold);
+
+        void RemoveRay(VssRay *ray,
+                                   vector<VspKdTreeLeaf *> *affectedLeaves,
+                                   const bool removeAllScheduledRays);
+
+        void AddRay(VssRay *ray);
+        
+        void TraverseInternalNode(RayTraversalData &data,
+                                                         stack<RayTraversalData> &tstack);
+
+        void EvaluateLeafStats(const TraversalData &data);
+
+
+        int     GetRootPvsSize() const 
+        {
                 return GetPvsSize(root, bbox);
         }
         
-        int
-        GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const;
-
-        void
-        GetRayContributionStatistics(
-                                                                                                                         float &minRayContribution,
-                                                                                                                         float &maxRayContribution,
-                                                                                                                         float &avgRayContribution
-                                                                                                                         );
-
-        int
-        GenerateRays(const float ratioPerLeaf,
-                                                         SimpleRayContainer &rays);
-
-        float
-        GetAvgPvsSize();
-
+        int     GetPvsSize(VspKdTreeNode *node, const AxisAlignedBox3 &box) const;
+
+        void GetRayContributionStatistics(float &minRayContribution,
+                                                                          float &maxRayContribution,
+                                                                          float &avgRayContribution);
+
+        int GenerateRays(const float ratioPerLeaf,
+                                         SimpleRayContainer &rays);
+
+        float GetAvgPvsSize();
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/VssRay.h

@@ -5 +5 @@
 using namespace std;
 #include "Vector3.h"
+#include "Ray.h"
 
 class AxisAlignedBox3;
@@ -60 +61 @@
   }
         
+        VccRay(const Ray &ray):
+  VccRay(ray.GetLoc(), ray.Extrap(ray.intersections[0].mT),  ray.intersections[0].mObject, ray.sourceObject.mObject)
+  {}
   void Precompute() {
     mFlags = 0;

trunk/VUT/GtpVisibilityPreprocessor/src/default.env

@@ -119 +119 @@
         #       input fromViewCells
         #       input fromSceneGeometry
-                samples 10000
+                samples 100000
                 sideTolerance 0.005
         }