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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
//-----------------------------------------------------------------------------
// BSPLIB MODULE: BoundingBox.cpp
//
// Copyright (c) 1997-1998 by Markus Hadwiger
// All Rights Reserved.
//-----------------------------------------------------------------------------
// bsplib headers
#include "BoundingBox.h"
#include "ObjectBSPNode.h"
#include "Plane.h"
BSPLIB_NAMESPACE_BEGIN
// apply scale factor to bounding box -----------------------------------------
//
void BoundingBox::ApplyScaleFactor( double sfac )
{
//NOTE:
// this will be needed if the attached object is scaled.
// the scale factor is applied to the space containing the
// bounding box, i.e. its midpoint will move.
minvertex.setX( minvertex.getX() * sfac );
minvertex.setY( minvertex.getY() * sfac );
minvertex.setZ( minvertex.getZ() * sfac );
maxvertex.setX( maxvertex.getX() * sfac );
maxvertex.setY( maxvertex.getY() * sfac );
maxvertex.setZ( maxvertex.getZ() * sfac );
}
// grow this bounding box by another one (maximum/minimum merge) --------------
//
void BoundingBox::GrowBoundingBox( BoundingBox *otherbox )
{
if ( otherbox != NULL ) {
if ( otherbox->minvertex.getX() < minvertex.getX() )
minvertex.setX( otherbox->minvertex.getX() );
if ( otherbox->minvertex.getY() < minvertex.getY() )
minvertex.setY( otherbox->minvertex.getY() );
if ( otherbox->minvertex.getZ() < minvertex.getZ() )
minvertex.setZ( otherbox->minvertex.getZ() );
if ( otherbox->maxvertex.getX() > maxvertex.getX() )
maxvertex.setX( otherbox->maxvertex.getX() );
if ( otherbox->maxvertex.getY() > maxvertex.getY() )
maxvertex.setY( otherbox->maxvertex.getY() );
if ( otherbox->maxvertex.getZ() > maxvertex.getZ() )
maxvertex.setZ( otherbox->maxvertex.getZ() );
}
}
// fill in bounding box as union of entire list -------------------------------
//
void BoundingBox::BoundingBoxListUnion( BoundingBox& unionbox )
{
// init union box
delete unionbox.nextbox;
unionbox.nextbox = NULL;
unionbox.containedobject = NULL;
unionbox.minvertex = minvertex;
unionbox.maxvertex = maxvertex;
// build union of entire list
for ( BoundingBox *curbox = nextbox; curbox; curbox = curbox->nextbox )
unionbox.GrowBoundingBox( curbox );
}
// partition list of bounding boxing boxes and build tree structure -----------
//
ObjectBSPNode *BoundingBox::PartitionSpace()
{
//NOTE:
// this function alters the link fields of the objects attached
// to bounding boxes. therefore, the original linked list of
// objects is invalid after this function! the objects themselves
// are only accessible via tree nodes afterwards.
//NOTE:
// analogously to polygon bsp trees where the polygon list is dissolved
// in the process of bsp compilation, the list of bounding boxes is
// completely dissolved by this function! that is, the bounding box
// for which PartitionSpace() has been invoked should not be accessed
// directly anymore. all bounding boxes can then be accessed via the
// generated object-bsp-tree!
// only one box in this subspace?
if ( nextbox == NULL ) {
// unlink tail of object list
containedobject->next = NULL;
// create ObjectBSPNode for this box (leaf!)
return new ObjectBSPNode( NULL, NULL, NULL, this );
}
// select a separating plane
Vector3 separatornormal( 1.0, 0.0, 0.0 );
double separatoroffset = maxvertex.getX();
int currentboundary = 0;
Plane *separator = new Plane( separatornormal, separatoroffset );
BoundingBox *currentbox = this;
// scan all bounding boxes to find a suitable separating plane
for ( currentbox = this; ; ) {
// check if plane separates bounding boxes cleanly
int cleanseparation = 1;
int membersofpos = 0;
int membersofneg = 0;
for ( BoundingBox *scan = this; scan; scan = scan->getNext() ) {
if ( !separator->PointInNegativeHalfspace( scan->getMinVertex() ) &&
!separator->PointInNegativeHalfspace( scan->getMaxVertex() ) ) {
membersofpos++;
} else if ( !separator->PointInPositiveHalfspace( scan->getMinVertex() ) &&
!separator->PointInPositiveHalfspace( scan->getMaxVertex() ) ) {
membersofneg++;
} else {
cleanseparation = 0;
break;
}
}
//NOTE:
// both halfspaces have to contain bounding boxes; separation of vacant
// space from inhabited space just makes the tree unnecessarily large.
// this does not influence if there is a clean separating plane or not!
if ( ( membersofpos > 0 ) && ( membersofneg > 0 ) && cleanseparation )
break;
// try next boundary plane
currentboundary = ( currentboundary + 1 ) % 6;
if ( currentboundary == 0 )
currentbox = currentbox->getNext();
if ( currentbox != NULL ) {
switch ( currentboundary ) {
case 0:
separatornormal = Vector3( 1.0, 0.0, 0.0 );
separatoroffset = currentbox->maxvertex.getX();
break;
case 1:
separatornormal = Vector3( 0.0, 1.0, 0.0 );
separatoroffset = currentbox->maxvertex.getY();
break;
case 2:
separatornormal = Vector3( 0.0, 0.0, 1.0 );
separatoroffset = currentbox->maxvertex.getZ();
break;
case 3:
separatornormal = Vector3( -1.0, 0.0, 0.0 );
separatoroffset = -currentbox->minvertex.getX();
break;
case 4:
separatornormal = Vector3( 0.0, -1.0, 0.0 );
separatoroffset = -currentbox->minvertex.getY();
break;
case 5:
separatornormal = Vector3( 0.0, 0.0, -1.0 );
separatoroffset = -currentbox->minvertex.getZ();
break;
}
separator->setPlaneNormal( separatornormal );
separator->setPlaneOffset( separatoroffset );
} else {
break;
}
}
BoundingBox *frontsubspace = NULL;
BoundingBox *backsubspace = NULL;
if ( currentbox != NULL ) {
// partition space into two halfspaces (walk list of bounding boxes)
for ( currentbox = this; currentbox; ) {
if ( !separator->PointInNegativeHalfspace( currentbox->getMinVertex() ) &&
!separator->PointInNegativeHalfspace( currentbox->getMaxVertex() ) ) {
// box contained in positive halfspace
BoundingBox *tmpbox = currentbox->getNext();
currentbox->nextbox = frontsubspace;
frontsubspace = currentbox;
currentbox = tmpbox;
} else {
// box contained in negative halfspace
BoundingBox *tmpbox = currentbox->getNext();
currentbox->nextbox = backsubspace;
backsubspace = currentbox;
currentbox = tmpbox;
}
}
} else {
// no suitable separating plane found: create list of unseparable objects
for ( currentbox = this; currentbox; currentbox = currentbox->getNext() ) {
currentbox->containedobject->next =
currentbox->getNext() ? currentbox->getNext()->containedobject : NULL;
}
// delete legacy bounding boxes
delete nextbox;
nextbox = NULL;
// create ObjectBSPNode for this box (leaf!)
return new ObjectBSPNode( NULL, NULL, NULL, this );
//NOTE:
// if bounding boxes cannot be separated cleanly, their corresponding objects
// are inserted into a linear list attached to a single bounding box. this
// bounding box, however, encompasses only the head of this list!
// for bsp compilation, the objects in these lists have to be explicitly merged
// into a single object. this is not done automatically!
// currently, only ObjectBSPNode::CreateObjectList() merges these objects.
}
// allocate new root; partition halfspaces recursively and return root
ObjectBSPNode *front = frontsubspace ? frontsubspace->PartitionSpace() : NULL;
ObjectBSPNode *back = backsubspace ? backsubspace->PartitionSpace() : NULL;
return new ObjectBSPNode( front, back, separator, NULL );
}
BSPLIB_NAMESPACE_END
//-----------------------------------------------------------------------------
|
