Added the Solid 3.5 sources to the blender source tree.
[blender.git] / extern / solid / src / complex / DT_BBoxTree.cpp
1 /*
2  * SOLID - Software Library for Interference Detection
3  * 
4  * Copyright (C) 2001-2003  Dtecta.  All rights reserved.
5  *
6  * This library may be distributed under the terms of the Q Public License
7  * (QPL) as defined by Trolltech AS of Norway and appearing in the file
8  * LICENSE.QPL included in the packaging of this file.
9  *
10  * This library may be distributed and/or modified under the terms of the
11  * GNU General Public License (GPL) version 2 as published by the Free Software
12  * Foundation and appearing in the file LICENSE.GPL included in the
13  * packaging of this file.
14  *
15  * This library is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
17  *
18  * Commercial use or any other use of this library not covered by either 
19  * the QPL or the GPL requires an additional license from Dtecta. 
20  * Please contact info@dtecta.com for enquiries about the terms of commercial
21  * use of this library.
22  */
23
24 #include "DT_BBoxTree.h"
25
26 inline DT_CBox getBBox(int first, int last, const DT_CBox *boxes, const DT_Index *indices) 
27 {
28         assert(last - first >= 1);
29
30         DT_CBox bbox = boxes[indices[first]];
31         int i;
32         for (i = first; i < last; ++i) 
33         {
34                 bbox = bbox.hull(boxes[indices[i]]);
35         }
36
37         return bbox;
38 }
39
40 DT_BBoxNode::DT_BBoxNode(int first, int last, int& node, DT_BBoxNode *free_nodes, const DT_CBox *boxes, DT_Index *indices, const DT_CBox& bbox)
41 {
42         assert(last - first >= 2);
43         
44         int axis = bbox.longestAxis();
45         MT_Scalar abscissa = bbox.getCenter()[axis];
46         int i = first, mid = last;
47         while (i < mid) 
48         {
49                 if (boxes[indices[i]].getCenter()[axis] < abscissa)
50                 {
51                         ++i;
52                 }
53                 else
54                 {
55                         --mid;
56                         std::swap(indices[i], indices[mid]);
57                 }
58         }
59
60         if (mid == first || mid == last) 
61         {
62                 mid = (first + last) / 2;
63         }
64         
65         m_lbox = getBBox(first, mid, boxes, indices);
66         m_rbox = getBBox(mid, last, boxes, indices);
67         m_flags = 0x0;
68
69         if (mid - first == 1)
70         {
71                 m_flags |= LLEAF;
72                 m_lchild = indices[first];
73         }
74         else 
75         {       
76                 m_lchild = node++;
77                 new(&free_nodes[m_lchild]) DT_BBoxNode(first, mid, node, free_nodes, boxes, indices, m_lbox);
78         }
79
80         if (last - mid == 1)
81         {
82                 m_flags |= RLEAF;
83                 m_rchild = indices[mid];
84         }
85         else 
86         {
87                 m_rchild = node++;
88                 new(&free_nodes[m_rchild]) DT_BBoxNode(mid, last, node, free_nodes, boxes, indices, m_rbox); 
89         }
90 }