tools/quake3/q3map2/surface_meta.c

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