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