X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=e3e2225f03299636137b21aa3a54aeb38fd25b38;hp=78d3aa875706cd61f4558740c7b90a8cf4f82cd3;hb=660e768e64c2c30928c7f157d5ff34195a4347fa;hpb=72d4af22710317acffab861421c4364b1780b6fe diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 78d3aa8..e3e2225 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -29,24 +29,37 @@ #ifndef _MOOF_OCTREE_HH_ #define _MOOF_OCTREE_HH_ +#include #include #include +#include + #include #include #include +#include #include #include -#include namespace Mf { +class Frustum; + + +struct OctreeNode; +typedef stlplus::ntree::iterator OctreeNodeP; + +class Octree; +typedef boost::shared_ptr OctreeP; + + struct OctreeNode : public Entity { - std::list objects; + std::list objects; OctreeNode() { @@ -64,277 +77,109 @@ struct OctreeNode : public Entity void draw(Scalar alpha) const { - std::list::const_iterator it; + std::list::const_iterator it; for (it = objects.begin(); it != objects.end(); ++it) { (*it)->draw(alpha); } + if (!objects.empty()) aabb_.draw(); // temporary } - void drawIfVisible(Scalar alpha, const Camera& cam) const + void drawIfVisible(Scalar alpha, const Frustum& frustum) const { - std::list::const_iterator it; + std::list::const_iterator it; for (it = objects.begin(); it != objects.end(); ++it) { - (*it)->drawIfVisible(alpha, cam); + (*it)->drawIfVisible(alpha, frustum); } + if (!objects.empty()) + { aabb_.draw(); + //sphere_.draw(); + } } - bool isVisible(const Camera& cam) const + bool isVisible(const Frustum& frustum) const { - if (sphere_.isVisible(cam)) + if (sphere_.isVisible(frustum)) { - return aabb_.isVisible(cam); + return aabb_.isVisible(frustum); } return false; } -}; -class Octree; -typedef boost::shared_ptr OctreePtr; + static bool compareZOrder(EntityP a, EntityP b) + { + return a->getSphere().point[2] < b->getSphere().point[2]; + } -class Octree : public Tree + void sort() + { + //std::sort(objects.begin(), objects.end(), compareZOrder); + objects.sort(compareZOrder); + } +}; + + +class Octree { + OctreeNodeP insert(EntityP entity, OctreeNodeP node); + + void addChild(OctreeNodeP node, int index); - Octree() {} + void draw(Scalar alpha, OctreeNodeP node); + void drawIfVisible(Scalar alpha, const Frustum& frustum, OctreeNodeP node); - explicit Octree(const OctreeNode& initNode) : - Tree(initNode) {} + stlplus::ntree tree_; public: - inline static OctreePtr createNewNode(const OctreeNode& item) + void print(OctreeNodeP node) { - OctreePtr newNode = OctreePtr(new Octree(item)); - init(newNode); - return newNode; + //logDebug("-----"); + //logDebug("depth to node: %d", tree_.depth(node)); + //logDebug("size of node: %d", tree_.size(node)); } - - static Tree::WeakPtr add(Ptr node, EntityPtr entity) + static OctreeP alloc(const OctreeNode& rootNode) { - Plane::Halfspace halfspace; - int octantNum = -1; - - Plane xy = node->node.getAabb().getPlaneXY(); - halfspace = xy.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - Plane xz = node->node.getAabb().getPlaneXZ(); - halfspace = xz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - Plane yz = node->node.getAabb().getPlaneYZ(); - halfspace = yz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - octantNum = 2; - } - else if (halfspace == Plane::NEGATIVE) - { - octantNum = 3; - } - } - else if (halfspace == Plane::NEGATIVE) - { - Plane yz = node->node.getAabb().getPlaneYZ(); - halfspace = yz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - octantNum = 1; - } - else if (halfspace == Plane::NEGATIVE) - { - octantNum = 0; - } - } - } - else if (halfspace == Plane::NEGATIVE) - { - Plane xz = node->node.getAabb().getPlaneXZ(); - halfspace = xz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - Plane yz = node->node.getAabb().getPlaneYZ(); - halfspace = yz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - octantNum = 6; - } - else if (halfspace == Plane::NEGATIVE) - { - octantNum = 7; - } - } - else if (halfspace == Plane::NEGATIVE) - { - Plane yz = node->node.getAabb().getPlaneYZ(); - halfspace = yz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - octantNum = 5; - } - else if (halfspace == Plane::NEGATIVE) - { - octantNum = 4; - } - } - } - - if (octantNum == -1) - { - node->node.objects.push_front(entity); - return node; - } - else - { - if (node->isLeaf()) - { - addChildren(node); - } - - Ptr child = node->getChild(octantNum); - if (child) - { - return add(child, entity); - } - else - { - std::cerr << "no child at index " << octantNum << std::endl; - return Ptr(); - } - //return WeakPtr(); - } + return OctreeP(new Octree(rootNode)); } - static void addChildren(Ptr node) + explicit Octree(const OctreeNode& rootNode) { - Aabb octant; - - for (int i = 0; i < 8; ++i) - { - node->node.getAabb().getOctant(octant, i); - //OctreeNode octantNode(octant); - - Ptr newChild = createNewNode(octant); - node->addChild(newChild); - } + tree_.insert(rootNode); } - void draw(Ptr node, Scalar alpha) + OctreeNodeP insert(EntityP entity) { - if (!node) - { - std::cerr << "null child :-(" << std::endl; - return; - } - - node->node.draw(alpha); - - if (!node->isLeaf()) - { - Ptr firstChild = node->getFirstChild(); - Ptr temp = firstChild; - - if (!firstChild) - { - std::cerr << "node is not a leaf, but has no first child :-(" << std::endl; - return; - } - - do - { - draw(temp, alpha); - temp = temp->getNextSibling(); - } - while (temp && temp != firstChild); - } + return insert(entity, tree_.root()); } - void drawIfVisible(Ptr node, Scalar alpha, const Camera& cam) - { - //node.drawIfVisible(alpha, cam); - - if (!node) - { - std::cerr << "null child :-(" << std::endl; - return; - } - - Frustum::Collision collision = - cam.getFrustum().containsSphere(node->node.getSphere()); - if (collision == Frustum::OUTSIDE) return; - - collision = cam.getFrustum().containsAabb(node->node.getAabb()); - if (collision == Frustum::OUTSIDE) return; - - - if (collision == Frustum::INSIDE) - { - node->node.draw(alpha); - } - else // collision == Frustum::INTERSECT - { - node->node.drawIfVisible(alpha, cam); - } + OctreeNodeP reinsert(EntityP entity, OctreeNodeP node); - if (!node->isLeaf()) - { - 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 - { - draw(temp, alpha); - temp = temp->getNextSibling(); - } - while (temp && temp != firstChild); - } - else // collision == Frustum::INTERSECT - { - do - { - drawIfVisible(temp, alpha, cam); - temp = temp->getNextSibling(); - } - while (temp && temp != firstChild); - } - } + void draw(Scalar alpha) + { + draw(alpha, tree_.root()); } - void drawIfVisible(Scalar alpha, const Camera& cam) + void drawIfVisible(Scalar alpha, const Frustum& frustum) { - drawIfVisible(getThis(), alpha, cam); + drawIfVisible(alpha, frustum, tree_.root()); } + void sort(); }; - } // namespace Mf #endif // _MOOF_OCTREE_HH_