Changeset 1989

Timestamp:

01/18/07 10:25:29 (17 years ago)

Author:

bittner

Message:

mutation updates

Location:

GTP/trunk/Lib/Vis/Preprocessing/src

Files:

• KdTree.cpp (modified) (6 diffs)
• KdTree.h (modified) (2 diffs)
• Makefile (modified) (2 diffs)
• Ray.h (modified) (1 diff)
• RayCaster.cpp (modified) (3 diffs)
• SamplingStrategy.cpp (modified) (3 diffs)
• SamplingStrategy.h (modified) (1 diff)
• ViewCellsManager.cpp (modified) (3 diffs)
• VssRay.h (modified) (1 diff)
• default.env (modified) (1 diff)
• preprocessor.pro (modified) (1 diff)
• run (modified) (1 diff)

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

@@ -9 +9 @@
 
 
+// $$JB HACK
+#define KD_PVS_AREA (1e-5f)
 
 namespace GtpVisibilityPreprocessor {
@@ -106 +108 @@
   delete splitCandidates;
 
+  float area = GetBox().SurfaceArea()*KD_PVS_AREA;
+
+  SetPvsTerminationNodes(area);
+  
   return true;
 }
@@ -828 +834 @@
 void
 KdTree::CollectKdObjects(const AxisAlignedBox3 &box,
-                                                 ObjectContainer &objects,
-                                                 const float maxArea
+                                                 ObjectContainer &objects
                                                  )
 {
@@ -839 +844 @@
     KdNode *node = nodeStack.top();
     nodeStack.pop();
-        if (node->IsLeaf() || (GetSurfaceArea(node) <= maxArea) ) {
+        if (node->IsLeaf() || node->mPvsTermination == 1)  {
           Intersectable *object = GetOrCreateKdIntersectable(node);
           if (!object->Mailed()) {
@@ -1425 +1430 @@
         }
 
+        float area = GetBox().SurfaceArea()*KD_PVS_AREA;
+        
+        SetPvsTerminationNodes(area);
+
         Debug << mStat << endl;
 
@@ -1444 +1453 @@
 
   return node->mIntersectable;
+}
+
+
+void
+KdTree::SetPvsTerminationNodes(
+                                                           const float maxArea)
+{
+  stack<KdNode *> nodeStack;
+  
+  nodeStack.push(mRoot);
+
+  while (!nodeStack.empty()) {
+    KdNode *node = nodeStack.top();
+        nodeStack.pop();
+
+        node->mPvsTermination = 0;
+        if (node->IsLeaf() || (GetSurfaceArea(node) <= maxArea) ) {
+          node->mPvsTermination = 1;
+          // create dummy kd intersectable
+          Intersectable *object = GetOrCreateKdIntersectable(node);
+        } else {
+          KdInterior *interior = (KdInterior *)node;
+          nodeStack.push(interior->mFront);
+          nodeStack.push(interior->mBack);
+    }
+  }
+}
+
+KdNode *
+KdTree::GetPvsNode(const Vector3 &point) const
+{
+  KdNode *node = mRoot;
+  
+  while (node->mPvsTermination == 0 ) {
+        KdInterior *inter = (KdInterior *)node;
+        if (point[inter->mAxis] < inter->mPosition)
+          node = inter->mBack;
+        else
+          node = inter->mFront;
+  }
+  
+  return node;
 }
 

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

@@ -133 +133 @@
       but allows various optimizations of tree traversal algorithms */
   KdInterior *mParent;
-  int mDepth;
+  short mDepth;
+  short mPvsTermination;
 };
 
@@ -344 +345 @@
   KdIntersectable *GetOrCreateKdIntersectable(KdNode *node);
 
+
+  void
+  SetPvsTerminationNodes(
+                                                 const float maxArea);
+  
+  KdNode *
+  GetPvsNode(const Vector3 &point) const;
+  
+
   void
   CollectKdObjects(const AxisAlignedBox3 &box,
-                                   ObjectContainer &objects,
-                                   const float maxArea
+                                   ObjectContainer &objects
                                    );
 

GTP/trunk/Lib/Vis/Preprocessing/src/Makefile

@@ -1 +1 @@
 #############################################################################
 # Makefile for building: preprocessor
-# Generated by qmake (2.00a) (Qt 4.1.2) on: po 15. I 21:59:19 2007
+# Generated by qmake (2.00a) (Qt 4.1.2) on: st 17. I 15:41:45 2007
 # Project:  preprocessor.pro
 # Template: app
@@ -63 +63 @@
         $(MAKE) -f $(MAKEFILE).Debug uninstall
 
-Makefile: preprocessor.pro  C:/Qt/4.1.2/mkspecs/win32-msvc.net\qmake.conf C:/Qt/4.1.2/mkspecs/qconfig.pri \
+Makefile: preprocessor.pro  C:/Qt/4.1.2/mkspecs/win32-msvc2005\qmake.conf C:/Qt/4.1.2/mkspecs/qconfig.pri \
                 C:\Qt\4.1.2\mkspecs\features\qt_config.prf \
                 C:\Qt\4.1.2\mkspecs\features\exclusive_builds.prf \

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

@@ -321 +321 @@
   short mType;
   short mDistribution;
+  // generator Id -> relative to the generating distribution!
+  int mGeneratorId;
   float mPdf;
   

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

@@ -282 +282 @@
                                                                         hitA.mObject,
                                                                         mPreprocessor.mPass,
-                                                                        simpleRay.mPdf);
+                                                                        simpleRay.mPdf
+                                                                        );
 
                 if (validA)
