]> icculus.org git repositories - divverent/netradiant.git/blob - tools/quake3/q3map2/surface_meta.c
new options:
[divverent/netradiant.git] / tools / quake3 / q3map2 / surface_meta.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_META_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 #define LIGHTMAP_EXCEEDED       -1
42 #define S_EXCEEDED                      -2
43 #define T_EXCEEDED                      -3
44 #define ST_EXCEEDED                     -4
45 #define UNSUITABLE_TRIANGLE     -10
46 #define VERTS_EXCEEDED          -1000
47 #define INDEXES_EXCEEDED        -2000
48
49 #define GROW_META_VERTS         1024
50 #define GROW_META_TRIANGLES     1024
51
52 static int                                      numMetaSurfaces, numPatchMetaSurfaces;
53
54 static int                                      maxMetaVerts = 0;
55 static int                                      numMetaVerts = 0;
56 static int                                      firstSearchMetaVert = 0;
57 static bspDrawVert_t            *metaVerts = NULL;
58
59 static int                                      maxMetaTriangles = 0;
60 static int                                      numMetaTriangles = 0;
61 static metaTriangle_t           *metaTriangles = NULL;
62
63
64
65 /*
66 ClearMetaVertexes()
67 called before staring a new entity to clear out the triangle list
68 */
69
70 void ClearMetaTriangles( void )
71 {
72         numMetaVerts = 0;
73         numMetaTriangles = 0;
74 }
75
76
77
78 /*
79 FindMetaVertex()
80 finds a matching metavertex in the global list, returning its index
81 */
82
83 static int FindMetaVertex( bspDrawVert_t *src )
84 {
85         int                     i;
86         bspDrawVert_t   *v, *temp;
87         
88         
89         /* try to find an existing drawvert */
90         for( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
91         {
92                 if( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 )
93                         return i;
94         }
95         
96         /* enough space? */
97         if( numMetaVerts >= maxMetaVerts )
98         {
99                 /* reallocate more room */
100                 maxMetaVerts += GROW_META_VERTS;
101                 temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );
102                 if( metaVerts != NULL )
103                 {
104                         memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );
105                         free( metaVerts );
106                 }
107                 metaVerts = temp;
108         }
109         
110         /* add the triangle */
111         memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );
112         numMetaVerts++;
113         
114         /* return the count */
115         return (numMetaVerts - 1);
116 }
117
118
119
120 /*
121 AddMetaTriangle()
122 adds a new meta triangle, allocating more memory if necessary
123 */
124
125 static int AddMetaTriangle( void )
126 {
127         metaTriangle_t  *temp;
128         
129         
130         /* enough space? */
131         if( numMetaTriangles >= maxMetaTriangles )
132         {
133                 /* reallocate more room */
134                 maxMetaTriangles += GROW_META_TRIANGLES;
135                 temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );
136                 if( metaTriangles != NULL )
137                 {
138                         memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );
139                         free( metaTriangles );
140                 }
141                 metaTriangles = temp;
142         }
143         
144         /* increment and return */
145         numMetaTriangles++;
146         return numMetaTriangles - 1;
147 }
148
149
150
151 /*
152 FindMetaTriangle()
153 finds a matching metatriangle in the global list,
154 otherwise adds it and returns the index to the metatriangle
155 */
156
157 int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum )
158 {
159         int                             triIndex;
160         vec3_t                  dir;
161
162         
163         
164         /* detect degenerate triangles fixme: do something proper here */
165         VectorSubtract( a->xyz, b->xyz, dir );
166         if( VectorLength( dir ) < 0.125f )
167                 return -1;
168         VectorSubtract( b->xyz, c->xyz, dir );
169         if( VectorLength( dir ) < 0.125f )
170                 return -1;
171         VectorSubtract( c->xyz, a->xyz, dir );
172         if( VectorLength( dir ) < 0.125f )
173                 return -1;
174         
175         /* find plane */
176         if( planeNum >= 0 )
177         {
178                 /* because of precision issues with small triangles, try to use the specified plane */
179                 src->planeNum = planeNum;
180                 VectorCopy( mapplanes[ planeNum ].normal, src->plane );
181                 src->plane[ 3 ] = mapplanes[ planeNum ].dist;
182         }
183         else
184         {
185                 /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */
186                 src->planeNum = -1;
187                 if( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse )
188                         return -1;
189         }
190         
191         /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */
192         if( VectorLength( a->normal ) <= 0.0f )
193                 VectorCopy( src->plane, a->normal );
194         if( VectorLength( b->normal ) <= 0.0f )
195                 VectorCopy( src->plane, b->normal );
196         if( VectorLength( c->normal ) <= 0.0f )
197                 VectorCopy( src->plane, c->normal );
198         
199         /* ydnar 2002-10-04: set lightmap axis if not already set */
200         if( !(src->si->compileFlags & C_VERTEXLIT) &&
201                 src->lightmapAxis[ 0 ] == 0.0f && src->lightmapAxis[ 1 ] == 0.0f && src->lightmapAxis[ 2 ] == 0.0f )
202         {
203                 /* the shader can specify an explicit lightmap axis */
204                 if( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] )
205                         VectorCopy( src->si->lightmapAxis, src->lightmapAxis );
206                 
207                 /* new axis-finding code */
208                 else
209                         CalcLightmapAxis( src->plane, src->lightmapAxis );
210         }
211         
212         /* fill out the src triangle */
213         src->indexes[ 0 ] = FindMetaVertex( a );
214         src->indexes[ 1 ] = FindMetaVertex( b );
215         src->indexes[ 2 ] = FindMetaVertex( c );
216         
217         /* try to find an existing triangle */
218         #ifdef USE_EXHAUSTIVE_SEARCH
219         {
220                 int                             i;
221                 metaTriangle_t  *tri;
222                 
223                 
224                 for( i = 0, tri = metaTriangles; i < numMetaTriangles; i++, tri++ )
225                 {
226                         if( memcmp( src, tri, sizeof( metaTriangle_t ) ) == 0 )
227                                 return i;
228                 }
229         }
230         #endif
231         
232         /* get a new triangle */
233         triIndex = AddMetaTriangle();
234         
235         /* add the triangle */
236         memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );
237         
238         /* return the triangle index */
239         return triIndex;
240 }
241
242
243
244 /*
245 SurfaceToMetaTriangles()
246 converts a classified surface to metatriangles
247 */
248
249 static void SurfaceToMetaTriangles( mapDrawSurface_t *ds )
250 {
251         int                             i;
252         metaTriangle_t  src;
253         bspDrawVert_t   a, b, c;
254         
255         
256         /* only handle certain types of surfaces */
257         if( ds->type != SURFACE_FACE &&
258                 ds->type != SURFACE_META &&
259                 ds->type != SURFACE_FORCED_META &&
260                 ds->type != SURFACE_DECAL )
261                 return;
262         
263         /* speed at the expense of memory */
264         firstSearchMetaVert = numMetaVerts;
265         
266         /* only handle valid surfaces */
267         if( ds->type != SURFACE_BAD && ds->numVerts >= 3 && ds->numIndexes >= 3 )
268         {
269                 /* walk the indexes and create triangles */
270                 for( i = 0; i < ds->numIndexes; i += 3 )
271                 {
272                         /* sanity check the indexes */
273                         if( ds->indexes[ i ] == ds->indexes[ i + 1 ] ||
274                                 ds->indexes[ i ] == ds->indexes[ i + 2 ] ||
275                                 ds->indexes[ i + 1 ] == ds->indexes[ i + 2 ] )
276                         {
277                                 //%     Sys_Printf( "%d! ", ds->numVerts );
278                                 continue;
279                         }
280                         
281                         /* build a metatriangle */
282                         src.si = ds->shaderInfo;
283                         src.side = (ds->sideRef != NULL ? ds->sideRef->side : NULL);
284                         src.entityNum = ds->entityNum;
285                         src.surfaceNum = ds->surfaceNum;
286                         src.planeNum = ds->planeNum;
287                         src.castShadows = ds->castShadows;
288                         src.recvShadows = ds->recvShadows;
289                         src.fogNum = ds->fogNum;
290                         src.sampleSize = ds->sampleSize;
291                         VectorCopy( ds->lightmapAxis, src.lightmapAxis );
292                         
293                         /* copy drawverts */
294                         memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );
295                         memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );
296                         memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );
297                         FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );
298                 }
299                 
300                 /* add to count */
301                 numMetaSurfaces++;
302         }
303         
304         /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */
305         ClearSurface( ds );
306 }
307
308
309
310 /*
311 TriangulatePatchSurface()
312 creates triangles from a patch
313 */
314
315 void TriangulatePatchSurface( entity_t *e , mapDrawSurface_t *ds )
316 {
317         int                                     iterations, x, y, pw[ 5 ], r;
318         mapDrawSurface_t        *dsNew;
319         mesh_t                          src, *subdivided, *mesh;
320         int                                     forcePatchMeta;
321         int                                     patchQuality;
322         int                                     patchSubdivision;
323
324         /* vortex: _patchMeta, _patchQuality, _patchSubdivide support */
325         forcePatchMeta = IntForKey(e, "_patchMeta" );
326         if (!forcePatchMeta)
327                 forcePatchMeta = IntForKey(e, "patchMeta" );
328         patchQuality = IntForKey(e, "_patchQuality" );
329         if (!patchQuality)
330                 patchQuality = IntForKey(e, "patchQuality" );
331         if (!patchQuality)
332                 patchQuality = 1.0;
333         patchSubdivision = IntForKey(e, "_patchSubdivide" );
334         if (!patchSubdivision)
335                 patchSubdivision = IntForKey(e, "patchSubdivide" );
336
337         /* try to early out */
338         if(ds->numVerts == 0 || ds->type != SURFACE_PATCH || ( patchMeta == qfalse && !forcePatchMeta) )
339                 return;
340         /* make a mesh from the drawsurf */ 
341         src.width = ds->patchWidth;
342         src.height = ds->patchHeight;
343         src.verts = ds->verts;
344         //%     subdivided = SubdivideMesh( src, 8, 999 );
345         if (patchSubdivision)
346                 iterations = IterationsForCurve( ds->longestCurve, patchSubdivision );
347         else
348                 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions / patchQuality );
349
350         subdivided = SubdivideMesh2( src, iterations ); //%     ds->maxIterations
351         
352         /* fit it to the curve and remove colinear verts on rows/columns */
353         PutMeshOnCurve( *subdivided );
354         mesh = RemoveLinearMeshColumnsRows( subdivided );
355         FreeMesh( subdivided );
356         //% MakeMeshNormals( mesh );
357         
358         /* make a copy of the drawsurface */
359         dsNew = AllocDrawSurface( SURFACE_META );
360         memcpy( dsNew, ds, sizeof( *ds ) );
361         
362         /* if the patch is nonsolid, then discard it */
363         if( !(ds->shaderInfo->compileFlags & C_SOLID) )
364                 ClearSurface( ds );
365         
366         /* set new pointer */
367         ds = dsNew;
368         
369         /* basic transmogrification */
370         ds->type = SURFACE_META;
371         ds->numIndexes = 0;
372         ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );
373         
374         /* copy the verts in */
375         ds->numVerts = (mesh->width * mesh->height);
376         ds->verts = mesh->verts;
377         
378         /* iterate through the mesh quads */
379         for( y = 0; y < (mesh->height - 1); y++ )
380         {
381                 for( x = 0; x < (mesh->width - 1); x++ )
382                 {
383                         /* set indexes */
384                         pw[ 0 ] = x + (y * mesh->width);
385                         pw[ 1 ] = x + ((y + 1) * mesh->width);
386                         pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
387                         pw[ 3 ] = x + 1 + (y * mesh->width);
388                         pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
389                         
390                         /* set radix */
391                         r = (x + y) & 1;
392                         
393                         /* make first triangle */
394                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
395                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];
396                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
397                         
398                         /* make second triangle */
399                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
400                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
401                         ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];
402                 }
403         }
404         
405         /* free the mesh, but not the verts */
406         free( mesh );
407         
408         /* add to count */
409         numPatchMetaSurfaces++;
410         
411         /* classify it */
412         ClassifySurfaces( 1, ds );
413 }
414
415
416
417 /*
418 FanFaceSurface() - ydnar
419 creates a tri-fan from a brush face winding
420 loosely based on SurfaceAsTriFan()
421 */
422
423 void FanFaceSurface( mapDrawSurface_t *ds )
424 {
425         int                             i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
426         bspDrawVert_t   *verts, *centroid, *dv;
427         double                  iv;
428         
429         
430         /* try to early out */
431         if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
432                 return;
433         
434         /* add a new vertex at the beginning of the surface */
435         verts = safe_malloc( (ds->numVerts + 1) * sizeof( bspDrawVert_t ) );
436         memset( verts, 0, sizeof( bspDrawVert_t ) );
437         memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
438         free( ds->verts );
439         ds->verts = verts;
440         
441         /* add up the drawverts to create a centroid */
442         centroid = &verts[ 0 ];
443         memset( color, 0,  4 * MAX_LIGHTMAPS * sizeof( int ) );
444         for( i = 1, dv = &verts[ 1 ]; i < (ds->numVerts + 1); i++, dv++ )
445         {
446                 VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
447                 VectorAdd( centroid->normal, dv->normal, centroid->normal );
448                 for( j = 0; j < 4; j++ )
449                 {
450                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
451                                 color[ k ][ j ] += dv->color[ k ][ j ];
452                         if( j < 2 )
453                         {
454                                 centroid->st[ j ] += dv->st[ j ];
455                                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
456                                         centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
457                         }
458                 }
459         }
460         
461         /* average the centroid */
462         iv = 1.0f / ds->numVerts;
463         VectorScale( centroid->xyz, iv, centroid->xyz );
464         if( VectorNormalize( centroid->normal, centroid->normal ) <= 0 )
465                 VectorCopy( verts[ 1 ].normal, centroid->normal );
466         for( j = 0; j < 4; j++ )
467         {
468                 for( k = 0; k < MAX_LIGHTMAPS; k++ )
469                 {
470                         color[ k ][ j ] /= ds->numVerts;
471                         centroid->color[ k ][ j ] = (color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255);
472                 }
473                 if( j < 2 )
474                 {
475                         centroid->st[ j ] *= iv;
476                         for( k = 0; k < MAX_LIGHTMAPS; k++ )
477                                 centroid->lightmap[ k ][ j ] *= iv;
478                 }
479         }
480         
481         /* add to vert count */
482         ds->numVerts++;
483         
484         /* fill indexes in triangle fan order */
485         ds->numIndexes = 0;
486         ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
487         for( i = 1; i < ds->numVerts; i++ )
488         {
489                 a = 0;
490                 b = i;
491                 c = (i + 1) % ds->numVerts;
492                 c = c ? c : 1;
493                 ds->indexes[ ds->numIndexes++ ] = a;
494                 ds->indexes[ ds->numIndexes++ ] = b;
495                 ds->indexes[ ds->numIndexes++ ] = c;
496         }
497         
498         /* add to count */
499         numFanSurfaces++;
500
501         /* classify it */
502         ClassifySurfaces( 1, ds );
503 }
504
505
506
507 /*
508 StripFaceSurface() - ydnar
509 attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
510 based on SurfaceAsTriStrip()
511 */
512
513 #define MAX_INDEXES             1024
514
515 void StripFaceSurface( mapDrawSurface_t *ds ) 
516 {
517         int                     i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
518         vec_t           *v1, *v2;
519         
520         
521         /* try to early out  */
522         if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
523                 return;
524         
525         /* is this a simple triangle? */
526         if( ds->numVerts == 3 )
527         {
528                 numIndexes = 3;
529                 VectorSet( indexes, 0, 1, 2 );
530         }
531         else
532         {
533                 /* ydnar: find smallest coordinate */
534                 least = 0;
535                 if( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse )
536                 {
537                         for( i = 0; i < ds->numVerts; i++ )
538                         {
539                                 /* get points */
540                                 v1 = ds->verts[ i ].xyz;
541                                 v2 = ds->verts[ least ].xyz;
542                                 
543                                 /* compare */
544                                 if( v1[ 0 ] < v2[ 0 ] ||
545                                         (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ]) ||
546                                         (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ]) )
547                                         least = i;
548                         }
549                 }
550                 
551                 /* determine the triangle strip order */
552                 numIndexes = (ds->numVerts - 2) * 3;
553                 if( numIndexes > MAX_INDEXES )
554                         Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
555                 
556                 /* try all possible orderings of the points looking for a non-degenerate strip order */
557                 for( r = 0; r < ds->numVerts; r++ )
558                 {
559                         /* set rotation */
560                         rotate = (r + least) % ds->numVerts;
561                         
562                         /* walk the winding in both directions */
563                         for( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
564                         {
565                                 /* make indexes */
566                                 a = (ds->numVerts - 1 - i + rotate) % ds->numVerts;
567                                 b = (i + rotate ) % ds->numVerts;
568                                 c = (ds->numVerts - 2 - i + rotate) % ds->numVerts;
569                                 
570                                 /* test this triangle */
571                                 if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
572                                         break;
573                                 indexes[ ni++ ] = a;
574                                 indexes[ ni++ ] = b;
575                                 indexes[ ni++ ] = c;
576                                 
577                                 /* handle end case */
578                                 if( i + 1 != ds->numVerts - 1 - i )
579                                 {
580                                         /* make indexes */
581                                         a = (ds->numVerts - 2 - i + rotate ) % ds->numVerts;
582                                         b = (i + rotate ) % ds->numVerts;
583                                         c = (i + 1 + rotate ) % ds->numVerts;
584                                         
585                                         /* test triangle */
586                                         if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
587                                                 break;
588                                         indexes[ ni++ ] = a;
589                                         indexes[ ni++ ] = b;
590                                         indexes[ ni++ ] = c;
591                                 }
592                         }
593                         
594                         /* valid strip? */
595                         if( ni == numIndexes )
596                                 break;
597                 }
598                 
599                 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
600                 if( ni < numIndexes )
601                 {
602                         FanFaceSurface( ds );
603                         return;
604                 }
605         }
606         
607         /* copy strip triangle indexes */
608         ds->numIndexes = numIndexes;
609         ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
610         memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
611         
612         /* add to count */
613         numStripSurfaces++;
614         
615         /* classify it */
616         ClassifySurfaces( 1, ds );
617 }
618  
619  
620 /*
621 EmitMetaStatictics
622 vortex: prints meta statistics in general output
623 */
624
625 void EmitMetaStats()
626 {
627         Sys_Printf( "--- EmitMetaStats ---\n" );
628         Sys_Printf( "%9d total meta surfaces\n", numMetaSurfaces );
629         Sys_Printf( "%9d stripped surfaces\n", numStripSurfaces );
630         Sys_Printf( "%9d fanned surfaces\n", numFanSurfaces );
631         Sys_Printf( "%9d patch meta surfaces\n", numPatchMetaSurfaces );
632         Sys_Printf( "%9d meta verts\n", numMetaVerts );
633         Sys_Printf( "%9d meta triangles\n", numMetaTriangles );
634 }
635
636 /*
637 MakeEntityMetaTriangles()
638 builds meta triangles from brush faces (tristrips and fans)
639 */
640
641 void MakeEntityMetaTriangles( entity_t *e )
642 {
643         int                                     i, f, fOld, start;
644         mapDrawSurface_t        *ds;
645         
646         
647         /* note it */
648         Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
649         
650         /* init pacifier */
651         fOld = -1;
652         start = I_FloatTime();
653         
654         /* walk the list of surfaces in the entity */
655         for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
656         {
657                 /* print pacifier */
658                 f = 10 * (i - e->firstDrawSurf) / (numMapDrawSurfs - e->firstDrawSurf);
659                 if( f != fOld )
660                 {
661                         fOld = f;
662                         Sys_FPrintf( SYS_VRB, "%d...", f );
663                 }
664                 
665                 /* get surface */
666                 ds = &mapDrawSurfs[ i ];
667                 if( ds->numVerts <= 0 )
668                         continue;
669                 
670                 /* ignore autosprite surfaces */
671                 if( ds->shaderInfo->autosprite )
672                         continue;
673                 
674                 /* meta this surface? */
675                 if( meta == qfalse && ds->shaderInfo->forceMeta == qfalse )
676                         continue;
677                 
678                 /* switch on type */
679                 switch( ds->type )
680                 {
681                         case SURFACE_FACE:
682                         case SURFACE_DECAL:
683                                 StripFaceSurface( ds );
684                                 SurfaceToMetaTriangles( ds );
685                                 break;
686                         
687                         case SURFACE_PATCH:
688                                 TriangulatePatchSurface(e, ds );
689                                 break;
690                         
691                         case SURFACE_TRIANGLES:
692                                 break;
693                 
694                         case SURFACE_FORCED_META:
695                         case SURFACE_META:
696                                 SurfaceToMetaTriangles( ds );
697                                 break;
698                         
699                         default:
700                                 break;
701                 }
702         }
703         
704         /* print time */
705         if( (numMapDrawSurfs - e->firstDrawSurf) )
706                 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
707         
708         /* emit some stats */
709         Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
710         Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
711         Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
712         Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
713         Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
714         Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
715         
716         /* tidy things up */
717         TidyEntitySurfaces( e );
718 }
719
720
721
722 /*
723 PointTriangleIntersect()
724 assuming that all points lie in plane, determine if pt
725 is inside the triangle abc
726 code originally (c) 2001 softSurfer (www.softsurfer.com)
727 */
728
729 #define MIN_OUTSIDE_EPSILON             -0.01f
730 #define MAX_OUTSIDE_EPSILON             1.01f
731
732 static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )
733 {
734         vec3_t  u, v, w;
735         float   uu, uv, vv, wu, wv, d;
736         
737         
738         /* make vectors */
739         VectorSubtract( b, a, u );
740         VectorSubtract( c, a, v );
741         VectorSubtract( pt, a, w );
742         
743         /* more setup */
744         uu = DotProduct( u, u );
745         uv = DotProduct( u, v );
746         vv = DotProduct( v, v );
747         wu = DotProduct( w, u );
748         wv = DotProduct( w, v );
749         d = uv * uv - uu * vv;
750         
751         /* calculate barycentric coordinates */
752         bary[ 1 ] = (uv * wv - vv * wu) / d;
753         if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )
754                 return qfalse;
755         bary[ 2 ] = (uv * wv - uu * wv) / d;
756         if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )
757                 return qfalse;
758         bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);
759         
760         /* point is in triangle */
761         return qtrue;
762 }
763
764
765
766 /*
767 CreateEdge()
768 sets up an edge structure from a plane and 2 points that the edge ab falls lies in
769 */
770
771 typedef struct edge_s
772 {
773         vec3_t  origin, edge;
774         vec_t   length, kingpinLength;
775         int             kingpin;
776         vec4_t  plane;
777 }
778 edge_t;
779
780 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge )
781 {
782         /* copy edge origin */
783         VectorCopy( a, edge->origin );
784         
785         /* create vector aligned with winding direction of edge */
786         VectorSubtract( b, a, edge->edge );
787         
788         if( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) )
789                 edge->kingpin = 0;
790         else if( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) )
791                 edge->kingpin = 1;
792         else
793                 edge->kingpin = 2;
794         edge->kingpinLength = edge->edge[ edge->kingpin ];
795         
796         VectorNormalize( edge->edge, edge->edge );
797         edge->edge[ 3 ] = DotProduct( a, edge->edge );
798         edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
799         
800         /* create perpendicular plane that edge lies in */
801         CrossProduct( plane, edge->edge, edge->plane );
802         edge->plane[ 3 ] = DotProduct( a, edge->plane );
803 }
804
805
806
807 /*
808 FixMetaTJunctions()
809 fixes t-junctions on meta triangles
810 */
811
812 #define TJ_PLANE_EPSILON        (1.0f / 8.0f)
813 #define TJ_EDGE_EPSILON         (1.0f / 8.0f)
814 #define TJ_POINT_EPSILON        (1.0f / 8.0f)
815
816 void FixMetaTJunctions( void )
817 {
818         int                             i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
819         metaTriangle_t  *tri, *newTri;
820         shaderInfo_t    *si;
821         bspDrawVert_t   *a, *b, *c, junc;
822         float                   dist, amount;
823         vec3_t                  pt;
824         vec4_t                  plane;
825         edge_t                  edges[ 3 ];
826         
827         
828         /* this code is crap; revisit later */
829         return;
830         
831         /* note it */
832         Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
833         
834         /* init pacifier */
835         fOld = -1;
836         start = I_FloatTime();
837         
838         /* walk triangle list */
839         numTJuncs = 0;
840         for( i = 0; i < numMetaTriangles; i++ )
841         {
842                 /* get triangle */
843                 tri = &metaTriangles[ i ];
844                 
845                 /* print pacifier */
846                 f = 10 * i / numMetaTriangles;
847                 if( f != fOld )
848                 {
849                         fOld = f;
850                         Sys_FPrintf( SYS_VRB, "%d...", f );
851                 }
852                 
853                 /* attempt to early out */
854                 si = tri->si;
855                 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc )
856                         continue;
857                 
858                 /* calculate planes */
859                 VectorCopy( tri->plane, plane );
860                 plane[ 3 ] = tri->plane[ 3 ];
861                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
862                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
863                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
864                 
865                 /* walk meta vert list */
866                 for( j = 0; j < numMetaVerts; j++ )
867                 {
868                         /* get vert */
869                         VectorCopy( metaVerts[ j ].xyz, pt );
870
871                         /* debug code: darken verts */
872                         if( i == 0 )
873                                 VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );
874                         
875                         /* determine if point lies in the triangle's plane */
876                         dist = DotProduct( pt, plane ) - plane[ 3 ];
877                         if( fabs( dist ) > TJ_PLANE_EPSILON )
878                                 continue;
879                         
880                         /* skip this point if it already exists in the triangle */
881                         for( k = 0; k < 3; k++ )
882                         {
883                                 if( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
884                                         fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
885                                         fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON )
886                                         break;
887                         }
888                         if( k < 3 )
889                                 continue;
890                         
891                         /* walk edges */
892                         for( k = 0; k < 3; k++ )
893                         {
894                                 /* ignore bogus edges */
895                                 if( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON )
896                                         continue;
897                                 
898                                 /* determine if point lies on the edge */
899                                 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
900                                 if( fabs( dist ) > TJ_EDGE_EPSILON )
901                                         continue;
902                                 
903                                 /* determine how far along the edge the point lies */
904                                 amount = (pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ]) / edges[ k ].kingpinLength;
905                                 if( amount <= 0.0f || amount >= 1.0f )
906                                         continue;
907                                 
908                                 #if 0
909                                 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
910                                 if( dist <= -0.0f || dist >= edges[ k ].length )
911                                         continue;
912                                 amount = dist / edges[ k ].length;
913                                 #endif
914                                 
915                                 /* debug code: brighten this point */
916                                 //%     metaVerts[ j ].color[ 0 ][ 0 ] += 5;
917                                 //%     metaVerts[ j ].color[ 0 ][ 1 ] += 4;
918                                 VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );
919                                 VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );
920                                 
921
922                                 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
923                                 a = &metaVerts[ tri->indexes[ k % 3 ] ];
924                                 b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];
925                                 c = &metaVerts[ tri->indexes[ (k + 2) % 3 ] ];
926                                 
927                                 /* make new vert */
928                                 LerpDrawVertAmount( a, b, amount, &junc );
929                                 VectorCopy( pt, junc.xyz );
930                                 
931                                 /* compare against existing verts */
932                                 if( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) )
933                                         continue;
934                                 
935                                 /* see if we can just re-use the existing vert */
936                                 if( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) )
937                                         vertIndex = j;
938                                 else
939                                 {
940                                         /* find new vertex (note: a and b are invalid pointers after this) */
941                                         firstSearchMetaVert = numMetaVerts;
942                                         vertIndex = FindMetaVertex( &junc );
943                                         if( vertIndex < 0 )
944                                                 continue;
945                                 }
946                                                 
947                                 /* make new triangle */
948                                 triIndex = AddMetaTriangle();
949                                 if( triIndex < 0 )
950                                         continue;
951                                 
952                                 /* get triangles */
953                                 tri = &metaTriangles[ i ];
954                                 newTri = &metaTriangles[ triIndex ];
955                                 
956                                 /* copy the triangle */
957                                 memcpy( newTri, tri, sizeof( *tri ) );
958                                 
959                                 /* fix verts */
960                                 tri->indexes[ (k + 1) % 3 ] = vertIndex;
961                                 newTri->indexes[ k ] = vertIndex;
962                                 
963                                 /* recalculate edges */
964                                 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
965                                 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
966                                 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
967                                 
968                                 /* debug code */
969                                 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
970                                 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
971                                 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
972                                 
973                                 /* add to counter and end processing of this vert */
974                                 numTJuncs++;
975                                 break;
976                         }
977                 }
978         }
979         
980         /* print time */
981         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
982         
983         /* emit some stats */
984         Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
985 }
986
987
988
989 /*
990 SmoothMetaTriangles()
991 averages coincident vertex normals in the meta triangles
992 */
993
994 #define MAX_SAMPLES                             256
995 #define THETA_EPSILON                   0.000001
996 #define EQUAL_NORMAL_EPSILON    0.01
997
998 void SmoothMetaTriangles( void )
999 {
1000         int                             i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
1001         float                   shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
1002         metaTriangle_t  *tri;
1003         float                   *shadeAngles;
1004         byte                    *smoothed;
1005         vec3_t                  average, diff;
1006         int                             indexes[ MAX_SAMPLES ];
1007         vec3_t                  votes[ MAX_SAMPLES ];
1008         const char              *classname;
1009         
1010         /* note it */
1011         Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
1012         
1013         /* allocate shade angle table */
1014         shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
1015         memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
1016         
1017         /* allocate smoothed table */
1018         cs = (numMetaVerts / 8) + 1;
1019         smoothed = safe_malloc( cs );
1020         memset( smoothed, 0, cs );
1021         
1022         /* set default shade angle */
1023         defaultShadeAngle = DEG2RAD( npDegrees );
1024         maxShadeAngle = 0.0f;
1025         
1026         /* run through every surface and flag verts belonging to non-lightmapped surfaces
1027            and set per-vertex smoothing angle */
1028         for( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
1029         {
1030                 /* vortex: try get smoothing from entity key */
1031                 shadeAngle = FloatForKey(&entities[tri->entityNum], "_smoothnormals");
1032                 if (shadeAngle <= 0.0f)
1033                         shadeAngle = FloatForKey(&entities[tri->entityNum], "_sn");
1034                 if (shadeAngle <= 0.0f)
1035                         shadeAngle = FloatForKey(&entities[tri->entityNum], "_smooth");
1036                 if (shadeAngle > 0.0f)
1037                 {
1038                         if (entities[tri->entityNum].forceNormalSmoothing == qfalse)
1039                         {
1040                                 entities[tri->entityNum].forceNormalSmoothing = qtrue;
1041                                 classname = ValueForKey( &entities[tri->entityNum], "classname" );
1042                                 Sys_Printf( "Entity %d (%s) has vertex normal smoothing with breaking angle of %3.0f\n", tri->entityNum, classname, shadeAngle );
1043                         }
1044                         shadeAngle = DEG2RAD( shadeAngle );
1045                 }
1046
1047                 /* get shader for shade angle */
1048                 if (shadeAngle <= 0.0f)
1049                 {
1050                         if( tri->si->shadeAngleDegrees > 0.0f )
1051                                 shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1052                         else
1053                                 shadeAngle = defaultShadeAngle;
1054                 }
1055                 if( shadeAngle > maxShadeAngle )
1056                         maxShadeAngle = shadeAngle;
1057                 
1058                 /* flag its verts */
1059                 for( j = 0; j < 3; j++ )
1060                 {
1061                         shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1062                         if( shadeAngle <= 0 )
1063                                 smoothed[ tri->indexes[ j ] >> 3 ] |= (1 << (tri->indexes[ j ] & 7));
1064                 }
1065         }
1066         
1067         /* bail if no surfaces have a shade angle */
1068         if( maxShadeAngle <= 0 )
1069         {
1070                 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1071                 free( shadeAngles );
1072                 free( smoothed );
1073                 return;
1074         }
1075         
1076         /* init pacifier */
1077         fOld = -1;
1078         start = I_FloatTime();
1079         
1080         /* go through the list of vertexes */
1081         numSmoothed = 0;
1082         for( i = 0; i < numMetaVerts; i++ )
1083         {
1084                 /* print pacifier */
1085                 f = 10 * i / numMetaVerts;
1086                 if( f != fOld )
1087                 {
1088                         fOld = f;
1089                         Sys_FPrintf( SYS_VRB, "%d...", f );
1090                 }
1091                 
1092                 /* already smoothed? */
1093                 if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
1094                         continue;
1095                 
1096                 /* clear */
1097                 VectorClear( average );
1098                 numVerts = 0;
1099                 numVotes = 0;
1100                 
1101                 /* build a table of coincident vertexes */
1102                 for( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1103                 {
1104                         /* already smoothed? */
1105                         if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
1106                                 continue;
1107                         
1108                         /* test vertexes */
1109                         if( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse )
1110                                 continue;
1111                         
1112                         /* use smallest shade angle */
1113                         shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
1114                         
1115                         /* check shade angle */
1116                         dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1117                         if( dot > 1.0 )
1118                                 dot = 1.0;
1119                         else if( dot < -1.0 )
1120                                 dot = -1.0;
1121                         testAngle = acos( dot ) + THETA_EPSILON;
1122                         if( testAngle >= shadeAngle )
1123                                 continue;
1124                         
1125                         /* add to the list */
1126                         indexes[ numVerts++ ] = j;
1127                         
1128                         /* flag vertex */
1129                         smoothed[ j >> 3 ] |= (1 << (j & 7));
1130                         
1131                         /* see if this normal has already been voted */
1132                         for( k = 0; k < numVotes; k++ )
1133                         {
1134                                 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1135                                 if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1136                                         fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1137                                         fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )
1138                                         break;
1139                         }
1140                         
1141                         /* add a new vote? */
1142                         if( k == numVotes && numVotes < MAX_SAMPLES )
1143                         {
1144                                 VectorAdd( average, metaVerts[ j ].normal, average );
1145                                 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1146                                 numVotes++;
1147                         }
1148                 }
1149                 
1150                 /* don't average for less than 2 verts */
1151                 if( numVerts < 2 )
1152                         continue;
1153                 
1154                 /* average normal */
1155                 if( VectorNormalize( average, average ) > 0 )
1156                 {
1157                         /* smooth */
1158                         for( j = 0; j < numVerts; j++ )
1159                                 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1160                         numSmoothed++;
1161                 }
1162         }
1163         
1164         /* free the tables */
1165         free( shadeAngles );
1166         free( smoothed );
1167         
1168         /* print time */
1169         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1170
1171         /* emit some stats */
1172         Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1173 }
1174
1175
1176
1177 /*
1178 AddMetaVertToSurface()
1179 adds a drawvert to a surface unless an existing vert matching already exists
1180 returns the index of that vert (or < 0 on failure)
1181 */
1182
1183 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident )
1184 {
1185         int                             i;
1186         bspDrawVert_t   *dv2;
1187         
1188         
1189         /* go through the verts and find a suitable candidate */
1190         for( i = 0; i < ds->numVerts; i++ )
1191         {
1192                 /* get test vert */
1193                 dv2 = &ds->verts[ i ];
1194                 
1195                 /* compare xyz and normal */
1196                 if( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse )
1197                         continue;
1198                 if( VectorCompare( dv1->normal, dv2->normal ) == qfalse )
1199                         continue;
1200                 
1201                 /* good enough at this point */
1202                 (*coincident)++;
1203                 
1204                 /* compare texture coordinates and color */
1205                 if( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] )
1206                         continue;
1207                 if( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] )
1208                         continue;
1209                 
1210                 /* found a winner */
1211                 numMergedVerts++;
1212                 return i;
1213         }
1214
1215         /* overflow check */
1216         if( ds->numVerts >= ((ds->shaderInfo->compileFlags & C_VERTEXLIT) ? maxSurfaceVerts : maxLMSurfaceVerts) )
1217                 return VERTS_EXCEEDED;
1218         
1219         /* made it this far, add the vert and return */
1220         dv2 = &ds->verts[ ds->numVerts++ ];
1221         *dv2 = *dv1;
1222         return (ds->numVerts - 1);
1223 }
1224
1225
1226
1227
1228 /*
1229 AddMetaTriangleToSurface()
1230 attempts to add a metatriangle to a surface
1231 returns the score of the triangle added
1232 */
1233
1234 #define AXIS_SCORE                      100000
1235 #define AXIS_MIN                        100000
1236 #define VERT_SCORE                      10000
1237 #define SURFACE_SCORE           1000
1238 #define ST_SCORE                        50
1239 #define ST_SCORE2                       (2 * (ST_SCORE))
1240
1241 #define ADEQUATE_SCORE          ((AXIS_MIN) + 1 * (VERT_SCORE))
1242 #define GOOD_SCORE                      ((AXIS_MIN) + 2 * (VERT_SCORE) + 4 * (ST_SCORE))
1243 #define PERFECT_SCORE           ((AXIS_MIN) + + 3 * (VERT_SCORE) + (SURFACE_SCORE) + 4 * (ST_SCORE))
1244
1245 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd )
1246 {
1247         int                                     i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1248         float                           lmMax;
1249         vec3_t                          mins, maxs;
1250         qboolean                        inTexRange, es, et;
1251         mapDrawSurface_t        old;
1252         
1253         
1254         /* overflow check */
1255         if( ds->numIndexes >= maxSurfaceIndexes )
1256                 return 0;
1257         
1258         /* test the triangle */
1259         if( ds->entityNum != tri->entityNum )   /* ydnar: added 2002-07-06 */
1260                 return 0;
1261         if( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows )
1262                 return 0;
1263         if( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize )
1264                 return 0;
1265         #if 0
1266                 if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1267                         //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1268                         DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f )
1269                         return 0;
1270         #endif
1271         
1272         /* planar surfaces will only merge with triangles in the same plane */
1273         if( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 )
1274         {
1275                 if( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] )
1276                         return 0;
1277                 if( tri->planeNum >= 0 && tri->planeNum != ds->planeNum )
1278                         return 0;
1279         }
1280         
1281         /* set initial score */
1282         score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1283         
1284         /* score the the dot product of lightmap axis to plane */
1285         if( (ds->shaderInfo->compileFlags & C_VERTEXLIT) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) )
1286                 score += AXIS_SCORE;
1287         else
1288                 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1289         
1290         /* preserve old drawsurface if this fails */
1291         memcpy( &old, ds, sizeof( *ds ) );
1292         
1293         /* attempt to add the verts */
1294         coincident = 0;
1295         ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1296         bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1297         ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1298         
1299         /* check vertex underflow */
1300         if( ai < 0 || bi < 0 || ci < 0 )
1301         {
1302                 memcpy( ds, &old, sizeof( *ds ) );
1303                 return 0;
1304         }
1305         
1306         /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1307         score += (coincident * VERT_SCORE);
1308         
1309         /* add new vertex bounds to mins/maxs */
1310         VectorCopy( ds->mins, mins );
1311         VectorCopy( ds->maxs, maxs );
1312         AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1313         AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1314         AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1315         
1316         /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1317         if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1318                 ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1319                 (VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse) )
1320         {
1321                 /* set maximum size before lightmap scaling (normally 2032 units) */
1322                 /* 2004-02-24: scale lightmap test size by 2 to catch larger brush faces */
1323                 /* 2004-04-11: reverting to actual lightmap size */
1324                 lmMax = (ds->sampleSize * (ds->shaderInfo->lmCustomWidth - 1));
1325                 for( i = 0; i < 3; i++ )
1326                 {
1327                         if( (maxs[ i ] - mins[ i ]) > lmMax )
1328                         {
1329                                 memcpy( ds, &old, sizeof( *ds ) );
1330                                 return 0;
1331                         }
1332                 }
1333         }
1334         
1335         /* check texture range overflow */
1336         oldTexRange[ 0 ] = ds->texRange[ 0 ];
1337         oldTexRange[ 1 ] = ds->texRange[ 1 ];
1338         inTexRange = CalcSurfaceTextureRange( ds );
1339         
1340         es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;
1341         et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;
1342         
1343         if( inTexRange == qfalse && ds->numIndexes > 0 )
1344         {
1345                 memcpy( ds, &old, sizeof( *ds ) );
1346                 return UNSUITABLE_TRIANGLE;
1347         }
1348         
1349         /* score texture range */
1350         if( ds->texRange[ 0 ] <= oldTexRange[ 0 ] )
1351                 score += ST_SCORE2;
1352         else if( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] )
1353                 score += ST_SCORE;
1354         
1355         if( ds->texRange[ 1 ] <= oldTexRange[ 1 ] )
1356                 score += ST_SCORE2;
1357         else if( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] )
1358                 score += ST_SCORE;
1359         
1360         
1361         /* go through the indexes and try to find an existing triangle that matches abc */
1362         for( i = 0; i < ds->numIndexes; i += 3 )
1363         {
1364                 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1365                 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ]) ||
1366                         (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ]) ||
1367                         (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ]) )
1368                 {
1369                         /* triangle already present */
1370                         memcpy( ds, &old, sizeof( *ds ) );
1371                         tri->si = NULL;
1372                         return 0;
1373                 }
1374                 
1375                 /* rotate the triangle 3x to find an inverse triangle (error case) */
1376                 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ]) ||
1377                         (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ]) ||
1378                         (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ]) )
1379                 {
1380                         /* warn about it */
1381                         Sys_Printf( "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
1382                                 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1383                                 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1384                                 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1385                         
1386                         /* reverse triangle already present */
1387                         memcpy( ds, &old, sizeof( *ds ) );
1388                         tri->si = NULL;
1389                         return 0;
1390                 }
1391         }
1392         
1393         /* add the triangle indexes */
1394         if( ds->numIndexes < maxSurfaceIndexes )
1395                 ds->indexes[ ds->numIndexes++ ] = ai;
1396         if( ds->numIndexes < maxSurfaceIndexes )
1397                 ds->indexes[ ds->numIndexes++ ] = bi;
1398         if( ds->numIndexes < maxSurfaceIndexes )
1399                 ds->indexes[ ds->numIndexes++ ] = ci;
1400         
1401         /* check index overflow */
1402         if( ds->numIndexes >= maxSurfaceIndexes  )
1403         {
1404                 memcpy( ds, &old, sizeof( *ds ) );
1405                 return 0;
1406         }
1407         
1408         /* sanity check the indexes */
1409         if( ds->numIndexes >= 3 &&
1410                 (ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1411                 ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1412                 ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ]) )
1413                 Sys_Printf( "DEG:%d! ", ds->numVerts );
1414         
1415         /* testing only? */
1416         if( testAdd )
1417                 memcpy( ds, &old, sizeof( *ds ) );
1418         else
1419         {
1420                 /* copy bounds back to surface */
1421                 VectorCopy( mins, ds->mins );
1422                 VectorCopy( maxs, ds->maxs );
1423                 
1424                 /* mark triangle as used */
1425                 tri->si = NULL;
1426         }
1427         
1428         /* add a side reference */
1429         ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1430         
1431         /* return to sender */
1432         return score;
1433 }
1434
1435
1436
1437 /*
1438 MetaTrianglesToSurface()
1439 creates map drawsurface(s) from the list of possibles
1440 */
1441
1442 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded )
1443 {
1444         int                                     i, j, f, best, score, bestScore;
1445         metaTriangle_t          *seed, *test;
1446         mapDrawSurface_t        *ds;
1447         bspDrawVert_t           *verts;
1448         int                                     *indexes;
1449         qboolean                        added;
1450         
1451         
1452         /* allocate arrays */
1453         verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1454         indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1455         
1456         /* walk the list of triangles */
1457         for( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1458         {
1459                 /* skip this triangle if it has already been merged */
1460                 if( seed->si == NULL )
1461                         continue;
1462                 
1463                 /* -----------------------------------------------------------------
1464                    initial drawsurf construction
1465                    ----------------------------------------------------------------- */
1466                 
1467                 /* start a new drawsurface */
1468                 ds = AllocDrawSurface( SURFACE_META );
1469                 ds->entityNum = seed->entityNum;
1470                 ds->surfaceNum = seed->surfaceNum;
1471                 ds->castShadows = seed->castShadows;
1472                 ds->recvShadows = seed->recvShadows;
1473                 
1474                 ds->shaderInfo = seed->si;
1475                 ds->planeNum = seed->planeNum;
1476                 ds->fogNum = seed->fogNum;
1477                 ds->sampleSize = seed->sampleSize;
1478                 ds->verts = verts;
1479                 ds->indexes = indexes;
1480                 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1481                 ds->sideRef = AllocSideRef( seed->side, NULL );
1482                 
1483                 ClearBounds( ds->mins, ds->maxs );
1484                 
1485                 /* clear verts/indexes */
1486                 memset( verts, 0, sizeof( verts ) );
1487                 memset( indexes, 0, sizeof( indexes ) );
1488                 
1489                 /* add the first triangle */
1490                 if( AddMetaTriangleToSurface( ds, seed, qfalse ) )
1491                         (*numAdded)++;
1492                 
1493                 /* -----------------------------------------------------------------
1494                    add triangles
1495                    ----------------------------------------------------------------- */
1496                 
1497                 /* progressively walk the list until no more triangles can be added */
1498                 added = qtrue;
1499                 while( added )
1500                 {
1501                         /* print pacifier */
1502                         f = 10 * *numAdded / numMetaTriangles;
1503                         if( f > *fOld )
1504                         {
1505                                 *fOld = f;
1506                                 Sys_FPrintf( SYS_VRB, "%d...", f );
1507                         }
1508                         
1509                         /* reset best score */
1510                         best = -1;
1511                         bestScore = 0;
1512                         added = qfalse;
1513                         
1514                         /* walk the list of possible candidates for merging */
1515                         for( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1516                         {
1517                                 /* skip this triangle if it has already been merged */
1518                                 if( test->si == NULL )
1519                                         continue;
1520                                 
1521                                 /* score this triangle */
1522                                 score = AddMetaTriangleToSurface( ds, test, qtrue );
1523                                 if( score > bestScore )
1524                                 {
1525                                         best = j;
1526                                         bestScore = score;
1527                                         
1528                                         /* if we have a score over a certain threshold, just use it */
1529                                         if( bestScore >= GOOD_SCORE )
1530                                         {
1531                                                 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1532                                                         (*numAdded)++;
1533                                                 
1534                                                 /* reset */
1535                                                 best = -1;
1536                                                 bestScore = 0;
1537                                                 added = qtrue;
1538                                         }
1539                                 }
1540                         }
1541                         
1542                         /* add best candidate */
1543                         if( best >= 0 && bestScore > ADEQUATE_SCORE )
1544                         {
1545                                 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1546                                         (*numAdded)++;
1547                                 
1548                                 /* reset */
1549                                 added = qtrue;
1550                         }
1551                 }
1552                 
1553                 /* copy the verts and indexes to the new surface */
1554                 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1555                 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1556                 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1557                 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1558                 
1559                 /* classify the surface */
1560                 ClassifySurfaces( 1, ds );
1561                 
1562                 /* add to count */
1563                 numMergedSurfaces++;
1564         }
1565         
1566         /* free arrays */
1567         free( verts );
1568         free( indexes );
1569 }
1570
1571
1572
1573 /*
1574 CompareMetaTriangles()
1575 compare function for qsort()
1576 */
1577
1578 static int CompareMetaTriangles( const void *a, const void *b )
1579 {
1580         int             i, j, av, bv;
1581         vec3_t  aMins, bMins;
1582         
1583         
1584         /* shader first */
1585         if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )
1586                 return 1;
1587         else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )
1588                 return -1;
1589         
1590         /* then fog */
1591         else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )
1592                 return 1;
1593         else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )
1594                 return -1;
1595         
1596         /* then plane */
1597         #if 0
1598                 else if( npDegrees == 0.0f && ((metaTriangle_t*) a)->si->nonplanar == qfalse &&
1599                         ((metaTriangle_t*) a)->planeNum >= 0 && ((metaTriangle_t*) a)->planeNum >= 0 )
1600                 {
1601                         if( ((metaTriangle_t*) a)->plane[ 3 ] < ((metaTriangle_t*) b)->plane[ 3 ] )
1602                                 return 1;
1603                         else if( ((metaTriangle_t*) a)->plane[ 3 ] > ((metaTriangle_t*) b)->plane[ 3 ] )
1604                                 return -1;
1605                         else if( ((metaTriangle_t*) a)->plane[ 0 ] < ((metaTriangle_t*) b)->plane[ 0 ] )
1606                                 return 1;
1607                         else if( ((metaTriangle_t*) a)->plane[ 0 ] > ((metaTriangle_t*) b)->plane[ 0 ] )
1608                                 return -1;
1609                         else if( ((metaTriangle_t*) a)->plane[ 1 ] < ((metaTriangle_t*) b)->plane[ 1 ] )
1610                                 return 1;
1611                         else if( ((metaTriangle_t*) a)->plane[ 1 ] > ((metaTriangle_t*) b)->plane[ 1 ] )
1612                                 return -1;
1613                         else if( ((metaTriangle_t*) a)->plane[ 2 ] < ((metaTriangle_t*) b)->plane[ 2 ] )
1614                                 return 1;
1615                         else if( ((metaTriangle_t*) a)->plane[ 2 ] > ((metaTriangle_t*) b)->plane[ 2 ] )
1616                                 return -1;
1617                 }
1618         #endif
1619         
1620         /* then position in world */
1621         
1622         /* find mins */
1623         VectorSet( aMins, 999999, 999999, 999999 );
1624         VectorSet( bMins, 999999, 999999, 999999 );
1625         for( i = 0; i < 3; i++ )
1626         {
1627                 av = ((metaTriangle_t*) a)->indexes[ i ];
1628                 bv = ((metaTriangle_t*) b)->indexes[ i ];
1629                 for( j = 0; j < 3; j++ )
1630                 {
1631                         if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )
1632                                 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1633                         if( metaVerts[ bv ].xyz[ j ] < bMins[ j ] )
1634                                 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1635                 }
1636         }
1637         
1638         /* test it */
1639         for( i = 0; i < 3; i++ )
1640         {
1641                 if( aMins[ i ] < bMins[ i ] )
1642                         return 1;
1643                 else if( aMins[ i ] > bMins[ i ] )
1644                         return -1;
1645         }
1646         
1647         /* functionally equivalent */
1648         return 0;
1649 }
1650
1651
1652
1653 /*
1654 MergeMetaTriangles()
1655 merges meta triangles into drawsurfaces
1656 */
1657
1658 void MergeMetaTriangles( void )
1659 {
1660         int                                     i, j, fOld, start, numAdded;
1661         metaTriangle_t          *head, *end;
1662         
1663         
1664         /* only do this if there are meta triangles */
1665         if( numMetaTriangles <= 0 )
1666                 return;
1667         
1668         /* note it */
1669         Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1670         
1671         /* sort the triangles by shader major, fognum minor */
1672         qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1673
1674         /* init pacifier */
1675         fOld = -1;
1676         start = I_FloatTime();
1677         numAdded = 0;
1678         
1679         /* merge */
1680         for( i = 0, j = 0; i < numMetaTriangles; i = j )
1681         {
1682                 /* get head of list */
1683                 head = &metaTriangles[ i ];
1684                 
1685                 /* skip this triangle if it has already been merged */
1686                 if( head->si == NULL )
1687                         continue;
1688                 
1689                 /* find end */
1690                 if( j <= i )
1691                 {
1692                         for( j = i + 1; j < numMetaTriangles; j++ )
1693                         {
1694                                 /* get end of list */
1695                                 end = &metaTriangles[ j ];
1696                                 if( head->si != end->si || head->fogNum != end->fogNum )
1697                                         break;
1698                         }
1699                 }
1700                 
1701                 /* try to merge this list of possible merge candidates */
1702                 MetaTrianglesToSurface( (j - i), head, &fOld, &numAdded );
1703         }
1704         
1705         /* clear meta triangle list */
1706         ClearMetaTriangles();
1707         
1708         /* print time */
1709         if( i )
1710                 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1711         
1712         /* emit some stats */
1713         Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1714         Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );
1715 }