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