@@ -288 +289 @@
 
                 vssRay->mDistribution = simpleRay.mDistribution;
+                vssRay->mGeneratorId = simpleRay.mGeneratorId;
+
                 vssRays.push_back(vssRay);
                 ++ hits;
@@ -311 +314 @@
 
                 vssRay->mDistribution = simpleRay.mDistribution;
+                vssRay->mGeneratorId = simpleRay.mGeneratorId;
                 vssRays.push_back(vssRay);
                 ++ hits;

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

@@ -6 +6 @@
 #include "AxisAlignedBox3.h"
 #include "RssTree.h"
-#include "Vector2.h"
-#include "RndGauss.h"
+#include "Mutation.h"
 
 namespace GtpVisibilityPreprocessor {
-
-#define MUTATION_USE_CDF 0
-
 
 //HaltonSequence SamplingStrategy::sHalton;
@@ -48 +44 @@
         // tmp changed matt. Q: should one rejected sample 
         // terminate the whole method?
-        if (0)
-        {
-                for (; i < number; i++) {
-                        if (!GenerateSample(ray))
-                                return i;
-                        rays.push_back(ray);
-                }
-        }
-        else
-        {
-                for (; i < number; i++) 
-                {
-                        int j = 0;
-                        bool sampleGenerated = false;
-
-                        for (j = 0; !sampleGenerated && (j < maxTries); ++ j)
-                        {
-                                sampleGenerated = GenerateSample(ray);
-
-                                if (sampleGenerated)
-                                {               
-                                        ++ samples;
-                                        rays.push_back(ray);
-                                }
-                        }
-                }
-        }
-        
+        for (; i < number; i++) 
+          {
+                int j = 0;
+                bool sampleGenerated = false;
+                
+                for (j = 0; !sampleGenerated && (j < maxTries); ++ j)
+                  {
+                        sampleGenerated = GenerateSample(ray);
+                        
+                        if (sampleGenerated)
+                          {             
+                                ++ samples;
+                                rays.push_back(ray);
+                          }
+                  }
+          }
+
+
         return samples;
 }
@@ -686 +672 @@
 }
 
