X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;fp=src%2FMoof%2FOctree.hh;h=0000000000000000000000000000000000000000;hp=155995934728e73b7721cc7c3f4765567d6bacb6;hb=831f04d4bc19a390415ac0bbac4331c7a65509bc;hpb=299af4f2047e767e5d79501c26444473bda64c64 diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh deleted file mode 100644 index 1559959..0000000 --- a/src/Moof/Octree.hh +++ /dev/null @@ -1,353 +0,0 @@ - -/*] Copyright (c) 2009-2010, Charles McGarvey [************************** -**] All rights reserved. -* -* vi:ts=4 sw=4 tw=75 -* -* Distributable under the terms and conditions of the 2-clause BSD license; -* see the file COPYING for a complete text of the license. -* -**************************************************************************/ - -#ifndef _MOOF_OCTREE_HH_ -#define _MOOF_OCTREE_HH_ - -#include -#include - -#include -#include - -#include -#include -#include -#include -#include -#include -#include - - -namespace Mf { - - -struct OctreeInsertable -{ - virtual ~OctreeInsertable() {} - - virtual int getOctant(const Aabb<3>& aabb) const = 0; -}; - - -template -class Octree : public Entity -{ - typedef boost::shared_ptr InsertableP; - - struct Node : public Entity - { - std::list objects; - - Node(const Aabb<3>& aabb) - { - mAabb = aabb; - mSphere.point = mAabb.getCenter(); - mSphere.radius = (mAabb.min - mSphere.point).length(); - } - - void draw(Scalar alpha) const - { - mAabb.draw(alpha); - } - - void printSize() - { - logInfo << "size of node " << objects.size() << std::endl; - } - - void getAll(std::list& insertables) const - { - insertables.insert(insertables.end(), objects.begin(), - objects.end()); - } - - void getIfVisible(std::list& insertables, - const Frustum& frustum) const - { - typename std::list::const_iterator it; - - for (it = objects.begin(); it != objects.end(); ++it) - { - if ((*it)->isVisible(frustum)) insertables.push_back(*it); - } - } - }; - - -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"); - - 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 - { - logInfo("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: " << mTree.depth(node) << std::endl; - logInfo << "size of node: " << mTree.size(node) << std::endl; - } - - 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 - { - logInfo("--- GETTING NEARBY"); - getNearbyObjects(insertables, entity, mTree.root()); - logInfo("---"); - savedObj = &entity; - } -}; - - -} // namespace Mf - -#endif // _MOOF_OCTREE_HH_ -