source/gameengine/SceneGraph/SG_Tree.h

   1 /*
   2  * $Id$
   3  *
   4  * ***** BEGIN GPL LICENSE BLOCK *****
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License
   8  * as published by the Free Software Foundation; either version 2
   9  * of the License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  19  *
  20  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  21  * All rights reserved.
  22  *
  23  * The Original Code is: all of this file.
  24  *
  25  * Contributor(s): none yet.
  26  *
  27  * ***** END GPL LICENSE BLOCK *****
  28  */
  29
  30 /** \file SG_Tree.h
  31  *  \ingroup bgesg
  32  */
  33
  34 #ifndef __SG_TREE_H__
  35 #define __SG_TREE_H__
  36
  37 #include "MT_Point3.h"
  38 #include "SG_BBox.h"
  39
  40 #include <set>
  41
  42 class SG_Node;
  43
  44
  45 /**
  46  * SG_Tree.
  47  * Holds a binary tree of SG_Nodes.
  48  */
  49 class SG_Tree
  50 {
  51         SG_Tree* m_left;
  52         SG_Tree* m_right;
  53         SG_Tree* m_parent;
  54         SG_BBox  m_bbox;
  55         MT_Point3 m_center;
  56         MT_Scalar m_radius;
  57         SG_Node* m_client_object;
  58 public:
  59         SG_Tree();
  60         SG_Tree(SG_Tree* left, SG_Tree* right);
  61
  62         SG_Tree(SG_Node* client);
  63         ~SG_Tree();
  64
  65         /**
  66          * Computes the volume of the bounding box.
  67          */
  68         MT_Scalar volume() const;
  69
  70         /**
  71          * Prints the tree (for debugging.)
  72          */
  73         void dump() const;
  74
  75         /**
  76          * Returns the left node.
  77          */
  78         SG_Tree *Left() const;
  79         SG_Tree *Right() const;
  80         SG_Node *Client() const;
  81
  82         SG_Tree* Find(SG_Node *node);
  83         /**
  84          * Gets the eight corners of this treenode's bounding box,
  85          * in world coordinates.
  86          * @param box: an array of 8 MT_Point3
  87          * @example MT_Point3 box[8];
  88          *          treenode->get(box);
  89          */
  90         void get(MT_Point3 *box) const;
  91         /**
  92          * Get the tree node's bounding box.
  93          */
  94         const SG_BBox& BBox() const;
  95
  96         /**
  97          * Test if the given bounding box is inside this bounding box.
  98          */
  99         bool inside(const MT_Point3 &point) const;
 100
 101         void SetLeft(SG_Tree *left);
 102         void SetRight(SG_Tree *right);
 103
 104         MT_Point3 Center() const { return m_center; }
 105         MT_Scalar Radius() { return m_radius; }
 106
 107         //friend class SG_TreeFactory;
 108
 109         struct greater
 110         {
 111                 bool operator()(const SG_Tree *a, const SG_Tree *b)
 112                 {
 113                         return a->volume() > b->volume();
 114                 }
 115         };
 116
 117
 118
 119 #ifdef WITH_CXX_GUARDEDALLOC
 120 public:
 121         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_Tree"); }
 122         void operator delete( void *mem ) { MEM_freeN(mem); }
 123 #endif
 124 };
 125
 126
 127 /**
 128  *  SG_TreeFactory generates an SG_Tree from a list of SG_Nodes.
 129  *  It joins pairs of SG_Nodes to minimise the size of the resultant
 130  *  bounding box.
 131  *  cf building an optimised Huffman tree.
 132  *  @warning O(n^3)!!!
 133  */
 134 class SG_TreeFactory
 135 {
 136         typedef std::multiset<SG_Tree*, SG_Tree::greater> TreeSet;
 137         TreeSet m_objects;
 138 public:
 139         SG_TreeFactory();
 140         ~SG_TreeFactory();
 141
 142         /**
 143          *  Add a node to be added to the tree.
 144          */
 145         void Add(SG_Node* client);
 146         void Add(SG_Tree* tree);
 147
 148         /**
 149          *  Build the tree from the set of nodes added by
 150          *  the Add method.
 151          */
 152         SG_Tree* MakeTreeUp();
 153
 154         /**
 155          *  Build the tree from the set of nodes top down.
 156          */
 157         SG_Tree* MakeTreeDown(SG_BBox &bbox);
 158
 159         SG_Tree* MakeTree();
 160
 161
 162 #ifdef WITH_CXX_GUARDEDALLOC
 163 public:
 164         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_TreeFactory"); }
 165         void operator delete( void *mem ) { MEM_freeN(mem); }
 166 #endif
 167 };
 168
 169 #endif /* __SG_BBOX_H__ */