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