X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=cdac62a29071f4eeaeb51c48c055e84db1a029dc;hp=e3e2225f03299636137b21aa3a54aeb38fd25b38;hb=a4debfe4a5f5d339410788971b698ba00cb7f09c;hpb=892da43bf5796e7c5f593a6d0f53bd797a36bd3e diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index e3e2225..cdac62a 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -39,6 +39,7 @@ #include #include #include +#include #include #include #include @@ -47,136 +48,260 @@ namespace Mf { -class Frustum; +//class Octree; +//typedef boost::shared_ptr OctreeP; +//class Octree::Node; +//typedef stlplus::ntree::iterator OctreeNodeP; -struct OctreeNode; -typedef stlplus::ntree::iterator OctreeNodeP; -class Octree; -typedef boost::shared_ptr OctreeP; +struct OctreeInsertable +{ + virtual ~OctreeInsertable() {} + + virtual bool isInsideAabb(const Aabb& aabb) const = 0; + virtual int getOctant(const Aabb& aabb) const = 0; +}; -struct OctreeNode : public Entity +template +class Octree : public Entity { - std::list objects; + typedef boost::shared_ptr InsertableP; - OctreeNode() + struct Node : public Entity { - aabb_.min = Vector3(-1.0, -1.0, -1.0); - aabb_.max = Vector3(1.0, 1.0, 1.0); - sphere_.init(Vector3(0.0, 0.0, 0.0), 1.41421); - } + std::list objects; - OctreeNode(const Aabb& aabb) - { - aabb_ = aabb; - sphere_.point = aabb.getCenter(); - sphere_.radius = (aabb.min - sphere_.point).length(); - } + Aabb aabb; + Sphere sphere; - void draw(Scalar alpha) const - { - std::list::const_iterator it; + Node(const Aabb& box) : + aabb(box) + { + sphere.point = aabb.getCenter(); + sphere.radius = (aabb.min - sphere.point).length(); + } - for (it = objects.begin(); it != objects.end(); ++it) + void draw(Scalar alpha) const { - (*it)->draw(alpha); + typename std::list::const_iterator it; + + for (it = objects.begin(); it != objects.end(); ++it) + { + (*it)->draw(alpha); + } + + if (!objects.empty()) + aabb.draw(); // temporary } - if (!objects.empty()) - aabb_.draw(); // temporary - } + void drawIfVisible(Scalar alpha, const Frustum& frustum) const + { + typename std::list::const_iterator it; + + for (it = objects.begin(); it != objects.end(); ++it) + { + (*it)->drawIfVisible(alpha, frustum); + } + + if (!objects.empty()) + { + //aabb.draw(); + //sphere.draw(); + } + } - void drawIfVisible(Scalar alpha, const Frustum& frustum) const - { - std::list::const_iterator it; - for (it = objects.begin(); it != objects.end(); ++it) + bool isVisible(const Frustum& frustum) const { - (*it)->drawIfVisible(alpha, frustum); + if (sphere.isVisible(frustum)) + { + return aabb.isVisible(frustum); + } + + return false; } + }; - if (!objects.empty()) + +public: + + typedef boost::shared_ptr Ptr; + typedef typename stlplus::ntree::iterator NodeP; + +private: + + + NodeP insert(InsertableP entity, NodeP node) + { + ASSERT(node.valid() && "invalid node passed"); + ASSERT(entity && "null entity passed"); + + if (entity->isInsideAabb(node->aabb)) { - aabb_.draw(); - //sphere_.draw(); + return insert_recurse(entity, node); + } + else + { + node->objects.push_back(entity); + return node; } } - - bool isVisible(const Frustum& frustum) const + NodeP insert_recurse(InsertableP entity, NodeP node) { - if (sphere_.isVisible(frustum)) + ASSERT(node.valid() && "invalid node passed"); + ASSERT(entity && "null entity passed"); + + int octantNum = entity->getOctant(node->aabb); + if (octantNum == -1) { - return aabb_.isVisible(frustum); + node->objects.push_back(entity); + return node; } + else + { + if ((int)tree_.children(node) <= octantNum) + { + addChild(node, octantNum); + } - return false; - } + NodeP child = tree_.child(node, octantNum); + ASSERT(child.valid() && "expected valid child node"); + return insert(entity, child); + } + } - static bool compareZOrder(EntityP a, EntityP b) + void addChild(NodeP node, int index) { - return a->getSphere().point[2] < b->getSphere().point[2]; + ASSERT(node.valid() && "invalid node passed"); + + Aabb octant; + + for (int i = tree_.children(node); i <= index; ++i) + { + node->aabb.getOctant(octant, i); + tree_.append(node, octant); + } } - void sort() + + void draw(Scalar alpha, NodeP node) const { - //std::sort(objects.begin(), objects.end(), compareZOrder); - objects.sort(compareZOrder); + ASSERT(node.valid() && "invalid node passed"); + + node->draw(alpha); + + for (unsigned i = 0; i < tree_.children(node); ++i) + { + NodeP child = tree_.child(node, i); + ASSERT(child.valid() && "expected valid child node"); + + draw(alpha, child); + } } -}; + void drawIfVisible(Scalar alpha, const Frustum& frustum, NodeP node) const + { + ASSERT(node.valid() && "invalid node passed"); -class Octree -{ - OctreeNodeP insert(EntityP entity, OctreeNodeP node); - - void addChild(OctreeNodeP node, int index); + // try to cull by sphere + Frustum::Collision collision = frustum.contains(node->sphere); + if (collision == Frustum::OUTSIDE) return; + + // try to cull by aabb + collision = frustum.contains(node->aabb); + if (collision == Frustum::OUTSIDE) return; + + + if (collision == Frustum::INSIDE) + { + node->draw(alpha); + } + else // collision == Frustum::INTERSECT + { + node->drawIfVisible(alpha, frustum); + } - void draw(Scalar alpha, OctreeNodeP node); - void drawIfVisible(Scalar alpha, const Frustum& frustum, OctreeNodeP node); + if (tree_.children(node) > 0) + { + if (collision == Frustum::INSIDE) + { + for (unsigned i = 0; i < tree_.children(node); ++i) + { + NodeP child = tree_.child(node, i); + ASSERT(child.valid() && "expected valid child node"); + + draw(alpha, child); + } + } + else // collision == Frustum::INTERSECT + { + for (unsigned i = 0; i < tree_.children(node); ++i) + { + NodeP child = tree_.child(node, i); + ASSERT(child.valid() && "expected valid child node"); + + drawIfVisible(alpha, frustum, child); + } + } + } + } + + mutable stlplus::ntree tree_; - stlplus::ntree tree_; public: - void print(OctreeNodeP node) + void print(NodeP node) { //logDebug("-----"); //logDebug("depth to node: %d", tree_.depth(node)); //logDebug("size of node: %d", tree_.size(node)); } - static OctreeP alloc(const OctreeNode& rootNode) + static Ptr alloc(const Node& rootNode) { - return OctreeP(new Octree(rootNode)); + return Ptr(new Octree(rootNode)); } - explicit Octree(const OctreeNode& rootNode) + explicit Octree(const Node& rootNode) { tree_.insert(rootNode); } - OctreeNodeP insert(EntityP entity) + NodeP insert(InsertableP entity) { return insert(entity, tree_.root()); } - OctreeNodeP reinsert(EntityP entity, OctreeNodeP node); + NodeP reinsert(InsertableP entity, NodeP node) + { + ASSERT(entity && "null entity passed"); + ASSERT(node.valid() && "invalid node passed"); + + typename std::list::iterator it; + it = std::find(node->objects.begin(), node->objects.end(), entity); - void draw(Scalar alpha) + if (it != node->objects.end()) + { + node->objects.erase(it); + } + + return insert(entity); + } + + void draw(Scalar alpha) const { draw(alpha, tree_.root()); } - void drawIfVisible(Scalar alpha, const Frustum& frustum) + void drawIfVisible(Scalar alpha, const Frustum& frustum) const { drawIfVisible(alpha, frustum, tree_.root()); } - - void sort(); };