X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=1c57ff2d3317fe83d10aa6972093683cb634556f;hp=78d3aa875706cd61f4558740c7b90a8cf4f82cd3;hb=329a48e4c4c2f5f2904b913938fc53154c48b825;hpb=72d4af22710317acffab861421c4364b1780b6fe 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); } };