From 3cba2347188d70f5ee6e401774b8f86acfd1a3b9 Mon Sep 17 00:00:00 2001 From: Charles McGarvey Date: Wed, 2 Sep 2009 09:50:59 -0600 Subject: [PATCH] fixed stack overflow of entities outside octree --- src/Moof/Octree.cc | 48 ++++++++++++++++++++++++++++++---------------- src/Moof/Octree.hh | 29 ++++++++++++++-------------- 2 files changed, 46 insertions(+), 31 deletions(-) diff --git a/src/Moof/Octree.cc b/src/Moof/Octree.cc index 22b4eb1..300dbcd 100644 --- a/src/Moof/Octree.cc +++ b/src/Moof/Octree.cc @@ -45,16 +45,30 @@ void Octree::sort() } -stlplus::ntree::iterator Octree::insert(stlplus::ntree::iterator node, - EntityP entity) +OctreeNodeP Octree::insert(EntityP entity, OctreeNodeP node) { ASSERT(node.valid() && "invalid node passed"); ASSERT(entity && "null entity passed"); - Plane::Halfspace halfspace; int octantNum = -1; + Plane::Halfspace halfspace; + + // TODO this method needs a lot of work Plane xy = node->getAabb().getPlaneXY(); + + + // make sure the entity is fully inside the volume + if (!(entity->getAabb().max[0] < node->getAabb().max[0] && + entity->getAabb().min[0] > node->getAabb().min[0] && + entity->getAabb().max[1] < node->getAabb().max[1] && + entity->getAabb().min[1] > node->getAabb().min[1] && + entity->getAabb().max[2] < node->getAabb().max[2] && + entity->getAabb().min[2] > node->getAabb().min[2])) + { + goto done; + } + halfspace = xy.intersectsSphere(entity->getSphere()); if (halfspace == Plane::INTERSECT) { @@ -154,6 +168,8 @@ stlplus::ntree::iterator Octree::insert(stlplus::ntree:: } } +done: + if (octantNum == -1) { node->objects.push_front(entity); @@ -166,15 +182,14 @@ stlplus::ntree::iterator Octree::insert(stlplus::ntree:: addChild(node, octantNum); } - stlplus::ntree::iterator child = tree_.child(node, octantNum); + OctreeNodeP child = tree_.child(node, octantNum); ASSERT(child.valid() && "expected valid child node"); - return insert(child, entity); + return insert(entity, child); } } -stlplus::ntree::iterator Octree::reinsert(EntityP entity, - stlplus::ntree::iterator node) +OctreeNodeP Octree::reinsert(EntityP entity, OctreeNodeP node) { ASSERT(entity && "null entity passed"); ASSERT(node.valid() && "invalid node passed"); @@ -191,7 +206,7 @@ stlplus::ntree::iterator Octree::reinsert(EntityP entity, } -void Octree::addChild(stlplus::ntree::iterator node, int index) +void Octree::addChild(OctreeNodeP node, int index) { ASSERT(node.valid() && "invalid node passed"); @@ -205,7 +220,7 @@ void Octree::addChild(stlplus::ntree::iterator node, int index) } -void Octree::draw(stlplus::ntree::iterator node, Scalar alpha) +void Octree::draw(Scalar alpha, OctreeNodeP node) { ASSERT(node.valid() && "invalid node passed"); @@ -213,15 +228,14 @@ void Octree::draw(stlplus::ntree::iterator node, Scalar alpha) for (unsigned i = 0; i < tree_.children(node); ++i) { - stlplus::ntree::iterator child = tree_.child(node, i); + OctreeNodeP child = tree_.child(node, i); ASSERT(child.valid() && "expected valid child node"); - draw(child, alpha); + draw(alpha, child); } } -void Octree::drawIfVisible(stlplus::ntree::iterator node, - Scalar alpha, const Camera& cam) +void Octree::drawIfVisible(Scalar alpha, const Camera& cam, OctreeNodeP node) { ASSERT(node.valid() && "invalid node passed"); @@ -250,20 +264,20 @@ void Octree::drawIfVisible(stlplus::ntree::iterator node, { for (unsigned i = 0; i < tree_.children(node); ++i) { - stlplus::ntree::iterator child = tree_.child(node, i); + OctreeNodeP child = tree_.child(node, i); ASSERT(child.valid() && "expected valid child node"); - draw(child, alpha); + draw(alpha, child); } } else // collision == Frustum::INTERSECT { for (unsigned i = 0; i < tree_.children(node); ++i) { - stlplus::ntree::iterator child = tree_.child(node, i); + OctreeNodeP child = tree_.child(node, i); ASSERT(child.valid() && "expected valid child node"); - drawIfVisible(child, alpha, cam); + drawIfVisible(alpha, cam, child); } } } diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh index 774eece..4dc0c5c 100644 --- a/src/Moof/Octree.hh +++ b/src/Moof/Octree.hh @@ -49,6 +49,13 @@ namespace Mf { class Camera; +struct OctreeNode; +typedef stlplus::ntree::iterator OctreeNodeP; + +class Octree; +typedef boost::shared_ptr OctreeP; + + struct OctreeNode : public Entity { std::list objects; @@ -118,19 +125,14 @@ struct OctreeNode : public Entity }; -class Octree; -typedef boost::shared_ptr OctreeP; - class Octree { - stlplus::ntree::iterator - insert(stlplus::ntree::iterator node, EntityP entity); + OctreeNodeP insert(EntityP entity, OctreeNodeP node); - void addChild(stlplus::ntree::iterator node, int index); + void addChild(OctreeNodeP node, int index); - void draw(stlplus::ntree::iterator node, Scalar alpha); - void drawIfVisible(stlplus::ntree::iterator node, - Scalar alpha, const Camera& cam); + void draw(Scalar alpha, OctreeNodeP node); + void drawIfVisible(Scalar alpha, const Camera& cam, OctreeNodeP node); stlplus::ntree tree_; @@ -146,17 +148,16 @@ public: tree_.insert(rootNode); } - stlplus::ntree::iterator insert(EntityP entity) + OctreeNodeP insert(EntityP entity) { - return insert(tree_.root(), entity); + return insert(entity, tree_.root()); } - stlplus::ntree::iterator reinsert(EntityP entity, - stlplus::ntree::iterator node); + OctreeNodeP reinsert(EntityP entity, OctreeNodeP node); void drawIfVisible(Scalar alpha, const Camera& cam) { - drawIfVisible(tree_.root(), alpha, cam); + drawIfVisible(alpha, cam, tree_.root()); } void sort(); -- 2.43.0