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         plane = &dplanes[node->planeNum];
  43         d = DotProduct(origin, plane->normal) - plane->dist;
  44         if (d >= 0) {
  45             if (node->children[0] < 0) {
  46                 return -(node->children[0] + 1);
  47             } else {
  48                 node = &dnodes[node->children[0]];
  49             }
  50         } else if (node->children[1] < 0) {
  51             return -(node->children[1] + 1);
  52         } else {
  53             node = &dnodes[node->children[1]];
  54         }
  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) {
  66             return (i);
  67         }
  68     }
  69     return (0);
  70 }
  71
  72 // leaf1 = origin leaf
  73 // leaf2 = leaf to test for
  74 /*int bsp_InPVS(int cluster1, int cluster2)
  75    {
  76     vis_header          *vheader;
  77     byte                        *visdata;
  78
  79     vheader = (vis_header *) visBytes;
  80     visdata = visBytes + VIS_HEADER_SIZE;
  81
  82     return( *( visdata + ( cluster1 * vheader->leafbytes ) + (cluster2 / 8) ) & ( 1 << ( cluster2 % 8 ) ) );
  83    }*/
  84
  85 void bsp_setbitvectorlength(byte *v, int length_bits, int length_vector)
  86 {
  87     int i;
  88
  89     i = length_bits / 8;
  90
  91     *(v + i) = (byte) bitmasks[length_bits % 8];
  92
  93     memset((v + i + 1), 0, length_vector - i - 1);
  94 }
  95
  96
  97 void bsp_bitvectorsubtract(byte *first, byte *second, byte *out, int length)
  98 {
  99
 100     int i;
 101
 102     for (i = 0; i < length; i++) {
 103         *(out + i) = *(first + i) & ~(*(second + i));
 104     }
 105 }
 106
 107 int bsp_countclusters(byte *bitvector, int length)
 108 {
 109     int i, j, c;
 110
 111     c = 0;
 112     for (i = 0; i < length; i++) {
 113         for (j = 0; j < 8; j++) {
 114             if ((*(bitvector + i) & (1 << j))) {
 115                 c++;
 116             }
 117         }
 118     }
 119     return (c);
 120 }
 121
 122 int bsp_countclusters_mask(byte *bitvector, byte *maskvector, int length)
 123 {
 124     int i, j, c;
 125
 126     c = 0;
 127     for (i = 0; i < length; i++) {
 128         for (j = 0; j < 8; j++) {
 129             if ((*(bitvector + i) & (1 << j)) && (*(maskvector + i) & (1 << j))) {
 130                 c++;
 131             }
 132         }
 133     }
 134     return (c);
 135 }
 136
 137 void AddCluster(std::list<DWinding *> *pointlist, dleaf_t *cl, bool *repeatlist, vec3_t clr)
 138 {
 139     DWinding *w;
 140
 141     int *leafsurf = &dleafsurfaces[cl->firstLeafSurface];
 142     for (int k = 0; k < cl->numLeafSurfaces; k++, leafsurf++) {
 143         if (repeatlist[*leafsurf]) {
 144             continue;
 145         }
 146
 147         dsurface_t *surf = &drawSurfaces[*leafsurf];
 148         if (surf->surfaceType != MST_PLANAR) {
 149             continue;
 150         }
 151
 152         qdrawVert_t *vert = &drawVerts[surf->firstVert];
 153         if (surf->firstVert + surf->numVerts > numDrawVerts) {
 154             DoMessageBox("Warning", "Warning", eMB_OK);
 155         }
 156
 157         w = new DWinding();
 158         w->AllocWinding(surf->numVerts);
 159
 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];
 164
 165             w->clr[0] = clr[0];
 166             w->clr[1] = clr[1];
 167             w->clr[2] = clr[2];
 168         }
 169         pointlist->push_back(w);
 170
 171         repeatlist[*leafsurf] = true;
 172     }
 173 }
 174
 175 /*
 176    =============
 177    CreateTrace
 178    =============
 179  */
 180 std::list<DWinding *> *CreateTrace(dleaf_t *leaf, int c, vis_header *header, byte *visdata, byte *seen)
 181 {
 182     byte *vis;
 183     int i, j, clusterNum;
 184     std::list<DWinding *> *pointlist = new std::list<DWinding *>;
 185     bool *repeatlist = new bool[numDrawSurfaces];
 186     dleaf_t *cl;
 187
 188     vec3_t clrRnd[5] = {
 189             {0.f, 0.f, 1.f},
 190             {0.f, 1.f, 1.f},
 191             {1.f, 0.f, 0.f},
 192             {1.f, 0.f, 1.f},
 193             {1.f, 1.f, 0.f},
 194     };
 195
 196     vec3_t clrGreen = {0.f, 1.f, 0.f};
 197
 198     memset(repeatlist, 0, sizeof(bool) * numDrawSurfaces);
 199
 200     vis = visdata + (c * header->leafbytes);
 201
 202     clusterNum = 0;
 203
 204     AddCluster(pointlist, &(dleafs[bsp_leafnumforcluster(c)]), repeatlist, clrGreen);
 205
 206     for (i = 0; i < header->leafbytes; i++) {
 207         for (j = 0; j < 8; j++) {
 208             cl = &(dleafs[bsp_leafnumforcluster(clusterNum)]);
 209
 210             if ((*(vis + i) & (1 << j)) && (*(seen + i) & (1 << j)) && (leaf->area == cl->area)) {
 211                 AddCluster(pointlist, cl, repeatlist, clrRnd[rand() % 5]);
 212             }
 213             clusterNum++;
 214         }
 215     }
 216
 217     delete repeatlist;
 218
 219     return pointlist;
 220 }
 221
 222 /*
 223    =============
 224    TraceCluster
 225
 226    setup for CreateTrace
 227    =============
 228  */
 229 std::list<DWinding *> *TraceCluster(int leafnum)
 230 {
 231     byte seen[(MAX_MAP_LEAFS / 8) + 1];
 232     vis_header *vheader;
 233     byte *visdata;
 234     dleaf_t *leaf;
 235
 236     vheader = (vis_header *) visBytes;
 237     visdata = visBytes + sizeof(vis_header);
 238
 239     memset(seen, 0xFF, sizeof(seen));
 240     bsp_setbitvectorlength(seen, vheader->portalclusters, sizeof(seen));
 241
 242     leaf = &(dleafs[leafnum]);
 243
 244     return CreateTrace(leaf, leaf->cluster, vheader, visdata, seen);
 245 }
 246
 247 std::list<DWinding *> *BuildTrace(char *filename, vec3_t v_origin)
 248 {
 249     if (!LoadBSPFile(filename)) {
 250         return NULL;
 251     }
 252
 253     int leafnum = bsp_leafnumfororigin(v_origin);
 254
 255     std::list<DWinding *> *pointlist = TraceCluster(leafnum);
 256
 257     FreeBSPData();
 258
 259     return pointlist;
 260 }