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