+++ /dev/null
-
-/*] 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 <algorithm>
-#include <list>
-
-#include <boost/shared_ptr.hpp>
-#include <stlplus/ntree.hpp>
-
-#include <Moof/Aabb.hh>
-#include <Moof/Drawable.hh>
-#include <Moof/Entity.hh>
-#include <Moof/Frustum.hh>
-#include <Moof/Log.hh>
-#include <Moof/Math.hh>
-#include <Moof/Sphere.hh>
-
-
-namespace Mf {
-
-
-struct OctreeInsertable
-{
- virtual ~OctreeInsertable() {}
-
- virtual int getOctant(const Aabb<3>& aabb) const = 0;
-};
-
-
-template <class T>
-class Octree : public Entity
-{
- typedef boost::shared_ptr<T> InsertableP;
-
- struct Node : public Entity
- {
- std::list<InsertableP> 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<InsertableP>& insertables) const
- {
- insertables.insert(insertables.end(), objects.begin(),
- objects.end());
- }
-
- void getIfVisible(std::list<InsertableP>& insertables,
- const Frustum& frustum) const
- {
- typename std::list<InsertableP>::const_iterator it;
-
- for (it = objects.begin(); it != objects.end(); ++it)
- {
- if ((*it)->isVisible(frustum)) insertables.push_back(*it);
- }
- }
- };
-
-
-public:
-
- typedef boost::shared_ptr<Octree> Ptr;
- typedef typename stlplus::ntree<Node>::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<InsertableP>& 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<InsertableP>& 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<InsertableP>& 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<Node> 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<InsertableP>::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<InsertableP> objects;
- getAll(objects);
-
- typename std::list<InsertableP>::const_iterator it;
- for (it = objects.begin(); it != objects.end(); ++it)
- {
- (*it)->draw(alpha);
- }
- }
-
- void drawIfVisible(Scalar alpha, const Frustum& frustum) const
- {
- std::list<InsertableP> objects;
- getIfVisible(objects, frustum);
- //getNearbyObjects(objects, *savedObj);
-
- typename std::list<InsertableP>::const_iterator it;
- for (it = objects.begin(); it != objects.end(); ++it)
- {
- (*it)->draw(alpha);
- }
- }
-
-
- void getAll(std::list<InsertableP>& insertables) const
- {
- getAll(insertables, mTree.root());
- }
-
- void getIfVisible(std::list<InsertableP>& insertables,
- const Frustum& frustum) const
- {
- getIfVisible(insertables, frustum, mTree.root());
- }
-
- mutable const OctreeInsertable* savedObj;
-
-
- void getNearbyObjects(std::list<InsertableP>& insertables,
- const OctreeInsertable& entity) const
- {
- logInfo("--- GETTING NEARBY");
- getNearbyObjects(insertables, entity, mTree.root());
- logInfo("---");
- savedObj = &entity;
- }
-};
-
-
-} // namespace Mf
-
-#endif // _MOOF_OCTREE_HH_
-
projects / chaz / yoink / blobdiff