+++ /dev/null
-
-/*******************************************************************************
-
- 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<OctreeNode>::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<EntityP>::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: *************************************************/
-
projects / chaz / yoink / blobdiff