Changeset 245

Timestamp:

08/22/05 21:07:44 (19 years ago)

Author:

bittner

Message:

Merged sources with ViewCellBsp?

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• Intersectable.h (modified) (1 diff)
• KdTree.cpp (modified) (2 diffs)
• KdTree.h (modified) (1 diff)
• Makefile (modified) (8 diffs)
• Matrix4x4.cpp (modified) (2 diffs)
• Mesh.cpp (modified) (1 diff)
• MeshKdTree.cpp (modified) (1 diff)
• MutualVisibility.cpp (modified) (15 diffs)
• MutualVisibility.h (modified) (10 diffs)
• Plane3.h (modified) (1 diff)
• Ray.h (modified) (1 diff)
• Rectangle3.h (modified) (5 diffs)
• SamplingPreprocessor.cpp (modified) (7 diffs)
• SamplingPreprocessor.h (modified) (2 diffs)
• ViewCell.cpp (modified) (1 diff)
• ViewCellBsp.cpp (modified) (2 diffs)
• default.env (modified) (2 diffs)
• preprocessor.pro (modified) (2 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/Intersectable.h

@@ -20 +20 @@
   static void NewMail() { mailID++; }
   bool Mailed() const { return mailbox == mailID; }
-  
+  int IncMail() { return ++mailbox - mailID; }
+
   virtual AxisAlignedBox3 GetBox() = 0;
   

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ -596 +596 @@
       entp = extp;
       mint = maxt;
+      if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+        break;
+      
       RayTraversalData &s  = tStack.top();
       node = s.mNode;
@@ -709 +712 @@
   
   return neighbors.size();
+}
+
+// Find random neighbor which was not mailed
+KdNode *
+KdTree::GetRandomLeaf(const Plane3 &plane)
+{
+  stack<KdNode *> nodeStack;
+  
+  nodeStack.push(mRoot);
+  
+  int mask = rand();
+  
+  while (!nodeStack.empty()) {
+    KdNode *node = nodeStack.top();
+    nodeStack.pop();
+    if (node->IsLeaf()) {
+      return node;
+    } else {
+      KdInterior *interior = (KdInterior *)node;
+      KdNode *next;
+        if (GetBox(interior->mBack).Side(plane) < 0)
+          next = interior->mFront;
+        else
+          if (GetBox(interior->mFront).Side(plane) < 0)
+            next = interior->mBack;
+          else {
+            // random decision
+            if (mask&1)
+              next = interior->mBack;
+            else
+              next = interior->mFront;
+            mask = mask>>1;
+          }
+        nodeStack.push(next);
+    }
+  }
+  
+  
+  return NULL;
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.h

@@ -307 +307 @@
                      );
 
