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