X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=13ece5bb4ecd9ac0fe75f7d3b838e9bacd0bc123;hp=2ee617f3744f0baa6155c15df3a767617cb35c56;hb=71bd9dbaf1c1e3c55a9f63392a73865d8aeee7d4;hpb=29e3d45f7bbbf31eadf793c41ff2b3d9c47b7539 diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 2ee617f..13ece5b 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -29,53 +29,339 @@ #ifndef _MOOF_OCTREE_HH_ #define _MOOF_OCTREE_HH_ +#include #include #include +#include + +#include +#include +#include +#include +#include #include -#include +#include namespace Mf { -class Entity; +struct OctreeInsertable +{ + virtual ~OctreeInsertable() {} + + virtual int getOctant(const Aabb<3>& aabb) const = 0; +}; -class Octree +template +class Octree : public Entity { -public: + typedef boost::shared_ptr InsertableP; - class Node + struct Node : public Entity { - Aabb aabb_; - Vector3 center_; + std::list objects; - std::list > objects_; + Node(const Aabb<3>& aabb) + { + mAabb = aabb; + mSphere.point = mAabb.getCenter(); + mSphere.radius = (mAabb.min - mSphere.point).length(); + } - public: + void draw(Scalar alpha) const + { + mAabb.draw(alpha); + } - Node() : - aabb_(-1.0, -1.0, -1.0, 1.0, 1.0, 1.0), - center_(0.0, 0.0, 0.0) {} + void printSize() + { + logDebug("size of node %d", objects.size()); + } - Node(const Aabb& aabb) : - aabb_(aabb), - center_(aabb.getCenter()) {} - }; + void getAll(std::list& insertables) const + { + insertables.insert(insertables.end(), objects.begin(), + objects.end()); + } - Octree() : - root_(new Tree()) {} + void getIfVisible(std::list& insertables, + const Frustum& frustum) const + { + typename std::list::const_iterator it; - Octree(const Aabb& aabb) : - root_(new Tree(Node(aabb))) {} + for (it = objects.begin(); it != objects.end(); ++it) + { + if ((*it)->isVisible(frustum)) insertables.push_back(*it); + } + } + }; - Tree::WeakPtr add(EntityPtr object); +public: + typedef boost::shared_ptr Ptr; + typedef typename stlplus::ntree::iterator NodeP; + private: - Tree::Ptr root_; + + + NodeP insert(InsertableP entity, NodeP node) + { + ASSERT(node.valid() && "invalid node passed"); + ASSERT(entity && "null entity passed"); + + Aabb<3> entityAabb = entity->getAabb(); + Aabb<3> nodeAabb = node->getAabb(); + + if (!(entityAabb.max[0] < nodeAabb.max[0] && + entityAabb.min[0] > nodeAabb.min[0] && + entityAabb.max[1] < nodeAabb.max[1] && + entityAabb.min[1] > nodeAabb.min[1] && + entityAabb.max[2] < nodeAabb.max[2] && + entityAabb.min[2] > nodeAabb.min[2])) + { + node->objects.push_back(entity); + return node; + } + else + { + return insert_recurse(entity, node); + } + } + + NodeP insert_recurse(InsertableP entity, NodeP node) + { + ASSERT(node.valid() && "invalid node passed"); + ASSERT(entity && "null entity passed"); + + int octantNum = entity->getOctant(node->getAabb()); + if (octantNum == -1) + { + node->objects.push_back(entity); + return node; + } + else + { + if ((int)mTree.children(node) <= octantNum) + { + addChild(node, octantNum); + } + + NodeP child = mTree.child(node, octantNum); + ASSERT(child.valid() && "expected valid child node"); + + return insert_recurse(entity, child); + } + } + + void addChild(NodeP node, int index) + { + ASSERT(node.valid() && "invalid node passed"); + + Aabb<3> octant; + + for (int i = mTree.children(node); i <= index; ++i) + { + node->getAabb().getOctant(octant, i); + mTree.append(node, octant); + } + } + + + void getNearbyObjects(std::list& insertables, + const OctreeInsertable& entity, NodeP node) const + { + ASSERT(node.valid() && "invalid node passed"); + + node->printSize(); + + int octantNum = entity.getOctant(node->getAabb()); + if (octantNum != -1) + { + node->getAll(insertables); + + if (octantNum < (int)mTree.children(node)) + { + NodeP child = mTree.child(node, octantNum); + ASSERT(child.valid() && "expected valid child node"); + + getNearbyObjects(insertables, entity, child); + } + } + else + { + logDebug("getting all the rest..."); + getAll(insertables, node); + } + } + + + void getAll(std::list& insertables, NodeP node) const + { + ASSERT(node.valid() && "invalid node passed"); + + node->getAll(insertables); + + for (unsigned i = 0; i < mTree.children(node); ++i) + { + NodeP child = mTree.child(node, i); + ASSERT(child.valid() && "expected valid child node"); + + getAll(insertables, child); + } + } + + void getIfVisible(std::list& insertables, + const Frustum& frustum, NodeP node) const + { + ASSERT(node.valid() && "invalid node passed"); + + // try to cull by sphere + Frustum::Collision collision = frustum.contains(node->getSphere()); + if (collision == Frustum::OUTSIDE) return; + + // try to cull by aabb + collision = frustum.contains(node->getAabb()); + if (collision == Frustum::OUTSIDE) return; + + + if (collision == Frustum::INSIDE) + { + node->getAll(insertables); + } + else // collision == Frustum::INTERSECT + { + node->getIfVisible(insertables, frustum); + } + + if (mTree.children(node) > 0) + { + if (collision == Frustum::INSIDE) + { + for (unsigned i = 0; i < mTree.children(node); ++i) + { + NodeP child = mTree.child(node, i); + ASSERT(child.valid() && "expected valid child node"); + + getAll(insertables, child); + } + } + else // collision == Frustum::INTERSECT + { + for (unsigned i = 0; i < mTree.children(node); ++i) + { + NodeP child = mTree.child(node, i); + ASSERT(child.valid() && "expected valid child node"); + + getIfVisible(insertables, frustum, child); + } + } + } + } + + + mutable stlplus::ntree mTree; + + +public: + + void print(NodeP node) + { + logInfo("-----"); + logInfo("depth to node: %d", mTree.depth(node)); + logInfo("size of node: %d", mTree.size(node)); + } + + static Ptr alloc(const Node& rootNode) + { + return Ptr(new Octree(rootNode)); + } + + explicit Octree(const Node& rootNode) + { + mTree.insert(rootNode); + } + + + NodeP insert(InsertableP entity) + { + return insert(entity, mTree.root()); + } + + void remove(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); + + if (it != node->objects.end()) + { + node->objects.erase(it); + } + } + + + NodeP reinsert(InsertableP entity, NodeP node) + { + remove(entity, node); + return insert(entity); + } + + + void draw(Scalar alpha) const + { + std::list objects; + getAll(objects); + + typename std::list::const_iterator it; + for (it = objects.begin(); it != objects.end(); ++it) + { + (*it)->draw(alpha); + } + } + + void drawIfVisible(Scalar alpha, const Frustum& frustum) const + { + std::list objects; + getIfVisible(objects, frustum); + //getNearbyObjects(objects, *savedObj); + + typename std::list::const_iterator it; + for (it = objects.begin(); it != objects.end(); ++it) + { + (*it)->draw(alpha); + } + } + + + void getAll(std::list& insertables) const + { + getAll(insertables, mTree.root()); + } + + void getIfVisible(std::list& insertables, + const Frustum& frustum) const + { + getIfVisible(insertables, frustum, mTree.root()); + } + + mutable const OctreeInsertable* savedObj; + + + void getNearbyObjects(std::list& insertables, + const OctreeInsertable& entity) const + { + logDebug("--- GETTING NEARBY"); + getNearbyObjects(insertables, entity, mTree.root()); + logDebug("---"); + savedObj = &entity; + } };