blob: 53e08a191978584c22521ac3cf20115dba1f8687 (
plain)
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
|
//-----------------------------------------------------------------------------
// BSPLIB MODULE: ObjectBSPNode.cpp
//
// Copyright (c) 1997-1998 by Markus Hadwiger
// All Rights Reserved.
//-----------------------------------------------------------------------------
// bsplib header files
#include "ObjectBSPNode.h"
BSPLIB_NAMESPACE_BEGIN
// create linear object list from objects attached to nodes -------------------
//
BspObject *ObjectBSPNode::CreateObjectList()
{
// process tree from its leaves upwards
BspObject *front = frontsubtree ? frontsubtree->CreateObjectList() : NULL;
BspObject *back = backsubtree ? backsubtree->CreateObjectList() : NULL;
BspObject *scan = NULL;
if ( front != NULL ) {
// append back-list to front-list if front-list exists
for ( scan = front; scan->next; scan = scan->next ) ;
scan->next = back;
}
if ( boundingbox != NULL ) {
static BspObject *headobject;
if ( ( headobject = boundingbox->containedobject ) != NULL ) {
// scan list and merge all subsequent objects into head object
static BspObject *scan;
for ( scan = headobject->next; scan; scan = scan->next ) {
headobject->MergeObjects( scan );
// invalidate other object's polygonlist
scan->getPolygonList().InvalidateList();
}
// delete all objects that have been merged into head
delete headobject->next;
// single object, no list
headobject->next = NULL;
// return head object now encompassing entire list
return headobject;
} else {
// return contatenated list for internal nodes with bounding box
return front ? front : back;
}
} else {
// simply return contatenated list for nodes without bounding box
return front ? front : back;
}
}
// merge all objects contained in tree into passed object ---------------------
//
void ObjectBSPNode::MergeTreeNodeObjects( BspObject *newobject )
{
if ( separatorplane == NULL ) {
// merge leaf into already existing cumulative object
newobject->MergeObjects( boundingbox->containedobject );
// unlink list from already merged object
boundingbox->containedobject->next = NULL;
//NOTE:
// the merged objects must not be freed at this point,
// since they are still needed for the subsequent merging
// of bsp trees! nevertheless, their next field must be
// set to null, to prevent crosslinking of leaves.
} else {
// process subtrees; order not relevant in any way
if ( frontsubtree ) frontsubtree->MergeTreeNodeObjects( newobject );
if ( backsubtree ) backsubtree->MergeTreeNodeObjects( newobject );
}
}
// create unified (separator plane/polygon bsp) from object bsp tree ----------
//
BSPNode *ObjectBSPNode::CreateUnifiedBSPTree()
{
//NOTE:
// the BSPTrees of the BspObjects are invalidated after they
// have been integrated into the unified BSPTree. this is done
// to prevent accidental deletion at the time when the underlying
// objects will be deleted. (which will normally be done in
// DeleteNodeBspObjects() later on.)
if ( separatorplane == NULL ) {
// node is leaf: return object's bsp tree
static BSPNode *root;
root = boundingbox->containedobject->getBSPTree().getRoot();
boundingbox->containedobject->getBSPTree().InvalidateTree();
return root;
} else {
// node is separator (internal node): create separator bsp node
BSPNode *front = frontsubtree ? frontsubtree->CreateUnifiedBSPTree() : NULL;
BSPNode *back = backsubtree ? backsubtree->CreateUnifiedBSPTree() : NULL;
return new BSPNode( front, back, NULL, NULL, separatorplane, NULL );
}
}
// merge all objects contained in object bsp tree into single object and tree -
//
BspObject *ObjectBSPNode::CreateMergedBSPTree()
{
//NOTE:
// this function may only be invoked on ObjectBSPNodes which
// actually contain objects with valid BSPTrees! so, it may only
// be invoked after successful bsp compilation.
// create new object to encompass all other objects
BspObject *newobject = new BspObject;
// merge objects of nodes into one big object
MergeTreeNodeObjects( newobject );
// create unified bsp tree for all contained objects and their respective separators
newobject->getBSPTree().InitTree( CreateUnifiedBSPTree() );
newobject->numbsppolygons = 0;
newobject->getBSPTree()->NumberBSPNodes( newobject->numbsppolygons ); //CAVEAT: sind nicht alles Polygone!!! //TODO
newobject->UpdateAttributeNumbers();
return newobject;
}
// delete all BSPObjects attached to bounding boxes contained in tree ---------
//
void ObjectBSPNode::DeleteNodeBspObjects()
{
if ( separatorplane == NULL ) {
// delete leaf
delete boundingbox->containedobject;
boundingbox->containedobject = NULL;
} else {
// detach separator plane from node to prevent accidental
// deletion later on. (planes are still used by unified
// bsp tree.)
separatorplane = NULL;
// process subtrees; order not relevant in any way
if ( frontsubtree ) frontsubtree->DeleteNodeBspObjects();
if ( backsubtree ) backsubtree->DeleteNodeBspObjects();
}
}
// traverse bsp tree (preorder) and number nodes as encountered ---------------
//
void ObjectBSPNode::NumberBSPNodes( int& curno )
{
// never used
}
// write bsp tree structure to output file (preorder traversal) ---------------
//
void ObjectBSPNode::WriteBSPTree( FILE *fp ) const
{
// never used
}
BSPLIB_NAMESPACE_END
//-----------------------------------------------------------------------------
|
