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