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=0000000000000000000000000000000000000000;hp=062788daa1f0d0378460c09cfd4b99eff4d924ca;hb=a4debfe4a5f5d339410788971b698ba00cb7f09c;hpb=892da43bf5796e7c5f593a6d0f53bd797a36bd3e diff --git a/src/Moof/Octree.cc b/src/Moof/Octree.cc deleted file mode 100644 index 062788d..0000000 --- a/src/Moof/Octree.cc +++ /dev/null @@ -1,293 +0,0 @@ - -/******************************************************************************* - - 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 "Frustum.hh" -#include "Log.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(); - } -} - - -OctreeNodeP Octree::insert(EntityP entity, OctreeNodeP node) -{ - ASSERT(node.valid() && "invalid node passed"); - ASSERT(entity && "null entity passed"); - - 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])) - { - // TODO this check is only needed for the root node, if we're inside the - // volume of the root node, we'll be fully inside the child as - // determined by trying to insert the parent node - goto done; - } - - halfspace = xy.intersects(entity->getSphere()); - if (halfspace == Plane::INTERSECT) - { - halfspace = xy.intersects(entity->getAabb()); - } - - if (halfspace == Plane::POSITIVE) - { - Plane xz = node->getAabb().getPlaneXZ(); - halfspace = xz.intersects(entity->getSphere()); - if (halfspace == Plane::INTERSECT) - { - halfspace = xz.intersects(entity->getAabb()); - } - - if (halfspace == Plane::POSITIVE) - { - Plane yz = node->getAabb().getPlaneYZ(); - halfspace = yz.intersects(entity->getSphere()); - if (halfspace == Plane::INTERSECT) - { - halfspace = yz.intersects(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.intersects(entity->getSphere()); - if (halfspace == Plane::INTERSECT) - { - halfspace = yz.intersects(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.intersects(entity->getSphere()); - if (halfspace == Plane::INTERSECT) - { - halfspace = xz.intersects(entity->getAabb()); - } - - if (halfspace == Plane::POSITIVE) - { - Plane yz = node->getAabb().getPlaneYZ(); - halfspace = yz.intersects(entity->getSphere()); - if (halfspace == Plane::INTERSECT) - { - halfspace = yz.intersects(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.intersects(entity->getSphere()); - if (halfspace == Plane::INTERSECT) - { - halfspace = yz.intersects(entity->getAabb()); - } - - if (halfspace == Plane::POSITIVE) - { - octantNum = 5; - } - else if (halfspace == Plane::NEGATIVE) - { - octantNum = 4; - } - } - } - -done: - - if (octantNum == -1) - { - node->objects.push_front(entity); - return node; - } - else - { - if ((int)tree_.children(node) <= octantNum) - { - addChild(node, octantNum); - } - - OctreeNodeP child = tree_.child(node, octantNum); - ASSERT(child.valid() && "expected valid child node"); - - return insert(entity, child); - } -} - -OctreeNodeP Octree::reinsert(EntityP entity, OctreeNodeP node) -{ - ASSERT(entity && "null entity passed"); - ASSERT(node.valid() && "invalid node passed"); - - 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(OctreeNodeP node, int index) -{ - ASSERT(node.valid() && "invalid node passed"); - - Aabb octant; - - for (int i = tree_.children(node); i <= index; ++i) - { - node->getAabb().getOctant(octant, i); - tree_.append(node, octant); - } -} - - -void Octree::draw(Scalar alpha, OctreeNodeP node) -{ - ASSERT(node.valid() && "invalid node passed"); - - node->draw(alpha); - - for (unsigned i = 0; i < tree_.children(node); ++i) - { - OctreeNodeP child = tree_.child(node, i); - ASSERT(child.valid() && "expected valid child node"); - - draw(alpha, child); - } -} - -void Octree::drawIfVisible(Scalar alpha, const Frustum& frustum, OctreeNodeP node) -{ - 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->draw(alpha); - } - else // collision == Frustum::INTERSECT - { - node->drawIfVisible(alpha, frustum); - } - - if (tree_.children(node) > 0) - { - if (collision == Frustum::INSIDE) - { - for (unsigned i = 0; i < tree_.children(node); ++i) - { - OctreeNodeP child = tree_.child(node, i); - ASSERT(child.valid() && "expected valid child node"); - - draw(alpha, child); - } - } - else // collision == Frustum::INTERSECT - { - for (unsigned i = 0; i < tree_.children(node); ++i) - { - OctreeNodeP child = tree_.child(node, i); - ASSERT(child.valid() && "expected valid child node"); - - drawIfVisible(alpha, frustum, child); - } - } - } -} - - -} // namespace Mf - -/** vim: set ts=4 sw=4 tw=80: *************************************************/ -