*******************************************************************************/
-#include "Camera.hh"
+#include "Frustum.hh"
+#include "Log.hh"
#include "Octree.hh"
}
-stlplus::ntree<OctreeNode>::iterator Octree::insert(stlplus::ntree<OctreeNode>::iterator node,
- EntityPtr entity)
+OctreeNodeP Octree::insert(EntityP entity, OctreeNodeP node)
{
- Plane::Halfspace halfspace;
+ ASSERT(node.valid() && "invalid node passed");
+ ASSERT(entity && "null entity passed");
+
int octantNum = -1;
- if (!node.valid())
+ 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]))
{
- std::cerr << "cannot insert into invalid node" << std::endl;
- return stlplus::ntree<OctreeNode>::iterator();
+ // 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;
}
- Plane xy = node->getAabb().getPlaneXY();
- halfspace = xy.intersectsSphere(entity->getSphere());
+ halfspace = xy.intersects(entity->getSphere());
if (halfspace == Plane::INTERSECT)
{
- halfspace = xy.intersectsAabb(entity->getAabb());
+ halfspace = xy.intersects(entity->getAabb());
}
if (halfspace == Plane::POSITIVE)
{
Plane xz = node->getAabb().getPlaneXZ();
- halfspace = xz.intersectsSphere(entity->getSphere());
+ halfspace = xz.intersects(entity->getSphere());
if (halfspace == Plane::INTERSECT)
{
- halfspace = xz.intersectsAabb(entity->getAabb());
+ halfspace = xz.intersects(entity->getAabb());
}
if (halfspace == Plane::POSITIVE)
{
Plane yz = node->getAabb().getPlaneYZ();
- halfspace = yz.intersectsSphere(entity->getSphere());
+ halfspace = yz.intersects(entity->getSphere());
if (halfspace == Plane::INTERSECT)
{
- halfspace = yz.intersectsAabb(entity->getAabb());
+ halfspace = yz.intersects(entity->getAabb());
}
if (halfspace == Plane::POSITIVE)
else if (halfspace == Plane::NEGATIVE)
{
Plane yz = node->getAabb().getPlaneYZ();
- halfspace = yz.intersectsSphere(entity->getSphere());
+ halfspace = yz.intersects(entity->getSphere());
if (halfspace == Plane::INTERSECT)
{
- halfspace = yz.intersectsAabb(entity->getAabb());
+ halfspace = yz.intersects(entity->getAabb());
}
if (halfspace == Plane::POSITIVE)
else if (halfspace == Plane::NEGATIVE)
{
Plane xz = node->getAabb().getPlaneXZ();
- halfspace = xz.intersectsSphere(entity->getSphere());
+ halfspace = xz.intersects(entity->getSphere());
if (halfspace == Plane::INTERSECT)
{
- halfspace = xz.intersectsAabb(entity->getAabb());
+ halfspace = xz.intersects(entity->getAabb());
}
if (halfspace == Plane::POSITIVE)
{
Plane yz = node->getAabb().getPlaneYZ();
- halfspace = yz.intersectsSphere(entity->getSphere());
+ halfspace = yz.intersects(entity->getSphere());
if (halfspace == Plane::INTERSECT)
{
- halfspace = yz.intersectsAabb(entity->getAabb());
+ halfspace = yz.intersects(entity->getAabb());
}
if (halfspace == Plane::POSITIVE)
else if (halfspace == Plane::NEGATIVE)
{
Plane yz = node->getAabb().getPlaneYZ();
- halfspace = yz.intersectsSphere(entity->getSphere());
+ halfspace = yz.intersects(entity->getSphere());
if (halfspace == Plane::INTERSECT)
{
- halfspace = yz.intersectsAabb(entity->getAabb());
+ halfspace = yz.intersects(entity->getAabb());
}
if (halfspace == Plane::POSITIVE)
}
}
+done:
+
if (octantNum == -1)
{
node->objects.push_front(entity);
addChild(node, octantNum);
}
- stlplus::ntree<OctreeNode>::iterator child = tree_.child(node, octantNum);
+ OctreeNodeP child = tree_.child(node, octantNum);
+ ASSERT(child.valid() && "expected valid child node");
- if (child.valid())
- {
- return insert(child, entity);
- }
- else
- {
- std::cerr << "expected but found no child at index " << octantNum << std::endl;
- return stlplus::ntree<OctreeNode>::iterator();
- }
+ return insert(entity, child);
}
}
-stlplus::ntree<OctreeNode>::iterator Octree::reinsert(EntityPtr entity,
- stlplus::ntree<OctreeNode>::iterator node)
+OctreeNodeP Octree::reinsert(EntityP entity, OctreeNodeP node)
{
- if (!node.valid())
- {
- std::cerr << "cannot move entity from invalid node" << std::endl;
- return stlplus::ntree<OctreeNode>::iterator();
- }
+ ASSERT(entity && "null entity passed");
+ ASSERT(node.valid() && "invalid node passed");
- std::list<EntityPtr>::iterator it;
+ std::list<EntityP>::iterator it;
it = std::find(node->objects.begin(), node->objects.end(), entity);
if (it != node->objects.end())
}
-void Octree::addChild(stlplus::ntree<OctreeNode>::iterator node, int index)
+void Octree::addChild(OctreeNodeP node, int index)
{
- Aabb octant;
+ ASSERT(node.valid() && "invalid node passed");
- if (!node.valid())
- {
- std::cerr << "cannot add children to invalid node" << std::endl;
- return;
- }
+ Aabb octant;
for (int i = tree_.children(node); i <= index; ++i)
{
}
-void Octree::draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
+void Octree::draw(Scalar alpha, OctreeNodeP node)
{
- if (!node.valid())
- {
- std::cerr << "cannot draw null child node :-(" << std::endl;
- return;
- }
+ ASSERT(node.valid() && "invalid node passed");
node->draw(alpha);
for (unsigned i = 0; i < tree_.children(node); ++i)
{
- stlplus::ntree<OctreeNode>::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;
- }
+ OctreeNodeP child = tree_.child(node, i);
+ ASSERT(child.valid() && "expected valid child node");
+ draw(alpha, child);
}
}
-void Octree::drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
- Scalar alpha, const Camera& cam)
+void Octree::drawIfVisible(Scalar alpha, const Frustum& frustum, OctreeNodeP node)
{
- //node.drawIfVisible(alpha, cam);
-
- if (!node.valid())
- {
- std::cerr << "invalid child while drawing :-(" << std::endl;
- return;
- }
+ ASSERT(node.valid() && "invalid node passed");
+ // try to cull by sphere
Frustum::Collision collision =
- cam.getFrustum().containsSphere(node->getSphere());
+ frustum.contains(node->getSphere());
if (collision == Frustum::OUTSIDE) return;
- collision = cam.getFrustum().containsAabb(node->getAabb());
+ // try to cull by aabb
+ collision = frustum.contains(node->getAabb());
if (collision == Frustum::OUTSIDE) return;
}
else // collision == Frustum::INTERSECT
{
- node->drawIfVisible(alpha, cam);
+ node->drawIfVisible(alpha, frustum);
}
if (tree_.children(node) > 0)
{
for (unsigned i = 0; i < tree_.children(node); ++i)
{
- stlplus::ntree<OctreeNode>::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;
- }
+ 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)
{
- stlplus::ntree<OctreeNode>::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;
- }
+ OctreeNodeP child = tree_.child(node, i);
+ ASSERT(child.valid() && "expected valid child node");
+
+ drawIfVisible(alpha, frustum, child);
}
}
}