Frustum sphere culling.
authorKester Maddock <Christopher.Maddock.1@uni.massey.ac.nz>
Fri, 21 May 2004 09:21:15 +0000 (09:21 +0000)
committerKester Maddock <Christopher.Maddock.1@uni.massey.ac.nz>
Fri, 21 May 2004 09:21:15 +0000 (09:21 +0000)
Do a sphere<->camera sphere and a sphere<->frustum before the box<->frustum test.

source/gameengine/Converter/BL_BlenderDataConversion.cpp
source/gameengine/Converter/KX_BlenderSceneConverter.cpp
source/gameengine/Ketsji/KX_Scene.cpp
source/gameengine/SceneGraph/SG_BBox.cpp
source/gameengine/SceneGraph/SG_BBox.h
source/gameengine/SceneGraph/SG_Spatial.cpp
source/gameengine/SceneGraph/SG_Spatial.h
source/gameengine/SceneGraph/SG_Tree.cpp
source/gameengine/SceneGraph/SG_Tree.h

index f51bf955f5168f77b295607dcea2c2faa6ac71e6..dbe68b96faca1a756dd76519f544e2a8f396575f 100644 (file)
@@ -39,6 +39,8 @@
 #pragma warning (disable : 4786)
 #endif
 
+#include <math.h>
+
 #include "BL_BlenderDataConversion.h"
 #include "KX_BlenderGL.h"
 #include "KX_BlenderScalarInterpolator.h"
