doxygen: gameengine/SceneGraph tagged.
[blender.git] / source / gameengine / SceneGraph / SG_Tree.cpp
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 /** \file gameengine/SceneGraph/SG_Tree.cpp
32  *  \ingroup bgesg
33  */
34
35
36 #include <math.h>
37  
38 #include "SG_BBox.h"
39 #include "SG_Tree.h"
40 #include "SG_Node.h"
41
42 SG_Tree::SG_Tree()
43 {
44 }
45
46 SG_Tree::SG_Tree(SG_Tree* left, SG_Tree* right) :
47                 m_left(left),
48                 m_right(right),
49                 m_client_object(NULL)
50 {
51         if (m_left)
52         {
53                 m_bbox = m_left->m_bbox;
54                 m_left->m_parent = this;
55         }
56         if (m_right)
57         {
58                 m_bbox += m_right->m_bbox;
59                 m_right->m_parent = this;
60         }
61         m_center = (m_bbox.m_min + m_bbox.m_max)/2.0;
62         m_radius = (m_bbox.m_max - m_bbox.m_min).length();
63 }
64         
65 SG_Tree::SG_Tree(SG_Node* client) :
66                 m_left(NULL),
67                 m_right(NULL),
68                 m_client_object(client)
69 {
70         m_bbox = SG_BBox(client->BBox(), client->GetWorldTransform());
71         m_center = (m_bbox.m_min + m_bbox.m_max)/2.0;
72         m_radius = (m_bbox.m_max - m_bbox.m_min).length();
73 }
74
75 SG_Tree::~SG_Tree() 
76 {
77 }
78         
79 MT_Scalar SG_Tree::volume() const
80 {
81         return m_bbox.volume();
82 }
83         
84 void SG_Tree::dump() const
85 {
86         if (m_left)
87                 m_left->dump();
88         if (m_client_object)
89                 std::cout << m_client_object << std::endl;
90         else
91                 std::cout << this << " ";
92         if (m_right)
93                 m_right->dump();
94 }
95
96 SG_Tree* SG_Tree::Left() const
97 {
98         return m_left;
99 }
100
101 SG_Tree* SG_Tree::Right() const
102 {
103         return m_right;
104 }
105
106 SG_Node* SG_Tree::Client() const
107 {
108         return m_client_object;
109 }
110
111 SG_Tree* SG_Tree::Find(SG_Node *node)
112 {
113         if (m_client_object == node)
114                 return this;
115         
116         SG_Tree *left = m_left, *right = m_right;
117         
118         if (left && right)
119         {
120                 if (right->m_bbox.intersects(node->BBox()))
121                         std::swap(left, right);
122         }
123                 
124         if (left)
125         {
126                 SG_Tree* ret = left->Find(node);
127                 if (ret) return ret;
128         }
129         
130         if (right)
131         {
132                 SG_Tree* ret = right->Find(node);
133                 if (ret) return ret;
134         }
135         
136         return NULL;
137 }
138
139 void SG_Tree::get(MT_Point3 *box) const
140 {
141         MT_Transform identity;
142         identity.setIdentity();
143         m_bbox.get(box, identity);
144 }
145
146 bool SG_Tree::inside(const MT_Point3 &point) const
147 {
148         return m_bbox.inside(point);
149 }
150
151 const SG_BBox& SG_Tree::BBox() const
152 {
153         return m_bbox;
154 }
155
156 void SG_Tree::SetLeft(SG_Tree *left)
157 {
158         m_left = left;
159         m_bbox += left->m_bbox;
160         m_center = (m_bbox.m_min + m_bbox.m_max)/2.0;
161         m_radius = (m_bbox.m_max - m_bbox.m_min).length();
162 }
163
164 void SG_Tree::SetRight(SG_Tree *right)
165 {
166         m_right = right;
167         m_bbox += right->m_bbox;
168         m_center = (m_bbox.m_min + m_bbox.m_max)/2.0;
169         m_radius = (m_bbox.m_max - m_bbox.m_min).length();
170 }
171
172 /**
173  * A Half array is a square 2d array where cell(x, y) is undefined
174  * if x < y.
175  */
176 template<typename T>
177 class HalfArray
178 {
179         std::vector<std::vector<T> > m_array;
180 public:
181         HalfArray() {}
182         ~HalfArray() {}
183         
184         void resize(unsigned int size)
185         {
186                 m_array.resize(size);
187                 for( unsigned int i = 0; i < size; i++)
188                 {
189                         m_array[i].resize(size - i);
190                 }
191         }
192         
193         T& operator() (unsigned int x, unsigned int y)
194         {
195                 assert(x >= y);
196                 return m_array[y][x - y];
197         }
198         
199         void erase_column (unsigned int x)
200         {
201                 for (unsigned int y = 0; y <= x; y++)
202                         m_array[y].erase(m_array[y].begin() + x - y);
203         }
204
205         void delete_column (unsigned int x)
206         {
207                 for (unsigned int y = 0; y < x; y++)
208                 {
209                         delete m_array[y][x - y];
210                         m_array[y].erase(m_array[y].begin() + x - y);
211                 }
212         }
213         
214         void erase_row (unsigned int y)
215         {
216                 m_array.erase(m_array.begin() + y);
217         }
218 };
219
220 SG_TreeFactory::SG_TreeFactory()
221 {
222 }
223
224 SG_TreeFactory::~SG_TreeFactory()
225 {
226 }
227         
228 void SG_TreeFactory::Add(SG_Node* client)
229 {
230         if (client)
231                 m_objects.insert(new SG_Tree(client));
232 }
233
234 void SG_TreeFactory::Add(SG_Tree* tree)
235 {
236         m_objects.insert(tree);
237 }
238
239 SG_Tree* SG_TreeFactory::MakeTreeDown(SG_BBox &bbox)
240 {
241         if (m_objects.size() == 0)
242                 return NULL;
243         if (m_objects.size() == 1)
244                 return *m_objects.begin();
245                 
246         TreeSet::iterator it = m_objects.begin();
247         SG_Tree *root = *it;
248         if (m_objects.size() == 2)
249         {
250                 root->SetRight(*(++it));
251                 return root;
252         }
253                 
254         if (m_objects.size() == 3)
255         {
256                 root->SetLeft(*(++it));
257                 root->SetRight(*(++it));
258                 return root;
259         }
260
261         if (bbox.volume() < 1.0)
262                 return MakeTreeUp();
263                 
264         SG_TreeFactory lefttree;
265         SG_TreeFactory righttree;
266         
267         SG_BBox left, right;
268         int hasleft = 0, hasright = 0;
269         bbox.split(left, right);
270         
271         if (left.test(root->BBox()) == SG_BBox::INSIDE)
272         {
273                 lefttree.Add(root);
274                 root = NULL;
275         }
276         
277         if (root && right.test(root->BBox()) == SG_BBox::INSIDE)
278         {
279                 righttree.Add(root);
280                 root = NULL;
281         }
282         
283         for (++it; it != m_objects.end(); ++it)
284         {
285                 switch (left.test((*it)->BBox()))
286                 {
287                         case SG_BBox::INSIDE:
288                                 // Object is inside left tree;
289                                 lefttree.Add(*it);
290                                 hasleft++;
291                                 break;
292                         case SG_BBox::OUTSIDE:
293                                 righttree.Add(*it);
294                                 hasright++;
295                                 break;
296                         case SG_BBox::INTERSECT:
297                                 if (left.inside((*it)->Client()->GetWorldPosition()))
298                                 {
299                                         lefttree.Add(*it);
300                                         hasleft++;
301                                 } else {
302                                         righttree.Add(*it);
303                                         hasright++;
304                                 }
305                                 break;
306                 }
307         }
308         std::cout << "Left: " << hasleft << " Right: " << hasright << " Count: " << m_objects.size() << std::endl;
309         
310         SG_Tree *leftnode = NULL;
311         if (hasleft)
312                 leftnode = lefttree.MakeTreeDown(left);
313         
314         SG_Tree *rightnode = NULL;
315         if (hasright)
316                 rightnode = righttree.MakeTreeDown(right);
317                 
318         if (!root)
319                 root = new SG_Tree(leftnode, rightnode);
320         else
321         {
322                 if (leftnode)
323                         root->SetLeft(leftnode);
324                 if (rightnode)
325                         root->SetRight(rightnode);
326         }
327
328         return root;
329 }
330
331 SG_Tree* SG_TreeFactory::MakeTree()
332 {
333         if (m_objects.size() < 8)
334                 return MakeTreeUp();
335
336         TreeSet::iterator it = m_objects.begin();
337         SG_BBox bbox((*it)->BBox());
338         for (++it; it != m_objects.end(); ++it)
339                 bbox += (*it)->BBox();
340         
341         return MakeTreeDown(bbox);
342 }
343
344 SG_Tree* SG_TreeFactory::MakeTreeUp()
345 {
346         unsigned int num_objects = m_objects.size();
347         
348         if (num_objects < 1)
349                 return NULL;
350         if (num_objects < 2)
351                 return *m_objects.begin();
352
353         HalfArray<SG_Tree*> sizes;
354         sizes.resize(num_objects);
355         
356         unsigned int x, y;
357         TreeSet::iterator xit, yit;
358         for( y = 0, yit = m_objects.begin(); y < num_objects; y++, ++yit)
359         {
360                 sizes(y, y) = *yit;
361                 xit = yit;
362                 for( x = y+1, ++xit; x < num_objects; x++, ++xit)
363                 {
364                         sizes(x, y) = new SG_Tree(*xit, *yit);
365                         
366                 }
367         }
368         while (num_objects > 2)
369         {
370                 /* Find the pair of bboxes that produce the smallest combined bbox. */
371                 unsigned int minx = UINT_MAX, miny = UINT_MAX;
372                 MT_Scalar min_volume = FLT_MAX;
373                 SG_Tree *min = NULL;
374                 //char temp[16];
375                 for( y = 0; y < num_objects; y++)
376                 {
377                         for( x = y+1; x < num_objects; x++)
378                         {
379                                 if (sizes(x, y)->volume() < min_volume)
380                                 {
381                                         min = sizes(x, y);
382                                         minx = x;
383                                         miny = y;
384                                         min_volume = sizes(x, y)->volume();
385                                 }
386                         }
387                 }
388                 
389                 /* Remove other bboxes that contain the two bboxes */
390                 sizes.delete_column(miny);
391                 
392                 for( x = miny + 1; x < num_objects; x++)
393                 {
394                         if (x == minx)
395                                 continue;
396                         delete sizes(x, miny);
397                 }
398                 sizes.erase_row(miny);
399                 
400                 num_objects--;
401                 minx--;
402                 sizes(minx, minx) = min;
403                 for( x = minx + 1; x < num_objects; x++)
404                 {
405                         delete sizes(x, minx);
406                         sizes(x, minx) = new SG_Tree(min, sizes(x, x));
407                 }
408                 for( y = 0; y < minx; y++)
409                 {
410                         delete sizes(minx, y);
411                         sizes(minx, y) = new SG_Tree(sizes(y, y), min);
412                 }
413         }
414         return sizes(1, 0);
415 }
416