1 #include "cmdlib.h"
2 #include "mathlib.h"
3 #include "bspfile.h"
4
5 // #define ON_EPSILON 0.001
6
7 typedef struct tnode_s
8 {
9 planetypes type;
10 vec3_t normal;
11 float dist;
12 int children[2];
13 int pad;
14 } tnode_t;
15
16 static tnode_t* tnodes;
17 static tnode_t* tnode_p;
18
19 /*
20 * ==============
21 * MakeTnode
22 *
23 * Converts the disk node structure into the efficient tracing structure
24 * ==============
25 */
MakeTnode(const int nodenum)26 static void MakeTnode(const int nodenum)
27 {
28 tnode_t* t;
29 dplane_t* plane;
30 int i;
31 dnode_t* node;
32
33 t = tnode_p++;
34
35 node = g_dnodes + nodenum;
36 plane = g_dplanes + node->planenum;
37
38 t->type = plane->type;
39 VectorCopy(plane->normal, t->normal);
40 t->dist = plane->dist;
41
42 for (i = 0; i < 2; i++)
43 {
44 if (node->children[i] < 0)
45 t->children[i] = g_dleafs[-node->children[i] - 1].contents;
46 else
47 {
48 t->children[i] = tnode_p - tnodes;
49 MakeTnode(node->children[i]);
50 }
51 }
52
53 }
54
55 /*
56 * =============
57 * MakeTnodes
58 *
59 * Loads the node structure out of a .bsp file to be used for light occlusion
60 * =============
61 */
MakeTnodes(dmodel_t *)62 void MakeTnodes(dmodel_t* /*bm*/)
63 {
64 // 32 byte align the structs
65 tnodes = (tnode_t*)calloc((g_numnodes + 1), sizeof(tnode_t));
66
67 #if SIZEOF_CHARP == 8
68 tnodes = (tnode_t*)(((long long)tnodes + 31) & ~31);
69 #else
70 tnodes = (tnode_t*)(((int)tnodes + 31) & ~31);
71 #endif
72 tnode_p = tnodes;
73
74 MakeTnode(0);
75 }
76
77 //==========================================================
78
TestLine_r(const int node,const vec3_t start,const vec3_t stop)79 int TestLine_r(const int node, const vec3_t start, const vec3_t stop)
80 {
81 tnode_t* tnode;
82 float front, back;
83 vec3_t mid;
84 float frac;
85 int side;
86 int r;
87
88 if ( (node == CONTENTS_SOLID)
89 || (node == CONTENTS_SKY )
90 /*|| (node == CONTENTS_NULL ) */
91 )
92 return node;
93
94 if (node < 0)
95 return CONTENTS_EMPTY;
96
97 tnode = &tnodes[node];
98 switch (tnode->type)
99 {
100 case plane_x:
101 front = start[0] - tnode->dist;
102 back = stop[0] - tnode->dist;
103 break;
104 case plane_y:
105 front = start[1] - tnode->dist;
106 back = stop[1] - tnode->dist;
107 break;
108 case plane_z:
109 front = start[2] - tnode->dist;
110 back = stop[2] - tnode->dist;
111 break;
112 default:
113 front = (start[0] * tnode->normal[0] + start[1] * tnode->normal[1] + start[2] * tnode->normal[2]) - tnode->dist;
114 back = (stop[0] * tnode->normal[0] + stop[1] * tnode->normal[1] + stop[2] * tnode->normal[2]) - tnode->dist;
115 break;
116 }
117
118 if (front >= -ON_EPSILON && back >= -ON_EPSILON)
119 return TestLine_r(tnode->children[0], start, stop);
120
121 if (front < ON_EPSILON && back < ON_EPSILON)
122 return TestLine_r(tnode->children[1], start, stop);
123
124 side = front < 0;
125
126 frac = front / (front - back);
127
128 mid[0] = start[0] + (stop[0] - start[0]) * frac;
129 mid[1] = start[1] + (stop[1] - start[1]) * frac;
130 mid[2] = start[2] + (stop[2] - start[2]) * frac;
131
132 r = TestLine_r(tnode->children[side], start, mid);
133 if (r != CONTENTS_EMPTY)
134 return r;
135 return TestLine_r(tnode->children[!side], mid, stop);
136 }
137
TestLine(const vec3_t start,const vec3_t stop)138 int TestLine(const vec3_t start, const vec3_t stop)
139 {
140 return TestLine_r(0, start, stop);
141 }
142