+  
+  KdNode *
+  KdTree::GetRandomLeaf(const Plane3 &halfspace);
+  
   int
   FindNeighbors(KdNode *n,

trunk/VUT/GtpVisibilityPreprocessor/src/Makefile

@@ -1 +1 @@
 #############################################################################
 # Makefile for building: preprocessor
-# Generated by qmake (1.07a) (Qt 3.3.2) on: Thu Aug 04 20:06:06 2005
+# Generated by qmake (1.07a) (Qt 3.3.2) on: Mon Aug 22 21:02:28 2005
 # Project:  preprocessor.pro
 # Template: app
@@ -65 +65 @@
                 Triangle3.cpp \
                 Rectangle3.cpp \
-                Plane3.cpp
+                Plane3.cpp \
+                Polygon3.cpp \
+                ViewCell.cpp \
+                ViewCellBsp.cpp
 OBJECTS =       Preprocessor.obj \
                 SamplingPreprocessor.obj \
@@ -91 +94 @@
                 Triangle3.obj \
                 Rectangle3.obj \
-                Plane3.obj
+                Plane3.obj \
+                Polygon3.obj \
+                ViewCell.obj \
+                ViewCellBsp.obj
 FORMS = 
 UICDECLS =      
@@ -179 +185 @@
         -$(DEL_FILE) Rectangle3.obj
         -$(DEL_FILE) Plane3.obj
+        -$(DEL_FILE) Polygon3.obj
+        -$(DEL_FILE) ViewCell.obj
+        -$(DEL_FILE) ViewCellBsp.obj
 
 
@@ -195 +204 @@
                 X3dParser.h \
                 Preprocessor.h \
+                ViewCell.h \
+                Environment.h \
                 Containers.h \
                 AxisAlignedBox3.h \
@@ -311 +322 @@
                 Mesh.h \
                 KdTree.h \
+                ViewCellBsp.h \
+                ViewCell.h \
+                Polygon3.h \
                 Containers.h \
                 AxisAlignedBox3.h \
@@ -486 +500 @@
                 Mesh.h \
                 Triangle3.h \
+                SceneGraph.h \
                 Containers.h \
                 Pvs.h \
@@ -511 +526 @@
 Plane3.obj: Plane3.cpp  \
                 Plane3.h \
-                Vector3.h \
-                common.h \
+                Matrix4x4.h \
+                Vector3.h \
+                common.h \
+                
+
+Polygon3.obj: Polygon3.cpp  \
+                Polygon3.h \
+                Mesh.h \
+                Containers.h \
+                Intersectable.h \
+                Plane3.h \
+                Matrix4x4.h \
+                AxisAlignedBox3.h \
+                Material.h \
+                Pvs.h \
+                Rectangle3.h \
+                Vector3.h \
+                common.h \
+                
+
+ViewCell.obj: ViewCell.cpp  \
+                ViewCell.h \
+                Mesh.h \
+                MeshKdTree.h \
+                Triangle3.h \
+                Intersectable.h \
+                Containers.h \
+                AxisAlignedBox3.h \
+                Pvs.h \
+                Rectangle3.h \
+                Matrix4x4.h \
+                Vector3.h \
+                Plane3.h \
+                common.h \
+                Material.h \
+                Ray.h \
+                
+
+ViewCellBsp.obj: ViewCellBsp.cpp  \
+                Plane3.h \
+                ViewCellBsp.h \
+                Mesh.h \
+                common.h \
+                ViewCell.h \
+                Environment.h \
+                Polygon3.h \
+                Ray.h \
+                AxisAlignedBox3.h \
+                Vector3.h \
+                Containers.h \
+                Intersectable.h \
+                Matrix4x4.h \
+                Material.h \
+                Pvs.h \
+                Rectangle3.h \
                 
 

trunk/VUT/GtpVisibilityPreprocessor/src/Matrix4x4.cpp

@@ -8 +8 @@
 
 Matrix4x4::Matrix4x4(const Vector3 &a, const Vector3 &b, const Vector3 &c)
+{
+  // first index is column [x], the second is row [y]
+  x[0][0] = a.x;
+  x[1][0] = b.x;
+  x[2][0] = c.x;
+  x[3][0] = 0.0f;
+
+  x[0][1] = a.y;
+  x[1][1] = b.y;
+  x[2][1] = c.y;
+  x[3][1] = 0.0f;
+
+  x[0][2] = a.z;
+  x[1][2] = b.z;
+  x[2][2] = c.z;
+  x[3][2] = 0.0f;
+
+  x[0][3] = 0.0f;
+  x[1][3] = 0.0f;
+  x[2][3] = 0.0f;
+  x[3][3] = 1.0f;
+
+}
+
+void
+Matrix4x4::SetColumns(const Vector3 &a, const Vector3 &b, const Vector3 &c)
 {
   // first index is column [x], the second is row [y]
@@ -22 +48 @@
   x[0][2] = c.x;
   x[1][2] = c.y;
-  x[2][2] = c.z;
-  x[3][2] = 0.0f;
-
-  x[0][3] = 0.0f;
-  x[1][3] = 0.0f;
-  x[2][3] = 0.0f;
-  x[3][3] = 1.0f;
-}
-
-void
-Matrix4x4::SetColumns(const Vector3 &a, const Vector3 &b, const Vector3 &c)
-{
-  // first index is column [x], the second is row [y]
-  x[0][0] = a.x;
-  x[1][0] = b.x;
-  x[2][0] = c.x;
-  x[3][0] = 0.0f;
-
-  x[0][1] = a.y;
-  x[1][1] = b.y;
-  x[2][1] = c.y;
-  x[3][1] = 0.0f;
-
-  x[0][2] = a.z;
-  x[1][2] = b.z;
   x[2][2] = c.z;
   x[3][2] = 0.0f;

trunk/VUT/GtpVisibilityPreprocessor/src/Mesh.cpp

@@ -68 +68 @@
       nearestFace = faceIndex;
       hit++;
+      break;
+    case Ray::LINE_SEGMENT:
+      if (t <= 1.0f) {
+        ray.intersections.push_back(Ray::Intersection(t, instance, faceIndex));
+        hit++;
+      }
       break;
     }

trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.cpp

@@ -369 +369 @@
       entp = extp;
       mint = maxt;
+
+      if (ray.GetType() == Ray::LINE_SEGMENT && mint > 1.0f)
+        break;
+
       RayTraversalData &s  = tStack.top();
       node = s.mNode;

trunk/VUT/GtpVisibilityPreprocessor/src/MutualVisibility.cpp

@@ -9 +9 @@
 #include "Mesh.h"
 #include "Triangle3.h"
+#include "SceneGraph.h"
 
 void
@@ -26 +27 @@
 {
   Vector3 origin, direction;
-  GetRay(rayIndex, origin, direction);
-  return origin + direction*mSamples[rayIndex].mIntersections[depth].mT;
+  Ray ray;
+  GetRaySegment(rayIndex, ray);
+  if (depth >= mSamples[rayIndex].mIntersections.size()) {
+    cerr<<"depth of sample out of limits"<<endl;
+    exit(1);
+  }
+  return ray.Extrap(mSamples[rayIndex].mIntersections[depth].mT);
+}
+
+void
+RayShaft::GetRaySegment(const int i, Ray &ray) const
+{
+  Vector3 origin, direction;
+  GetRay(i, origin, direction);
+  ray.Init(origin, direction, Ray::LINE_SEGMENT);
+  if ( mSamples[i].IsValid() ) {
+    origin = ray.Extrap(mSamples[i].mMinT);
+    direction = ray.Extrap(mSamples[i].mMaxT) - origin;
+    ray.Init(origin, direction, Ray::LINE_SEGMENT);
+  }
 }
 
@@ -98 +117 @@
 
 float
-MutualVisibilitySampler::GetSpatialAngle(const RayShaft &sample,
+MutualVisibilitySampler::GetSpatialAngle(const RayShaft &shaft,
                                          const Vector3 &point
                                          )
 {
-  const int sampleIndices[][2]={
-    (0,1,2),
-    (0,2,3)
+  const int sampleIndices[]={
+    0,1,2,
+    0,2,3
   };
   
   float sum = 0.0f;
-  int i;
-  
+  int i, j=0;
+
+  if (!shaft.IsValid())
+    return 2.0f*mSolidAngleThreshold;
+
   for (i=0; i < 2; i++) {
-    Triangle3 triangle(sample.GetIntersectionPoint(sampleIndices[i][0], 0),
-                       sample.GetIntersectionPoint(sampleIndices[i][1], 0),
-                       sample.GetIntersectionPoint(sampleIndices[i][2], 0));
+    Triangle3 triangle(shaft.GetIntersectionPoint(sampleIndices[j++], 0),
+                       shaft.GetIntersectionPoint(sampleIndices[j++], 0),
+                       shaft.GetIntersectionPoint(sampleIndices[j++], 0));
     sum += triangle.GetSpatialAngle(point);
   }
@@ -122 +144 @@
 
 void
-MutualVisibilitySampler::ComputeError(RayShaft &sample)
+MutualVisibilitySampler::ComputeError(RayShaft &shaft)
 {
   // evaluate minimal error which can be achieved by more precise evaluation
   // if this is above the threshold do not proceed further
 
-  float maxAngle = GetSpatialAngle(sample,
-                                   sample.mSource.GetCenter());
-  
-  for (int i=0; i < 3; i++) {
-    float angle = GetSpatialAngle(sample,
-                                  sample.mSource.mVertices[i]);
+  // check whether the samples pierce the same mesh
+  Intersectable::NewMail();
+  int i, j;
+  for (i=0; i < 4; i++) {
+    RaySample *sample = &shaft.mSamples[i];
+    for (j=0; j < sample->mIntersections.size(); j++)
+      sample->mIntersections[j].mObject->Mail();
+  }
+
+  for (i=0; i < 4; i++) {
+    RaySample *sample = &shaft.mSamples[i];
+    for (j=0; j < sample->mIntersections.size(); j++) {
+      if (sample->mIntersections[j].mObject->IncMail() == 4) {
+        cerr<<"T";
+        shaft.mError = 0.0f;
+        return;
+      }
+    }
+  }
+    
+  
+  float maxAngle = GetSpatialAngle(shaft,
+                                   shaft.mTarget.GetCenter());
+  
+  for (i=0; i < 3; i++) {
+    float angle = GetSpatialAngle(shaft,
+                                  shaft.mTarget.mVertices[i]);
     if (angle > maxAngle)
       maxAngle = angle;
   }
-  
-  sample.mError = maxAngle;
-}
-
+
+  maxAngle = MAX_FLOAT;
+  shaft.mError = maxAngle;
+}
+
+
+void
+MutualVisibilitySampler::ConstructInitialSamples2(
+                                                  const AxisAlignedBox3 &source,
+                                                  const AxisAlignedBox3 &target,
+                                                  vector<RayShaft *> &samples
+                                                  )
+{
+  // get all rectangles potentially visible from the source box
+  int i;
+  int sourceMask = 0;
+  for (i=0; i < 8; i++)
+    sourceMask |= source.GetFaceVisibilityMask(target.GetVertex(i));
+
+  // now for each visble source face find all visible target faces
+  for (i=0; i < 6; i++) {
+    Rectangle3 sourceFace = source.GetFace(i);
+    if ( sourceMask &(1<<i) ) {
+      int mask = target.GetFaceVisibilityMask(sourceFace);
+      // construct triangle samples for all visible rectangles
+      for (int j=0; j < 6; j++)
+        if (mask & (1<<j)) {
+          AddInitialSamples2(sourceFace, target.GetFace(j), samples);
+        }
+    }
+  }
+}
+
+void
+MutualVisibilitySampler::ConstructInitialSamples3(
+                                                  const AxisAlignedBox3 &source,
+                                                  const AxisAlignedBox3 &target,
+                                                  vector<RayShaft *> &samples
+                                                  )
+{
+  // get all rectangles potentially visible from the source box
+  int i;
+  int sourceMask = 0;
+  for (i=0; i < 8; i++)
+    sourceMask |= source.GetFaceVisibilityMask(target.GetVertex(i));
+
+  // now for each visble source face find all visible target faces
+  int face;
+  for (face=0; face < 6; face++) {
+    if ( sourceMask & (1<<face) ) {
+      Rectangle3 sourceRect = source.GetFace(face);
+
+      Vector3 targetCenter = target.Center();
+      
+      Vector3 normal = sourceRect.GetNormal();
+      
+      Plane3 sourcePlane(normal, sourceRect.GetVertex(0));
+      
+      Plane3 targetPlane(normal, target.GetVertex(0));
+
+      int i;
+      for (i=1; i < 8; i++) {
+        Vector3 v = target.GetVertex(i);
+        if (targetPlane.Distance(v) < 0)
+          targetPlane = Plane3(normal, v);
+      }
+  
+      Vector3 xBasis = Normalize(sourceRect.GetVertex(1) - sourceRect.GetVertex(0));
+      Vector3 yBasis = Normalize(sourceRect.GetVertex(3) - sourceRect.GetVertex(0));
+
+      // cast rays between the centers of the boxes
+      Vector3 targetRCenter = targetPlane.FindIntersection(sourceRect.GetCenter(),
+                                                           targetCenter);
+      
+      Rectangle3 targetRect;
+      
+      float targetDist[4];
+      targetDist[0] = targetDist[1] = targetDist[2] = targetDist[3] = 0.0f;
+      
+      // cast rays between corresponding vertices of the boxes
+      int j;
+      int intersections=0;
+      for (i=0; i < 4; i++)
+        for (j=0; j < 8; j++) {
+          Vector3 v;
+          Vector3 diff;
+          bool coplanar;
+          float dist;
+          
+          v = targetPlane.FindIntersection(sourceRect.GetVertex(i),
+                                           target.GetVertex(j),
+                                           NULL,
+                                           &coplanar);
+          if (!coplanar) {
+            // evaluate target and 
+            diff = targetRCenter - v;
+            dist = DotProd(diff, xBasis);
+            if (dist < targetDist[0])
+              targetDist[0] = dist;
+            if (dist > targetDist[1])
+              targetDist[1] = dist;
+
+            dist = DotProd(diff, yBasis);
+
+            if (dist < targetDist[2])
+              targetDist[2] = dist;
+            if (dist > targetDist[3])
+              targetDist[3] = dist;
+            intersections++;
+          }
+        }
+      
+      if (intersections>=4) {
+        targetRect.mVertices[0] = targetRCenter + targetDist[0]*xBasis + targetDist[2]*yBasis;
+        targetRect.mVertices[1] = targetRCenter + targetDist[1]*xBasis + targetDist[2]*yBasis;
+        targetRect.mVertices[2] = targetRCenter + targetDist[1]*xBasis + targetDist[3]*yBasis;
+        targetRect.mVertices[3] = targetRCenter + targetDist[0]*xBasis + targetDist[3]*yBasis;
+        
+        //      cout<<sourceRect<<targetRect<<endl;
+        AddInitialSamples(sourceRect, targetRect, samples);
+      }
+    }
+  }
+}
 
 void
@@ -173 +336 @@
     xBasis.Normalize();
   else {
-    xBasis = CrossProd(Vector3(0,0,1), normal);
+    xBasis = Normalize(CrossProd(Vector3(0,0,1), normal));
   }
 
@@ -188 +351 @@
   Rectangle3 targetRect;
 
-  
+
+  if (0) {
   float scale = Magnitude(source.Size())*0.7f;
   sourceRect.mVertices[0] = sourceRCenter - scale*xBasis - scale*yBasis;
@@ -200 +364 @@
   targetRect.mVertices[2] = targetRCenter + scale*xBasis + scale*yBasis;
   targetRect.mVertices[3] = targetRCenter - scale*xBasis + scale*yBasis;
-
+  }
+
+
+  float sourceDist[4];
+  float targetDist[4];
+  sourceDist[0] = sourceDist[1] = sourceDist[2] = sourceDist[3] = 0.0f;
+  targetDist[0] = targetDist[1] = targetDist[2] = targetDist[3] = 0.0f;
+
+  // cast rays between corresponding vertices of the boxes
+  int j;
+  for (i=0; i < 8; i++)
+    for (j=0; j < 8; j++) {
+      Vector3 v;
+      Vector3 diff;
+      bool coplanar;
+      float dist;
+      v = sourcePlane.FindIntersection(source.GetVertex(i),
+                                       target.GetVertex(j),
+                                       NULL,
+                                       &coplanar);
+      if (!coplanar) {
+        // evaluate source and 
+        diff = sourceRCenter - v;
+        dist = DotProd(diff, xBasis);
+        if (dist < sourceDist[0])
+          sourceDist[0] = dist;
+        if (dist > sourceDist[1])
+          sourceDist[1] = dist;
+
+        dist = DotProd(diff, yBasis);
+        if (dist < sourceDist[2])
+          sourceDist[2] = dist;
+        if (dist > sourceDist[3])
+          sourceDist[3] = dist;
+      }
+      
+      v = targetPlane.FindIntersection(source.GetVertex(i),
+                                       target.GetVertex(j),
+                                       NULL,
+                                       &coplanar);
+      if (!coplanar) {
+        // evaluate target and 
+        diff = targetRCenter - v;
+        dist = DotProd(diff, xBasis);
+        if (dist < targetDist[0])
+          targetDist[0] = dist;
+        if (dist > targetDist[1])
+          targetDist[1] = dist;
+        dist = DotProd(diff, yBasis);
+        if (dist < targetDist[2])
+          targetDist[2] = dist;
+        if (dist > targetDist[3])
+          targetDist[3] = dist;
+      }
+    }
+
+  sourceRect.mVertices[0] = sourceRCenter + sourceDist[0]*xBasis + sourceDist[2]*yBasis;
+  sourceRect.mVertices[1] = sourceRCenter + sourceDist[1]*xBasis + sourceDist[2]*yBasis;
+  sourceRect.mVertices[2] = sourceRCenter + sourceDist[1]*xBasis + sourceDist[3]*yBasis;
+  sourceRect.mVertices[3] = sourceRCenter + sourceDist[0]*xBasis + sourceDist[3]*yBasis;
+
+  targetRect.mVertices[0] = targetRCenter + targetDist[0]*xBasis + targetDist[2]*yBasis;
+  targetRect.mVertices[1] = targetRCenter + targetDist[1]*xBasis + targetDist[2]*yBasis;
+  targetRect.mVertices[2] = targetRCenter + targetDist[1]*xBasis + targetDist[3]*yBasis;
+  targetRect.mVertices[3] = targetRCenter + targetDist[0]*xBasis + targetDist[3]*yBasis;
+
+
+  cout<<sourceRect<<targetRect<<endl;
   AddInitialSamples(sourceRect, targetRect, samples);
-
-  //    Plane3 bottomPlane(xBasis, source.Center());
-  //    Plane3 sidePlane(yBasis, source.Center());
-  
-  //    // cast rays between corresponding vertices of the boxes
-  //    for (i=0; i < 8; i++) {
-  //      Vector3 v;
-  //      bool coplanar;
-  //      v = sourcePlane.FindIntersection(source.GetVertex(i),
-  //                                 target.GetVertex(i),
-  //                                 NULL,
-  //                                 &coplanar);
-  //      if (!coplanar) {
-  //        // evaluate source and 
-  
-  //      }
-  //    }
-  
-  //  AddInitialSamples(sourceRectangle, targetRectangle, samples);
 }
 
@@ -236 +448 @@
 }
 
-
-void
-MutualVisibilitySampler::ExportSamples(vector<RayShaft *> &samples)
+void
+MutualVisibilitySampler::AddInitialSamples2(
+                                            const Rectangle3 &sourceRect,
+                                            const Rectangle3 &targetRect,
+                                            vector<RayShaft *> &samples
+                                            )
+{
+  // align the rectangles properly
+  Rectangle3 sRect, tRect;
+  if (DotProd(sourceRect.GetNormal(), targetRect.GetNormal()) < -0.99f) {
+    int i;
+    for (i=0; i < 4; i++) {
+      tRect.mVertices[i] = targetRect.mVertices[( 7 - i )%4];
+    }
+    
+    RayShaft *sample = new RayShaft(sourceRect, 
+                                    tRect);
+    samples.push_back(sample);
+  }
+  
+  return;
+  
+  float minDist = MAX_FLOAT;
+  int startI;
+  int startJ;
+  int i, j;
+
+  
+  for (i=0; i < 4; i++) {
+    for (j=0; j < 4; j++) {
+      float dist = Distance(sourceRect.mVertices[i], targetRect.mVertices[j]);
+      if (dist < minDist) {
+        minDist = dist;
+        startI = i;
+        startJ = j;
+      }
+    }
+  }
+  for (i=0; i < 4; i++) {
+    sRect.mVertices[i] = sourceRect.mVertices[(startI + i )%4];
+    tRect.mVertices[i] = targetRect.mVertices[(4 + startJ - i )%4];
+  }
+  
+  RayShaft *sample = new RayShaft(sRect, 
+                                  tRect);
+  samples.push_back(sample);
+}
+
+
+void
+MutualVisibilitySampler::ExportShafts(vector<RayShaft *> &shafts,
+                                      const bool singleFile)
 {
   static int id = 0;
@@ -244 +505 @@
   if (id > 20)
     return;
-                            
-  for (int i=0; i < samples.size(); i++) {
-    sprintf(filename, "samples%04d-%02d.x3d", id++, i);
-    Exporter *exporter = Exporter::GetExporter(filename);
-
+  
+  Exporter *exporter = NULL;
+  for (int i=0; i < shafts.size(); i++) {
+    if (!exporter) {
+      if (singleFile)
+        sprintf(filename, "shafts-single-%04d.x3d", id++);
+      else
+        sprintf(filename, "shafts%04d-%02d.x3d", id++, i);
+      exporter = Exporter::GetExporter(filename);
+    }
+    
     exporter->SetWireframe();
+    //    exporter->ExportScene(mSceneGraph->mRoot);
+
     exporter->ExportBox(mSource);
     exporter->ExportBox(mTarget);
@@ -256 +525 @@
 
 
-    RayShaft *sample = samples[i];
+    RayShaft *shaft = shafts[i];
     Mesh *mesh = new Mesh;
-    mesh->AddRectangle(sample->mSource);
-    mesh->AddRectangle(sample->mTarget);
+    mesh->AddRectangle(shaft->mSource);
+    mesh->AddRectangle(shaft->mTarget);
     vector<Ray> rays;
     for (int j=0; j < 4; j++) {
-      Vector3 origin, direction;
-      sample->GetRay(j, origin, direction);
-      Ray ray(origin, direction, Ray::LINE_SEGMENT);
+      Ray ray;
+      shaft->GetRaySegment(j, ray);
       rays.push_back(ray);
     }
@@ -273 +541 @@
     exporter->ExportIntersectable(&mi);
     exporter->ExportRays(rays, -1.0f, m.mDiffuseColor);
+    if (!singleFile) {
+      delete exporter;
+      exporter = NULL;
+    }
+  }
+  if (exporter)
     delete exporter;
-  }
+  
 }
 
@@ -283 +557 @@
   int i;
 
-  for (i=0; i < 4; i++) {
-    Vector3 origin, direction;
-    shaft.GetRay(i, origin, direction);
-    // determine intersections with the boxes
-    ray.Init(origin, direction, Ray::LINE_SEGMENT);
-    float stmin, stmax, ttmin, ttmax;
-    if ( mSource.GetMinMaxT(ray, &stmin, &stmax) && mTarget.GetMinMaxT(ray, &ttmin, &ttmax) ) {
-      shaft.mSamples[i].mMinT = stmax;
-      shaft.mSamples[i].mMaxT = ttmin;
-      origin = ray.Extrap(stmax);
-      direction = ray.Extrap(ttmin) - origin;
-      // reinit the ray
+  for (i=0; i < 4; i++)
+    if (!shaft.mSamples[i].IsProcessed()) {
+      Vector3 origin, direction;
+      shaft.GetRay(i, origin, direction);
+      // determine intersections with the boxes
       ray.Init(origin, direction, Ray::LINE_SEGMENT);
-      if (!mKdTree->CastRay(ray))
-        return VISIBLE;
-    } else {
-      shaft.mSamples[i].mMaxT = -1.0;
-    }
-  }
+      float stmin, stmax = 0.0f, ttmin=1.0f, ttmax;
+      bool valid = true;
+      
+      if (mUseBoxes) {
+        if (mSource.GetMinMaxT(ray, &stmin, &stmax) &&
+            mTarget.GetMinMaxT(ray, &ttmin, &ttmax)) {
+          shaft.mSamples[i].mMinT = stmax;
+          shaft.mSamples[i].mMaxT = ttmin;
+          origin = ray.Extrap(stmax);
+          direction = ray.Extrap(ttmin) - origin;
+          // reinit the ray
+          ray.Init(origin, direction, Ray::LINE_SEGMENT);
+        } else
+          valid = false;
+      } else {
+        shaft.mSamples[i].mMinT = 0.0f;
+        shaft.mSamples[i].mMaxT = 1.0f;
+      }
+      if (valid) {
+        if (!mKdTree->CastRay(ray)) {
+          cerr<<"V"<<endl;
+          return VISIBLE;
+        }
+        shaft.mSamples[i].mIntersections = ray.intersections;
+        cerr<<"I";
+      } else {
+        cerr<<"X";
+        shaft.mSamples[i].SetInvalid();
+      }
+    }
   return INVISIBLE;
 }
@@ -308 +599 @@
 MutualVisibilitySampler::ComputeVisibility()
 {
+  int result = INVISIBLE;
 
   vector<RayShaft *> shafts;
-  ConstructInitialSamples(mSource, mTarget, shafts);
-  ExportSamples(shafts);
+  ConstructInitialSamples3(mSource, mTarget, shafts);
+
+  if (1)
+    ExportShafts(shafts, false);
 
   stack<RayShaft *> shaftStack;
   
-  
-  
+  for (int i=0; i < shafts.size(); i++)
+    shaftStack.push(shafts[i]);
+
+  shafts.clear();
   Ray ray;
-  // now process the shafts as long as we have something to do
+  
+// now process the shafts as long as we have something to do
   while (!shaftStack.empty()) {
     RayShaft *shaft = shaftStack.top();
@@ -326 +623 @@
 //      int triangleSplitEdge = SetupExtremalRay(sample, source, ray);
     
-    if (CastRays(*shaft) == VISIBLE)
-      return VISIBLE;
-    
-    //      // generate 2 new samples
-    //      RayShaft newSamples[2];
-    //      sample.Split(triangleSplitEdge, ray, newSamples[0], newSamples[1]);
-    //      for (i=0; i < 2; i++) {
-    //        newSamples[i].ComputeError();
-    //        if (newSamples[i].mError > solidAngleThreshold) {
-    //          sampleStack.push(newSamples[i]);
-    //        }
-    //      }
-    //    }
-  }
-
-  for (int i=0; i < shafts.size(); i++)
+    if (CastRays(*shaft) == VISIBLE) {
+      result = VISIBLE;
+      break;
+    }
+
+    // compute error ....
+    ComputeError(*shaft);
+    cout<<shaft->mDepth<<"|";
+    if (shaft->IsValid())
+      shafts.push_back(shaft);
+
+    if (shaft->mDepth < 10 &&
+        shaft->mError > mSolidAngleThreshold) {
+      
+      // generate 2 new samples
+      RayShaft *newSamples[2];
+      newSamples[0] = new RayShaft;
+      newSamples[1] = new RayShaft;
+      
+      // chose what to split
+      bool splitSource = shaft->mSource.GetArea() > shaft->mTarget.GetArea();
+      int axis;
+      if (splitSource) {
+        axis = shaft->mSource.DominantAxis();
+      } else {
+        axis = shaft->mTarget.DominantAxis();
+      }
+      
+      PerformSplit(*shaft, splitSource, axis, *newSamples[0], *newSamples[1]);
+      //      delete shaft;
+      shaftStack.push(newSamples[0]);
+      shaftStack.push(newSamples[1]);
+    } else {
+      // store a terminal shaft
+    }
+
+  }
+  
+  while (!shaftStack.empty()) {
+    RayShaft *shaft = shaftStack.top();
+    shaftStack.pop();
+    delete shaft;
+  }
+
+  if (0)
+    ExportShafts(shafts, true);
+
+  for (i=0; i < shafts.size(); i++) {
     delete shafts[i];
-  return INVISIBLE;
-}
-
-MutualVisibilitySampler::MutualVisibilitySampler(KdTree *kdTree,
+  }
+
+  return result;
+}
+
+MutualVisibilitySampler::MutualVisibilitySampler(SceneGraph *sceneGraph,
+                                                 KdTree *kdTree,
                                                  AxisAlignedBox3 &source,
                                                  AxisAlignedBox3 &target,
                                                  const float solidAngleThreshold)
 {
+  mSceneGraph = sceneGraph;
   mKdTree = kdTree;
   mSource = source;
   mTarget = target;
+  mUseBoxes = true;
   mSolidAngleThreshold = solidAngleThreshold;
 }
