better shadeangle support by jal
[divverent/netradiant.git] / tools / quake3 / q3map2 / surface.c
1 /* -------------------------------------------------------------------------------
2
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
5
6 This file is part of GtkRadiant.
7
8 GtkRadiant is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 GtkRadiant is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GtkRadiant; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
21
22 ----------------------------------------------------------------------------------
23
24 This code has been altered significantly from its original form, to support
25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26
27 ------------------------------------------------------------------------------- */
28
29
30
31 /* marker */
32 #define SURFACE_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 /*
42 AllocDrawSurface()
43 ydnar: gs mods: changed to force an explicit type when allocating
44 */
45
46 mapDrawSurface_t *AllocDrawSurface( surfaceType_t type )
47 {
48         mapDrawSurface_t        *ds;
49         
50         
51         /* ydnar: gs mods: only allocate valid types */
52         if( type <= SURFACE_BAD || type >= NUM_SURFACE_TYPES )
53                 Error( "AllocDrawSurface: Invalid surface type %d specified", type );
54         
55         /* bounds check */
56         if( numMapDrawSurfs >= MAX_MAP_DRAW_SURFS )
57                 Error( "MAX_MAP_DRAW_SURFS (%d) exceeded", MAX_MAP_DRAW_SURFS );
58         ds = &mapDrawSurfs[ numMapDrawSurfs ];
59         numMapDrawSurfs++;
60         
61         /* ydnar: do initial surface setup */
62         memset( ds, 0, sizeof( mapDrawSurface_t ) );
63         ds->type = type;
64         ds->planeNum = -1;
65         ds->fogNum = defaultFogNum;                             /* ydnar 2003-02-12 */
66         ds->outputNum = -1;                                             /* ydnar 2002-08-13 */
67         ds->surfaceNum = numMapDrawSurfs - 1;   /* ydnar 2003-02-16 */
68         
69         return ds;
70 }
71
72
73
74 /*
75 FinishSurface()
76 ydnar: general surface finish pass
77 */
78
79 void FinishSurface( mapDrawSurface_t *ds )
80 {
81         mapDrawSurface_t        *ds2;
82         
83         
84         /* dummy check */
85         if( ds->type <= SURFACE_BAD || ds->type >= NUM_SURFACE_TYPES || ds == NULL || ds->shaderInfo == NULL )
86                 return;
87         
88         /* ydnar: rocking tek-fu celshading */
89         if( ds->celShader != NULL )
90                 MakeCelSurface( ds, ds->celShader );
91         
92         /* backsides stop here */
93         if( ds->backSide )
94                 return;
95         
96         /* ydnar: rocking surface cloning (fur baby yeah!) */
97         if( ds->shaderInfo->cloneShader != NULL && ds->shaderInfo->cloneShader[ 0 ] != '\0' )
98                 CloneSurface( ds, ShaderInfoForShader( ds->shaderInfo->cloneShader ) );
99         
100         /* ydnar: q3map_backShader support */
101         if( ds->shaderInfo->backShader != NULL && ds->shaderInfo->backShader[ 0 ] != '\0' )
102         {
103                 ds2 = CloneSurface( ds, ShaderInfoForShader( ds->shaderInfo->backShader ) );
104                 ds2->backSide = qtrue;
105         }
106 }
107
108
109
110 /*
111 CloneSurface()
112 clones a map drawsurface, using the specified shader
113 */
114
115 mapDrawSurface_t *CloneSurface( mapDrawSurface_t *src, shaderInfo_t *si )
116 {
117         mapDrawSurface_t        *ds;
118         
119         
120         /* dummy check */
121         if( src == NULL || si == NULL )
122                 return NULL;
123         
124         /* allocate a new surface */
125         ds = AllocDrawSurface( src->type );
126         if( ds == NULL )
127                 return NULL;
128         
129         /* copy it */
130         memcpy( ds, src, sizeof( *ds ) );
131         
132         /* destroy side reference */
133         ds->sideRef = NULL;
134         
135         /* set shader */
136         ds->shaderInfo = si;
137         
138         /* copy verts */
139         if( ds->numVerts > 0 )
140         {
141                 ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
142                 memcpy( ds->verts, src->verts, ds->numVerts * sizeof( *ds->verts ) );
143         }
144         
145         /* copy indexes */
146         if( ds->numIndexes <= 0 )
147                 return ds;
148         ds->indexes = safe_malloc( ds->numIndexes * sizeof( *ds->indexes ) );
149         memcpy( ds->indexes, src->indexes, ds->numIndexes * sizeof( *ds->indexes ) );
150         
151         /* return the surface */
152         return ds;
153 }
154
155
156
157 /*
158 MakeCelSurface() - ydnar
159 makes a copy of a surface, but specific to cel shading
160 */
161
162 mapDrawSurface_t *MakeCelSurface( mapDrawSurface_t *src, shaderInfo_t *si )
163 {
164         mapDrawSurface_t        *ds;
165         
166         
167         /* dummy check */
168         if( src == NULL || si == NULL )
169                 return NULL;
170         
171         /* don't create cel surfaces for certain types of shaders */
172         if( (src->shaderInfo->compileFlags & C_TRANSLUCENT) ||
173                 (src->shaderInfo->compileFlags & C_SKY) )
174                 return NULL;
175         
176         /* make a copy */
177         ds = CloneSurface( src, si );
178         if( ds == NULL )
179                 return NULL;
180         
181         /* do some fixups for celshading */
182         ds->planar = qfalse;
183         ds->planeNum = -1;
184         ds->celShader = NULL; /* don't cel shade cels :P */
185         
186         /* return the surface */
187         return ds;
188 }
189
190
191
192 /*
193 MakeSkyboxSurface() - ydnar
194 generates a skybox surface, viewable from everywhere there is sky
195 */
196
197 mapDrawSurface_t *MakeSkyboxSurface( mapDrawSurface_t *src )
198 {
199         int                                     i;
200         mapDrawSurface_t        *ds;
201         
202         
203         /* dummy check */
204         if( src == NULL )
205                 return NULL;
206         
207         /* make a copy */
208         ds = CloneSurface( src, src->shaderInfo );
209         if( ds == NULL )
210                 return NULL;
211         
212         /* set parent */
213         ds->parent = src;
214         
215         /* scale the surface vertexes */
216         for( i = 0; i < ds->numVerts; i++ )
217         {
218                 m4x4_transform_point( skyboxTransform, ds->verts[ i ].xyz );
219                 
220                 /* debug code */
221                 //%     bspDrawVerts[ bspDrawSurfaces[ ds->outputNum ].firstVert + i ].color[ 0 ][ 1 ] = 0;
222                 //%     bspDrawVerts[ bspDrawSurfaces[ ds->outputNum ].firstVert + i ].color[ 0 ][ 2 ] = 0;
223         }
224         
225         /* so backface culling creep doesn't bork the surface */
226         VectorClear( ds->lightmapVecs[ 2 ] );
227         
228         /* return the surface */
229         return ds;
230 }
231
232
233
234 /*
235 IsTriangleDegenerate
236 returns qtrue if all three points are colinear, backwards, or the triangle is just plain bogus
237 */
238
239 #define TINY_AREA       1.0f
240
241 qboolean IsTriangleDegenerate( bspDrawVert_t *points, int a, int b, int c )
242 {
243         vec3_t          v1, v2, v3;
244         float           d;
245         
246         
247         /* calcuate the area of the triangle */
248         VectorSubtract( points[ b ].xyz, points[ a ].xyz, v1 );
249         VectorSubtract( points[ c ].xyz, points[ a ].xyz, v2 );
250         CrossProduct( v1, v2, v3 );
251         d = VectorLength( v3 );
252         
253         /* assume all very small or backwards triangles will cause problems */
254         if( d < TINY_AREA )
255                 return qtrue;
256         
257         /* must be a good triangle */
258         return qfalse;
259 }
260
261
262
263 /*
264 ClearSurface() - ydnar
265 clears a surface and frees any allocated memory
266 */
267
268 void ClearSurface( mapDrawSurface_t *ds )
269 {
270         ds->type = SURFACE_BAD;
271         ds->planar = qfalse;
272         ds->planeNum = -1;
273         ds->numVerts = 0;
274         if( ds->verts != NULL )
275                 free( ds->verts );
276         ds->verts = NULL;
277         ds->numIndexes = 0;
278         if( ds->indexes != NULL )
279                 free( ds->indexes );
280         ds->indexes = NULL;
281         numClearedSurfaces++;
282 }
283
284
285
286 /*
287 TidyEntitySurfaces() - ydnar
288 deletes all empty or bad surfaces from the surface list
289 */
290
291 void TidyEntitySurfaces( entity_t *e )
292 {
293         int                                     i, j, deleted;
294         mapDrawSurface_t        *out, *in;
295         
296         
297         /* note it */
298         Sys_FPrintf( SYS_VRB, "--- TidyEntitySurfaces ---\n" );
299         
300         /* walk the surface list */
301         deleted = 0;
302         for( i = e->firstDrawSurf, j = e->firstDrawSurf; j < numMapDrawSurfs; i++, j++ )
303         {
304                 /* get out surface */
305                 out = &mapDrawSurfs[ i ];
306                 
307                 /* walk the surface list again until a proper surface is found */
308                 for( ; j < numMapDrawSurfs; j++ )
309                 {
310                         /* get in surface */
311                         in = &mapDrawSurfs[ j ];
312                         
313                         /* this surface ok? */
314                         if( in->type == SURFACE_FLARE || in->type == SURFACE_SHADER ||
315                                 (in->type != SURFACE_BAD && in->numVerts > 0) )
316                                 break;
317                         
318                         /* nuke it */
319                         ClearSurface( in );
320                         deleted++;
321                 }
322                 
323                 /* copy if necessary */
324                 if( i != j )
325                         memcpy( out, in, sizeof( mapDrawSurface_t ) );
326         }
327         
328         /* set the new number of drawsurfs */
329         numMapDrawSurfs = i;
330         
331         /* emit some stats */
332         Sys_FPrintf( SYS_VRB, "%9d empty or malformed surfaces deleted\n", deleted );
333 }
334
335
336
337 /*
338 CalcSurfaceTextureRange() - ydnar
339 calculates the clamped texture range for a given surface, returns qtrue if it's within [-texRange,texRange]
340 */
341
342 qboolean CalcSurfaceTextureRange( mapDrawSurface_t *ds )
343 {
344         int             i, j, v, size[ 2 ];
345         float   mins[ 2 ], maxs[ 2 ];
346         
347         
348         /* try to early out */
349         if( ds->numVerts <= 0 )
350                 return qtrue;
351         
352         /* walk the verts and determine min/max st values */
353         mins[ 0 ] = 999999;
354         mins[ 1 ] = 999999;
355         maxs[ 0 ] = -999999;
356         maxs[ 1 ] = -999999;
357         for( i = 0; i < ds->numVerts; i++ )
358         {
359                 for( j = 0; j < 2; j++ )
360                 {
361                         if( ds->verts[ i ].st[ j ] < mins[ j ] )
362                                 mins[ j ] = ds->verts[ i ].st[ j ];
363                         if( ds->verts[ i ].st[ j ] > maxs[ j ] )
364                                 maxs[ j ] = ds->verts[ i ].st[ j ];
365                 }
366         }
367         
368         /* clamp to integer range and calculate surface bias values */
369         for( j = 0; j < 2; j++ )
370                 ds->bias[ j ] = -floor( 0.5f * (mins[ j ] + maxs[ j ]) );
371         
372         /* find biased texture coordinate mins/maxs */
373         size[ 0 ] = ds->shaderInfo->shaderWidth;
374         size[ 1 ] = ds->shaderInfo->shaderHeight;
375         ds->texMins[ 0 ] = 999999;
376         ds->texMins[ 1 ] = 999999;
377         ds->texMaxs[ 0 ] = -999999;
378         ds->texMaxs[ 1 ] = -999999;
379         for( i = 0; i < ds->numVerts; i++ )
380         {
381                 for( j = 0; j < 2; j++ )
382                 {
383                         v = ((float) ds->verts[ i ].st[ j ] + ds->bias[ j ]) * size[ j ];
384                         if( v < ds->texMins[ j ] )
385                                 ds->texMins[ j ] = v;
386                         if( v > ds->texMaxs[ j ] )
387                                 ds->texMaxs[ j ] = v;
388                 }
389         }
390         
391         /* calc ranges */
392         for( j = 0; j < 2; j++ )
393                 ds->texRange[ j ] = (ds->texMaxs[ j ] - ds->texMins[ j ]);
394         
395         /* if range is zero, then assume unlimited precision */
396         if( texRange == 0 )
397                 return qtrue;
398         
399         /* within range? */
400         for( j = 0; j < 2; j++ )
401         {
402                 if( ds->texMins[ j ] < -texRange || ds->texMaxs[ j ] > texRange )
403                         return qfalse;
404         }
405         
406         /* within range */
407         return qtrue;
408 }
409
410
411
412 /*
413 CalcLightmapAxis() - ydnar
414 gives closed lightmap axis for a plane normal
415 */
416
417 qboolean CalcLightmapAxis( vec3_t normal, vec3_t axis )
418 {
419         vec3_t  absolute;
420                 
421         
422         /* test */
423         if( normal[ 0 ] == 0.0f && normal[ 1 ] == 0.0f && normal[ 2 ] == 0.0f )
424         {
425                 VectorClear( axis );
426                 return qfalse;
427         }
428         
429         /* get absolute normal */
430         absolute[ 0 ] = fabs( normal[ 0 ] );
431         absolute[ 1 ] = fabs( normal[ 1 ] );
432         absolute[ 2 ] = fabs( normal[ 2 ] );
433         
434         /* test and set */
435         if( absolute[ 2 ] > absolute[ 0 ] - 0.0001f && absolute[ 2 ] > absolute[ 1 ] - 0.0001f )
436         {
437                 if( normal[ 2 ] > 0.0f )
438                         VectorSet( axis, 0.0f, 0.0f, 1.0f );
439                 else
440                         VectorSet( axis, 0.0f, 0.0f, -1.0f );
441         }
442         else if( absolute[ 0 ] > absolute[ 1 ] - 0.0001f && absolute[ 0 ] > absolute[ 2 ] - 0.0001f )
443         {
444                 if( normal[ 0 ] > 0.0f )
445                         VectorSet( axis, 1.0f, 0.0f, 0.0f );
446                 else
447                         VectorSet( axis, -1.0f, 0.0f, 0.0f );
448         }
449         else
450         {
451                 if( normal[ 1 ] > 0.0f )
452                         VectorSet( axis, 0.0f, 1.0f, 0.0f );
453                 else
454                         VectorSet( axis, 0.0f, -1.0f, 0.0f );
455         }
456         
457         /* return ok */
458         return qtrue;
459 }
460
461
462
463 /*
464 ClassifySurfaces() - ydnar
465 fills out a bunch of info in the surfaces, including planar status, lightmap projection, and bounding box
466 */
467
468 #define PLANAR_EPSILON  0.5f    //% 0.126f 0.25f
469
470 void ClassifySurfaces( int numSurfs, mapDrawSurface_t *ds )
471 {
472         int                                     i, bestAxis;
473         float                           dist;
474         vec4_t                          plane;
475         shaderInfo_t            *si;
476         static vec3_t           axii[ 6 ] =
477                                                 {
478                                                         { 0, 0, -1 },
479                                                         { 0, 0, 1 },
480                                                         { -1, 0, 0 },
481                                                         { 1, 0, 0 },
482                                                         { 0, -1, 0 },
483                                                         { 0, 1, 0 }
484                                                 };
485         
486         
487         /* walk the list of surfaces */
488         for( ; numSurfs > 0; numSurfs--, ds++ )
489         {
490                 /* ignore bogus (or flare) surfaces */
491                 if( ds->type == SURFACE_BAD || ds->numVerts <= 0 )
492                         continue;
493                 
494                 /* get shader */
495                 si = ds->shaderInfo;
496                 
497                 /* -----------------------------------------------------------------
498                    force meta if vertex count is too high or shader requires it
499                    ----------------------------------------------------------------- */
500                 
501                 if( ds->type != SURFACE_PATCH && ds->type != SURFACE_FACE )
502                 {
503                         if( ds->numVerts > SHADER_MAX_VERTEXES )
504                                 ds->type = SURFACE_FORCED_META;
505                 }
506                 
507                 /* -----------------------------------------------------------------
508                    plane and bounding box classification 
509                    ----------------------------------------------------------------- */
510                 
511                 /* set surface bounding box */
512                 ClearBounds( ds->mins, ds->maxs );
513                 for( i = 0; i < ds->numVerts; i++ )
514                         AddPointToBounds( ds->verts[ i ].xyz, ds->mins, ds->maxs );
515                 
516                 /* try to get an existing plane */
517                 if( ds->planeNum >= 0 )
518                 {
519                         VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
520                         plane[ 3 ] = mapplanes[ ds->planeNum ].dist;
521                 }
522                 
523                 /* construct one from the first vert with a valid normal */
524                 else
525                 {
526                         VectorClear( plane );
527                         plane[ 3 ] = 0.0f;
528                         for( i = 0; i < ds->numVerts; i++ )
529                         {
530                                 if( ds->verts[ i ].normal[ 0 ] != 0.0f && ds->verts[ i ].normal[ 1 ] != 0.0f && ds->verts[ i ].normal[ 2 ] != 0.0f )
531                                 {
532                                         VectorCopy( ds->verts[ i ].normal, plane );
533                                         plane[ 3 ] = DotProduct( ds->verts[ i ].xyz, plane );
534                                         break;
535                                 }
536                         }
537                 }
538                 
539                 /* test for bogus plane */
540                 if( VectorLength( plane ) <= 0.0f )
541                 {
542                         ds->planar = qfalse;
543                         ds->planeNum = -1;
544                 }
545                 else
546                 {
547                         /* determine if surface is planar */
548                         ds->planar = qtrue;
549                         
550                         /* test each vert */
551                         for( i = 0; i < ds->numVerts; i++ )
552                         {
553                                 /* point-plane test */
554                                 dist = DotProduct( ds->verts[ i ].xyz, plane ) - plane[ 3 ];
555                                 if( fabs( dist ) > PLANAR_EPSILON )
556                                 {
557                                         //%     if( ds->planeNum >= 0 )
558                                         //%     {
559                                         //%             Sys_Printf( "WARNING: Planar surface marked unplanar (%f > %f)\n", fabs( dist ), PLANAR_EPSILON );
560                                         //%             ds->verts[ i ].color[ 0 ][ 0 ] = ds->verts[ i ].color[ 0 ][ 2 ] = 0;
561                                         //%     }
562                                         ds->planar = qfalse;
563                                         break;
564                                 }
565                         }
566                 }
567                 
568                 /* find map plane if necessary */
569                 if( ds->planar )
570                 {
571                         if( ds->planeNum < 0 )
572                                 ds->planeNum = FindFloatPlane( plane, plane[ 3 ], 1, &ds->verts[ 0 ].xyz );
573                         VectorCopy( plane, ds->lightmapVecs[ 2 ] );
574                 }
575                 else
576                 {
577                         ds->planeNum = -1;
578                         VectorClear( ds->lightmapVecs[ 2 ] );
579                         //% if( ds->type == SURF_META || ds->type == SURF_FACE )
580                         //%             Sys_Printf( "WARNING: Non-planar face (%d): %s\n", ds->planeNum, ds->shaderInfo->shader );
581                 }
582                 
583                 /* -----------------------------------------------------------------
584                    lightmap bounds and axis projection
585                    ----------------------------------------------------------------- */
586                 
587                 /* vertex lit surfaces don't need this information */
588                 if( si->compileFlags & C_VERTEXLIT || ds->type == SURFACE_TRIANGLES )
589                 {
590                         VectorClear( ds->lightmapAxis );
591                         //%     VectorClear( ds->lightmapVecs[ 2 ] );
592                         ds->sampleSize = 0;
593                         continue;
594                 }
595                 
596                 /* the shader can specify an explicit lightmap axis */
597                 if( si->lightmapAxis[ 0 ] || si->lightmapAxis[ 1 ] || si->lightmapAxis[ 2 ] )
598                         VectorCopy( si->lightmapAxis, ds->lightmapAxis );
599                 else if( ds->type == SURFACE_FORCED_META )
600                         VectorClear( ds->lightmapAxis );
601                 else if( ds->planar )
602                         CalcLightmapAxis( plane, ds->lightmapAxis );
603                 else
604                 {
605                         /* find best lightmap axis */
606                         for( bestAxis = 0; bestAxis < 6; bestAxis++ )
607                         {
608                                 for( i = 0; i < ds->numVerts && bestAxis < 6; i++ )
609                                 {
610                                         //% Sys_Printf( "Comparing %1.3f %1.3f %1.3f to %1.3f %1.3f %1.3f\n",
611                                         //%     ds->verts[ i ].normal[ 0 ], ds->verts[ i ].normal[ 1 ], ds->verts[ i ].normal[ 2 ],
612                                         //%     axii[ bestAxis ][ 0 ], axii[ bestAxis ][ 1 ], axii[ bestAxis ][ 2 ] );
613                                         if( DotProduct( ds->verts[ i ].normal, axii[ bestAxis ] ) < 0.25f )     /* fixme: adjust this tolerance to taste */
614                                                 break;
615                                 }
616                                 
617                                 if( i == ds->numVerts )
618                                         break;
619                         }
620                         
621                         /* set axis if possible */
622                         if( bestAxis < 6 )
623                         {
624                                 //% if( ds->type == SURFACE_PATCH )
625                                 //%     Sys_Printf( "Mapped axis %d onto patch\n", bestAxis );
626                                 VectorCopy( axii[ bestAxis ], ds->lightmapAxis );
627                         }
628                         
629                         /* debug code */
630                         //% if( ds->type == SURFACE_PATCH )
631                         //%     Sys_Printf( "Failed to map axis %d onto patch\n", bestAxis );
632                 }
633                 
634                 /* get lightmap sample size */
635                 if( ds->sampleSize <= 0 )
636                 {
637                         ds->sampleSize = sampleSize;
638                         if( ds->shaderInfo->lightmapSampleSize )
639                                 ds->sampleSize = ds->shaderInfo->lightmapSampleSize;
640                         if( ds->lightmapScale > 0 )
641                                 ds->sampleSize *= ds->lightmapScale;
642                         if( ds->sampleSize <= 0 )
643                                 ds->sampleSize = 1;
644                         if(ds->sampleSize < minSampleSize)
645                                 ds->sampleSize = minSampleSize;
646                         if( ds->sampleSize > 16384 )    /* powers of 2 are preferred */
647                                 ds->sampleSize = 16384;
648                 }
649         }
650 }
651
652
653
654 /*
655 ClassifyEntitySurfaces() - ydnar
656 classifies all surfaces in an entity
657 */
658
659 void ClassifyEntitySurfaces( entity_t *e )
660 {
661         int             i;
662         
663         
664         /* note it */
665         Sys_FPrintf( SYS_VRB, "--- ClassifyEntitySurfaces ---\n" );
666         
667         /* walk the surface list */
668         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
669         {
670                 FinishSurface( &mapDrawSurfs[ i ] );
671                 ClassifySurfaces( 1, &mapDrawSurfs[ i ] );
672         }
673         
674         /* tidy things up */
675         TidyEntitySurfaces( e );
676 }
677
678
679
680 /*
681 GetShaderIndexForPoint() - ydnar
682 for shader-indexed surfaces (terrain), find a matching index from the indexmap
683 */
684
685 byte GetShaderIndexForPoint( indexMap_t *im, vec3_t eMins, vec3_t eMaxs, vec3_t point )
686 {
687         int                     i, x, y;
688         float           s, t;
689         vec3_t          mins, maxs, size;
690         
691         
692         /* early out if no indexmap */
693         if( im == NULL )
694                 return 0;
695         
696         /* this code is really broken */
697         #if 0
698                 /* legacy precision fudges for terrain */
699                 for( i = 0; i < 3; i++ )
700                 {
701                         mins[ i ] = floor( eMins[ i ] + 0.1 );
702                         maxs[ i ] = floor( eMaxs[ i ] + 0.1 );
703                         size[ i ] = maxs[ i ] - mins[ i ];
704                 }
705                 
706                 /* find st (fixme: support more than just z-axis projection) */
707                 s = floor( point[ 0 ] + 0.1f - mins[ 0 ] ) / size[ 0 ];
708                 t = floor( maxs[ 1 ] - point[ 1 ] + 0.1f ) / size[ 1 ];
709                 if( s < 0.0f )
710                         s = 0.0f;
711                 else if( s > 1.0f )
712                         s = 1.0f;
713                 if( t < 0.0f )
714                         t = 0.0f;
715                 else if( t > 1.0f )
716                         t = 1.0f;
717                 
718                 /* make xy */
719                 x = (im->w - 1) * s;
720                 y = (im->h - 1) * t;
721         #else
722                 /* get size */
723                 for( i = 0; i < 3; i++ )
724                 {
725                         mins[ i ] = eMins[ i ];
726                         maxs[ i ] = eMaxs[ i ];
727                         size[ i ] = maxs[ i ] - mins[ i ];
728                 }
729                 
730                 /* calc st */
731                 s = (point[ 0 ] - mins[ 0 ]) / size[ 0 ];
732                 t = (maxs[ 1 ] - point[ 1 ]) / size[ 1 ];
733                 
734                 /* calc xy */
735                 x = s * im->w;
736                 y = t * im->h;
737                 if( x < 0 )
738                         x = 0;
739                 else if( x > (im->w - 1) )
740                         x = (im->w - 1);
741                 if( y < 0 )
742                         y = 0;
743                 else if( y > (im->h - 1) )
744                         y = (im->h - 1);
745         #endif
746         
747         /* return index */
748         return im->pixels[ y * im->w + x ];
749 }
750
751
752
753 /*
754 GetIndexedShader() - ydnar
755 for a given set of indexes and an indexmap, get a shader and set the vertex alpha in-place
756 this combines a couple different functions from terrain.c
757 */
758
759 shaderInfo_t *GetIndexedShader( shaderInfo_t *parent, indexMap_t *im, int numPoints, byte *shaderIndexes )
760 {
761         int                             i;
762         byte                    minShaderIndex, maxShaderIndex;
763         char                    shader[ MAX_QPATH ];
764         shaderInfo_t    *si;
765         
766         
767         /* early out if bad data */
768         if( im == NULL || numPoints <= 0 || shaderIndexes == NULL )
769                 return ShaderInfoForShader( "default" );
770         
771         /* determine min/max index */
772         minShaderIndex = 255;
773         maxShaderIndex = 0;
774         for( i = 0; i < numPoints; i++ )
775         {
776                 if( shaderIndexes[ i ] < minShaderIndex )
777                         minShaderIndex = shaderIndexes[ i ];
778                 if( shaderIndexes[ i ] > maxShaderIndex )
779                         maxShaderIndex = shaderIndexes[ i ];
780         }
781         
782         /* set alpha inline */
783         for( i = 0; i < numPoints; i++ )
784         {
785                 /* straight rip from terrain.c */
786                 if( shaderIndexes[ i ] < maxShaderIndex )
787                         shaderIndexes[ i ] = 0;
788                 else
789                         shaderIndexes[ i ] = 255;
790         }
791         
792         /* make a shader name */
793         if( minShaderIndex == maxShaderIndex )
794                 sprintf( shader, "textures/%s_%d", im->shader, maxShaderIndex );
795         else
796                 sprintf( shader, "textures/%s_%dto%d", im->shader, minShaderIndex, maxShaderIndex );
797         
798         /* get the shader */
799         si = ShaderInfoForShader( shader );
800         
801         /* inherit a few things from parent shader */
802         if( parent->globalTexture )
803                 si->globalTexture = qtrue;
804         if( parent->forceMeta )
805                 si->forceMeta = qtrue;
806         if( parent->nonplanar )
807                 si->nonplanar = qtrue;
808         if( si->shadeAngleDegrees == 0.0 )
809                 si->shadeAngleDegrees = parent->shadeAngleDegrees;
810         if( parent->tcGen && si->tcGen == qfalse )
811         {
812                 /* set xy texture projection */
813                 si->tcGen = qtrue;
814                 VectorCopy( parent->vecs[ 0 ], si->vecs[ 0 ] );
815                 VectorCopy( parent->vecs[ 1 ], si->vecs[ 1 ] );
816         }
817         if( VectorLength( parent->lightmapAxis ) > 0.0f && VectorLength( si->lightmapAxis ) <= 0.0f )
818         {
819                 /* set lightmap projection axis */
820                 VectorCopy( parent->lightmapAxis, si->lightmapAxis );
821         }
822         
823         /* return the shader */
824         return si;
825 }
826
827
828
829
830 /*
831 DrawSurfaceForSide()
832 creates a SURF_FACE drawsurface from a given brush side and winding
833 */
834
835 #define SNAP_FLOAT_TO_INT       8
836 #define SNAP_INT_TO_FLOAT       (1.0 / SNAP_FLOAT_TO_INT)
837
838 mapDrawSurface_t *DrawSurfaceForSide( entity_t *e, brush_t *b, side_t *s, winding_t *w )
839 {
840         int                                     i, j, k;
841         mapDrawSurface_t        *ds;
842         shaderInfo_t            *si, *parent;
843         bspDrawVert_t           *dv;
844         vec3_t                          texX, texY;
845         vec_t                           x, y;
846         vec3_t                          vTranslated;
847         qboolean                        indexed;
848         byte                            shaderIndexes[ 256 ];
849         float                           offsets[ 256 ];
850         char                            tempShader[ MAX_QPATH ];
851
852         
853         /* ydnar: don't make a drawsurf for culled sides */
854         if( s->culled )
855                 return NULL;
856         
857         /* range check */
858         if( w->numpoints > MAX_POINTS_ON_WINDING )
859                 Error( "DrawSurfaceForSide: w->numpoints = %d (> %d)", w->numpoints, MAX_POINTS_ON_WINDING );
860         
861         /* get shader */
862         si = s->shaderInfo;
863         
864         /* ydnar: gs mods: check for indexed shader */
865         if( si->indexed && b->im != NULL )
866         {
867                 /* indexed */
868                 indexed = qtrue;
869                 
870                 /* get shader indexes for each point */
871                 for( i = 0; i < w->numpoints; i++ )
872                 {
873                         shaderIndexes[ i ] = GetShaderIndexForPoint( b->im, b->eMins, b->eMaxs, w->p[ i ] );
874                         offsets[ i ] = b->im->offsets[ shaderIndexes[ i ] ];
875                         //%     Sys_Printf( "%f ", offsets[ i ] );
876                 }
877                 
878                 /* get matching shader and set alpha */
879                 parent = si;
880                 si = GetIndexedShader( parent, b->im, w->numpoints, shaderIndexes );
881         }
882         else
883                 indexed = qfalse;
884         
885         /* ydnar: sky hack/fix for GL_CLAMP borders on ati cards */
886         if( skyFixHack && si->skyParmsImageBase[ 0 ] != '\0' )
887         {
888                 //%     Sys_FPrintf( SYS_VRB, "Enabling sky hack for shader %s using env %s\n", si->shader, si->skyParmsImageBase );
889                 sprintf( tempShader, "%s_lf", si->skyParmsImageBase );
890                 DrawSurfaceForShader( tempShader );
891                 sprintf( tempShader, "%s_rt", si->skyParmsImageBase );
892                 DrawSurfaceForShader( tempShader );
893                 sprintf( tempShader, "%s_ft", si->skyParmsImageBase );
894                 DrawSurfaceForShader( tempShader );
895                 sprintf( tempShader, "%s_bk", si->skyParmsImageBase );
896                 DrawSurfaceForShader( tempShader );
897                 sprintf( tempShader, "%s_up", si->skyParmsImageBase );
898                 DrawSurfaceForShader( tempShader );
899                 sprintf( tempShader, "%s_dn", si->skyParmsImageBase );
900                 DrawSurfaceForShader( tempShader );
901         }
902         
903         /* ydnar: gs mods */
904         ds = AllocDrawSurface( SURFACE_FACE );
905         ds->entityNum = b->entityNum;
906         ds->castShadows = b->castShadows;
907         ds->recvShadows = b->recvShadows;
908         
909         ds->planar = qtrue;
910         ds->planeNum = s->planenum;
911         VectorCopy( mapplanes[ s->planenum ].normal, ds->lightmapVecs[ 2 ] );
912         
913         ds->shaderInfo = si;
914         ds->mapBrush = b;
915         ds->sideRef = AllocSideRef( s, NULL );
916         ds->fogNum = -1;
917         ds->lightmapScale = b->lightmapScale;
918         ds->numVerts = w->numpoints;
919         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
920         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
921         
922         /* compute s/t coordinates from brush primitive texture matrix (compute axis base) */
923         ComputeAxisBase( mapplanes[ s->planenum ].normal, texX, texY );
924         
925         /* create the vertexes */
926         for( j = 0; j < w->numpoints; j++ )
927         {
928                 /* get the drawvert */
929                 dv = ds->verts + j;
930                 
931                 /* copy xyz and do potential z offset */
932                 VectorCopy( w->p[ j ], dv->xyz );
933                 if( indexed )
934                         dv->xyz[ 2 ] += offsets[ j ];
935                 
936                 /* round the xyz to a given precision and translate by origin */
937                 for( i = 0 ; i < 3 ; i++ )
938                         dv->xyz[ i ] = SNAP_INT_TO_FLOAT * floor( dv->xyz[ i ] * SNAP_FLOAT_TO_INT + 0.5f );
939                 VectorAdd( dv->xyz, e->origin, vTranslated );
940                 
941                 /* ydnar: tek-fu celshading support for flat shaded shit */
942                 if( flat )
943                 {
944                         dv->st[ 0 ] = si->stFlat[ 0 ];
945                         dv->st[ 1 ] = si->stFlat[ 1 ];
946                 }
947                 
948                 /* ydnar: gs mods: added support for explicit shader texcoord generation */
949                 else if( si->tcGen )
950                 {
951                         dv->st[ 0 ] = DotProduct( si->vecs[ 0 ], vTranslated );
952                         dv->st[ 1 ] = DotProduct( si->vecs[ 1 ], vTranslated );
953                 }
954                 
955                 /* old quake-style texturing */
956                 else if( g_bBrushPrimit == BPRIMIT_OLDBRUSHES )
957                 {
958                         /* nearest-axial projection */
959                         dv->st[ 0 ] = s->vecs[ 0 ][ 3 ] + DotProduct( s->vecs[ 0 ], vTranslated );
960                         dv->st[ 1 ] = s->vecs[ 1 ][ 3 ] + DotProduct( s->vecs[ 1 ], vTranslated );
961                         dv->st[ 0 ] /= si->shaderWidth;
962                         dv->st[ 1 ] /= si->shaderHeight;
963                 }
964                 
965                 /* brush primitive texturing */
966                 else
967                 {
968                         /* calculate texture s/t from brush primitive texture matrix */
969                         x = DotProduct( vTranslated, texX );
970                         y = DotProduct( vTranslated, texY );
971                         dv->st[ 0 ] = s->texMat[ 0 ][ 0 ] * x + s->texMat[ 0 ][ 1 ] * y + s->texMat[ 0 ][ 2 ];
972                         dv->st[ 1 ] = s->texMat[ 1 ][ 0 ] * x + s->texMat[ 1 ][ 1 ] * y + s->texMat[ 1 ][ 2 ];
973                 }
974                 
975                 /* copy normal */
976                 VectorCopy( mapplanes[ s->planenum ].normal, dv->normal );
977                 
978                 /* ydnar: set color */
979                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
980                 {
981                         dv->color[ k ][ 0 ] = 255;
982                         dv->color[ k ][ 1 ] = 255;
983                         dv->color[ k ][ 2 ] = 255;
984                         
985                         /* ydnar: gs mods: handle indexed shader blending */
986                         dv->color[ k ][ 3 ] = (indexed ? shaderIndexes[ j ] : 255);
987                 }
988         }
989         
990         /* set cel shader */
991         ds->celShader = b->celShader;
992
993         /* set shade angle */
994         if( si->shadeAngleDegrees )
995                 ds->shadeAngleDegrees = ds->shadeAngleDegrees;
996         else
997                 ds->shadeAngleDegrees = b->shadeAngleDegrees; /* otherwise it's 0 */
998         
999         /* ydnar: gs mods: moved st biasing elsewhere */
1000         return ds;
1001 }
1002
1003
1004
1005 /*
1006 DrawSurfaceForMesh()
1007 moved here from patch.c
1008 */
1009
1010 #define YDNAR_NORMAL_EPSILON 0.50f
1011
1012 qboolean VectorCompareExt( vec3_t n1, vec3_t n2, float epsilon )
1013 {
1014         int             i;
1015         
1016         
1017         /* test */
1018         for( i= 0; i < 3; i++ )
1019                 if( fabs( n1[ i ] - n2[ i ]) > epsilon )
1020                         return qfalse;
1021         return qtrue;
1022 }
1023
1024 mapDrawSurface_t *DrawSurfaceForMesh( entity_t *e, parseMesh_t *p, mesh_t *mesh )
1025 {
1026         int                                     i, k, numVerts;
1027         vec4_t                          plane;
1028         qboolean                        planar;
1029         float                           dist;
1030         mapDrawSurface_t        *ds;
1031         shaderInfo_t            *si, *parent;
1032         bspDrawVert_t           *dv;
1033         vec3_t                          vTranslated;
1034         mesh_t                          *copy;
1035         qboolean                        indexed;
1036         byte                            shaderIndexes[ MAX_EXPANDED_AXIS * MAX_EXPANDED_AXIS ];
1037         float                           offsets[ MAX_EXPANDED_AXIS * MAX_EXPANDED_AXIS ];
1038         
1039         
1040         /* get mesh and shader shader */
1041         if( mesh == NULL )
1042                 mesh = &p->mesh;
1043         si = p->shaderInfo;
1044         if( mesh == NULL || si == NULL )
1045                 return NULL;
1046         
1047         /* get vertex count */
1048         numVerts = mesh->width * mesh->height;
1049         
1050         /* to make valid normals for patches with degenerate edges,
1051            we need to make a copy of the mesh and put the aproximating
1052            points onto the curve */
1053         
1054         /* create a copy of the mesh */
1055         copy = CopyMesh( mesh );
1056         
1057         /* store off the original (potentially bad) normals */
1058         MakeMeshNormals( *copy );
1059         for( i = 0; i < numVerts; i++ )
1060                 VectorCopy( copy->verts[ i ].normal, mesh->verts[ i ].normal );
1061         
1062         /* put the mesh on the curve */
1063         PutMeshOnCurve( *copy );
1064
1065         /* find new normals (to take into account degenerate/flipped edges */
1066         MakeMeshNormals( *copy );
1067         for( i = 0; i < numVerts; i++ )
1068         {
1069                 /* ydnar: only copy normals that are significantly different from the originals */
1070                 if( DotProduct( copy->verts[ i ].normal, mesh->verts[ i ].normal ) < 0.75f )
1071                         VectorCopy( copy->verts[ i ].normal, mesh->verts[ i ].normal );
1072         }
1073         
1074         /* free the old mesh */
1075         FreeMesh( copy );
1076         
1077         /* ydnar: gs mods: check for indexed shader */
1078         if( si->indexed && p->im != NULL )
1079         {
1080                 /* indexed */
1081                 indexed = qtrue;
1082
1083                 /* get shader indexes for each point */
1084                 for( i = 0; i < numVerts; i++ )
1085                 {
1086                         shaderIndexes[ i ] = GetShaderIndexForPoint( p->im, p->eMins, p->eMaxs, mesh->verts[ i ].xyz );
1087                         offsets[ i ] = p->im->offsets[ shaderIndexes[ i ] ];
1088                 }
1089                 
1090                 /* get matching shader and set alpha */
1091                 parent = si;
1092                 si = GetIndexedShader( parent, p->im, numVerts, shaderIndexes );
1093         }
1094         else
1095                 indexed = qfalse;
1096         
1097         
1098         /* ydnar: gs mods */
1099         ds = AllocDrawSurface( SURFACE_PATCH );
1100         ds->entityNum = p->entityNum;
1101         ds->castShadows = p->castShadows;
1102         ds->recvShadows = p->recvShadows;
1103         
1104         ds->shaderInfo = si;
1105         ds->mapMesh = p;
1106         ds->lightmapScale = p->lightmapScale;   /* ydnar */
1107         ds->patchWidth = mesh->width;
1108         ds->patchHeight = mesh->height;
1109         ds->numVerts = ds->patchWidth * ds->patchHeight;
1110         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
1111         memcpy( ds->verts, mesh->verts, ds->numVerts * sizeof( *ds->verts ) );
1112         
1113         ds->fogNum = -1;
1114         ds->planeNum = -1;
1115         
1116         ds->longestCurve = p->longestCurve;
1117         ds->maxIterations = p->maxIterations;
1118         
1119         /* construct a plane from the first vert */
1120         VectorCopy( mesh->verts[ 0 ].normal, plane );
1121         plane[ 3 ] = DotProduct( mesh->verts[ 0 ].xyz, plane );
1122         planar = qtrue;
1123         
1124         /* spew forth errors */
1125         if( VectorLength( plane ) < 0.001f )
1126                 Sys_Printf( "BOGUS " );
1127         
1128         /* test each vert */
1129         for( i = 1; i < ds->numVerts && planar; i++ )
1130         {
1131                 /* normal test */
1132                 if( VectorCompare( plane, mesh->verts[ i ].normal ) == qfalse )
1133                         planar = qfalse;
1134                 
1135                 /* point-plane test */
1136                 dist = DotProduct( mesh->verts[ i ].xyz, plane ) - plane[ 3 ];
1137                 if( fabs( dist ) > EQUAL_EPSILON )
1138                         planar = qfalse;
1139         }
1140         
1141         /* add a map plane */
1142         if( planar )
1143         {
1144                 /* make a map plane */
1145                 ds->planeNum = FindFloatPlane( plane, plane[ 3 ], 1, &mesh->verts[ 0 ].xyz );
1146                 VectorCopy( plane, ds->lightmapVecs[ 2 ] );
1147                 
1148                 /* push this normal to all verts (ydnar 2003-02-14: bad idea, small patches get screwed up) */
1149                 for( i = 0; i < ds->numVerts; i++ )
1150                         VectorCopy( plane, ds->verts[ i ].normal );
1151         }
1152         
1153         /* walk the verts to do special stuff */
1154         for( i = 0; i < ds->numVerts; i++ )
1155         {
1156                 /* get the drawvert */
1157                 dv = &ds->verts[ i ];
1158                 
1159                 /* ydnar: tek-fu celshading support for flat shaded shit */
1160                 if( flat )
1161                 {
1162                         dv->st[ 0 ] = si->stFlat[ 0 ];
1163                         dv->st[ 1 ] = si->stFlat[ 1 ];
1164                 }
1165                 
1166                 /* ydnar: gs mods: added support for explicit shader texcoord generation */
1167                 else if( si->tcGen )
1168                 {
1169                         /* translate by origin and project the texture */
1170                         VectorAdd( dv->xyz, e->origin, vTranslated );
1171                         dv->st[ 0 ] = DotProduct( si->vecs[ 0 ], vTranslated );
1172                         dv->st[ 1 ] = DotProduct( si->vecs[ 1 ], vTranslated );
1173                 }
1174                 
1175                 /* ydnar: set color */
1176                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
1177                 {
1178                         dv->color[ k ][ 0 ] = 255;
1179                         dv->color[ k ][ 1 ] = 255;
1180                         dv->color[ k ][ 2 ] = 255;
1181                         
1182                         /* ydnar: gs mods: handle indexed shader blending */
1183                         dv->color[ k ][ 3 ] = (indexed ? shaderIndexes[ i ] : 255);
1184                 }
1185                 
1186                 /* ydnar: offset */
1187                 if( indexed )
1188                         dv->xyz[ 2 ] += offsets[ i ];
1189         }
1190         
1191         /* set cel shader */
1192         ds->celShader = p->celShader;
1193         
1194         /* return the drawsurface */
1195         return ds;
1196 }
1197
1198
1199
1200 /*
1201 DrawSurfaceForFlare() - ydnar
1202 creates a flare draw surface
1203 */
1204
1205 mapDrawSurface_t *DrawSurfaceForFlare( int entNum, vec3_t origin, vec3_t normal, vec3_t color, char *flareShader, int lightStyle )
1206 {
1207         mapDrawSurface_t        *ds;
1208         
1209         
1210         /* emit flares? */
1211         if( emitFlares == qfalse )
1212                 return NULL;
1213         
1214         /* allocate drawsurface */
1215         ds = AllocDrawSurface( SURFACE_FLARE );
1216         ds->entityNum = entNum;
1217         
1218         /* set it up */
1219         if( flareShader != NULL && flareShader[ 0 ] != '\0' )
1220                 ds->shaderInfo = ShaderInfoForShader( flareShader );
1221         else
1222                 ds->shaderInfo = ShaderInfoForShader( game->flareShader );
1223         if( origin != NULL )
1224                 VectorCopy( origin, ds->lightmapOrigin );
1225         if( normal != NULL )
1226                 VectorCopy( normal, ds->lightmapVecs[ 2 ] );
1227         if( color != NULL )
1228                 VectorCopy( color, ds->lightmapVecs[ 0 ] );
1229         
1230         /* store light style */
1231         ds->lightStyle = lightStyle;
1232         if( ds->lightStyle < 0 || ds->lightStyle >= LS_NONE )
1233                 ds->lightStyle = LS_NORMAL;
1234         
1235         /* fixme: fog */
1236         
1237         /* return to sender */
1238         return ds;
1239 }
1240
1241
1242
1243 /*
1244 DrawSurfaceForShader() - ydnar
1245 creates a bogus surface to forcing the game to load a shader
1246 */
1247
1248 mapDrawSurface_t *DrawSurfaceForShader( char *shader )
1249 {
1250         int                                     i;
1251         shaderInfo_t            *si;
1252         mapDrawSurface_t        *ds;
1253         
1254         
1255         /* get shader */
1256         si = ShaderInfoForShader( shader );
1257
1258         /* find existing surface */
1259         for( i = 0; i < numMapDrawSurfs; i++ )
1260         {
1261                 /* get surface */
1262                 ds = &mapDrawSurfs[ i ];
1263                 
1264                 /* check it */
1265                 if( ds->shaderInfo == si )
1266                         return ds;
1267         }
1268         
1269         /* create a new surface */
1270         ds = AllocDrawSurface( SURFACE_SHADER );
1271         ds->entityNum = 0;
1272         ds->shaderInfo = ShaderInfoForShader( shader );
1273         
1274         /* return to sender */
1275         return ds;
1276 }
1277
1278
1279
1280 /*
1281 AddSurfaceFlare() - ydnar
1282 creates flares (coronas) centered on surfaces
1283 */
1284
1285 static void AddSurfaceFlare( mapDrawSurface_t *ds, vec3_t entityOrigin )
1286 {
1287         vec3_t                          origin;
1288         int                                     i;
1289         
1290         
1291         /* find centroid */
1292         VectorClear( origin );
1293         for ( i = 0; i < ds->numVerts; i++ )
1294                 VectorAdd( origin, ds->verts[ i ].xyz, origin );
1295         VectorScale( origin, (1.0f / ds->numVerts), origin );
1296         if( entityOrigin != NULL )
1297                 VectorAdd( origin, entityOrigin, origin );
1298         
1299         /* push origin off surface a bit */
1300         VectorMA( origin, 2.0f,  ds->lightmapVecs[ 2 ], origin );
1301         
1302         /* create the drawsurface */
1303         DrawSurfaceForFlare( ds->entityNum, origin, ds->lightmapVecs[ 2 ], ds->shaderInfo->color, ds->shaderInfo->flareShader, ds->shaderInfo->lightStyle );
1304 }
1305
1306
1307
1308 /*
1309 SubdivideFace()
1310 subdivides a face surface until it is smaller than the specified size (subdivisions)
1311 */
1312
1313 static void SubdivideFace_r( entity_t *e, brush_t *brush, side_t *side, winding_t *w, int fogNum, float subdivisions )
1314 {
1315         int                                     i;
1316         int                                     axis;
1317         vec3_t                          bounds[ 2 ];
1318         const float                     epsilon = 0.1;
1319         int                                     subFloor, subCeil;
1320         winding_t                       *frontWinding, *backWinding;
1321         mapDrawSurface_t        *ds;
1322         
1323         
1324         /* dummy check */
1325         if( w == NULL )
1326                 return;
1327         if( w->numpoints < 3 )
1328                 Error( "SubdivideFace_r: Bad w->numpoints (%d < 3)", w->numpoints );
1329         
1330         /* determine surface bounds */
1331         ClearBounds( bounds[ 0 ], bounds[ 1 ] );
1332         for( i = 0; i < w->numpoints; i++ )
1333                 AddPointToBounds( w->p[ i ], bounds[ 0 ], bounds[ 1 ] );
1334         
1335         /* split the face */
1336         for( axis = 0; axis < 3; axis++ )
1337         {
1338                 vec3_t                  planePoint = { 0, 0, 0 };
1339                 vec3_t                  planeNormal = { 0, 0, 0 };
1340                 float                   d;
1341                 
1342                 
1343                 /* create an axial clipping plane */
1344                 subFloor = floor( bounds[ 0 ][ axis ] / subdivisions) * subdivisions;
1345                 subCeil = ceil( bounds[ 1 ][ axis ] / subdivisions) * subdivisions;
1346                 planePoint[ axis ] = subFloor + subdivisions;
1347                 planeNormal[ axis ] = -1;
1348                 d = DotProduct( planePoint, planeNormal );
1349
1350                 /* subdivide if necessary */
1351                 if( (subCeil - subFloor) > subdivisions )
1352                 {
1353                         /* clip the winding */
1354                         ClipWindingEpsilon( w, planeNormal, d, epsilon, &frontWinding, &backWinding );
1355
1356                         /* the clip may not produce two polygons if it was epsilon close */
1357                         if( frontWinding == NULL )
1358                                 w = backWinding;
1359                         else if( backWinding == NULL )
1360                                 w = frontWinding;
1361                         else
1362                         {
1363                                 SubdivideFace_r( e, brush, side, frontWinding, fogNum, subdivisions );
1364                                 SubdivideFace_r( e, brush, side, backWinding, fogNum, subdivisions );
1365                                 return;
1366                         }
1367                 }
1368         }
1369         
1370         /* create a face surface */
1371         ds = DrawSurfaceForSide( e, brush, side, w );
1372         
1373         /* set correct fog num */
1374         ds->fogNum = fogNum;
1375 }
1376
1377
1378
1379 /*
1380 SubdivideFaceSurfaces()
1381 chop up brush face surfaces that have subdivision attributes
1382 ydnar: and subdivide surfaces that exceed specified texture coordinate range
1383 */
1384
1385 void SubdivideFaceSurfaces( entity_t *e, tree_t *tree )
1386 {
1387         int                                     i, j, numBaseDrawSurfs, fogNum;
1388         mapDrawSurface_t        *ds;
1389         brush_t                         *brush;
1390         side_t                          *side;
1391         shaderInfo_t            *si;
1392         winding_t                       *w;
1393         float                           range, size, subdivisions, s2;
1394         
1395         
1396         /* note it */
1397         Sys_FPrintf( SYS_VRB, "--- SubdivideFaceSurfaces ---\n" );
1398         
1399         /* walk the list of surfaces */
1400         numBaseDrawSurfs = numMapDrawSurfs;
1401         for( i = e->firstDrawSurf; i < numBaseDrawSurfs; i++ )
1402         {
1403                 /* get surface */
1404                 ds = &mapDrawSurfs[ i ];
1405
1406                 /* only subdivide brush sides */
1407                 if( ds->type != SURFACE_FACE || ds->mapBrush == NULL || ds->sideRef == NULL || ds->sideRef->side == NULL )
1408                         continue;
1409                 
1410                 /* get bits */
1411                 brush = ds->mapBrush;
1412                 side = ds->sideRef->side;
1413                 
1414                 /* check subdivision for shader */
1415                 si = side->shaderInfo;
1416                 if( si == NULL )
1417                         continue;
1418                 
1419                 /* ydnar: don't subdivide sky surfaces */
1420                 if( si->compileFlags & C_SKY )
1421                         continue;
1422                 
1423                 /* do texture coordinate range check */
1424                 ClassifySurfaces( 1, ds );
1425                 if( CalcSurfaceTextureRange( ds ) == qfalse )
1426                 {
1427                         /* calculate subdivisions texture range (this code is shit) */
1428                         range = (ds->texRange[ 0 ] > ds->texRange[ 1 ] ? ds->texRange[ 0 ] : ds->texRange[ 1 ]);
1429                         size = ds->maxs[ 0 ] - ds->mins[ 0 ];
1430                         for( j = 1; j < 3; j++ )
1431                                 if( (ds->maxs[ j ] - ds->mins[ j ]) > size )
1432                                         size = ds->maxs[ j ] - ds->mins[ j ];
1433                         subdivisions = (size / range) * texRange;
1434                         subdivisions = ceil( subdivisions / 2 ) * 2;
1435                         for( j = 1; j < 8; j++ )
1436                         {
1437                                 s2 = ceil( (float) texRange / j );
1438                                 if( fabs( subdivisions - s2 ) <= 4.0 )
1439                                 {
1440                                         subdivisions = s2;
1441                                         break;
1442                                 }
1443                         }
1444                 }
1445                 else
1446                         subdivisions = si->subdivisions;
1447                 
1448                 /* get subdivisions from shader */
1449                 if(     si->subdivisions > 0 && si->subdivisions < subdivisions )
1450                         subdivisions = si->subdivisions;
1451                 if( subdivisions < 1.0f )
1452                         continue;
1453                 
1454                 /* preserve fog num */
1455                 fogNum = ds->fogNum;
1456                 
1457                 /* make a winding and free the surface */
1458                 w = WindingFromDrawSurf( ds );
1459                 ClearSurface( ds );
1460                 
1461                 /* subdivide it */
1462                 SubdivideFace_r( e, brush, side, w, fogNum, subdivisions );
1463         }
1464 }
1465
1466
1467
1468 /*
1469 ====================
1470 ClipSideIntoTree_r
1471
1472 Adds non-opaque leaf fragments to the convex hull
1473 ====================
1474 */
1475
1476 void ClipSideIntoTree_r( winding_t *w, side_t *side, node_t *node )
1477 {
1478         plane_t                 *plane;
1479         winding_t               *front, *back;
1480
1481         if ( !w ) {
1482                 return;
1483         }
1484
1485         if ( node->planenum != PLANENUM_LEAF ) {
1486                 if ( side->planenum == node->planenum ) {
1487                         ClipSideIntoTree_r( w, side, node->children[0] );
1488                         return;
1489                 }
1490                 if ( side->planenum == ( node->planenum ^ 1) ) {
1491                         ClipSideIntoTree_r( w, side, node->children[1] );
1492                         return;
1493                 }
1494
1495                 plane = &mapplanes[ node->planenum ];
1496                 ClipWindingEpsilon ( w, plane->normal, plane->dist,
1497                                 ON_EPSILON, &front, &back );
1498                 FreeWinding( w );
1499
1500                 ClipSideIntoTree_r( front, side, node->children[0] );
1501                 ClipSideIntoTree_r( back, side, node->children[1] );
1502
1503                 return;
1504         }
1505
1506         // if opaque leaf, don't add
1507         if ( !node->opaque ) {
1508                 AddWindingToConvexHull( w, &side->visibleHull, mapplanes[ side->planenum ].normal );
1509         }
1510
1511         FreeWinding( w );
1512         return;
1513 }
1514
1515
1516
1517
1518
1519 static int g_numHiddenFaces, g_numCoinFaces;
1520
1521
1522
1523 /*
1524 CullVectorCompare() - ydnar
1525 compares two vectors with an epsilon
1526 */
1527
1528 #define CULL_EPSILON 0.1f
1529
1530 qboolean CullVectorCompare( const vec3_t v1, const vec3_t v2 )
1531 {
1532         int             i;
1533         
1534         
1535         for( i = 0; i < 3; i++ )
1536                 if( fabs( v1[ i ] - v2[ i ] ) > CULL_EPSILON )
1537                         return qfalse;
1538         return qtrue;
1539 }
1540
1541
1542
1543 /*
1544 SideInBrush() - ydnar
1545 determines if a brushside lies inside another brush
1546 */
1547
1548 qboolean SideInBrush( side_t *side, brush_t *b )
1549 {
1550         int                     i, s;
1551         plane_t         *plane;
1552         
1553         
1554         /* ignore sides w/o windings or shaders */
1555         if( side->winding == NULL || side->shaderInfo == NULL )
1556                 return qtrue;
1557
1558         /* ignore culled sides and translucent brushes */
1559         if( side->culled == qtrue || (b->compileFlags & C_TRANSLUCENT) )
1560                 return qfalse;
1561
1562         /* side iterator */
1563         for( i = 0; i < b->numsides; i++ )
1564         {
1565                 /* fail if any sides are caulk */
1566                 if( b->sides[ i ].compileFlags & C_NODRAW )
1567                         return qfalse;
1568
1569                 /* check if side's winding is on or behind the plane */
1570                 plane = &mapplanes[ b->sides[ i ].planenum ];
1571                 s = WindingOnPlaneSide( side->winding, plane->normal, plane->dist );
1572                 if( s == SIDE_FRONT || s == SIDE_CROSS )
1573                         return qfalse;
1574         }
1575         
1576         /* don't cull autosprite or polygonoffset surfaces */
1577         if( side->shaderInfo )
1578         {
1579                 if( side->shaderInfo->autosprite || side->shaderInfo->polygonOffset )
1580                         return qfalse;
1581         }
1582         
1583         /* inside */
1584         side->culled = qtrue;
1585         g_numHiddenFaces++;
1586         return qtrue;
1587 }
1588
1589
1590 /*
1591 CullSides() - ydnar
1592 culls obscured or buried brushsides from the map
1593 */
1594
1595 void CullSides( entity_t *e )
1596 {
1597         int                     numPoints;
1598         int                     i, j, k, l, first, second, dir;
1599         winding_t       *w1, *w2;
1600         brush_t *b1, *b2;
1601         side_t          *side1, *side2;
1602         
1603         
1604         /* note it */
1605         Sys_FPrintf( SYS_VRB, "--- CullSides ---\n" );
1606         
1607         g_numHiddenFaces = 0;
1608         g_numCoinFaces = 0;
1609         
1610         /* brush interator 1 */
1611         for( b1 = e->brushes; b1; b1 = b1->next )
1612         {
1613                 /* sides check */
1614                 if( b1->numsides < 1 )
1615                         continue;
1616
1617                 /* brush iterator 2 */
1618                 for( b2 = b1->next; b2; b2 = b2->next )
1619                 {
1620                         /* sides check */
1621                         if( b2->numsides < 1 )
1622                                 continue;
1623                         
1624                         /* original check */
1625                         if( b1->original == b2->original && b1->original != NULL )
1626                                 continue;
1627                         
1628                         /* bbox check */
1629                         j = 0;
1630                         for( i = 0; i < 3; i++ )
1631                                 if( b1->mins[ i ] > b2->maxs[ i ] || b1->maxs[ i ] < b2->mins[ i ] )
1632                                         j++;
1633                         if( j )
1634                                 continue;
1635
1636                         /* cull inside sides */
1637                         for( i = 0; i < b1->numsides; i++ )
1638                                 SideInBrush( &b1->sides[ i ], b2 );
1639                         for( i = 0; i < b2->numsides; i++ )
1640                                 SideInBrush( &b2->sides[ i ], b1 );
1641                         
1642                         /* side iterator 1 */
1643                         for( i = 0; i < b1->numsides; i++ )
1644                         {
1645                                 /* winding check */
1646                                 side1 = &b1->sides[ i ];
1647                                 w1 = side1->winding;
1648                                 if( w1 == NULL )
1649                                         continue;
1650                                 numPoints = w1->numpoints;
1651                                 if( side1->shaderInfo == NULL )
1652                                         continue;
1653                                 
1654                                 /* side iterator 2 */
1655                                 for( j = 0; j < b2->numsides; j++ )
1656                                 {
1657                                         /* winding check */
1658                                         side2 = &b2->sides[ j ];
1659                                         w2 = side2->winding;
1660                                         if( w2 == NULL )
1661                                                 continue;
1662                                         if( side2->shaderInfo == NULL )
1663                                                 continue;
1664                                         if( w1->numpoints != w2->numpoints )
1665                                                 continue;
1666                                         if( side1->culled == qtrue && side2->culled == qtrue )
1667                                                 continue;
1668                                         
1669                                         /* compare planes */
1670                                         if( (side1->planenum & ~0x00000001) != (side2->planenum & ~0x00000001) )
1671                                                 continue;
1672                                         
1673                                         /* get autosprite and polygonoffset status */
1674                                         if( side1->shaderInfo &&
1675                                                 (side1->shaderInfo->autosprite || side1->shaderInfo->polygonOffset) )
1676                                                 continue;
1677                                         if( side2->shaderInfo &&
1678                                                 (side2->shaderInfo->autosprite || side2->shaderInfo->polygonOffset) )
1679                                                 continue;
1680                                         
1681                                         /* find first common point */
1682                                         first = -1;
1683                                         for( k = 0; k < numPoints; k++ )
1684                                         {
1685                                                 if( VectorCompare( w1->p[ 0 ], w2->p[ k ] ) )
1686                                                 {
1687                                                         first = k;
1688                                                         k = numPoints;
1689                                                 }
1690                                         }
1691                                         if( first == -1 )
1692                                                 continue;
1693                                         
1694                                         /* find second common point (regardless of winding order) */
1695                                         second = -1;
1696                                         dir = 0;
1697                                         if( (first + 1) < numPoints )
1698                                                 second = first + 1;
1699                                         else
1700                                                 second = 0;
1701                                         if( CullVectorCompare( w1->p[ 1 ], w2->p[ second ] ) )
1702                                                 dir = 1;
1703                                         else
1704                                         {
1705                                                 if( first > 0 )
1706                                                         second = first - 1;
1707                                                 else
1708                                                         second = numPoints - 1;
1709                                                 if( CullVectorCompare( w1->p[ 1 ], w2->p[ second ] ) )
1710                                                         dir = -1;
1711                                         }
1712                                         if( dir == 0 )
1713                                                 continue;
1714                                         
1715                                         /* compare the rest of the points */
1716                                         l = first;
1717                                         for( k = 0; k < numPoints; k++ )
1718                                         {
1719                                                 if( !CullVectorCompare( w1->p[ k ], w2->p[ l ] ) )
1720                                                         k = 100000;
1721                                                 
1722                                                 l += dir;
1723                                                 if( l < 0 )
1724                                                         l = numPoints - 1;
1725                                                 else if( l >= numPoints )
1726                                                         l = 0;
1727                                         }
1728                                         if( k >= 100000 )
1729                                                 continue;
1730                                         
1731                                         /* cull face 1 */
1732                                         if( !side2->culled && !(side2->compileFlags & C_TRANSLUCENT) && !(side2->compileFlags & C_NODRAW) )
1733                                         {
1734                                                 side1->culled = qtrue;
1735                                                 g_numCoinFaces++;
1736                                         }
1737                                         
1738                                         if( side1->planenum == side2->planenum && side1->culled == qtrue )
1739                                                 continue;
1740                                         
1741                                         /* cull face 2 */
1742                                         if( !side1->culled && !(side1->compileFlags & C_TRANSLUCENT) && !(side1->compileFlags & C_NODRAW) )
1743                                         {
1744                                                 side2->culled = qtrue;
1745                                                 g_numCoinFaces++;
1746                                         }
1747                                 }
1748                         }
1749                 }
1750         }
1751         
1752         /* emit some stats */
1753         Sys_FPrintf( SYS_VRB, "%9d hidden faces culled\n", g_numHiddenFaces );
1754         Sys_FPrintf( SYS_VRB, "%9d coincident faces culled\n", g_numCoinFaces );
1755 }
1756
1757
1758
1759
1760 /*
1761 ClipSidesIntoTree()
1762
1763 creates side->visibleHull for all visible sides
1764
1765 the drawsurf for a side will consist of the convex hull of
1766 all points in non-opaque clusters, which allows overlaps
1767 to be trimmed off automatically.
1768 */
1769
1770 void ClipSidesIntoTree( entity_t *e, tree_t *tree )
1771 {
1772         brush_t         *b;
1773         int                             i;
1774         winding_t               *w;
1775         side_t                  *side, *newSide;
1776         shaderInfo_t    *si;
1777   
1778         
1779         /* ydnar: cull brush sides */
1780         CullSides( e );
1781         
1782         /* note it */
1783         Sys_FPrintf( SYS_VRB, "--- ClipSidesIntoTree ---\n" );
1784         
1785         /* walk the brush list */
1786         for( b = e->brushes; b; b = b->next )
1787         {
1788                 /* walk the brush sides */
1789                 for( i = 0; i < b->numsides; i++ )
1790                 {
1791                         /* get side */
1792                         side = &b->sides[ i ];
1793                         if( side->winding == NULL )
1794                                 continue;
1795                         
1796                         /* copy the winding */
1797                         w = CopyWinding( side->winding );
1798                         side->visibleHull = NULL;
1799                         ClipSideIntoTree_r( w, side, tree->headnode );
1800                         
1801                         /* anything left? */
1802                         w = side->visibleHull;
1803                         if( w == NULL )
1804                                 continue;
1805                         
1806                         /* shader? */
1807                         si = side->shaderInfo;
1808                         if( si == NULL )
1809                                 continue;
1810                         
1811                         /* don't create faces for non-visible sides */
1812                         /* ydnar: except indexed shaders, like common/terrain and nodraw fog surfaces */
1813                         if( (si->compileFlags & C_NODRAW) && si->indexed == qfalse && !(si->compileFlags & C_FOG) )
1814                                 continue;
1815                         
1816                         /* always use the original winding for autosprites and noclip faces */
1817                         if( si->autosprite || si->noClip )
1818                                 w = side->winding;
1819                         
1820                         /* save this winding as a visible surface */
1821                         DrawSurfaceForSide( e, b, side, w );
1822
1823                         /* make a back side for fog */
1824                         if( !(si->compileFlags & C_FOG) )
1825                                 continue;
1826                         
1827                         /* duplicate the up-facing side */
1828                         w = ReverseWinding( w );
1829                         newSide = safe_malloc( sizeof( *side ) );
1830                         *newSide = *side;
1831                         newSide->visibleHull = w;
1832                         newSide->planenum ^= 1;
1833                         
1834                         /* save this winding as a visible surface */
1835                         DrawSurfaceForSide( e, b, newSide, w );
1836                 }
1837         }
1838 }
1839
1840
1841
1842 /*
1843
1844 this section deals with filtering drawsurfaces into the bsp tree,
1845 adding references to each leaf a surface touches
1846
1847 */
1848
1849 /*
1850 AddReferenceToLeaf() - ydnar
1851 adds a reference to surface ds in the bsp leaf node
1852 */
1853
1854 int AddReferenceToLeaf( mapDrawSurface_t *ds, node_t *node )
1855 {
1856         drawSurfRef_t   *dsr;
1857         
1858         
1859         /* dummy check */
1860         if( node->planenum != PLANENUM_LEAF || node->opaque )
1861                 return 0;
1862         
1863         /* try to find an existing reference */
1864         for( dsr = node->drawSurfReferences; dsr; dsr = dsr->nextRef )
1865         {
1866                 if( dsr->outputNum == numBSPDrawSurfaces )
1867                         return 0;
1868         }
1869         
1870         /* add a new reference */
1871         dsr = safe_malloc( sizeof( *dsr ) );
1872         dsr->outputNum = numBSPDrawSurfaces;
1873         dsr->nextRef = node->drawSurfReferences;
1874         node->drawSurfReferences = dsr;
1875         
1876         /* ydnar: sky/skybox surfaces */
1877         if( node->skybox )
1878                 ds->skybox = qtrue;
1879         if( ds->shaderInfo->compileFlags & C_SKY )
1880                 node->sky = qtrue;
1881         
1882         /* return */
1883         return 1;
1884 }
1885
1886
1887
1888 /*
1889 AddReferenceToTree_r() - ydnar
1890 adds a reference to the specified drawsurface to every leaf in the tree
1891 */
1892
1893 int AddReferenceToTree_r( mapDrawSurface_t *ds, node_t *node, qboolean skybox )
1894 {
1895         int             i, refs = 0;
1896         
1897         
1898         /* dummy check */
1899         if( node == NULL )
1900                 return 0;
1901         
1902         /* is this a decision node? */
1903         if( node->planenum != PLANENUM_LEAF )
1904         {
1905                 /* add to child nodes and return */
1906                 refs += AddReferenceToTree_r( ds, node->children[ 0 ], skybox );
1907                 refs += AddReferenceToTree_r( ds, node->children[ 1 ], skybox );
1908                 return refs;
1909         }
1910         
1911         /* ydnar */
1912         if( skybox )
1913         {
1914                 /* skybox surfaces only get added to sky leaves */
1915                 if( !node->sky )
1916                         return 0;
1917                 
1918                 /* increase the leaf bounds */
1919                 for( i = 0; i < ds->numVerts; i++ )
1920                         AddPointToBounds( ds->verts[ i ].xyz, node->mins, node->maxs );
1921         }
1922         
1923         /* add a reference */
1924         return AddReferenceToLeaf( ds, node );
1925 }
1926
1927
1928
1929 /*
1930 FilterPointIntoTree_r() - ydnar
1931 filters a single point from a surface into the tree
1932 */
1933
1934 int FilterPointIntoTree_r( vec3_t point, mapDrawSurface_t *ds, node_t *node )
1935 {
1936         float                   d;
1937         plane_t                 *plane;
1938         int                             refs = 0;
1939         
1940         
1941         /* is this a decision node? */
1942         if( node->planenum != PLANENUM_LEAF )
1943         {
1944                 /* classify the point in relation to the plane */
1945                 plane = &mapplanes[ node->planenum ];
1946                 d = DotProduct( point, plane->normal ) - plane->dist;
1947                 
1948                 /* filter by this plane */
1949                 refs = 0;
1950                 if( d >= -ON_EPSILON )
1951                         refs += FilterPointIntoTree_r( point, ds, node->children[ 0 ] );
1952                 if( d <= ON_EPSILON )
1953                         refs += FilterPointIntoTree_r( point, ds, node->children[ 1 ] );
1954                 
1955                 /* return */
1956                 return refs;
1957         }
1958         
1959         /* add a reference */
1960         return AddReferenceToLeaf( ds, node );
1961 }
1962
1963
1964
1965 /*
1966 FilterWindingIntoTree_r() - ydnar
1967 filters a winding from a drawsurface into the tree
1968 */
1969
1970 int FilterWindingIntoTree_r( winding_t *w, mapDrawSurface_t *ds, node_t *node )
1971 {
1972         int                             i, refs = 0;
1973         plane_t                 *p1, *p2;
1974         vec4_t                  plane1, plane2, reverse;
1975         winding_t               *fat, *front, *back;
1976         shaderInfo_t    *si;
1977         
1978         
1979         /* get shaderinfo */
1980         si = ds->shaderInfo;
1981         
1982         /* ydnar: is this the head node? */
1983         if( node->parent == NULL && si != NULL &&
1984                 (si->mins[ 0 ] != 0.0f || si->maxs[ 0 ] != 0.0f ||
1985                 si->mins[ 1 ] != 0.0f || si->maxs[ 1 ] != 0.0f ||
1986                 si->mins[ 2 ] != 0.0f || si->maxs[ 2 ] != 0.0f) )
1987         {
1988                 /* 'fatten' the winding by the shader mins/maxs (parsed from vertexDeform move) */
1989                 /* note this winding is completely invalid (concave, nonplanar, etc) */
1990                 fat = AllocWinding( w->numpoints * 3 );
1991                 fat->numpoints = w->numpoints * 3;
1992                 for( i = 0; i < w->numpoints; i++ )
1993                 {
1994                         VectorCopy( w->p[ i ], fat->p[ i ] );
1995                         VectorAdd( w->p[ i ], si->mins, fat->p[ i * 2 ] );
1996                         VectorAdd( w->p[ i ], si->maxs, fat->p[ i * 3 ] );
1997                 }
1998                 
1999                 FreeWinding( w );
2000                 w = fat;
2001         }
2002         
2003         /* is this a decision node? */
2004         if( node->planenum != PLANENUM_LEAF )
2005         {       
2006                 /* get node plane */
2007                 p1 = &mapplanes[ node->planenum ];
2008                 VectorCopy( p1->normal, plane1 );
2009                 plane1[ 3 ] = p1->dist;
2010                 
2011                 /* check if surface is planar */
2012                 if( ds->planeNum >= 0 )
2013                 {
2014                         /* get surface plane */
2015                         p2 = &mapplanes[ ds->planeNum ];
2016                         VectorCopy( p2->normal, plane2 );
2017                         plane2[ 3 ] = p2->dist;
2018                         
2019                         #if 1
2020                                 /* invert surface plane */
2021                                 VectorSubtract( vec3_origin, plane2, reverse );
2022                                 reverse[ 3 ] = -plane2[ 3 ];
2023                                 
2024                                 /* compare planes */
2025                                 if( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f )
2026                                         return FilterWindingIntoTree_r( w, ds, node->children[ 0 ] );
2027                                 if( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f )
2028                                         return FilterWindingIntoTree_r( w, ds, node->children[ 1 ] );
2029                         #else
2030                                 /* the drawsurf might have an associated plane, if so, force a filter here */
2031                                 if( ds->planeNum == node->planenum )
2032                                         return FilterWindingIntoTree_r( w, ds, node->children[ 0 ] );
2033                                 if( ds->planeNum == (node->planenum ^ 1) )
2034                                         return FilterWindingIntoTree_r( w, ds, node->children[ 1 ] );
2035                         #endif
2036                 }
2037                 
2038                 /* clip the winding by this plane */
2039                 ClipWindingEpsilon( w, plane1, plane1[ 3 ], ON_EPSILON, &front, &back );
2040                 
2041                 /* filter by this plane */
2042                 refs = 0;
2043                 if( front != NULL )
2044                         refs += FilterWindingIntoTree_r( front, ds, node->children[ 0 ] );
2045                 if( back != NULL )
2046                         refs += FilterWindingIntoTree_r( back, ds, node->children[ 1 ] );
2047                 FreeWinding( w );
2048                 
2049                 /* return */
2050                 return refs;
2051         }
2052         
2053         /* add a reference */
2054         return AddReferenceToLeaf( ds, node );
2055 }
2056
2057
2058
2059 /*
2060 FilterFaceIntoTree()
2061 filters a planar winding face drawsurface into the bsp tree
2062 */
2063
2064 int     FilterFaceIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2065 {
2066         winding_t       *w;
2067         int                     refs = 0;
2068         
2069         
2070         /* make a winding and filter it into the tree */
2071         w = WindingFromDrawSurf( ds );
2072         refs = FilterWindingIntoTree_r( w, ds, tree->headnode );
2073         
2074         /* return */
2075         return refs;
2076 }
2077
2078
2079
2080 /*
2081 FilterPatchIntoTree()
2082 subdivides a patch into an approximate curve and filters it into the tree
2083 */
2084
2085 #define FILTER_SUBDIVISION              8
2086
2087 static int FilterPatchIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2088 {
2089         int                                     i, x, y, refs;
2090         mesh_t                          src, *mesh;
2091         winding_t                       *w;
2092         
2093         
2094         /* subdivide the surface */
2095         src.width = ds->patchWidth;
2096         src.height = ds->patchHeight;
2097         src.verts = ds->verts;
2098         mesh = SubdivideMesh( src, FILTER_SUBDIVISION, 32 );
2099         
2100         
2101         /* filter each quad into the tree (fixme: use new patch x-triangulation code?) */
2102         refs = 0;
2103         for( y = 0; y < (mesh->height - 1); y++ )
2104         {
2105                 for( x = 0; x < (mesh->width - 1); x++ )
2106                 {
2107                         /* triangle 1 */
2108                         w = AllocWinding( 3 );
2109                         w->numpoints = 3;
2110                         VectorCopy( mesh->verts[ y * mesh->width + x ].xyz, w->p[ 0 ] );
2111                         VectorCopy( mesh->verts[ y * mesh->width + x + 1 ].xyz, w->p[ 1 ] );
2112                         VectorCopy( mesh->verts[ (y + 1) * mesh->width + x ].xyz, w->p[ 2 ] );
2113                         refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2114                         
2115                         /* triangle 2 */
2116                         w = AllocWinding( 3 );
2117                         w->numpoints = 3;
2118                         VectorCopy( mesh->verts[ y * mesh->width + x + 1 ].xyz, w->p[ 0 ] );
2119                         VectorCopy( mesh->verts[ (y + 1 ) * mesh->width + x + 1 ].xyz, w->p[ 1 ] );
2120                         VectorCopy( mesh->verts[ (y + 1 ) * mesh->width + x ].xyz, w->p[ 2 ] );
2121                         refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2122                 }
2123         }
2124         
2125         /* use point filtering as well */
2126         for( i = 0; i < (mesh->width * mesh->height); i++ )
2127                 refs += FilterPointIntoTree_r( mesh->verts[ i ].xyz, ds, tree->headnode );
2128         
2129         /* free the subdivided mesh and return */
2130         FreeMesh( mesh );
2131         return refs;
2132 }
2133
2134
2135
2136 /*
2137 FilterTrianglesIntoTree()
2138 filters a triangle surface (meta, model) into the bsp
2139 */
2140
2141 static int FilterTrianglesIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2142 {
2143         int                     i, refs;
2144         winding_t       *w;
2145         
2146         
2147         /* ydnar: gs mods: this was creating bogus triangles before */
2148         refs = 0;
2149         for( i = 0; i < ds->numIndexes; i += 3 )
2150         {
2151                 /* error check */
2152                 if( ds->indexes[ i ] >= ds->numVerts ||
2153                         ds->indexes[ i + 1 ] >= ds->numVerts ||
2154                         ds->indexes[ i + 2 ] >= ds->numVerts )
2155                         Error( "Index %d greater than vertex count %d", ds->indexes[ i ], ds->numVerts );
2156                 
2157                 /* make a triangle winding and filter it into the tree */
2158                 w = AllocWinding( 3 );
2159                 w->numpoints = 3;
2160                 VectorCopy( ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
2161                 VectorCopy( ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
2162                 VectorCopy( ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
2163                 refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2164         }
2165         
2166         /* use point filtering as well */
2167         for( i = 0; i < ds->numVerts; i++ )
2168                 refs += FilterPointIntoTree_r( ds->verts[ i ].xyz, ds, tree->headnode );
2169
2170         return refs;
2171 }
2172
2173
2174
2175 /*
2176 FilterFoliageIntoTree()
2177 filters a foliage surface (wolf et/splash damage)
2178 */
2179
2180 static int FilterFoliageIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2181 {
2182         int                             f, i, refs;
2183         bspDrawVert_t   *instance;
2184         vec3_t                  xyz;
2185         winding_t               *w;
2186         
2187         
2188         /* walk origin list */
2189         refs = 0;
2190         for( f = 0; f < ds->numFoliageInstances; f++ )
2191         {
2192                 /* get instance */
2193                 instance = ds->verts + ds->patchHeight + f;
2194                 
2195                 /* walk triangle list */
2196                 for( i = 0; i < ds->numIndexes; i += 3 )
2197                 {
2198                         /* error check */
2199                         if( ds->indexes[ i ] >= ds->numVerts ||
2200                                 ds->indexes[ i + 1 ] >= ds->numVerts ||
2201                                 ds->indexes[ i + 2 ] >= ds->numVerts )
2202                                 Error( "Index %d greater than vertex count %d", ds->indexes[ i ], ds->numVerts );
2203                         
2204                         /* make a triangle winding and filter it into the tree */
2205                         w = AllocWinding( 3 );
2206                         w->numpoints = 3;
2207                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
2208                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
2209                         VectorAdd( instance->xyz, ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
2210                         refs += FilterWindingIntoTree_r( w, ds, tree->headnode );
2211                 }
2212                 
2213                 /* use point filtering as well */
2214                 for( i = 0; i < (ds->numVerts - ds->numFoliageInstances); i++ )
2215                 {
2216                         VectorAdd( instance->xyz, ds->verts[ i ].xyz, xyz );
2217                         refs += FilterPointIntoTree_r( xyz, ds, tree->headnode );
2218                 }
2219         }
2220         
2221         return refs;
2222 }
2223
2224
2225
2226 /*
2227 FilterFlareIntoTree()
2228 simple point filtering for flare surfaces
2229 */
2230 static int FilterFlareSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree )
2231 {
2232         return FilterPointIntoTree_r( ds->lightmapOrigin, ds, tree->headnode );
2233 }
2234
2235
2236
2237 /*
2238 EmitDrawVerts() - ydnar
2239 emits bsp drawverts from a map drawsurface
2240 */
2241
2242 void EmitDrawVerts( mapDrawSurface_t *ds, bspDrawSurface_t *out )
2243 {
2244         int                             i, k;
2245         bspDrawVert_t   *dv;
2246         shaderInfo_t    *si;
2247         float                   offset;
2248         
2249         
2250         /* get stuff */
2251         si = ds->shaderInfo;
2252         offset = si->offset;
2253         
2254         /* copy the verts */
2255         out->firstVert = numBSPDrawVerts;
2256         out->numVerts = ds->numVerts;
2257         for( i = 0; i < ds->numVerts; i++ )
2258         {
2259                 /* allocate a new vert */
2260                 IncDrawVerts();
2261                 dv = &bspDrawVerts[ numBSPDrawVerts - 1 ];
2262                 
2263                 /* copy it */
2264                 memcpy( dv, &ds->verts[ i ], sizeof( *dv ) );
2265                 
2266                 /* offset? */
2267                 if( offset != 0.0f )
2268                         VectorMA( dv->xyz, offset, dv->normal, dv->xyz );
2269                 
2270                 /* expand model bounds
2271                    necessary because of misc_model surfaces on entities
2272                    note: does not happen on worldspawn as its bounds is only used for determining lightgrid bounds */
2273                 if( numBSPModels > 0 )
2274                         AddPointToBounds( dv->xyz, bspModels[ numBSPModels ].mins, bspModels[ numBSPModels ].maxs );
2275                 
2276                 /* debug color? */
2277                 if( debugSurfaces )
2278                 {
2279                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
2280                                 VectorCopy( debugColors[ (ds - mapDrawSurfs) % 12 ], dv->color[ k ] );
2281                 }
2282         }
2283 }
2284
2285
2286
2287 /*
2288 FindDrawIndexes() - ydnar
2289 this attempts to find a run of indexes in the bsp that match the given indexes
2290 this tends to reduce the size of the bsp index pool by 1/3 or more
2291 returns numIndexes + 1 if the search failed
2292 */
2293
2294 int FindDrawIndexes( int numIndexes, int *indexes )
2295 {
2296         int             i, j, numTestIndexes;
2297         
2298         
2299         /* dummy check */
2300         if( numIndexes < 3 || numBSPDrawIndexes < numIndexes || indexes == NULL )
2301                 return numBSPDrawIndexes;
2302         
2303         /* set limit */
2304         numTestIndexes = 1 + numBSPDrawIndexes - numIndexes;
2305         
2306         /* handle 3 indexes as a special case for performance */
2307         if( numIndexes == 3 )
2308         {
2309                 /* run through all indexes */
2310                 for( i = 0; i < numTestIndexes; i++ )
2311                 {
2312                         /* test 3 indexes */
2313                         if( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2314                                 indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2315                                 indexes[ 2 ] == bspDrawIndexes[ i + 2 ] )
2316                         {
2317                                 numRedundantIndexes += numIndexes;
2318                                 return i;
2319                         }
2320                 }
2321                 
2322                 /* failed */
2323                 return numBSPDrawIndexes;
2324         }
2325         
2326         /* handle 4 or more indexes */
2327         for( i = 0; i < numTestIndexes; i++ )
2328         {
2329                 /* test first 4 indexes */
2330                 if( indexes[ 0 ] == bspDrawIndexes[ i ] &&
2331                         indexes[ 1 ] == bspDrawIndexes[ i + 1 ] &&
2332                         indexes[ 2 ] == bspDrawIndexes[ i + 2 ] &&
2333                         indexes[ 3 ] == bspDrawIndexes[ i + 3 ] )
2334                 {
2335                         /* handle 4 indexes */
2336                         if( numIndexes == 4 )
2337                                 return i;
2338                         
2339                         /* test the remainder */
2340                         for( j = 4; j < numIndexes; j++ )
2341                         {
2342                                 if( indexes[ j ] != bspDrawIndexes[ i + j ] )
2343                                         break;
2344                                 else if( j == (numIndexes - 1) )
2345                                 {
2346                                         numRedundantIndexes += numIndexes;
2347                                         return i;
2348                                 }
2349                         }
2350                 }
2351         }
2352         
2353         /* failed */
2354         return numBSPDrawIndexes;
2355 }
2356
2357
2358
2359 /*
2360 EmitDrawIndexes() - ydnar
2361 attempts to find an existing run of drawindexes before adding new ones
2362 */
2363
2364 void EmitDrawIndexes( mapDrawSurface_t *ds, bspDrawSurface_t *out )
2365 {
2366         int                     i;
2367         
2368         
2369         /* attempt to use redundant indexing */
2370         out->firstIndex = FindDrawIndexes( ds->numIndexes, ds->indexes );
2371         out->numIndexes = ds->numIndexes;
2372         if( out->firstIndex == numBSPDrawIndexes )
2373         {
2374                 /* copy new unique indexes */
2375                 for( i = 0; i < ds->numIndexes; i++ )
2376                 {
2377                         if( numBSPDrawIndexes == MAX_MAP_DRAW_INDEXES )
2378                                 Error( "MAX_MAP_DRAW_INDEXES" );
2379                         bspDrawIndexes[ numBSPDrawIndexes ] = ds->indexes[ i ];
2380
2381                         /* validate the index */
2382                         if( ds->type != SURFACE_PATCH )
2383                         {
2384                                 if( bspDrawIndexes[ numBSPDrawIndexes ] < 0 || bspDrawIndexes[ numBSPDrawIndexes ] >= ds->numVerts )
2385                                 {
2386                                         Sys_Printf( "WARNING: %d %s has invalid index %d (%d)\n",
2387                                                 numBSPDrawSurfaces,
2388                                                 ds->shaderInfo->shader,
2389                                                 bspDrawIndexes[ numBSPDrawIndexes ],
2390                                                 i );
2391                                         bspDrawIndexes[ numBSPDrawIndexes ] = 0;
2392                                 }
2393                         }
2394                         
2395                         /* increment index count */
2396                         numBSPDrawIndexes++;
2397                 }
2398         }
2399 }
2400
2401
2402
2403
2404 /*
2405 EmitFlareSurface()
2406 emits a bsp flare drawsurface
2407 */
2408
2409 void EmitFlareSurface( mapDrawSurface_t *ds )
2410 {
2411         int                                             i;
2412         bspDrawSurface_t                *out;
2413         
2414         
2415         /* ydnar: nuking useless flare drawsurfaces */
2416         if( emitFlares == qfalse && ds->type != SURFACE_SHADER )
2417                 return;
2418         
2419         /* limit check */
2420         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2421                 Error( "MAX_MAP_DRAW_SURFS" );
2422         
2423         /* allocate a new surface */
2424         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2425                 Error( "MAX_MAP_DRAW_SURFS" );
2426         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2427         ds->outputNum = numBSPDrawSurfaces;
2428         numBSPDrawSurfaces++;
2429         memset( out, 0, sizeof( *out ) );
2430         
2431         /* set it up */
2432         out->surfaceType = MST_FLARE;
2433         out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2434         out->fogNum = ds->fogNum;
2435         
2436         /* RBSP */
2437         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2438         {
2439                 out->lightmapNum[ i ] = -3;
2440                 out->lightmapStyles[ i ] = LS_NONE;
2441                 out->vertexStyles[ i ] = LS_NONE;
2442         }
2443         out->lightmapStyles[ 0 ] = ds->lightStyle;
2444         out->vertexStyles[ 0 ] = ds->lightStyle;
2445         
2446         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );                  /* origin */
2447         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );    /* color */
2448         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2449         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );    /* normal */
2450         
2451         /* add to count */
2452         numSurfacesByType[ ds->type ]++;
2453 }
2454
2455 /*
2456 EmitPatchSurface()
2457 emits a bsp patch drawsurface
2458 */
2459
2460 void EmitPatchSurface( entity_t *e, mapDrawSurface_t *ds )
2461 {
2462         int                                     i, j;
2463         bspDrawSurface_t        *out;
2464         int                                     surfaceFlags, contentFlags;
2465         int                                     forcePatchMeta;
2466
2467         /* vortex: _patchMeta support */
2468         forcePatchMeta = IntForKey(e, "_patchMeta" );
2469         if (!forcePatchMeta)
2470                 forcePatchMeta = IntForKey(e, "patchMeta" );
2471         
2472         /* invert the surface if necessary */
2473         if( ds->backSide || ds->shaderInfo->invert )
2474         {
2475                 bspDrawVert_t   *dv1, *dv2, temp;
2476
2477                 /* walk the verts, flip the normal */
2478                 for( i = 0; i < ds->numVerts; i++ )
2479                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2480                 
2481                 /* walk the verts again, but this time reverse their order */
2482                 for( j = 0; j < ds->patchHeight; j++ )
2483                 {
2484                         for( i = 0; i < (ds->patchWidth / 2); i++ )
2485                         {
2486                                 dv1 = &ds->verts[ j * ds->patchWidth + i ];
2487                                 dv2 = &ds->verts[ j * ds->patchWidth + (ds->patchWidth - i - 1) ];
2488                                 memcpy( &temp, dv1, sizeof( bspDrawVert_t ) );
2489                                 memcpy( dv1, dv2, sizeof( bspDrawVert_t ) );
2490                                 memcpy( dv2, &temp, sizeof( bspDrawVert_t ) );
2491                         }
2492                 }
2493                 
2494                 /* invert facing */
2495                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2496         }
2497
2498         /* allocate a new surface */
2499         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2500                 Error( "MAX_MAP_DRAW_SURFS" );
2501         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2502         ds->outputNum = numBSPDrawSurfaces;
2503         numBSPDrawSurfaces++;
2504         memset( out, 0, sizeof( *out ) );
2505
2506         /* set it up */
2507         out->surfaceType = MST_PATCH;
2508         if( debugSurfaces )
2509                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2510         else if( patchMeta || forcePatchMeta )
2511         {
2512                 /* patch meta requires that we have nodraw patches for collision */
2513                 surfaceFlags = ds->shaderInfo->surfaceFlags;
2514                 contentFlags = ds->shaderInfo->contentFlags;
2515                 ApplySurfaceParm( "nodraw", &contentFlags, &surfaceFlags, NULL );
2516                 ApplySurfaceParm( "pointlight", &contentFlags, &surfaceFlags, NULL );
2517                 
2518                 /* we don't want this patch getting lightmapped */
2519                 VectorClear( ds->lightmapVecs[ 2 ] );
2520                 VectorClear( ds->lightmapAxis );
2521                 ds->sampleSize = 0;
2522
2523                 /* emit the new fake shader */
2524                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &contentFlags, &surfaceFlags );
2525         }
2526         else
2527                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2528         out->patchWidth = ds->patchWidth;
2529         out->patchHeight = ds->patchHeight;
2530         out->fogNum = ds->fogNum;
2531         
2532         /* RBSP */
2533         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2534         {
2535                 out->lightmapNum[ i ] = -3;
2536                 out->lightmapStyles[ i ] = LS_NONE;
2537                 out->vertexStyles[ i ] = LS_NONE;
2538         }
2539         out->lightmapStyles[ 0 ] = LS_NORMAL;
2540         out->vertexStyles[ 0 ] = LS_NORMAL;
2541         
2542         /* ydnar: gs mods: previously, the lod bounds were stored in lightmapVecs[ 0 ] and [ 1 ], moved to bounds[ 0 ] and [ 1 ] */
2543         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2544         VectorCopy( ds->bounds[ 0 ], out->lightmapVecs[ 0 ] );
2545         VectorCopy( ds->bounds[ 1 ], out->lightmapVecs[ 1 ] );
2546         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2547         
2548         /* ydnar: gs mods: clear out the plane normal */
2549         if( ds->planar == qfalse )
2550                 VectorClear( out->lightmapVecs[ 2 ] );
2551         
2552         /* emit the verts and indexes */
2553         EmitDrawVerts( ds, out );
2554         EmitDrawIndexes( ds, out );
2555         
2556         /* add to count */
2557         numSurfacesByType[ ds->type ]++;
2558 }
2559
2560 /*
2561 OptimizeTriangleSurface() - ydnar
2562 optimizes the vertex/index data in a triangle surface
2563 */
2564
2565 #define VERTEX_CACHE_SIZE       16
2566
2567 static void OptimizeTriangleSurface( mapDrawSurface_t *ds )
2568 {
2569         int             i, j, k, temp, first, best, bestScore, score;
2570         int             vertexCache[ VERTEX_CACHE_SIZE + 1 ];   /* one more for optimizing insert */
2571         int             *indexes;
2572         
2573         
2574         /* certain surfaces don't get optimized */
2575         if( ds->numIndexes <= VERTEX_CACHE_SIZE ||
2576                 ds->shaderInfo->autosprite )
2577                 return;
2578         
2579         /* create index scratch pad */
2580         indexes = safe_malloc( ds->numIndexes * sizeof( *indexes ) );
2581         memcpy( indexes, ds->indexes, ds->numIndexes * sizeof( *indexes ) );
2582         
2583         /* setup */
2584         for( i = 0; i <= VERTEX_CACHE_SIZE && i < ds->numIndexes; i++ )
2585                 vertexCache[ i ] = indexes[ i ];
2586         
2587         /* add triangles in a vertex cache-aware order */
2588         for( i = 0; i < ds->numIndexes; i += 3 )
2589         {
2590                 /* find best triangle given the current vertex cache */
2591                 first = -1;
2592                 best = -1;
2593                 bestScore = -1;
2594                 for( j = 0; j < ds->numIndexes; j += 3 )
2595                 {
2596                         /* valid triangle? */
2597                         if( indexes[ j ] != -1 )
2598                         {
2599                                 /* set first if necessary */
2600                                 if( first < 0 )
2601                                         first = j;
2602                                 
2603                                 /* score the triangle */
2604                                 score = 0;
2605                                 for( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2606                                 {
2607                                         if( indexes[ j ] == vertexCache[ k ] || indexes[ j + 1 ] == vertexCache[ k ] || indexes[ j + 2 ] == vertexCache[ k ] )
2608                                                 score++;
2609                                 }
2610                                 
2611                                 /* better triangle? */
2612                                 if( score > bestScore )
2613                                 {
2614                                         bestScore = score;
2615                                         best = j;
2616                                 }
2617                                 
2618                                 /* a perfect score of 3 means this triangle's verts are already present in the vertex cache */
2619                                 if( score == 3 )
2620                                         break;
2621                         }
2622                 }
2623                 
2624                 /* check if no decent triangle was found, and use first available */
2625                 if( best < 0 )
2626                         best = first;
2627                 
2628                 /* valid triangle? */
2629                 if( best >= 0 )
2630                 {
2631                         /* add triangle to vertex cache */
2632                         for( j = 0; j < 3; j++ )
2633                         {
2634                                 for( k = 0; k < VERTEX_CACHE_SIZE; k++ )
2635                                 {
2636                                         if( indexes[ best + j ] == vertexCache[ k ] )
2637                                                 break;
2638                                 }
2639                                 
2640                                 if( k >= VERTEX_CACHE_SIZE )
2641                                 {
2642                                         /* pop off top of vertex cache */
2643                                         for( k = VERTEX_CACHE_SIZE; k > 0; k-- )
2644                                                 vertexCache[ k ] = vertexCache[ k - 1 ];
2645                                         
2646                                         /* add vertex */
2647                                         vertexCache[ 0 ] = indexes[ best + j ];
2648                                 }
2649                         }
2650                         
2651                         /* add triangle to surface */
2652                         ds->indexes[ i ] = indexes[ best ];
2653                         ds->indexes[ i + 1 ] = indexes[ best + 1 ];
2654                         ds->indexes[ i + 2 ] = indexes[ best + 2 ];
2655                         
2656                         /* clear from input pool */
2657                         indexes[ best ] = -1;
2658                         indexes[ best + 1 ] = -1;
2659                         indexes[ best + 2 ] = -1;
2660                         
2661                         /* sort triangle windings (312 -> 123) */
2662                         while( ds->indexes[ i ] > ds->indexes[ i + 1 ] || ds->indexes[ i ] > ds->indexes[ i + 2 ] )
2663                         {
2664                                 temp = ds->indexes[ i ];
2665                                 ds->indexes[ i ] = ds->indexes[ i + 1 ];
2666                                 ds->indexes[ i + 1 ] = ds->indexes[ i + 2 ];
2667                                 ds->indexes[ i + 2 ] = temp;
2668                         }
2669                 }
2670         }
2671         
2672         /* clean up */
2673         free( indexes );
2674 }
2675
2676
2677
2678 /*
2679 EmitTriangleSurface()
2680 creates a bsp drawsurface from arbitrary triangle surfaces
2681 */
2682
2683 void EmitTriangleSurface( mapDrawSurface_t *ds )
2684 {
2685         int                                             i, temp;
2686         bspDrawSurface_t                *out;
2687
2688         /* invert the surface if necessary */
2689         if( ds->backSide || ds->shaderInfo->invert )
2690         {
2691                 /* walk the indexes, reverse the triangle order */
2692                 for( i = 0; i < ds->numIndexes; i += 3 )
2693                 {
2694                         temp = ds->indexes[ i ];
2695                         ds->indexes[ i ] = ds->indexes[ i + 1 ];
2696                         ds->indexes[ i + 1 ] = temp;
2697                 }
2698                         
2699                 /* walk the verts, flip the normal */
2700                 for( i = 0; i < ds->numVerts; i++ )
2701                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2702                         
2703                 /* invert facing */
2704                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2705         }
2706                 
2707         /* allocate a new surface */
2708         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2709                 Error( "MAX_MAP_DRAW_SURFS" );
2710         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2711         ds->outputNum = numBSPDrawSurfaces;
2712         numBSPDrawSurfaces++;
2713         memset( out, 0, sizeof( *out ) );
2714         
2715         /* ydnar/sd: handle wolf et foliage surfaces */
2716         if( ds->type == SURFACE_FOLIAGE )
2717                 out->surfaceType = MST_FOLIAGE;
2718         
2719         /* ydnar: gs mods: handle lightmapped terrain (force to planar type) */
2720         //%     else if( VectorLength( ds->lightmapAxis ) <= 0.0f || ds->type == SURFACE_TRIANGLES || ds->type == SURFACE_FOGHULL || debugSurfaces )
2721         else if( (VectorLength( ds->lightmapAxis ) <= 0.0f && ds->planar == qfalse) ||
2722                 ds->type == SURFACE_TRIANGLES ||
2723                 ds->type == SURFACE_FOGHULL ||
2724                 ds->numVerts > maxLMSurfaceVerts ||
2725                 debugSurfaces )
2726                 out->surfaceType = MST_TRIANGLE_SOUP;
2727         
2728         /* set to a planar face */
2729         else
2730                 out->surfaceType = MST_PLANAR;
2731         
2732         /* set it up */
2733         if( debugSurfaces )
2734                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2735         else
2736                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2737         out->patchWidth = ds->patchWidth;
2738         out->patchHeight = ds->patchHeight;
2739         out->fogNum = ds->fogNum;
2740         
2741         /* debug inset (push each triangle vertex towards the center of each triangle it is on */
2742         if( debugInset )
2743         {
2744                 bspDrawVert_t   *a, *b, *c;
2745                 vec3_t                  cent, dir;
2746
2747                 
2748                 /* walk triangle list */
2749                 for( i = 0; i < ds->numIndexes; i += 3 )
2750                 {
2751                         /* get verts */
2752                         a = &ds->verts[ ds->indexes[ i ] ];
2753                         b = &ds->verts[ ds->indexes[ i + 1 ] ];
2754                         c = &ds->verts[ ds->indexes[ i + 2 ] ];
2755                         
2756                         /* calculate centroid */
2757                         VectorCopy( a->xyz, cent );
2758                         VectorAdd( cent, b->xyz, cent );
2759                         VectorAdd( cent, c->xyz, cent );
2760                         VectorScale( cent, 1.0f / 3.0f, cent );
2761                         
2762                         /* offset each vertex */
2763                         VectorSubtract( cent, a->xyz, dir );
2764                         VectorNormalize( dir, dir );
2765                         VectorAdd( a->xyz, dir, a->xyz );
2766                         VectorSubtract( cent, b->xyz, dir );
2767                         VectorNormalize( dir, dir );
2768                         VectorAdd( b->xyz, dir, b->xyz );
2769                         VectorSubtract( cent, c->xyz, dir );
2770                         VectorNormalize( dir, dir );
2771                         VectorAdd( c->xyz, dir, c->xyz );
2772                 }
2773         }
2774         
2775         /* RBSP */
2776         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2777         {
2778                 out->lightmapNum[ i ] = -3;
2779                 out->lightmapStyles[ i ] = LS_NONE;
2780                 out->vertexStyles[ i ] = LS_NONE;
2781         }
2782         out->lightmapStyles[ 0 ] = LS_NORMAL;
2783         out->vertexStyles[ 0 ] = LS_NORMAL;
2784         
2785         /* lightmap vectors (lod bounds for patches */
2786         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2787         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );
2788         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2789         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2790         
2791         /* ydnar: gs mods: clear out the plane normal */
2792         if( ds->planar == qfalse )
2793                 VectorClear( out->lightmapVecs[ 2 ] );
2794         
2795         /* optimize the surface's triangles */
2796         OptimizeTriangleSurface( ds );
2797         
2798         /* emit the verts and indexes */
2799         EmitDrawVerts( ds, out );
2800         EmitDrawIndexes( ds, out );
2801         
2802         /* add to count */
2803         numSurfacesByType[ ds->type ]++;
2804 }
2805
2806
2807
2808 /*
2809 EmitFaceSurface()
2810 emits a bsp planar winding (brush face) drawsurface
2811 */
2812
2813 static void EmitFaceSurface(mapDrawSurface_t *ds )
2814 {
2815         /* strip/fan finding was moved elsewhere */
2816         StripFaceSurface( ds );
2817         EmitTriangleSurface(ds);
2818 }
2819
2820
2821 /*
2822 MakeDebugPortalSurfs_r() - ydnar
2823 generates drawsurfaces for passable portals in the bsp
2824 */
2825
2826 static void MakeDebugPortalSurfs_r( node_t *node, shaderInfo_t *si )
2827 {
2828         int                                     i, k, c, s;     
2829         portal_t                        *p;
2830         winding_t                       *w;
2831         mapDrawSurface_t        *ds;
2832         bspDrawVert_t           *dv;
2833         
2834         
2835         /* recurse if decision node */
2836         if( node->planenum != PLANENUM_LEAF)
2837         {
2838                 MakeDebugPortalSurfs_r( node->children[ 0 ], si );
2839                 MakeDebugPortalSurfs_r( node->children[ 1 ], si );
2840                 return;
2841         }
2842         
2843         /* don't bother with opaque leaves */
2844         if( node->opaque )
2845                 return;
2846         
2847         /* walk the list of portals */
2848         for( c = 0, p = node->portals; p != NULL; c++, p = p->next[ s ] )
2849         {
2850                 /* get winding and side even/odd */
2851                 w = p->winding;
2852                 s = (p->nodes[ 1 ] == node);
2853                 
2854                 /* is this a valid portal for this leaf? */
2855                 if( w && p->nodes[ 0 ] == node )
2856                 {
2857                         /* is this portal passable? */
2858                         if( PortalPassable( p ) == qfalse )
2859                                 continue;
2860                         
2861                         /* check max points */
2862                         if( w->numpoints > 64 )
2863                                 Error( "MakePortalSurfs_r: w->numpoints = %d", w->numpoints );
2864                         
2865                         /* allocate a drawsurface */
2866                         ds = AllocDrawSurface( SURFACE_FACE );
2867                         ds->shaderInfo = si;
2868                         ds->planar = qtrue;
2869                         ds->sideRef = AllocSideRef( p->side, NULL );
2870                         ds->planeNum = FindFloatPlane( p->plane.normal, p->plane.dist, 0, NULL );
2871                         VectorCopy( p->plane.normal, ds->lightmapVecs[ 2 ] );
2872                         ds->fogNum = -1;
2873                         ds->numVerts = w->numpoints;
2874                         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
2875                         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
2876                         
2877                         /* walk the winding */
2878                         for( i = 0; i < ds->numVerts; i++ )
2879                         {
2880                                 /* get vert */
2881                                 dv = ds->verts + i;
2882                                 
2883                                 /* set it */
2884                                 VectorCopy( w->p[ i ], dv->xyz );
2885                                 VectorCopy( p->plane.normal, dv->normal );
2886                                 dv->st[ 0 ] = 0;
2887                                 dv->st[ 1 ] = 0;
2888                                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
2889                                 {
2890                                         VectorCopy( debugColors[ c % 12 ], dv->color[ k ] );
2891                                         dv->color[ k ][ 3 ] = 32;
2892                                 }
2893                         }
2894                 }
2895         }
2896 }
2897
2898
2899
2900 /*
2901 MakeDebugPortalSurfs() - ydnar
2902 generates drawsurfaces for passable portals in the bsp
2903 */
2904
2905 void MakeDebugPortalSurfs( tree_t *tree )
2906 {
2907         shaderInfo_t    *si;
2908         
2909         
2910         /* note it */
2911         Sys_FPrintf( SYS_VRB, "--- MakeDebugPortalSurfs ---\n" );
2912         
2913         /* get portal debug shader */
2914         si = ShaderInfoForShader( "debugportals" );
2915         
2916         /* walk the tree */
2917         MakeDebugPortalSurfs_r( tree->headnode, si );
2918 }
2919
2920
2921
2922 /*
2923 MakeFogHullSurfs()
2924 generates drawsurfaces for a foghull (this MUST use a sky shader)
2925 */
2926
2927 void MakeFogHullSurfs( entity_t *e, tree_t *tree, char *shader )
2928 {
2929         shaderInfo_t            *si;
2930         mapDrawSurface_t        *ds;
2931         vec3_t                          fogMins, fogMaxs;
2932         int                                     i, indexes[] =
2933                                                 {
2934                                                         0, 1, 2, 0, 2, 3,
2935                                                         4, 7, 5, 5, 7, 6,
2936                                                         1, 5, 6, 1, 6, 2,
2937                                                         0, 4, 5, 0, 5, 1,
2938                                                         2, 6, 7, 2, 7, 3,
2939                                                         3, 7, 4, 3, 4, 0
2940                                                 };
2941
2942         
2943         /* dummy check */
2944         if( shader == NULL || shader[ 0 ] == '\0' )
2945                 return;
2946         
2947         /* note it */
2948         Sys_FPrintf( SYS_VRB, "--- MakeFogHullSurfs ---\n" );
2949         
2950         /* get hull bounds */
2951         VectorCopy( mapMins, fogMins );
2952         VectorCopy( mapMaxs, fogMaxs );
2953         for( i = 0; i < 3; i++ )
2954         {
2955                 fogMins[ i ] -= 128;
2956                 fogMaxs[ i ] += 128;
2957         }
2958         
2959         /* get foghull shader */
2960         si = ShaderInfoForShader( shader );
2961         
2962         /* allocate a drawsurface */
2963     &