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