Changeset 406 for trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellKd.h

Timestamp:

11/11/05 21:28:02 (19 years ago)

Author:

mattausch

Message:

started kd based bottom-up view cells

File:

• trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellKd.h (moved) (moved from trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellsKd.h) (26 diffs)

trunk/VUT/GtpVisibilityPreprocessor/src/ViewCellKd.h

@@ -1 @@
-#ifndef _KdTree_H__
-#define _KdTree_H__
+#ifndef _ViewCellKdTree_H__
+#define _ViewCellKdTree_H__
 
 #include <functional>
@@ -11 +11 @@
 
   
-class KdNode;
-class KdLeaf;
-class KdInterior;
+class ViewCellKdNode;
+class ViewCellKdLeaf;
+class ViewCellKdInterior;
 class Intersectable;
 
@@ -20 +20 @@
 // Static statistics for kd-tree search
 // --------------------------------------------------------------
-class KdTreeStatistics 
+class ViewCellKdTreeStatistics 
 {
 public:  
@@ -51 +51 @@
   
   // Constructor
-  KdTreeStatistics() {
+  ViewCellKdTreeStatistics() {
     Reset();
   }
@@ -75 +75 @@
   Print(ostream &app) const;
 
-  friend ostream &operator<<(ostream &s, const KdTreeStatistics &stat) {
+  friend ostream &operator<<(ostream &s, const ViewCellKdTreeStatistics &stat) {
     stat.Print(s);
     return s;
@@ -83 +83 @@
 
   
-class KdInterior;
+class ViewCellKdInterior;
 /** Abstract class for kd-tree node */
-class KdNode {
+class ViewCellKdNode {
 public:
   static int mailID;
@@ -95 +95 @@
 
 
-  KdNode(KdInterior *parent);
+  ViewCellKdNode(ViewCellKdInterior *parent);
 
   /** Determines whether this node is a leaf or interior node
@@ -111 +111 @@
   /** Parent of the node - the parent is a little overhead for maintanance of the tree,
       but allows various optimizations of tree traversal algorithms */
-  KdInterior *mParent;
+  ViewCellKdInterior *mParent;
   int mDepth;
 };
 
 /** Implementation of the kd-tree interior node */
-class KdInterior : public KdNode {
+class ViewCellKdInterior : public ViewCellKdNode {
 
 public:
     
-  KdInterior(KdInterior *parent):KdNode(parent), mBack(NULL), mFront(NULL) {}
-
-  /** \sa KdNode::IsLeaf() */
+  ViewCellKdInterior(ViewCellKdInterior *parent):ViewCellKdNode(parent), mBack(NULL), mFront(NULL) {}
+
+  /** \sa ViewCellKdNode::IsLeaf() */
   virtual bool IsLeaf() const { return false; }
 
@@ -133 +133 @@
 
   /** back node */
-  KdNode *mBack;
+  ViewCellKdNode *mBack;
   /** front node */
-  KdNode *mFront;
-
-  void SetupChildLinks(KdNode *b, KdNode *f) {
+  ViewCellKdNode *mFront;
+
+  void SetupChildLinks(ViewCellKdNode *b, ViewCellKdNode *f) {
     mBack = b;
     mFront = f;
@@ -143 +143 @@
   }
   
-  void ReplaceChildLink(KdNode *oldChild, KdNode *newChild) {
+  void ReplaceChildLink(ViewCellKdNode *oldChild, ViewCellKdNode *newChild) {
     if (mBack == oldChild)
       mBack = newChild;
@@ -155 +155 @@
   
 /** Implementation of the kd-tree leaf node */
-class KdLeaf : public KdNode {
+class ViewCellKdLeaf : public ViewCellKdNode {
 public:
-  KdLeaf(KdInterior *parent, const int objects):KdNode(parent) {
+  ViewCellKdLeaf(ViewCellKdInterior *parent, const int objects):ViewCellKdNode(parent) {
     mObjects.reserve(objects);
   }
@@ -176 +176 @@
   }
 
-  /** \sa KdNode::IsLeaf() */
+  /** \sa ViewCellKdNode::IsLeaf() */
   virtual bool IsLeaf() const { return true; }
   
@@ -191 +191 @@
   PassingRaySet mPassingRays;
         
-  /** PVS consisting of visible KdTree nodes */
-  KdPvs mKdPvs;
+  /** PVS consisting of visible ViewCellKd nodes */
+  ViewCellKdPvs mKdPvs;
         
         /** PVS consisting of visible objects */
@@ -200 +200 @@
   
 
-/** KdTree for indexing scene entities - occluders/occludees/viewcells */
-class KdTree {
+/** ViewCellKd for indexing scene entities - occluders/occludees/viewcells */
+class ViewCellKd {
 
 protected:
   struct TraversalData
   {  
-    KdNode *mNode;
+    ViewCellKdNode *mNode;
     AxisAlignedBox3 mBox;
     int mDepth;
@@ -213 +213 @@
     TraversalData() {}
 
-    TraversalData(KdNode *n, const float p):
+    TraversalData(ViewCellKdNode *n, const float p):
       mNode(n), mPriority(p)
     {}
     
-    TraversalData(KdNode *n,
+    TraversalData(ViewCellKdNode *n,
                    const AxisAlignedBox3 &b,
                    const int d):
@@ -225 +225 @@
     bool operator<(
                    const TraversalData &b) const {
-      KdLeaf *leafa = (KdLeaf *) mNode;
-      KdLeaf *leafb = (KdLeaf *) b.mNode;
+      ViewCellKdLeaf *leafa = (ViewCellKdLeaf *) mNode;
+      ViewCellKdLeaf *leafb = (ViewCellKdLeaf *) b.mNode;
       return 
         leafa->mObjects.size()*mBox.SurfaceArea()
@@ -254 +254 @@
         SPLIT_SAH};
   
-  KdTree();
+  ViewCellKd();
   
     
@@ -274 +274 @@
       were already met
   */
-  virtual KdNode *Subdivide(const TraversalData &tdata);
+  virtual ViewCellKdNode *Subdivide(const TraversalData &tdata);
 
   /** Get the root of the tree */
-  KdNode *GetRoot() const {
+  ViewCellKdNode *GetRoot() const {
     return mRoot;
   }
@@ -289 +289 @@
           );
 
-  const KdTreeStatistics &GetStatistics() const {
+  const ViewCellKdTreeStatistics &GetStatistics() const {
     return mStat;
   }
 
   void
-  CollectObjects(KdNode *n, ObjectContainer &objects);
+  CollectObjects(ViewCellKdNode *n, ObjectContainer &objects);
         
   void
-  CollectLeaves(vector<KdLeaf *> &leaves);
-        
-  AxisAlignedBox3 GetBox(const KdNode *node) const {
-    KdInterior *parent = node->mParent;
+  CollectLeaves(vector<ViewCellKdLeaf *> &leaves);
+        
+  AxisAlignedBox3 GetBox(const ViewCellKdNode *node) const {
+    ViewCellKdInterior *parent = node->mParent;
     if (parent == NULL)
       return mBox;
     
     if (!node->IsLeaf())
-      return ((KdInterior *)node)->mBox;
+      return ((ViewCellKdInterior *)node)->mBox;
     
     AxisAlignedBox3 box(parent->mBox);
@@ -315 +315 @@
   }
         
-  KdNode *
-  FindRandomNeighbor(KdNode *n,
+  ViewCellKdNode *
+  FindRandomNeighbor(ViewCellKdNode *n,
                                                                                  bool onlyUnmailed
                                                                                  );
   
-  KdNode *
-  KdTree::GetRandomLeaf(const Plane3 &halfspace);
-
-        KdNode *
+  ViewCellKdNode *
+  ViewCellKd::GetRandomLeaf(const Plane3 &halfspace);
+
+        ViewCellKdNode *
         GetRandomLeaf(const bool onlyUnmailed = false);
 
   int
-  FindNeighbors(KdNode *n,
-                vector<KdNode *> &neighbors,
+  FindNeighbors(ViewCellKdNode *n,
+                vector<ViewCellKdNode *> &neighbors,
                 bool onlyUnmailed
                 );
@@ -419 +419 @@
 
   struct RayTraversalData {
-    KdNode *mNode;
+    ViewCellKdNode *mNode;
     Vector3 mExitPoint;
     float mMaxT;
     
     RayTraversalData() {}
-    RayTraversalData(KdNode *n,
+    RayTraversalData(ViewCellKdNode *n,
                      const Vector3 &p,
                      const float maxt):
@@ -460 +460 @@
   float
   BestCostRatio(
-                KdLeaf *node,
+                ViewCellKdLeaf *node,
                 const AxisAlignedBox3 &box,
                 const int axis,
@@ -470 +470 @@
   void
   SortSplitCandidates(
-                      KdLeaf *node,
+                      ViewCellKdLeaf *node,
                       const int axis
                       );
@@ -477 +477 @@
   EvaluateLeafStats(const TraversalData &data);
 
-  KdNode *
+  ViewCellKdNode *
   SubdivideNode(
-                KdLeaf *leaf,
+                ViewCellKdLeaf *leaf,
                 const AxisAlignedBox3 &box,
                 AxisAlignedBox3 &backBBox,
@@ -486 +486 @@
 
   bool
-  TerminationCriteriaMet(const KdLeaf *leaf);
+  TerminationCriteriaMet(const ViewCellKdLeaf *leaf);
   
   int
-  SelectPlane(KdLeaf *leaf,
+  SelectPlane(ViewCellKdLeaf *leaf,
               const AxisAlignedBox3 &box,
               float &position
@@ -504 +504 @@
   bool mSahUseFaces;
   /// root of the tree
-  KdNode *mRoot;
+  ViewCellKdNode *mRoot;
   /// bounding box of the tree root
   AxisAlignedBox3 mBox;
-  KdTreeStatistics mStat;
+  ViewCellKdTreeStatistics mStat;
   
 };
-  
-
-
-
-
 
 #endif