Changeset 500

Timestamp:

01/05/06 00:47:59 (18 years ago)

Author:

mattausch

Message:

added new node primitive ro vspkd tree

Location:

trunk/VUT

Files:

• GtpVisibilityPreprocessor/src/GlRenderer.h (modified) (1 diff)
• GtpVisibilityPreprocessor/src/RssTree.cpp (modified) (1 diff)
• GtpVisibilityPreprocessor/src/VspBspTree.cpp (modified) (2 diffs)
• GtpVisibilityPreprocessor/src/VspKdTree.cpp (modified) (10 diffs)
• GtpVisibilityPreprocessor/src/VspKdTree.h (modified) (9 diffs)
• scripts/GtpVisibility.suo (modified) (previous)

trunk/VUT/GtpVisibilityPreprocessor/src/GlRenderer.h

@@ -4 +4 @@
 #include <QtOpenGL>
 #include <QWaitCondition>
+//#include <QGLPixelBuffer>
 
 #include "Vector3.h"

trunk/VUT/GtpVisibilityPreprocessor/src/RssTree.cpp

@@ -1922 +1922 @@
         positions--;
   }
+  return true; // corr. matt
 }
 

trunk/VUT/GtpVisibilityPreprocessor/src/VspBspTree.cpp

@@ -1751 +1751 @@
         nodeStack.push(mRoot);
 
-        // planes needed to verify that we found neighbor leaf.
+        // split planes from the root to this node
+        // needed to verify that we found neighbor leaf
         vector<Plane3> halfSpaces;
         ExtractHalfSpaces(n, halfSpaces);
@@ -1783 +1784 @@
                                                 isAdjacent = false;
                                 }
-
+                                // neighbor was found
                                 if (isAdjacent)
                                         neighbors.push_back(dynamic_cast<BspLeaf *>(node));

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.cpp

@@ -75 +75 @@
 
 // Inline constructor
-VspKdNode::VspKdNode(VspKdInterior *p):
+VspKdNode::VspKdNode(VspKdNode *p):
 mParent(p), mAxis(-1), mDepth(p ? p->mDepth + 1 : 0)
 {}
@@ -83 +83 @@
 };
 
-inline VspKdInterior *VspKdNode::GetParent() const
+inline VspKdNode *VspKdNode::GetParent() const
 {
         return mParent;
 }
 
