1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
/*
SOLID - Software Library for Interference Detection
Copyright (C) 1997-1998 Gino van den Bergen
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free
Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
Please send remarks, questions and bug reports to gino@win.tue.nl,
or write to:
Gino van den Bergen
Department of Mathematics and Computing Science
Eindhoven University of Technology
P.O. Box 513, 5600 MB Eindhoven, The Netherlands
*/
#include "CSG_BBoxTree.h"
#include <algorithm>
using namespace std;
BBoxInternal::
BBoxInternal(
int n, LeafPtr leafIt
)
{
m_tag = INTERNAL;
m_bbox.SetEmpty();
int i;
for (i=0;i<n;i++) {
m_bbox.Include(leafIt[i].m_bbox);
}
}
// Construct a BBoxInternal from a list of BBoxLeaf nodes.
// Recursive function that does the longest axis median point
// fit.
void BBoxTree::
BuildTree(
LeafPtr leaves, int numLeaves
) {
m_branch = 0;
m_leaves = leaves;
m_numLeaves = numLeaves;
m_internals = new BBoxInternal[numLeaves];
RecursiveTreeBuild(m_numLeaves,m_leaves);
}
void
BBoxTree::
RecursiveTreeBuild(
int n, LeafPtr leafIt
){
m_internals[m_branch] = BBoxInternal(n,leafIt);
BBoxInternal& aBBox = m_internals[m_branch];
m_branch++;
int axis = aBBox.m_bbox.LongestAxis();
int i = 0, mid = n;
// split the leaves into two groups those that are < bbox.getCenter()[axis]
// and those that are >=
// smart bit about this code is it does the grouping in place.
while (i < mid)
{
if (leafIt[i].m_bbox.Center()[axis] < aBBox.m_bbox.Center()[axis])
{
++i;
} else {
--mid;
swap(leafIt[i], leafIt[mid]);
}
}
// all of the nodes were on one side of the box centre
// I'm not sure if this case ever gets reached?
if (mid == 0 || mid == n)
{
mid = n / 2;
}
if (mid >= 2)
{
aBBox.rson = m_internals + m_branch;
RecursiveTreeBuild(mid,leafIt);
} else {
aBBox.rson = leafIt;
}
if (n - mid >= 2) {
aBBox.lson = m_internals + m_branch;
RecursiveTreeBuild(n - mid, leafIt + mid);
} else {
aBBox.lson = leafIt + mid;
}
}
|