-void
-MutationBasedDistribution::Update(VssRayContainer &vssRays)
-{
-  //  for (int i=0; i < mRays.size(); i++)
-  //    cout<<mRays[i].mSamples<<" ";
-  //  cout<<endl;
-  cerr<<"Muattion update..."<<endl;
-  cerr<<"rays = "<<mRays.size()<<endl;
-  if (mRays.size()) {
-        cerr<<"Oversampling factors = "<<
-          GetEntry(0).mSamples<<" "<<
-          GetEntry(1).mSamples<<" "<<
-          GetEntry(2).mSamples<<" "<<
-          GetEntry(3).mSamples<<" "<<
-          GetEntry(4).mSamples<<" "<<
-          GetEntry(5).mSamples<<" ... "<<
-          GetEntry(mRays.size()-6).mSamples<<" "<<
-          GetEntry(mRays.size()-5).mSamples<<" "<<
-          GetEntry(mRays.size()-4).mSamples<<" "<<
-          GetEntry(mRays.size()-3).mSamples<<" "<<
-          GetEntry(mRays.size()-2).mSamples<<" "<<
-          GetEntry(mRays.size()-1).mSamples<<endl;
-  }
-  int contributingRays = 0;
-  for (int i=0; i < vssRays.size(); i++) {
-        if (vssRays[i]->mPvsContribution) {
-          contributingRays++;
-          if (mRays.size() < mMaxRays) {
-                VssRay *newRay = new VssRay(*vssRays[i]);
-                // add this ray
-                newRay->Ref();
-                mRays.push_back(RayEntry(newRay));
-          } else {
-                // unref the old ray
-                *mRays[mBufferStart].mRay = *vssRays[i];
-                mRays[mBufferStart].mSamples = 0;
-                //              mRays[mBufferStart] = RayEntry(newRay);
-                mBufferStart++;
-                if (mBufferStart >= mMaxRays)
-                  mBufferStart = 0;
-          }
-        }
-  }
-  
-  float pContributingRays = contributingRays/(float)vssRays.size();
-  float importance = 1.0f; //sqr(1.0f/(pContributingRays + 1e-5));
-  // set this values for last contributingRays
-  int index = mBufferStart - 1;
-  
-  for (int i=0; i < contributingRays; i++, index--) {
-        if (index < 0)
-          index = mRays.size()-1;
-        mRays[index].mImportance = importance;
-  }
-
-#if MUTATION_USE_CDF
-  // compute cdf
-  mRays[0].mCdf = mRays[0].mImportance/(mRays[0].mSamples+1);
-  for (int i=1; i < mRays.size(); i++) 
-        mRays[i].mCdf = mRays[i-1].mCdf + mRays[i].mImportance/(mRays[i].mSamples+1);
-  
-  float scale = 1.0f/mRays[i-1].mCdf;
-  for (i=0; i < mRays.size(); i++) {
-        mRays[i].mCdf *= scale;
-  }
-#endif
-  
-  cout<<"Importance = "<<
-        GetEntry(0).mImportance<<" "<<
-        GetEntry(mRays.size()-1).mImportance<<endl;
-  
-  cerr<<"Mutation update done."<<endl;
-}
-
-
-Vector3
-MutationBasedDistribution::ComputeOriginMutation(const VssRay &ray,
-                                                                                                 const Vector3 &U,
-                                                                                                 const Vector3 &V,
-                                                                                                 const Vector2 vr2,
-                                                                                                 const float radius
-                                                                                                 )
-{
-#if 0
-  Vector3 v;
-  if (d.DrivingAxis() == 0)
-        v = Vector3(0, r[0]-0.5f, r[1]-0.5f);
-  else
-        if (d.DrivingAxis() == 1)
-          v = Vector3(r[0]-0.5f, 0, r[1]-0.5f);
-        else
-          v = Vector3(r[0]-0.5f, r[1]-0.5f, 0);
-  return v*(2*radius);
-#endif
-#if 0
-  return (U*(r[0] - 0.5f) + V*(r[1] - 0.5f))*(2*radius);
-#endif
-
-
-  // Output random variable
-  Vector2 gaussvec2; 
-  
-  // Here we apply transform to gaussian, so 2D bivariate
-  // normal distribution
-  //  float sigma = ComputeSigmaFromRadius(radius);
-  float sigma = radius;
-  GaussianOn2D(vr2,
-                           sigma, // input
-                           gaussvec2);  // output
-
-        
-    // Here we tranform the point correctly to 3D space using base
-    // vectors of the 3D space defined by the direction
-    Vector3 shift = gaussvec2.xx * U + gaussvec2.yy * V;
-        
-        //      cout<<shift<<endl;
-        return shift;
-}
-
-Vector3
-MutationBasedDistribution::ComputeTerminationMutation(const VssRay &ray,
-                                                                                                          const Vector3 &U,
-                                                                                                          const Vector3 &V,
-                                                                                                          const Vector2 vr2,
-                                                                                                          const float radius
-                                                                                                          )
-{
-#if 0
-  Vector3 v;
-  // mutate the termination
-  if (d.DrivingAxis() == 0)
-        v = Vector3(0, r[2]-0.5f, r[3]-0.5f);
-  else
-        if (d.DrivingAxis() == 1)
-          v = Vector3(r[2]-0.5f, 0, r[3]-0.5f);
-        else
-          v = Vector3(r[2]-0.5f, r[3]-0.5f, 0);
-  
-  //   Vector3 nv;
-  
-  //   if (Magnitude(v) > Limits::Small)
-  //    nv = Normalize(v);
-  //   else
-  //    nv = v;
-  
-  //  v = nv*size + v*size;
-
-  return v*(4.0f*radius);
-#endif
-#if 0
-  return (U*(vr2.xx - 0.5f) + V*(vr2.yy - 0.5f))*(4.0f*radius);
-#endif
-  Vector2 gaussvec2; 
-#if 1
-  float sigma = radius;
-  GaussianOn2D(vr2,
-                           sigma, // input
-                           gaussvec2);  // output
-  Vector3 shift = gaussvec2.xx * U + gaussvec2.yy * V;
-  //    cout<<shift<<endl;
-  return shift;
-#endif
-#if 0
-  // Here we estimate standard deviation (sigma) from radius
-  float sigma = 1.1f*ComputeSigmaFromRadius(radius);
-  Vector3 vr3(vr2.xx, vr2.yy, RandomValue(0,1));
-  PolarGaussianOnDisk(vr3,
-                                          sigma,
-                                          radius, // input
-                                          gaussvec2); // output
-  
-  // Here we tranform the point correctly to 3D space using base
-  // vectors of the 3D space defined by the direction
-  Vector3 shift = gaussvec2.xx * U + gaussvec2.yy * V;
-  
-  //    cout<<shift<<endl;
-  return shift;
-#endif
-}
-
-
-bool
-MutationBasedDistribution::GenerateSample(SimpleRay &sray)
-{
-  float rr[5];
-
-  if (mRays.size() == 0) {
-        // use direction based distribution
-        Vector3 origin, direction;
-        static HaltonSequence halton;
-        
-        halton.GetNext(5, rr);
-        mPreprocessor.mViewCellsManager->GetViewPoint(origin,
-                                                                                                  Vector3(rr[0], rr[1], rr[2]));
-        
-
-        direction = UniformRandomVector(rr[3], rr[4]);
-        
-        const float pdf = 1.0f;
-        sray = SimpleRay(origin, direction, MUTATION_BASED_DISTRIBUTION, pdf);
-
-        return true;
-  } 
-
-  int index;
-
-#if !MUTATION_USE_CDF
-  // get tail of the buffer
-  index = (mLastIndex+1)%mRays.size();
-  if (mRays[index].GetSamplingFactor() >
-          mRays[mLastIndex].GetSamplingFactor()) {
-        // search back for index where this is valid
-        index = (mLastIndex - 1 + mRays.size())%mRays.size();
-        for (int i=0; i < mRays.size(); i++) {
-          
-          //      if (mRays[index].mSamples > mRays[mLastIndex].mSamples)
-          //            break;
-          if (mRays[index].GetSamplingFactor() >
-                  mRays[mLastIndex].GetSamplingFactor() )
-                break;
-          index = (index - 1 + mRays.size())%mRays.size();
-        }
-        // go one step back
-        index = (index+1)%mRays.size();
-  }
-#else
-  static HaltonSequence iHalton;
-  iHalton.GetNext(1, rr);
-  //rr[0] = RandomValue(0,1);
-  // use binary search to find index with this cdf
-  int l=0, r=mRays.size()-1;
-  while(l<r) {
-        int i = (l+r)/2;
-        if (rr[0] < mRays[i].mCdf )
-          r = i;
-        else
-          l = i+1;
-  }
-  index = l;
-  //  if (rr[0] >= mRays[r].mCdf)
-  //    index = r;
-  //  else
-  //    index = l;
-        
-        
-#endif
-  //  cout<<index<<" "<<rr[0]<<" "<<mRays[index].mCdf<<" "<<mRays[(index+1)%mRays.size()].mCdf<<endl;
-  
-  VssRay *ray = mRays[index].mRay;
-  mRays[index].mSamples++;
-  mLastIndex = index;
-
-  mRays[index].mHalton.GetNext(4, rr);
-
-  // mutate the origin
-  Vector3 d = ray->GetDir();
-
-
-  AxisAlignedBox3 box = ray->mTerminationObject->GetBox();
-  float objectRadius = 0.5f*Magnitude(box.Diagonal());
-  //  cout<<objectRadius<<endl;
-  if (objectRadius < Limits::Small)
-        return false;
-  
-  // Compute right handed coordinate system from direction
-  Vector3 U, V;
-  Vector3 nd = Normalize(d);
-  nd.RightHandedBase(U, V);
-
-  Vector3 origin = ray->mOrigin;
-  Vector3 termination = ray->mTermination; //box.Center(); //ray->mTermination; //box.Center();
-
-  float radiusExtension = 1.0f;
-  //  + mRays[index].mSamples/50.0f;
-  
-  //  origin += ComputeOriginMutation(*ray, U, V, Vector2(r[0], r[1]), 0.5f*mOriginMutationSize*radiusExtension);
-  origin += ComputeOriginMutation(*ray, U, V,
-                                                                  Vector2(rr[0], rr[1]),
-                                                                  objectRadius*radiusExtension);
-  termination += ComputeTerminationMutation(*ray, U, V,
-                                                                                        Vector2(rr[2], rr[3]),
-                                                                                        objectRadius*radiusExtension);
-  
-  Vector3 direction = termination - origin;
-  
-  if (Magnitude(direction) < Limits::Small)
-        return false;
-  
-  // shift the origin a little bit
-  origin += direction*0.5f;
-  
-  direction.Normalize();
-  
-  // $$ jb the pdf is yet not correct for all sampling methods!
-  const float pdf = 1.0f;
-  
-  sray = SimpleRay(origin, direction, MUTATION_BASED_DISTRIBUTION, pdf);
-  return true;
-}
-
-MutationBasedDistribution::MutationBasedDistribution(Preprocessor &preprocessor
-                                                                                                         ) :
-  SamplingStrategy(preprocessor)
-{
-  mType = MUTATION_BASED_DISTRIBUTION;
-  mBufferStart = 0;
-  mMaxRays = 500000;
-  mRays.reserve(mMaxRays);
-  mOriginMutationSize = 10.0f;
-  mLastIndex = 0;
-  //  mOriginMutationSize = Magnitude(preprocessor.mViewCellsManager->
-  //                                                              GetViewSpaceBox().Diagonal())*1e-3;
-  
-}
 
 

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