@@ -523,12 +525,11 @@ static PHY_ShapeProps *CreateShapePropsFromBlenderObject(struct Object* blendero
        
 
 
-
-void my_boundbox_mesh(Mesh *me, float *loc, float *size)
-               {
+float my_boundbox_mesh(Mesh *me, float *loc, float *size)
+{
        MVert *mvert;
        BoundBox *bb;
-       float min[3], max[3];
+       MT_Point3 min, max;
        float mloc[3], msize[3];
        int a;
        
@@ -543,7 +544,7 @@ void my_boundbox_mesh(Mesh *me, float *loc, float *size)
        mvert= me->mvert;
        for(a=0; a<me->totvert; a++, mvert++) {
                DO_MINMAX(mvert->co, min, max);
-               }
+       }
                
        if(me->totvert) {
                loc[0]= (min[0]+max[0])/2.0;
@@ -567,7 +568,16 @@ void my_boundbox_mesh(Mesh *me, float *loc, float *size)
 
        bb->vec[0][2]=bb->vec[3][2]=bb->vec[4][2]=bb->vec[7][2]= loc[2]-size[2];
        bb->vec[1][2]=bb->vec[2][2]=bb->vec[5][2]=bb->vec[6][2]= loc[2]+size[2];
-                       }
+
+       float radius = 0;
+       for (a=0, mvert = me->mvert; a < me->totvert; a++, mvert++)
+       {
+               float vert_radius = MT_Vector3(mvert->co).length2();
+               if (vert_radius > radius)
+                       radius = vert_radius;
+       } 
+       return sqrt(radius);
+}
                
 
 
@@ -863,7 +873,7 @@ static KX_GameObject *gameobject_from_blenderobject(
                Mesh* mesh = static_cast<Mesh*>(ob->data);
                RAS_MeshObject* meshobj = converter->FindGameMesh(mesh, ob->lay);
                float centre[3], extents[3];
-               my_boundbox_mesh((Mesh*) ob->data, centre, extents);
+               float radius = my_boundbox_mesh((Mesh*) ob->data, centre, extents);
                
                if (!meshobj) {
                        meshobj = BL_ConvertMesh(mesh,ob,rendertools,kxscene,converter);
@@ -898,6 +908,7 @@ static KX_GameObject *gameobject_from_blenderobject(
                MT_Point3 max = MT_Point3(centre) + MT_Vector3(extents);
                SG_BBox bbox = SG_BBox(min, max);
                gameobj->GetSGNode()->SetBBox(bbox);
+               gameobj->GetSGNode()->SetRadius(radius);
        
                break;
        }
index 8e552d3f3d4c14032e4f37686dc33099ad83c32b..f7eb25a70a64050ebca6832c2f430a03f9437e4b 100644 (file)
@@ -118,7 +118,9 @@ KX_BlenderSceneConverter::~KX_BlenderSceneConverter()
                itm++;
        }
        
+#ifdef USE_SUMO_SOLID
        KX_ClearSumoSharedShapes();
+#endif
 }
 
 
index 5abd43574baa1be3091252525a817402c37f2d3c..40aca5d712987754be383eede8d0cc0b2c89bc43 100644 (file)
@@ -615,6 +615,7 @@ SCA_IObject* KX_Scene::AddReplicaObject(class CValue* originalobject,
 
        replica->GetSGNode()->UpdateWorldData(0);
        replica->GetSGNode()->SetBBox(originalobj->GetSGNode()->BBox());
+       replica->GetSGNode()->SetRadius(originalobj->GetSGNode()->Radius());
        
        return replica;
 }
@@ -803,13 +804,22 @@ void KX_Scene::UpdateMeshTransformations()
 void KX_Scene::MarkVisible(SG_Tree *node, RAS_IRasterizer* rasty)
 {
        int intersect = KX_Camera::INTERSECT;
+       KX_GameObject *gameobj = node->Client()?(KX_GameObject*) node->Client()->GetSGClientObject():NULL;
        
        /* If the camera is inside the box, assume intersect. */
        if (!node->inside(GetActiveCamera()->NodeGetWorldPosition()))
        {
-               MT_Point3 box[8];
-               node->get(box);
-               intersect = GetActiveCamera()->BoxInsideFrustum(box);
+               MT_Scalar radius = node->Radius();
+               MT_Point3 centre = node->Centre();
+               
+               intersect = GetActiveCamera()->SphereInsideFrustum(centre, radius);
+               
+               if (intersect == KX_Camera::INTERSECT)
+               {
+                       MT_Point3 box[8];
+                       node->get(box);
+                       intersect = GetActiveCamera()->BoxInsideFrustum(box);
+               }
        }
 
        switch (intersect)
@@ -818,9 +828,8 @@ void KX_Scene::MarkVisible(SG_Tree *node, RAS_IRasterizer* rasty)
                        MarkSubTreeVisible(node, rasty, false);
                        break;
                case KX_Camera::INTERSECT:
-                       if (node->Client())
+                       if (gameobj)
                        {
-                               KX_GameObject *gameobj = (KX_GameObject*) node->Client()->GetSGClientObject();
                                int nummeshes = gameobj->GetMeshCount();
                                
                                for (int m=0;m<nummeshes;m++)
@@ -856,7 +865,7 @@ void KX_Scene::MarkSubTreeVisible(SG_Tree *node, RAS_IRasterizer* rasty, bool vi
                                (gameobj->GetMesh(m))->SchedulePolygons(rasty->GetDrawingMode(),rasty);
                        }
                }
-               gameobj->MarkVisible(visible);
+               gameobj->MarkVisible(visible && gameobj->GetVisible());
        }
        if (node->Left())
                MarkSubTreeVisible(node->Left(), rasty, visible);
@@ -873,19 +882,39 @@ void KX_Scene::CalculateVisibleMeshes(RAS_IRasterizer* rasty)
        for (int i = 0; i < m_objectlist->GetCount(); i++)
        {
                KX_GameObject* gameobj = (KX_GameObject*)m_objectlist->GetValue(i);
+               // If Frustum culling is off, the object is always visible.
                bool vis = !GetActiveCamera()->GetFrustumCulling();
+               
+               // If the camera is inside this node, then the object is visible.
                if (!vis)
+               {
                        vis = gameobj->GetSGNode()->inside( GetActiveCamera()->GetCameraLocation() );
+               }
+                       
+               // Test the object's bound sphere against the view frustum.
                if (!vis)
                {
-                       MT_Point3 box[8];
-                       gameobj->GetSGNode()->getBBox(box);
-                       vis = GetActiveCamera()->BoxInsideFrustum(box) != KX_Camera::OUTSIDE;
+                       MT_Vector3 scale = gameobj->GetSGNode()->GetWorldScaling();
+                       MT_Scalar radius = scale[scale.closestAxis()] * gameobj->GetSGNode()->Radius();
+                       switch (GetActiveCamera()->SphereInsideFrustum(gameobj->NodeGetWorldPosition(), radius))
+                       {
+                               case KX_Camera::INSIDE:
+                                       vis = true;
+                                       break;
+                               case KX_Camera::OUTSIDE:
+                                       vis = false;
+                                       break;
+                               case KX_Camera::INTERSECT:
+                                       // Test the object's bound box against the view frustum.
+                                       MT_Point3 box[8];
+                                       gameobj->GetSGNode()->getBBox(box);
+                                       vis = GetActiveCamera()->BoxInsideFrustum(box) != KX_Camera::OUTSIDE;
+                                       break;
+                       }
                }
                
                if (vis)
                {
-                       
                        int nummeshes = gameobj->GetMeshCount();
                        
                        for (int m=0;m<nummeshes;m++)
@@ -901,7 +930,10 @@ void KX_Scene::CalculateVisibleMeshes(RAS_IRasterizer* rasty)
                }
        }
 #else
-       MarkVisible(m_objecttree, rasty);
+       if (GetActiveCamera()->GetFrustumCulling())
+               MarkVisible(m_objecttree, rasty);
+       else
+               MarkSubTreeVisible(m_objecttree, rasty, true);
 #endif
 }
 
