X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=155995934728e73b7721cc7c3f4765567d6bacb6;hp=186961f00e7b3d28a55ea7e6bef9a69c7aceb945;hb=c78934a448d0126709fccec3d5a636b3baa87da4;hpb=25aefe01ef7dbdb603c51411e04b0d6a6107684f diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 186961f..1559959 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -1,30 +1,13 @@ -/******************************************************************************* - - Copyright (c) 2009, Charles McGarvey - All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions are met: - - * Redistributions of source code must retain the above copyright notice, - this list of conditions and the following disclaimer. - * Redistributions in binary form must reproduce the above copyright notice, - this list of conditions and the following disclaimer in the documentation - and/or other materials provided with the distribution. - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE - DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE - FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR - SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER - CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, - OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - -*******************************************************************************/ +/*] 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_ @@ -33,12 +16,12 @@ #include #include - #include #include #include #include +#include #include #include #include @@ -47,128 +30,320 @@ namespace Mf { -class Frustum; - - -struct OctreeNode; -typedef stlplus::ntree::iterator OctreeNodeP; +struct OctreeInsertable +{ + virtual ~OctreeInsertable() {} -class Octree; -typedef boost::shared_ptr OctreeP; + virtual int getOctant(const Aabb<3>& 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; + + 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: - OctreeNode(const Aabb& aabb) + + NodeP insert(InsertableP entity, NodeP node) { - aabb_ = aabb; - sphere_.point = aabb.getCenter(); - sphere_.radius = (aabb.min - sphere_.point).length(); + 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); + } } - void draw(Scalar alpha) const + NodeP insert_recurse(InsertableP entity, NodeP node) { - std::list::const_iterator it; + ASSERT(node.valid() && "invalid node passed"); + ASSERT(entity && "null entity passed"); - for (it = objects.begin(); it != objects.end(); ++it) + int octantNum = entity->getOctant(node->getAabb()); + if (octantNum == -1) { - (*it)->draw(alpha); + 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"); - if (!objects.empty()) - aabb_.draw(); // temporary + return insert_recurse(entity, child); + } } - void drawIfVisible(Scalar alpha, const Frustum& frustum) const + void addChild(NodeP node, int index) { - std::list::const_iterator it; + ASSERT(node.valid() && "invalid node passed"); - for (it = objects.begin(); it != objects.end(); ++it) + Aabb<3> octant; + + for (int i = mTree.children(node); i <= index; ++i) { - (*it)->drawIfVisible(alpha, frustum); + node->getAabb().getOctant(octant, i); + mTree.append(node, octant); } + } - if (!objects.empty()) - aabb_.draw(); + + 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); + } } - bool isVisible(const Frustum& frustum) const + 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 { - if (sphere_.isVisible(frustum)) + 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) { - return aabb_.isVisible(frustum); + node->getAll(insertables); + } + else // collision == Frustum::INTERSECT + { + node->getIfVisible(insertables, frustum); } - return false; + 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); + } + } + } } - static bool compareZOrder(EntityP a, EntityP b) + mutable stlplus::ntree mTree; + + +public: + + void print(NodeP node) { - return a->getSphere().point[2] < b->getSphere().point[2]; + logInfo("-----"); + logInfo << "depth to node: " << mTree.depth(node) << std::endl; + logInfo << "size of node: " << mTree.size(node) << std::endl; } - void sort() + static Ptr alloc(const Node& rootNode) { - //std::sort(objects.begin(), objects.end(), compareZOrder); - objects.sort(compareZOrder); + return Ptr(new Octree(rootNode)); } -}; + explicit Octree(const Node& rootNode) + { + mTree.insert(rootNode); + } -class Octree -{ - OctreeNodeP insert(EntityP entity, OctreeNodeP node); - - void addChild(OctreeNodeP node, int index); - void draw(Scalar alpha, OctreeNodeP node); - void drawIfVisible(Scalar alpha, const Frustum& frustum, OctreeNodeP node); + NodeP insert(InsertableP entity) + { + return insert(entity, mTree.root()); + } - stlplus::ntree tree_; + void remove(InsertableP entity, NodeP node) + { + ASSERT(entity && "null entity passed"); + ASSERT(node.valid() && "invalid node passed"); -public: + typename std::list::iterator it; + it = std::find(node->objects.begin(), node->objects.end(), entity); - void print(OctreeNodeP node) - { - //logDebug("-----"); - //logDebug("depth to node: %d", tree_.depth(node)); - //logDebug("size of node: %d", tree_.size(node)); + if (it != node->objects.end()) + { + node->objects.erase(it); + } } - static OctreeP alloc(const OctreeNode& rootNode) + + NodeP reinsert(InsertableP entity, NodeP node) { - return OctreeP(new Octree(rootNode)); + remove(entity, node); + return insert(entity); } - explicit Octree(const OctreeNode& rootNode) + + void draw(Scalar alpha) const { - tree_.insert(rootNode); + std::list objects; + getAll(objects); + + typename std::list::const_iterator it; + for (it = objects.begin(); it != objects.end(); ++it) + { + (*it)->draw(alpha); + } } - OctreeNodeP insert(EntityP entity) + void drawIfVisible(Scalar alpha, const Frustum& frustum) const { - return insert(entity, 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); + } } - OctreeNodeP reinsert(EntityP entity, OctreeNodeP node); - void drawIfVisible(Scalar alpha, const Frustum& frustum) + void getAll(std::list& insertables) const { - drawIfVisible(alpha, frustum, tree_.root()); + getAll(insertables, mTree.root()); } - void sort(); + 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; + } }; @@ -176,5 +351,3 @@ public: #endif // _MOOF_OCTREE_HH_ -/** vim: set ts=4 sw=4 tw=80: *************************************************/ -