@@ -225 +225 @@
 };
 
-class MutationBasedDistribution: public SamplingStrategy
-{
-public:
-  MutationBasedDistribution(Preprocessor &preprocessor);
-  virtual void Update(VssRayContainer &vssRays);
-
-  virtual bool RequiresRays() { return true; }
-
-private:
-  virtual bool GenerateSample(SimpleRay &ray);
-
-  struct RayEntry {
-        // halton sequence for generatin gmutations of this ray
-        VssRay *mRay;
-        int mSamples;
-        HaltonSequence mHalton;
-        float mImportance;
-        float mCdf;
-
-        float GetSamplingFactor() const { return mSamples/mImportance; }
-        RayEntry() {}
-        RayEntry(VssRay *r):mRay(r), mSamples(0), mHalton(), mImportance(1.0f) {}
-  };
-
-
-  Vector3
-  ComputeOriginMutation(const VssRay &ray,
-                                                const Vector3 &U,
-                                                const Vector3 &V,
-                                                const Vector2 vr2,
-                                                const float radius
-                                                );
-
-  Vector3
-  ComputeTerminationMutation(const VssRay &ray,
-                                                         const Vector3 &U,
-                                                         const Vector3 &V,
-                                                         const Vector2 vr2,
-                                                         const float radius
-                                                         );
-
-  RayEntry &GetEntry(const int index) {
-        return mRays[(mBufferStart+index)%mRays.size()];
-  }
-  
-  vector<RayEntry> mRays;
-  int mMaxRays;
-  float mOriginMutationSize;
-  int mBufferStart;
-  int mLastIndex;
-};
 
 class GlobalLinesDistribution: public SamplingStrategy

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