index 1430313afafddd00ef743f944ebb433bb2f39802..bc7d00327a9a3d83f9214ad5645e0cf055098297 100644 (file)
@@ -52,6 +52,12 @@ SG_BBox::SG_BBox(const SG_BBox &other, const MT_Transform &world) :
        m_min(world(other.m_min)),
        m_max(world(other.m_max))
 {
+       *this += world(MT_Point3(m_min[0], m_min[1], m_max[2]));
+       *this += world(MT_Point3(m_min[0], m_max[1], m_min[2]));
+       *this += world(MT_Point3(m_min[0], m_max[1], m_max[2]));
+       *this += world(MT_Point3(m_max[0], m_min[1], m_min[2]));
+       *this += world(MT_Point3(m_max[0], m_min[1], m_max[2]));
+       *this += world(MT_Point3(m_max[0], m_max[1], m_min[2]));
 }
 
 SG_BBox::SG_BBox(const SG_BBox &other) :
@@ -64,7 +70,7 @@ SG_BBox::~ SG_BBox()
 {
 }
 
-SG_BBox& SG_BBox::operator +=(MT_Point3 &point)
+SG_BBox& SG_BBox::operator +=(const MT_Point3 &point)
 {
        if (point[0] < m_min[0])
                m_min[0] = point[0];
@@ -84,7 +90,7 @@ SG_BBox& SG_BBox::operator +=(MT_Point3 &point)
        return *this;
 }
 
-SG_BBox& SG_BBox::operator += (SG_BBox &bbox)
+SG_BBox& SG_BBox::operator += (const SG_BBox &bbox)
 {
        *this += bbox.m_min;
        *this += bbox.m_max;
@@ -92,7 +98,7 @@ SG_BBox& SG_BBox::operator += (SG_BBox &bbox)
        return *this;
 }
 
-SG_BBox SG_BBox::operator +(SG_BBox &bbox2) const
+SG_BBox SG_BBox::operator +(const SG_BBox &bbox2) const
 {
        SG_BBox ret = *this;
        ret += bbox2;
@@ -121,7 +127,14 @@ void SG_BBox::scale(const MT_Vector3& size, const MT_Point3& point)
 
 SG_BBox SG_BBox::transform(const MT_Transform &world) const
 {
-       return SG_BBox(world(m_min), world(m_max));
+       SG_BBox bbox(world(m_min), world(m_max));
+       bbox += world(MT_Point3(m_min[0], m_min[1], m_max[2]));
+       bbox += world(MT_Point3(m_min[0], m_max[1], m_min[2]));
+       bbox += world(MT_Point3(m_min[0], m_max[1], m_max[2]));
+       bbox += world(MT_Point3(m_max[0], m_min[1], m_min[2]));
+       bbox += world(MT_Point3(m_max[0], m_min[1], m_max[2]));
+       bbox += world(MT_Point3(m_max[0], m_max[1], m_min[2]));
+       return bbox;
 }
 
 bool SG_BBox::inside(const MT_Point3 &point) const
@@ -177,3 +190,64 @@ void SG_BBox::getaa(MT_Point3 *box, const MT_Transform &world) const
        *box++ = MT_Point3(max[0], max[1], min[2]);
        *box++ = max;
 }
