try to eliminate MAX_MAP_PLANES limits
[divverent/netradiant.git] / 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