@@ -26 +26 @@
 
 
-// $$JB HACK
-#define KD_PVS_AREA (1e-5f)
 
 #define USE_RAY_LENGTH_AS_CONTRIBUTION 0
@@ -330 +328 @@
         if (mUseKdPvs)
         {
-                float area = GetPreprocessor()->mKdTree->GetBox().SurfaceArea()*KD_PVS_AREA;
-                KdNode *node = GetPreprocessor()->mKdTree->GetNode(isTermination ?
-                                                                                                                 ray.mTermination : ray.mOrigin,
-                                                                                                                 area);
-        return GetPreprocessor()->mKdTree->GetOrCreateKdIntersectable(node);
+          KdNode *node = GetPreprocessor()->mKdTree->GetPvsNode(isTermination ?
+                                                                                                                        ray.mTermination : ray.mOrigin);
+          return GetPreprocessor()->mKdTree->GetOrCreateKdIntersectable(node);
         }
         else
-        {
+          {
                 return isTermination ? ray.mTerminationObject : ray.mOriginObject;
-        }
+          }
 }
 
@@ -3061 +3057 @@
           // $$ warning collect objects takes only unmailed ones!
           if (mUseKdPvsAfterFiltering) {
-                float area = GetPreprocessor()->mKdTree->GetBox().SurfaceArea()*KD_PVS_AREA;
-                GetPreprocessor()->mKdTree->CollectKdObjects(box, objects, area);
+                GetPreprocessor()->mKdTree->CollectKdObjects(box, objects);
           } else
                 CollectObjects(box, objects);

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

