- Radiant is now Vista compatible (Aero must be disabled)
[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 "visfind.h"
6 #include "dialogs/dialogs-gtk.h"
7 #include "DWinding.h"
8 #include "bsploader.h"
9
10 #include <list>
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
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
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
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
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
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
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
125 void AddCluster(std::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 */
167 std::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         std::list<DWinding*> *pointlist = new std::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 */
217 std::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
235 std::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         std::list<DWinding*> *pointlist = TraceCluster(leafnum);
243
244         FreeBSPData();
245
246         return pointlist;
247 }