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