SceneGraph support for bounding boxs
authorKester Maddock <Christopher.Maddock.1@uni.massey.ac.nz>
Sun, 16 May 2004 12:54:44 +0000 (12:54 +0000)
committerKester Maddock <Christopher.Maddock.1@uni.massey.ac.nz>
Sun, 16 May 2004 12:54:44 +0000 (12:54 +0000)
source/gameengine/SceneGraph/SConscript
source/gameengine/SceneGraph/SG_BBox.cpp [new file with mode: 0644]
source/gameengine/SceneGraph/SG_BBox.h [new file with mode: 0644]
source/gameengine/SceneGraph/SG_IObject.h
source/gameengine/SceneGraph/SG_Node.cpp
source/gameengine/SceneGraph/SG_Node.h
source/gameengine/SceneGraph/SG_Spatial.cpp
source/gameengine/SceneGraph/SG_Spatial.h
source/gameengine/SceneGraph/SG_Tree.cpp [new file with mode: 0644]
source/gameengine/SceneGraph/SG_Tree.h [new file with mode: 0644]

index 3782d60d828f2bb00c5715b71c71a05df72a715a..2905684d50ee652583aab62344fb94b6cbaa9d55 100755 (executable)
@@ -1,12 +1,16 @@
+#!/usr/bin/python
+
 Import ('user_options_dict')
 Import ('library_env')
 
 sg_scenegraph_env = library_env.Copy ()
 