@@ -359 +693 @@
 
 int
-ComputeBoxVisibility(KdTree *kdTree,
+ComputeBoxVisibility(SceneGraph *sceneGraph,
+                     KdTree *kdTree,
                      AxisAlignedBox3 &source,
                      AxisAlignedBox3 &target,
                      const float solidAngleThreshold)
 {
-  MutualVisibilitySampler sampler(kdTree, source, target, solidAngleThreshold);
+  MutualVisibilitySampler sampler(sceneGraph, kdTree, source, target, solidAngleThreshold);
 
   

trunk/VUT/GtpVisibilityPreprocessor/src/MutualVisibility.h

@@ -7 +7 @@
 class Intersectable;
 class AxisAlignedBox3;
+class SceneGraph;
 
-struct SimpleRay {
-  Vector3 mOrigin;
-  Vector3 mDirection;
-};
 
 struct RaySample {
@@ -17 +14 @@
   float mMinT;
   float mMaxT;
+
+  RaySample():mMinT(-1.0f), mMaxT(-1.0f) {}
   /// intersections of the sample with the scene
   vector<Ray::Intersection> mIntersections;
-  bool IsValid() const { return mMaxT > 0.0; }
+  void SetInvalid() {
+    mMinT = 0.0f;
+    mMaxT = -1.0f;
+  }
+  bool IsValid() const { return mMaxT > 0.0f; }
+  bool IsProcessed() const { return mMinT != mMaxT; }
 };
 
@@ -37 +41 @@
   void ComputeError();
   
-  RayShaft () {}
+  RayShaft() {}
   
   RayShaft (
@@ -45 +49 @@
     Init(source, target);
   }
-  
+
+  bool IsValid() const { return
+                           mSamples[0].IsValid() &&
+                           mSamples[1].IsValid() &&
+                           mSamples[2].IsValid() &&
+                           mSamples[3].IsValid();
+  }
+
   // initial triangle sample
   void Init(
@@ -58 +69 @@
               Vector3 &origin,
               Vector3 &direction) const;
+
+  void
+  GetRaySegment(const int i, Ray &ray) const;
+
 };
 
@@ -65 +80 @@
 class MutualVisibilitySampler {
 public:
+  SceneGraph *mSceneGraph;
   KdTree *mKdTree;
   AxisAlignedBox3 mSource;
   AxisAlignedBox3 mTarget;
   float mSolidAngleThreshold;
+  bool mUseBoxes;
 
-
-  MutualVisibilitySampler(KdTree *kdTree,
+  MutualVisibilitySampler(SceneGraph *sceneGraph,
+                          KdTree *kdTree,
                           AxisAlignedBox3 &source,
                           AxisAlignedBox3 &target,
@@ -86 +103 @@
 
   void
+  ConstructInitialSamples2(
+                          const AxisAlignedBox3 &source,
+                          const AxisAlignedBox3 &target,
+                          vector<RayShaft *> &samples
+                          );
+
+  void
+  ConstructInitialSamples3(
+                           const AxisAlignedBox3 &source,
+                           const AxisAlignedBox3 &target,
+                           vector<RayShaft *> &samples
+                           );
+
+  void
   AddInitialSamples(
                     const Rectangle3 &sourceRect,
@@ -91 +122 @@
                     vector<RayShaft *> &samples
                     );
+
+  void
+  AddInitialSamples2(
+                     const Rectangle3 &sourceRect,
+                     const Rectangle3 &targetRect,
+                     vector<RayShaft *> &samples
+                     );
 
   // the split sample method contains a methodology to create new samples
@@ -126 +164 @@
   
   void
-  ExportSamples(vector<RayShaft *> &samples);
+  ExportShafts(vector<RayShaft *> &samples, const bool singleFile);
 
 
@@ -132 +170 @@
   
 int
-ComputeBoxVisibility(KdTree *kdTree,
+ComputeBoxVisibility(SceneGraph *sceneGraph,
+                     KdTree *kdTree,
                      AxisAlignedBox3 &source,
                      AxisAlignedBox3 &target,

trunk/VUT/GtpVisibilityPreprocessor/src/Plane3.h

@@ -43 +43 @@
                            ) const 
   {
-          const Vector3 v = b - a; // line from A to B
-          float dv = DotProd(mNormal, v);
-         
-          if (signum(dv) == 0)
-          {
-                  if (coplanar) 
-                          (*coplanar) = true;   
-
-                  return a;
-          }
-          
-          float u = - Distance(a) / dv; // TODO: could be done more efficiently
-          //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl;
-          if (coplanar) 
-                  (*coplanar) = false;
+    const Vector3 v = b - a; // line from A to B
+    float dv = DotProd(mNormal, v);
+    
+    if (signum(dv) == 0)
+      {
+        if (coplanar) 
+          (*coplanar) = true;   
         
-          if (t) 
-                  (*t) = u;
-                  
-          return a + u * b - u * a; // NOTE: gives better precision than calclulating a + u * v
-          //return a + (u * v);
+        return a;
+      }
+    
+    float u = - Distance(a) / dv; // TODO: could be done more efficiently
+    //Debug << "t: " << u << ", b - a: " << v << ", norm: " << mNormal << ", dist(a): " << - Distance(a) << ", dv: " << dv << endl;
+    if (coplanar) 
+      (*coplanar) = false;
+    
+    if (t) 
+      (*t) = u;
+    
+    return a + u * b - u * a; // NOTE: gives better precision than calclulating a + u * v
+    //return a + (u * v);
   }
-
+  
   friend bool
   PlaneIntersection(const Plane3 &a, const Plane3 &b, const Plane3 &c, Vector3 &result);

trunk/VUT/GtpVisibilityPreprocessor/src/Ray.h

@@ -86 +86 @@
   
   // Inititalize the ray again when already constructed
-  void Init(const Vector3 &wherefrom, const Vector3 &whichdir,
+  void Init(const Vector3 &wherefrom,
+            const Vector3 &whichdir,
             const int _type, 
             bool dirNormalized = false) {
     loc = wherefrom;
-    dir = (dirNormalized) ? whichdir: Normalize(whichdir) ;
+    dir = (dirNormalized || _type == LINE_SEGMENT) ? whichdir: Normalize(whichdir) ;
     mType = _type;
     depth = 0;

trunk/VUT/GtpVisibilityPreprocessor/src/Rectangle3.h

@@ -1 +1 @@
 #ifndef __RECTANGLE3_H
 #define __RECTANGLE3_H
-
+#include <iostream>
+using namespace std;
 #include "Vector3.h"
 
@@ -11 +12 @@
   Vector3 mVertices[4];
 
+  Vector3 GetVertex(const int i) const { return mVertices[i]; }
   Rectangle3() {}
   
@@ -23 +25 @@
   }
   
-  Vector3 GetNormal() {
+  Vector3 GetNormal() const {
     return Normalize(CrossProd(mVertices[0]-mVertices[1],
                                mVertices[2]-mVertices[1]
@@ -29 +31 @@
   }
   
-  Vector3 GetCenter() {
+  Vector3 GetCenter() const {
     return (mVertices[0] + mVertices[1] + mVertices[2] + mVertices[3])/4.0f;
   }
 
-
+  int DominantAxis() const {
+    if (SqrMagnitude(mVertices[0] - mVertices[1]) >  SqrMagnitude(mVertices[0] - mVertices[3]))
+      return 0;
+    else
+      return 1;
+  }
+      
+  float GetArea() const {
+    Vector3 v = CrossProd(mVertices[3], mVertices[0]);
+    
+    for (int i=0; i < 3; i++)
+      v += CrossProd(mVertices[i], mVertices[i+1]);
+    
+    return 0.5f*abs(DotProd(GetNormal(), v));
+  }
+  
   void
   Split(const int axis,
@@ -39 +56 @@
         Rectangle3 &r2
         ) const;
-  
+
+  friend ostream& operator<< (ostream &s, const Rectangle3 &r) {
+    return s<<"Rectangle3:"<<r.mVertices[0]<<r.mVertices[1]<<r.mVertices[2]<<r.mVertices[3];
+  }
+
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -12 +12 @@
   environment->GetIntValue("Sampling.totalSamples", mTotalSamples);
   mKdPvsDepth = 100;
+  mStats.open("stats.log");
 
 }
@@ -68 +69 @@
 }
 
+//  void
+//  SamplingPreprocessor::AvsGenerateRandomRay(Ray &ray)
+//  {
+//    int objId = RandomValue(0, mObjects.size());
+//    Intersectable *object = objects[objId];
+//    object->GetRandomSurfacePoint(point, normal);
+//    direction = UniformRandomVector(normal);
+//    SetupRay(ray, point, direction);
+//  }
+
+//  void
+//  SamplingPreprocessor::AvsHandleRay(Ray &ray)
+//  {
+//    int sampleContributions = 0;
+
+//    mKdTree->CastRay(ray);
+  
+//    if (ray.leaves.size()) {
+//      sampleContributions += AddNodeSamples(object, ray, pass);
+    
+//      if (ray.intersections.size()) {
+//        sampleContributions += AddNodeSamples(ray.intersections[0].mObject, ray, pass);
+//      }
+//    }
+//  }
+
+//  void
+//  SamplingPreprocessor::AvsBorderSampling(Ray &ray)
+//  {
+  
+
+//  }
+
+//  void
+//  SamplingPreprocessor::AvsPass()
+//  {
+//    Ray ray;
+//    while (1) {
+//      AvsGenerateRay(ray);
+//      HandleRay(ray);
+//      while ( !mRayQueue.empty() ) {
+//        Ray ray = mRayQueue.pop();
+//        mRayQueue.pop();
+//        AdaptiveBorderSampling(ray);
+//      }
+//    }
+  
+  
+
+//  }
+
+
+
 bool
 SamplingPreprocessor::ComputeVisibility()
 {
-
+  
   // pickup an object
   ObjectContainer objects;
@@ -100 +154 @@
         KdNode *nodeToSample = NULL;
         Intersectable *object = objects[i];
-                  
+        
         int pvsSize = object->mKdPvs.GetSize();
-      
+
+
+
         if (0 && pvsSize) {
           // mail all nodes from the pvs
@@ -125 +181 @@
           }
         }
-
-        
-        if (pvsSize && pass == 50 ) {
+        
+        if (0 && pvsSize && pass == 1000 ) {
           // mail all nodes from the pvs
           Intersectable::NewMail();
@@ -144 +199 @@
             AxisAlignedBox3 box = object->GetBox();
             for (int j=0; j < invisibleNeighbors.size(); j++) {
-              int visibility = ComputeBoxVisibility(mKdTree,
+              int visibility = ComputeBoxVisibility(mSceneGraph,
+                                                    mKdTree,
                                                     box,
                                                     mKdTree->GetBox(invisibleNeighbors[j]),
-                                                    1.0f);
-            
+                                                    1e-6f);
+              //              exit(0);
             }
             // now rank all the neighbors according to probability that a new
@@ -155 +211 @@
         }
 
-      
+        object->GetRandomSurfacePoint(point, normal);
+        nodeToSample = mKdTree->GetRandomLeaf(Plane3(normal, point));
+
         for (int k=0; k < mSamplesPerPass; k++) {
-          object->GetRandomSurfacePoint(point, normal);
-        
+          
           if (nodeToSample) {
             int maxTries = 5;
-          
+            
             for (int tries = 0; tries < maxTries; tries++) {
               direction = mKdTree->GetBox(nodeToSample).GetRandomPoint() - point;
-            
+              
               if (DotProd(direction, normal) > Limits::Small)
                 break;
             }
-          
+            
             if (tries == maxTries)
               direction = UniformRandomVector(normal);
-          } 
-          else
+          }
+          else {
             direction = UniformRandomVector(normal);
-        
+          }
+          
           // construct a ray
           SetupRay(ray, point, direction);
           mKdTree->CastRay(ray);
-
-          if (i < pvsOut)
+          
+          if ( i < pvsOut )
             rays[i].push_back(ray);
-        
+          
           int sampleContributions = 0;
-        
-                  
+          
           if (ray.leaves.size()) {
             sampleContributions += AddNodeSamples(object, ray, pass);
-          
+            
             if (ray.intersections.size()) {
               sampleContributions += AddNodeSamples(ray.intersections[0].mObject, ray, pass);
@@ -222 +279 @@
       }
     
-      cout << "pass " << pass<<" : t = " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
-      cout << "#totalSamples=" << totalSamples/1000 
-           << "k   #sampleContributions=" << passSampleContributions << " (" 
+      cout << "#Pass " << pass<<" : t = " << TimeDiff(startTime, GetTime())*1e-3 << "s" << endl;
+      cout << "#TotalSamples=" << totalSamples/1000 
+           << "k   #SampleContributions=" << passSampleContributions << " (" 
            << 100*passContributingSamples/(float)passSamples<<"%)" << " avgPVS="
            << pvsSize/(float)objects.size() << endl 
            << "avg ray contrib=" << passSampleContributions/(float)passContributingSamples << endl;
+
+
+      mStats <<
+        "#Pass\n" <<pass<<endl<<
+        "#Time\n" << TimeDiff(startTime, GetTime())*1e-3 << endl<<
+        "#TotalSamples\n" << totalSamples<< endl<<
+        "#SampleContributions\n" << passSampleContributions << endl << 
+        "#PContributingSamples\n"<<100*passContributingSamples/(float)passSamples<<endl <<
+        "#AvgPVS\n"<< pvsSize/(float)objects.size() << endl <<
+        "#AvgRayContrib\n" << passSampleContributions/(float)passContributingSamples << endl;
     }
 

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.h

@@ -2 +2 @@
 #define _SamplingPreprocessor_H__
 
+#include <fstream>
+using namespace std;
+
 #include "Preprocessor.h"
 
+struct SimpleRay {
+  Vector3 mOrigin;
+  Vector3 mDirection;
+};
 
 /** Sampling based visibility preprocessing. The implementation is based on heuristical
@@ -12 +19 @@
   int mTotalSamples;
   int mKdPvsDepth;
-  
+  ofstream mStats;
+  ObjectContainer mObjects;
+
   SamplingPreprocessor();
 

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCell.cpp

@@ -59 +59 @@
 {
         // maximal max viewcells
-        int limit = maxViewCells > 0 ? std::min((int)objects.size(), maxViewCells) : (int)objects.size();
+        int limit = maxViewCells > 0 ? Min((int)objects.size(), maxViewCells) : (int)objects.size();
 
         for (int i = 0; i < limit; ++i)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellBsp.cpp

@@ -350 +350 @@
         ObjectContainer::const_iterator it, it_end = objects.end();
 
-        int limit = (maxObjects > 0) ? min((int)objects.size(), maxObjects) : (int)objects.size();
+        int limit = (maxObjects > 0) ? Min((int)objects.size(), maxObjects) : (int)objects.size();
         
         // initialise bounding box
@@ -463 +463 @@
         Plane3 *bestPlane = NULL;
         
-        int limit = min((int)polygons->size(), maxTests);
+        int limit = Min((int)polygons->size(), maxTests);
 
         for (int i = 0; i < limit; ++i)

trunk/VUT/GtpVisibilityPreprocessor/src/default.env

@@ -8 +8 @@
 #       filename glasgow1.x3d
 #       filename vienna.x3d
-        filename ../data/atlanta/atlanta2.x3d
+#       filename ../data/atlanta/atlanta2.x3d
 #       filename ../data/soda/soda.dat
-#       filename ../data/soda/soda5.dat
+        filename ../data/soda/soda5.dat
 
 }
@@ -54 +54 @@
 
 Sampling {
-        totalSamples    1000000
-        samplesPerPass  5
+        totalSamples    50000000
+        samplesPerPass  20
 }

trunk/VUT/GtpVisibilityPreprocessor/src/preprocessor.pro

@@ -16 +16 @@
 
 # RELEASE CONFIG
-#CONFIG         += windows warn_on thread
+#CONFIG         += windows warn_on thread release
 
 # DEPENDPATH    = ../../include
@@ -32 +32 @@
 Matrix4x4.cpp Vector3.cpp AxisAlignedBox3.cpp Ray.cpp main.cpp Mesh.cpp \
 Exporter.cpp Camera.cpp X3dParser.cpp MeshKdTree.cpp Pvs.cpp \
-MutualVisibility.cpp Triangle3.cpp Rectangle3.cpp Plane3.cpp
+MutualVisibility.cpp Triangle3.cpp Rectangle3.cpp Plane3.cpp Polygon3.cpp \
+ViewCell.cpp ViewCellBsp.cpp