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