X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.hh;h=155995934728e73b7721cc7c3f4765567d6bacb6;hp=88dae7ac6492e587d1bb133516a27b4343d98735;hb=c78934a448d0126709fccec3d5a636b3baa87da4;hpb=64bd443538f57ad1bdff6c6b35953e72141129b2 diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 88dae7a..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,7 +16,6 @@ #include #include - #include #include @@ -52,8 +34,7 @@ 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; }; @@ -66,32 +47,21 @@ 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 { - aabb.draw(alpha); - } - - void drawIfVisible(Scalar alpha, const Frustum& frustum) const - { - if (isVisible(frustum)) - { - aabb.draw(alpha); - } + mAabb.draw(alpha); } void printSize() { - logDebug("size of node %d", objects.size()); + logInfo << "size of node " << objects.size() << std::endl; } void getAll(std::list& insertables) const @@ -110,17 +80,6 @@ class Octree : public Entity if ((*it)->isVisible(frustum)) insertables.push_back(*it); } } - - - bool isVisible(const Frustum& frustum) const - { - if (sphere.isVisible(frustum)) - { - return aabb.isVisible(frustum); - } - - return false; - } }; @@ -137,14 +96,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); } } @@ -153,7 +120,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); @@ -161,12 +128,12 @@ 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_recurse(entity, child); @@ -177,12 +144,12 @@ 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); } } @@ -194,14 +161,14 @@ private: node->printSize(); - int octantNum = entity.getOctant(node->aabb); + int octantNum = entity.getOctant(node->getAabb()); if (octantNum != -1) { node->getAll(insertables); - if (octantNum < (int)tree_.children(node)) + if (octantNum < (int)mTree.children(node)) { - NodeP child = tree_.child(node, octantNum); + NodeP child = mTree.child(node, octantNum); ASSERT(child.valid() && "expected valid child node"); getNearbyObjects(insertables, entity, child); @@ -209,7 +176,7 @@ private: } else { - logDebug("getting all the rest..."); + logInfo("getting all the rest..."); getAll(insertables, node); } } @@ -221,9 +188,9 @@ private: node->getAll(insertables); - 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"); getAll(insertables, child); @@ -236,11 +203,11 @@ private: 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; @@ -253,13 +220,13 @@ private: 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"); getAll(insertables, child); @@ -267,9 +234,9 @@ private: } 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"); getIfVisible(insertables, frustum, child); @@ -279,7 +246,7 @@ private: } - mutable stlplus::ntree tree_; + mutable stlplus::ntree mTree; public: @@ -287,8 +254,8 @@ public: void print(NodeP node) { logInfo("-----"); - logInfo("depth to node: %d", tree_.depth(node)); - logInfo("size of node: %d", tree_.size(node)); + logInfo << "depth to node: " << mTree.depth(node) << std::endl; + logInfo << "size of node: " << mTree.size(node) << std::endl; } static Ptr alloc(const Node& rootNode) @@ -298,13 +265,13 @@ 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()); } void remove(InsertableP entity, NodeP node) @@ -344,8 +311,8 @@ public: void drawIfVisible(Scalar alpha, const Frustum& frustum) const { std::list objects; - //getIfVisible(objects, frustum); - getNearbyObjects(objects, *savedObj); + getIfVisible(objects, frustum); + //getNearbyObjects(objects, *savedObj); typename std::list::const_iterator it; for (it = objects.begin(); it != objects.end(); ++it) @@ -357,13 +324,13 @@ public: void getAll(std::list& insertables) const { - getAll(insertables, tree_.root()); + getAll(insertables, mTree.root()); } void getIfVisible(std::list& insertables, const Frustum& frustum) const { - getIfVisible(insertables, frustum, tree_.root()); + getIfVisible(insertables, frustum, mTree.root()); } mutable const OctreeInsertable* savedObj; @@ -372,9 +339,9 @@ public: void getNearbyObjects(std::list& insertables, const OctreeInsertable& entity) const { - logDebug("--- GETTING NEARBY"); - getNearbyObjects(insertables, entity, tree_.root()); - logDebug("---"); + logInfo("--- GETTING NEARBY"); + getNearbyObjects(insertables, entity, mTree.root()); + logInfo("---"); savedObj = &entity; } }; @@ -384,5 +351,3 @@ public: #endif // _MOOF_OCTREE_HH_ -/** vim: set ts=4 sw=4 tw=80: *************************************************/ -