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
|
/*
* PARSEC - BSP Tree Operations
*
* $Author: uberlinuxguy $ - $Date: 2004/09/15 12:25:43 $
*
* Orginally written by:
* Copyright (c) Markus Hadwiger <msh@parsec.org> 1999
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program 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 General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
// C library
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
// compilation flags/debug support
#include "config.h"
#include "debug.h"
// general definitions
#include "general.h"
#include "objstruc.h"
// global externals
#include "globals.h"
// mathematics header
#include "utl_math.h"
// model header
#include "utl_model.h"
// local module header
#include "utl_bsp.h"
// static tree traversal variables --------------------------------------------
//
static Vertex3* bsp_line_v0;
static Vertex3* bsp_line_v1;
static CullBSPNode* bsp_tree;
static dword bsp_collider;
static geomv_t bsp_coll_t;
// traversal function to find line segment <-> bsp node collision -------------
//
PRIVATE
int BSP_FindCollider( dword nodeid, geomv_t t0, geomv_t t1 )
{
ASSERT( nodeid != 0 );
//NOTE:
// nodeid==0: tree NULL
// nodeid==1: tree root
//NOTE:
// baseseg: [ (t=0) v0 --------------------- v1 (t=1) ]
// subseg: [ (d0) t0 --------- t1 (d1) ]
// seg0: [ t0 --- t ]
// seg1: [ t --- t1 ]
static CullBSPNode *node;
node = &bsp_tree[ nodeid ];
// signed distances of baseseg vertices to current plane
static geomv_t d0;
static geomv_t d1;
d0 = PLANE_DOT( &node->plane, bsp_line_v0 ) - PLANE_OFFSET( &node->plane );
d1 = PLANE_DOT( &node->plane, bsp_line_v1 ) - PLANE_OFFSET( &node->plane );
static dword seg0treeid;
dword seg1treeid;
int seg0solid;
// determine halfspace (subtree) of v0
if ( GEOMV_GEZERO( d0 ) ) {
seg0solid = FALSE; // leaf would be empty
seg0treeid = node->subtrees[ 1 ]; // fronttree
seg1treeid = node->subtrees[ 0 ]; // backtree
} else {
seg0solid = TRUE; // leaf would be solid
seg0treeid = node->subtrees[ 0 ]; // backtree
seg1treeid = node->subtrees[ 1 ]; // fronttree
}
// special case if baseseg not straddling
if ( ( DW32( d0 ) ^ DW32( d1 ) ) < 0x80000000 ) {
pushseg:
// classify if seg in leaf
if ( seg0treeid == 0 )
return seg0solid;
// push down without clipping (tail rec)
return BSP_FindCollider( seg0treeid, t0, t1 );
}
// drop distance signs
ABS_GEOMV( d0 );
ABS_GEOMV( d1 );
// calc projected length
static geomv_t seglen;
seglen = d0 + d1;
ASSERT( seglen >= 0 );
// simply push down if baseseg is on
if ( seglen <= FLOAT_TO_GEOMV( 0.00001 ) ) {
goto pushseg;
}
// calc intersection parameter using baseseg
geomv_t t = GEOMV_DIV( d0, seglen );
// subseg not straddling: case 1
if ( t <= t0 ) {
// invert classification (subseg in v1's halfspace)
seg0solid = !seg0solid;
seg0treeid = seg1treeid;
goto pushseg;
}
// subseg not straddling: case 2
if ( t >= t1 ) {
goto pushseg;
}
// check seg0 first
if ( seg0treeid != 0 ) {
// push seg0 into its tree if not leaf
if ( BSP_FindCollider( seg0treeid, t0, t ) )
return TRUE;
} else if ( seg0solid ) {
// collision if seg0 in solid leaf
return TRUE;
}
// this node becomes potential collider (ray passes through its plane)
bsp_collider = nodeid;
bsp_coll_t = t;
// check if seg1's tree is a leaf
if ( seg1treeid == 0 ) {
// classification of seg1 is inverse of seg0's
return !seg0solid;
}
// push seg1 into its tree
return BSP_FindCollider( seg1treeid, t, t1 );
}
// find collider (tree node) for specified line segment -----------------------
//
int BSP_FindColliderLine( CullBSPNode *tree, Vertex3 *v0, Vertex3 *v1, dword *colnode, geomv_t *colt )
{
ASSERT( tree != NULL );
ASSERT( v0 != NULL );
ASSERT( v1 != NULL );
// set root pointer and lineseg
bsp_tree = tree;
bsp_line_v0 = v0;
bsp_line_v1 = v1;
bsp_coll_t = GEOMV_0;
// no potential collider until first boundary pierced
bsp_collider = 0;
// clip lineseg into bsp tree
int collided = BSP_FindCollider( 1, GEOMV_0, GEOMV_1 );
// set collider (node id) and t (parameter of collision)
if ( colnode != NULL )
*colnode = bsp_collider;
if ( colt != NULL )
*colt = bsp_coll_t;
return collided;
}
|
