svn merge ^/trunk/blender -r41226:41227 .
[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 public:
119         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_Tree"); }
120         void operator delete( void *mem ) { MEM_freeN(mem); }
121 #endif
122 };
123
124
125 /**
126  *  SG_TreeFactory generates an SG_Tree from a list of SG_Nodes.
127  *  It joins pairs of SG_Nodes to minimise the size of the resultant
128  *  bounding box.
129  *  cf building an optimised Huffman tree.
130  *  @warning O(n^3)!!!
131  */
132 class SG_TreeFactory 
133 {
134         typedef std::multiset<SG_Tree*, SG_Tree::greater> TreeSet;
135         TreeSet m_objects;
136 public:
137         SG_TreeFactory();
138         ~SG_TreeFactory();
139         
140         /**
141          *  Add a node to be added to the tree.
142          */
143         void Add(SG_Node* client);
144         void Add(SG_Tree* tree);
145
146         /**
147          *  Build the tree from the set of nodes added by
148          *  the Add method.
149          */
150         SG_Tree* MakeTreeUp();
151         
152         /**
153          *  Build the tree from the set of nodes top down.
154          */
155         SG_Tree* MakeTreeDown(SG_BBox &bbox);
156         
157         SG_Tree* MakeTree();
158         
159         
160 #ifdef WITH_CXX_GUARDEDALLOC
161 public:
162         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_TreeFactory"); }
163         void operator delete( void *mem ) { MEM_freeN(mem); }
164 #endif
165 };
166
167 #endif /* __SG_BBOX_H__ */