X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=e3e2225f03299636137b21aa3a54aeb38fd25b38;hp=1c57ff2d3317fe83d10aa6972093683cb634556f;hb=660e768e64c2c30928c7f157d5ff34195a4347fa;hpb=329a48e4c4c2f5f2904b913938fc53154c48b825 diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 1c57ff2..e3e2225 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -29,6 +29,7 @@ #ifndef _MOOF_OCTREE_HH_ #define _MOOF_OCTREE_HH_ +#include #include #include @@ -38,6 +39,7 @@ #include #include #include +#include #include #include @@ -45,9 +47,19 @@ 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() { @@ -65,291 +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; - -class Octree -{ - stlplus::ntree root_; -public: - - explicit Octree(const OctreeNode& rootNode) + static bool compareZOrder(EntityP a, EntityP b) { - root_.insert(rootNode); + return a->getSphere().point[2] < b->getSphere().point[2]; } - void insert(EntityPtr entity) + void sort() { - insert(root_.root(), entity); + //std::sort(objects.begin(), objects.end(), compareZOrder); + objects.sort(compareZOrder); } +}; - void insert(stlplus::ntree::iterator node, EntityPtr entity) - { - Plane::Halfspace halfspace; - int octantNum = -1; - if (!node.valid()) - { - std::cerr << "cannot insert into invalid node" << std::endl; - return; - } +class Octree +{ + OctreeNodeP insert(EntityP entity, OctreeNodeP node); + + void addChild(OctreeNodeP node, int index); - Plane xy = node->getAabb().getPlaneXY(); - halfspace = xy.intersectsSphere(entity->getSphere()); + void draw(Scalar alpha, OctreeNodeP node); + void drawIfVisible(Scalar alpha, const Frustum& frustum, OctreeNodeP node); - if (halfspace == Plane::POSITIVE) - { - Plane xz = node->getAabb().getPlaneXZ(); - halfspace = xz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - Plane yz = 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->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->getAabb().getPlaneXZ(); - halfspace = xz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - Plane yz = 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->getAabb().getPlaneYZ(); - halfspace = yz.intersectsSphere(entity->getSphere()); - - if (halfspace == Plane::POSITIVE) - { - octantNum = 5; - } - else if (halfspace == Plane::NEGATIVE) - { - octantNum = 4; - } - } - } + stlplus::ntree tree_; - if (octantNum == -1) - { - node->objects.push_front(entity); - //return node; - } - else - { - if (root_.children(node) == 0) - { - addChildren(node); - } - - stlplus::ntree::iterator child = root_.child(node, octantNum); - - if (child.valid()) - { - return insert(child, entity); - } - else - { - std::cerr << "expected but found no child at index " << octantNum << std::endl; - //return stlplus::ntree::iterator(); - } - //return WeakPtr(); - } - } +public: - void addChildren(stlplus::ntree::iterator node) + void print(OctreeNodeP 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->getAabb().getOctant(octant, i); - //OctreeNode octantNode(octant); - - root_.append(node, octant); - } + //logDebug("-----"); + //logDebug("depth to node: %d", tree_.depth(node)); + //logDebug("size of node: %d", tree_.size(node)); } - void draw(stlplus::ntree::iterator node, Scalar alpha) + static OctreeP alloc(const OctreeNode& rootNode) { - if (!node.valid()) - { - std::cerr << "cannot draw null child node :-(" << std::endl; - return; - } - - node->draw(alpha); - - for (unsigned i = 0; i < root_.children(node); ++i) - { - 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; - } - - } + return OctreeP(new Octree(rootNode)); } - void drawIfVisible(stlplus::ntree::iterator node, - Scalar alpha, const Camera& cam) + explicit Octree(const OctreeNode& rootNode) { - //node.drawIfVisible(alpha, cam); - - if (!node.valid()) - { - std::cerr << "invalid child while drawing :-(" << std::endl; - return; - } - - Frustum::Collision collision = - cam.getFrustum().containsSphere(node->getSphere()); - if (collision == Frustum::OUTSIDE) return; + tree_.insert(rootNode); + } - collision = cam.getFrustum().containsAabb(node->getAabb()); - if (collision == Frustum::OUTSIDE) return; + OctreeNodeP insert(EntityP entity) + { + return insert(entity, tree_.root()); + } + OctreeNodeP reinsert(EntityP entity, OctreeNodeP node); - if (collision == Frustum::INSIDE) - { - node->draw(alpha); - } - else // collision == Frustum::INTERSECT - { - node->drawIfVisible(alpha, cam); - } - - if (root_.children(node) > 0) - { - if (collision == Frustum::INSIDE) - { - for (unsigned i = 0; i < root_.children(node); ++i) - { - 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; - } - - } - } - else // collision == Frustum::INTERSECT - { - for (unsigned i = 0; i < root_.children(node); ++i) - { - 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; - } - } - } - } + void draw(Scalar alpha) + { + draw(alpha, tree_.root()); } - void drawIfVisible(Scalar alpha, const Camera& cam) + void drawIfVisible(Scalar alpha, const Frustum& frustum) { - drawIfVisible(root_.root(), alpha, cam); + drawIfVisible(alpha, frustum, tree_.root()); } + void sort(); }; - } // namespace Mf #endif // _MOOF_OCTREE_HH_