fa6facde66ce8067c857b756a1e7d019fc8c7eed
[blender-staging.git] / 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  * Bounding Box
29  */
30  
31 #ifndef __SG_TREE_H__
32 #define __SG_TREE_H__
33  
34 #include "MT_Point3.h"
35 #include "SG_BBox.h"
36
37 #include <set> 
38
39 class SG_Node;
40
41
42 /**
43  * SG_Tree.
44  * Holds a binary tree of SG_Nodes.
45  */
46 class SG_Tree 
47 {
48         SG_Tree* m_left;
49         SG_Tree* m_right;
50         SG_Tree* m_parent;
51         SG_BBox  m_bbox;
52         MT_Point3 m_center;
53         MT_Scalar m_radius;
54         SG_Node* m_client_object;
55 public:
56         SG_Tree();
57         SG_Tree(SG_Tree* left, SG_Tree* right);
58         
59         SG_Tree(SG_Node* client);
60         ~SG_Tree();
61         
62         /**
63          * Computes the volume of the bounding box.
64          */
65         MT_Scalar volume() const;
66         
67         /**
68          * Prints the tree (for debugging.)
69          */
70         void dump() const;
71         
72         /**
73          * Returns the left node.
74          */
75         SG_Tree *Left() const;
76         SG_Tree *Right() const;
77         SG_Node *Client() const;
78         
79         SG_Tree* Find(SG_Node *node);
80         /**
81          * Gets the eight corners of this treenode's bounding box,
82          * in world coordinates.
83          * @param box: an array of 8 MT_Point3
84          * @example MT_Point3 box[8];
85          *          treenode->get(box);
86          */
87         void get(MT_Point3 *box) const;
88         /**
89          * Get the tree node's bounding box.
90          */
91         const SG_BBox& BBox() const;
92         
93         /**
94          * Test if the given bounding box is inside this bounding box.
95          */
96         bool inside(const MT_Point3 &point) const;
97         
98         void SetLeft(SG_Tree *left);
99         void SetRight(SG_Tree *right);
100
101         MT_Point3 Center() const { return m_center; }
102         MT_Scalar Radius() { return m_radius; }
103         
104         //friend class SG_TreeFactory;
105         
106         struct greater
107         {
108                 bool operator()(const SG_Tree *a, const SG_Tree *b)
109                 {
110                         return a->volume() > b->volume();
111                 }
112         };
113         
114         
115         
116 #ifdef WITH_CXX_GUARDEDALLOC
117 public:
118         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_Tree"); }
119         void operator delete( void *mem ) { MEM_freeN(mem); }
120 #endif
121 };
122
123
124 /**
125  *  SG_TreeFactory generates an SG_Tree from a list of SG_Nodes.
126  *  It joins pairs of SG_Nodes to minimise the size of the resultant
127  *  bounding box.
128  *  cf building an optimised Huffman tree.
129  *  @warning O(n^3)!!!
130  */
131 class SG_TreeFactory 
132 {
133         typedef std::multiset<SG_Tree*, SG_Tree::greater> TreeSet;
134         TreeSet m_objects;
135 public:
136         SG_TreeFactory();
137         ~SG_TreeFactory();
138         
139         /**
140          *  Add a node to be added to the tree.
141          */
142         void Add(SG_Node* client);
143         void Add(SG_Tree* tree);
144
145         /**
146          *  Build the tree from the set of nodes added by
147          *  the Add method.
148          */
149         SG_Tree* MakeTreeUp();
150         
151         /**
152          *  Build the tree from the set of nodes top down.
153          */
154         SG_Tree* MakeTreeDown(SG_BBox &bbox);
155         
156         SG_Tree* MakeTree();
157         
158         
159 #ifdef WITH_CXX_GUARDEDALLOC
160 public:
161         void *operator new(size_t num_bytes) { return MEM_mallocN(num_bytes, "GE:SG_TreeFactory"); }
162         void operator delete( void *mem ) { MEM_freeN(mem); }
163 #endif
164 };
165
166 #endif /* __SG_BBOX_H__ */