diff options
Diffstat (limited to 'source/gameengine/SceneGraph')
| -rw-r--r-- | source/gameengine/SceneGraph/CMakeLists.txt | 53 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_BBox.cpp | 262 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_BBox.h | 143 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Controller.cpp | 46 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Controller.h | 124 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_DList.h | 251 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_IObject.cpp | 111 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_IObject.h | 374 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Node.cpp | 224 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Node.h | 278 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_ParentRelation.h | 138 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_QList.h | 164 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Spatial.cpp | 216 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Spatial.h | 294 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Tree.cpp | 421 | ||||
| -rw-r--r-- | source/gameengine/SceneGraph/SG_Tree.h | 163 |
16 files changed, 0 insertions, 3262 deletions
diff --git a/source/gameengine/SceneGraph/CMakeLists.txt b/source/gameengine/SceneGraph/CMakeLists.txt deleted file mode 100644 index bbad429bbcd..00000000000 --- a/source/gameengine/SceneGraph/CMakeLists.txt +++ /dev/null @@ -1,53 +0,0 @@ -# ***** BEGIN GPL 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. -# -# 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. -# -# The Original Code is Copyright (C) 2006, Blender Foundation -# All rights reserved. -# -# The Original Code is: all of this file. -# -# Contributor(s): Jacques Beaurain. -# -# ***** END GPL LICENSE BLOCK ***** - -set(INC - . -) - -set(INC_SYS - ../../../intern/moto/include -) - -set(SRC - SG_BBox.cpp - SG_Controller.cpp - SG_IObject.cpp - SG_Node.cpp - SG_Spatial.cpp - SG_Tree.cpp - - SG_BBox.h - SG_Controller.h - SG_DList.h - SG_IObject.h - SG_Node.h - SG_ParentRelation.h - SG_QList.h - SG_Spatial.h - SG_Tree.h -) - -blender_add_lib(ge_scenegraph "${SRC}" "${INC}" "${INC_SYS}") diff --git a/source/gameengine/SceneGraph/SG_BBox.cpp b/source/gameengine/SceneGraph/SG_BBox.cpp deleted file mode 100644 index 9eaba788435..00000000000 --- a/source/gameengine/SceneGraph/SG_BBox.cpp +++ /dev/null @@ -1,262 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - * Bounding Box - */ - -/** \file gameengine/SceneGraph/SG_BBox.cpp - * \ingroup bgesg - */ - - -#include <math.h> - -#include "SG_BBox.h" -#include "SG_Node.h" - -SG_BBox::SG_BBox() : - m_min(0.0f, 0.0f, 0.0f), - m_max(0.0f, 0.0f, 0.0f) -{ -} - -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)) -{ - *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) : - m_min(other.m_min), - m_max(other.m_max) -{ -} - -SG_BBox::~ SG_BBox() -{ -} - -SG_BBox& SG_BBox::operator +=(const 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 += (const SG_BBox &bbox) -{ - *this += bbox.m_min; - *this += bbox.m_max; - - return *this; -} - -SG_BBox SG_BBox::operator +(const 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 center = (m_max - m_min)/2. + point; - m_max = (m_max - center)*size; - m_min = (m_min - center)*size; -} -#endif - -SG_BBox SG_BBox::transform(const MT_Transform &world) const -{ - 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 -{ - 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; -} - -void SG_BBox::getmm(MT_Point3 *box, const MT_Transform &world) const -{ - const MT_Point3 min(world(m_min)), max(world(m_max)); - *box++ = min; - *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.0f; - left.m_max[2] = m_max[2]; - - right.m_min[0] = m_min[0]; - right.m_min[1] = m_min[1] + sizey/2.0f; - 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.0f; - - right.m_min[0] = m_min[0]; - right.m_min[1] = m_min[1]; - right.m_min[2] = m_min[2] + sizez/2.0f; - 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.0f; - left.m_max[1] = m_max[1]; - left.m_max[2] = m_max[2]; - - right.m_min[0] = m_min[0] + sizex/2.0f; - 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.0f; - - right.m_min[0] = m_min[0]; - right.m_min[1] = m_min[1]; - right.m_min[2] = m_min[2] + sizez/2.0f; - 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; -} diff --git a/source/gameengine/SceneGraph/SG_BBox.h b/source/gameengine/SceneGraph/SG_BBox.h deleted file mode 100644 index 65fa417d25a..00000000000 --- a/source/gameengine/SceneGraph/SG_BBox.h +++ /dev/null @@ -1,143 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_BBox.h - * \ingroup bgesg - * \brief 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> - -#ifdef WITH_CXX_GUARDEDALLOC -#include "MEM_guardedalloc.h" -#endif - -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 +=(const MT_Point3 &point); - /** - * Enlarges the bounding box to contain the specified bound box. - */ - SG_BBox& operator +=(const SG_BBox &bbox); - - SG_BBox operator + (const 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.0f, 0.0f, 0.0f)); -#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; - - void getmm(MT_Point3 *box, const MT_Transform &world) const; - - void split(SG_BBox &left, SG_BBox &right) const; - - friend class SG_Tree; - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_BBox") -#endif -}; - -#endif /* __SG_BBOX_H__ */ diff --git a/source/gameengine/SceneGraph/SG_Controller.cpp b/source/gameengine/SceneGraph/SG_Controller.cpp deleted file mode 100644 index 1731b572fbd..00000000000 --- a/source/gameengine/SceneGraph/SG_Controller.cpp +++ /dev/null @@ -1,46 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file gameengine/SceneGraph/SG_Controller.cpp - * \ingroup bgesg - */ - -#include "SG_Controller.h" - - void -SG_Controller:: -SetObject(SG_IObject* obj) -{ - m_pObject = obj; // no checks yet ? -} - - void -SG_Controller:: -ClearObject( -) { - m_pObject = NULL; -} diff --git a/source/gameengine/SceneGraph/SG_Controller.h b/source/gameengine/SceneGraph/SG_Controller.h deleted file mode 100644 index 000be4f871a..00000000000 --- a/source/gameengine/SceneGraph/SG_Controller.h +++ /dev/null @@ -1,124 +0,0 @@ -/* - * Implementationclass to derive controllers from - * - * - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_Controller.h - * \ingroup bgesg - */ - -#ifndef __SG_CONTROLLER_H__ -#define __SG_CONTROLLER_H__ - -#include "SG_IObject.h" - -/** - * A scenegraph controller - */ -class SG_Controller -{ -public: - SG_Controller( - ) : - m_pObject(NULL) { - } - - virtual - ~SG_Controller( - ) {}; - - virtual - bool - Update( - double time - )=0; - - virtual - void - SetObject ( - SG_IObject* object - ); - - void - ClearObject( - ); - - virtual - void - SetSimulatedTime( - double time - )=0; - - virtual - SG_Controller* - GetReplica( - class SG_Node* destnode - )=0; - - /** - * Hacky way of passing options to specific controllers - * \param option An integer identifying the option. - * \param value The value of this option. - * \attention This has been placed here to give sca-elements - * \attention some control over the controllers. This is - * \attention necessary because the identity of the controller - * \attention is lost on the way here. - */ - virtual - void - SetOption( - int option, - int value - )=0; - - /** - * Option-identifiers: SG_CONTR_<controller-type>_<option>. - * Options only apply to a specific controller type. The - * semantics are defined by whoever uses the setting. - */ - enum SG_Controller_option { - SG_CONTR_NODEF = 0, - SG_CONTR_IPO_IPO_AS_FORCE, - SG_CONTR_IPO_IPO_ADD, - SG_CONTR_IPO_LOCAL, - SG_CONTR_IPO_RESET, - SG_CONTR_CAMIPO_LENS, - SG_CONTR_CAMIPO_CLIPEND, - SG_CONTR_CAMIPO_CLIPSTART, - SG_CONTR_MAX - }; - -protected: - SG_IObject* m_pObject; - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_Controller") -#endif -}; - -#endif /* __SG_CONTROLLER_H__ */ diff --git a/source/gameengine/SceneGraph/SG_DList.h b/source/gameengine/SceneGraph/SG_DList.h deleted file mode 100644 index 6e0998a197e..00000000000 --- a/source/gameengine/SceneGraph/SG_DList.h +++ /dev/null @@ -1,251 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_DList.h - * \ingroup bgesg - */ - -#ifndef __SG_DLIST_H__ -#define __SG_DLIST_H__ - -#include <stdlib.h> - -#ifdef WITH_CXX_GUARDEDALLOC -#include "MEM_guardedalloc.h" -#endif - -/** - * Double circular linked list - */ -class SG_DList -{ -protected : - SG_DList* m_flink; - SG_DList* m_blink; - -public: - template<typename T> class iterator - { - private: - SG_DList& m_head; - T* m_current; - public: - typedef iterator<T> _myT; - iterator(SG_DList& head) : m_head(head), m_current(NULL) {} - ~iterator() {} - - void begin() - { - m_current = (T*)m_head.Peek(); - } - void back() - { - m_current = (T*)m_head.Back(); - } - bool end() - { - return (m_current == (T*)m_head.Self()); - } - bool add_back(T* item) - { - return m_current->AddBack(item); - } - T* operator*() - { - return m_current; - } - _myT& operator++() - { - // no check of NULL! make sure you don't try to increment beyond end - m_current = (T*)m_current->Peek(); - return *this; - } - _myT& operator--() - { - // no check of NULL! make sure you don't try to increment beyond end - m_current = (T*)m_current->Back(); - return *this; - } - }; - - template<typename T> class const_iterator - { - private: - const SG_DList& m_head; - const T* m_current; - public: - typedef const_iterator<T> _myT; - const_iterator(const SG_DList& head) : m_head(head), m_current(NULL) {} - ~const_iterator() {} - - void begin() - { - m_current = (const T*)m_head.Peek(); - } - void back() - { - m_current = (const T*)m_head.Back(); - } - bool end() - { - return (m_current == (const T*)m_head.Self()); - } - const T* operator*() - { - return m_current; - } - _myT& operator++() - { - // no check of NULL! make sure you don't try to increment beyond end - m_current = (const T*)m_current->Peek(); - return *this; - } - _myT& operator--() - { - // no check of NULL! make sure you don't try to increment beyond end - m_current = (const T*)m_current->Back(); - return *this; - } - }; - - SG_DList() - { - m_flink = m_blink = this; - } - SG_DList(const SG_DList& other) - { - m_flink = m_blink = this; - } - virtual ~SG_DList() - { - Delink(); - } - - inline bool Empty() // Check for empty queue - { - return ( m_flink == this ); - } - bool AddBack( SG_DList *item ) // Add to the back - { - if (!item->Empty()) - return false; - item->m_blink = m_blink; - item->m_flink = this; - m_blink->m_flink = item; - m_blink = item; - return true; - } - bool AddFront( SG_DList *item ) // Add to the back - { - if (!item->Empty()) - return false; - item->m_flink = m_flink; - item->m_blink = this; - m_flink->m_blink = item; - m_flink = item; - return true; - } - SG_DList *Remove() // Remove from the front - { - if (Empty()) - { - return NULL; - } - SG_DList* item = m_flink; - m_flink = item->m_flink; - m_flink->m_blink = this; - item->m_flink = item->m_blink = item; - return item; - } - bool Delink() // Remove from the middle - { - if (Empty()) - return false; - m_blink->m_flink = m_flink; - m_flink->m_blink = m_blink; - m_flink = m_blink = this; - return true; - } - inline SG_DList *Peek() // Look at front without removing - { - return m_flink; - } - inline SG_DList *Back() // Look at front without removing - { - return m_blink; - } - inline SG_DList *Self() - { - return this; - } - inline const SG_DList *Peek() const // Look at front without removing - { - return (const SG_DList*)m_flink; - } - inline const SG_DList *Back() const // Look at front without removing - { - return (const SG_DList*)m_blink; - } - inline const SG_DList *Self() const - { - return this; - } - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_DList") -#endif -}; - -/** - * SG_DListHead : Template class that implements copy constructor to duplicate list automatically - * The elements of the list must have themselves a copy constructor. - */ -template<typename T> class SG_DListHead : public SG_DList -{ -public: - typedef SG_DListHead<T> _myT; - SG_DListHead() : SG_DList() {} - SG_DListHead(const _myT& other) : SG_DList() - { - // copy the list, assuming objects of type T - const_iterator<T> eit(other); - T* elem; - for (eit.begin(); !eit.end(); ++eit) { - elem = (*eit)->GetReplica(); - AddBack(elem); - } - } - virtual ~SG_DListHead() {} - T* Remove() - { - return static_cast<T*>(SG_DList::Remove()); - } - -}; - -#endif /* __SG_DLIST_H__ */ diff --git a/source/gameengine/SceneGraph/SG_IObject.cpp b/source/gameengine/SceneGraph/SG_IObject.cpp deleted file mode 100644 index 4e8c56da8a7..00000000000 --- a/source/gameengine/SceneGraph/SG_IObject.cpp +++ /dev/null @@ -1,111 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file gameengine/SceneGraph/SG_IObject.cpp - * \ingroup bgesg - */ - - -#include "SG_IObject.h" -#include "SG_Controller.h" - -#include <algorithm> - -SG_Stage gSG_Stage = SG_STAGE_UNKNOWN; - -SG_IObject:: -SG_IObject( - void* clientobj, - void* clientinfo, - SG_Callbacks& callbacks -): - SG_QList(), - m_SGclientObject(clientobj), - m_SGclientInfo(clientinfo) -{ - m_callbacks = callbacks; -} - -SG_IObject:: -SG_IObject( - const SG_IObject &other -) : - SG_QList(), - m_SGclientObject(other.m_SGclientObject), - m_SGclientInfo(other.m_SGclientInfo), - m_callbacks(other.m_callbacks) -{ - //nothing to do -} - - void -SG_IObject:: -AddSGController( - SG_Controller* cont -) { - m_SGcontrollers.push_back(cont); -} - - void -SG_IObject:: -RemoveSGController( - SG_Controller* cont -) { - SGControllerList::iterator contit; - - m_SGcontrollers.erase(std::remove(m_SGcontrollers.begin(), m_SGcontrollers.end(), cont)); -} - - void -SG_IObject:: -RemoveAllControllers( -) { - m_SGcontrollers.clear(); -} - -void SG_IObject::SetControllerTime(double time) -{ - SGControllerList::iterator contit; - for (contit = m_SGcontrollers.begin();contit!=m_SGcontrollers.end();++contit) - { - (*contit)->SetSimulatedTime(time); - } -} - -/// Needed for replication - - -SG_IObject:: -~SG_IObject() -{ - SGControllerList::iterator contit; - - for (contit = m_SGcontrollers.begin();contit!=m_SGcontrollers.end();++contit) - { - delete (*contit); - } -} diff --git a/source/gameengine/SceneGraph/SG_IObject.h b/source/gameengine/SceneGraph/SG_IObject.h deleted file mode 100644 index 91f53d04c90..00000000000 --- a/source/gameengine/SceneGraph/SG_IObject.h +++ /dev/null @@ -1,374 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_IObject.h - * \ingroup bgesg - */ - -#ifndef __SG_IOBJECT_H__ -#define __SG_IOBJECT_H__ - -#include "SG_QList.h" -#include <vector> - -// used for debugging: stage of the game engine main loop at which a Scenegraph modification is done -enum SG_Stage -{ - SG_STAGE_UNKNOWN = 0, - SG_STAGE_NETWORK, - SG_STAGE_NETWORK_UPDATE, - SG_STAGE_PHYSICS1, - SG_STAGE_PHYSICS1_UPDATE, - SG_STAGE_CONTROLLER, - SG_STAGE_CONTROLLER_UPDATE, - SG_STAGE_ACTUATOR, - SG_STAGE_ACTUATOR_UPDATE, - SG_STAGE_ANIMATION_UPDATE, - SG_STAGE_PHYSICS2, - SG_STAGE_PHYSICS2_UPDATE, - SG_STAGE_SCENE, - SG_STAGE_RENDER, - SG_STAGE_CONVERTER, - SG_STAGE_CULLING, - SG_STAGE_MAX -}; - -extern SG_Stage gSG_Stage; - -inline void SG_SetActiveStage(SG_Stage stage) -{ - gSG_Stage = stage; -} - - - -class SG_Controller; -class SG_IObject; - -typedef std::vector<SG_Controller*> SGControllerList; - -typedef void* (*SG_ReplicationNewCallback)( - SG_IObject* sgobject, - void* clientobj, - void* clientinfo -); - -typedef void* (*SG_DestructionNewCallback)( - SG_IObject* sgobject, - void* clientobj, - void* clientinfo -); - -typedef void (*SG_UpdateTransformCallback)( - SG_IObject* sgobject, - void* clientobj, - void* clientinfo -); - -typedef bool (*SG_ScheduleUpdateCallback)( - SG_IObject* sgobject, - void* clientobj, - void* clientinfo -); - -typedef bool (*SG_RescheduleUpdateCallback)( - SG_IObject* sgobject, - void* clientobj, - void* clientinfo -); - - -/** - * SG_Callbacks hold 2 call backs to the outside world. - * The first is meant to be called when objects are replicated. - * And allows the outside world to synchronize external objects - * with replicated nodes and their children. - * The second is called when a node is destroyed and again - * is their for synchronization purposes - * These callbacks may both be NULL. - * The efficacy of this approach has not been proved some - * alternatives might be to perform all replication and destruction - * externally. - * To define a class interface rather than a simple function - * call back so that replication information can be transmitted from - * parent->child. - */ -struct SG_Callbacks -{ - SG_Callbacks( - ): - m_replicafunc(NULL), - m_destructionfunc(NULL), - m_updatefunc(NULL), - m_schedulefunc(NULL), - m_reschedulefunc(NULL) - { - } - - SG_Callbacks( - SG_ReplicationNewCallback repfunc, - SG_DestructionNewCallback destructfunc, - SG_UpdateTransformCallback updatefunc, - SG_ScheduleUpdateCallback schedulefunc, - SG_RescheduleUpdateCallback reschedulefunc - ): - m_replicafunc(repfunc), - m_destructionfunc(destructfunc), - m_updatefunc(updatefunc), - m_schedulefunc(schedulefunc), - m_reschedulefunc(reschedulefunc) - { - } - - SG_ReplicationNewCallback m_replicafunc; - SG_DestructionNewCallback m_destructionfunc; - SG_UpdateTransformCallback m_updatefunc; - SG_ScheduleUpdateCallback m_schedulefunc; - SG_RescheduleUpdateCallback m_reschedulefunc; -}; - -/** - * base object that can be part of the scenegraph. - */ -class SG_IObject : public SG_QList -{ -private : - - void* m_SGclientObject; - void* m_SGclientInfo; - SG_Callbacks m_callbacks; - SGControllerList m_SGcontrollers; - -public: - virtual ~SG_IObject(); - - - /** - * Add a pointer to a controller allocated on the heap, to - * this node. This memory for this controller becomes the - * responsibility of this class. It will be deleted when - * this object is deleted. - */ - - void - AddSGController( - SG_Controller* cont - ); - - /** - * Remove a pointer to a controller from this node. - * This does not delete the controller itself! Be careful to - * avoid memory leaks. - */ - void - RemoveSGController( - SG_Controller* cont - ); - - /** - * Clear the array of pointers to controllers associated with - * this node. This does not delete the controllers themselves! - * This should be used very carefully to avoid memory - * leaks. - */ - - void - RemoveAllControllers( - ); - - /// Needed for replication - - /** - * Return a reference to this node's controller list. - * Whilst we don't wish to expose full control of the container - * to the user we do allow them to call non_const methods - * on pointers in the container. C++ topic: how to do this in - * using STL? - */ - - SGControllerList& GetSGControllerList() - { - return m_SGcontrollers; - } - - /** - * - */ - SG_Callbacks& GetCallBackFunctions() - { - return m_callbacks; - } - - /** - * Get the client object associated with this - * node. This interface allows you to associate - * arbitrary external objects with this node. They are - * passed to the callback functions when they are - * activated so you can synchronize these external objects - * upon replication and destruction - * This may be NULL. - */ - - inline const void* GetSGClientObject() const - { - return m_SGclientObject; - } - - inline void* GetSGClientObject() - { - return m_SGclientObject; - } - - /** - * Set the client object for this node. This is just a - * pointer to an object allocated that should exist for - * the duration of the lifetime of this object, or until - * this function is called again. - */ - - void SetSGClientObject(void* clientObject) - { - m_SGclientObject = clientObject; - } - - - /* needed for scene switching */ - inline const void* GetSGClientInfo() const - { - return m_SGclientInfo; - } - inline void* GetSGClientInfo() - { - return m_SGclientInfo; - } - void SetSGClientInfo(void* clientInfo) - { - m_SGclientInfo = clientInfo; - } - - - /** - * Set the current simulation time for this node. - * The implementation of this function runs through - * the nodes list of controllers and calls their SetSimulatedTime methods - */ - - void SetControllerTime(double time); - - virtual - void - Destruct( - ) = 0; - -protected : - - bool - ActivateReplicationCallback( - SG_IObject *replica - ) - { - if (m_callbacks.m_replicafunc) - { - // Call client provided replication func - if (m_callbacks.m_replicafunc(replica,m_SGclientObject,m_SGclientInfo) == NULL) - return false; - } - return true; - } - - - void - ActivateDestructionCallback( - ) - { - if (m_callbacks.m_destructionfunc) - { - // Call client provided destruction function on this! - m_callbacks.m_destructionfunc(this,m_SGclientObject,m_SGclientInfo); - } - else - { - // no callback but must still destroy the node to avoid memory leak - delete this; - } - } - - void - ActivateUpdateTransformCallback( - ) - { - if (m_callbacks.m_updatefunc) - { - // Call client provided update func. - m_callbacks.m_updatefunc(this, m_SGclientObject, m_SGclientInfo); - } - } - - bool - ActivateScheduleUpdateCallback( - ) - { - // HACK, this check assumes that the scheduled nodes are put on a DList (see SG_Node.h) - // The early check on Empty() allows up to avoid calling the callback function - // when the node is already scheduled for update. - if (Empty() && m_callbacks.m_schedulefunc) - { - // Call client provided update func. - return m_callbacks.m_schedulefunc(this, m_SGclientObject, m_SGclientInfo); - } - return false; - } - - void - ActivateRecheduleUpdateCallback( - ) - { - if (m_callbacks.m_reschedulefunc) - { - // Call client provided update func. - m_callbacks.m_reschedulefunc(this, m_SGclientObject, m_SGclientInfo); - } - } - - - SG_IObject( - void* clientobj, - void* clientinfo, - SG_Callbacks& callbacks - ); - - SG_IObject( - const SG_IObject &other - ); - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_IObject") -#endif -}; - -#endif /* __SG_IOBJECT_H__ */ diff --git a/source/gameengine/SceneGraph/SG_Node.cpp b/source/gameengine/SceneGraph/SG_Node.cpp deleted file mode 100644 index 9688de097ba..00000000000 --- a/source/gameengine/SceneGraph/SG_Node.cpp +++ /dev/null @@ -1,224 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file gameengine/SceneGraph/SG_Node.cpp - * \ingroup bgesg - */ - - -#include "SG_Node.h" -#include "SG_ParentRelation.h" -#include <algorithm> - -using namespace std; - - -SG_Node::SG_Node( - void* clientobj, - void* clientinfo, - SG_Callbacks& callbacks - -) - : SG_Spatial(clientobj,clientinfo,callbacks), - m_SGparent(NULL) -{ - m_modified = true; -} - -SG_Node::SG_Node( - const SG_Node & other -) : - SG_Spatial(other), - m_children(other.m_children), - m_SGparent(other.m_SGparent) -{ - m_modified = true; -} - -SG_Node::~SG_Node() -{ -} - - -SG_Node* SG_Node::GetSGReplica() -{ - SG_Node* replica = new SG_Node(*this); - if (replica == NULL) return NULL; - - ProcessSGReplica(&replica); - - return replica; -} - - void -SG_Node:: -ProcessSGReplica( - SG_Node** replica -) { - // Apply the replication call back function. - if (!ActivateReplicationCallback(*replica)) - { - delete (*replica); - *replica = NULL; - return; - } - - // clear the replica node of it's parent. - static_cast<SG_Node*>(*replica)->m_SGparent = NULL; - - if (m_children.begin() != m_children.end()) - { - // if this node has children, the replica has too, so clear and clone children - (*replica)->ClearSGChildren(); - - NodeList::iterator childit; - for (childit = m_children.begin();childit!=m_children.end();++childit) - { - SG_Node* childnode = (*childit)->GetSGReplica(); - if (childnode) - (*replica)->AddChild(childnode); - } - } - // Nodes without children and without client object are - // not worth to keep, they will just take up CPU - // This can happen in partial replication of hierarchy - // during group duplication. - if ((*replica)->m_children.empty() && - (*replica)->GetSGClientObject() == NULL) - { - delete (*replica); - *replica = NULL; - } -} - - - void -SG_Node:: -Destruct() -{ - // Not entirely sure what Destruct() expects to happen. - // I think it probably means just to call the DestructionCallback - // in the right order on all the children - rather than free any memory - - // We'll delete m_parent_relation now anyway. - - delete(m_parent_relation); - m_parent_relation = NULL; - - if (m_children.begin() != m_children.end()) - { - NodeList::iterator childit; - for (childit = m_children.begin();childit!=m_children.end();++childit) - { - // call the SG_Node destruct method on each of our children }-) - (*childit)->Destruct(); - } - } - - ActivateDestructionCallback(); -} - -const - SG_Node * -SG_Node:: -GetRootSGParent( -) const { - return (m_SGparent ? (const SG_Node*) m_SGparent->GetRootSGParent() : (const SG_Node*) this); -} - -bool SG_Node::IsAncessor(const SG_Node* child) const -{ - return (!child->m_SGparent) ? false : - (child->m_SGparent == this) ? true : IsAncessor(child->m_SGparent); -} - - void -SG_Node:: -DisconnectFromParent( -) { - if (m_SGparent) - { - m_SGparent->RemoveChild(this); - m_SGparent = NULL; - } - -} - -void SG_Node::AddChild(SG_Node* child) -{ - m_children.push_back(child); - child->SetSGParent(this); // this way ? -} - -void SG_Node::RemoveChild(SG_Node* child) -{ - NodeList::iterator childfound = find(m_children.begin(),m_children.end(),child); - - if (childfound != m_children.end()) - { - m_children.erase(childfound); - } -} - - - -void SG_Node::UpdateWorldData(double time, bool parentUpdated) -{ - //if (!GetSGParent()) - // return; - - if (UpdateSpatialData(GetSGParent(),time,parentUpdated)) - // to update the - ActivateUpdateTransformCallback(); - - // The node is updated, remove it from the update list - Delink(); - - // update children's worlddata - for (NodeList::iterator it = m_children.begin();it!=m_children.end();++it) - { - (*it)->UpdateWorldData(time, parentUpdated); - } -} - - - -void SG_Node::SetSimulatedTime(double time,bool recurse) -{ - - // update the controllers of this node. - SetControllerTime(time); - - // update children's simulate time. - if (recurse) - { - for (NodeList::iterator it = m_children.begin();it!=m_children.end();++it) - { - (*it)->SetSimulatedTime(time,recurse); - } - } -} diff --git a/source/gameengine/SceneGraph/SG_Node.h b/source/gameengine/SceneGraph/SG_Node.h deleted file mode 100644 index 8043fed082c..00000000000 --- a/source/gameengine/SceneGraph/SG_Node.h +++ /dev/null @@ -1,278 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_Node.h - * \ingroup bgesg - */ - -#ifndef __SG_NODE_H__ -#define __SG_NODE_H__ - -#include "SG_Spatial.h" -#include <vector> - -typedef std::vector<SG_Node*> NodeList; - -/** - * Scenegraph node. - */ -class SG_Node : public SG_Spatial -{ -public: - SG_Node( - void* clientobj, - void* clientinfo, - SG_Callbacks& callbacks - ); - - SG_Node( - const SG_Node & other - ); - - virtual ~SG_Node(); - - - /** - * Add a child to this object. This also informs the child of - * it's parent. - * This just stores a pointer to the child and does not - * make a deep copy. - */ - - void - AddChild( - SG_Node* child - ); - - /** - * Remove a child node from this object. This just removes the child - * pointer from the list of children - it does not destroy the child. - * This does not inform the child that this node is no longer it's parent. - * If the node was not a child of this object no action is performed. - */ - - void - RemoveChild( - SG_Node* child - ); - - /** - * Return true if the node is the ancestor of child - */ - bool - IsAncessor( - const SG_Node* child - ) const; - /** - * Get the current list of children. Do not use this interface for - * adding or removing children please use the methods of this class for - * that. - * \return a reference to the list of children of this node. - */ - - NodeList& GetSGChildren() - { - return this->m_children; - } - - /** - * Get the current list of children. - * \return a const reference to the current list of children of this node. - */ - - const NodeList& GetSGChildren() const - { - return this->m_children; - } - - /** - * Clear the list of children associated with this node - */ - - void ClearSGChildren() - { - m_children.clear(); - } - - /** - * return the parent of this node if it exists. - */ - - SG_Node* GetSGParent() const - { - return m_SGparent; - } - - /** - * Set the parent of this node. - */ - - void SetSGParent(SG_Node* parent) - { - m_SGparent = parent; - } - - /** - * Return the top node in this node's Scene graph hierarchy - */ - - const - SG_Node* - GetRootSGParent( - ) const; - - /** - * Disconnect this node from it's parent - */ - - void - DisconnectFromParent( - ); - - /** - * Return vertex parent status. - */ - bool IsVertexParent() - { - if (m_parent_relation) - { - return m_parent_relation->IsVertexRelation(); - } - return false; - } - - - /** - * Return slow parent status. - */ - - bool IsSlowParent() - { - if (m_parent_relation) - { - return m_parent_relation->IsSlowRelation(); - } - return false; - } - - - - - /** - * Update the spatial data of this node. Iterate through - * the children of this node and update their world data. - */ - - void - UpdateWorldData( - double time, - bool parentUpdated=false - ); - - /** - * Update the simulation time of this node. Iterate through - * the children nodes and update their simulated time. - */ - - void - SetSimulatedTime( - double time, - bool recurse - ); - - /** - * Schedule this node for update by placing it in head queue - */ - bool Schedule(SG_QList& head) - { - // Put top parent in front of list to make sure they are updated before their - // children => the children will be udpated and removed from the list before - // we get to them, should they be in the list too. - return (m_SGparent)?head.AddBack(this):head.AddFront(this); - } - - /** - * Used during Scenegraph update - */ - static SG_Node* GetNextScheduled(SG_QList& head) - { - return static_cast<SG_Node*>(head.Remove()); - } - - /** - * Make this node ready for schedule on next update. This is needed for nodes - * that must always be updated (slow parent, bone parent) - */ - bool Reschedule(SG_QList& head) - { - return head.QAddBack(this); - } - - /** - * Used during Scenegraph update - */ - static SG_Node* GetNextRescheduled(SG_QList& head) - { - return static_cast<SG_Node*>(head.QRemove()); - } - - /** - * Node replication functions. - */ - - SG_Node* - GetSGReplica( - ); - - void - Destruct( - ); - -private: - - void - ProcessSGReplica( - SG_Node** replica - ); - - /** - * The list of children of this node. - */ - NodeList m_children; - - /** - * The parent of this node may be NULL - */ - SG_Node* m_SGparent; - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_Node") -#endif -}; - -#endif /* __SG_NODE_H__ */ diff --git a/source/gameengine/SceneGraph/SG_ParentRelation.h b/source/gameengine/SceneGraph/SG_ParentRelation.h deleted file mode 100644 index e8bd46a1a65..00000000000 --- a/source/gameengine/SceneGraph/SG_ParentRelation.h +++ /dev/null @@ -1,138 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - * - */ - -/** \file SG_ParentRelation.h - * \ingroup bgesg - * \page SG_ParentRelationPage SG_ParentRelation - * - * \section SG_ParentRelationSection SG_ParentRelation - * - * This is an abstract interface class to the Scene Graph library. - * It allows you to specify how child nodes react to parent nodes. - * Normally a child will use it's parent's transforms to compute - * it's own global transforms. How this is performed depends on - * the type of relation. For example if the parent is a vertex - * parent to this child then the child should not inherit any - * rotation information from the parent. Or if the parent is a - * 'slow parent' to this child then the child should react - * slowly to changes in the parent's position. The exact relation - * is left for you to implement by filling out this interface - * with concrete examples. - * - * There is exactly one SG_ParentRelation per SG_Node. Subclasses - * should not be value types and should be allocated on the heap. - * - */ - -#ifndef __SG_PARENTRELATION_H__ -#define __SG_PARENTRELATION_H__ - -class SG_Spatial; - -class SG_ParentRelation { - -public : - /** - * Update the childs local and global coordinates - * based upon the parents global coordinates. - * You must also handle the case when this node has no - * parent (parent == NULL). Usually you should just - * copy the local coordinates of the child to the - * world coordinates. - */ - - virtual - bool - UpdateChildCoordinates( - SG_Spatial * child, - const SG_Spatial * parent, - bool& parentUpdated - ) = 0; - - virtual - ~SG_ParentRelation( - ) {}; - - /** - * You must provide a way of duplicating an - * instance of an SG_ParentRelation. This should - * return a pointer to a new duplicate allocated - * on the heap. Responsibility for deleting the - * duplicate resides with the caller of this method. - */ - - virtual - SG_ParentRelation * - NewCopy( - ) = 0; - - /** - * Vertex Parent Relation are special: they don't propagate rotation - */ - virtual - bool - IsVertexRelation( - ) { - return false; - } - - /** - * Need this to see if we are able to adjust time-offset from the python api - */ - virtual - bool - IsSlowRelation( - ) { - return false; - } -protected : - - /** - * Protected constructors - * this class is not meant to be instantiated. - */ - - SG_ParentRelation( - ) { - }; - - /** - * Copy construction should not be implemented - */ - - SG_ParentRelation( - const SG_ParentRelation & - ); - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_ParentRelation") -#endif -}; - -#endif diff --git a/source/gameengine/SceneGraph/SG_QList.h b/source/gameengine/SceneGraph/SG_QList.h deleted file mode 100644 index baf5f52f3e6..00000000000 --- a/source/gameengine/SceneGraph/SG_QList.h +++ /dev/null @@ -1,164 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_QList.h - * \ingroup bgesg - */ - -#ifndef __SG_QLIST_H__ -#define __SG_QLIST_H__ - -#include "SG_DList.h" - -/** - * Double-Double circular linked list - * For storing an object is two lists simultaneously - */ -class SG_QList : public SG_DList -{ -protected : - SG_QList* m_fqlink; - SG_QList* m_bqlink; - -public: - template<typename T> class iterator - { - private: - SG_QList& m_head; - T* m_current; - public: - typedef iterator<T> _myT; - iterator(SG_QList& head, SG_QList* current=NULL) : m_head(head) { m_current = (T*)current; } - ~iterator() {} - - void begin() - { - m_current = (T*)m_head.QPeek(); - } - void back() - { - m_current = (T*)m_head.QBack(); - } - bool end() - { - return (m_current == (T*)m_head.Self()); - } - bool add_back(T* item) - { - return m_current->QAddBack(item); - } - T* operator*() - { - return m_current; - } - _myT& operator++() - { - m_current = (T*)m_current->QPeek(); - return *this; - } - _myT& operator--() - { - // no check on NULL! make sure you don't try to increment beyond end - m_current = (T*)m_current->QBack(); - return *this; - } - }; - - SG_QList() : SG_DList() - { - m_fqlink = m_bqlink = this; - } - SG_QList(const SG_QList& other) : SG_DList() - { - m_fqlink = m_bqlink = this; - } - virtual ~SG_QList() - { - QDelink(); - } - - inline bool QEmpty() // Check for empty queue - { - return ( m_fqlink == this ); - } - bool QAddBack( SG_QList *item ) // Add to the back - { - if (!item->QEmpty()) - return false; - item->m_bqlink = m_bqlink; - item->m_fqlink = this; - m_bqlink->m_fqlink = item; - m_bqlink = item; - return true; - } - bool QAddFront( SG_QList *item ) // Add to the back - { - if (!item->Empty()) - return false; - item->m_fqlink = m_fqlink; - item->m_bqlink = this; - m_fqlink->m_bqlink = item; - m_fqlink = item; - return true; - } - SG_QList *QRemove() // Remove from the front - { - if (QEmpty()) - { - return NULL; - } - SG_QList* item = m_fqlink; - m_fqlink = item->m_fqlink; - m_fqlink->m_bqlink = this; - item->m_fqlink = item->m_bqlink = item; - return item; - } - bool QDelink() // Remove from the middle - { - if (QEmpty()) - return false; - m_bqlink->m_fqlink = m_fqlink; - m_fqlink->m_bqlink = m_bqlink; - m_fqlink = m_bqlink = this; - return true; - } - inline SG_QList *QPeek() // Look at front without removing - { - return m_fqlink; - } - inline SG_QList *QBack() // Look at front without removing - { - return m_bqlink; - } - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_QList") -#endif -}; - -#endif /* __SG_QLIST_H__ */ diff --git a/source/gameengine/SceneGraph/SG_Spatial.cpp b/source/gameengine/SceneGraph/SG_Spatial.cpp deleted file mode 100644 index 40682249355..00000000000 --- a/source/gameengine/SceneGraph/SG_Spatial.cpp +++ /dev/null @@ -1,216 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file gameengine/SceneGraph/SG_Spatial.cpp - * \ingroup bgesg - */ - - -#include "SG_Node.h" -#include "SG_Spatial.h" -#include "SG_Controller.h" -#include "SG_ParentRelation.h" - -SG_Spatial:: -SG_Spatial( - void* clientobj, - void* clientinfo, - SG_Callbacks& callbacks -): - - SG_IObject(clientobj,clientinfo,callbacks), - m_localPosition(0.0f,0.0f,0.0f), - m_localRotation(1.0f,0.0f,0.0f,0.0f,1.0f,0.0f,0.0f,0.0f,1.0f), - m_localScaling(1.0f,1.0f,1.0f), - - m_worldPosition(0.0f,0.0f,0.0f), - m_worldRotation(1.0f,0.0f,0.0f,0.0f,1.0f,0.0f,0.0f,0.0f,1.0f), - m_worldScaling(1.0f,1.0f,1.0f), - - m_parent_relation (NULL), - - m_bbox(MT_Point3(-1.0f, -1.0f, -1.0f), MT_Point3(1.0f, 1.0f, 1.0f)), - m_radius(1.0f), - m_modified(false), - m_ogldirty(false) -{ -} - -SG_Spatial:: -SG_Spatial( - const SG_Spatial& other -) : - SG_IObject(other), - m_localPosition(other.m_localPosition), - m_localRotation(other.m_localRotation), - m_localScaling(other.m_localScaling), - - m_worldPosition(other.m_worldPosition), - m_worldRotation(other.m_worldRotation), - m_worldScaling(other.m_worldScaling), - - m_parent_relation(NULL), - - m_bbox(other.m_bbox), - m_radius(other.m_radius), - m_modified(false), - m_ogldirty(false) -{ - // duplicate the parent relation for this object - m_parent_relation = other.m_parent_relation->NewCopy(); -} - -SG_Spatial:: -~SG_Spatial() -{ - delete (m_parent_relation); -} - - void -SG_Spatial:: -SetParentRelation( - SG_ParentRelation *relation -) { - delete (m_parent_relation); - m_parent_relation = relation; - SetModified(); -} - - -/** - * Update Spatial Data. - * Calculates WorldTransform., (either doing its self or using the linked SGControllers) - */ - - - bool -SG_Spatial:: -UpdateSpatialData( - const SG_Spatial *parent, - double time, - bool& parentUpdated) -{ - bool bComputesWorldTransform = false; - - // update spatial controllers - - SGControllerList::iterator cit = GetSGControllerList().begin(); - SGControllerList::const_iterator c_end = GetSGControllerList().end(); - - for (;cit!=c_end;++cit) - { - if ((*cit)->Update(time)) - bComputesWorldTransform = true; - } - - // If none of the objects updated our values then we ask the - // parent_relation object owned by this class to update - // our world coordinates. - - if (!bComputesWorldTransform) - bComputesWorldTransform = ComputeWorldTransforms(parent, parentUpdated); - - return bComputesWorldTransform; -} - -/** - * Position and translation methods - */ - - - void -SG_Spatial:: -RelativeTranslate( - const MT_Vector3& trans, - const SG_Spatial *parent, - bool local -) { - if (local) { - m_localPosition += m_localRotation * trans; - } - else { - if (parent) { - m_localPosition += trans * parent->GetWorldOrientation(); - } - else { - m_localPosition += trans; - } - } - SetModified(); -} - - -/** - * Scaling methods. - */ - - -/** - * Orientation and rotation methods. - */ - - - void -SG_Spatial:: -RelativeRotate( - const MT_Matrix3x3& rot, - bool local -) { - m_localRotation = m_localRotation * ( - local ? - rot - : - (GetWorldOrientation().inverse() * rot * GetWorldOrientation())); - SetModified(); -} - - - -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 -{ - 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, GetWorldTransform()); -} - -void SG_Spatial::getAABBox(MT_Point3 *box) const -{ - m_bbox.getaa(box, GetWorldTransform()); -} diff --git a/source/gameengine/SceneGraph/SG_Spatial.h b/source/gameengine/SceneGraph/SG_Spatial.h deleted file mode 100644 index 7fa21506675..00000000000 --- a/source/gameengine/SceneGraph/SG_Spatial.h +++ /dev/null @@ -1,294 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_Spatial.h - * \ingroup bgesg - */ - -#ifndef __SG_SPATIAL_H__ -#define __SG_SPATIAL_H__ - -#include <MT_Vector3.h> -#include <MT_Point3.h> -#include <MT_Matrix3x3.h> // or Quaternion later ? -#include "SG_IObject.h" -#include "SG_BBox.h" -#include "SG_ParentRelation.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 -{ - -protected: - MT_Point3 m_localPosition; - MT_Matrix3x3 m_localRotation; - MT_Vector3 m_localScaling; - - MT_Point3 m_worldPosition; - MT_Matrix3x3 m_worldRotation; - MT_Vector3 m_worldScaling; - - SG_ParentRelation * m_parent_relation; - - SG_BBox m_bbox; - MT_Scalar m_radius; - bool m_modified; - bool m_ogldirty; // true if the openGL matrix for this object must be recomputed - -public: - inline void ClearModified() - { - m_modified = false; - m_ogldirty = true; - } - inline void SetModified() - { - m_modified = true; - ActivateScheduleUpdateCallback(); - } - inline void ClearDirty() - { - m_ogldirty = false; - } - /** - * Define the relationship this node has with it's parent - * node. You should pass an unshared instance of an SG_ParentRelation - * allocated on the heap to this method. Ownership of this - * instance is assumed by this class. - * You may call this function several times in the lifetime - * of a node to change the relationship dynamically. - * You must call this method before the first call to UpdateSpatialData(). - * An assertion will be fired at run-time in debug if this is not - * the case. - * The relation is activated only if no controllers of this object - * updated the coordinates of the child. - */ - - void - SetParentRelation( - SG_ParentRelation *relation - ); - - SG_ParentRelation * GetParentRelation() - { - return m_parent_relation; - } - - - - - /** - * Apply a translation relative to the current position. - * if local then the translation is assumed to be in the - * local coordinates of this object. If not then the translation - * is assumed to be in global coordinates. In this case - * you must provide a pointer to the parent of this object if it - * exists otherwise if there is no parent set it to NULL - */ - - void - RelativeTranslate( - const MT_Vector3& trans, - const SG_Spatial *parent, - bool local - ); - - void SetLocalPosition(const MT_Point3& trans) - { - m_localPosition = trans; - SetModified(); - } - - void SetWorldPosition(const MT_Point3& trans) - { - m_worldPosition = trans; - } - - - void - RelativeRotate( - const MT_Matrix3x3& rot, - bool local - ); - - void SetLocalOrientation(const MT_Matrix3x3& rot) - { - m_localRotation = rot; - SetModified(); - } - - // rot is arrange like openGL matrix - void SetLocalOrientation(const float* rot) - { - m_localRotation.setValue(rot); - SetModified(); - } - - void SetWorldOrientation(const MT_Matrix3x3& rot) - { - m_worldRotation = rot; - } - - void RelativeScale(const MT_Vector3& scale) - { - m_localScaling = m_localScaling * scale; - SetModified(); - } - - void SetLocalScale(const MT_Vector3& scale) - { - m_localScaling = scale; - SetModified(); - } - - void SetWorldScale(const MT_Vector3& scale) - { - m_worldScaling = scale; - } - - const MT_Point3& GetLocalPosition() const - { - return m_localPosition; - } - - const MT_Matrix3x3& GetLocalOrientation() const - { - return m_localRotation; - } - - const MT_Vector3& GetLocalScale() const - { - return m_localScaling; - } - - const MT_Point3& GetWorldPosition() const - { - return m_worldPosition; - } - - const MT_Matrix3x3& GetWorldOrientation() const - { - return m_worldRotation; - } - - const MT_Vector3& GetWorldScaling() const - { - return m_worldScaling; - } - - void SetWorldFromLocalTransform() - { - m_worldPosition= m_localPosition; - m_worldScaling= m_localScaling; - m_worldRotation= m_localRotation; - } - - - - MT_Transform GetWorldTransform() const; - - bool ComputeWorldTransforms(const SG_Spatial *parent, bool& parentUpdated) - { - return m_parent_relation->UpdateChildCoordinates(this,parent,parentUpdated); - } - - - /** - * Bounding box functions. - */ - SG_BBox& BBox() - { - return m_bbox; - } - - void SetBBox(SG_BBox& bbox) - { - m_bbox = bbox; - } - - - 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; } - bool IsModified() { return m_modified; } - bool IsDirty() { return m_ogldirty; } - -protected: - friend class SG_Controller; - friend class KX_BoneParentRelation; - friend class KX_VertexParentRelation; - friend class KX_SlowParentRelation; - friend class KX_NormalParentRelation; - - /** - * Protected constructor this class is not - * designed for direct instantiation - */ - - SG_Spatial( - void* clientobj, - void* clientinfo, - SG_Callbacks& callbacks - ); - - SG_Spatial( - const SG_Spatial& other - ); - - - virtual ~SG_Spatial(); - - /** - * Update the world coordinates of this spatial node. This also informs - * any controllers to update this object. - */ - - bool - UpdateSpatialData( - const SG_Spatial *parent, - double time, - bool& parentUpdated - ); - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_Spatial") -#endif -}; - -#endif /* __SG_SPATIAL_H__ */ diff --git a/source/gameengine/SceneGraph/SG_Tree.cpp b/source/gameengine/SceneGraph/SG_Tree.cpp deleted file mode 100644 index d0cf74038d1..00000000000 --- a/source/gameengine/SceneGraph/SG_Tree.cpp +++ /dev/null @@ -1,421 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - * Bounding Box - */ - -/** \file gameengine/SceneGraph/SG_Tree.cpp - * \ingroup bgesg - */ - - -#include <math.h> - -#include "SG_BBox.h" -#include "SG_Tree.h" -#include "SG_Node.h" - -SG_Tree::SG_Tree() : - m_left(NULL), - m_right(NULL), - m_parent(NULL), - m_radius(0.0f), - m_client_object(NULL) -{ -} - -SG_Tree::SG_Tree(SG_Tree* left, SG_Tree* right) : - m_left(left), - m_right(right), - m_parent(NULL), - m_client_object(NULL) -{ - 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_center = (m_bbox.m_min + m_bbox.m_max)/2.0f; - m_radius = (m_bbox.m_max - m_bbox.m_min).length(); -} - -SG_Tree::SG_Tree(SG_Node* client) : - m_left(NULL), - m_right(NULL), - m_parent(NULL), - m_client_object(client) -{ - m_bbox = SG_BBox(client->BBox(), client->GetWorldTransform()); - m_center = (m_bbox.m_min + m_bbox.m_max)/2.0f; - m_radius = (m_bbox.m_max - m_bbox.m_min).length(); -} - -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 -{ - MT_Transform identity; - identity.setIdentity(); - m_bbox.get(box, identity); -} - -bool SG_Tree::inside(const MT_Point3 &point) const -{ - return m_bbox.inside(point); -} - -const SG_BBox& SG_Tree::BBox() const -{ - return m_bbox; -} - -void SG_Tree::SetLeft(SG_Tree *left) -{ - m_left = left; - m_bbox += left->m_bbox; - m_center = (m_bbox.m_min + m_bbox.m_max)/2.0f; - m_radius = (m_bbox.m_max - m_bbox.m_min).length(); -} - -void SG_Tree::SetRight(SG_Tree *right) -{ - m_right = right; - m_bbox += right->m_bbox; - m_center = (m_bbox.m_min + m_bbox.m_max)/2.0f; - m_radius = (m_bbox.m_max - m_bbox.m_min).length(); -} - -/** - * 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_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.empty()) - 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.0f) - 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.begin(); - - HalfArray<SG_Tree*> sizes; - sizes.resize(num_objects); - - unsigned int x, y; - TreeSet::iterator xit, yit; - for ( y = 0, yit = m_objects.begin(); y < num_objects; y++, ++yit) - { - sizes(y, y) = *yit; - xit = yit; - for ( x = y+1, ++xit; x < num_objects; x++, ++xit) - { - sizes(x, y) = new SG_Tree(*xit, *yit); - - } - } - while (num_objects > 2) - { - /* Find the pair of bboxes that produce the smallest combined bbox. */ - unsigned int minx = UINT_MAX, miny = UINT_MAX; - MT_Scalar min_volume = FLT_MAX; - SG_Tree *min = NULL; - //char temp[16]; - for ( y = 0; y < num_objects; y++) - { - for ( x = y+1; x < num_objects; x++) - { - if (sizes(x, y)->volume() < min_volume) - { - min = sizes(x, y); - minx = x; - miny = y; - min_volume = sizes(x, y)->volume(); - } - } - } - - /* Remove other bboxes that contain the two bboxes */ - sizes.delete_column(miny); - - for ( 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 ( x = minx + 1; x < num_objects; x++) - { - delete sizes(x, minx); - sizes(x, minx) = new SG_Tree(min, sizes(x, x)); - } - for ( 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 deleted file mode 100644 index b0eaea814e8..00000000000 --- a/source/gameengine/SceneGraph/SG_Tree.h +++ /dev/null @@ -1,163 +0,0 @@ -/* - * ***** BEGIN GPL 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 LICENSE BLOCK ***** - */ - -/** \file SG_Tree.h - * \ingroup bgesg - */ - -#ifndef __SG_TREE_H__ -#define __SG_TREE_H__ - -#include "MT_Point3.h" -#include "SG_BBox.h" - -#include <set> - -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; - MT_Point3 m_center; - MT_Scalar m_radius; - 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; - - void SetLeft(SG_Tree *left); - void SetRight(SG_Tree *right); - - MT_Point3 Center() const { return m_center; } - 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(); - } - }; - - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_Tree") -#endif -}; - - -/** - * SG_TreeFactory generates an SG_Tree from a list of SG_Nodes. - * It joins pairs of SG_Nodes to minimize the size of the resultant - * bounding box. - * cf building an optimized Huffman tree. - * \warning O(n^3)!!! - */ -class SG_TreeFactory -{ - typedef std::multiset<SG_Tree*, SG_Tree::greater> TreeSet; - TreeSet m_objects; -public: - SG_TreeFactory(); - ~SG_TreeFactory(); - - /** - * 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(); - - -#ifdef WITH_CXX_GUARDEDALLOC - MEM_CXX_CLASS_ALLOC_FUNCS("GE:SG_TreeFactory") -#endif -}; - -#endif /* __SG_BBOX_H__ */ |