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