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