tools/quake3/q3map2/lightmaps.c

   1 /*
   2    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21
  22 #include "qbsp.h"
  23
  24
  25 /*
  26
  27    Lightmap allocation has to be done after all flood filling and
  28    visible surface determination.
  29
  30  */
  31
  32 int numSortShaders;
  33 mapDrawSurface_t    *surfsOnShader[ MAX_MAP_SHADERS ];
  34
  35
  36 int allocated[ LIGHTMAP_WIDTH ];
  37
  38 int numLightmaps = 1;
  39 int c_exactLightmap = 0;
  40 int c_planarPatch = 0;
  41 int c_nonplanarLightmap = 0;
  42
  43
  44 void PrepareNewLightmap( void ) {
  45         memset( allocated, 0, sizeof( allocated ) );
  46         numLightmaps++;
  47 }
  48
  49 /*
  50    ===============
  51    AllocLMBlock
  52
  53    returns a texture number and the position inside it
  54    ===============
  55  */
  56 qboolean AllocLMBlock( int w, int h, int *x, int *y ){
  57         int i, j;
  58         int best, best2;
  59
  60         best = LIGHTMAP_HEIGHT;
  61
  62         for ( i = 0 ; i <= LIGHTMAP_WIDTH - w ; i++ ) {
  63                 best2 = 0;
  64
  65                 for ( j = 0 ; j < w ; j++ ) {
  66                         if ( allocated[i + j] >= best ) {
  67                                 break;
  68                         }
  69                         if ( allocated[i + j] > best2 ) {
  70                                 best2 = allocated[i + j];
  71                         }
  72                 }
  73                 if ( j == w ) {   // this is a valid spot
  74                         *x = i;
  75                         *y = best = best2;
  76                 }
  77         }
  78
  79         if ( best + h > LIGHTMAP_HEIGHT ) {
  80                 return qfalse;
  81         }
  82
  83         for ( i = 0 ; i < w ; i++ ) {
  84                 allocated[*x + i] = best + h;
  85         }
  86
  87         return qtrue;
  88 }
  89
  90
  91 /*
  92    ===================
  93    AllocateLightmapForPatch
  94    ===================
  95  */
  96 //#define LIGHTMAP_PATCHSHIFT
  97
  98 void AllocateLightmapForPatch( mapDrawSurface_t *ds ){
  99         int i, j, k;
 100         drawVert_t  *verts;
 101         int w, h;
 102         int x, y;
 103         float s, t;
 104         mesh_t mesh, *subdividedMesh, *tempMesh, *newmesh;
 105         int widthtable[LIGHTMAP_WIDTH], heighttable[LIGHTMAP_HEIGHT], ssize;
 106
 107         verts = ds->verts;
 108
 109         mesh.width = ds->patchWidth;
 110         mesh.height = ds->patchHeight;
 111         mesh.verts = verts;
 112         newmesh = SubdivideMesh( mesh, 8, 999 );
 113
 114         PutMeshOnCurve( *newmesh );
 115         tempMesh = RemoveLinearMeshColumnsRows( newmesh );
 116         FreeMesh( newmesh );
 117
 118         /* get sample size */
 119         ssize = ds->sampleSize;
 120
 121
 122 #ifdef LIGHTMAP_PATCHSHIFT
 123         subdividedMesh = SubdivideMeshQuads( tempMesh, ssize, LIGHTMAP_WIDTH - 1, widthtable, heighttable );
 124 #else
 125         subdividedMesh = SubdivideMeshQuads( tempMesh, ssize, LIGHTMAP_WIDTH, widthtable, heighttable );
 126 #endif
 127
 128         w = subdividedMesh->width;
 129         h = subdividedMesh->height;
 130
 131 #ifdef LIGHTMAP_PATCHSHIFT
 132         w++;
 133         h++;
 134 #endif
 135
 136         FreeMesh( subdividedMesh );
 137
 138         // allocate the lightmap
 139         c_exactLightmap += w * h;
 140
 141         if ( !AllocLMBlock( w, h, &x, &y ) ) {
 142                 PrepareNewLightmap();
 143                 if ( !AllocLMBlock( w, h, &x, &y ) ) {
 144                         Error( "Entity %i, brush %i: Lightmap allocation failed",
 145                                    ds->mapBrush->entitynum, ds->mapBrush->brushnum );
 146                 }
 147         }
 148
 149 #ifdef LIGHTMAP_PATCHSHIFT
 150         w--;
 151         h--;
 152 #endif
 153
 154         // set the lightmap texture coordinates in the drawVerts
 155         ds->lightmapNum = numLightmaps - 1;
 156         ds->lightmapWidth = w;
 157         ds->lightmapHeight = h;
 158         ds->lightmapX = x;
 159         ds->lightmapY = y;
 160
 161         for ( i = 0 ; i < ds->patchWidth ; i++ ) {
 162                 for ( k = 0 ; k < w ; k++ ) {
 163                         if ( originalWidths[k] >= i ) {
 164                                 break;
 165                         }
 166                 }
 167                 if ( k >= w ) {
 168                         k = w - 1;
 169                 }
 170                 s = x + k;
 171                 for ( j = 0 ; j < ds->patchHeight ; j++ ) {
 172                         for ( k = 0 ; k < h ; k++ ) {
 173                                 if ( originalHeights[k] >= j ) {
 174                                         break;
 175                                 }
 176                         }
 177                         if ( k >= h ) {
 178                                 k = h - 1;
 179                         }
 180                         t = y + k;
 181                         verts[i + j * ds->patchWidth].lightmap[0] = ( s + 0.5 ) / LIGHTMAP_WIDTH;
 182                         verts[i + j * ds->patchWidth].lightmap[1] = ( t + 0.5 ) / LIGHTMAP_HEIGHT;
 183                 }
 184         }
 185 }
 186
 187
 188 /*
 189    ===================
 190    AllocateLightmapForSurface
 191    ===================
 192  */
 193
 194 //#define       LIGHTMAP_BLOCK  16
 195
 196 void AllocateLightmapForSurface( mapDrawSurface_t *ds ){
 197         vec3_t mins, maxs, size, exactSize, delta;
 198         int i;
 199         drawVert_t  *verts;
 200         int w, h;
 201         int x, y, ssize;
 202         int axis;
 203         vec3_t vecs[ 2 ];
 204         float s, t;
 205         vec3_t origin;
 206         vec4_t plane;
 207         float d;
 208
 209
 210         /* debug code */
 211         #if 0
 212         if ( ds->type == SURF_META && ds->planar == qfalse ) {
 213                 Sys_Printf( "NPMS: %3d vertexes, %s\n", ds->numVerts, ds->shaderInfo->shader );
 214         }
 215         else if ( ds->type == SURF_META && ds->planar == qtrue ) {
 216                 Sys_Printf( "PMS:  %3d vertexes, %s\n", ds->numVerts, ds->shaderInfo->shader );
 217         }
 218         #endif
 219
 220         /* ydnar: handle planar patches */
 221         if ( noPatchFix == qtrue || ( ds->type == SURF_PATCH && ds->planeNum < 0 ) ) {
 222                 AllocateLightmapForPatch( ds );
 223                 return;
 224         }
 225
 226         /* get sample size */
 227         ssize = ds->sampleSize;
 228
 229         /* bound the surface */
 230         ClearBounds( mins, maxs );
 231         verts = ds->verts;
 232         for ( i = 0 ; i < ds->numVerts ; i++ )
 233                 AddPointToBounds( verts[i].xyz, mins, maxs );
 234
 235         /* round to the lightmap resolution */
 236         for ( i = 0; i < 3; i++ )
 237         {
 238                 exactSize[i] = maxs[i] - mins[i];
 239                 mins[i] = ssize * floor( mins[i] / ssize );
 240                 maxs[i] = ssize * ceil( maxs[i] / ssize );
 241                 size[i] = ( maxs[i] - mins[i] ) / ssize + 1;
 242         }
 243
 244         /* ydnar: lightmap projection axis is already stored */
 245         memset( vecs, 0, sizeof( vecs ) );
 246
 247         /* classify the plane (x y or z major) (ydnar: biased to z axis projection) */
 248         if ( ds->lightmapAxis[ 2 ] >= ds->lightmapAxis[ 0 ] && ds->lightmapAxis[ 2 ] >= ds->lightmapAxis[ 1 ] ) {
 249                 w = size[ 0 ];
 250                 h = size[ 1 ];
 251                 axis = 2;
 252                 vecs[ 0 ][ 0 ] = 1.0 / ssize;
 253                 vecs[ 1 ][ 1 ] = 1.0 / ssize;
 254         }
 255         else if ( ds->lightmapAxis[ 0 ] >= ds->lightmapAxis[ 1 ] && ds->lightmapAxis[ 0 ] >= ds->lightmapAxis[ 2 ] ) {
 256                 w = size[ 1 ];
 257                 h = size[ 2 ];
 258                 axis = 0;
 259                 vecs[ 0 ][ 1 ] = 1.0 / ssize;
 260                 vecs[ 1 ][ 2 ] = 1.0 / ssize;
 261         }
 262         else
 263         {
 264                 w = size[ 0 ];
 265                 h = size[ 2 ];
 266                 axis = 1;
 267                 vecs[ 0 ][ 0 ] = 1.0 / ssize;
 268                 vecs[ 1 ][ 2 ] = 1.0 / ssize;
 269         }
 270
 271         /* odd check, given projection is now precalculated */
 272         if ( ds->lightmapAxis[ axis ] == 0 ) {
 273                 Error( "Chose a 0 valued axis" );
 274         }
 275
 276         /* clamp to lightmap texture resolution */
 277         if ( w > LIGHTMAP_WIDTH ) {
 278                 VectorScale( vecs[0], (float) LIGHTMAP_WIDTH / w, vecs[0] );
 279                 w = LIGHTMAP_WIDTH;
 280         }
 281         if ( h > LIGHTMAP_HEIGHT ) {
 282                 VectorScale( vecs[1], (float) LIGHTMAP_HEIGHT / h, vecs[1] );
 283                 h = LIGHTMAP_HEIGHT;
 284         }
 285
 286
 287         /* ydnar */
 288         if ( ds->planar == qfalse ) {
 289                 c_nonplanarLightmap += w * h;
 290         }
 291         c_exactLightmap += w * h;
 292
 293
 294         if ( !AllocLMBlock( w, h, &x, &y ) ) {
 295                 PrepareNewLightmap();
 296                 if ( !AllocLMBlock( w, h, &x, &y ) ) {
 297                         Error( "Entity %i, brush %i: Lightmap allocation failed",
 298                                    ds->mapBrush->entitynum, ds->mapBrush->brushnum );
 299                 }
 300         }
 301
 302         /* set the lightmap texture coordinates in the drawVerts */
 303         ds->lightmapNum = numLightmaps - 1;
 304         ds->lightmapWidth = w;
 305         ds->lightmapHeight = h;
 306         ds->lightmapX = x;
 307         ds->lightmapY = y;
 308         for ( i = 0 ; i < ds->numVerts ; i++ )
 309         {
 310                 VectorSubtract( verts[i].xyz, mins, delta );
 311                 s = DotProduct( delta, vecs[0] ) + x + 0.5;
 312                 t = DotProduct( delta, vecs[1] ) + y + 0.5;
 313                 verts[i].lightmap[0] = s / LIGHTMAP_WIDTH;
 314                 verts[i].lightmap[1] = t / LIGHTMAP_HEIGHT;
 315         }
 316
 317         /* calculate the world coordinates of the lightmap samples */
 318
 319         /* construct a plane from the first vert and clear bounding box */
 320
 321         /* project mins onto plane to get origin */
 322         VectorCopy( ds->lightmapVecs[ 2 ], plane );
 323         plane[ 3 ] = DotProduct( ds->verts[ 0 ].xyz, plane );
 324         d = DotProduct( mins, plane ) - plane[ 3 ];
 325         d /= plane[ axis ];
 326
 327         //% d = DotProduct( mins, plane->normal ) - plane->dist;
 328         //% d /= plane->normal[ axis ];
 329         VectorCopy( mins, origin );
 330         origin[ axis ] -= d;
 331
 332         /* project stepped lightmap blocks and subtract to get planevecs */
 333         for ( i = 0; i < 2; i++ )
 334         {
 335                 vec3_t normalized;
 336                 float len;
 337
 338                 len = VectorNormalize( vecs[i], normalized );
 339                 VectorScale( normalized, ( 1.0 / len ), vecs[i] );
 340                 d = DotProduct( vecs[i], plane );
 341                 d /= plane[ axis ];
 342                 //%d = DotProduct( vecs[i], plane->normal );
 343                 //%d /= plane->normal[ axis ];
 344                 vecs[i][axis] -= d;
 345         }
 346
 347         /* store lightmap origin and vectors (fixme: make this work right) */
 348         VectorCopy( origin, ds->lightmapOrigin );
 349         //% VectorCopy( plane->normal, ds->lightmapVecs[ 2 ] );
 350
 351         /* ydnar: lightmap vectors 0 and 1 are used for lod bounds, so don't overwrite */
 352         if ( ds->type == SURF_PATCH ) {
 353                 c_planarPatch++;
 354         }
 355
 356         /* store lightmap vectors */
 357         VectorCopy( vecs[ 0 ], ds->lightmapVecs[ 0 ] );
 358         VectorCopy( vecs[ 1 ], ds->lightmapVecs[ 1 ] );
 359
 360         /* ydnar: print some stats */
 361         //Sys_FPrintf( SYS_VRB, "Lightmap block %3d (%3d, %3d) (%3d x %3d) emitted\n", (numLightmaps - 1), x, y, w, h );
 362 }
 363
 364
 365 /*
 366    ===================
 367    AllocateLightmaps
 368    ===================
 369  */
 370 void AllocateLightmaps( entity_t *e ){
 371         int i, j;
 372         mapDrawSurface_t    *ds;
 373         shaderInfo_t        *si;
 374
 375
 376         /* note it */
 377         Sys_FPrintf( SYS_VRB,"--- AllocateLightmaps ---\n" );
 378
 379
 380         /* sort all surfaces by shader so common shaders will usually be in the same lightmap */
 381         /* ydnar: this is done in two passes, because of an odd bug with lightmapped terrain */
 382         numSortShaders = 0;
 383         for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
 384         {
 385                 /* get surface and early out if possible */
 386                 ds = &mapDrawSurfs[ i ];
 387                 si = ds->shaderInfo;
 388                 if ( si->surfaceFlags & SURF_VERTEXLIT ) {
 389                         continue;
 390                 }
 391                 if ( ds->numVerts <= 0 ) {
 392                         continue;
 393                 }
 394
 395                 /* ydnar: handle brush faces and patches first */
 396                 if ( ds->type != SURF_FACE && ds->type != SURF_PATCH ) {
 397                         continue;
 398                 }
 399
 400                 /* ydnar: this is unecessary because it should already be set */
 401                 //% VectorCopy( ds->plane.normal, ds->lightmapVecs[ 2 ] );
 402
 403                 /* search for this shader */
 404                 for ( j = 0 ; j < numSortShaders; j++ )
 405                 {
 406                         if ( ds->shaderInfo == surfsOnShader[ j ]->shaderInfo ) {
 407                                 ds->nextOnShader = surfsOnShader[ j ];
 408                                 surfsOnShader[ j ] = ds;
 409                                 break;
 410                         }
 411                 }
 412
 413                 /* new shader */
 414                 if ( j == numSortShaders ) {
 415                         if ( numSortShaders >= MAX_MAP_SHADERS ) {
 416                                 Error( "MAX_MAP_SHADERS" );
 417                         }
 418                         surfsOnShader[ j ] = ds;
 419                         ds->nextOnShader = NULL;
 420                         numSortShaders++;
 421                 }
 422         }
 423
 424         /* second pass, to allocate lightmapped terrain last */
 425         for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
 426         {
 427                 /* get surface and early out if possible */
 428                 ds = &mapDrawSurfs[ i ];
 429                 si = ds->shaderInfo;
 430                 if ( si->surfaceFlags & SURF_VERTEXLIT ) {
 431                         continue;
 432                 }
 433                 if ( ds->numVerts <= 0 ) {
 434                         continue;
 435                 }
 436
 437                 /* ydnar: this only handles metasurfaces and terrain */
 438                 if ( ds->type != SURF_TERRAIN && ds->type != SURF_META ) {
 439                         continue;
 440                 }
 441
 442                 /* ydnar: a lightmap projection should be pre-stored for anything but excessively curved patches */
 443                 if ( VectorLength( ds->lightmapAxis ) <= 0 ) {
 444                         continue;
 445                 }
 446
 447                 /* search for this shader */
 448                 for ( j = 0; j < numSortShaders; j++ )
 449                 {
 450                         if ( ds->shaderInfo == surfsOnShader[ j ]->shaderInfo ) {
 451                                 ds->nextOnShader = surfsOnShader[ j ];
 452                                 surfsOnShader[ j ] = ds;
 453                                 break;
 454                         }
 455                 }
 456
 457                 /* new shader */
 458                 if ( j == numSortShaders ) {
 459                         if ( numSortShaders >= MAX_MAP_SHADERS ) {
 460                                 Error( "MAX_MAP_SHADERS" );
 461                         }
 462                         surfsOnShader[ j ] = ds;
 463                         ds->nextOnShader = NULL;
 464                         numSortShaders++;
 465                 }
 466         }
 467
 468         /* tot up shader count */
 469         Sys_FPrintf( SYS_VRB, "%9d unique shaders\n", numSortShaders );
 470
 471         /* for each shader, allocate lightmaps for each surface */
 472         for ( i = 0; i < numSortShaders; i++ )
 473         {
 474                 si = surfsOnShader[ i ]->shaderInfo;
 475                 for ( ds = surfsOnShader[ i ]; ds; ds = ds->nextOnShader )
 476                 {
 477                         /* ydnar: promoting pointlight above nolightmap */
 478                         if ( si->surfaceFlags & SURF_POINTLIGHT ) {
 479                                 ds->lightmapNum = -3;
 480                         }
 481                         else if ( si->surfaceFlags & SURF_NOLIGHTMAP ) {
 482                                 ds->lightmapNum = -1;
 483                         }
 484                         else{
 485                                 AllocateLightmapForSurface( ds );
 486                         }
 487                 }
 488         }
 489
 490         /* emit some statistics */
 491         Sys_FPrintf( SYS_VRB, "%9d exact lightmap texels\n", c_exactLightmap );
 492         Sys_FPrintf( SYS_VRB, "%9d block lightmap texels\n", numLightmaps * LIGHTMAP_WIDTH * LIGHTMAP_HEIGHT );
 493         Sys_FPrintf( SYS_VRB, "%9d non-planar or terrain lightmap texels\n", c_nonplanarLightmap );
 494         Sys_FPrintf( SYS_VRB, "%9d planar patch lightmaps\n", c_planarPatch );
 495         Sys_FPrintf( SYS_VRB, "%9d lightmap textures, size: %d Kbytes\n", numLightmaps, ( numLightmaps * LIGHTMAP_WIDTH * LIGHTMAP_HEIGHT * 3 ) / 1024 );
 496 }