remove two mysterious crashes (although I don't know why it was broken to begin with)
[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
2451 /*
2452 EmitPatchSurface()
2453 emits a bsp patch drawsurface
2454 */
2455
2456 void EmitPatchSurface( mapDrawSurface_t *ds )
2457 {
2458         int                                     i, j;
2459         bspDrawSurface_t        *out;
2460         int                                     surfaceFlags, contentFlags;
2461         
2462         
2463         /* invert the surface if necessary */
2464         if( ds->backSide || ds->shaderInfo->invert )
2465         {
2466                 bspDrawVert_t   *dv1, *dv2, temp;
2467                 
2468
2469                 /* walk the verts, flip the normal */
2470                 for( i = 0; i < ds->numVerts; i++ )
2471                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2472                 
2473                 /* walk the verts again, but this time reverse their order */
2474                 for( j = 0; j < ds->patchHeight; j++ )
2475                 {
2476                         for( i = 0; i < (ds->patchWidth / 2); i++ )
2477                         {
2478                                 dv1 = &ds->verts[ j * ds->patchWidth + i ];
2479                                 dv2 = &ds->verts[ j * ds->patchWidth + (ds->patchWidth - i - 1) ];
2480                                 memcpy( &temp, dv1, sizeof( bspDrawVert_t ) );
2481                                 memcpy( dv1, dv2, sizeof( bspDrawVert_t ) );
2482                                 memcpy( dv2, &temp, sizeof( bspDrawVert_t ) );
2483                         }
2484                 }
2485                 
2486                 /* invert facing */
2487                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2488         }
2489         
2490         /* allocate a new surface */
2491         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2492                 Error( "MAX_MAP_DRAW_SURFS" );
2493         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2494         ds->outputNum = numBSPDrawSurfaces;
2495         numBSPDrawSurfaces++;
2496         memset( out, 0, sizeof( *out ) );
2497         
2498         /* set it up */
2499         out->surfaceType = MST_PATCH;
2500         if( debugSurfaces )
2501                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2502         else if( patchMeta )
2503         {
2504                 /* patch meta requires that we have nodraw patches for collision */
2505                 surfaceFlags = ds->shaderInfo->surfaceFlags;
2506                 contentFlags = ds->shaderInfo->contentFlags;
2507                 ApplySurfaceParm( "nodraw", &contentFlags, &surfaceFlags, NULL );
2508                 ApplySurfaceParm( "pointlight", &contentFlags, &surfaceFlags, NULL );
2509                 
2510                 /* we don't want this patch getting lightmapped */
2511                 VectorClear( ds->lightmapVecs[ 2 ] );
2512                 VectorClear( ds->lightmapAxis );
2513                 ds->sampleSize = 0;
2514
2515                 /* emit the new fake shader */
2516                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &contentFlags, &surfaceFlags );
2517         }
2518         else
2519                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2520         out->patchWidth = ds->patchWidth;
2521         out->patchHeight = ds->patchHeight;
2522         out->fogNum = ds->fogNum;
2523         
2524         /* RBSP */
2525         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2526         {
2527                 out->lightmapNum[ i ] = -3;
2528                 out->lightmapStyles[ i ] = LS_NONE;
2529                 out->vertexStyles[ i ] = LS_NONE;
2530         }
2531         out->lightmapStyles[ 0 ] = LS_NORMAL;
2532         out->vertexStyles[ 0 ] = LS_NORMAL;
2533         
2534         /* ydnar: gs mods: previously, the lod bounds were stored in lightmapVecs[ 0 ] and [ 1 ], moved to bounds[ 0 ] and [ 1 ] */
2535         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2536         VectorCopy( ds->bounds[ 0 ], out->lightmapVecs[ 0 ] );
2537         VectorCopy( ds->bounds[ 1 ], out->lightmapVecs[ 1 ] );
2538         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2539         
2540         /* ydnar: gs mods: clear out the plane normal */
2541         if( ds->planar == qfalse )
2542                 VectorClear( out->lightmapVecs[ 2 ] );
2543         
2544         /* emit the verts and indexes */
2545         EmitDrawVerts( ds, out );
2546         EmitDrawIndexes( ds, out );
2547         
2548         /* add to count */
2549         numSurfacesByType[ ds->type ]++;
2550 }
2551
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 static void EmitTriangleSurface( mapDrawSurface_t *ds )
2678 {
2679         int                                             i, temp;
2680         bspDrawSurface_t                *out;
2681         
2682         
2683         /* invert the surface if necessary */
2684         if( ds->backSide || ds->shaderInfo->invert )
2685         {
2686                 /* walk the indexes, reverse the triangle order */
2687                 for( i = 0; i < ds->numIndexes; i += 3 )
2688                 {
2689                         temp = ds->indexes[ i ];
2690                         ds->indexes[ i ] = ds->indexes[ i + 1 ];
2691                         ds->indexes[ i + 1 ] = temp;
2692                 }
2693                 
2694                 /* walk the verts, flip the normal */
2695                 for( i = 0; i < ds->numVerts; i++ )
2696                         VectorScale( ds->verts[ i ].normal, -1.0f, ds->verts[ i ].normal );
2697                 
2698                 /* invert facing */
2699                 VectorScale( ds->lightmapVecs[ 2 ], -1.0f, ds->lightmapVecs[ 2 ] );
2700         }
2701         
2702         /* allocate a new surface */
2703         if( numBSPDrawSurfaces == MAX_MAP_DRAW_SURFS )
2704                 Error( "MAX_MAP_DRAW_SURFS" );
2705         out = &bspDrawSurfaces[ numBSPDrawSurfaces ];
2706         ds->outputNum = numBSPDrawSurfaces;
2707         numBSPDrawSurfaces++;
2708         memset( out, 0, sizeof( *out ) );
2709         
2710         /* ydnar/sd: handle wolf et foliage surfaces */
2711         if( ds->type == SURFACE_FOLIAGE )
2712                 out->surfaceType = MST_FOLIAGE;
2713         
2714         /* ydnar: gs mods: handle lightmapped terrain (force to planar type) */
2715         //%     else if( VectorLength( ds->lightmapAxis ) <= 0.0f || ds->type == SURFACE_TRIANGLES || ds->type == SURFACE_FOGHULL || debugSurfaces )
2716         else if( (VectorLength( ds->lightmapAxis ) <= 0.0f && ds->planar == qfalse) ||
2717                 ds->type == SURFACE_TRIANGLES ||
2718                 ds->type == SURFACE_FOGHULL ||
2719                 ds->numVerts > maxLMSurfaceVerts ||
2720                 debugSurfaces )
2721                 out->surfaceType = MST_TRIANGLE_SOUP;
2722         
2723         /* set to a planar face */
2724         else
2725                 out->surfaceType = MST_PLANAR;
2726         
2727         /* set it up */
2728         if( debugSurfaces )
2729                 out->shaderNum = EmitShader( "debugsurfaces", NULL, NULL );
2730         else
2731                 out->shaderNum = EmitShader( ds->shaderInfo->shader, &ds->shaderInfo->contentFlags, &ds->shaderInfo->surfaceFlags );
2732         out->patchWidth = ds->patchWidth;
2733         out->patchHeight = ds->patchHeight;
2734         out->fogNum = ds->fogNum;
2735         
2736         /* debug inset (push each triangle vertex towards the center of each triangle it is on */
2737         if( debugInset )
2738         {
2739                 bspDrawVert_t   *a, *b, *c;
2740                 vec3_t                  cent, dir;
2741
2742                 
2743                 /* walk triangle list */
2744                 for( i = 0; i < ds->numIndexes; i += 3 )
2745                 {
2746                         /* get verts */
2747                         a = &ds->verts[ ds->indexes[ i ] ];
2748                         b = &ds->verts[ ds->indexes[ i + 1 ] ];
2749                         c = &ds->verts[ ds->indexes[ i + 2 ] ];
2750                         
2751                         /* calculate centroid */
2752                         VectorCopy( a->xyz, cent );
2753                         VectorAdd( cent, b->xyz, cent );
2754                         VectorAdd( cent, c->xyz, cent );
2755                         VectorScale( cent, 1.0f / 3.0f, cent );
2756                         
2757                         /* offset each vertex */
2758                         VectorSubtract( cent, a->xyz, dir );
2759                         VectorNormalize( dir, dir );
2760                         VectorAdd( a->xyz, dir, a->xyz );
2761                         VectorSubtract( cent, b->xyz, dir );
2762                         VectorNormalize( dir, dir );
2763                         VectorAdd( b->xyz, dir, b->xyz );
2764                         VectorSubtract( cent, c->xyz, dir );
2765                         VectorNormalize( dir, dir );
2766                         VectorAdd( c->xyz, dir, c->xyz );
2767                 }
2768         }
2769         
2770         /* RBSP */
2771         for( i = 0; i < MAX_LIGHTMAPS; i++ )
2772         {
2773                 out->lightmapNum[ i ] = -3;
2774                 out->lightmapStyles[ i ] = LS_NONE;
2775                 out->vertexStyles[ i ] = LS_NONE;
2776         }
2777         out->lightmapStyles[ 0 ] = LS_NORMAL;
2778         out->vertexStyles[ 0 ] = LS_NORMAL;
2779         
2780         /* lightmap vectors (lod bounds for patches */
2781         VectorCopy( ds->lightmapOrigin, out->lightmapOrigin );
2782         VectorCopy( ds->lightmapVecs[ 0 ], out->lightmapVecs[ 0 ] );
2783         VectorCopy( ds->lightmapVecs[ 1 ], out->lightmapVecs[ 1 ] );
2784         VectorCopy( ds->lightmapVecs[ 2 ], out->lightmapVecs[ 2 ] );
2785         
2786         /* ydnar: gs mods: clear out the plane normal */
2787         if( ds->planar == qfalse )
2788                 VectorClear( out->lightmapVecs[ 2 ] );
2789         
2790         /* optimize the surface's triangles */
2791         OptimizeTriangleSurface( ds );
2792         
2793         /* emit the verts and indexes */
2794         EmitDrawVerts( ds, out );
2795         EmitDrawIndexes( ds, out );
2796         
2797         /* add to count */
2798         numSurfacesByType[ ds->type ]++;
2799 }
2800
2801
2802
2803 /*
2804 EmitFaceSurface()
2805 emits a bsp planar winding (brush face) drawsurface
2806 */
2807
2808 static void EmitFaceSurface( mapDrawSurface_t *ds )
2809 {
2810         /* strip/fan finding was moved elsewhere */
2811         StripFaceSurface( ds );
2812         EmitTriangleSurface( ds );
2813 }
2814
2815
2816
2817 /*
2818 MakeDebugPortalSurfs_r() - ydnar
2819 generates drawsurfaces for passable portals in the bsp
2820 */
2821
2822 static void MakeDebugPortalSurfs_r( node_t *node, shaderInfo_t *si )
2823 {
2824         int                                     i, k, c, s;     
2825         portal_t                        *p;
2826         winding_t                       *w;
2827         mapDrawSurface_t        *ds;
2828         bspDrawVert_t           *dv;
2829         
2830         
2831         /* recurse if decision node */
2832         if( node->planenum != PLANENUM_LEAF)
2833         {
2834                 MakeDebugPortalSurfs_r( node->children[ 0 ], si );
2835                 MakeDebugPortalSurfs_r( node->children[ 1 ], si );
2836                 return;
2837         }
2838         
2839         /* don't bother with opaque leaves */
2840         if( node->opaque )
2841                 return;
2842         
2843         /* walk the list of portals */
2844         for( c = 0, p = node->portals; p != NULL; c++, p = p->next[ s ] )
2845         {
2846                 /* get winding and side even/odd */
2847                 w = p->winding;
2848                 s = (p->nodes[ 1 ] == node);
2849                 
2850                 /* is this a valid portal for this leaf? */
2851                 if( w && p->nodes[ 0 ] == node )
2852                 {
2853                         /* is this portal passable? */
2854                         if( PortalPassable( p ) == qfalse )
2855                                 continue;
2856                         
2857                         /* check max points */
2858                         if( w->numpoints > 64 )
2859                                 Error( "MakePortalSurfs_r: w->numpoints = %d", w->numpoints );
2860                         
2861                         /* allocate a drawsurface */
2862                         ds = AllocDrawSurface( SURFACE_FACE );
2863                         ds->shaderInfo = si;
2864                         ds->planar = qtrue;
2865                         ds->sideRef = AllocSideRef( p->side, NULL );
2866                         ds->planeNum = FindFloatPlane( p->plane.normal, p->plane.dist, 0, NULL );
2867                         VectorCopy( p->plane.normal, ds->lightmapVecs[ 2 ] );
2868                         ds->fogNum = -1;
2869                         ds->numVerts = w->numpoints;
2870                         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
2871                         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
2872                         
2873                         /* walk the winding */
2874                         for( i = 0; i < ds->numVerts; i++ )
2875                         {
2876                                 /* get vert */
2877                                 dv = ds->verts + i;
2878                                 
2879                                 /* set it */
2880                                 VectorCopy( w->p[ i ], dv->xyz );
2881                                 VectorCopy( p->plane.normal, dv->normal );
2882                                 dv->st[ 0 ] = 0;
2883                                 dv->st[ 1 ] = 0;
2884                                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
2885                                 {
2886                                         VectorCopy( debugColors[ c % 12 ], dv->color[ k ] );
2887                                         dv->color[ k ][ 3 ] = 32;
2888                                 }
2889                         }
2890                 }
2891         }
2892 }
2893
2894
2895
2896 /*
2897 MakeDebugPortalSurfs() - ydnar
2898 generates drawsurfaces for passable portals in the bsp
2899 */
2900
2901 void MakeDebugPortalSurfs( tree_t *tree )
2902 {
2903         shaderInfo_t    *si;
2904         
2905         
2906         /* note it */
2907         Sys_FPrintf( SYS_VRB, "--- MakeDebugPortalSurfs ---\n" );
2908         
2909         /* get portal debug shader */
2910         si = ShaderInfoForShader( "debugportals" );
2911         
2912         /* walk the tree */
2913         MakeDebugPortalSurfs_r( tree->headnode, si );
2914 }
2915
2916
2917
2918 /*
2919 MakeFogHullSurfs()
2920 generates drawsurfaces for a foghull (this MUST use a sky shader)
2921 */
2922
2923 void MakeFogHullSurfs( entity_t *e, tree_t *tree, char *shader )
2924 {
2925         shaderInfo_t            *si;
2926         mapDrawSurface_t        *ds;
2927         vec3_t                          fogMins, fogMaxs;
2928         int                                     i, indexes[] =
2929                                                 {
2930                                                         0, 1, 2, 0, 2, 3,
2931                                                         4, 7, 5, 5, 7, 6,
2932                                                         1, 5, 6, 1, 6, 2,
2933                                                         0, 4, 5, 0, 5, 1,
2934                                                         2, 6, 7, 2, 7, 3,
2935                                                         3, 7, 4, 3, 4, 0
2936                                                 };
2937
2938         
2939         /* dummy check */
2940         if( shader == NULL || shader[ 0 ] == '\0' )
2941                 return;
2942         
2943         /* note it */
2944         Sys_FPrintf( SYS_VRB, "--- MakeFogHullSurfs ---\n" );
2945         
2946         /* get hull bounds */
2947         VectorCopy( mapMins, fogMins );
2948         VectorCopy( mapMaxs, fogMaxs );
2949         for( i = 0; i < 3; i++ )
2950         {
2951                 fogMins[ i ] -= 128;
2952                 fogMaxs[ i ] += 128;
2953         }
2954         
2955         /* get foghull shader */
2956         si = ShaderInfoForShader( shader );
2957         
2958         /* allocate a drawsurface */
2959         ds = AllocDrawSurface( SURFACE_FOGHULL );
2960         ds->shaderInfo = si;
2961         ds->fogNum = -1;
2962         ds->numVerts = 8;
2963         ds->verts = safe_malloc( ds->numVerts * sizeof( *ds->verts ) );
2964         memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) );
2965         ds->numIndexes = 36;
2966         ds->indexes = safe_malloc( ds->numIndexes * sizeof( *ds->indexes ) );
2967         memset( ds->indexes, 0, ds->numIndexes * sizeof( *ds->indexes ) );
2968         
2969         /* set verts */
2970         VectorSet( ds->verts[ 0 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
2971         VectorSet( ds->verts[ 1 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
2972         VectorSet( ds->verts[ 2 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMins[ 2 ] );
2973         VectorSet( ds->verts[ 3 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMins[ 2 ] );
2974         
2975         VectorSet( ds->verts[ 4 ].xyz, fogMins[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
2976         VectorSet( ds->verts[ 5 ].xyz, fogMins[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
2977         VectorSet( ds->verts[ 6 ].xyz, fogMaxs[ 0 ], fogMaxs[ 1 ], fogMaxs[ 2 ] );
2978         VectorSet( ds->verts[ 7 ].xyz, fogMaxs[ 0 ], fogMins[ 1 ], fogMaxs[ 2 ] );
2979         
2980         /* set indexes */
2981         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( *ds->indexes ) );
2982 }
2983
2984
2985
2986 /*
2987 BiasSurfaceTextures()
2988 biases a surface's texcoords as close to 0 as possible
2989 */
2990
2991 void BiasSurfaceTextures( mapDrawSurface_t *ds )
2992 {
2993         int             i;
2994         
2995         
2996         /* calculate the surface texture bias */
2997         CalcSurfaceTextureRange( ds );
2998         
2999         /* don't bias globaltextured shaders */
3000         if( ds->shaderInfo->globalTexture )
3001                 return;
3002         
3003         /* bias the texture coordinates */
3004         for( i = 0; i < ds->numVerts; i++ )
3005         {
3006                 ds->verts[ i ].st[ 0 ] += ds->bias[ 0 ];
3007                 ds->verts[ i ].st[ 1 ] += ds->bias[ 1 ];
3008         }
3009 }
3010
3011
3012
3013 /*
3014 AddSurfaceModelsToTriangle_r()
3015 adds models to a specified triangle, returns the number of models added
3016 */
3017
3018 int AddSurfaceModelsToTriangle_r( mapDrawSurface_t *ds, surfaceModel_t *model, bspDrawVert_t **tri )
3019 {
3020         bspDrawVert_t   mid, *tri2[ 3 ];
3021         int                             max, n, localNumSurfaceModels;
3022         
3023         
3024         /* init */
3025         localNumSurfaceModels = 0;
3026         
3027         /* subdivide calc */
3028         {
3029                 int                     i;
3030                 float           *a, *b, dx, dy, dz, dist, maxDist;
3031                 
3032                 
3033                 /* find the longest edge and split it */
3034                 max = -1;
3035                 maxDist = 0.0f;
3036                 for( i = 0; i < 3; i++ )
3037                 {
3038                         /* get verts */
3039                         a = tri[ i ]->xyz;
3040                         b = tri[ (i + 1) % 3 ]->xyz;
3041                         
3042                         /* get dists */
3043                         dx = a[ 0 ] - b[ 0 ];
3044                         dy = a[ 1 ] - b[ 1 ];
3045                         dz = a[ 2 ] - b[ 2 ];
3046                         dist = (dx * dx) + (dy * dy) + (dz * dz);
3047                         
3048                         /* longer? */
3049                         if( dist > maxDist )
3050                         {
3051                                 maxDist = dist;
3052                                 max = i;
3053                         }
3054                 }
3055                 
3056                 /* is the triangle small enough? */
3057                 if( max < 0 || maxDist <= (model->density * model->density) )
3058                 {
3059                         float   odds, r, angle;
3060                         vec3_t  origin, normal, scale, axis[ 3 ], angles;
3061                         m4x4_t  transform, temp;
3062
3063                         
3064                         /* roll the dice (model's odds scaled by vertex alpha) */
3065                         odds = model->odds * (tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ] + tri[ 0 ]->color[ 0 ][ 3 ]) / 765.0f;
3066                         r = Random();
3067                         if( r > model->odds )
3068                                 return 0;
3069                         
3070                         /* calculate scale */
3071                         r = model->minScale + Random() * (model->maxScale - model->minScale);
3072                         VectorSet( scale, r, r, r );
3073                         
3074                         /* calculate angle */
3075                         angle = model->minAngle + Random() * (model->maxAngle - model->minAngle);
3076                         
3077                         /* calculate average origin */
3078                         VectorCopy( tri[ 0 ]->xyz, origin );
3079                         VectorAdd( origin, tri[ 1 ]->xyz, origin );
3080                         VectorAdd( origin, tri[ 2 ]->xyz, origin );
3081                         VectorScale( origin, (1.0f / 3.0f), origin );
3082                         
3083                         /* clear transform matrix */
3084                         m4x4_identity( transform );
3085
3086                         /* handle oriented models */
3087                         if( model->oriented )
3088                         {
3089                                 /* set angles */
3090                                 VectorSet( angles, 0.0f, 0.0f, angle );
3091                                 
3092                                 /* calculate average normal */
3093                                 VectorCopy( tri[ 0 ]->normal, normal );
3094                                 VectorAdd( normal, tri[ 1 ]->normal, normal );
3095                                 VectorAdd( normal, tri[ 2 ]->normal, normal );
3096                                 if( VectorNormalize( normal, axis[ 2 ] ) == 0.0f )
3097                                         VectorCopy( tri[ 0 ]->normal, axis[ 2 ] );
3098                                 
3099                                 /* make perpendicular vectors */
3100                                 MakeNormalVectors( axis[ 2 ], axis[ 1 ], axis[ 0 ] );
3101                                 
3102                                 /* copy to matrix */
3103                                 m4x4_identity( temp );
3104                                 temp[ 0 ] = axis[ 0 ][ 0 ];     temp[ 1 ] = axis[ 0 ][ 1 ];     temp[ 2 ] = axis[ 0 ][ 2 ];
3105                                 temp[ 4 ] = axis[ 1 ][ 0 ];     temp[ 5 ] = axis[ 1 ][ 1 ];     temp[ 6 ] = axis[ 1 ][ 2 ];
3106                                 temp[ 8 ] = axis[ 2 ][ 0 ];     temp[ 9 ] = axis[ 2 ][ 1 ];     temp[ 10 ] = axis[ 2 ][ 2 ];
3107                                 
3108                                 /* scale */
3109                                 m4x4_scale_by_vec3( temp, scale );
3110                                 
3111                                 /* rotate around z axis */
3112                                 m4x4_rotate_by_vec3( temp, angles, eXYZ );
3113                                 
3114                                 /* translate */
3115                                 m4x4_translate_by_vec3( transform, origin );
3116                                 
3117                                 /* tranform into axis space */
3118                                 m4x4_multiply_by_m4x4( transform, temp );
3119                         }
3120                         
3121                         /* handle z-up models */
3122                         else
3123                         {
3124                                 /* set angles */
3125                                 VectorSet( angles, 0.0f, 0.0f, angle );
3126                                 
3127                                 /* set matrix */
3128                                 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
3129                         }
3130                         
3131                         /* insert the model */
3132                         InsertModel( (char *) model->model, 0, transform, NULL, ds->celShader, ds->entityNum, ds->castShadows, ds->recvShadows, 0, ds->lightmapScale );
3133                         
3134                         /* return to sender */
3135                         return 1;
3136                 }
3137         }
3138         
3139         /* split the longest edge and map it */
3140         LerpDrawVert( tri[ max ], tri[ (max + 1) % 3 ], &mid );
3141         
3142         /* recurse to first triangle */
3143         VectorCopy( tri, tri2 );
3144         tri2[ max ] = &mid;
3145         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3146         if( n < 0 )
3147                 return n;
3148         localNumSurfaceModels += n;
3149         
3150         /* recurse to second triangle */
3151         VectorCopy( tri, tri2 );
3152         tri2[ (max + 1) % 3 ] = &mid;
3153         n = AddSurfaceModelsToTriangle_r( ds, model, tri2 );
3154         if( n < 0 )
3155                 return n;
3156         localNumSurfaceModels += n;
3157         
3158         /* return count */
3159         return localNumSurfaceModels;
3160 }
3161
3162
3163
3164 /*
3165 AddSurfaceModels()
3166 adds a surface's shader models to the surface
3167 */
3168
3169 int AddSurfaceModels( mapDrawSurface_t *ds )
3170 {
3171         surfaceModel_t  *model;
3172         int                             i, x, y, n, pw[ 5 ], r, localNumSurfaceModels, iterations;
3173         mesh_t                  src, *mesh, *subdivided;
3174         bspDrawVert_t   centroid, *tri[ 3 ];
3175         float                   alpha;
3176         
3177         
3178         /* dummy check */
3179         if( ds == NULL || ds->shaderInfo == NULL || ds->shaderInfo->surfaceModel == NULL )
3180                 return 0;
3181         
3182         /* init */
3183         localNumSurfaceModels = 0;
3184         
3185         /* walk the model list */
3186         for( model = ds->shaderInfo->surfaceModel; model != NULL; model = model->next )
3187         {
3188                 /* switch on type */
3189                 switch( ds->type )
3190                 {
3191                         /* handle brush faces and decals */
3192                         case SURFACE_FACE:
3193                         case SURFACE_DECAL:
3194                                 /* calculate centroid */
3195                                 memset( &centroid, 0, sizeof( centroid ) );
3196                                 alpha = 0.0f;
3197                                 
3198                                 /* walk verts */
3199                                 for( i = 0; i < ds->numVerts; i++ )
3200                                 {
3201                                         VectorAdd( centroid.xyz, ds->verts[ i ].xyz, centroid.xyz );
3202                                         VectorAdd( centroid.normal, ds->verts[ i ].normal, centroid.normal );
3203                                         centroid.st[ 0 ] += ds->verts[ i ].st[ 0 ];
3204                                         centroid.st[ 1 ] += ds->verts[ i ].st[ 1 ];
3205                                         alpha += ds->verts[ i ].color[ 0 ][ 3 ];
3206                                 }
3207                                 
3208                                 /* average */
3209                                 centroid.xyz[ 0 ] /= ds->numVerts;
3210                                 centroid.xyz[ 1 ] /= ds->numVerts;
3211                                 centroid.xyz[ 2 ] /= ds->numVerts;
3212                                 if( VectorNormalize( centroid.normal, centroid.normal ) == 0.0f )
3213                                         VectorCopy( ds->verts[ 0 ].normal, centroid.normal );
3214                                 centroid.st[ 0 ]  /= ds->numVerts;
3215                                 centroid.st[ 1 ]  /= ds->numVerts;
3216                                 alpha /= ds->numVerts;
3217                                 centroid.color[ 0 ][ 0 ] = 0xFF;
3218                                 centroid.color[ 0 ][ 1 ] = 0xFF;
3219                                 centroid.color[ 0 ][ 2 ] = 0xFF;
3220                                 centroid.color[ 0 ][ 2 ] = (alpha > 255.0f ? 0xFF : alpha);
3221                                 
3222                                 /* head vert is centroid */
3223                                 tri[ 0 ] = &centroid;
3224                                 
3225                                 /* walk fanned triangles */
3226                                 for( i = 0; i < ds->numVerts; i++ )
3227                                 {
3228                                         /* set triangle */
3229                                         tri[ 1 ] = &ds->verts[ i ];
3230                                         tri[ 2 ] = &ds->verts[ (i + 1) % ds->numVerts ];
3231                                         
3232                                         /* create models */
3233                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3234                                         if( n < 0 )
3235                                                 return n;
3236                                         localNumSurfaceModels += n;
3237                                 }
3238                                 break;
3239                         
3240                         /* handle patches */
3241                         case SURFACE_PATCH:
3242                                 /* subdivide the surface */
3243                                 src.width = ds->patchWidth;
3244                                 src.height = ds->patchHeight;
3245                                 src.verts = ds->verts;
3246                                 //%     subdivided = SubdivideMesh( src, 8.0f, 512 );
3247                                 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
3248                                 subdivided = SubdivideMesh2( src, iterations );
3249                                 
3250                                 /* fit it to the curve and remove colinear verts on rows/columns */
3251                                 PutMeshOnCurve( *subdivided );
3252                                 mesh = RemoveLinearMeshColumnsRows( subdivided );
3253                                 FreeMesh( subdivided );
3254                                 
3255                                 /* subdivide each quad to place the models */
3256                                 for( y = 0; y < (mesh->height - 1); y++ )
3257                                 {
3258                                         for( x = 0; x < (mesh->width - 1); x++ )
3259                                         {
3260                                                 /* set indexes */
3261                                                 pw[ 0 ] = x + (y * mesh->width);
3262                                                 pw[ 1 ] = x + ((y + 1) * mesh->width);
3263                                                 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
3264                                                 pw[ 3 ] = x + 1 + (y * mesh->width);
3265                                                 pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
3266                                                 
3267                                                 /* set radix */
3268                                                 r = (x + y) & 1;
3269                                                 
3270                                                 /* triangle 1 */
3271                                                 tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3272                                                 tri[ 1 ] = &mesh->verts[ pw[ r + 1 ] ];
3273                                                 tri[ 2 ] = &mesh->verts[ pw[ r + 2 ] ];
3274                                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3275                                                 if( n < 0 )
3276                                                         return n;
3277                                                 localNumSurfaceModels += n;
3278                                                 
3279                                                 /* triangle 2 */
3280                                                 tri[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
3281                                                 tri[ 1 ] = &mesh->verts[ pw[ r + 2 ] ];
3282                                                 tri[ 2 ] = &mesh->verts[ pw[ r + 3 ] ];
3283                                                 n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3284                                                 if( n < 0 )
3285                                                         return n;
3286                                                 localNumSurfaceModels += n;
3287                                         }
3288                                 }
3289                                 
3290                                 /* free the subdivided mesh */
3291                                 FreeMesh( mesh );
3292                                 break;
3293                         
3294                         /* handle triangle surfaces */
3295                         case SURFACE_TRIANGLES:
3296                         case SURFACE_FORCED_META:
3297                         case SURFACE_META:
3298                                 /* walk the triangle list */
3299                                 for( i = 0; i < ds->numIndexes; i += 3 )
3300                                 {
3301                                         tri[ 0 ] = &ds->verts[ ds->indexes[ i ] ];
3302                                         tri[ 1 ] = &ds->verts[ ds->indexes[ i + 1 ] ];
3303                                         tri[ 2 ] = &ds->verts[ ds->indexes[ i + 2 ] ];
3304                                         n = AddSurfaceModelsToTriangle_r( ds, model, tri );
3305                                         if( n < 0 )
3306                                                 return n;
3307                                         localNumSurfaceModels += n;
3308                                 }