preliminary physics, sound, hud

[chaz/yoink] / src / Moof / Octree.hh

diff --git a/src/Moof/Octree.hh b/src/Moof/Octree.hh
index 1c57ff2d3317fe83d10aa6972093683cb634556f..d896844f0379a4ab7ca1cebe32d52cb5a719a775 100644 (file)
--- a/src/Moof/Octree.hh
+++ b/src/Moof/Octree.hh
@@ -29,6 +29,7 @@
 #ifndef _MOOF_OCTREE_HH_
 #define _MOOF_OCTREE_HH_
 
 #ifndef _MOOF_OCTREE_HH_
 #define _MOOF_OCTREE_HH_
 

+#include <algorithm>

 #include <list>
 
 #include <boost/shared_ptr.hpp>
 #include <list>
 
 #include <boost/shared_ptr.hpp>


@@ -45,6 +46,9 @@
 namespace Mf {
 
 
 namespace Mf {
 
 

+class Camera;
+
+

 struct OctreeNode : public Entity
 {
        std::list<EntityPtr> objects;
 struct OctreeNode : public Entity
 {
        std::list<EntityPtr> objects;


@@ -71,8 +75,9 @@ struct OctreeNode : public Entity
                {
                        (*it)->draw(alpha);
                }
                {
                        (*it)->draw(alpha);
                }

-               if (!objects.empty())
-                       aabb_.draw(); // temporary
+
+               //if (!objects.empty())
+                       //aabb_.draw(); // temporary

        }
 
        void drawIfVisible(Scalar alpha, const Camera& cam) const
        }
 
        void drawIfVisible(Scalar alpha, const Camera& cam) const


@@ -83,8 +88,9 @@ struct OctreeNode : public Entity
                {
                        (*it)->drawIfVisible(alpha, cam);
                }
                {
                        (*it)->drawIfVisible(alpha, cam);
                }

-               if (!objects.empty())
-                       aabb_.draw();
+
+               //if (!objects.empty())
+                       //aabb_.draw();

        }
 
 
        }
 
 


@@ -97,257 +103,58 @@ struct OctreeNode : public Entity
 
                return false;
        }
 
                return false;
        }

-};

 
 
 
 

-class Octree;
-typedef boost::shared_ptr<Octree> OctreePtr;
+       static bool compareZOrder(EntityPtr a, EntityPtr b)
+       {
+               return a->getSphere().point[2] < b->getSphere().point[2];
+       }

 
 

-class Octree
-{
+       void sort()
+       {
+               //std::sort(objects.begin(), objects.end(), compareZOrder);
+               objects.sort(compareZOrder);
+       }
+};

 
 

-       stlplus::ntree<OctreeNode> root_;

 
 

+class Octree
+{

 public:
 
        explicit Octree(const OctreeNode& rootNode)
        {
 public:
 
        explicit Octree(const OctreeNode& rootNode)
        {

-               root_.insert(rootNode);
+               tree_.insert(rootNode);

        }
 
        }
 

-       void insert(EntityPtr entity)
+       stlplus::ntree<OctreeNode>::iterator insert(EntityPtr entity)

        {
        {

-               insert(root_.root(), entity);
+               return insert(tree_.root(), entity);

        }
 
        }
 

-       void insert(stlplus::ntree<OctreeNode>::iterator node, EntityPtr entity)
-       {
-               Plane::Halfspace halfspace;
-               int octantNum = -1;
+       stlplus::ntree<OctreeNode>::iterator reinsert(EntityPtr entity,
+                       stlplus::ntree<OctreeNode>::iterator node);

 
 

-               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->getAabb().getPlaneXZ();
-                       halfspace = xz.intersectsSphere(entity->getSphere());
-
-                       if (halfspace == Plane::POSITIVE)
-                       {
-                               Plane yz = node->getAabb().getPlaneYZ();
-                               halfspace = yz.intersectsSphere(entity->getSphere());
-
-                               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::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::POSITIVE)
-                       {
-                               Plane yz = node->getAabb().getPlaneYZ();
-                               halfspace = yz.intersectsSphere(entity->getSphere());
-
-                               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::POSITIVE)
-                               {
-                                       octantNum = 5;
-                               }
-                               else if (halfspace == Plane::NEGATIVE)
-                               {
-                                       octantNum = 4;
-                               }
-                       }
-               }
-
-               if (octantNum == -1)
-               {
-                       node->objects.push_front(entity);
-                       //return node;
-               }
-               else
-               {
-                       if (root_.children(node) == 0)
-                       {
-                               addChildren(node);
-                       }
-
-                       stlplus::ntree<OctreeNode>::iterator child = root_.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<OctreeNode>::iterator();
-                       }
-                       //return WeakPtr();
-               }
-       }
-
-       void addChildren(stlplus::ntree<OctreeNode>::iterator node)
+       void drawIfVisible(Scalar alpha, const Camera& cam)

        {
        {

-               Aabb octant;
-
-               if (!node.valid())
-               {
-                       std::cerr << "cannot add children to invalid node" << std::endl;
-                       return;
-               }
-
-               for (int i = 0; i < 8; ++i)
-               {
-                       node->getAabb().getOctant(octant, i);
-                       //OctreeNode octantNode(octant);
-
-                       root_.append(node, octant);
-               }
+               drawIfVisible(tree_.root(), alpha, cam);

        }
 
        }
 

-       void draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
-       {
-               if (!node.valid())
-               {
-                       std::cerr << "cannot draw null child node :-(" << std::endl;
-                       return;
-               }
+       void sort();

 
 

-               node->draw(alpha);
-
-               for (unsigned i = 0; i < root_.children(node); ++i)
-               {
-                       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;
-                       }
-
-               }
-       }
+private:
+       stlplus::ntree<OctreeNode>::iterator insert(stlplus::ntree<OctreeNode>::iterator node, EntityPtr entity);
+       
+       void addChild(stlplus::ntree<OctreeNode>::iterator node, int index);

 
 

+       void draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha);

        void drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
        void drawIfVisible(stlplus::ntree<OctreeNode>::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 (root_.children(node) > 0)
-               {
-                       if (collision == Frustum::INSIDE)
-                       {
-                               for (unsigned i = 0; i < root_.children(node); ++i)
-                               {
-                                       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;
-                                       }
-
-                               }
-                       }
-                       else // collision == Frustum::INTERSECT
-                       {
-                               for (unsigned i = 0; i < root_.children(node); ++i)
-                               {
-                                       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;
-                                       }
-                               }
-                       }
-               }
-       }
-
-       void drawIfVisible(Scalar alpha, const Camera& cam)
-       {
-               drawIfVisible(root_.root(), alpha, cam);
-       }
+                       Scalar alpha, const Camera& cam);

 
 

+       stlplus::ntree<OctreeNode> tree_;

 };
 
 };
 

+typedef boost::shared_ptr<Octree> OctreePtr;

 
 
 } // namespace Mf
 
 
 } // namespace Mf