From c50055204df1a73583f646bba688d5f7a76531a8 Mon Sep 17 00:00:00 2001 From: Kester Maddock Date: Sun, 16 May 2004 12:54:44 +0000 Subject: SceneGraph support for bounding boxs --- source/gameengine/SceneGraph/SConscript | 8 +- source/gameengine/SceneGraph/SG_BBox.cpp | 179 +++++++++++++++++ source/gameengine/SceneGraph/SG_BBox.h | 130 ++++++++++++ source/gameengine/SceneGraph/SG_IObject.h | 7 +- source/gameengine/SceneGraph/SG_Node.cpp | 2 + source/gameengine/SceneGraph/SG_Node.h | 6 +- source/gameengine/SceneGraph/SG_Spatial.cpp | 37 +++- source/gameengine/SceneGraph/SG_Spatial.h | 19 +- source/gameengine/SceneGraph/SG_Tree.cpp | 296 ++++++++++++++++++++++++++++ source/gameengine/SceneGraph/SG_Tree.h | 128 ++++++++++++ 10 files changed, 801 insertions(+), 11 deletions(-) create mode 100644 source/gameengine/SceneGraph/SG_BBox.cpp create mode 100644 source/gameengine/SceneGraph/SG_BBox.h create mode 100644 source/gameengine/SceneGraph/SG_Tree.cpp create mode 100644 source/gameengine/SceneGraph/SG_Tree.h (limited to 'source/gameengine/SceneGraph') diff --git a/source/gameengine/SceneGraph/SConscript b/source/gameengine/SceneGraph/SConscript index 3782d60d828..2905684d50e 100755 --- a/source/gameengine/SceneGraph/SConscript +++ b/source/gameengine/SceneGraph/SConscript @@ -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 index 00000000000..1430313afaf --- /dev/null +++ b/source/gameengine/SceneGraph/SG_BBox.cpp @@ -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 + + #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 index 00000000000..6e3d208ea54 --- /dev/null +++ b/source/gameengine/SceneGraph/SG_BBox.h @@ -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 + +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__ */ diff --git a/source/gameengine/SceneGraph/SG_IObject.h b/source/gameengine/SceneGraph/SG_IObject.h index 40cf80da99d..f3af9a68d85 100644 --- a/source/gameengine/SceneGraph/SG_IObject.h +++ b/source/gameengine/SceneGraph/SG_IObject.h @@ -31,9 +31,7 @@ */ #ifndef __SG_IOBJECT #define __SG_IOBJECT -/** -base object that can be part of the scenegraph. -*/ + #include 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 : diff --git a/source/gameengine/SceneGraph/SG_Node.cpp b/source/gameengine/SceneGraph/SG_Node.cpp index 821bc86af16..b083d79bb70 100644 --- a/source/gameengine/SceneGraph/SG_Node.cpp +++ b/source/gameengine/SceneGraph/SG_Node.cpp @@ -231,3 +231,5 @@ void SG_Node::SetSimulatedTime(double time,bool recurse) } } + + diff --git a/source/gameengine/SceneGraph/SG_Node.h b/source/gameengine/SceneGraph/SG_Node.h index 225ea513630..fe30213614f 100644 --- a/source/gameengine/SceneGraph/SG_Node.h +++ b/source/gameengine/SceneGraph/SG_Node.h @@ -37,9 +37,11 @@ typedef std::vector NodeList; +/** + * Scenegraph node. + */ class SG_Node : public SG_Spatial { - public: SG_Node( @@ -185,6 +187,8 @@ public: void Destruct( ); + + private: diff --git a/source/gameengine/SceneGraph/SG_Spatial.cpp b/source/gameengine/SceneGraph/SG_Spatial.cpp index 77e805c0758..633e89b3e6a 100644 --- a/source/gameengine/SceneGraph/SG_Spatial.cpp +++ b/source/gameengine/SceneGraph/SG_Spatial.cpp @@ -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]))); +} + diff --git a/source/gameengine/SceneGraph/SG_Spatial.h b/source/gameengine/SceneGraph/SG_Spatial.h index 9536a4ff940..e029ce51919 100644 --- a/source/gameengine/SceneGraph/SG_Spatial.h +++ b/source/gameengine/SceneGraph/SG_Spatial.h @@ -37,10 +37,17 @@ #include #include // 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 index 00000000000..8e4c96c1536 --- /dev/null +++ b/source/gameengine/SceneGraph/SG_Tree.cpp @@ -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 + +#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 +class HalfArray +{ + std::vector > 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 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 index 00000000000..78c8411de8d --- /dev/null +++ b/source/gameengine/SceneGraph/SG_Tree.h @@ -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 + +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 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__ */ -- cgit v1.2.3