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