now using stlplus containers, especially ntree
authorCharles McGarvey <chazmcgarvey@brokenzipper.com>
Fri, 21 Aug 2009 07:15:59 +0000 (01:15 -0600)
committerCharles McGarvey <chazmcgarvey@brokenzipper.com>
Fri, 21 Aug 2009 07:15:59 +0000 (01:15 -0600)
data/scenes/Test.json
src/Makefile.am
src/Moof/Octree.hh
src/Moof/Scene.cc
src/Moof/Tree.hh [deleted file]
src/YoinkApp.cc

index db9ba5d1e626cc147b8fd17fd6a0a567373ab2b1..562a3befec0cb3224423f30392716e4c6b2c8c54 100644 (file)
@@ -1,6 +1,6 @@
 {
        "playfield_bounds": [0, 0, -100, 1280, 500, 100],
-       "maximum_bounds": [-165, -5, -197, 1445, 517, 229],
+       "maximum_bounds": [-160, 0, -192, 1440, 512, 224],
        "instructions":
        [
 
index 1d320e691cbbd2a87a753e02555722f21258f6a7..f4122dec4a3a6659d7531e510db69bb1535f8cf7 100644 (file)
@@ -32,7 +32,6 @@ libmoof_la_SOURCES = \
                                   Moof/OpenGL.hh \
                                   Moof/Plane.cc \
                                   Moof/Plane.hh \
-                                  Moof/Profiler.hh \
                                   Moof/Random.cc \
                                   Moof/Random.hh \
                                   Moof/Resource.cc \
@@ -57,7 +56,6 @@ libmoof_la_SOURCES = \
                                   Moof/Tilemap.hh \
                                   Moof/Timer.cc \
                                   Moof/Timer.hh \
-                                  Moof/Tree.hh \
                                   Moof/Video.cc \
                                   Moof/Video.hh \
                                   Moof/fastevents.c \
@@ -85,7 +83,7 @@ yoink_CPPFLAGS = -I$(top_srcdir)/src/Moof
 yoink_LDADD    = libmoof.la
 
 
-EXTRA_DIST = Moof/cml
+EXTRA_DIST = Moof/cml Moof/stlplus
 
 
 YOINK_ENVIRONMENT = YOINK_DATADIR="$(top_srcdir)/data"
index 78d3aa875706cd61f4558740c7b90a8cf4f82cd3..1c57ff2d3317fe83d10aa6972093683cb634556f 100644 (file)
 
 #include <boost/shared_ptr.hpp>
 
+#include <stlplus/ntree.hpp>
+
 #include <Moof/Aabb.hh>
 #include <Moof/Drawable.hh>
 #include <Moof/Entity.hh>
 #include <Moof/Math.hh>
 #include <Moof/Sphere.hh>
-#include <Moof/Tree.hh>
        
 
 namespace Mf {
@@ -102,40 +103,45 @@ struct OctreeNode : public Entity
 class Octree;
 typedef boost::shared_ptr<Octree> OctreePtr;
 
-class Octree : public Tree<OctreeNode>
+class Octree
 {
 
-       Octree() {}
-
-       explicit Octree(const OctreeNode& initNode) :
-               Tree<OctreeNode>(initNode) {}
+       stlplus::ntree<OctreeNode> root_;
 
 public:
 
-       inline static OctreePtr createNewNode(const OctreeNode& item)
+       explicit Octree(const OctreeNode& rootNode)
        {
-               OctreePtr newNode = OctreePtr(new Octree(item));
-               init(newNode);
-               return newNode;
+               root_.insert(rootNode);
        }
 
+       void insert(EntityPtr entity)
+       {
+               insert(root_.root(), entity);
+       }
 
-       static Tree<OctreeNode>::WeakPtr add(Ptr node, EntityPtr entity)
+       void insert(stlplus::ntree<OctreeNode>::iterator node, EntityPtr entity)
        {
                Plane::Halfspace halfspace;
                int octantNum = -1;
 
-               Plane xy = node->node.getAabb().getPlaneXY();
+               if (!node.valid())
+               {
+                       std::cerr << "cannot insert into invalid node" << std::endl;
+                       return;
+               }
+
+               Plane xy = node->getAabb().getPlaneXY();
                halfspace = xy.intersectsSphere(entity->getSphere());
 
                if (halfspace == Plane::POSITIVE)
                {
-                       Plane xz = node->node.getAabb().getPlaneXZ();
+                       Plane xz = node->getAabb().getPlaneXZ();
                        halfspace = xz.intersectsSphere(entity->getSphere());
 
                        if (halfspace == Plane::POSITIVE)
                        {
-                               Plane yz = node->node.getAabb().getPlaneYZ();
+                               Plane yz = node->getAabb().getPlaneYZ();
                                halfspace = yz.intersectsSphere(entity->getSphere());
 
                                if (halfspace == Plane::POSITIVE)
@@ -149,7 +155,7 @@ public:
                        }
                        else if (halfspace == Plane::NEGATIVE)
                        {
-                               Plane yz = node->node.getAabb().getPlaneYZ();
+                               Plane yz = node->getAabb().getPlaneYZ();
                                halfspace = yz.intersectsSphere(entity->getSphere());
 
                                if (halfspace == Plane::POSITIVE)
@@ -164,12 +170,12 @@ public:
                }
                else if (halfspace == Plane::NEGATIVE)
                {
-                       Plane xz = node->node.getAabb().getPlaneXZ();
+                       Plane xz = node->getAabb().getPlaneXZ();
                        halfspace = xz.intersectsSphere(entity->getSphere());
 
                        if (halfspace == Plane::POSITIVE)
                        {
-                               Plane yz = node->node.getAabb().getPlaneYZ();
+                               Plane yz = node->getAabb().getPlaneYZ();
                                halfspace = yz.intersectsSphere(entity->getSphere());
 
                                if (halfspace == Plane::POSITIVE)
@@ -183,7 +189,7 @@ public:
                        }
                        else if (halfspace == Plane::NEGATIVE)
                        {
-                               Plane yz = node->node.getAabb().getPlaneYZ();
+                               Plane yz = node->getAabb().getPlaneYZ();
                                halfspace = yz.intersectsSphere(entity->getSphere());
 
                                if (halfspace == Plane::POSITIVE)
@@ -199,136 +205,145 @@ public:
 
                if (octantNum == -1)
                {
-                       node->node.objects.push_front(entity);
-                       return node;
+                       node->objects.push_front(entity);
+                       //return node;
                }
                else
                {
-                       if (node->isLeaf())
+                       if (root_.children(node) == 0)
                        {
                                addChildren(node);
                        }
 
-                       Ptr child = node->getChild(octantNum);
-                       if (child)
+                       stlplus::ntree<OctreeNode>::iterator child = root_.child(node, octantNum);
+
+                       if (child.valid())
                        {
-                               return add(child, entity);
+                               return insert(child, entity);
                        }
                        else
                        {
-                               std::cerr << "no child at index " << octantNum << std::endl;
-                               return Ptr();
+                               std::cerr << "expected but found no child at index " << octantNum << std::endl;
+                               //return stlplus::ntree<OctreeNode>::iterator();
                        }
                        //return WeakPtr();
                }
        }
 
-       static void addChildren(Ptr node)
+       void addChildren(stlplus::ntree<OctreeNode>::iterator node)
        {
                Aabb octant;
 
+               if (!node.valid())
+               {
+                       std::cerr << "cannot add children to invalid node" << std::endl;
+                       return;
+               }
+
                for (int i = 0; i < 8; ++i)
                {
-                       node->node.getAabb().getOctant(octant, i);
+                       node->getAabb().getOctant(octant, i);
                        //OctreeNode octantNode(octant);
 
-                       Ptr newChild = createNewNode(octant);
-                       node->addChild(newChild);
+                       root_.append(node, octant);
                }
        }
 
-       void draw(Ptr node, Scalar alpha)
+       void draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
        {
-               if (!node)
+               if (!node.valid())
                {
-                       std::cerr << "null child :-(" << std::endl;
+                       std::cerr << "cannot draw null child node :-(" << std::endl;
                        return;
                }
 
-               node->node.draw(alpha);
+               node->draw(alpha);
 
-               if (!node->isLeaf())
+               for (unsigned i = 0; i < root_.children(node); ++i)
                {
-                       Ptr firstChild = node->getFirstChild();
-                       Ptr temp = firstChild;
+                       stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
 
-                       if (!firstChild)
+                       if (child.valid())
                        {
-                               std::cerr << "node is not a leaf, but has no first child :-(" << std::endl;
-                               return;
+                               draw(child, alpha);
                        }
-
-                       do
+                       else
                        {
-                               draw(temp, alpha);
-                               temp = temp->getNextSibling();
+                               std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
                        }
-                       while (temp && temp != firstChild);
+
                }
        }
 
-       void drawIfVisible(Ptr node, Scalar alpha, const Camera& cam)
+       void drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
+                       Scalar alpha, const Camera& cam)
        {
                //node.drawIfVisible(alpha, cam);
                
-               if (!node)
+               if (!node.valid())
                {
-                       std::cerr << "null child :-(" << std::endl;
+                       std::cerr << "invalid child while drawing :-(" << std::endl;
                        return;
                }
 
                Frustum::Collision collision =
-                       cam.getFrustum().containsSphere(node->node.getSphere());
+                       cam.getFrustum().containsSphere(node->getSphere());
                if (collision == Frustum::OUTSIDE) return;
 
-               collision = cam.getFrustum().containsAabb(node->node.getAabb());
+               collision = cam.getFrustum().containsAabb(node->getAabb());
                if (collision == Frustum::OUTSIDE) return;
 
 
                if (collision == Frustum::INSIDE)
                {
-                       node->node.draw(alpha);
+                       node->draw(alpha);
                }
                else // collision == Frustum::INTERSECT
                {
-                       node->node.drawIfVisible(alpha, cam);
+                       node->drawIfVisible(alpha, cam);
                }
 
-               if (!node->isLeaf())
+               if (root_.children(node) > 0)
                {
-                       Ptr firstChild = node->getFirstChild();
-                       Ptr temp = firstChild;
-
-                       if (!firstChild)
-                       {
-                               std::cerr << "node is not a leaf, but has no first child :-(" << std::endl;
-                               return;
-                       }
-
                        if (collision == Frustum::INSIDE)
                        {
-                               do
+                               for (unsigned i = 0; i < root_.children(node); ++i)
                                {
-                                       draw(temp, alpha);
-                                       temp = temp->getNextSibling();
+                                       stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
+
+                                       if (child.valid())
+                                       {
+                                               draw(child, alpha);
+                                       }
+                                       else
+                                       {
+                                               std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
+                                       }
+
                                }
-                               while (temp && temp != firstChild);
                        }
                        else // collision == Frustum::INTERSECT
                        {
-                               do
+                               for (unsigned i = 0; i < root_.children(node); ++i)
                                {
-                                       drawIfVisible(temp, alpha, cam);
-                                       temp = temp->getNextSibling();
+                                       stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
+
+                                       if (child.valid())
+                                       {
+                                               drawIfVisible(child, alpha, cam);
+                                       }
+                                       else
+                                       {
+                                               std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
+                                       }
                                }
-                               while (temp && temp != firstChild);
                        }
                }
        }
 
        void drawIfVisible(Scalar alpha, const Camera& cam)
        {
-               drawIfVisible(getThis(), alpha, cam);
+               drawIfVisible(root_.root(), alpha, cam);
        }
 
 };
index 85e5be75d9697a315e5aded091589e6ab3c8da58..6c2b42715f70c767d0a74516dec05a8965692d2f 100644 (file)
@@ -381,7 +381,7 @@ public:
                                boost::shared_ptr<Quad> quadPtr(quad);
 
                                //objects.push_back(quadPtr);
-                               Octree::add(octree, quadPtr);
+                               octree->insert(quadPtr);
                        }
                }
        }
@@ -462,7 +462,7 @@ public:
                        boost::shared_ptr<Quad> quadPtr(quad);
 
                        //objects.push_back(quad_Ptr);
-                       Octree::add(octree, quadPtr);
+                       octree->insert(quadPtr);
                }
        }
 
