Changeset 162 for trunk

Timestamp:

07/11/05 00:02:07 (19 years ago)

Author:

bittner

Message:

functional raycasting version

Location:

trunk/VUT/GtpVisibilityPreprocessor/src

Files:

• AxisAlignedBox3.cpp (added)
• AxisAlignedBox3.h (added)
• Camera.cpp (added)
• Camera.h (added)
• Containers.h (added)
• Environment.cpp (added)
• Environment.h (added)
• ExactPreprocessor.cpp (modified) (1 diff)
• ExactPreprocessor.h (added)
• Exporter.cpp (added)
• Exporter.h (added)
• Intersectable.h (added)
• KdTree.cpp (modified) (1 diff)
• KdTree.h (added)
• Material.cpp (added)
• Material.h (added)
• Matrix4x4.cpp (added)
• Matrix4x4.h (added)
• Mesh.cpp (added)
• Mesh.h (added)
• Parser.h (added)
• Plane3.h (added)
• Preprocessor.cpp (modified) (1 diff)
• Preprocessor.h (added)
• Ray.cpp (added)
• Ray.h (added)
• SamplingPreprocessor.cpp (modified) (1 diff)
• SamplingPreprocessor.h (added)
• SceneGraph.cpp (added)
• SceneGraph.h (added)
• UnigraphicsParser.cpp (added)
• UnigraphicsParser.h (added)
• Vector3.cpp (added)
• Vector3.h (added)
• ViewCellBSP.h (added)
• VisibilityVector3.h (added)
• X3dExporter.cpp (added)
• X3dExporter.h (added)
• X3dParser.cpp (added)
• X3dParser.h (added)
• common.cpp (added)
• common.h (added)
• gzstream.cpp (added)
• gzstream.h (added)
• main.cpp (added)

trunk/VUT/GtpVisibilityPreprocessor/src/ExactPreprocessor.cpp

@@ -1 +1 @@
 #include "ExactPreprocessor.h"
 