-inline void VspKdNode::SetParent(VspKdInterior *p)
+inline void VspKdNode::SetParent(VspKdNode *p)
 {
         mParent = p;
@@ -126 +126 @@
 
 void VspKdInterior::ReplaceChildLink(VspKdNode *oldChild,
-                                                                                 VspKdNode *newChild)
+                                                                         VspKdNode *newChild)
 {
         if (mBack == oldChild)
@@ -184 +184 @@
 
 
-VspKdLeaf::VspKdLeaf(VspKdInterior *p, 
+VspKdLeaf::VspKdLeaf(VspKdNode *p, 
                                          const int nRays, 
                                          const int maxCostMisses):
@@ -339 +339 @@
 }
 
-/*********************************************************/
-/*            class VspKdTree implementation             */
-/*********************************************************/
+
+/***************************************************************/
+/*          class VspKdIntermediate implementation             */
+/***************************************************************/
+
+
+VspKdIntermediate::VspKdIntermediate(VspKdInterior *p):
+VspKdNode(p), mBack(NULL), mFront(NULL), mAccesses(0), mLastAccessTime(-1)
+{
+}
+
+
+VspKdIntermediate::~VspKdIntermediate()
+{
+        DEL_PTR(mFront);
+        DEL_PTR(mBack);
+}
+    
+        
+int VspKdIntermediate::Type() const
+{
+        return EIntermediate;
+}
+
+
+VspKdLeaf *VspKdIntermediate::GetBack() const
+{
+        return mBack;
+}
+
+
+VspKdLeaf *VspKdIntermediate::GetFront() const
+{
+        return mFront;
+}
+
+
+void VspKdIntermediate::Print(ostream &s) const
+{
+        s << endl << mSplitPlane << endl;
+}
+
+
+void VspKdIntermediate::SetupChildLinks(VspKdLeaf *b, VspKdLeaf *f)
+{
+        mBack = b;
+        mFront = f;
+
+        b->SetParent(this);
+        f->SetParent(this);
+}
+
+
+int VspKdIntermediate::ComputeRayIntersection(const RayInfo &rayData, float &t)
+{
+        return rayData.ComputeRayIntersection(mSplitPlane, t);
+}
+
+
+/*************************************************************/
+/*              class VspKdTree implementation               */
+/*************************************************************/
 
 
@@ -1131 +1190 @@
 
         // add the new nodes to the tree
-        VspKdInterior *node = new VspKdInterior(leaf->mParent);
+        VspKdInterior *node = 
+                new VspKdInterior(dynamic_cast<VspKdInterior *>(leaf->mParent));
 
         node->mAxis = axis;
@@ -1147 +1207 @@
         // replace a link from node's parent
         if (leaf->mParent)
-                leaf->mParent->ReplaceChildLink(leaf, node);
+        {
+                VspKdInterior *parent = dynamic_cast<VspKdInterior *>(leaf->mParent);
+                parent->ReplaceChildLink(leaf, node);
+        }
         // and setup child links
         node->SetupChildLinks(back, front);
@@ -1570 +1633 @@
         VspKdLeaf *newLeaf = new VspKdLeaf(sroot->mParent, rayCount);
 
-        if (newLeaf->mParent)
-        {
-                newLeaf->mParent->ReplaceChildLink(sroot, newLeaf);
+        VspKdInterior *parent = 
+                dynamic_cast<VspKdInterior *>(newLeaf->mParent);
+
+        if (parent)
+        {
+                parent->ReplaceChildLink(sroot, newLeaf);
         }
         tstack.push(sroot);
@@ -1834 +1900 @@
 
         if (!node->IsLeaf())
-                return (dynamic_cast<VspKdInterior *>(node))->mBox;
-
-        if (node->mParent->mAxis >= 3)
-                return node->mParent->mBox;
-
-        AxisAlignedBox3 box(node->mParent->mBox);
-        if (node->mParent->GetFront() == node)
-                box.SetMin(node->mParent->mAxis, node->mParent->mPosition);
+        {
+                if (node->Type() == VspKdNode::EIntermediate)
+            return (dynamic_cast<VspKdInterior *>(node))->mBox;
+                else
+                        return (dynamic_cast<VspKdIntermediate *>(node))->mBox;
+        }
+
+        VspKdInterior *parent = dynamic_cast<VspKdInterior *>(node->mParent);
+
+        if (parent->mAxis >= 3)
+                return parent->mBox;
+
+        AxisAlignedBox3 box(parent->mBox);
+        if (parent->GetFront() == node)
+                box.SetMin(parent->mAxis, parent->mPosition);
         else
-                box.SetMax(node->mParent->mAxis, node->mParent->mPosition);
+                box.SetMax(parent->mAxis, parent->mPosition);
 
         return box;
@@ -2348 +2421 @@
                         leaf->SetViewCell(vc);
 
+                        VspKdInterior *parent = 
+                                dynamic_cast<VspKdInterior *>(leaf->mParent);
                         // replace a link from node's parent
-                        if (leaf->mParent)
-                                leaf->mParent->ReplaceChildLink(node, leaf);
+                        if (parent)
+                                parent->ReplaceChildLink(node, leaf);
 
                         delete interior;

trunk/VUT/GtpVisibilityPreprocessor/src/VspKdTree.h

@@ -203 +203 @@
         friend class VspKdTree;
 
-        enum {EInterior, ELeaf};
+        enum {EInterior, EIntermediate, ELeaf};
 
         /** Constructs new interior node from the parent node.
         */
-        inline VspKdNode(VspKdInterior *p);
+        inline VspKdNode(VspKdNode *p);
 
         /** Destroys this node and the subtree.
@@ -226 +226 @@
 
         /** Returns time needed to access this node.
-        */
-        virtual int GetAccessTime(); // NOTE: don't really know how it is used!
+                @NOTE: don't really know how it is used!
+        */
+        virtual int GetAccessTime(); 
 
         /** Returns parent node.
         */
-        VspKdInterior *GetParent() const;
+        VspKdNode *GetParent() const;
 
         /** Sets parent node.
         */
-        void SetParent(VspKdInterior *p);
+        void SetParent(VspKdNode *p);
 
 protected:
@@ -242 +243 @@
   
         /// link to the parent
-        VspKdInterior *mParent;
+        VspKdNode *mParent;
 
         enum {SPLIT_X = 0, SPLIT_Y, SPLIT_Z};
@@ -308 +309 @@
 
 
+/**
+        Node type just before leaf holding abitrary split plane
+*/
+class VspKdIntermediate: public VspKdNode
+{
+public:
+        friend class VspKdTree;
+
+        /** Constructs new interior node from parent node.
+        */
+        VspKdIntermediate(VspKdInterior *p);
+                        
+        //virtual int GetAccessTime();
+        
+        virtual int Type() const;
+  
+        virtual ~VspKdIntermediate();
+    
+        virtual void Print(ostream &s) const;
+
+        /** Returns back child.
+        */
+        inline VspKdLeaf *GetBack() const;
+        /** Returns front child.
+        */
+        inline VspKdLeaf *GetFront() const;
+
+protected:
+
+        /** Sets pointers to back child and front child.
+        */
+        void SetupChildLinks(VspKdLeaf *b, VspKdLeaf *f);
+        /** Computes intersection of the ray with the node boundaries.
+        */
+        int ComputeRayIntersection(const RayInfo &rayData, float &t);
+
+        // plane in local modelling coordinates
+        Plane3 mSplitPlane;
+
+        // pointers to children
+        VspKdLeaf *mBack;
+        VspKdLeaf *mFront;
+
+        // the bbox of the node
+        AxisAlignedBox3 mBox;
+
+        // data for caching
+        long mAccesses;
+        long mLastAccessTime;
+};
+
 // --------------------------------------------------------------
 // KD-tree node - leaf node
@@ -322 +374 @@
                 @parma maxMisses how many times the max cost ratio was missed on the path to the leaf
         */
-        VspKdLeaf(VspKdInterior *p,     const int nRays, const int maxCostMisses = 0);
+        VspKdLeaf(VspKdNode *p, const int nRays, const int maxCostMisses = 0);
         
         virtual ~VspKdLeaf();
@@ -385 +437 @@
         */
         int GetMaxCostMisses();
-
 
         ////////////////////////////////////////////
@@ -413 +464 @@
         int mMaxCostMisses;
 
-private:
+//private:
         /// stores PVS size so we have to evaluate PVS size only once
         int mPvsSize;
 };
-
 
 
@@ -456 +506 @@
                 VspKdNode *mNode;
                 AxisAlignedBox3 mBox;
+                //TODO PolygonContainer *mPolys;
+
                 int mDepth;
                 //float mPriority;
@@ -480 +532 @@
                 {
                         // return a.node->queries.size() < b.node->queries.size();
-                        VspKdLeaf *leafa = (VspKdLeaf *) a.mNode;
-                        VspKdLeaf *leafb = (VspKdLeaf *) b.mNode;
+                        VspKdLeaf *leafa = dynamic_cast<VspKdLeaf *>(a.mNode);
+                        VspKdLeaf *leafb = dynamic_cast<VspKdLeaf *>(b.mNode);
 #if 0
                         return