-source_files = ['SG_Controller.cpp',
+source_files = ['SG_BBox.cpp',
+                'SG_Controller.cpp',
                 'SG_IObject.cpp',
                 'SG_Node.cpp',
-                'SG_Spatial.cpp']
+                'SG_Spatial.cpp',
+                'SG_Tree.cpp']
 
 sg_scenegraph_env.Append (CPPPATH=['.',
                                    '#intern/moto/include'
diff --git a/source/gameengine/SceneGraph/SG_BBox.cpp b/source/gameengine/SceneGraph/SG_BBox.cpp
new file mode 100644 (file)
index 0000000..1430313
--- /dev/null
@@ -0,0 +1,179 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ * Bounding Box
+ */
+
+#include <math.h>
+ #include "SG_BBox.h"
+ #include "SG_Node.h"
+SG_BBox::SG_BBox() :
+       m_min(MT_Point3(0., 0., 0.)),
+       m_max(MT_Point3(0., 0., 0.))
+{
+}
+
+SG_BBox::SG_BBox(const MT_Point3 &min, const MT_Point3 &max) :
+       m_min(min),
+       m_max(max)
+{
+}
+
+SG_BBox::SG_BBox(const SG_BBox &other, const MT_Transform &world) :
+       m_min(world(other.m_min)),
+       m_max(world(other.m_max))
+{
+}
+
+SG_BBox::SG_BBox(const SG_BBox &other) :
+       m_min(other.m_min),
+       m_max(other.m_max)
+{
+}
+
+SG_BBox::~ SG_BBox()
+{
+}
+
+SG_BBox& SG_BBox::operator +=(MT_Point3 &point)
+{
+       if (point[0] < m_min[0])
+               m_min[0] = point[0];
+       else if (point[0] > m_max[0])
+               m_max[0] = point[0];
+
+       if (point[1] < m_min[1])
+               m_min[1] = point[1];
+       else if (point[1] > m_max[1])
+               m_max[1] = point[1];
+       
+       if (point[2] < m_min[2])
+               m_min[2] = point[2];
+       else if (point[2] > m_max[2])
+               m_max[2] = point[2];
+               
+       return *this;
+}
+
+SG_BBox& SG_BBox::operator += (SG_BBox &bbox)
+{
+       *this += bbox.m_min;
+       *this += bbox.m_max;
+       
+       return *this;
+}
+
+SG_BBox SG_BBox::operator +(SG_BBox &bbox2) const
+{
+       SG_BBox ret = *this;
+       ret += bbox2;
+       return ret;
+}
+
+MT_Scalar SG_BBox::volume() const
+{
+       MT_Vector3 size = m_max - m_min;
+       return size[0]*size[1]*size[2];
+}
+#if 0
+void SG_BBox::translate(const MT_Vector3& dx)
+{
+       m_min += dx;
+       m_max += dx;
+}
+
+void SG_BBox::scale(const MT_Vector3& size, const MT_Point3& point)
+{
+       MT_Vector3 centre = (m_max - m_min)/2. + point;
+       m_max = (m_max - centre)*size;
+       m_min = (m_min - centre)*size;
+}
+#endif
+
+SG_BBox SG_BBox::transform(const MT_Transform &world) const
+{
+       return SG_BBox(world(m_min), world(m_max));
+}
+
+bool SG_BBox::inside(const MT_Point3 &point) const
+{
+       return point[0] >= m_min[0] && point[0] <= m_max[0] &&
+           point[1] >= m_min[1] && point[1] <= m_max[1] &&
+           point[2] >= m_min[2] && point[2] <= m_max[2];
+}
+
+bool SG_BBox::inside(const SG_BBox& other) const
+{
+       return inside(other.m_min) && inside(other.m_max);
+}
+
+bool SG_BBox::intersects(const SG_BBox& other) const
+{
+       return inside(other.m_min) != inside(other.m_max);
+}
+
+bool SG_BBox::outside(const SG_BBox& other) const
+{
+       return !inside(other.m_min) && !inside(other.m_max);
+}
+
+SG_BBox::intersect SG_BBox::test(const SG_BBox& other) const
+{
+       bool point1(inside(other.m_min)), point2(inside(other.m_max));
+       
+       return point1?(point2?INSIDE:INTERSECT):(point2?INTERSECT:OUTSIDE);
+}
+
+void SG_BBox::get(MT_Point3 *box, const MT_Transform &world) const
+{
+       *box++ = world(m_min);
+       *box++ = world(MT_Point3(m_min[0], m_min[1], m_max[2]));
+       *box++ = world(MT_Point3(m_min[0], m_max[1], m_min[2]));
+       *box++ = world(MT_Point3(m_min[0], m_max[1], m_max[2]));
+       *box++ = world(MT_Point3(m_max[0], m_min[1], m_min[2]));
+       *box++ = world(MT_Point3(m_max[0], m_min[1], m_max[2]));
+       *box++ = world(MT_Point3(m_max[0], m_max[1], m_min[2]));
+       *box++ = world(m_max);
+}
+
+void SG_BBox::getaa(MT_Point3 *box, const MT_Transform &world) const
+{
+       const MT_Point3 min(world(m_min)), max(world(m_max));
+       *box++ = min;
+       *box++ = MT_Point3(min[0], min[1], max[2]);
+       *box++ = MT_Point3(min[0], max[1], min[2]);
+       *box++ = MT_Point3(min[0], max[1], max[2]);
+       *box++ = MT_Point3(max[0], min[1], min[2]);
+       *box++ = MT_Point3(max[0], min[1], max[2]);
+       *box++ = MT_Point3(max[0], max[1], min[2]);
+       *box++ = max;
+}
diff --git a/source/gameengine/SceneGraph/SG_BBox.h b/source/gameengine/SceneGraph/SG_BBox.h
new file mode 100644 (file)
index 0000000..6e3d208
--- /dev/null
@@ -0,0 +1,130 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ * Bounding Box
+ */
+#ifndef __SG_BBOX_H__
+#define __SG_BBOX_H__
+#include "MT_Scalar.h"
+#include "MT_Point3.h"
+#include "MT_Vector3.h"
+#include "MT_Transform.h"
+
+#include <vector> 
+
+class SG_Node;
+
+/**
+ * Bounding box class.
+ * Holds the minimum and maximum axis aligned points of a node's bounding box,
+ * in world coordinates.
+ */
+class SG_BBox
+{
+       MT_Point3 m_min;
+       MT_Point3 m_max;
+public:
+       typedef enum { INSIDE, INTERSECT, OUTSIDE } intersect;
+       SG_BBox();
+       SG_BBox(const MT_Point3 &min, const MT_Point3 &max);
+       SG_BBox(const SG_BBox &other, const MT_Transform &world);
+       SG_BBox(const SG_BBox &other);
+       ~SG_BBox();
+
+       /**
+        * Enlarges the bounding box to contain the specified point.
+        */
+       SG_BBox& operator +=(MT_Point3 &point);
+       /**
+        * Enlarges the bounding box to contain the specified bound box.
+        */
+       SG_BBox& operator +=(SG_BBox &bbox);
+       
+       SG_BBox operator + (SG_BBox &bbox2) const;
+#if 0
+       /**
+        * Translates the bounding box.
+        */
+       void translate(const MT_Vector3 &dx);
+       /**
+        * Scales the bounding box about the optional point.
+        */
+       void scale(const MT_Vector3 &size, const MT_Point3 &point = MT_Point3(0., 0., 0.));
+#endif
+       SG_BBox transform(const MT_Transform &world) const;
+       /**
+        * Computes the volume of the bounding box.
+        */
+       MT_Scalar volume() const;
+       
+       /**
+        * Test if the given point is inside this bounding box.
+        */
+       bool inside(const MT_Point3 &point) const;
+       
+       /**
+        * Test if the given bounding box is inside this bounding box.
+        */
+       bool inside(const SG_BBox &other) const;
+
+       /**
+        * Test if the given bounding box is outside this bounding box.
+        */
+       bool outside(const SG_BBox &other) const;
+       
+       /**
+        * Test if the given bounding box intersects this bounding box.
+        */
+       bool intersects(const SG_BBox &other) const;
+       
+       /**
+        * Test the given bounding box with this bounding box.
+        */
+       intersect test(const SG_BBox &other) const;
+       
+       /**
+        * Get the eight points that define this bounding box.
+        *
+        * @param world a world transform to apply to the produced points bounding box.
+        */
+       void get(MT_Point3 *box, const MT_Transform &world) const;
+       /**
+        * Get the eight points that define this axis aligned bounding box.
+        * This differs from SG_BBox::get() in that the produced box will be world axis aligned.
+        * The maximum & minimum local points will be transformed *before* splitting to 8 points.
+        * @param world a world transform to be applied.
+        */
+       void getaa(MT_Point3 *box, const MT_Transform &world) const;
+
+};
+
+#endif /* __SG_BBOX_H__ */
index 40cf80da99dab4bd2d16fde3b105e38b2f594fa3..f3af9a68d8571ee97bfea4de31b393d88bc279e9 100644 (file)
@@ -31,9 +31,7 @@
  */
 #ifndef __SG_IOBJECT
 #define __SG_IOBJECT
-/**
-base object that can be part of the scenegraph.
-*/
+
 #include <vector>
 
 class SG_Controller;
@@ -91,6 +89,9 @@ struct        SG_Callbacks
        SG_DestructionNewCallback       m_destructionfunc;
 };
 
+/**
+base object that can be part of the scenegraph.
+*/
 class SG_IObject
 {
 private :
index 821bc86af1687c9159efa2270c06b188983a4e8c..b083d79bb70cc4f81865e91fbd4a232130063f09 100644 (file)
@@ -231,3 +231,5 @@ void SG_Node::SetSimulatedTime(double time,bool recurse)
        }
 }
 
