2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
30 #define ON_EPSILON 0.1
32 typedef struct tnode_s
41 tnode_t *tnodes, *tnode_p;
47 Converts the disk node structure into the efficient tracing structure
50 void MakeTnode( int nodenum ){
58 node = dnodes + nodenum;
59 plane = dplanes + node->planenum;
61 t->type = plane->type;
62 VectorCopy( plane->normal, t->normal );
63 t->dist = plane->dist;
65 for ( i = 0 ; i < 2 ; i++ )
67 if ( node->children[i] < 0 ) {
68 t->children[i] = ( dleafs[-node->children[i] - 1].contents & CONTENTS_SOLID ) | ( 1 << 31 );
72 t->children[i] = tnode_p - tnodes;
73 MakeTnode( node->children[i] );
84 Loads the node structure out of a .bsp file to be used for light occlusion
87 void MakeTnodes( dmodel_t *bm ){
88 // 32 byte align the structs
89 tnodes = malloc( ( numnodes + 1 ) * sizeof( tnode_t ) );
90 tnodes = (tnode_t *)( ( (int)tnodes + 31 ) & ~31 );
97 //==========================================================
100 int TestLine_r( int node, vec3_t start, vec3_t stop ){
108 if ( node & ( 1 << 31 ) ) {
109 return node & ~( 1 << 31 ); // leaf node
112 tnode = &tnodes[node];
113 switch ( tnode->type )
116 front = start[0] - tnode->dist;
117 back = stop[0] - tnode->dist;
120 front = start[1] - tnode->dist;
121 back = stop[1] - tnode->dist;
124 front = start[2] - tnode->dist;
125 back = stop[2] - tnode->dist;
128 front = ( start[0] * tnode->normal[0] + start[1] * tnode->normal[1] + start[2] * tnode->normal[2] ) - tnode->dist;
129 back = ( stop[0] * tnode->normal[0] + stop[1] * tnode->normal[1] + stop[2] * tnode->normal[2] ) - tnode->dist;
133 if ( front >= -ON_EPSILON && back >= -ON_EPSILON ) {
134 return TestLine_r( tnode->children[0], start, stop );
137 if ( front < ON_EPSILON && back < ON_EPSILON ) {
138 return TestLine_r( tnode->children[1], start, stop );
143 frac = front / ( front - back );
145 mid[0] = start[0] + ( stop[0] - start[0] ) * frac;
146 mid[1] = start[1] + ( stop[1] - start[1] ) * frac;
147 mid[2] = start[2] + ( stop[2] - start[2] ) * frac;
149 r = TestLine_r( tnode->children[side], start, mid );
153 return TestLine_r( tnode->children[!side], mid, stop );
156 int TestLine( vec3_t start, vec3_t stop ){
157 return TestLine_r( 0, start, stop );
161 ==============================================================================
165 The major lighting operation is a point to point visibility test, performed
166 by recursive subdivision of the line by the BSP tree.
168 ==============================================================================
184 qboolean _TestLine( vec3_t start, vec3_t stop ){
187 tracestack_t *tstack_p;
189 float frontx,fronty, frontz, backx, backy, backz;
190 tracestack_t tracestack[64];
200 tstack_p = tracestack;
205 if ( node == CONTENTS_SOLID ) {
213 if ( d1 * d1 + d2 * d2 + d3 * d3 > 1 )
215 return false; // DONE!
220 // pop up the stack for a back side
222 if ( tstack_p < tracestack ) {
225 node = tstack_p->node;
227 // set the hit point for this plane
233 // go down the back side
235 backx = tstack_p->backpt[0];
236 backy = tstack_p->backpt[1];
237 backz = tstack_p->backpt[2];
239 node = tnodes[tstack_p->node].children[!tstack_p->side];
242 tnode = &tnodes[node];
244 switch ( tnode->type )
247 front = frontx - tnode->dist;
248 back = backx - tnode->dist;
251 front = fronty - tnode->dist;
252 back = backy - tnode->dist;
255 front = frontz - tnode->dist;
256 back = backz - tnode->dist;
259 front = ( frontx * tnode->normal[0] + fronty * tnode->normal[1] + frontz * tnode->normal[2] ) - tnode->dist;
260 back = ( backx * tnode->normal[0] + backy * tnode->normal[1] + backz * tnode->normal[2] ) - tnode->dist;
264 if ( front > -ON_EPSILON && back > -ON_EPSILON ) {
265 // if (front > 0 && back > 0)
266 node = tnode->children[0];
270 if ( front < ON_EPSILON && back < ON_EPSILON ) {
271 // if (front <= 0 && back <= 0)
272 node = tnode->children[1];
278 front = front / ( front - back );
280 tstack_p->node = node;
281 tstack_p->side = side;
282 tstack_p->backpt[0] = backx;
283 tstack_p->backpt[1] = backy;
284 tstack_p->backpt[2] = backz;
288 backx = frontx + front * ( backx - frontx );
289 backy = fronty + front * ( backy - fronty );
290 backz = frontz + front * ( backz - frontz );
292 node = tnode->children[side];