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 }