+
+
index 225ea51363049bccba8203f01dfbab68bd026f91..fe30213614fc39cf52b5915b0d053fed67d1ad05 100644 (file)
 
 typedef std::vector<SG_Node*> NodeList;
 
+/**
+ * Scenegraph node.
+ */
 class SG_Node : public SG_Spatial
 {
-
 public:
 
        SG_Node(
@@ -185,6 +187,8 @@ public:
                void            
        Destruct(
        );
+       
+
 
 private:
 
index 77e805c07585df6a51ab474260388a313c36b735..633e89b3e6a19b5e8092870c09a5eab53af390ce 100644 (file)
@@ -50,12 +50,12 @@ 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_parent_relation (NULL),
 
        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))
+       m_worldScaling(MT_Vector3(1.f,1.f,1.f)),
 
+       m_parent_relation (NULL)
 {
 }
 
@@ -67,10 +67,14 @@ SG_Spatial(
        m_localPosition(other.m_localPosition),
        m_localRotation(other.m_localRotation),
        m_localScaling(other.m_localScaling),
-       m_parent_relation(NULL),
+       
        m_worldPosition(other.m_worldPosition),
        m_worldRotation(other.m_worldRotation),
-       m_worldScaling(other.m_worldScaling)
+       m_worldScaling(other.m_worldScaling),
+       
+       m_parent_relation(NULL),
+       
+       m_bbox(other.m_bbox)
 {
        // duplicate the parent relation for this object
        m_parent_relation = other.m_parent_relation->NewCopy();
@@ -285,3 +289,28 @@ GetWorldScaling(
        return m_worldScaling;
 }
 
+SG_BBox& SG_Spatial::BBox()
+{
+       return m_bbox;
+}
+
+void SG_Spatial::SetBBox(SG_BBox& bbox)
+{
+       m_bbox = bbox;
+}
+
+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);
+}
+
+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])));
+}
+
+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])));
+}
+
index 9536a4ff940948b3646cb8982b81b0b1b0644ca3..e029ce51919df4a337a4735c9fad5749cdba3904 100644 (file)
 #include <MT_Point3.h>
 #include <MT_Matrix3x3.h> // or Quaternion later ?
 #include "SG_IObject.h"