+
+void SG_BBox::split(SG_BBox &left, SG_BBox &right) const
+{
+       MT_Scalar sizex = m_max[0] - m_min[0];
+       MT_Scalar sizey = m_max[1] - m_min[1];
+       MT_Scalar sizez = m_max[2] - m_min[2];
+       if (sizex < sizey)
+       {
+               if (sizey > sizez)
+               {
+                       left.m_min = m_min;
+                       left.m_max[0] = m_max[0];
+                       left.m_max[1] = m_min[1] + sizey/2.0;
+                       left.m_max[2] = m_max[2];
+                       
+                       right.m_min[0] = m_min[0];
+                       right.m_min[1] = m_min[1] + sizey/2.0;
+                       right.m_min[2] = m_min[2];
+                       right.m_max = m_max;
+                       std::cout << "splity" << std::endl;
+               } else {
+                       left.m_min = m_min;
+                       left.m_max[0] = m_max[0];
+                       left.m_max[1] = m_max[1];
+                       left.m_max[2] = m_min[2] + sizez/2.0;
+               
+                       right.m_min[0] = m_min[0];
+                       right.m_min[1] = m_min[1];
+                       right.m_min[2] = m_min[2] + sizez/2.0;
+                       right.m_max = m_max;
+                       std::cout << "splitz" << std::endl;
+               }
+       } else {
+               if (sizex > sizez)
+               {
+                       left.m_min = m_min;
+                       left.m_max[0] = m_min[0] + sizex/2.0;
+                       left.m_max[1] = m_max[1];
+                       left.m_max[2] = m_max[2];
+                       
+                       right.m_min[0] = m_min[0] + sizex/2.0;
+                       right.m_min[1] = m_min[1];
+                       right.m_min[2] = m_min[2];
+                       right.m_max = m_max;
+                       std::cout << "splitx" << std::endl;
+               } else {
+                       left.m_min = m_min;
+                       left.m_max[0] = m_max[0];
+                       left.m_max[1] = m_max[1];
+                       left.m_max[2] = m_min[2] + sizez/2.0;
+               
+                       right.m_min[0] = m_min[0];
+                       right.m_min[1] = m_min[1];
+                       right.m_min[2] = m_min[2] + sizez/2.0;
+                       right.m_max = m_max;
+                       std::cout << "splitz" << std::endl;
+               }
+       }
+       
+       //std::cout << "Left: " << left.m_min << " -> " << left.m_max << " Right: " << right.m_min << " -> " << right.m_max << std::endl;
+}
index 6e3d208ea5475c781498270499596ee83a1ceac4..5a4d396faf140ae28b25dfbbb3c041cfe33c2ca8 100644 (file)
@@ -63,13 +63,13 @@ public:
        /**
         * Enlarges the bounding box to contain the specified point.
         */
-       SG_BBox& operator +=(MT_Point3 &point);
+       SG_BBox& operator +=(const MT_Point3 &point);
        /**
         * Enlarges the bounding box to contain the specified bound box.
         */
-       SG_BBox& operator +=(SG_BBox &bbox);
+       SG_BBox& operator +=(const SG_BBox &bbox);
        
-       SG_BBox operator + (SG_BBox &bbox2) const;
+       SG_BBox operator + (const SG_BBox &bbox2) const;
 #if 0
        /**
         * Translates the bounding box.
@@ -124,6 +124,10 @@ public:
         * @param world a world transform to be applied.
         */
        void getaa(MT_Point3 *box, const MT_Transform &world) const;
