1 // Requries parts of the q3 tools source to compile
3 // Written by: Brad Whitehead (whiteheb@gamerstv.net)
6 #include "dialogs/dialogs-gtk.h"
14 int leafbytes; //leafbytes = ((portalclusters+63)&~63)>>3;
17 // added because int shift = 32; i = 0xFFFFFFFF >> shift;
18 // then i = 0xFFFFFFFF, when it should = 0
19 const unsigned long bitmasks[33] =
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
32 int bsp_leafnumfororigin(vec3_t origin)
38 // TODO: check if origin is in the map??
42 plane = &dplanes[node->planeNum];
43 d = DotProduct(origin, plane->normal) - plane->dist;
45 if (node->children[0] < 0) {
46 return -(node->children[0] + 1);
48 node = &dnodes[node->children[0]];
50 } else if (node->children[1] < 0) {
51 return -(node->children[1] + 1);
53 node = &dnodes[node->children[1]];
59 int bsp_leafnumforcluster(int cluster)
64 for (i = 0, l = dleafs; i < numleafs; i++, l++) {
65 if (l->cluster == cluster) {
72 // leaf1 = origin leaf
73 // leaf2 = leaf to test for
74 /*int bsp_InPVS(int cluster1, int cluster2)
79 vheader = (vis_header *) visBytes;
80 visdata = visBytes + VIS_HEADER_SIZE;
82 return( *( visdata + ( cluster1 * vheader->leafbytes ) + (cluster2 / 8) ) & ( 1 << ( cluster2 % 8 ) ) );
85 void bsp_setbitvectorlength(byte *v, int length_bits, int length_vector)
91 *(v + i) = (byte) bitmasks[length_bits % 8];
93 memset((v + i + 1), 0, length_vector - i - 1);
97 void bsp_bitvectorsubtract(byte *first, byte *second, byte *out, int length)
102 for (i = 0; i < length; i++) {
103 *(out + i) = *(first + i) & ~(*(second + i));
107 int bsp_countclusters(byte *bitvector, int length)
112 for (i = 0; i < length; i++) {
113 for (j = 0; j < 8; j++) {
114 if ((*(bitvector + i) & (1 << j))) {
122 int bsp_countclusters_mask(byte *bitvector, byte *maskvector, int length)
127 for (i = 0; i < length; i++) {
128 for (j = 0; j < 8; j++) {
129 if ((*(bitvector + i) & (1 << j)) && (*(maskvector + i) & (1 << j))) {
137 void AddCluster(std::list<DWinding *> *pointlist, dleaf_t *cl, bool *repeatlist, vec3_t clr)
141 int *leafsurf = &dleafsurfaces[cl->firstLeafSurface];
142 for (int k = 0; k < cl->numLeafSurfaces; k++, leafsurf++) {
143 if (repeatlist[*leafsurf]) {
147 dsurface_t *surf = &drawSurfaces[*leafsurf];
148 if (surf->surfaceType != MST_PLANAR) {
152 qdrawVert_t *vert = &drawVerts[surf->firstVert];
153 if (surf->firstVert + surf->numVerts > numDrawVerts) {
154 DoMessageBox("Warning", "Warning", eMB_OK);
158 w->AllocWinding(surf->numVerts);
160 for (int l = 0; l < surf->numVerts; l++, vert++) {
161 (w->p[l])[0] = vert->xyz[0];
162 (w->p[l])[1] = vert->xyz[1];
163 (w->p[l])[2] = vert->xyz[2];
169 pointlist->push_back(w);
171 repeatlist[*leafsurf] = true;
180 std::list<DWinding *> *CreateTrace(dleaf_t *leaf, int c, vis_header *header, byte *visdata, byte *seen)
183 int i, j, clusterNum;
184 std::list<DWinding *> *pointlist = new std::list<DWinding *>;
185 bool *repeatlist = new bool[numDrawSurfaces];
196 vec3_t clrGreen = {0.f, 1.f, 0.f};
198 memset(repeatlist, 0, sizeof(bool) * numDrawSurfaces);
200 vis = visdata + (c * header->leafbytes);
204 AddCluster(pointlist, &(dleafs[bsp_leafnumforcluster(c)]), repeatlist, clrGreen);
206 for (i = 0; i < header->leafbytes; i++) {
207 for (j = 0; j < 8; j++) {
208 cl = &(dleafs[bsp_leafnumforcluster(clusterNum)]);
210 if ((*(vis + i) & (1 << j)) && (*(seen + i) & (1 << j)) && (leaf->area == cl->area)) {
211 AddCluster(pointlist, cl, repeatlist, clrRnd[rand() % 5]);
226 setup for CreateTrace
229 std::list<DWinding *> *TraceCluster(int leafnum)
231 byte seen[(MAX_MAP_LEAFS / 8) + 1];
236 vheader = (vis_header *) visBytes;
237 visdata = visBytes + sizeof(vis_header);
239 memset(seen, 0xFF, sizeof(seen));
240 bsp_setbitvectorlength(seen, vheader->portalclusters, sizeof(seen));
242 leaf = &(dleafs[leafnum]);
244 return CreateTrace(leaf, leaf->cluster, vheader, visdata, seen);
247 std::list<DWinding *> *BuildTrace(char *filename, vec3_t v_origin)
249 if (!LoadBSPFile(filename)) {
253 int leafnum = bsp_leafnumfororigin(v_origin);
255 std::list<DWinding *> *pointlist = TraceCluster(leafnum);