@@ -32 +32 @@
 
   // Id of the generating SimpleRay
-  int mGeneratingRayId;
+  int mGeneratorId;
   
   static int mailID;

GTP/trunk/Lib/Vis/Preprocessing/src/default.env

@@ -172 +172 @@
                 maxCostRatio 0.98
                 ct_div_ci 0.5
-                maxNodes 200000
+                maxNodes 50000
 #500000 
         }

GTP/trunk/Lib/Vis/Preprocessing/src/preprocessor.pro

@@ -112 +112 @@
 Mailable.cpp \
 CombinedPreprocessor.cpp Vector2.cpp GlobalLinesRenderer.cpp \
-RenderTexture.cpp
+RenderTexture.cpp Mutation.cpp
 
 SOURCES += BoostPreprocessorThread.cpp 

GTP/trunk/Lib/Vis/Preprocessing/src/run

@@ -1 +1 @@
 #!/bin/sh
 
-COMMAND="../scripts/preprocessor.sh -preprocessor_quit_on_finish- -preprocessor_use_gl_renderer+ -preprocessor_evaluate_filter- -preprocessor_ray_cast_method=0"
+COMMAND="../scripts/preprocessor.sh -preprocessor_quit_on_finish- -preprocessor_use_gl_renderer+ -preprocessor_evaluate_filter- -preprocessor_ray_cast_method=1"
 
-#SCENE=../data/Pompeii/PompeiiTen.obj
-#VIEWCELLS=../data/Pompeii/pompeii_big-seq-viewcells.xml.gz
+SCENE=../data/Pompeii/PompeiiTen.obj
+VIEWCELLS=../data/Pompeii/pompeii_big-seq-viewcells.xml.gz
 
 #SCENE=../data/artificial/room_with_sphere.obj
 #VIEWCELLS=../data/artificial/simpleHoleViewCell.x3d
 
-SCENE=../data/soda/soda5.dat
-VIEWCELLS=../data/soda/soda5-viewcells.xml
+#SCENE=../data/soda/soda5.dat
+#VIEWCELLS=../data/soda/soda5-viewcells.xml
 
 $COMMAND -preprocessor=combined -scene_filename=$SCENE -view_cells_filename=$VIEWCELLS \