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