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