-namespace GtpVisibilityPreprocessor {
   
-  bool
-  ExactPreprocessor::ComputeVisibility()
-  {
-
-    return true;
-  };
+bool
+ExactPreprocessor::ComputeVisibility()
+{
   
+  return true;
 };
 

trunk/VUT/GtpVisibilityPreprocessor/src/KdTree.cpp

@@ +1 @@
+#include <stack>
+#include <algorithm>
+#include <queue>
+#include "Environment.h"
+#include "Mesh.h"
 #include "KdTree.h"
 
-namespace GtpVisibilityPreprocessor {
-  
-  bool
-  KdTree::Subdivide(KdNode *subtree)
-  {
-    return true;
-  }
-
-}
+
+
+
+KdNode::KdNode(KdInterior *parent):mParent(parent)
+{
+  if (parent)
+    mDepth = parent->mDepth+1;
+  else
+    mDepth = 0;
+}
+
+KdTree::KdTree()
+{
+  mRoot = new KdLeaf(NULL, 0);
+  environment->GetIntValue("KdTree.Termination.maxDepth", mTermMaxDepth);
+  environment->GetIntValue("KdTree.Termination.minCost", mTermMinCost);
+  environment->GetFloatValue("KdTree.Termination.maxCostRatio", mMaxCostRatio);
+  environment->GetFloatValue("KdTree.Termination.ct_div_ci", mCt_div_ci);
+  environment->GetFloatValue("KdTree.splitBorder", mSplitBorder);
+
+  char splitType[64];
+  environment->GetStringValue("KdTree.splitMethod", splitType);
+  
+  mSplitMethod = SPLIT_SPATIAL_MEDIAN;
+  if (strcmp(splitType, "spatialMedian") == 0)
+    mSplitMethod = SPLIT_SPATIAL_MEDIAN;
+  else
+    if (strcmp(splitType, "objectMedian") == 0)
+      mSplitMethod = SPLIT_OBJECT_MEDIAN;
+    else
+      if (strcmp(splitType, "SAH") == 0)
+        mSplitMethod = SPLIT_SAH;
+      else {
+        cerr<<"Wrong kd split type "<<splitType<<endl;
+        exit(1);
+      }
+
+  splitCandidates = new vector<SortableEntry>;
+}
+
+bool
+KdTree::Construct()
+{
+  // first construct a leaf that will get subdivide
+  KdLeaf *leaf = (KdLeaf *) mRoot;
+
+  mStat.nodes = 1;
+
+  mBox.Initialize();
+  
+  MeshContainer::const_iterator mi;
+  for ( mi = leaf->mObjects.begin();
+        mi != leaf->mObjects.end();
+        mi++) {
+    mBox.Include((*mi)->GetBox());
+  }
+
+  cout <<"box:"<< mBox<<endl;
+
+  
+  mRoot = Subdivide(TraversalData(leaf, mBox, 0));
+
+  return true;
+}
+
+KdNode *
+KdTree::Subdivide(const TraversalData &tdata)
+{
+
+  KdNode *result = NULL;
+
+  priority_queue<TraversalData> tStack;
+  //  stack<STraversalData> tStack;
+  
+  tStack.push(tdata);
+  AxisAlignedBox3 backBox, frontBox;
+
+  
+  while (!tStack.empty()) {
+
+#if 0
+    if ( GetMemUsage() > maxMemory ) {
+      // count statistics on unprocessed leafs
+      while (!tStack.empty()) {
+        EvaluateLeafStats(tStack.top());
+        tStack.pop();
+      }
+      break;
+    }
+#endif
+
+    TraversalData data = tStack.top();
+    tStack.pop();
+    
+    KdNode *node = SubdivideNode((KdLeaf *) data.mNode,
+                                 data.mBox,
+                                 backBox,
+                                 frontBox
+                                 );
+    if (result == NULL)
+      result = node;
+    
+    if (!node->IsLeaf()) {
+
+      KdInterior *interior = (KdInterior *) node;
+      // push the children on the stack
+      tStack.push(TraversalData(interior->mBack, backBox, data.mDepth+1));
+      tStack.push(TraversalData(interior->mFront, frontBox, data.mDepth+1));
+      
+    } else {
+      EvaluateLeafStats(data);
+    }
+  }
+  
+  return result;
+
+}
+
+
+
+bool
+KdTree::TerminationCriteriaMet(const KdLeaf *leaf)
+{
+  //  cerr<<"\n OBJECTS="<<leaf->mObjects.size()<<endl;
+  return
+    (leaf->mObjects.size() < mTermMinCost) ||
+    (leaf->mDepth >= mTermMaxDepth);
+  
+}
+
+
+int
+KdTree::SelectPlane(KdLeaf *leaf,
+                    const AxisAlignedBox3 &box,
+                    float &position
+                    )
+{
+  int axis = -1;
+  
+  switch (mSplitMethod)
+    {
+    case SPLIT_SPATIAL_MEDIAN: {
+      axis = box.Size().DrivingAxis();
+      position = (box.Min()[axis] + box.Max()[axis])*0.5f;
+      break;
+    }
+    case SPLIT_SAH: {
+      int objectsBack, objectsFront;
+      float costRatio;
+      bool mOnlyDrivingAxis = false;
+      if (mOnlyDrivingAxis) {
+        axis = box.Size().DrivingAxis();
+        costRatio = BestCostRatio(leaf,
+                                  box,
+                                  axis,
+                                  position,
+                                  objectsBack,
+                                  objectsFront);
+      } else {
+        costRatio = MAX_FLOAT;
+        for (int i=0; i < 3; i++) {
+          float p;
+          float r = BestCostRatio(leaf,
+                                  box,
+                                  i,
+                                  p,
+                                  objectsBack,
+                                  objectsFront);
+          if (r < costRatio) {
+            costRatio = r;
+            axis = i;
+            position = p;
+          }
+        }
+      }
+      
+      if (costRatio > mMaxCostRatio) {
+        //      cout<<"Too big cost ratio "<<costRatio<<endl;
+        axis = -1;
+      }
+      break;
+    }
+    
+    }
+  return axis;
+}
+
+KdNode *
+KdTree::SubdivideNode(
+                      KdLeaf *leaf,
+                      const AxisAlignedBox3 &box,
+                      AxisAlignedBox3 &backBBox,
+                      AxisAlignedBox3 &frontBBox
+                      )
+{
+  
+  if (TerminationCriteriaMet(leaf))
+    return leaf;
+  
+  float position;
+  
+  // select subdivision axis
+  int axis = SelectPlane( leaf, box, position );
+
+  if (axis == -1) {
+    return leaf;
+  }
+  
+  mStat.nodes+=2;
+  mStat.splits[axis]++;
+  
+  // add the new nodes to the tree
+  KdInterior *node = new KdInterior(leaf->mParent);
+
+  node->mAxis = axis;
+  node->mPosition = position;
+  node->mBox = box;
+  
+  backBBox = box;
+  frontBBox = box;
+  
+  // first count ray sides
+  int objectsBack = 0;
+  int objectsFront = 0;
+  
+  backBBox.SetMax(axis, position);
+  frontBBox.SetMin(axis, position);
+
+  MeshContainer::const_iterator mi;
+
+  for ( mi = leaf->mObjects.begin();
+        mi != leaf->mObjects.end();
+        mi++) {
+    // determine the side of this ray with respect to the plane
+    AxisAlignedBox3 box = (*mi)->GetBox();
+    if (box.Max(axis) > position ) 
+      objectsFront++;
+    
+    if (box.Min(axis) < position )
+      objectsBack++;
+  }
+
+  
+  KdLeaf *back = new KdLeaf(node, objectsBack);
+  KdLeaf *front = new KdLeaf(node, objectsFront);
+
+  // replace a link from node's parent
+  if (  leaf->mParent )
+    leaf->mParent->ReplaceChildLink(leaf, node);
+
+  // and setup child links
+  node->SetupChildLinks(back, front);
+  
+  for (mi = leaf->mObjects.begin();
+       mi != leaf->mObjects.end();
+       mi++) {
+    // determine the side of this ray with respect to the plane
+    AxisAlignedBox3 box = (*mi)->GetBox();
+
+    if (box.Max(axis) >= position )
+      front->mObjects.push_back(*mi);
+    
+    if (box.Min(axis) < position )
+      back->mObjects.push_back(*mi);
+    
+    mStat.objectRefs -= leaf->mObjects.size();
+    mStat.objectRefs += objectsBack + objectsFront;
+  }
+  
+  delete leaf;
+  return node;
+}
+
+
+
+void
+KdTreeStatistics::Print(ostream &app) const
+{
+  app << "===== KdTree statistics ===============\n";
+
+  app << "#N_RAYS Number of rays )\n"
+      << rays <<endl;
+  app << "#N_DOMAINS  ( Number of query domains )\n"
+      << queryDomains <<endl;
+  
+  app << "#N_NODES ( Number of nodes )\n" << nodes << "\n";
+
+  app << "#N_LEAVES ( Number of leaves )\n" << Leaves() << "\n";
+
+  app << "#N_SPLITS ( Number of splits in axes x y z dx dy dz \n";
+  for (int i=0; i<7; i++)
+    app << splits[i] <<" ";
+  app <<endl;
+
+  app << "#N_RAYREFS ( Number of rayRefs )\n" <<
+    rayRefs << "\n";
+
+  app << "#N_RAYRAYREFS  ( Number of rayRefs / ray )\n" <<
+    rayRefs/(double)rays << "\n";
+
+  app << "#N_LEAFRAYREFS  ( Number of rayRefs / leaf )\n" <<
+    rayRefs/(double)Leaves() << "\n";
+
+  app << "#N_MAXOBJECTREFS  ( Max number of rayRefs / leaf )\n" <<
+    maxObjectRefs << "\n";
+
+  app << "#N_NONEMPTYRAYREFS  ( Number of rayRefs in nonEmpty leaves / non empty leaf )\n" <<
+    rayRefsNonZeroQuery/(double)(Leaves() - zeroQueryNodes) << "\n";
+
+  app << "#N_LEAFDOMAINREFS  ( Number of query domain Refs / leaf )\n" <<
+    objectRefs/(double)Leaves() << "\n";
+
+  //  app << setprecision(4);
+
+  app << "#N_PEMPTYLEAVES  ( Percentage of leaves with zero query domains )\n"<<
+    zeroQueryNodes*100/(double)Leaves()<<endl;
+
+  app << "#N_PMAXDEPTHLEAVES ( Percentage of leaves at maxdepth )\n"<<
+    maxDepthNodes*100/(double)Leaves()<<endl;
+
+  app << "#N_PMINCOSTLEAVES  ( Percentage of leaves with minCost )\n"<<
+    minCostNodes*100/(double)Leaves()<<endl;
+
+  app << "#N_ADDED_RAYREFS  (Number of dynamically added ray references )\n"<<
+    addedRayRefs<<endl;
+
+  app << "#N_REMOVED_RAYREFS  (Number of dynamically removed ray references )\n"<<
+    removedRayRefs<<endl;
+
+  //  app << setprecision(4);
+
+  //  app << "#N_CTIME  ( Construction time [s] )\n"
+  //      << Time() << " \n";
+
+  app << "===== END OF KdTree statistics ==========\n";
+
+}
+
+
+
+void
+KdTree::EvaluateLeafStats(const TraversalData &data)
+{
+
+  // the node became a leaf -> evaluate stats for leafs
+  KdLeaf *leaf = (KdLeaf *)data.mNode;
+
+  if (data.mDepth > mTermMaxDepth)
+    mStat.maxDepthNodes++;
+  
+  if ( (int)(leaf->mObjects.size()) < mTermMinCost)
+    mStat.minCostNodes++;
+  
+  
+  if ( (int)(leaf->mObjects.size()) > mStat.maxObjectRefs)
+    mStat.maxObjectRefs = leaf->mObjects.size();
+  
+}
+
+
+
+void
+KdTree::SortSplitCandidates(
+                            KdLeaf *node,
+                            const int axis
+                            )
+{
+  splitCandidates->clear();
+  
+  int requestedSize = 2*node->mObjects.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(MeshContainer::const_iterator mi = node->mObjects.begin();
+      mi < node->mObjects.end();
+      mi++) {
+    AxisAlignedBox3 box = (*mi)->GetBox();
+
+    splitCandidates->push_back(SortableEntry(SortableEntry::MESH_MIN,
+                                             box.Min(axis),
+                                             (void *)*mi)
+                               );
+    
+    
+    splitCandidates->push_back(SortableEntry(SortableEntry::MESH_MAX,
+                                             box.Max(axis),
+                                             (void *)*mi)
+                               );
+  }
+  
+  stable_sort(splitCandidates->begin(), splitCandidates->end());
+}
+
+
+float
+KdTree::BestCostRatio(
+                      KdLeaf *node,
+                      const AxisAlignedBox3 &box,
+                      const int axis,
+                      float &position,
+                      int &objectsBack,
+                      int &objectsFront
+                      )
+{
+
+  SortSplitCandidates(node, axis);
+  
+  // go through the lists, count the number of objects left and right
+  // and evaluate the following cost funcion:
+  // C = ct_div_ci  + (ol + or)/queries
+
+  int ol = 0, or = node->mObjects.size();
+
+  float minBox = box.Min(axis);
+  float maxBox = box.Max(axis);
+  float boxArea = box.SurfaceArea();
+  
+  
+  
+  float minBand = minBox + mSplitBorder*(maxBox - minBox);
+  float maxBand = minBox + (1.0f - mSplitBorder)*(maxBox - minBox);
+  
+  float minSum = 1e20;
+  
+  for(vector<SortableEntry>::const_iterator ci = splitCandidates->begin();
+      ci < splitCandidates->end();
+      ci++) {
+    
+    switch ((*ci).type) {
+    case SortableEntry::MESH_MIN:
+      ol++;
+      break;
+    case SortableEntry::MESH_MAX:
+      or--;
+      break;
+    }
+
+    if ((*ci).value > minBand && (*ci).value < maxBand) {
+      AxisAlignedBox3 lbox = box;
+      AxisAlignedBox3 rbox = box;
+      lbox.SetMax(axis, (*ci).value);
+      rbox.SetMin(axis, (*ci).value);
+
+      float sum = ol*lbox.SurfaceArea() + or*rbox.SurfaceArea();
+      
+      //      cout<<"pos="<<(*ci).value<<"\t q=("<<ql<<","<<qr<<")\t r=("<<rl<<","<<rr<<")"<<endl;
+      //      cout<<"cost= "<<sum<<endl;
+      
+      if (sum < minSum) {
+        minSum = sum;
+        position = (*ci).value;
+        
+        objectsBack = ol;
+        objectsFront = or;
+      }
+    }
+  }
+  
+  float oldCost = node->mObjects.size();
+  float newCost = mCt_div_ci + minSum/boxArea;
+  float ratio = newCost/oldCost;
+
+#if 0
+  cout<<"===================="<<endl;
+  cout<<"costRatio="<<ratio<<" pos="<<position<<" t="<<(position - minBox)/(maxBox - minBox)
+      <<"\t o=("<<objectsBack<<","<<objectsFront<<")"<<endl;
+#endif
+  return ratio;
+}
+
+int
+KdTree::CastRay(
+                Ray &ray
+                )
+{
+  int hits = 0;
+  
+  stack<RayTraversalData> tStack;
+  
+  float maxt = 1e6;
+  float mint = 0;
+
+  
+  if (!mBox.GetMinMaxT(ray, &mint, &maxt))
+    return 0;
+
+  if (mint < 0)
+    mint = 0;
+  
+  maxt += Limits::Threshold;
+  
+  Vector3 entp = ray.Extrap(mint);
+  Vector3 extp = ray.Extrap(maxt);
+  
+  KdNode *node = mRoot;
+  KdNode *farChild;
+  float position;
+  int axis;
+  
+  while (1) {
+    if (!node->IsLeaf()) {
+      KdInterior *in = (KdInterior *) node;
+      position = in->mPosition;
+      axis = in->mAxis;
+
+      if (entp[axis] <= position) {
+        if (extp[axis] <= position) {
+          node = in->mBack;
+          // cases N1,N2,N3,P5,Z2,Z3
+          continue;
+        } else {
+          // case N4
+          node = in->mBack;
+          farChild = in->mFront;
+        }
+      }
+      else {
+        if (position <= extp[axis]) {
+          node = in->mFront;
+          // cases P1,P2,P3,N5,Z1
+          continue;
+        } else {
+          node = in->mFront;
+          farChild = in->mBack;
+          // case P4
+        }
+      }
+      // $$ modification 3.5.2004 - hints from Kamil Ghais
+      // case N4 or P4
+      float tdist = (position - ray.GetLoc(axis)) / ray.GetDir(axis);
+      tStack.push(RayTraversalData(farChild, extp, maxt));
+      extp = ray.GetLoc() + ray.GetDir()*tdist;
+      maxt = tdist;
+    } else {
+      // compute intersection with all objects in this leaf
+      KdLeaf *leaf = (KdLeaf *) node;
+      ray.leaves.push_back(leaf);
+      
+      MeshContainer::const_iterator mi;
+      for ( mi = leaf->mObjects.begin();
+            mi != leaf->mObjects.end();
+            mi++) {
+        MeshInstance *mesh = *mi;
+        if (!mesh->Mailed() ) {
+          mesh->Mail();
+          //ray.meshes.push_back(mesh);
+          hits += mesh->CastRay(ray);
+        }
+      }
+
+      if (hits && ray.GetType() == Ray::LOCAL_RAY)
+        if (ray.intersections[0].mT <= maxt)
+          break;
+      
+      // get the next node from the stack
+      if (tStack.empty())
+        break;
+      
+      entp = extp;
+      mint = maxt;
+      RayTraversalData &s  = tStack.top();
+      node = s.mNode;
+      extp = s.mExitPoint;
+      maxt = s.mMaxT;
+      tStack.pop();
+    }
+  }
+  
+  
+  return hits;
+}
+

trunk/VUT/GtpVisibilityPreprocessor/src/Preprocessor.cpp

@@ +1 @@
+#include "SceneGraph.h"
+#include "Exporter.h"
+#include "UnigraphicsParser.h"
 #include "Preprocessor.h"
-#include "SamplingPreprocessor.h"
-#include "ExactPreprocessor.h"
 
-namespace GtpVisibilityPreprocessor {
 
-  bool
-  Preprocessor::LoadViewcells(const string filename)
-  {
 
+  
+bool
+Preprocessor::LoadViewcells(const string filename)
+{
+  
+  return true;
+}
+
+bool
+Preprocessor::GenerateViewcells()
+{
+  
+  return true;
+}
+
+bool
+Preprocessor::LoadScene(const string filename)
+{
+  // use leaf nodes of the original spatial hiearrchy as occludees
+
+  mSceneGraph = new SceneGraph;
+  Parser *parser = new UnigraphicsParser;
+  bool result = parser->ParseFile(filename, &mSceneGraph->mRoot);
+  
+  return result;
+}
+
+bool
+Preprocessor::ExportPreprocessedData(const string filename)
+{
+  return false;
+}
+
+bool
+Preprocessor::BuildKdTree()
+{
+  mKdTree = new KdTree;
+  // add mesh instances of the scene graph to the root of the tree
+  KdLeaf *root = (KdLeaf *)mKdTree->GetRoot();
+  mSceneGraph->CollectMeshInstaces(&root->mObjects);
+  
+  mKdTree->Construct();
+  return true;
+}
+
+
+void
+Preprocessor::KdTreeStatistics(ostream &s)
+{
+  s<<mKdTree->GetStatistics();
+}
+
+
+bool
+Preprocessor::Export( const string filename,
+                      const bool scene,
+                      const bool kdtree
+                      )
+{
+  Exporter *exporter = Exporter::GetExporter(filename);
+
+  if (exporter) {
+    if (scene)
+      exporter->ExportScene(mSceneGraph->mRoot);
+
+    if (kdtree) {
+      exporter->SetWireframe();
+      exporter->ExportKdTree(*mKdTree);
+    }
+
+    delete exporter;
     return true;
   }
 
-  bool
-  Preprocessor::GenerateViewcells()
-  {
-    
-    return true;
-  }
-    
-  bool
-  Preprocessor::LoadScene(const string filename)
-  {
-    // use leaf nodes of the original spatial hiearrchy as occludees
-    
-    return true;
-  }
+  return false;
+}
 
-  bool
-  Preprocessor::ExportPreprocessedData(const string filename)
-  {
-    return false;
-  }
-  
-  bool
-  Preprocessor::BuildKdTree()
-  {
-    mKdTree = new KdTree;
-    mKdTree->Subdivide(mKdTree->GetRoot());
-    return true;
-  }
-  
-};
 
-int
-main(int argc, char **argv)
-{
-  GtpVisibilityPreprocessor::Preprocessor *p = new GtpVisibilityPreprocessor::SamplingPreprocessor();
-  p->LoadScene("scene.wrl");
-  p->LoadViewcells("viewcells.wrl");
-  p->ComputeVisibility();
-  p->ExportPreprocessedData("scene.vis");
-  return 0;
-}
+

trunk/VUT/GtpVisibilityPreprocessor/src/SamplingPreprocessor.cpp

@@ -1 +1 @@
 #include "SamplingPreprocessor.h"
 
-namespace GtpVisibilityPreprocessor {
+
   
-  bool
-  SamplingPreprocessor::ComputeVisibility()
-  {
-
-    return true;
-  };
-  
+bool
+SamplingPreprocessor::ComputeVisibility()
+{
+  return true;
 };