+#include "SG_BBox.h"
+
 
 class SG_Node;
 class SG_ParentRelation;
 
+/**
+ * SG_Spatial contains spatial information (local & world position, rotation 
+ * and scaling) for a Scene graph node.
+ * It also contains a link to the node's parent.
+ */
 class SG_Spatial : public SG_IObject
 {
 
@@ -54,6 +61,8 @@ protected:
        MT_Vector3              m_worldScaling;
        
        SG_ParentRelation * m_parent_relation;
+       
+       SG_BBox         m_bbox;
 
 public:
 
@@ -167,7 +176,15 @@ public:
 
        void    ComputeWorldTransforms(         const SG_Spatial *parent);
 
-       
+       /**
+        * Bounding box functions.
+        */
+       SG_BBox& BBox();
+       void SetBBox(SG_BBox & bbox);
+       bool inside(const MT_Point3 &point) const;
+       void getBBox(MT_Point3 *box) const;
+       void getAABBox(MT_Point3 *box) const;
+
 protected:
        friend class SG_Controller;
        
diff --git a/source/gameengine/SceneGraph/SG_Tree.cpp b/source/gameengine/SceneGraph/SG_Tree.cpp
new file mode 100644 (file)
index 0000000..8e4c96c
--- /dev/null
@@ -0,0 +1,296 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ * Bounding Box
+ */
+
+#include <math.h>
+#include "SG_BBox.h"
+#include "SG_Tree.h"
+#include "SG_Node.h"
+
+SG_Tree::SG_Tree()
+{
+}
+
+SG_Tree::SG_Tree(SG_Tree* left, SG_Tree* right) :
+               m_left(left),
+               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;
+}
+       
+SG_Tree::SG_Tree(SG_Node* client) :
+               m_left(NULL),
+               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])));
+}
+       
+SG_Tree::~SG_Tree() 
+{
+}
+       
+MT_Scalar SG_Tree::volume() const
+{
+       return m_bbox.volume();
+}
+       
+void SG_Tree::dump() const
+{
+       if (m_left)
+               m_left->dump();
+       if (m_client_object)
+               std::cout << m_client_object << std::endl;
+       else
+               std::cout << this << " ";
+       if (m_right)
+               m_right->dump();
+}
+
+SG_Tree* SG_Tree::Left() const
+{
+       return m_left;
+}
+
+SG_Tree* SG_Tree::Right() const
+{
+       return m_right;
+}
+
+SG_Node* SG_Tree::Client() const
+{
+       return m_client_object;
+}
+
+SG_Tree* SG_Tree::Find(SG_Node *node)
+{
+       if (m_client_object == node)
+               return this;
+       
+       SG_Tree *left(m_left), *right(m_right);
+       
+       if (left && right)
+       {
+               if (right->m_bbox.intersects(node->BBox()))
+                       std::swap(left, right);
+       }
+               
+       if (left)
+       {
+               SG_Tree* ret = left->Find(node);
+               if (ret) return ret;
+       }
+       
+       if (right)
+       {
+               SG_Tree* ret = right->Find(node);
+               if (ret) return ret;
+       }
+       
+       return NULL;
+}
+
+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);
+       }
+}
+
+bool SG_Tree::inside(const MT_Point3 &point) const
+{
+       if (m_client_object)
+               return m_client_object->inside(point);
+
+       return m_bbox.inside(point);
+}
+
+const SG_BBox& SG_Tree::BBox() const
+{
+       return m_bbox;
+}
+
+SG_TreeFactory::SG_TreeFactory()
+{
+}
+
+SG_TreeFactory::~SG_TreeFactory()
+{
+}
+       
+void SG_TreeFactory::Add(SG_Node* client)
+{
+       if (client)
+               m_objects.push_back(new SG_Tree(client));
+}
+
+/**
+ * A Half array is a square 2d array where cell(x, y) is undefined
+ * if x < y.
+ */
+template<typename T>
+class HalfArray
+{
+       std::vector<std::vector<T> > m_array;
+public:
+       HalfArray() {}
+       ~HalfArray() {}
+       
+       void resize(unsigned int size)
+       {
+               m_array.resize(size);
+               for( unsigned int i = 0; i < size; i++)
+               {
+                       m_array[i].resize(size - i);
+               }
+       }
+       
+       T& operator() (unsigned int x, unsigned int y)
+       {
+               assert(x >= y);
+               return m_array[y][x - y];
+       }
+       
+       void erase_column (unsigned int x)
+       {
+               for (unsigned int y = 0; y <= x; y++)
+                       m_array[y].erase(m_array[y].begin() + x - y);
+       }
+
+       void delete_column (unsigned int x)
+       {
+               for (unsigned int y = 0; y < x; y++)
+               {
+                       delete m_array[y][x - y];
+                       m_array[y].erase(m_array[y].begin() + x - y);
+               }
+       }
+       
+       void erase_row (unsigned int y)
+       {
+               m_array.erase(m_array.begin() + y);
+       }
+};
+
+SG_Tree* SG_TreeFactory::MakeTree()
+{
+       unsigned int num_objects = m_objects.size();
+       
+       if (num_objects < 1)
+               return NULL;
+       if (num_objects < 2)
+               return m_objects[0];
+
+       HalfArray<SG_Tree*> sizes;
+       sizes.resize(num_objects);
+
+       for( unsigned int y = 0; y < num_objects; y++)
+       {
+               sizes(y, y) = m_objects[y];
+               for( unsigned int x = y+1; x < num_objects; x++)
+               {
+                       sizes(x, y) = new SG_Tree(m_objects[x], m_objects[y]);
+                       
+               }
+       }
+       while (num_objects > 2)
+       {
+               /* Find the pair of bboxes that produce the smallest combined bbox. */
+               unsigned int minx, miny;
+               MT_Scalar min_volume = FLT_MAX;
+               SG_Tree *min;
+               //char temp[16];
+               for( unsigned int y = 0; y < num_objects; y++)
+               {
+                       /*std::cout << sizes(y, y) << " ";
+                       for( unsigned int x = 0; x < y; x++)
+                               std::cout << "                   "; */
+                       
+                       for( unsigned int 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);
+                                       minx = x;
+                                       miny = y;
+                                       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);
+               
+               for( unsigned int x = miny + 1; x < num_objects; x++)
+               {
+                       if (x == minx)
+                               continue;
+                       delete sizes(x, miny);
+               }
+               sizes.erase_row(miny);
+               
+               num_objects--;
+               minx--;
+               sizes(minx, minx) = min;
+               for( unsigned int x = minx + 1; x < num_objects; x++)
+               {
+                       delete sizes(x, minx);
+                       sizes(x, minx) = new SG_Tree(min, sizes(x, x));
+               }
+               for( unsigned int y = 0; y < minx; y++)
+               {
+                       delete sizes(minx, y);
+                       sizes(minx, y) = new SG_Tree(sizes(y, y), min);
+               }
+       }
+       return sizes(1, 0);
+}
+
diff --git a/source/gameengine/SceneGraph/SG_Tree.h b/source/gameengine/SceneGraph/SG_Tree.h
new file mode 100644 (file)
index 0000000..78c8411
--- /dev/null
@@ -0,0 +1,128 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ * Bounding Box
+ */
+#ifndef __SG_TREE_H__
+#define __SG_TREE_H__
+#include "MT_Point3.h"
+#include "SG_BBox.h"
+
+#include <vector> 
+
+class SG_Node;
+
+
+/**
+ * SG_Tree.
+ * Holds a binary tree of SG_Nodes.
+ */
+class SG_Tree 
+{
+       SG_Tree* m_left;
+       SG_Tree* m_right;
+       SG_Tree* m_parent;
+       SG_BBox  m_bbox;
+       SG_Node* m_client_object;
+public:
+       SG_Tree();
+       SG_Tree(SG_Tree* left, SG_Tree* right);
+       
+       SG_Tree(SG_Node* client);
+       ~SG_Tree();
+       
+       /**
+        * Computes the volume of the bounding box.
+        */
+       MT_Scalar volume() const;
+       
+       /**
+        * Prints the tree (for debugging.)
+        */
+       void dump() const;
+       
+       /**
+        * Returns the left node.
+        */
+       SG_Tree *Left() const;
+       SG_Tree *Right() const;
+       SG_Node *Client() const;
+       
+       SG_Tree* Find(SG_Node *node);
+       /**
+        * Gets the eight corners of this treenode's bounding box,
+        * in world coordinates.
+        * @param box: an array of 8 MT_Point3
+        * @example MT_Point3 box[8];
+        *          treenode->get(box);
+        */
+       void get(MT_Point3 *box) const;
+       /**
+        * Get the tree node's bounding box.
+        */
+       const SG_BBox& BBox() const;
+       
+       /**
+        * Test if the given bounding box is inside this bounding box.
+        */
+       bool inside(const MT_Point3 &point) const;
+
+};
+
+
+/**
+ *  SG_TreeFactory generates an SG_Tree from a list of SG_Nodes.
+ *  It joins pairs of SG_Nodes to minimise the size of the resultant
+ *  bounding box.
+ *  cf building an optimised Huffman tree.
+ *  @warning O(n^3)!!!
+ */
+class SG_TreeFactory 
+{
+       std::vector<SG_Tree*> m_objects;
+public:
+       SG_TreeFactory();
+       ~SG_TreeFactory();
+       
+       /**
+        *  Add a node to be added to the tree.
+        */
+       void Add(SG_Node* client);
+
+       /**
+        *  Build the tree from the set of nodes added by
+        *  the Add method.
+        */
+       SG_Tree* MakeTree();
+};
+
+#endif /* __SG_BBOX_H__ */