1 // Requries parts of the q3 tools source to compile
2 // Date: Oct 5, 2001
3 // Written by: Brad Whitehead (whiteheb@gamerstv.net)
4
5 #include "StdAfx.h"
6 #include "dialogs/dialogs-gtk.h"
7 #include "DWinding.h"
8 #include "bsploader.h"
9
10 #include "gtkr_list.h"
11
12 typedef struct {
13 int portalclusters;
14 int leafbytes; //leafbytes = ((portalclusters+63)&~63)>>3;
15 } vis_header;
16
17 // added because int shift = 32; i = 0xFFFFFFFF >> shift;
18 // then i = 0xFFFFFFFF, when it should = 0
19 const unsigned long bitmasks[33] =
20 {
21 0x00000000,
22 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
23 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
24 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
25 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
26 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
27 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
28 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
29 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
30 };
31
bsp_leafnumfororigin(vec3_t origin)32 int bsp_leafnumfororigin(vec3_t origin)
33 {
34 dnode_t *node;
35 dplane_t *plane;
36 float d;
37
38 // TODO: check if origin is in the map??
39
40 node = dnodes;
41 while (true)
42 {
43 plane = &dplanes[node->planeNum];
44 d = DotProduct (origin, plane->normal) - plane->dist;
45 if ( d >= 0 )
46 if ( node->children[0] < 0 )
47 return -(node->children[0]+1);
48 else
49 node = &dnodes[node->children[0]];
50 else
51 if ( node->children[1] < 0 )
52 return -(node->children[1]+1);
53 else
54 node = &dnodes[node->children[1]];
55 }
56 return 0;
57 }
58
bsp_leafnumforcluster(int cluster)59 int bsp_leafnumforcluster(int cluster)
60 {
61 dleaf_t *l;
62 int i;
63
64 for ( i = 0, l = dleafs; i < numleafs; i++, l++ )
65 if ( l->cluster == cluster ) return(i);
66 return(0);
67 }
68
69 // leaf1 = origin leaf
70 // leaf2 = leaf to test for
71 /*int bsp_InPVS(int cluster1, int cluster2)
72 {
73 vis_header *vheader;
74 byte *visdata;
75
76 vheader = (vis_header *) visBytes;
77 visdata = visBytes + VIS_HEADER_SIZE;
78
79 return( *( visdata + ( cluster1 * vheader->leafbytes ) + (cluster2 / 8) ) & ( 1 << ( cluster2 % 8 ) ) );
80 }*/
81
bsp_setbitvectorlength(byte * v,int length_bits,int length_vector)82 void bsp_setbitvectorlength( byte *v, int length_bits, int length_vector )
83 {
84 int i;
85
86 i = length_bits/8;
87
88 *(v+i) = (byte) bitmasks[length_bits % 8];
89
90 memset((v+i+1), 0, length_vector-i-1);
91 }
92
93
bsp_bitvectorsubtract(byte * first,byte * second,byte * out,int length)94 void bsp_bitvectorsubtract(byte *first, byte *second, byte *out, int length)
95 {
96
97 int i;
98
99 for ( i = 0; i < length; i++ )
100 *(out+i) = *(first+i) & ~(*(second+i));
101 }
102
bsp_countclusters(byte * bitvector,int length)103 int bsp_countclusters(byte *bitvector, int length)
104 {
105 int i, j, c;
106
107 c = 0;
108 for ( i = 0; i < length; i++ )
109 for ( j = 0; j < 8; j++ )
110 if ( (*(bitvector+i) & (1 << j)) ) c++;
111 return(c);
112 }
113
bsp_countclusters_mask(byte * bitvector,byte * maskvector,int length)114 int bsp_countclusters_mask(byte *bitvector, byte *maskvector, int length)
115 {
116 int i, j, c;
117
118 c = 0;
119 for ( i = 0; i < length; i++ )
120 for ( j = 0; j < 8; j++ )
121 if ( (*(bitvector+i) & (1 << j)) && (*(maskvector+i) & (1 << j)) ) c++;
122 return(c);
123 }
124
AddCluster(list<DWinding * > * pointlist,dleaf_t * cl,bool * repeatlist,vec3_t clr)125 void AddCluster(list<DWinding*> *pointlist, dleaf_t *cl, bool* repeatlist, vec3_t clr)
126 {
127 DWinding* w;
128
129 int* leafsurf = &dleafsurfaces[cl->firstLeafSurface];
130 for(int k = 0; k < cl->numLeafSurfaces; k++, leafsurf++)
131 {
132 if(repeatlist[*leafsurf])
133 continue;
134
135 dsurface_t* surf = &drawSurfaces[*leafsurf];
136 if(surf->surfaceType != MST_PLANAR)
137 continue;
138
139 qdrawVert_t* vert = &drawVerts[surf->firstVert];
140 if(surf->firstVert + surf->numVerts > numDrawVerts)
141 DoMessageBox("Warning", "Warning", eMB_OK);
142
143 w = new DWinding();
144 w->AllocWinding(surf->numVerts);
145
146 for (int l = 0; l < surf->numVerts; l++, vert++)
147 {
148 (w->p[l])[0] = vert->xyz[0];
149 (w->p[l])[1] = vert->xyz[1];
150 (w->p[l])[2] = vert->xyz[2];
151
152 w->clr[0] = clr[0];
153 w->clr[1] = clr[1];
154 w->clr[2] = clr[2];
155 }
156 pointlist->push_back(w);
157
158 repeatlist[*leafsurf] = true;
159 }
160 }
161
162 /*
163 =============
164 CreateTrace
165 =============
166 */
CreateTrace(dleaf_t * leaf,int c,vis_header * header,byte * visdata,byte * seen)167 list<DWinding*> *CreateTrace( dleaf_t *leaf, int c, vis_header *header, byte *visdata, byte *seen )
168 {
169 byte *vis;
170 int i, j, clusterNum;
171 list<DWinding*> *pointlist = new list<DWinding*>;
172 bool* repeatlist = new bool[numDrawSurfaces];
173 dleaf_t *cl;
174
175 vec3_t clrRnd[5] = {
176 {0.f, 0.f, 1.f},
177 {0.f, 1.f, 1.f},
178 {1.f, 0.f, 0.f},
179 {1.f, 0.f, 1.f},
180 {1.f, 1.f, 0.f},
181 };
182
183 vec3_t clrGreen = {0.f, 1.f, 0.f};
184
185 memset(repeatlist, 0, sizeof(bool)*numDrawSurfaces);
186
187 vis = visdata + ( c * header->leafbytes );
188
189 clusterNum = 0;
190
191 AddCluster(pointlist, &(dleafs[bsp_leafnumforcluster( c )]), repeatlist, clrGreen);
192
193 for ( i = 0; i < header->leafbytes; i++ )
194 {
195 for ( j = 0; j < 8; j++ )
196 {
197 cl = &(dleafs[bsp_leafnumforcluster( clusterNum )]);
198
199 if ( ( *(vis + i) & (1 << j) ) && (*(seen+i) & (1 << j)) && (leaf->area == cl->area))
200 AddCluster(pointlist, cl, repeatlist, clrRnd[rand()%5]);
201 clusterNum++;
202 }
203 }
204
205 delete repeatlist;
206
207 return pointlist;
208 }
209
210 /*
211 =============
212 TraceCluster
213
214 setup for CreateTrace
215 =============
216 */
TraceCluster(int leafnum)217 list<DWinding*> *TraceCluster (int leafnum)
218 {
219 byte seen[(MAX_MAP_LEAFS/8) + 1];
220 vis_header *vheader;
221 byte *visdata;
222 dleaf_t *leaf;
223
224 vheader = (vis_header *) visBytes;
225 visdata = visBytes + sizeof(vis_header);
226
227 memset(seen, 0xFF, sizeof(seen));
228 bsp_setbitvectorlength(seen, vheader->portalclusters, sizeof(seen));
229
230 leaf = &(dleafs[leafnum]);
231
232 return CreateTrace(leaf, leaf->cluster, vheader, visdata, seen);
233 }
234
BuildTrace(char * filename,vec3_t v_origin)235 list<DWinding *>* BuildTrace(char* filename, vec3_t v_origin)
236 {
237 if(!LoadBSPFile(filename))
238 return NULL;
239
240 int leafnum = bsp_leafnumfororigin(v_origin);
241
242 list<DWinding*> *pointlist = TraceCluster(leafnum);
243
244 FreeBSPData();
245
246 return pointlist;
247 }
248