resolved conflict state with HEAD r14096
[blender.git] / source / gameengine / SceneGraph / SG_Tree.h
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL/BL DUAL 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. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  * Bounding Box
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
120 /**
121  *  SG_TreeFactory generates an SG_Tree from a list of SG_Nodes.
122  *  It joins pairs of SG_Nodes to minimise the size of the resultant
123  *  bounding box.
124  *  cf building an optimised Huffman tree.
125  *  @warning O(n^3)!!!
126  */
127 class SG_TreeFactory 
128 {
129         typedef std::multiset<SG_Tree*, SG_Tree::greater> TreeSet;
130         TreeSet m_objects;
131 public:
132         SG_TreeFactory();
133         ~SG_TreeFactory();
134         
135         /**
136          *  Add a node to be added to the tree.
137          */
138         void Add(SG_Node* client);
139         void Add(SG_Tree* tree);
140
141         /**
142          *  Build the tree from the set of nodes added by
143          *  the Add method.
144          */
145         SG_Tree* MakeTreeUp();
146         
147         /**
148          *  Build the tree from the set of nodes top down.
149          */
150         SG_Tree* MakeTreeDown(SG_BBox &bbox);
151         
152         SG_Tree* MakeTree();
153         
154 };
155
156 #endif /* __SG_BBOX_H__ */