contrib/bobtoolz/visfind.cpp

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