X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=13ece5bb4ecd9ac0fe75f7d3b838e9bacd0bc123;hp=cdac62a29071f4eeaeb51c48c055e84db1a029dc;hb=71bd9dbaf1c1e3c55a9f63392a73865d8aeee7d4;hpb=a4debfe4a5f5d339410788971b698ba00cb7f09c diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index cdac62a..13ece5b 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -48,19 +48,11 @@ namespace Mf { -//class Octree; -//typedef boost::shared_ptr OctreeP; - -//class Octree::Node; -//typedef stlplus::ntree::iterator OctreeNodeP; - - struct OctreeInsertable { virtual ~OctreeInsertable() {} - virtual bool isInsideAabb(const Aabb& aabb) const = 0; - virtual int getOctant(const Aabb& aabb) const = 0; + virtual int getOctant(const Aabb<3>& aabb) const = 0; }; @@ -73,55 +65,39 @@ class Octree : public Entity { std::list objects; - Aabb aabb; - Sphere sphere; - - Node(const Aabb& box) : - aabb(box) + Node(const Aabb<3>& aabb) { - sphere.point = aabb.getCenter(); - sphere.radius = (aabb.min - sphere.point).length(); + mAabb = aabb; + mSphere.point = mAabb.getCenter(); + mSphere.radius = (mAabb.min - mSphere.point).length(); } void draw(Scalar alpha) const { - typename std::list::const_iterator it; + mAabb.draw(alpha); + } - for (it = objects.begin(); it != objects.end(); ++it) - { - (*it)->draw(alpha); - } + void printSize() + { + logDebug("size of node %d", objects.size()); + } - if (!objects.empty()) - aabb.draw(); // temporary + void getAll(std::list& insertables) const + { + insertables.insert(insertables.end(), objects.begin(), + objects.end()); } - void drawIfVisible(Scalar alpha, const Frustum& frustum) const + void getIfVisible(std::list& insertables, + 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(); + if ((*it)->isVisible(frustum)) insertables.push_back(*it); } } - - - bool isVisible(const Frustum& frustum) const - { - if (sphere.isVisible(frustum)) - { - return aabb.isVisible(frustum); - } - - return false; - } }; @@ -138,14 +114,22 @@ private: ASSERT(node.valid() && "invalid node passed"); ASSERT(entity && "null entity passed"); - if (entity->isInsideAabb(node->aabb)) + 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])) { - return insert_recurse(entity, node); + node->objects.push_back(entity); + return node; } else { - node->objects.push_back(entity); - return node; + return insert_recurse(entity, node); } } @@ -154,7 +138,7 @@ private: ASSERT(node.valid() && "invalid node passed"); ASSERT(entity && "null entity passed"); - int octantNum = entity->getOctant(node->aabb); + int octantNum = entity->getOctant(node->getAabb()); if (octantNum == -1) { node->objects.push_back(entity); @@ -162,15 +146,15 @@ private: } else { - if ((int)tree_.children(node) <= octantNum) + if ((int)mTree.children(node) <= octantNum) { addChild(node, octantNum); } - NodeP child = tree_.child(node, octantNum); + NodeP child = mTree.child(node, octantNum); ASSERT(child.valid() && "expected valid child node"); - return insert(entity, child); + return insert_recurse(entity, child); } } @@ -178,88 +162,118 @@ private: { ASSERT(node.valid() && "invalid node passed"); - Aabb octant; + Aabb<3> octant; - for (int i = tree_.children(node); i <= index; ++i) + for (int i = mTree.children(node); i <= index; ++i) { - node->aabb.getOctant(octant, i); - tree_.append(node, octant); + node->getAabb().getOctant(octant, i); + mTree.append(node, octant); } } - void draw(Scalar alpha, NodeP node) const + void getNearbyObjects(std::list& insertables, + const OctreeInsertable& entity, NodeP node) const { ASSERT(node.valid() && "invalid node passed"); - node->draw(alpha); + node->printSize(); - for (unsigned i = 0; i < tree_.children(node); ++i) + int octantNum = entity.getOctant(node->getAabb()); + if (octantNum != -1) { - NodeP child = tree_.child(node, i); + 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"); - draw(alpha, child); + getAll(insertables, child); } } - void drawIfVisible(Scalar alpha, const Frustum& frustum, NodeP node) const + 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->sphere); + Frustum::Collision collision = frustum.contains(node->getSphere()); if (collision == Frustum::OUTSIDE) return; // try to cull by aabb - collision = frustum.contains(node->aabb); + collision = frustum.contains(node->getAabb()); if (collision == Frustum::OUTSIDE) return; if (collision == Frustum::INSIDE) { - node->draw(alpha); + node->getAll(insertables); } else // collision == Frustum::INTERSECT { - node->drawIfVisible(alpha, frustum); + node->getIfVisible(insertables, frustum); } - if (tree_.children(node) > 0) + if (mTree.children(node) > 0) { if (collision == Frustum::INSIDE) { - for (unsigned i = 0; i < tree_.children(node); ++i) + for (unsigned i = 0; i < mTree.children(node); ++i) { - NodeP child = tree_.child(node, i); + NodeP child = mTree.child(node, i); ASSERT(child.valid() && "expected valid child node"); - draw(alpha, child); + getAll(insertables, child); } } else // collision == Frustum::INTERSECT { - for (unsigned i = 0; i < tree_.children(node); ++i) + for (unsigned i = 0; i < mTree.children(node); ++i) { - NodeP child = tree_.child(node, i); + NodeP child = mTree.child(node, i); ASSERT(child.valid() && "expected valid child node"); - drawIfVisible(alpha, frustum, child); + getIfVisible(insertables, frustum, child); } } } } - mutable stlplus::ntree tree_; + + mutable stlplus::ntree mTree; public: void print(NodeP node) { - //logDebug("-----"); - //logDebug("depth to node: %d", tree_.depth(node)); - //logDebug("size of node: %d", tree_.size(node)); + logInfo("-----"); + logInfo("depth to node: %d", mTree.depth(node)); + logInfo("size of node: %d", mTree.size(node)); } static Ptr alloc(const Node& rootNode) @@ -269,15 +283,16 @@ public: explicit Octree(const Node& rootNode) { - tree_.insert(rootNode); + mTree.insert(rootNode); } + NodeP insert(InsertableP entity) { - return insert(entity, tree_.root()); + return insert(entity, mTree.root()); } - NodeP reinsert(InsertableP entity, NodeP node) + void remove(InsertableP entity, NodeP node) { ASSERT(entity && "null entity passed"); ASSERT(node.valid() && "invalid node passed"); @@ -289,18 +304,63 @@ public: { node->objects.erase(it); } + } + + NodeP reinsert(InsertableP entity, NodeP node) + { + remove(entity, node); return insert(entity); } + void draw(Scalar alpha) const { - draw(alpha, tree_.root()); + 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 { - drawIfVisible(alpha, frustum, tree_.root()); + 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; } };