From 329a48e4c4c2f5f2904b913938fc53154c48b825 Mon Sep 17 00:00:00 2001 From: Charles McGarvey Date: Fri, 21 Aug 2009 01:15:59 -0600 Subject: [PATCH] now using stlplus containers, especially ntree --- data/scenes/Test.json | 2 +- src/Makefile.am | 4 +- src/Moof/Octree.hh | 157 ++++++++++--------- src/Moof/Scene.cc | 6 +- src/Moof/Tree.hh | 341 ------------------------------------------ src/YoinkApp.cc | 36 +---- 6 files changed, 92 insertions(+), 454 deletions(-) delete mode 100644 src/Moof/Tree.hh diff --git a/data/scenes/Test.json b/data/scenes/Test.json index db9ba5d..562a3be 100644 --- a/data/scenes/Test.json +++ b/data/scenes/Test.json @@ -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": [ diff --git a/src/Makefile.am b/src/Makefile.am index 1d320e6..f4122de 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -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" diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 78d3aa8..1c57ff2 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -33,12 +33,13 @@ #include +#include + #include #include #include #include #include -#include namespace Mf { @@ -102,40 +103,45 @@ struct OctreeNode : public Entity class Octree; typedef boost::shared_ptr OctreePtr; -class Octree : public Tree +class Octree { - Octree() {} - - explicit Octree(const OctreeNode& initNode) : - Tree(initNode) {} + stlplus::ntree 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::WeakPtr add(Ptr node, EntityPtr entity) + void insert(stlplus::ntree::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::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::iterator(); } //return WeakPtr(); } } - static void addChildren(Ptr node) + void addChildren(stlplus::ntree::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::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::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::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::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::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); } }; diff --git a/src/Moof/Scene.cc b/src/Moof/Scene.cc index 85e5be7..6c2b427 100644 --- a/src/Moof/Scene.cc +++ b/src/Moof/Scene.cc @@ -381,7 +381,7 @@ public: boost::shared_ptr quadPtr(quad); //objects.push_back(quadPtr); - Octree::add(octree, quadPtr); + octree->insert(quadPtr); } } } @@ -462,7 +462,7 @@ public: boost::shared_ptr 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 index b3f6a97..0000000 --- a/src/Moof/Tree.hh +++ /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 -#include - - -namespace Mf { - - -template -class Tree -{ -public: - typedef boost::shared_ptr Ptr; - typedef boost::weak_ptr 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()); - } - - inline static Ptr createNewNode(const T& item) - { - Ptr newNode = Ptr(new Tree(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: *************************************************/ - diff --git a/src/YoinkApp.cc b/src/YoinkApp.cc index 43767d2..493e615 100644 --- a/src/YoinkApp.cc +++ b/src/YoinkApp.cc @@ -406,8 +406,6 @@ void YoinkApp::handleEvent(const Mf::Event& event) } -#include - int main(int argc, char* argv[]) { @@ -418,39 +416,6 @@ int main(int argc, char* argv[]) int status = 0; - //Mf::Tree::Ptr rootNode; - //Mf::Tree::Ptr temp, temp2, temp3; - - //rootNode = Mf::Tree::Ptr(Mf::Tree::createNewNode(1)); - - //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(2)); - //temp3 = temp; - //rootNode->addChild(temp); - - //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(3)); - //temp2 = temp; - //rootNode->addChild(temp); - - //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(4)); - //rootNode->addChild(temp); - - //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(5)); - //temp2->addChild(temp); - - //temp = Mf::Tree::Ptr(Mf::Tree::createNewNode(6)); - //temp2->addChild(temp); - - //temp = Mf::Tree::Ptr(Mf::Tree::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: *************************************************/ -- 2.45.2