+       
+       void split(SG_BBox &left, SG_BBox &right) const;
+       
+       friend class SG_Tree;
 
 };
 
index 633e89b3e6a19b5e8092870c09a5eab53af390ce..c65542c98ce71692ffbfb76bbdbe65f5c77d8b0b 100644 (file)
@@ -50,7 +50,7 @@ SG_Spatial(
        m_localPosition(MT_Point3(0,0,0)),
        m_localRotation(1,0,0,0,1,0,0,0,1),
        m_localScaling(MT_Vector3(1.f,1.f,1.f)),
-
+       
        m_worldPosition(MT_Point3(0,0,0)),
        m_worldRotation(0,0,0,0,0,0,0,0,0),
        m_worldScaling(MT_Vector3(1.f,1.f,1.f)),
@@ -74,7 +74,8 @@ SG_Spatial(
        
        m_parent_relation(NULL),
        
-       m_bbox(other.m_bbox)
+       m_bbox(other.m_bbox),
+       m_radius(other.m_radius)
 {
        // duplicate the parent relation for this object
        m_parent_relation = other.m_parent_relation->NewCopy();
@@ -118,7 +119,8 @@ UpdateSpatialData(
 
        for (;cit!=c_end;++cit)
        {
-               bComputesWorldTransform = bComputesWorldTransform || (*cit)->Update(time);
+               if ((*cit)->Update(time))
+                       bComputesWorldTransform = true;
        }
 
        // If none of the objects updated our values then we ask the
@@ -126,9 +128,9 @@ UpdateSpatialData(
        // our world coordinates.
 
        if (!bComputesWorldTransform)
-    {
+       {
                ComputeWorldTransforms(parent);
-    }
+       }
 }
 
 void   SG_Spatial::ComputeWorldTransforms(const SG_Spatial *parent)
@@ -299,18 +301,26 @@ void SG_Spatial::SetBBox(SG_BBox& bbox)
        m_bbox = bbox;
 }
 
+MT_Transform SG_Spatial::GetWorldTransform() const
+{
+       return MT_Transform(m_worldPosition, m_worldRotation.scaled(m_worldScaling[0], m_worldScaling[1], m_worldScaling[2]));
+}
+
 bool SG_Spatial::inside(const MT_Point3 &point) const
 {
-       return m_bbox.transform(MT_Transform(m_worldPosition, m_worldRotation.scaled(m_worldScaling[0], m_worldScaling[1], m_worldScaling[2]))).inside(point);
+       MT_Scalar radius = m_worldScaling[m_worldScaling.closestAxis()]*m_radius;
+       return (m_worldPosition.distance2(point) <= radius*radius) ?
+               m_bbox.transform(GetWorldTransform()).inside(point) :
+               false;
 }
 
 void SG_Spatial::getBBox(MT_Point3 *box) const
 {
-       m_bbox.get(box, MT_Transform(m_worldPosition, m_worldRotation.scaled(m_worldScaling[0], m_worldScaling[1], m_worldScaling[2])));
+       m_bbox.get(box, GetWorldTransform());
 }
 
 void SG_Spatial::getAABBox(MT_Point3 *box) const
 {
-       m_bbox.getaa(box, MT_Transform(m_worldPosition, m_worldRotation.scaled(m_worldScaling[0], m_worldScaling[1], m_worldScaling[2])));
+       m_bbox.getaa(box, GetWorldTransform());
 }
 
index e029ce51919df4a337a4735c9fad5749cdba3904..e58e45bb4512d2824455cb88fbcc039599bc2bb4 100644 (file)
@@ -53,16 +53,18 @@ class SG_Spatial : public SG_IObject
 
 protected:
        MT_Point3               m_localPosition;
-       MT_Matrix3x3    m_localRotation;
+       MT_Matrix3x3            m_localRotation;
        MT_Vector3              m_localScaling;
 
        MT_Point3               m_worldPosition;
-       MT_Matrix3x3    m_worldRotation;
+       MT_Matrix3x3            m_worldRotation;
        MT_Vector3              m_worldScaling;
        
-       SG_ParentRelation * m_parent_relation;
+       SG_ParentRelation *     m_parent_relation;
+       
+       SG_BBox                 m_bbox;
+       MT_Scalar               m_radius;
        
-       SG_BBox         m_bbox;
 
 public:
 
@@ -173,6 +175,7 @@ public:
        GetWorldScaling(
        ) const ;
 
+       MT_Transform GetWorldTransform() const;
 
        void    ComputeWorldTransforms(         const SG_Spatial *parent);
 
@@ -184,7 +187,10 @@ public:
        bool inside(const MT_Point3 &point) const;
        void getBBox(MT_Point3 *box) const;
        void getAABBox(MT_Point3 *box) const;
-
+       
+       MT_Scalar Radius() const { return m_radius; }
+       void SetRadius(MT_Scalar radius) { m_radius = radius; }
+       
 protected:
        friend class SG_Controller;
        
index 417e42858f502930b5dcdf82efaef9c4169708c0..fcbf3d924d35a8c4dd741cab63b9d8ee86219f75 100644 (file)
@@ -46,9 +46,18 @@ SG_Tree::SG_Tree(SG_Tree* left, SG_Tree* right) :
                m_right(right),
                m_client_object(NULL)
 {
-       m_bbox = m_left->m_bbox + m_right->m_bbox;
-       m_left->m_parent = this;
-       m_right->m_parent = this;
+       if (m_left)
+       {
+               m_bbox = m_left->m_bbox;
+               m_left->m_parent = this;
+       }
+       if (m_right)
+       {
+               m_bbox += m_right->m_bbox;
+               m_right->m_parent = this;
+       }
+       m_centre = (m_bbox.m_min + m_bbox.m_max)/2.0;
+       m_radius = (m_bbox.m_max - m_bbox.m_min).length();
 }
        
 SG_Tree::SG_Tree(SG_Node* client) :
@@ -56,10 +65,9 @@ SG_Tree::SG_Tree(SG_Node* client) :
                m_right(NULL),
                m_client_object(client)
 {
-       const MT_Vector3 &scale = client->GetWorldScaling();
-       m_bbox = SG_BBox(client->BBox(), 
-               MT_Transform(client->GetWorldPosition(), 
-                       client->GetWorldOrientation().scaled(scale[0], scale[1], scale[2])));
+       m_bbox = SG_BBox(client->BBox(), client->GetWorldTransform());
+       m_centre = (m_bbox.m_min + m_bbox.m_max)/2.0;
+       m_radius = (m_bbox.m_max - m_bbox.m_min).length();
 }
 
 SG_Tree::~SG_Tree() 
@@ -128,23 +136,13 @@ SG_Tree* SG_Tree::Find(SG_Node *node)
 
 void SG_Tree::get(MT_Point3 *box) const
 {
-       if (m_client_object)
-       {
-               m_client_object->getAABBox(box);
-       }
-       else
-       {
-               MT_Transform identity;
-               identity.setIdentity();
-               m_bbox.getaa(box, identity);
-       }
+       MT_Transform identity;
+       identity.setIdentity();
+       m_bbox.get(box, identity);
 }
 
 bool SG_Tree::inside(const MT_Point3 &point) const
 {
-       if (m_client_object)
-               return m_client_object->inside(point);
-
        return m_bbox.inside(point);
 }
 
@@ -153,18 +151,20 @@ const SG_BBox& SG_Tree::BBox() const
        return m_bbox;
 }
 
-SG_TreeFactory::SG_TreeFactory()
+void SG_Tree::SetLeft(SG_Tree *left)
 {
+       m_left = left;
+       m_bbox += left->m_bbox;
+       m_centre = (m_bbox.m_min + m_bbox.m_max)/2.0;
+       m_radius = (m_bbox.m_max - m_bbox.m_min).length();
 }
 
-SG_TreeFactory::~SG_TreeFactory()
+void SG_Tree::SetRight(SG_Tree *right)
 {
-}
-       
-void SG_TreeFactory::Add(SG_Node* client)
-{
-       if (client)
-               m_objects.push_back(new SG_Tree(client));
+       m_right = right;
+       m_bbox += right->m_bbox;
+       m_centre = (m_bbox.m_min + m_bbox.m_max)/2.0;
+       m_radius = (m_bbox.m_max - m_bbox.m_min).length();
 }
 
 /**
@@ -215,25 +215,151 @@ public:
        }
 };
 
+SG_TreeFactory::SG_TreeFactory()
+{
+}
+
+SG_TreeFactory::~SG_TreeFactory()
+{
+}
+       
+void SG_TreeFactory::Add(SG_Node* client)
+{
+       if (client)
+               m_objects.insert(new SG_Tree(client));
+}
+
+void SG_TreeFactory::Add(SG_Tree* tree)
+{
+       m_objects.insert(tree);
+}
+
+SG_Tree* SG_TreeFactory::MakeTreeDown(SG_BBox &bbox)
+{
+       if (m_objects.size() == 0)
+               return NULL;
+       if (m_objects.size() == 1)
+               return *m_objects.begin();
+               
+       TreeSet::iterator it = m_objects.begin();
+       SG_Tree *root = *it;
+       if (m_objects.size() == 2)
+       {
+               root->SetRight(*(++it));
+               return root;
+       }
+               
+       if (m_objects.size() == 3)
+       {
+               root->SetLeft(*(++it));
+               root->SetRight(*(++it));
+               return root;
+       }
+
+       if (bbox.volume() < 1.0)
+               return MakeTreeUp();
+               
+       SG_TreeFactory lefttree;
+       SG_TreeFactory righttree;
+       
+       SG_BBox left, right;
+       int hasleft = 0, hasright = 0;
+       bbox.split(left, right);
+       
+       if (left.test(root->BBox()) == SG_BBox::INSIDE)
+       {
+               lefttree.Add(root);
+               root = NULL;
+       }
+       
+       if (root && right.test(root->BBox()) == SG_BBox::INSIDE)
+       {
+               righttree.Add(root);
+               root = NULL;
+       }
+       
+       for (++it; it != m_objects.end(); ++it)
+       {
+               switch (left.test((*it)->BBox()))
+               {
+                       case SG_BBox::INSIDE:
+                               // Object is inside left tree;
+                               lefttree.Add(*it);
+                               hasleft++;
+                               break;
+                       case SG_BBox::OUTSIDE:
+                               righttree.Add(*it);
+                               hasright++;
+                               break;
+                       case SG_BBox::INTERSECT:
+                               if (left.inside((*it)->Client()->GetWorldPosition()))
+                               {
+                                       lefttree.Add(*it);
+                                       hasleft++;
+                               } else {
+                                       righttree.Add(*it);
+                                       hasright++;
+                               }
+                               break;
+               }
+       }
+       std::cout << "Left: " << hasleft << " Right: " << hasright << " Count: " << m_objects.size() << std::endl;
+       
+       SG_Tree *leftnode = NULL;
+       if (hasleft)
+               leftnode = lefttree.MakeTreeDown(left);
+       
+       SG_Tree *rightnode = NULL;
+       if (hasright)
+               rightnode = righttree.MakeTreeDown(right);
+               
+       if (!root)
+               root = new SG_Tree(leftnode, rightnode);
+       else
+       {
+               if (leftnode)
+                       root->SetLeft(leftnode);
+               if (rightnode)
+                       root->SetRight(rightnode);
+       }
+
+       return root;
+}
+
 SG_Tree* SG_TreeFactory::MakeTree()
+{
+       if (m_objects.size() < 8)
+               return MakeTreeUp();
+
+       TreeSet::iterator it = m_objects.begin();
+       SG_BBox bbox((*it)->BBox());
+       for (++it; it != m_objects.end(); ++it)
+               bbox += (*it)->BBox();
+       
+       return MakeTreeDown(bbox);
+}
+
+SG_Tree* SG_TreeFactory::MakeTreeUp()
 {
        unsigned int num_objects = m_objects.size();
        
        if (num_objects < 1)
                return NULL;
        if (num_objects < 2)
-               return m_objects[0];
+               return *m_objects.begin();
 
        HalfArray<SG_Tree*> sizes;
        sizes.resize(num_objects);
        
        unsigned int x, y;
-       for( y = 0; y < num_objects; y++)
+       TreeSet::iterator xit, yit;
+       for( y = 0, yit = m_objects.begin(); y < num_objects; y++, ++yit)
        {
-               sizes(y, y) = m_objects[y];
-               for( x = y+1; x < num_objects; x++)
+               sizes(y, y) = *yit;
+               xit = yit;
+               for( x = y+1, ++xit; x < num_objects; x++, ++xit)
                {
-                       sizes(x, y) = new SG_Tree(m_objects[x], m_objects[y]);
+                       sizes(x, y) = new SG_Tree(*xit, *yit);
                        
                }
        }
@@ -246,14 +372,8 @@ SG_Tree* SG_TreeFactory::MakeTree()
                //char temp[16];
                for( y = 0; y < num_objects; y++)
                {
-                       /*std::cout << sizes(y, y) << " ";
-                       for( unsigned int x = 0; x < y; x++)
-                               std::cout << "                   "; */
-                       
                        for( x = y+1; x < num_objects; x++)
                        {
-                               //sprintf(temp, "%7.1f", sizes(x, y)->volume());
-                               //std::cout << sizes(x, y) << "(" << temp << ") ";
                                if (sizes(x, y)->volume() < min_volume)
                                {
                                        min = sizes(x, y);
@@ -262,11 +382,8 @@ SG_Tree* SG_TreeFactory::MakeTree()
                                        min_volume = sizes(x, y)->volume();
                                }
                        }
-                       //std::cout << std::endl;
                }
                
-               //std::cout << "minx, miny, minv = " << minx << ", " << miny << ", " << min_volume << std::endl;
-               
                /* Remove other bboxes that contain the two bboxes */
                sizes.delete_column(miny);
                
index 78c8411de8d1dd6e9bac5779e0648504b16f0992..51eeec4f3e1701049f24b7cfba3ef7d49ae5320a 100644 (file)
@@ -37,7 +37,7 @@
 #include "MT_Point3.h"
 #include "SG_BBox.h"
 
-#include <vector
+#include <set
 
 class SG_Node;
 
@@ -52,6 +52,8 @@ class SG_Tree
        SG_Tree* m_right;
        SG_Tree* m_parent;
        SG_BBox  m_bbox;
+       MT_Point3 m_centre;
+       MT_Scalar m_radius;
        SG_Node* m_client_object;
 public:
        SG_Tree();
@@ -95,7 +97,23 @@ public:
         * Test if the given bounding box is inside this bounding box.
         */
        bool inside(const MT_Point3 &point) const;
+       
+       void SetLeft(SG_Tree *left);
+       void SetRight(SG_Tree *right);
 
+       MT_Point3 Centre() const { return m_centre; }
+       MT_Scalar Radius() { return m_radius; }
+       
+       //friend class SG_TreeFactory;
+       
+       struct greater
+       {
+               bool operator()(const SG_Tree *a, const SG_Tree *b)
+               {
+                       return a->volume() > b->volume();
+               }
+       };
+       
 };
 
 
@@ -108,7 +126,8 @@ public:
  */
 class SG_TreeFactory 
 {
-       std::vector<SG_Tree*> m_objects;
+       typedef std::multiset<SG_Tree*, SG_Tree::greater> TreeSet;
+       TreeSet m_objects;
 public:
        SG_TreeFactory();
        ~SG_TreeFactory();
@@ -117,12 +136,21 @@ public:
         *  Add a node to be added to the tree.
         */
        void Add(SG_Node* client);
+       void Add(SG_Tree* tree);
 
        /**
         *  Build the tree from the set of nodes added by
         *  the Add method.
         */
+       SG_Tree* MakeTreeUp();
+       
+       /**
+        *  Build the tree from the set of nodes top down.
+        */
+       SG_Tree* MakeTreeDown(SG_BBox &bbox);
+       
        SG_Tree* MakeTree();
+       
 };
 
 #endif /* __SG_BBOX_H__ */