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
|
//-----------------------------------------------------------------------------
// BSPLIB MODULE: BSPTree.cpp
//
// Copyright (c) 1997-1998 by Markus Hadwiger
// All Rights Reserved.
//-----------------------------------------------------------------------------
// bsplib header files
#include "BSPTree.h"
BSPLIB_NAMESPACE_BEGIN
#define BLOCK_SIZE 4096
// append new node to flat bsp tree -------------------------------------------
//
BSPNodeFlat *BSPTreeFlatRep::AppendNode( int front, int back, Polygon *poly, int clist, int blist )
{
// expand storage area (array) if no space available
if ( nodestorage - numnodes == 0 ) {
BSPNodeFlat *newroot = new BSPNodeFlat[ nodestorage + BLOCK_SIZE ];
if ( root != NULL ) {
memcpy( newroot, root, nodestorage * sizeof( BSPNodeFlat ) );
delete[] root;
}
root = newroot;
nodestorage += BLOCK_SIZE;
}
// init new node and return its address
root[ numnodes ].InitNode( front, back, poly, clist, blist );
return root + numnodes++;
}
// fetch node per id (node number) --------------------------------------------
//
BSPNodeFlat *BSPTreeFlatRep::FetchNodePerId( int id )
{
// id has to be greater than 0 since 0 means empty halfspace
return ( ( id > 0 ) && ( id <= numnodes ) ) ? ( root + id - 1 ) : NULL;
}
// apply scale factor to separator planes and bounding boxes of all nodes -----
//
void BSPTreeFlatRep::ApplyScaleFactor( double sfac )
{
BSPNodeFlat *scan = root;
for ( int i = 0; i < numnodes; i++, scan++ )
scan->ApplyScaleFactor( sfac );
}
// build pointer-based bsp tree from flat representation ----------------------
//
BSPNode *BSPTreeFlatRep::BuildBSPTree( int nodenum )
{
if ( nodenum == 0 )
return NULL;
BSPNodeFlat *node = FetchNodePerId( nodenum );
if ( node == NULL )
return NULL;
// get node's polygon
Polygon *poly = node->getPolygon();
// append contained list to polygon (frontfacing polygons)
static int containedindx;
static Polygon *precpoly;
containedindx = node->getContainedList();
precpoly = poly;
while ( containedindx > 0 ) {
static BSPNodeFlat *cnode;
static Polygon *cpoly;
cnode = FetchNodePerId( containedindx );
cpoly = cnode ? cnode->getPolygon() : NULL;
containedindx = cnode ? cnode->getContainedList() : 0;
precpoly->setNext( cpoly );
precpoly = cpoly;
}
if ( precpoly ) {
// detach original polygon list
precpoly->setNext( NULL );
}
// build list of backfacing polygons (backlist)
Polygon *backlist = NULL;
containedindx = node->getBackList();
precpoly = NULL;
while ( containedindx > 0 ) {
static BSPNodeFlat *cnode;
static Polygon *cpoly;
cnode = FetchNodePerId( containedindx );
cpoly = cnode ? cnode->getPolygon() : NULL;
containedindx = cnode ? cnode->getBackList() : 0;
if ( precpoly == NULL)
backlist = cpoly;
else
precpoly->setNext( cpoly );
precpoly = cpoly;
}
if ( precpoly ) {
// detach original polygon list
precpoly->setNext( NULL );
}
// recursively build front- and back-subtree
BSPNode *front = BuildBSPTree( node->getFrontSubTree() );
BSPNode *back = BuildBSPTree( node->getBackSubTree() );
return new BSPNode( front, back, poly, backlist, node->getSeparatorPlane(), node->getBoundingBox() );
}
BSPLIB_NAMESPACE_END
//-----------------------------------------------------------------------------
|
