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