#include <boost/shared_ptr.hpp>
+#include <stlplus/ntree.hpp>
+
#include <Moof/Aabb.hh>
#include <Moof/Drawable.hh>
#include <Moof/Entity.hh>
#include <Moof/Math.hh>
#include <Moof/Sphere.hh>
-#include <Moof/Tree.hh>
namespace Mf {
class Octree;
typedef boost::shared_ptr<Octree> OctreePtr;
-class Octree : public Tree<OctreeNode>
+class Octree
{
- Octree() {}
-
- explicit Octree(const OctreeNode& initNode) :
- Tree<OctreeNode>(initNode) {}
+ stlplus::ntree<OctreeNode> root_;
public:
- inline static OctreePtr createNewNode(const OctreeNode& item)
+ explicit Octree(const OctreeNode& rootNode)
{
- OctreePtr newNode = OctreePtr(new Octree(item));
- init(newNode);
- return newNode;
+ root_.insert(rootNode);
}
+ void insert(EntityPtr entity)
+ {
+ insert(root_.root(), entity);
+ }
- static Tree<OctreeNode>::WeakPtr add(Ptr node, EntityPtr entity)
+ void insert(stlplus::ntree<OctreeNode>::iterator node, EntityPtr entity)
{
Plane::Halfspace halfspace;
int octantNum = -1;
- Plane xy = node->node.getAabb().getPlaneXY();
+ if (!node.valid())
+ {
+ std::cerr << "cannot insert into invalid node" << std::endl;
+ return;
+ }
+
+ Plane xy = node->getAabb().getPlaneXY();
halfspace = xy.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
{
- Plane xz = node->node.getAabb().getPlaneXZ();
+ Plane xz = node->getAabb().getPlaneXZ();
halfspace = xz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
}
else if (halfspace == Plane::NEGATIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
}
else if (halfspace == Plane::NEGATIVE)
{
- Plane xz = node->node.getAabb().getPlaneXZ();
+ Plane xz = node->getAabb().getPlaneXZ();
halfspace = xz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
}
else if (halfspace == Plane::NEGATIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
if (octantNum == -1)
{
- node->node.objects.push_front(entity);
- return node;
+ node->objects.push_front(entity);
+ //return node;
}
else
{
- if (node->isLeaf())
+ if (root_.children(node) == 0)
{
addChildren(node);
}
- Ptr child = node->getChild(octantNum);
- if (child)
+ stlplus::ntree<OctreeNode>::iterator child = root_.child(node, octantNum);
+
+ if (child.valid())
{
- return add(child, entity);
+ return insert(child, entity);
}
else
{
- std::cerr << "no child at index " << octantNum << std::endl;
- return Ptr();
+ std::cerr << "expected but found no child at index " << octantNum << std::endl;
+ //return stlplus::ntree<OctreeNode>::iterator();
}
//return WeakPtr();
}
}
- static void addChildren(Ptr node)
+ void addChildren(stlplus::ntree<OctreeNode>::iterator node)
{
Aabb octant;
+ if (!node.valid())
+ {
+ std::cerr << "cannot add children to invalid node" << std::endl;
+ return;
+ }
+
for (int i = 0; i < 8; ++i)
{
- node->node.getAabb().getOctant(octant, i);
+ node->getAabb().getOctant(octant, i);
//OctreeNode octantNode(octant);
- Ptr newChild = createNewNode(octant);
- node->addChild(newChild);
+ root_.append(node, octant);
}
}
- void draw(Ptr node, Scalar alpha)
+ void draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
{
- if (!node)
+ if (!node.valid())
{
- std::cerr << "null child :-(" << std::endl;
+ std::cerr << "cannot draw null child node :-(" << std::endl;
return;
}
- node->node.draw(alpha);
+ node->draw(alpha);
- if (!node->isLeaf())
+ for (unsigned i = 0; i < root_.children(node); ++i)
{
- Ptr firstChild = node->getFirstChild();
- Ptr temp = firstChild;
+ stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
- if (!firstChild)
+ if (child.valid())
{
- std::cerr << "node is not a leaf, but has no first child :-(" << std::endl;
- return;
+ draw(child, alpha);
}
-
- do
+ else
{
- draw(temp, alpha);
- temp = temp->getNextSibling();
+ std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
}
- while (temp && temp != firstChild);
+
}
}
- void drawIfVisible(Ptr node, Scalar alpha, const Camera& cam)
+ void drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
+ Scalar alpha, const Camera& cam)
{
//node.drawIfVisible(alpha, cam);
- if (!node)
+ if (!node.valid())
{
- std::cerr << "null child :-(" << std::endl;
+ std::cerr << "invalid child while drawing :-(" << std::endl;
return;
}
Frustum::Collision collision =
- cam.getFrustum().containsSphere(node->node.getSphere());
+ cam.getFrustum().containsSphere(node->getSphere());
if (collision == Frustum::OUTSIDE) return;
- collision = cam.getFrustum().containsAabb(node->node.getAabb());
+ collision = cam.getFrustum().containsAabb(node->getAabb());
if (collision == Frustum::OUTSIDE) return;
if (collision == Frustum::INSIDE)
{
- node->node.draw(alpha);
+ node->draw(alpha);
}
else // collision == Frustum::INTERSECT
{
- node->node.drawIfVisible(alpha, cam);
+ node->drawIfVisible(alpha, cam);
}
- if (!node->isLeaf())
+ if (root_.children(node) > 0)
{
- Ptr firstChild = node->getFirstChild();
- Ptr temp = firstChild;
-
- if (!firstChild)
- {
- std::cerr << "node is not a leaf, but has no first child :-(" << std::endl;
- return;
- }
-
if (collision == Frustum::INSIDE)
{
- do
+ for (unsigned i = 0; i < root_.children(node); ++i)
{
- draw(temp, alpha);
- temp = temp->getNextSibling();
+ stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
+
+ if (child.valid())
+ {
+ draw(child, alpha);
+ }
+ else
+ {
+ std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
+ }
+
}
- while (temp && temp != firstChild);
}
else // collision == Frustum::INTERSECT
{
- do
+ for (unsigned i = 0; i < root_.children(node); ++i)
{
- drawIfVisible(temp, alpha, cam);
- temp = temp->getNextSibling();
+ stlplus::ntree<OctreeNode>::iterator child = root_.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;
+ }
}
- while (temp && temp != firstChild);
}
}
}
void drawIfVisible(Scalar alpha, const Camera& cam)
{
- drawIfVisible(getThis(), alpha, cam);
+ drawIfVisible(root_.root(), alpha, cam);
}
};