@@ -498,7 +498,7 @@ public:
                }
 
                //OctreeNode rootNode(maximumBounds);
-               octree = Octree::createNewNode(maximumBounds);
+               octree = OctreePtr(new Octree(maximumBounds));
 
                if ((it = rootObj.find("instructions")) != rootObj.end())
                {
diff --git a/src/Moof/Tree.hh b/src/Moof/Tree.hh
deleted file mode 100644 (file)
index b3f6a97..0000000
+++ /dev/null
@@ -1,341 +0,0 @@
-
-/*******************************************************************************
-
- Copyright (c) 2009, Charles McGarvey
- All rights reserved.
- Redistribution   and   use  in  source  and  binary  forms,  with  or  without
- modification, are permitted provided that the following conditions are met:
-   * Redistributions  of  source  code  must retain the above copyright notice,
-     this list of conditions and the following disclaimer.
-   * Redistributions  in binary form must reproduce the above copyright notice,
-     this  list of conditions and the following disclaimer in the documentation
-     and/or other materials provided with the distribution.
- THIS  SOFTWARE  IS  PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND  ANY  EXPRESS  OR  IMPLIED  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- DISCLAIMED.  IN  NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
- FOR  ANY  DIRECT,  INDIRECT,  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- DAMAGES  (INCLUDING,  BUT  NOT  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- SERVICES;  LOSS  OF  USE,  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- CAUSED  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- OR  TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-*******************************************************************************/
-
-#ifndef _MOOF_TREE_HH_
-#define _MOOF_TREE_HH_
-
-#include <boost/shared_ptr.hpp>
-#include <boost/weak_ptr.hpp>
-       
-
-namespace Mf {
-
-
-template <typename T>
-class Tree
-{
-public:
-       typedef boost::shared_ptr<Tree> Ptr;
-       typedef boost::weak_ptr<Tree>   WeakPtr;
-
-       T               node;
-
-protected:
-       WeakPtr parent_;
-       WeakPtr prevSibling_;
-       Ptr             next_;
-       WeakPtr lastDescendant_;
-
-       inline static void init(Ptr itself)
-       {
-               itself->prevSibling_ = itself;
-               itself->lastDescendant_ = itself;
-       }
-
-       Tree() {}
-
-       explicit Tree(const T& item) :
-               node(item) {}
-
-public:
-
-       inline void print() const
-       {
-               std::cout << "==================" << std::endl;
-               std::cout << "    Node: " << getThis() << std::endl;
-               std::cout << "  Parent: " << parent_.lock() << std::endl;
-               std::cout << " PrevSib: " << prevSibling_.lock() << std::endl;
-               std::cout << "    Next: " << next_ << std::endl;
-               std::cout << "LastDesc: " << lastDescendant_.lock() << std::endl;
-               //std::cout << "   Value: " << node << std::endl;
-               std::cout << "==================" << std::endl;
-       }
-
-       inline static Ptr createNewNode()
-       {
-               Ptr newNode = Ptr(new Tree<T>());
-       }
-
-       inline static Ptr createNewNode(const T& item)
-       {
-               Ptr newNode = Ptr(new Tree<T>(item));
-               init(newNode);
-               return newNode;
-       }
-
-       inline Ptr getNext() const
-       {
-               return next_;
-       }
-
-       inline Ptr getPrevious() const
-       {
-               Ptr parent = getParent();
-
-               if (parent)
-               {
-                       if (parent->getNext().get() == this)
-                       {
-                               return parent;
-                       }
-                       else
-                       {
-                               return prevSibling_.lock()->getLastDescendant();
-                       }
-               }
-
-               return Ptr();
-       }
-
-       inline Ptr getFirstChild() const
-       {
-               if (next_ && next_->getParent().get() == this)
-               {
-                       return next_;
-               }
-               
-               return Ptr();
-       }
-
-       inline Ptr getLastChild() const
-       {
-               Ptr child = getFirstChild();
-
-               if (child)
-               {
-                       child = child->prevSibling_.lock();
-               }
-
-               return child;
-       }
-
-       inline Ptr getChild(int index) const
-       {
-               Ptr child = getFirstChild();
-
-               for (int i = 0; child && i < index; ++i)
-               {
-                       child = child->getNextSibling();
-               }
-
-               return child;
-       }
-
-       inline Ptr getNextSibling() const
-       {
-               Ptr sibling = getLastDescendant()->getNext();
-
-               if (sibling && sibling->getParent() != getParent())
-               {
-                       return Ptr();
-               }
-
-               return sibling;
-       }
-
-       inline Ptr getPreviousSibling() const
-       {
-               Ptr parent = getParent();
-
-               if (parent && parent->getNext().get() != this)
-               {
-                       return prevSibling_.lock();
-               }
-
-               return Ptr();
-       }
-
-       inline Ptr getParent() const
-       {
-               return parent_.lock();
-       }
-
-       inline Ptr getLastDescendant() const
-       {
-               return lastDescendant_.lock();
-       }
-
-       inline Ptr getThis() const
-       {
-               if (next_)
-               {
-                       return next_->getPrevious();
-               }
-
-               return getLastDescendant();
-       }
-
-       inline bool isRoot() const
-       {
-               return getParent().get() == 0;
-       }
-
-       inline bool isLeaf() const
-       {
-               return getLastDescendant().get() == this;
-       }
-
-       inline bool isDescendantOf(Ptr ancestor) const
-       {
-               Ptr temp = getParent();
-
-               while (temp)
-               {
-                       if (temp.get() == this) return true;
-
-                       temp = temp->getParent();
-               }
-
-               return false;
-       }
-
-
-       class Iterator
-       {
-               Ptr current;
-
-       public:
-
-       };
-
-
-       void addChild(Ptr subtree)
-       {
-       //WeakPtr       parent_;
-       //WeakPtr       prevSibling_;
-       //Ptr           next_;
-       //WeakPtr       lastDescendant_;
-       
-               subtree->remove();
-               
-               Ptr firstChild = getFirstChild();
-               Ptr lastChild = getLastChild();
-               Ptr nextSibling = getNextSibling();
-               Ptr lastDescendant = getLastDescendant();
-               Ptr newLastDescendant = subtree->getLastDescendant();
-               Ptr parent = getThis();
-
-               // 1. If parent is leaf, set parent.next to subtree.
-
-               if (isLeaf())
-               {
-                       next_ = subtree;
-               }
-
-               // 2. Set parent.last_descendant to subtree.last_descendant.
-
-               Ptr temp = parent;
-               while (temp && temp->getLastDescendant() == lastDescendant)
-               {
-                       temp->lastDescendant_ = newLastDescendant;
-                       temp = temp->getParent();
-               }
-
-               // 3. Set subtree.parent to parent.
-
-               subtree->parent_ = parent;
-
-               // 4. Set parent.first_child.prev_sibling to subtree.
-
-               if (firstChild)
-               {
-                       firstChild->prevSibling_ = subtree;
-               }
-
-               // 5. Set subtree.prev_sibling to parent.last_child.
-               // 6. Set parent.last_child.last_descendant.next to subtree.
-               
-               if (lastChild)
-               {
-                       subtree->prevSibling_ = lastChild;
-                       lastChild->getLastDescendant()->next_ = subtree;
-               }
-               else
-               {
-                       subtree->prevSibling_ = subtree;
-               }
-
-               // 7. Set subtree.last_descendant.next to parent.next_sibling.
-
-               if (nextSibling)
-               {
-                       subtree->getLastDescendant()->next_ = nextSibling;
-               }
-       }
-
-       void remove()
-       {
-               Ptr parent = getParent();
-               Ptr prevSibling = getPreviousSibling();
-               Ptr nextSibling = getNextSibling();
-               Ptr lastDescendant = getLastDescendant();
-               Ptr previous = getPrevious();
-
-               Ptr newLastDescendant;
-
-               // 1. Fix last descendant of each direct ancestor.
-
-               if (prevSibling) newLastDescendant = prevSibling->getLastDescendant();
-               else             newLastDescendant = parent;
-
-               Ptr temp = parent;
-               while (temp && temp->getLastDescendant() == lastDescendant)
-               {
-                       temp->lastDescendant_ = newLastDescendant;
-                       temp = temp->getParent();
-               }
-
-               // 2. Fix next of previous.
-
-               if (previous)
-               {
-                       previous->next_ = nextSibling;
-               }
-
-               // 3. Fix the previous sibling of next sibling.
-
-               if (nextSibling)
-               {
-                       nextSibling->prevSibling_ = prevSibling;
-               }
-               
-               // 4. Once detached, the subtree root has no parent or siblings.
-
-               parent_.reset();
-               prevSibling_ = getThis();
-       }
-
-};
-
-
-} // namespace Mf
-
-#endif // _MOOF_TREE_HH_
-
-/** vim: set ts=4 sw=4 tw=80: *************************************************/
-
index 43767d25c94468bd7d2d3b140dff4c26e0749caf..493e6157cad7bdc2347f820cb26a1c1d406bbc39 100644 (file)
@@ -406,8 +406,6 @@ void YoinkApp::handleEvent(const Mf::Event& event)
 }
 
 
-#include <Moof/Tree.hh>
-
 
 int main(int argc, char* argv[])
 {
@@ -418,39 +416,6 @@ int main(int argc, char* argv[])
 
        int status = 0;
 
-       //Mf::Tree<int>::Ptr rootNode;
-       //Mf::Tree<int>::Ptr temp, temp2, temp3;
-
-       //rootNode = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(1));
-
-       //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(2));
-       //temp3 = temp;
-       //rootNode->addChild(temp);
-
-       //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(3));
-       //temp2 = temp;
-       //rootNode->addChild(temp);
-
-       //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(4));
-       //rootNode->addChild(temp);
-
-       //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(5));
-       //temp2->addChild(temp);
-
-       //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(6));
-       //temp2->addChild(temp);
-
-       //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(7));
-       //temp3->addChild(temp);
-
-       //temp = rootNode;
-       //while (temp)
-       //{
-               //temp->print();
-               //temp = temp->getNext();
-       //}
-       //return 0;
-
        try
        {
                YoinkApp app(argc, argv);
@@ -466,5 +431,6 @@ int main(int argc, char* argv[])
        return status;
 }
 
+
 /** vim: set ts=4 sw=4 tw=80: *************************************************/
 
This page took 0.042983 seconds and 4 git commands to generate.