X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2FOctree.cc;fp=src%2FMoof%2FOctree.cc;h=50b38ac08f36ca4bb0af26e38ab3e6ac4e5a717e;hp=0000000000000000000000000000000000000000;hb=bfa6212d09d8735d8fd5e2638188e4a99f21ada4;hpb=eebb993ca929c3f4c235cad9e01dc4797fcd2945 diff --git a/src/Moof/Octree.cc b/src/Moof/Octree.cc new file mode 100644 index 0000000..50b38ac --- /dev/null +++ b/src/Moof/Octree.cc @@ -0,0 +1,320 @@ + +/******************************************************************************* + + 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. + +*******************************************************************************/ + +#include "Camera.hh" +#include "Octree.hh" + + +namespace Mf { + + +void Octree::sort() +{ + stlplus::ntree::prefix_iterator it; + + for (it = tree_.prefix_begin(); it != tree_.prefix_end(); ++it) + { + it->sort(); + } +} + + +stlplus::ntree::iterator Octree::insert(stlplus::ntree::iterator node, + EntityPtr entity) +{ + Plane::Halfspace halfspace; + int octantNum = -1; + + if (!node.valid()) + { + std::cerr << "cannot insert into invalid node" << std::endl; + return stlplus::ntree::iterator(); + } + + Plane xy = node->getAabb().getPlaneXY(); + halfspace = xy.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::INTERSECT) + { + halfspace = xy.intersectsAabb(entity->getAabb()); + } + + if (halfspace == Plane::POSITIVE) + { + Plane xz = node->getAabb().getPlaneXZ(); + halfspace = xz.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::INTERSECT) + { + halfspace = xz.intersectsAabb(entity->getAabb()); + } + + if (halfspace == Plane::POSITIVE) + { + Plane yz = node->getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::INTERSECT) + { + halfspace = yz.intersectsAabb(entity->getAabb()); + } + + if (halfspace == Plane::POSITIVE) + { + octantNum = 2; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 3; + } + } + else if (halfspace == Plane::NEGATIVE) + { + Plane yz = node->getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::INTERSECT) + { + halfspace = yz.intersectsAabb(entity->getAabb()); + } + + if (halfspace == Plane::POSITIVE) + { + octantNum = 1; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 0; + } + } + } + else if (halfspace == Plane::NEGATIVE) + { + Plane xz = node->getAabb().getPlaneXZ(); + halfspace = xz.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::INTERSECT) + { + halfspace = xz.intersectsAabb(entity->getAabb()); + } + + if (halfspace == Plane::POSITIVE) + { + Plane yz = node->getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::INTERSECT) + { + halfspace = yz.intersectsAabb(entity->getAabb()); + } + + if (halfspace == Plane::POSITIVE) + { + octantNum = 6; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 7; + } + } + else if (halfspace == Plane::NEGATIVE) + { + Plane yz = node->getAabb().getPlaneYZ(); + halfspace = yz.intersectsSphere(entity->getSphere()); + if (halfspace == Plane::INTERSECT) + { + halfspace = yz.intersectsAabb(entity->getAabb()); + } + + if (halfspace == Plane::POSITIVE) + { + octantNum = 5; + } + else if (halfspace == Plane::NEGATIVE) + { + octantNum = 4; + } + } + } + + if (octantNum == -1) + { + node->objects.push_front(entity); + return node; + } + else + { + if ((int)tree_.children(node) <= octantNum) + { + addChild(node, octantNum); + } + + stlplus::ntree::iterator child = tree_.child(node, octantNum); + + if (child.valid()) + { + return insert(child, entity); + } + else + { + std::cerr << "expected but found no child at index " << octantNum << std::endl; + return stlplus::ntree::iterator(); + } + } +} + +stlplus::ntree::iterator Octree::reinsert(EntityPtr entity, + stlplus::ntree::iterator node) +{ + if (!node.valid()) + { + std::cerr << "cannot move entity from invalid node" << std::endl; + return stlplus::ntree::iterator(); + } + + std::list::iterator it; + it = std::find(node->objects.begin(), node->objects.end(), entity); + + if (it != node->objects.end()) + { + node->objects.erase(it); + } + + return insert(entity); +} + + +void Octree::addChild(stlplus::ntree::iterator node, int index) +{ + Aabb octant; + + if (!node.valid()) + { + std::cerr << "cannot add children to invalid node" << std::endl; + return; + } + + for (int i = tree_.children(node); i <= index; ++i) + { + node->getAabb().getOctant(octant, i); + tree_.append(node, octant); + } +} + + +void Octree::draw(stlplus::ntree::iterator node, Scalar alpha) +{ + if (!node.valid()) + { + std::cerr << "cannot draw null child node :-(" << std::endl; + return; + } + + node->draw(alpha); + + for (unsigned i = 0; i < tree_.children(node); ++i) + { + stlplus::ntree::iterator child = tree_.child(node, i); + + if (child.valid()) + { + draw(child, alpha); + } + else + { + std::cerr << "node is not a leaf, but has an invalid child" << std::endl; + } + + } +} + +void Octree::drawIfVisible(stlplus::ntree::iterator node, + Scalar alpha, const Camera& cam) +{ + //node.drawIfVisible(alpha, cam); + + if (!node.valid()) + { + std::cerr << "invalid child while drawing :-(" << std::endl; + return; + } + + Frustum::Collision collision = + cam.getFrustum().containsSphere(node->getSphere()); + if (collision == Frustum::OUTSIDE) return; + + collision = cam.getFrustum().containsAabb(node->getAabb()); + if (collision == Frustum::OUTSIDE) return; + + + if (collision == Frustum::INSIDE) + { + node->draw(alpha); + } + else // collision == Frustum::INTERSECT + { + node->drawIfVisible(alpha, cam); + } + + if (tree_.children(node) > 0) + { + if (collision == Frustum::INSIDE) + { + for (unsigned i = 0; i < tree_.children(node); ++i) + { + stlplus::ntree::iterator child = tree_.child(node, i); + + if (child.valid()) + { + draw(child, alpha); + } + else + { + std::cerr << "node is not a leaf, but has an invalid child" << std::endl; + } + + } + } + else // collision == Frustum::INTERSECT + { + for (unsigned i = 0; i < tree_.children(node); ++i) + { + stlplus::ntree::iterator child = tree_.child(node, i); + + if (child.valid()) + { + drawIfVisible(child, alpha, cam); + } + else + { + std::cerr << "node is not a leaf, but has an invalid child" << std::endl; + } + } + } + } +} + + +} // namespace Mf + +/** vim: set ts=4 sw=4 tw=80: *************************************************/ +