-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-\r
-----------------------------------------------------------------------------------\r
-\r
-This code has been altered significantly from its original form, to support\r
-several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
-\r
-------------------------------------------------------------------------------- */\r
-\r
-\r
-\r
-/* marker */\r
-#define SURFACE_META_C\r
-\r
-\r
-\r
-/* dependencies */\r
-#include "q3map2.h"\r
-\r
-\r
-\r
-#define LIGHTMAP_EXCEEDED -1\r
-#define S_EXCEEDED -2\r
-#define T_EXCEEDED -3\r
-#define ST_EXCEEDED -4\r
-#define UNSUITABLE_TRIANGLE -10\r
-#define VERTS_EXCEEDED -1000\r
-#define INDEXES_EXCEEDED -2000\r
-\r
-#define GROW_META_VERTS 1024\r
-#define GROW_META_TRIANGLES 1024\r
-\r
-static int numMetaSurfaces, numPatchMetaSurfaces;\r
-\r
-static int maxMetaVerts = 0;\r
-static int numMetaVerts = 0;\r
-static int firstSearchMetaVert = 0;\r
-static bspDrawVert_t *metaVerts = NULL;\r
-\r
-static int maxMetaTriangles = 0;\r
-static int numMetaTriangles = 0;\r
-static metaTriangle_t *metaTriangles = NULL;\r
-\r
-\r
-\r
-/*\r
-ClearMetaVertexes()\r
-called before staring a new entity to clear out the triangle list\r
-*/\r
-\r
-void ClearMetaTriangles( void )\r
-{\r
- numMetaVerts = 0;\r
- numMetaTriangles = 0;\r
-}\r
-\r
-\r
-\r
-/*\r
-FindMetaVertex()\r
-finds a matching metavertex in the global list, returning its index\r
-*/\r
-\r
-static int FindMetaVertex( bspDrawVert_t *src )\r
-{\r
- int i;\r
- bspDrawVert_t *v, *temp;\r
- \r
- \r
- /* try to find an existing drawvert */\r
- for( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )\r
- {\r
- if( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 )\r
- return i;\r
- }\r
- \r
- /* enough space? */\r
- if( numMetaVerts >= maxMetaVerts )\r
- {\r
- /* reallocate more room */\r
- maxMetaVerts += GROW_META_VERTS;\r
- temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );\r
- if( metaVerts != NULL )\r
- {\r
- memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );\r
- free( metaVerts );\r
- }\r
- metaVerts = temp;\r
- }\r
- \r
- /* add the triangle */\r
- memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );\r
- numMetaVerts++;\r
- \r
- /* return the count */\r
- return (numMetaVerts - 1);\r
-}\r
-\r
-\r
-\r
-/*\r
-AddMetaTriangle()\r
-adds a new meta triangle, allocating more memory if necessary\r
-*/\r
-\r
-static int AddMetaTriangle( void )\r
-{\r
- metaTriangle_t *temp;\r
- \r
- \r
- /* enough space? */\r
- if( numMetaTriangles >= maxMetaTriangles )\r
- {\r
- /* reallocate more room */\r
- maxMetaTriangles += GROW_META_TRIANGLES;\r
- temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );\r
- if( metaTriangles != NULL )\r
- {\r
- memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );\r
- free( metaTriangles );\r
- }\r
- metaTriangles = temp;\r
- }\r
- \r
- /* increment and return */\r
- numMetaTriangles++;\r
- return numMetaTriangles - 1;\r
-}\r
-\r
-\r
-\r
-/*\r
-FindMetaTriangle()\r
-finds a matching metatriangle in the global list,\r
-otherwise adds it and returns the index to the metatriangle\r
-*/\r
-\r
-int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum )\r
-{\r
- int triIndex;\r
- vec3_t dir;\r
-\r
- \r
- \r
- /* detect degenerate triangles fixme: do something proper here */\r
- VectorSubtract( a->xyz, b->xyz, dir );\r
- if( VectorLength( dir ) < 0.125f )\r
- return -1;\r
- VectorSubtract( b->xyz, c->xyz, dir );\r
- if( VectorLength( dir ) < 0.125f )\r
- return -1;\r
- VectorSubtract( c->xyz, a->xyz, dir );\r
- if( VectorLength( dir ) < 0.125f )\r
- return -1;\r
- \r
- /* find plane */\r
- if( planeNum >= 0 )\r
- {\r
- /* because of precision issues with small triangles, try to use the specified plane */\r
- src->planeNum = planeNum;\r
- VectorCopy( mapplanes[ planeNum ].normal, src->plane );\r
- src->plane[ 3 ] = mapplanes[ planeNum ].dist;\r
- }\r
- else\r
- {\r
- /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */\r
- src->planeNum = -1;\r
- if( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse )\r
- return -1;\r
- }\r
- \r
- /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */\r
- if( VectorLength( a->normal ) <= 0.0f )\r
- VectorCopy( src->plane, a->normal );\r
- if( VectorLength( b->normal ) <= 0.0f )\r
- VectorCopy( src->plane, b->normal );\r
- if( VectorLength( c->normal ) <= 0.0f )\r
- VectorCopy( src->plane, c->normal );\r
- \r
- /* ydnar 2002-10-04: set lightmap axis if not already set */\r
- if( !(src->si->compileFlags & C_VERTEXLIT) &&\r
- src->lightmapAxis[ 0 ] == 0.0f && src->lightmapAxis[ 1 ] == 0.0f && src->lightmapAxis[ 2 ] == 0.0f )\r
- {\r
- /* the shader can specify an explicit lightmap axis */\r
- if( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] )\r
- VectorCopy( src->si->lightmapAxis, src->lightmapAxis );\r
- \r
- /* new axis-finding code */\r
- else\r
- CalcLightmapAxis( src->plane, src->lightmapAxis );\r
- }\r
- \r
- /* fill out the src triangle */\r
- src->indexes[ 0 ] = FindMetaVertex( a );\r
- src->indexes[ 1 ] = FindMetaVertex( b );\r
- src->indexes[ 2 ] = FindMetaVertex( c );\r
- \r
- /* try to find an existing triangle */\r
- #ifdef USE_EXHAUSTIVE_SEARCH\r
- {\r
- int i;\r
- metaTriangle_t *tri;\r
- \r
- \r
- for( i = 0, tri = metaTriangles; i < numMetaTriangles; i++, tri++ )\r
- {\r
- if( memcmp( src, tri, sizeof( metaTriangle_t ) ) == 0 )\r
- return i;\r
- }\r
- }\r
- #endif\r
- \r
- /* get a new triangle */\r
- triIndex = AddMetaTriangle();\r
- \r
- /* add the triangle */\r
- memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );\r
- \r
- /* return the triangle index */\r
- return triIndex;\r
-}\r
-\r
-\r
-\r
-/*\r
-SurfaceToMetaTriangles()\r
-converts a classified surface to metatriangles\r
-*/\r
-\r
-static void SurfaceToMetaTriangles( mapDrawSurface_t *ds )\r
-{\r
- int i;\r
- metaTriangle_t src;\r
- bspDrawVert_t a, b, c;\r
- \r
- \r
- /* only handle certain types of surfaces */\r
- if( ds->type != SURFACE_FACE &&\r
- ds->type != SURFACE_META &&\r
- ds->type != SURFACE_FORCED_META &&\r
- ds->type != SURFACE_DECAL )\r
- return;\r
- \r
- /* speed at the expense of memory */\r
- firstSearchMetaVert = numMetaVerts;\r
- \r
- /* only handle valid surfaces */\r
- if( ds->type != SURFACE_BAD && ds->numVerts >= 3 && ds->numIndexes >= 3 )\r
- {\r
- /* walk the indexes and create triangles */\r
- for( i = 0; i < ds->numIndexes; i += 3 )\r
- {\r
- /* sanity check the indexes */\r
- if( ds->indexes[ i ] == ds->indexes[ i + 1 ] ||\r
- ds->indexes[ i ] == ds->indexes[ i + 2 ] ||\r
- ds->indexes[ i + 1 ] == ds->indexes[ i + 2 ] )\r
- {\r
- //% Sys_Printf( "%d! ", ds->numVerts );\r
- continue;\r
- }\r
- \r
- /* build a metatriangle */\r
- src.si = ds->shaderInfo;\r
- src.side = (ds->sideRef != NULL ? ds->sideRef->side : NULL);\r
- src.entityNum = ds->entityNum;\r
- src.surfaceNum = ds->surfaceNum;\r
- src.planeNum = ds->planeNum;\r
- src.castShadows = ds->castShadows;\r
- src.recvShadows = ds->recvShadows;\r
- src.fogNum = ds->fogNum;\r
- src.sampleSize = ds->sampleSize;\r
- VectorCopy( ds->lightmapAxis, src.lightmapAxis );\r
- \r
- /* copy drawverts */\r
- memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );\r
- memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );\r
- memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );\r
- FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );\r
- }\r
- \r
- /* add to count */\r
- numMetaSurfaces++;\r
- }\r
- \r
- /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */\r
- ClearSurface( ds );\r
-}\r
-\r
-\r
-\r
-/*\r
-TriangulatePatchSurface()\r
-creates triangles from a patch\r
-*/\r
-\r
-void TriangulatePatchSurface( mapDrawSurface_t *ds )\r
-{\r
- int iterations, x, y, pw[ 5 ], r;\r
- mapDrawSurface_t *dsNew;\r
- mesh_t src, *subdivided, *mesh;\r
- \r
- \r
- /* try to early out */\r
- if( ds->numVerts == 0 || ds->type != SURFACE_PATCH || patchMeta == qfalse )\r
- return;\r
- \r
- /* make a mesh from the drawsurf */ \r
- src.width = ds->patchWidth;\r
- src.height = ds->patchHeight;\r
- src.verts = ds->verts;\r
- //% subdivided = SubdivideMesh( src, 8, 999 );\r
- iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );\r
- subdivided = SubdivideMesh2( src, iterations ); //% ds->maxIterations\r
- \r
- /* fit it to the curve and remove colinear verts on rows/columns */\r
- PutMeshOnCurve( *subdivided );\r
- mesh = RemoveLinearMeshColumnsRows( subdivided );\r
- FreeMesh( subdivided );\r
- //% MakeMeshNormals( mesh );\r
- \r
- /* make a copy of the drawsurface */\r
- dsNew = AllocDrawSurface( SURFACE_META );\r
- memcpy( dsNew, ds, sizeof( *ds ) );\r
- \r
- /* if the patch is nonsolid, then discard it */\r
- if( !(ds->shaderInfo->compileFlags & C_SOLID) )\r
- ClearSurface( ds );\r
- \r
- /* set new pointer */\r
- ds = dsNew;\r
- \r
- /* basic transmogrification */\r
- ds->type = SURFACE_META;\r
- ds->numIndexes = 0;\r
- ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );\r
- \r
- /* copy the verts in */\r
- ds->numVerts = (mesh->width * mesh->height);\r
- ds->verts = mesh->verts;\r
- \r
- /* iterate through the mesh quads */\r
- for( y = 0; y < (mesh->height - 1); y++ )\r
- {\r
- for( x = 0; x < (mesh->width - 1); x++ )\r
- {\r
- /* set indexes */\r
- pw[ 0 ] = x + (y * mesh->width);\r
- pw[ 1 ] = x + ((y + 1) * mesh->width);\r
- pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);\r
- pw[ 3 ] = x + 1 + (y * mesh->width);\r
- pw[ 4 ] = x + (y * mesh->width); /* same as pw[ 0 ] */\r
- \r
- /* set radix */\r
- r = (x + y) & 1;\r
- \r
- /* make first triangle */\r
- ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];\r
- ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];\r
- ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];\r
- \r
- /* make second triangle */\r
- ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];\r
- ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];\r
- ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];\r
- }\r
- }\r
- \r
- /* free the mesh, but not the verts */\r
- free( mesh );\r
- \r
- /* add to count */\r
- numPatchMetaSurfaces++;\r
- \r
- /* classify it */\r
- ClassifySurfaces( 1, ds );\r
-}\r
-\r
-\r
-\r
-/*\r
-FanFaceSurface() - ydnar\r
-creates a tri-fan from a brush face winding\r
-loosely based on SurfaceAsTriFan()\r
-*/\r
-\r
-void FanFaceSurface( mapDrawSurface_t *ds )\r
-{\r
- int i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];\r
- bspDrawVert_t *verts, *centroid, *dv;\r
- double iv;\r
- \r
- \r
- /* try to early out */\r
- if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )\r
- return;\r
- \r
- /* add a new vertex at the beginning of the surface */\r
- verts = safe_malloc( (ds->numVerts + 1) * sizeof( bspDrawVert_t ) );\r
- memset( verts, 0, sizeof( bspDrawVert_t ) );\r
- memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );\r
- free( ds->verts );\r
- ds->verts = verts;\r
- \r
- /* add up the drawverts to create a centroid */\r
- centroid = &verts[ 0 ];\r
- memset( color, 0, 4 * MAX_LIGHTMAPS * sizeof( int ) );\r
- for( i = 1, dv = &verts[ 1 ]; i < (ds->numVerts + 1); i++, dv++ )\r
- {\r
- VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );\r
- VectorAdd( centroid->normal, dv->normal, centroid->normal );\r
- for( j = 0; j < 4; j++ )\r
- {\r
- for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
- color[ k ][ j ] += dv->color[ k ][ j ];\r
- if( j < 2 )\r
- {\r
- centroid->st[ j ] += dv->st[ j ];\r
- for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
- centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];\r
- }\r
- }\r
- }\r
- \r
- /* average the centroid */\r
- iv = 1.0f / ds->numVerts;\r
- VectorScale( centroid->xyz, iv, centroid->xyz );\r
- if( VectorNormalize( centroid->normal, centroid->normal ) <= 0 )\r
- VectorCopy( verts[ 1 ].normal, centroid->normal );\r
- for( j = 0; j < 4; j++ )\r
- {\r
- for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
- {\r
- color[ k ][ j ] /= ds->numVerts;\r
- centroid->color[ k ][ j ] = (color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255);\r
- }\r
- if( j < 2 )\r
- {\r
- centroid->st[ j ] *= iv;\r
- for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
- centroid->lightmap[ k ][ j ] *= iv;\r
- }\r
- }\r
- \r
- /* add to vert count */\r
- ds->numVerts++;\r
- \r
- /* fill indexes in triangle fan order */\r
- ds->numIndexes = 0;\r
- ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );\r
- for( i = 1; i < ds->numVerts; i++ )\r
- {\r
- a = 0;\r
- b = i;\r
- c = (i + 1) % ds->numVerts;\r
- c = c ? c : 1;\r
- ds->indexes[ ds->numIndexes++ ] = a;\r
- ds->indexes[ ds->numIndexes++ ] = b;\r
- ds->indexes[ ds->numIndexes++ ] = c;\r
- }\r
- \r
- /* add to count */\r
- numFanSurfaces++;\r
-\r
- /* classify it */\r
- ClassifySurfaces( 1, ds );\r
-}\r
-\r
-\r
-\r
-/*\r
-StripFaceSurface() - ydnar\r
-attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding\r
-based on SurfaceAsTriStrip()\r
-*/\r
-\r
-#define MAX_INDEXES 1024\r
-\r
-void StripFaceSurface( mapDrawSurface_t *ds ) \r
-{\r
- int i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];\r
- vec_t *v1, *v2;\r
- \r
- \r
- /* try to early out */\r
- if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )\r
- return;\r
- \r
- /* is this a simple triangle? */\r
- if( ds->numVerts == 3 )\r
- {\r
- numIndexes = 3;\r
- VectorSet( indexes, 0, 1, 2 );\r
- }\r
- else\r
- {\r
- /* ydnar: find smallest coordinate */\r
- least = 0;\r
- if( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse )\r
- {\r
- for( i = 0; i < ds->numVerts; i++ )\r
- {\r
- /* get points */\r
- v1 = ds->verts[ i ].xyz;\r
- v2 = ds->verts[ least ].xyz;\r
- \r
- /* compare */\r
- if( v1[ 0 ] < v2[ 0 ] ||\r
- (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ]) ||\r
- (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ]) )\r
- least = i;\r
- }\r
- }\r
- \r
- /* determine the triangle strip order */\r
- numIndexes = (ds->numVerts - 2) * 3;\r
- if( numIndexes > MAX_INDEXES )\r
- Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );\r
- \r
- /* try all possible orderings of the points looking for a non-degenerate strip order */\r
- for( r = 0; r < ds->numVerts; r++ )\r
- {\r
- /* set rotation */\r
- rotate = (r + least) % ds->numVerts;\r
- \r
- /* walk the winding in both directions */\r
- for( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )\r
- {\r
- /* make indexes */\r
- a = (ds->numVerts - 1 - i + rotate) % ds->numVerts;\r
- b = (i + rotate ) % ds->numVerts;\r
- c = (ds->numVerts - 2 - i + rotate) % ds->numVerts;\r
- \r
- /* test this triangle */\r
- if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )\r
- break;\r
- indexes[ ni++ ] = a;\r
- indexes[ ni++ ] = b;\r
- indexes[ ni++ ] = c;\r
- \r
- /* handle end case */\r
- if( i + 1 != ds->numVerts - 1 - i )\r
- {\r
- /* make indexes */\r
- a = (ds->numVerts - 2 - i + rotate ) % ds->numVerts;\r
- b = (i + rotate ) % ds->numVerts;\r
- c = (i + 1 + rotate ) % ds->numVerts;\r
- \r
- /* test triangle */\r
- if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )\r
- break;\r
- indexes[ ni++ ] = a;\r
- indexes[ ni++ ] = b;\r
- indexes[ ni++ ] = c;\r
- }\r
- }\r
- \r
- /* valid strip? */\r
- if( ni == numIndexes )\r
- break;\r
- }\r
- \r
- /* if any triangle in the strip is degenerate, render from a centered fan point instead */\r
- if( ni < numIndexes )\r
- {\r
- FanFaceSurface( ds );\r
- return;\r
- }\r
- }\r
- \r
- /* copy strip triangle indexes */\r
- ds->numIndexes = numIndexes;\r
- ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );\r
- memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );\r
- \r
- /* add to count */\r
- numStripSurfaces++;\r
- \r
- /* classify it */\r
- ClassifySurfaces( 1, ds );\r
-}\r
-\r
-\r
-\r
-/*\r
-MakeEntityMetaTriangles()\r
-builds meta triangles from brush faces (tristrips and fans)\r
-*/\r
-\r
-void MakeEntityMetaTriangles( entity_t *e )\r
-{\r
- int i, f, fOld, start;\r
- mapDrawSurface_t *ds;\r
- \r
- \r
- /* note it */\r
- Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );\r
- \r
- /* init pacifier */\r
- fOld = -1;\r
- start = I_FloatTime();\r
- \r
- /* walk the list of surfaces in the entity */\r
- for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )\r
- {\r
- /* print pacifier */\r
- f = 10 * (i - e->firstDrawSurf) / (numMapDrawSurfs - e->firstDrawSurf);\r
- if( f != fOld )\r
- {\r
- fOld = f;\r
- Sys_FPrintf( SYS_VRB, "%d...", f );\r
- }\r
- \r
- /* get surface */\r
- ds = &mapDrawSurfs[ i ];\r
- if( ds->numVerts <= 0 )\r
- continue;\r
- \r
- /* ignore autosprite surfaces */\r
- if( ds->shaderInfo->autosprite )\r
- continue;\r
- \r
- /* meta this surface? */\r
- if( meta == qfalse && ds->shaderInfo->forceMeta == qfalse )\r
- continue;\r
- \r
- /* switch on type */\r
- switch( ds->type )\r
- {\r
- case SURFACE_FACE:\r
- case SURFACE_DECAL:\r
- StripFaceSurface( ds );\r
- SurfaceToMetaTriangles( ds );\r
- break;\r
- \r
- case SURFACE_PATCH:\r
- TriangulatePatchSurface( ds );\r
- break;\r
- \r
- case SURFACE_TRIANGLES:\r
- break;\r
- \r
- case SURFACE_FORCED_META:\r
- case SURFACE_META:\r
- SurfaceToMetaTriangles( ds );\r
- break;\r
- \r
- default:\r
- break;\r
- }\r
- }\r
- \r
- /* print time */\r
- if( (numMapDrawSurfs - e->firstDrawSurf) )\r
- Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );\r
- \r
- /* emit some stats */\r
- Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );\r
- Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );\r
- Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );\r
- Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );\r
- Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );\r
- Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );\r
- \r
- /* tidy things up */\r
- TidyEntitySurfaces( e );\r
-}\r
-\r
-\r
-\r
-/*\r
-PointTriangleIntersect()\r
-assuming that all points lie in plane, determine if pt\r
-is inside the triangle abc\r
-code originally (c) 2001 softSurfer (www.softsurfer.com)\r
-*/\r
-\r
-#define MIN_OUTSIDE_EPSILON -0.01f\r
-#define MAX_OUTSIDE_EPSILON 1.01f\r
-\r
-static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )\r
-{\r
- vec3_t u, v, w;\r
- float uu, uv, vv, wu, wv, d;\r
- \r
- \r
- /* make vectors */\r
- VectorSubtract( b, a, u );\r
- VectorSubtract( c, a, v );\r
- VectorSubtract( pt, a, w );\r
- \r
- /* more setup */\r
- uu = DotProduct( u, u );\r
- uv = DotProduct( u, v );\r
- vv = DotProduct( v, v );\r
- wu = DotProduct( w, u );\r
- wv = DotProduct( w, v );\r
- d = uv * uv - uu * vv;\r
- \r
- /* calculate barycentric coordinates */\r
- bary[ 1 ] = (uv * wv - vv * wu) / d;\r
- if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )\r
- return qfalse;\r
- bary[ 2 ] = (uv * wv - uu * wv) / d;\r
- if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )\r
- return qfalse;\r
- bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);\r
- \r
- /* point is in triangle */\r
- return qtrue;\r
-}\r
-\r
-\r
-\r
-/*\r
-CreateEdge()\r
-sets up an edge structure from a plane and 2 points that the edge ab falls lies in\r
-*/\r
-\r
-typedef struct edge_s\r
-{\r
- vec3_t origin, edge;\r
- vec_t length, kingpinLength;\r
- int kingpin;\r
- vec4_t plane;\r
-}\r
-edge_t;\r
-\r
-void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge )\r
-{\r
- /* copy edge origin */\r
- VectorCopy( a, edge->origin );\r
- \r
- /* create vector aligned with winding direction of edge */\r
- VectorSubtract( b, a, edge->edge );\r
- \r
- if( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) )\r
- edge->kingpin = 0;\r
- else if( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) )\r
- edge->kingpin = 1;\r
- else\r
- edge->kingpin = 2;\r
- edge->kingpinLength = edge->edge[ edge->kingpin ];\r
- \r
- VectorNormalize( edge->edge, edge->edge );\r
- edge->edge[ 3 ] = DotProduct( a, edge->edge );\r
- edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];\r
- \r
- /* create perpendicular plane that edge lies in */\r
- CrossProduct( plane, edge->edge, edge->plane );\r
- edge->plane[ 3 ] = DotProduct( a, edge->plane );\r
-}\r
-\r
-\r
-\r
-/*\r
-FixMetaTJunctions()\r
-fixes t-junctions on meta triangles\r
-*/\r
-\r
-#define TJ_PLANE_EPSILON (1.0f / 8.0f)\r
-#define TJ_EDGE_EPSILON (1.0f / 8.0f)\r
-#define TJ_POINT_EPSILON (1.0f / 8.0f)\r
-\r
-void FixMetaTJunctions( void )\r
-{\r
- int i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;\r
- metaTriangle_t *tri, *newTri;\r
- shaderInfo_t *si;\r
- bspDrawVert_t *a, *b, *c, junc;\r
- float dist, amount;\r
- vec3_t pt;\r
- vec4_t plane;\r
- edge_t edges[ 3 ];\r
- \r
- \r
- /* this code is crap; revisit later */\r
- return;\r
- \r
- /* note it */\r
- Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );\r
- \r
- /* init pacifier */\r
- fOld = -1;\r
- start = I_FloatTime();\r
- \r
- /* walk triangle list */\r
- numTJuncs = 0;\r
- for( i = 0; i < numMetaTriangles; i++ )\r
- {\r
- /* get triangle */\r
- tri = &metaTriangles[ i ];\r
- \r
- /* print pacifier */\r
- f = 10 * i / numMetaTriangles;\r
- if( f != fOld )\r
- {\r
- fOld = f;\r
- Sys_FPrintf( SYS_VRB, "%d...", f );\r
- }\r
- \r
- /* attempt to early out */\r
- si = tri->si;\r
- if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc )\r
- continue;\r
- \r
- /* calculate planes */\r
- VectorCopy( tri->plane, plane );\r
- plane[ 3 ] = tri->plane[ 3 ];\r
- CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );\r
- CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );\r
- CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );\r
- \r
- /* walk meta vert list */\r
- for( j = 0; j < numMetaVerts; j++ )\r
- {\r
- /* get vert */\r
- VectorCopy( metaVerts[ j ].xyz, pt );\r
-\r
- /* debug code: darken verts */\r
- if( i == 0 )\r
- VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );\r
- \r
- /* determine if point lies in the triangle's plane */\r
- dist = DotProduct( pt, plane ) - plane[ 3 ];\r
- if( fabs( dist ) > TJ_PLANE_EPSILON )\r
- continue;\r
- \r
- /* skip this point if it already exists in the triangle */\r
- for( k = 0; k < 3; k++ )\r
- {\r
- if( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&\r
- fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&\r
- fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON )\r
- break;\r
- }\r
- if( k < 3 )\r
- continue;\r
- \r
- /* walk edges */\r
- for( k = 0; k < 3; k++ )\r
- {\r
- /* ignore bogus edges */\r
- if( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON )\r
- continue;\r
- \r
- /* determine if point lies on the edge */\r
- dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];\r
- if( fabs( dist ) > TJ_EDGE_EPSILON )\r
- continue;\r
- \r
- /* determine how far along the edge the point lies */\r
- amount = (pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ]) / edges[ k ].kingpinLength;\r
- if( amount <= 0.0f || amount >= 1.0f )\r
- continue;\r
- \r
- #if 0\r
- dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];\r
- if( dist <= -0.0f || dist >= edges[ k ].length )\r
- continue;\r
- amount = dist / edges[ k ].length;\r
- #endif\r
- \r
- /* debug code: brighten this point */\r
- //% metaVerts[ j ].color[ 0 ][ 0 ] += 5;\r
- //% metaVerts[ j ].color[ 0 ][ 1 ] += 4;\r
- VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );\r
- VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );\r
- \r
-\r
- /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */\r
- a = &metaVerts[ tri->indexes[ k % 3 ] ];\r
- b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];\r
- c = &metaVerts[ tri->indexes[ (k + 2) % 3 ] ];\r
- \r
- /* make new vert */\r
- LerpDrawVertAmount( a, b, amount, &junc );\r
- VectorCopy( pt, junc.xyz );\r
- \r
- /* compare against existing verts */\r
- if( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) )\r
- continue;\r
- \r
- /* see if we can just re-use the existing vert */\r
- if( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) )\r
- vertIndex = j;\r
- else\r
- {\r
- /* find new vertex (note: a and b are invalid pointers after this) */\r
- firstSearchMetaVert = numMetaVerts;\r
- vertIndex = FindMetaVertex( &junc );\r
- if( vertIndex < 0 )\r
- continue;\r
- }\r
- \r
- /* make new triangle */\r
- triIndex = AddMetaTriangle();\r
- if( triIndex < 0 )\r
- continue;\r
- \r
- /* get triangles */\r
- tri = &metaTriangles[ i ];\r
- newTri = &metaTriangles[ triIndex ];\r
- \r
- /* copy the triangle */\r
- memcpy( newTri, tri, sizeof( *tri ) );\r
- \r
- /* fix verts */\r
- tri->indexes[ (k + 1) % 3 ] = vertIndex;\r
- newTri->indexes[ k ] = vertIndex;\r
- \r
- /* recalculate edges */\r
- CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );\r
- CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );\r
- CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );\r
- \r
- /* debug code */\r
- metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;\r
- metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;\r
- metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;\r
- \r
- /* add to counter and end processing of this vert */\r
- numTJuncs++;\r
- break;\r
- }\r
- }\r
- }\r
- \r
- /* print time */\r
- Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );\r
- \r
- /* emit some stats */\r
- Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );\r
-}\r
-\r
-\r
-\r
-/*\r
-SmoothMetaTriangles()\r
-averages coincident vertex normals in the meta triangles\r
-*/\r
-\r
-#define MAX_SAMPLES 256\r
-#define THETA_EPSILON 0.000001\r
-#define EQUAL_NORMAL_EPSILON 0.01\r
-\r
-void SmoothMetaTriangles( void )\r
-{\r
- int i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;\r
- float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;\r
- metaTriangle_t *tri;\r
- float *shadeAngles;\r
- byte *smoothed;\r
- vec3_t average, diff;\r
- int indexes[ MAX_SAMPLES ];\r
- vec3_t votes[ MAX_SAMPLES ];\r
- \r
- \r
- /* note it */\r
- Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );\r
- \r
- /* allocate shade angle table */\r
- shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );\r
- memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );\r
- \r
- /* allocate smoothed table */\r
- cs = (numMetaVerts / 8) + 1;\r
- smoothed = safe_malloc( cs );\r
- memset( smoothed, 0, cs );\r
- \r
- /* set default shade angle */\r
- defaultShadeAngle = DEG2RAD( npDegrees );\r
- maxShadeAngle = 0.0f;\r
- \r
- /* run through every surface and flag verts belonging to non-lightmapped surfaces\r
- and set per-vertex smoothing angle */\r
- for( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )\r
- {\r
- /* get shader for shade angle */\r
- if( tri->si->shadeAngleDegrees > 0.0f )\r
- shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );\r
- else\r
- shadeAngle = defaultShadeAngle;\r
- if( shadeAngle > maxShadeAngle )\r
- maxShadeAngle = shadeAngle;\r
- \r
- /* flag its verts */\r
- for( j = 0; j < 3; j++ )\r
- {\r
- shadeAngles[ tri->indexes[ j ] ] = shadeAngle;\r
- if( shadeAngle <= 0 )\r
- smoothed[ tri->indexes[ j ] >> 3 ] |= (1 << (tri->indexes[ j ] & 7));\r
- }\r
- }\r
- \r
- /* bail if no surfaces have a shade angle */\r
- if( maxShadeAngle <= 0 )\r
- {\r
- Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );\r
- free( shadeAngles );\r
- free( smoothed );\r
- return;\r
- }\r
- \r
- /* init pacifier */\r
- fOld = -1;\r
- start = I_FloatTime();\r
- \r
- /* go through the list of vertexes */\r
- numSmoothed = 0;\r
- for( i = 0; i < numMetaVerts; i++ )\r
- {\r
- /* print pacifier */\r
- f = 10 * i / numMetaVerts;\r
- if( f != fOld )\r
- {\r
- fOld = f;\r
- Sys_FPrintf( SYS_VRB, "%d...", f );\r
- }\r
- \r
- /* already smoothed? */\r
- if( smoothed[ i >> 3 ] & (1 << (i & 7)) )\r
- continue;\r
- \r
- /* clear */\r
- VectorClear( average );\r
- numVerts = 0;\r
- numVotes = 0;\r
- \r
- /* build a table of coincident vertexes */\r
- for( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )\r
- {\r
- /* already smoothed? */\r
- if( smoothed[ j >> 3 ] & (1 << (j & 7)) )\r
- continue;\r
- \r
- /* test vertexes */\r
- if( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse )\r
- continue;\r
- \r
- /* use smallest shade angle */\r
- shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);\r
- \r
- /* check shade angle */\r
- dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );\r
- if( dot > 1.0 )\r
- dot = 1.0;\r
- else if( dot < -1.0 )\r
- dot = -1.0;\r
- testAngle = acos( dot ) + THETA_EPSILON;\r
- if( testAngle >= shadeAngle )\r
- continue;\r
- \r
- /* add to the list */\r
- indexes[ numVerts++ ] = j;\r
- \r
- /* flag vertex */\r
- smoothed[ j >> 3 ] |= (1 << (j & 7));\r
- \r
- /* see if this normal has already been voted */\r
- for( k = 0; k < numVotes; k++ )\r
- {\r
- VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );\r
- if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&\r
- fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&\r
- fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )\r
- break;\r
- }\r
- \r
- /* add a new vote? */\r
- if( k == numVotes && numVotes < MAX_SAMPLES )\r
- {\r
- VectorAdd( average, metaVerts[ j ].normal, average );\r
- VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );\r
- numVotes++;\r
- }\r
- }\r
- \r
- /* don't average for less than 2 verts */\r
- if( numVerts < 2 )\r
- continue;\r
- \r
- /* average normal */\r
- if( VectorNormalize( average, average ) > 0 )\r
- {\r
- /* smooth */\r
- for( j = 0; j < numVerts; j++ )\r
- VectorCopy( average, metaVerts[ indexes[ j ] ].normal );\r
- numSmoothed++;\r
- }\r
- }\r
- \r
- /* free the tables */\r
- free( shadeAngles );\r
- free( smoothed );\r
- \r
- /* print time */\r
- Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );\r
-\r
- /* emit some stats */\r
- Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );\r
-}\r
-\r
-\r
-\r
-/*\r
-AddMetaVertToSurface()\r
-adds a drawvert to a surface unless an existing vert matching already exists\r
-returns the index of that vert (or < 0 on failure)\r
-*/\r
-\r
-int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident )\r
-{\r
- int i;\r
- bspDrawVert_t *dv2;\r
- \r
- \r
- /* go through the verts and find a suitable candidate */\r
- for( i = 0; i < ds->numVerts; i++ )\r
- {\r
- /* get test vert */\r
- dv2 = &ds->verts[ i ];\r
- \r
- /* compare xyz and normal */\r
- if( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse )\r
- continue;\r
- if( VectorCompare( dv1->normal, dv2->normal ) == qfalse )\r
- continue;\r
- \r
- /* good enough at this point */\r
- (*coincident)++;\r
- \r
- /* compare texture coordinates and color */\r
- if( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] )\r
- continue;\r
- if( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] )\r
- continue;\r
- \r
- /* found a winner */\r
- numMergedVerts++;\r
- return i;\r
- }\r
-\r
- /* overflow check */\r
- if( ds->numVerts >= maxSurfaceVerts )\r
- return VERTS_EXCEEDED;\r
- \r
- /* made it this far, add the vert and return */\r
- dv2 = &ds->verts[ ds->numVerts++ ];\r
- *dv2 = *dv1;\r
- return (ds->numVerts - 1);\r
-}\r
-\r
-\r
-\r
-\r
-/*\r
-AddMetaTriangleToSurface()\r
-attempts to add a metatriangle to a surface\r
-returns the score of the triangle added\r
-*/\r
-\r
-#define AXIS_SCORE 100000\r
-#define AXIS_MIN 100000\r
-#define VERT_SCORE 10000\r
-#define SURFACE_SCORE 1000\r
-#define ST_SCORE 50\r
-#define ST_SCORE2 (2 * (ST_SCORE))\r
-\r
-#define ADEQUATE_SCORE ((AXIS_MIN) + 1 * (VERT_SCORE))\r
-#define GOOD_SCORE ((AXIS_MIN) + 2 * (VERT_SCORE) + 4 * (ST_SCORE))\r
-#define PERFECT_SCORE ((AXIS_MIN) + + 3 * (VERT_SCORE) + (SURFACE_SCORE) + 4 * (ST_SCORE))\r
-\r
-static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd )\r
-{\r
- int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];\r
- float lmMax;\r
- vec3_t mins, maxs;\r
- qboolean inTexRange, es, et;\r
- mapDrawSurface_t old;\r
- \r
- \r
- /* overflow check */\r
- if( ds->numIndexes >= maxSurfaceIndexes )\r
- return 0;\r
- \r
- /* test the triangle */\r
- if( ds->entityNum != tri->entityNum ) /* ydnar: added 2002-07-06 */\r
- return 0;\r
- if( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows )\r
- return 0;\r
- if( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize )\r
- return 0;\r
- #if 0\r
- if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&\r
- //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )\r
- DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f )\r
- return 0;\r
- #endif\r
- \r
- /* planar surfaces will only merge with triangles in the same plane */\r
- if( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 )\r
- {\r
- if( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] )\r
- return 0;\r
- if( tri->planeNum >= 0 && tri->planeNum != ds->planeNum )\r
- return 0;\r
- }\r
- \r
- /* set initial score */\r
- score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;\r
- \r
- /* score the the dot product of lightmap axis to plane */\r
- if( (ds->shaderInfo->compileFlags & C_VERTEXLIT) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) )\r
- score += AXIS_SCORE;\r
- else\r
- score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );\r
- \r
- /* preserve old drawsurface if this fails */\r
- memcpy( &old, ds, sizeof( *ds ) );\r
- \r
- /* attempt to add the verts */\r
- coincident = 0;\r
- ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );\r
- bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );\r
- ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );\r
- \r
- /* check vertex underflow */\r
- if( ai < 0 || bi < 0 || ci < 0 )\r
- {\r
- memcpy( ds, &old, sizeof( *ds ) );\r
- return 0;\r
- }\r
- \r
- /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */\r
- score += (coincident * VERT_SCORE);\r
- \r
- /* add new vertex bounds to mins/maxs */\r
- VectorCopy( ds->mins, mins );\r
- VectorCopy( ds->maxs, maxs );\r
- AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );\r
- AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );\r
- AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );\r
- \r
- /* check lightmap bounds overflow (after at least 1 triangle has been added) */\r
- if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&\r
- ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&\r
- (VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse) )\r
- {\r
- /* set maximum size before lightmap scaling (normally 2032 units) */\r
- lmMax = (ds->sampleSize * (ds->shaderInfo->lmCustomWidth - 1));\r
- for( i = 0; i < 3; i++ )\r
- {\r
- if( (maxs[ i ] - mins[ i ]) > lmMax )\r
- {\r
- memcpy( ds, &old, sizeof( *ds ) );\r
- return 0;\r
- }\r
- }\r
- }\r
- \r
- /* check texture range overflow */\r
- oldTexRange[ 0 ] = ds->texRange[ 0 ];\r
- oldTexRange[ 1 ] = ds->texRange[ 1 ];\r
- inTexRange = CalcSurfaceTextureRange( ds );\r
- \r
- es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;\r
- et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;\r
- \r
- if( inTexRange == qfalse && ds->numIndexes > 0 )\r
- {\r
- memcpy( ds, &old, sizeof( *ds ) );\r
- return UNSUITABLE_TRIANGLE;\r
- }\r
- \r
- /* score texture range */\r
- if( ds->texRange[ 0 ] <= oldTexRange[ 0 ] )\r
- score += ST_SCORE2;\r
- else if( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] )\r
- score += ST_SCORE;\r
- \r
- if( ds->texRange[ 1 ] <= oldTexRange[ 1 ] )\r
- score += ST_SCORE2;\r
- else if( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] )\r
- score += ST_SCORE;\r
- \r
- \r
- /* go through the indexes and try to find an existing triangle that matches abc */\r
- for( i = 0; i < ds->numIndexes; i += 3 )\r
- {\r
- /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */\r
- if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ]) ||\r
- (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ]) ||\r
- (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ]) )\r
- {\r
- /* triangle already present */\r
- memcpy( ds, &old, sizeof( *ds ) );\r
- tri->si = NULL;\r
- return 0;\r
- }\r
- \r
- /* rotate the triangle 3x to find an inverse triangle (error case) */\r
- if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ]) ||\r
- (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ]) ||\r
- (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ]) )\r
- {\r
- /* warn about it */\r
- 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
- ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],\r
- ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],\r
- ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );\r
- \r
- /* reverse triangle already present */\r
- memcpy( ds, &old, sizeof( *ds ) );\r
- tri->si = NULL;\r
- return 0;\r
- }\r
- }\r
- \r
- /* add the triangle indexes */\r
- if( ds->numIndexes < maxSurfaceIndexes )\r
- ds->indexes[ ds->numIndexes++ ] = ai;\r
- if( ds->numIndexes < maxSurfaceIndexes )\r
- ds->indexes[ ds->numIndexes++ ] = bi;\r
- if( ds->numIndexes < maxSurfaceIndexes )\r
- ds->indexes[ ds->numIndexes++ ] = ci;\r
- \r
- /* check index overflow */\r
- if( ds->numIndexes >= maxSurfaceIndexes )\r
- {\r
- memcpy( ds, &old, sizeof( *ds ) );\r
- return 0;\r
- }\r
- \r
- /* sanity check the indexes */\r
- if( ds->numIndexes >= 3 &&\r
- (ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||\r
- ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||\r
- ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ]) )\r
- Sys_Printf( "DEG:%d! ", ds->numVerts );\r
- \r
- /* testing only? */\r
- if( testAdd )\r
- memcpy( ds, &old, sizeof( *ds ) );\r
- else\r
- {\r
- /* copy bounds back to surface */\r
- VectorCopy( mins, ds->mins );\r
- VectorCopy( maxs, ds->maxs );\r
- \r
- /* mark triangle as used */\r
- tri->si = NULL;\r
- }\r
- \r
- /* add a side reference */\r
- ds->sideRef = AllocSideRef( tri->side, ds->sideRef );\r
- \r
- /* return to sender */\r
- return score;\r
-}\r
-\r
-\r
-\r
-/*\r
-MetaTrianglesToSurface()\r
-creates map drawsurface(s) from the list of possibles\r
-*/\r
-\r
-static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded )\r
-{\r
- int i, j, f, best, score, bestScore;\r
- metaTriangle_t *seed, *test;\r
- mapDrawSurface_t *ds;\r
- bspDrawVert_t *verts;\r
- int *indexes;\r
- qboolean added;\r
- \r
- \r
- /* allocate arrays */\r
- verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );\r
- indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );\r
- \r
- /* walk the list of triangles */\r
- for( i = 0, seed = possibles; i < numPossibles; i++, seed++ )\r
- {\r
- /* skip this triangle if it has already been merged */\r
- if( seed->si == NULL )\r
- continue;\r
- \r
- /* -----------------------------------------------------------------\r
- initial drawsurf construction\r
- ----------------------------------------------------------------- */\r
- \r
- /* start a new drawsurface */\r
- ds = AllocDrawSurface( SURFACE_META );\r
- ds->entityNum = seed->entityNum;\r
- ds->surfaceNum = seed->surfaceNum;\r
- ds->castShadows = seed->castShadows;\r
- ds->recvShadows = seed->recvShadows;\r
- \r
- ds->shaderInfo = seed->si;\r
- ds->planeNum = seed->planeNum;\r
- ds->fogNum = seed->fogNum;\r
- ds->sampleSize = seed->sampleSize;\r
- ds->verts = verts;\r
- ds->indexes = indexes;\r
- VectorCopy( seed->lightmapAxis, ds->lightmapAxis );\r
- ds->sideRef = AllocSideRef( seed->side, NULL );\r
- \r
- ClearBounds( ds->mins, ds->maxs );\r
- \r
- /* clear verts/indexes */\r
- memset( verts, 0, sizeof( verts ) );\r
- memset( indexes, 0, sizeof( indexes ) );\r
- \r
- /* add the first triangle */\r
- if( AddMetaTriangleToSurface( ds, seed, qfalse ) )\r
- (*numAdded)++;\r
- \r
- /* -----------------------------------------------------------------\r
- add triangles\r
- ----------------------------------------------------------------- */\r
- \r
- /* progressively walk the list until no more triangles can be added */\r
- added = qtrue;\r
- while( added )\r
- {\r
- /* print pacifier */\r
- f = 10 * *numAdded / numMetaTriangles;\r
- if( f > *fOld )\r
- {\r
- *fOld = f;\r
- Sys_FPrintf( SYS_VRB, "%d...", f );\r
- }\r
- \r
- /* reset best score */\r
- best = -1;\r
- bestScore = 0;\r
- added = qfalse;\r
- \r
- /* walk the list of possible candidates for merging */\r
- for( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )\r
- {\r
- /* score this triangle */\r
- score = AddMetaTriangleToSurface( ds, test, qtrue );\r
- if( score > bestScore )\r
- {\r
- best = j;\r
- bestScore = score;\r
- \r
- /* if we have a score over a certain threshold, just use it */\r
- if( bestScore >= GOOD_SCORE )\r
- {\r
- if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )\r
- (*numAdded)++;\r
- \r
- /* reset */\r
- best = -1;\r
- bestScore = 0;\r
- added = qtrue;\r
- }\r
- }\r
- }\r
- \r
- /* add best candidate */\r
- if( best >= 0 && bestScore > ADEQUATE_SCORE )\r
- {\r
- if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )\r
- (*numAdded)++;\r
- \r
- /* reset */\r
- added = qtrue;\r
- }\r
- }\r
- \r
- /* copy the verts and indexes to the new surface */\r
- ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );\r
- memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );\r
- ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );\r
- memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );\r
- \r
- /* classify the surface */\r
- ClassifySurfaces( 1, ds );\r
- \r
- /* add to count */\r
- numMergedSurfaces++;\r
- }\r
- \r
- /* free arrays */\r
- free( verts );\r
- free( indexes );\r
-}\r
-\r
-\r
-\r
-/*\r
-CompareMetaTriangles()\r
-compare function for qsort()\r
-*/\r
-\r
-static int CompareMetaTriangles( const void *a, const void *b )\r
-{\r
- int i, j, av, bv;\r
- vec3_t aMins, bMins;\r
- \r
- \r
- /* shader first */\r
- if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )\r
- return 1;\r
- else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )\r
- return -1;\r
- \r
- /* then fog */\r
- else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )\r
- return 1;\r
- else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )\r
- return -1;\r
- \r
- /* then position in world */\r
- else\r
- {\r
- /* find mins */\r
- VectorSet( aMins, 999999, 999999, 999999 );\r
- VectorSet( bMins, 999999, 999999, 999999 );\r
- for( i = 0; i < 3; i++ )\r
- {\r
- av = ((metaTriangle_t*) a)->indexes[ i ];\r
- bv = ((metaTriangle_t*) b)->indexes[ i ];\r
- for( j = 0; j < 3; j++ )\r
- {\r
- if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )\r
- aMins[ j ] = metaVerts[ av ].xyz[ j ];\r
- if( metaVerts[ bv ].xyz[ j ] < bMins[ j ] )\r
- bMins[ j ] = metaVerts[ bv ].xyz[ j ];\r
- }\r
- }\r
- \r
- /* test it */\r
- for( i = 0; i < 3; i++ )\r
- {\r
- if( aMins[ i ] < bMins[ i ] )\r
- return 1;\r
- else if( aMins[ i ] > bMins[ i ] )\r
- return -1;\r
- }\r
- }\r
- \r
- /* functionally equivalent */\r
- return 0;\r
-}\r
-\r
-\r
-\r
-/*\r
-MergeMetaTriangles()\r
-merges meta triangles into drawsurfaces\r
-*/\r
-\r
-void MergeMetaTriangles( void )\r
-{\r
- int i, j, fOld, start, numAdded;\r
- metaTriangle_t *head, *end;\r
- \r
- \r
- /* only do this if there are meta triangles */\r
- if( numMetaTriangles <= 0 )\r
- return;\r
- \r
- /* note it */\r
- Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );\r
- \r
- /* sort the triangles by shader major, fognum minor */\r
- qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );\r
-\r
- /* init pacifier */\r
- fOld = -1;\r
- start = I_FloatTime();\r
- numAdded = 0;\r
- \r
- /* merge */\r
- for( i = 0; i < numMetaTriangles; i = j )\r
- {\r
- /* get head of list */\r
- head = &metaTriangles[ i ];\r
- \r
- /* find end */\r
- for( j = i + 1; j < numMetaTriangles; j++ )\r
- {\r
- /* get end of list */\r
- end = &metaTriangles[ j ];\r
- if( head->si != end->si || head->fogNum != end->fogNum )\r
- break;\r
- }\r
- \r
- /* try to merge this list of possible merge candidates */\r
- MetaTrianglesToSurface( (j - i), head, &fOld, &numAdded );\r
- }\r
- \r
- /* clear meta triangle list */\r
- ClearMetaTriangles();\r
- \r
- /* print time */\r
- if( i )\r
- Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );\r
- \r
- /* emit some stats */\r
- Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );\r
- Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );\r
-}\r
+/*
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+GtkRadiant is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+
+----------------------------------------------------------------------------------
+
+This code has been altered significantly from its original form, to support
+several games based on the Quake III Arena engine, in the form of "Q3Map2."
+
+------------------------------------------------------------------------------- */
+
+
+
+/* marker */
+#define SURFACE_META_C
+
+
+
+/* dependencies */
+#include "q3map2.h"
+
+
+
+#define LIGHTMAP_EXCEEDED -1
+#define S_EXCEEDED -2
+#define T_EXCEEDED -3
+#define ST_EXCEEDED -4
+#define UNSUITABLE_TRIANGLE -10
+#define VERTS_EXCEEDED -1000
+#define INDEXES_EXCEEDED -2000
+
+#define GROW_META_VERTS 1024
+#define GROW_META_TRIANGLES 1024
+
+static int numMetaSurfaces, numPatchMetaSurfaces;
+
+static int maxMetaVerts = 0;
+static int numMetaVerts = 0;
+static int firstSearchMetaVert = 0;
+static bspDrawVert_t *metaVerts = NULL;
+
+static int maxMetaTriangles = 0;
+static int numMetaTriangles = 0;
+static metaTriangle_t *metaTriangles = NULL;
+
+
+
+/*
+ClearMetaVertexes()
+called before staring a new entity to clear out the triangle list
+*/
+
+void ClearMetaTriangles( void )
+{
+ numMetaVerts = 0;
+ numMetaTriangles = 0;
+}
+
+
+
+/*
+FindMetaVertex()
+finds a matching metavertex in the global list, returning its index
+*/
+
+static int FindMetaVertex( bspDrawVert_t *src )
+{
+ int i;
+ bspDrawVert_t *v, *temp;
+
+
+ /* try to find an existing drawvert */
+ for( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
+ {
+ if( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 )
+ return i;
+ }
+
+ /* enough space? */
+ if( numMetaVerts >= maxMetaVerts )
+ {
+ /* reallocate more room */
+ maxMetaVerts += GROW_META_VERTS;
+ temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );
+ if( metaVerts != NULL )
+ {
+ memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );
+ free( metaVerts );
+ }
+ metaVerts = temp;
+ }
+
+ /* add the triangle */
+ memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );
+ numMetaVerts++;
+
+ /* return the count */
+ return (numMetaVerts - 1);
+}
+
+
+
+/*
+AddMetaTriangle()
+adds a new meta triangle, allocating more memory if necessary
+*/
+
+static int AddMetaTriangle( void )
+{
+ metaTriangle_t *temp;
+
+
+ /* enough space? */
+ if( numMetaTriangles >= maxMetaTriangles )
+ {
+ /* reallocate more room */
+ maxMetaTriangles += GROW_META_TRIANGLES;
+ temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );
+ if( metaTriangles != NULL )
+ {
+ memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );
+ free( metaTriangles );
+ }
+ metaTriangles = temp;
+ }
+
+ /* increment and return */
+ numMetaTriangles++;
+ return numMetaTriangles - 1;
+}
+
+
+
+/*
+FindMetaTriangle()
+finds a matching metatriangle in the global list,
+otherwise adds it and returns the index to the metatriangle
+*/
+
+int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum )
+{
+ int triIndex;
+ vec3_t dir;
+
+
+
+ /* detect degenerate triangles fixme: do something proper here */
+ VectorSubtract( a->xyz, b->xyz, dir );
+ if( VectorLength( dir ) < 0.125f )
+ return -1;
+ VectorSubtract( b->xyz, c->xyz, dir );
+ if( VectorLength( dir ) < 0.125f )
+ return -1;
+ VectorSubtract( c->xyz, a->xyz, dir );
+ if( VectorLength( dir ) < 0.125f )
+ return -1;
+
+ /* find plane */
+ if( planeNum >= 0 )
+ {
+ /* because of precision issues with small triangles, try to use the specified plane */
+ src->planeNum = planeNum;
+ VectorCopy( mapplanes[ planeNum ].normal, src->plane );
+ src->plane[ 3 ] = mapplanes[ planeNum ].dist;
+ }
+ else
+ {
+ /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */
+ src->planeNum = -1;
+ if( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse )
+ return -1;
+ }
+
+ /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */
+ if( VectorLength( a->normal ) <= 0.0f )
+ VectorCopy( src->plane, a->normal );
+ if( VectorLength( b->normal ) <= 0.0f )
+ VectorCopy( src->plane, b->normal );
+ if( VectorLength( c->normal ) <= 0.0f )
+ VectorCopy( src->plane, c->normal );
+
+ /* ydnar 2002-10-04: set lightmap axis if not already set */
+ if( !(src->si->compileFlags & C_VERTEXLIT) &&
+ src->lightmapAxis[ 0 ] == 0.0f && src->lightmapAxis[ 1 ] == 0.0f && src->lightmapAxis[ 2 ] == 0.0f )
+ {
+ /* the shader can specify an explicit lightmap axis */
+ if( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] )
+ VectorCopy( src->si->lightmapAxis, src->lightmapAxis );
+
+ /* new axis-finding code */
+ else
+ CalcLightmapAxis( src->plane, src->lightmapAxis );
+ }
+
+ /* fill out the src triangle */
+ src->indexes[ 0 ] = FindMetaVertex( a );
+ src->indexes[ 1 ] = FindMetaVertex( b );
+ src->indexes[ 2 ] = FindMetaVertex( c );
+
+ /* try to find an existing triangle */
+ #ifdef USE_EXHAUSTIVE_SEARCH
+ {
+ int i;
+ metaTriangle_t *tri;
+
+
+ for( i = 0, tri = metaTriangles; i < numMetaTriangles; i++, tri++ )
+ {
+ if( memcmp( src, tri, sizeof( metaTriangle_t ) ) == 0 )
+ return i;
+ }
+ }
+ #endif
+
+ /* get a new triangle */
+ triIndex = AddMetaTriangle();
+
+ /* add the triangle */
+ memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );
+
+ /* return the triangle index */
+ return triIndex;
+}
+
+
+
+/*
+SurfaceToMetaTriangles()
+converts a classified surface to metatriangles
+*/
+
+static void SurfaceToMetaTriangles( mapDrawSurface_t *ds )
+{
+ int i;
+ metaTriangle_t src;
+ bspDrawVert_t a, b, c;
+
+
+ /* only handle certain types of surfaces */
+ if( ds->type != SURFACE_FACE &&
+ ds->type != SURFACE_META &&
+ ds->type != SURFACE_FORCED_META &&
+ ds->type != SURFACE_DECAL )
+ return;
+
+ /* speed at the expense of memory */
+ firstSearchMetaVert = numMetaVerts;
+
+ /* only handle valid surfaces */
+ if( ds->type != SURFACE_BAD && ds->numVerts >= 3 && ds->numIndexes >= 3 )
+ {
+ /* walk the indexes and create triangles */
+ for( i = 0; i < ds->numIndexes; i += 3 )
+ {
+ /* sanity check the indexes */
+ if( ds->indexes[ i ] == ds->indexes[ i + 1 ] ||
+ ds->indexes[ i ] == ds->indexes[ i + 2 ] ||
+ ds->indexes[ i + 1 ] == ds->indexes[ i + 2 ] )
+ {
+ //% Sys_Printf( "%d! ", ds->numVerts );
+ continue;
+ }
+
+ /* build a metatriangle */
+ src.si = ds->shaderInfo;
+ src.side = (ds->sideRef != NULL ? ds->sideRef->side : NULL);
+ src.entityNum = ds->entityNum;
+ src.surfaceNum = ds->surfaceNum;
+ src.planeNum = ds->planeNum;
+ src.castShadows = ds->castShadows;
+ src.recvShadows = ds->recvShadows;
+ src.fogNum = ds->fogNum;
+ src.sampleSize = ds->sampleSize;
+ VectorCopy( ds->lightmapAxis, src.lightmapAxis );
+
+ /* copy drawverts */
+ memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );
+ memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );
+ memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );
+ FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );
+ }
+
+ /* add to count */
+ numMetaSurfaces++;
+ }
+
+ /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */
+ ClearSurface( ds );
+}
+
+
+
+/*
+TriangulatePatchSurface()
+creates triangles from a patch
+*/
+
+void TriangulatePatchSurface( mapDrawSurface_t *ds )
+{
+ int iterations, x, y, pw[ 5 ], r;
+ mapDrawSurface_t *dsNew;
+ mesh_t src, *subdivided, *mesh;
+
+
+ /* try to early out */
+ if( ds->numVerts == 0 || ds->type != SURFACE_PATCH || patchMeta == qfalse )
+ return;
+
+ /* make a mesh from the drawsurf */
+ src.width = ds->patchWidth;
+ src.height = ds->patchHeight;
+ src.verts = ds->verts;
+ //% subdivided = SubdivideMesh( src, 8, 999 );
+ iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
+ subdivided = SubdivideMesh2( src, iterations ); //% ds->maxIterations
+
+ /* fit it to the curve and remove colinear verts on rows/columns */
+ PutMeshOnCurve( *subdivided );
+ mesh = RemoveLinearMeshColumnsRows( subdivided );
+ FreeMesh( subdivided );
+ //% MakeMeshNormals( mesh );
+
+ /* make a copy of the drawsurface */
+ dsNew = AllocDrawSurface( SURFACE_META );
+ memcpy( dsNew, ds, sizeof( *ds ) );
+
+ /* if the patch is nonsolid, then discard it */
+ if( !(ds->shaderInfo->compileFlags & C_SOLID) )
+ ClearSurface( ds );
+
+ /* set new pointer */
+ ds = dsNew;
+
+ /* basic transmogrification */
+ ds->type = SURFACE_META;
+ ds->numIndexes = 0;
+ ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );
+
+ /* copy the verts in */
+ ds->numVerts = (mesh->width * mesh->height);
+ ds->verts = mesh->verts;
+
+ /* iterate through the mesh quads */
+ for( y = 0; y < (mesh->height - 1); y++ )
+ {
+ for( x = 0; x < (mesh->width - 1); x++ )
+ {
+ /* set indexes */
+ pw[ 0 ] = x + (y * mesh->width);
+ pw[ 1 ] = x + ((y + 1) * mesh->width);
+ pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
+ pw[ 3 ] = x + 1 + (y * mesh->width);
+ pw[ 4 ] = x + (y * mesh->width); /* same as pw[ 0 ] */
+
+ /* set radix */
+ r = (x + y) & 1;
+
+ /* make first triangle */
+ ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
+ ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];
+ ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
+
+ /* make second triangle */
+ ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
+ ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
+ ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];
+ }
+ }
+
+ /* free the mesh, but not the verts */
+ free( mesh );
+
+ /* add to count */
+ numPatchMetaSurfaces++;
+
+ /* classify it */
+ ClassifySurfaces( 1, ds );
+}
+
+
+
+/*
+FanFaceSurface() - ydnar
+creates a tri-fan from a brush face winding
+loosely based on SurfaceAsTriFan()
+*/
+
+void FanFaceSurface( mapDrawSurface_t *ds )
+{
+ int i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
+ bspDrawVert_t *verts, *centroid, *dv;
+ double iv;
+
+
+ /* try to early out */
+ if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
+ return;
+
+ /* add a new vertex at the beginning of the surface */
+ verts = safe_malloc( (ds->numVerts + 1) * sizeof( bspDrawVert_t ) );
+ memset( verts, 0, sizeof( bspDrawVert_t ) );
+ memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
+ free( ds->verts );
+ ds->verts = verts;
+
+ /* add up the drawverts to create a centroid */
+ centroid = &verts[ 0 ];
+ memset( color, 0, 4 * MAX_LIGHTMAPS * sizeof( int ) );
+ for( i = 1, dv = &verts[ 1 ]; i < (ds->numVerts + 1); i++, dv++ )
+ {
+ VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
+ VectorAdd( centroid->normal, dv->normal, centroid->normal );
+ for( j = 0; j < 4; j++ )
+ {
+ for( k = 0; k < MAX_LIGHTMAPS; k++ )
+ color[ k ][ j ] += dv->color[ k ][ j ];
+ if( j < 2 )
+ {
+ centroid->st[ j ] += dv->st[ j ];
+ for( k = 0; k < MAX_LIGHTMAPS; k++ )
+ centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
+ }
+ }
+ }
+
+ /* average the centroid */
+ iv = 1.0f / ds->numVerts;
+ VectorScale( centroid->xyz, iv, centroid->xyz );
+ if( VectorNormalize( centroid->normal, centroid->normal ) <= 0 )
+ VectorCopy( verts[ 1 ].normal, centroid->normal );
+ for( j = 0; j < 4; j++ )
+ {
+ for( k = 0; k < MAX_LIGHTMAPS; k++ )
+ {
+ color[ k ][ j ] /= ds->numVerts;
+ centroid->color[ k ][ j ] = (color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255);
+ }
+ if( j < 2 )
+ {
+ centroid->st[ j ] *= iv;
+ for( k = 0; k < MAX_LIGHTMAPS; k++ )
+ centroid->lightmap[ k ][ j ] *= iv;
+ }
+ }
+
+ /* add to vert count */
+ ds->numVerts++;
+
+ /* fill indexes in triangle fan order */
+ ds->numIndexes = 0;
+ ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
+ for( i = 1; i < ds->numVerts; i++ )
+ {
+ a = 0;
+ b = i;
+ c = (i + 1) % ds->numVerts;
+ c = c ? c : 1;
+ ds->indexes[ ds->numIndexes++ ] = a;
+ ds->indexes[ ds->numIndexes++ ] = b;
+ ds->indexes[ ds->numIndexes++ ] = c;
+ }
+
+ /* add to count */
+ numFanSurfaces++;
+
+ /* classify it */
+ ClassifySurfaces( 1, ds );
+}
+
+
+
+/*
+StripFaceSurface() - ydnar
+attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
+based on SurfaceAsTriStrip()
+*/
+
+#define MAX_INDEXES 1024
+
+void StripFaceSurface( mapDrawSurface_t *ds )
+{
+ int i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
+ vec_t *v1, *v2;
+
+
+ /* try to early out */
+ if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
+ return;
+
+ /* is this a simple triangle? */
+ if( ds->numVerts == 3 )
+ {
+ numIndexes = 3;
+ VectorSet( indexes, 0, 1, 2 );
+ }
+ else
+ {
+ /* ydnar: find smallest coordinate */
+ least = 0;
+ if( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse )
+ {
+ for( i = 0; i < ds->numVerts; i++ )
+ {
+ /* get points */
+ v1 = ds->verts[ i ].xyz;
+ v2 = ds->verts[ least ].xyz;
+
+ /* compare */
+ if( v1[ 0 ] < v2[ 0 ] ||
+ (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ]) ||
+ (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ]) )
+ least = i;
+ }
+ }
+
+ /* determine the triangle strip order */
+ numIndexes = (ds->numVerts - 2) * 3;
+ if( numIndexes > MAX_INDEXES )
+ Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
+
+ /* try all possible orderings of the points looking for a non-degenerate strip order */
+ for( r = 0; r < ds->numVerts; r++ )
+ {
+ /* set rotation */
+ rotate = (r + least) % ds->numVerts;
+
+ /* walk the winding in both directions */
+ for( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
+ {
+ /* make indexes */
+ a = (ds->numVerts - 1 - i + rotate) % ds->numVerts;
+ b = (i + rotate ) % ds->numVerts;
+ c = (ds->numVerts - 2 - i + rotate) % ds->numVerts;
+
+ /* test this triangle */
+ if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
+ break;
+ indexes[ ni++ ] = a;
+ indexes[ ni++ ] = b;
+ indexes[ ni++ ] = c;
+
+ /* handle end case */
+ if( i + 1 != ds->numVerts - 1 - i )
+ {
+ /* make indexes */
+ a = (ds->numVerts - 2 - i + rotate ) % ds->numVerts;
+ b = (i + rotate ) % ds->numVerts;
+ c = (i + 1 + rotate ) % ds->numVerts;
+
+ /* test triangle */
+ if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
+ break;
+ indexes[ ni++ ] = a;
+ indexes[ ni++ ] = b;
+ indexes[ ni++ ] = c;
+ }
+ }
+
+ /* valid strip? */
+ if( ni == numIndexes )
+ break;
+ }
+
+ /* if any triangle in the strip is degenerate, render from a centered fan point instead */
+ if( ni < numIndexes )
+ {
+ FanFaceSurface( ds );
+ return;
+ }
+ }
+
+ /* copy strip triangle indexes */
+ ds->numIndexes = numIndexes;
+ ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
+ memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
+
+ /* add to count */
+ numStripSurfaces++;
+
+ /* classify it */
+ ClassifySurfaces( 1, ds );
+}
+
+
+
+/*
+MakeEntityMetaTriangles()
+builds meta triangles from brush faces (tristrips and fans)
+*/
+
+void MakeEntityMetaTriangles( entity_t *e )
+{
+ int i, f, fOld, start;
+ mapDrawSurface_t *ds;
+
+
+ /* note it */
+ Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
+
+ /* init pacifier */
+ fOld = -1;
+ start = I_FloatTime();
+
+ /* walk the list of surfaces in the entity */
+ for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
+ {
+ /* print pacifier */
+ f = 10 * (i - e->firstDrawSurf) / (numMapDrawSurfs - e->firstDrawSurf);
+ if( f != fOld )
+ {
+ fOld = f;
+ Sys_FPrintf( SYS_VRB, "%d...", f );
+ }
+
+ /* get surface */
+ ds = &mapDrawSurfs[ i ];
+ if( ds->numVerts <= 0 )
+ continue;
+
+ /* ignore autosprite surfaces */
+ if( ds->shaderInfo->autosprite )
+ continue;
+
+ /* meta this surface? */
+ if( meta == qfalse && ds->shaderInfo->forceMeta == qfalse )
+ continue;
+
+ /* switch on type */
+ switch( ds->type )
+ {
+ case SURFACE_FACE:
+ case SURFACE_DECAL:
+ StripFaceSurface( ds );
+ SurfaceToMetaTriangles( ds );
+ break;
+
+ case SURFACE_PATCH:
+ TriangulatePatchSurface( ds );
+ break;
+
+ case SURFACE_TRIANGLES:
+ break;
+
+ case SURFACE_FORCED_META:
+ case SURFACE_META:
+ SurfaceToMetaTriangles( ds );
+ break;
+
+ default:
+ break;
+ }
+ }
+
+ /* print time */
+ if( (numMapDrawSurfs - e->firstDrawSurf) )
+ Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
+
+ /* emit some stats */
+ Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
+ Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
+ Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
+ Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
+ Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
+ Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
+
+ /* tidy things up */
+ TidyEntitySurfaces( e );
+}
+
+
+
+/*
+PointTriangleIntersect()
+assuming that all points lie in plane, determine if pt
+is inside the triangle abc
+code originally (c) 2001 softSurfer (www.softsurfer.com)
+*/
+
+#define MIN_OUTSIDE_EPSILON -0.01f
+#define MAX_OUTSIDE_EPSILON 1.01f
+
+static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )
+{
+ vec3_t u, v, w;
+ float uu, uv, vv, wu, wv, d;
+
+
+ /* make vectors */
+ VectorSubtract( b, a, u );
+ VectorSubtract( c, a, v );
+ VectorSubtract( pt, a, w );
+
+ /* more setup */
+ uu = DotProduct( u, u );
+ uv = DotProduct( u, v );
+ vv = DotProduct( v, v );
+ wu = DotProduct( w, u );
+ wv = DotProduct( w, v );
+ d = uv * uv - uu * vv;
+
+ /* calculate barycentric coordinates */
+ bary[ 1 ] = (uv * wv - vv * wu) / d;
+ if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )
+ return qfalse;
+ bary[ 2 ] = (uv * wv - uu * wv) / d;
+ if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )
+ return qfalse;
+ bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);
+
+ /* point is in triangle */
+ return qtrue;
+}
+
+
+
+/*
+CreateEdge()
+sets up an edge structure from a plane and 2 points that the edge ab falls lies in
+*/
+
+typedef struct edge_s
+{
+ vec3_t origin, edge;
+ vec_t length, kingpinLength;
+ int kingpin;
+ vec4_t plane;
+}
+edge_t;
+
+void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge )
+{
+ /* copy edge origin */
+ VectorCopy( a, edge->origin );
+
+ /* create vector aligned with winding direction of edge */
+ VectorSubtract( b, a, edge->edge );
+
+ if( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) )
+ edge->kingpin = 0;
+ else if( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) )
+ edge->kingpin = 1;
+ else
+ edge->kingpin = 2;
+ edge->kingpinLength = edge->edge[ edge->kingpin ];
+
+ VectorNormalize( edge->edge, edge->edge );
+ edge->edge[ 3 ] = DotProduct( a, edge->edge );
+ edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
+
+ /* create perpendicular plane that edge lies in */
+ CrossProduct( plane, edge->edge, edge->plane );
+ edge->plane[ 3 ] = DotProduct( a, edge->plane );
+}
+
+
+
+/*
+FixMetaTJunctions()
+fixes t-junctions on meta triangles
+*/
+
+#define TJ_PLANE_EPSILON (1.0f / 8.0f)
+#define TJ_EDGE_EPSILON (1.0f / 8.0f)
+#define TJ_POINT_EPSILON (1.0f / 8.0f)
+
+void FixMetaTJunctions( void )
+{
+ int i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
+ metaTriangle_t *tri, *newTri;
+ shaderInfo_t *si;
+ bspDrawVert_t *a, *b, *c, junc;
+ float dist, amount;
+ vec3_t pt;
+ vec4_t plane;
+ edge_t edges[ 3 ];
+
+
+ /* this code is crap; revisit later */
+ return;
+
+ /* note it */
+ Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
+
+ /* init pacifier */
+ fOld = -1;
+ start = I_FloatTime();
+
+ /* walk triangle list */
+ numTJuncs = 0;
+ for( i = 0; i < numMetaTriangles; i++ )
+ {
+ /* get triangle */
+ tri = &metaTriangles[ i ];
+
+ /* print pacifier */
+ f = 10 * i / numMetaTriangles;
+ if( f != fOld )
+ {
+ fOld = f;
+ Sys_FPrintf( SYS_VRB, "%d...", f );
+ }
+
+ /* attempt to early out */
+ si = tri->si;
+ if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc )
+ continue;
+
+ /* calculate planes */
+ VectorCopy( tri->plane, plane );
+ plane[ 3 ] = tri->plane[ 3 ];
+ CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
+ CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
+ CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
+
+ /* walk meta vert list */
+ for( j = 0; j < numMetaVerts; j++ )
+ {
+ /* get vert */
+ VectorCopy( metaVerts[ j ].xyz, pt );
+
+ /* debug code: darken verts */
+ if( i == 0 )
+ VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );
+
+ /* determine if point lies in the triangle's plane */
+ dist = DotProduct( pt, plane ) - plane[ 3 ];
+ if( fabs( dist ) > TJ_PLANE_EPSILON )
+ continue;
+
+ /* skip this point if it already exists in the triangle */
+ for( k = 0; k < 3; k++ )
+ {
+ if( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
+ fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
+ fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON )
+ break;
+ }
+ if( k < 3 )
+ continue;
+
+ /* walk edges */
+ for( k = 0; k < 3; k++ )
+ {
+ /* ignore bogus edges */
+ if( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON )
+ continue;
+
+ /* determine if point lies on the edge */
+ dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
+ if( fabs( dist ) > TJ_EDGE_EPSILON )
+ continue;
+
+ /* determine how far along the edge the point lies */
+ amount = (pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ]) / edges[ k ].kingpinLength;
+ if( amount <= 0.0f || amount >= 1.0f )
+ continue;
+
+ #if 0
+ dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
+ if( dist <= -0.0f || dist >= edges[ k ].length )
+ continue;
+ amount = dist / edges[ k ].length;
+ #endif
+
+ /* debug code: brighten this point */
+ //% metaVerts[ j ].color[ 0 ][ 0 ] += 5;
+ //% metaVerts[ j ].color[ 0 ][ 1 ] += 4;
+ VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );
+ VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );
+
+
+ /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
+ a = &metaVerts[ tri->indexes[ k % 3 ] ];
+ b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];
+ c = &metaVerts[ tri->indexes[ (k + 2) % 3 ] ];
+
+ /* make new vert */
+ LerpDrawVertAmount( a, b, amount, &junc );
+ VectorCopy( pt, junc.xyz );
+
+ /* compare against existing verts */
+ if( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) )
+ continue;
+
+ /* see if we can just re-use the existing vert */
+ if( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) )
+ vertIndex = j;
+ else
+ {
+ /* find new vertex (note: a and b are invalid pointers after this) */
+ firstSearchMetaVert = numMetaVerts;
+ vertIndex = FindMetaVertex( &junc );
+ if( vertIndex < 0 )
+ continue;
+ }
+
+ /* make new triangle */
+ triIndex = AddMetaTriangle();
+ if( triIndex < 0 )
+ continue;
+
+ /* get triangles */
+ tri = &metaTriangles[ i ];
+ newTri = &metaTriangles[ triIndex ];
+
+ /* copy the triangle */
+ memcpy( newTri, tri, sizeof( *tri ) );
+
+ /* fix verts */
+ tri->indexes[ (k + 1) % 3 ] = vertIndex;
+ newTri->indexes[ k ] = vertIndex;
+
+ /* recalculate edges */
+ CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
+ CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
+ CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
+
+ /* debug code */
+ metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
+ metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
+ metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
+
+ /* add to counter and end processing of this vert */
+ numTJuncs++;
+ break;
+ }
+ }
+ }
+
+ /* print time */
+ Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
+
+ /* emit some stats */
+ Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
+}
+
+
+
+/*
+SmoothMetaTriangles()
+averages coincident vertex normals in the meta triangles
+*/
+
+#define MAX_SAMPLES 256
+#define THETA_EPSILON 0.000001
+#define EQUAL_NORMAL_EPSILON 0.01
+
+void SmoothMetaTriangles( void )
+{
+ int i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
+ float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
+ metaTriangle_t *tri;
+ float *shadeAngles;
+ byte *smoothed;
+ vec3_t average, diff;
+ int indexes[ MAX_SAMPLES ];
+ vec3_t votes[ MAX_SAMPLES ];
+
+
+ /* note it */
+ Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
+
+ /* allocate shade angle table */
+ shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
+ memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
+
+ /* allocate smoothed table */
+ cs = (numMetaVerts / 8) + 1;
+ smoothed = safe_malloc( cs );
+ memset( smoothed, 0, cs );
+
+ /* set default shade angle */
+ defaultShadeAngle = DEG2RAD( npDegrees );
+ maxShadeAngle = 0.0f;
+
+ /* run through every surface and flag verts belonging to non-lightmapped surfaces
+ and set per-vertex smoothing angle */
+ for( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
+ {
+ /* get shader for shade angle */
+ if( tri->si->shadeAngleDegrees > 0.0f )
+ shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
+ else
+ shadeAngle = defaultShadeAngle;
+ if( shadeAngle > maxShadeAngle )
+ maxShadeAngle = shadeAngle;
+
+ /* flag its verts */
+ for( j = 0; j < 3; j++ )
+ {
+ shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
+ if( shadeAngle <= 0 )
+ smoothed[ tri->indexes[ j ] >> 3 ] |= (1 << (tri->indexes[ j ] & 7));
+ }
+ }
+
+ /* bail if no surfaces have a shade angle */
+ if( maxShadeAngle <= 0 )
+ {
+ Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
+ free( shadeAngles );
+ free( smoothed );
+ return;
+ }
+
+ /* init pacifier */
+ fOld = -1;
+ start = I_FloatTime();
+
+ /* go through the list of vertexes */
+ numSmoothed = 0;
+ for( i = 0; i < numMetaVerts; i++ )
+ {
+ /* print pacifier */
+ f = 10 * i / numMetaVerts;
+ if( f != fOld )
+ {
+ fOld = f;
+ Sys_FPrintf( SYS_VRB, "%d...", f );
+ }
+
+ /* already smoothed? */
+ if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
+ continue;
+
+ /* clear */
+ VectorClear( average );
+ numVerts = 0;
+ numVotes = 0;
+
+ /* build a table of coincident vertexes */
+ for( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
+ {
+ /* already smoothed? */
+ if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
+ continue;
+
+ /* test vertexes */
+ if( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse )
+ continue;
+
+ /* use smallest shade angle */
+ shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
+
+ /* check shade angle */
+ dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
+ if( dot > 1.0 )
+ dot = 1.0;
+ else if( dot < -1.0 )
+ dot = -1.0;
+ testAngle = acos( dot ) + THETA_EPSILON;
+ if( testAngle >= shadeAngle )
+ continue;
+
+ /* add to the list */
+ indexes[ numVerts++ ] = j;
+
+ /* flag vertex */
+ smoothed[ j >> 3 ] |= (1 << (j & 7));
+
+ /* see if this normal has already been voted */
+ for( k = 0; k < numVotes; k++ )
+ {
+ VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
+ if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
+ fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
+ fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )
+ break;
+ }
+
+ /* add a new vote? */
+ if( k == numVotes && numVotes < MAX_SAMPLES )
+ {
+ VectorAdd( average, metaVerts[ j ].normal, average );
+ VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
+ numVotes++;
+ }
+ }
+
+ /* don't average for less than 2 verts */
+ if( numVerts < 2 )
+ continue;
+
+ /* average normal */
+ if( VectorNormalize( average, average ) > 0 )
+ {
+ /* smooth */
+ for( j = 0; j < numVerts; j++ )
+ VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
+ numSmoothed++;
+ }
+ }
+
+ /* free the tables */
+ free( shadeAngles );
+ free( smoothed );
+
+ /* print time */
+ Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
+
+ /* emit some stats */
+ Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
+}
+
+
+
+/*
+AddMetaVertToSurface()
+adds a drawvert to a surface unless an existing vert matching already exists
+returns the index of that vert (or < 0 on failure)
+*/
+
+int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident )
+{
+ int i;
+ bspDrawVert_t *dv2;
+
+
+ /* go through the verts and find a suitable candidate */
+ for( i = 0; i < ds->numVerts; i++ )
+ {
+ /* get test vert */
+ dv2 = &ds->verts[ i ];
+
+ /* compare xyz and normal */
+ if( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse )
+ continue;
+ if( VectorCompare( dv1->normal, dv2->normal ) == qfalse )
+ continue;
+
+ /* good enough at this point */
+ (*coincident)++;
+
+ /* compare texture coordinates and color */
+ if( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] )
+ continue;
+ if( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] )
+ continue;
+
+ /* found a winner */
+ numMergedVerts++;
+ return i;
+ }
+
+ /* overflow check */
+ if( ds->numVerts >= maxSurfaceVerts )
+ return VERTS_EXCEEDED;
+
+ /* made it this far, add the vert and return */
+ dv2 = &ds->verts[ ds->numVerts++ ];
+ *dv2 = *dv1;
+ return (ds->numVerts - 1);
+}
+
+
+
+
+/*
+AddMetaTriangleToSurface()
+attempts to add a metatriangle to a surface
+returns the score of the triangle added
+*/
+
+#define AXIS_SCORE 100000
+#define AXIS_MIN 100000
+#define VERT_SCORE 10000
+#define SURFACE_SCORE 1000
+#define ST_SCORE 50
+#define ST_SCORE2 (2 * (ST_SCORE))
+
+#define ADEQUATE_SCORE ((AXIS_MIN) + 1 * (VERT_SCORE))
+#define GOOD_SCORE ((AXIS_MIN) + 2 * (VERT_SCORE) + 4 * (ST_SCORE))
+#define PERFECT_SCORE ((AXIS_MIN) + + 3 * (VERT_SCORE) + (SURFACE_SCORE) + 4 * (ST_SCORE))
+
+static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd )
+{
+ int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
+ float lmMax;
+ vec3_t mins, maxs;
+ qboolean inTexRange, es, et;
+ mapDrawSurface_t old;
+
+
+ /* overflow check */
+ if( ds->numIndexes >= maxSurfaceIndexes )
+ return 0;
+
+ /* test the triangle */
+ if( ds->entityNum != tri->entityNum ) /* ydnar: added 2002-07-06 */
+ return 0;
+ if( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows )
+ return 0;
+ if( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize )
+ return 0;
+ #if 0
+ if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
+ //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
+ DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f )
+ return 0;
+ #endif
+
+ /* planar surfaces will only merge with triangles in the same plane */
+ if( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 )
+ {
+ if( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] )
+ return 0;
+ if( tri->planeNum >= 0 && tri->planeNum != ds->planeNum )
+ return 0;
+ }
+
+ /* set initial score */
+ score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
+
+ /* score the the dot product of lightmap axis to plane */
+ if( (ds->shaderInfo->compileFlags & C_VERTEXLIT) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) )
+ score += AXIS_SCORE;
+ else
+ score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
+
+ /* preserve old drawsurface if this fails */
+ memcpy( &old, ds, sizeof( *ds ) );
+
+ /* attempt to add the verts */
+ coincident = 0;
+ ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
+ bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
+ ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
+
+ /* check vertex underflow */
+ if( ai < 0 || bi < 0 || ci < 0 )
+ {
+ memcpy( ds, &old, sizeof( *ds ) );
+ return 0;
+ }
+
+ /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
+ score += (coincident * VERT_SCORE);
+
+ /* add new vertex bounds to mins/maxs */
+ VectorCopy( ds->mins, mins );
+ VectorCopy( ds->maxs, maxs );
+ AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
+ AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
+ AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
+
+ /* check lightmap bounds overflow (after at least 1 triangle has been added) */
+ if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
+ ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
+ (VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse) )
+ {
+ /* set maximum size before lightmap scaling (normally 2032 units) */
+ lmMax = (ds->sampleSize * (ds->shaderInfo->lmCustomWidth - 1));
+ for( i = 0; i < 3; i++ )
+ {
+ if( (maxs[ i ] - mins[ i ]) > lmMax )
+ {
+ memcpy( ds, &old, sizeof( *ds ) );
+ return 0;
+ }
+ }
+ }
+
+ /* check texture range overflow */
+ oldTexRange[ 0 ] = ds->texRange[ 0 ];
+ oldTexRange[ 1 ] = ds->texRange[ 1 ];
+ inTexRange = CalcSurfaceTextureRange( ds );
+
+ es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;
+ et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;
+
+ if( inTexRange == qfalse && ds->numIndexes > 0 )
+ {
+ memcpy( ds, &old, sizeof( *ds ) );
+ return UNSUITABLE_TRIANGLE;
+ }
+
+ /* score texture range */
+ if( ds->texRange[ 0 ] <= oldTexRange[ 0 ] )
+ score += ST_SCORE2;
+ else if( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] )
+ score += ST_SCORE;
+
+ if( ds->texRange[ 1 ] <= oldTexRange[ 1 ] )
+ score += ST_SCORE2;
+ else if( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] )
+ score += ST_SCORE;
+
+
+ /* go through the indexes and try to find an existing triangle that matches abc */
+ for( i = 0; i < ds->numIndexes; i += 3 )
+ {
+ /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
+ if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ]) ||
+ (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ]) ||
+ (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ]) )
+ {
+ /* triangle already present */
+ memcpy( ds, &old, sizeof( *ds ) );
+ tri->si = NULL;
+ return 0;
+ }
+
+ /* rotate the triangle 3x to find an inverse triangle (error case) */
+ if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ]) ||
+ (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ]) ||
+ (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ]) )
+ {
+ /* warn about it */
+ Sys_Printf( "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
+ ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
+ ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
+ ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
+
+ /* reverse triangle already present */
+ memcpy( ds, &old, sizeof( *ds ) );
+ tri->si = NULL;
+ return 0;
+ }
+ }
+
+ /* add the triangle indexes */
+ if( ds->numIndexes < maxSurfaceIndexes )
+ ds->indexes[ ds->numIndexes++ ] = ai;
+ if( ds->numIndexes < maxSurfaceIndexes )
+ ds->indexes[ ds->numIndexes++ ] = bi;
+ if( ds->numIndexes < maxSurfaceIndexes )
+ ds->indexes[ ds->numIndexes++ ] = ci;
+
+ /* check index overflow */
+ if( ds->numIndexes >= maxSurfaceIndexes )
+ {
+ memcpy( ds, &old, sizeof( *ds ) );
+ return 0;
+ }
+
+ /* sanity check the indexes */
+ if( ds->numIndexes >= 3 &&
+ (ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
+ ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
+ ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ]) )
+ Sys_Printf( "DEG:%d! ", ds->numVerts );
+
+ /* testing only? */
+ if( testAdd )
+ memcpy( ds, &old, sizeof( *ds ) );
+ else
+ {
+ /* copy bounds back to surface */
+ VectorCopy( mins, ds->mins );
+ VectorCopy( maxs, ds->maxs );
+
+ /* mark triangle as used */
+ tri->si = NULL;
+ }
+
+ /* add a side reference */
+ ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
+
+ /* return to sender */
+ return score;
+}
+
+
+
+/*
+MetaTrianglesToSurface()
+creates map drawsurface(s) from the list of possibles
+*/
+
+static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded )
+{
+ int i, j, f, best, score, bestScore;
+ metaTriangle_t *seed, *test;
+ mapDrawSurface_t *ds;
+ bspDrawVert_t *verts;
+ int *indexes;
+ qboolean added;
+
+
+ /* allocate arrays */
+ verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
+ indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
+
+ /* walk the list of triangles */
+ for( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
+ {
+ /* skip this triangle if it has already been merged */
+ if( seed->si == NULL )
+ continue;
+
+ /* -----------------------------------------------------------------
+ initial drawsurf construction
+ ----------------------------------------------------------------- */
+
+ /* start a new drawsurface */
+ ds = AllocDrawSurface( SURFACE_META );
+ ds->entityNum = seed->entityNum;
+ ds->surfaceNum = seed->surfaceNum;
+ ds->castShadows = seed->castShadows;
+ ds->recvShadows = seed->recvShadows;
+
+ ds->shaderInfo = seed->si;
+ ds->planeNum = seed->planeNum;
+ ds->fogNum = seed->fogNum;
+ ds->sampleSize = seed->sampleSize;
+ ds->verts = verts;
+ ds->indexes = indexes;
+ VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
+ ds->sideRef = AllocSideRef( seed->side, NULL );
+
+ ClearBounds( ds->mins, ds->maxs );
+
+ /* clear verts/indexes */
+ memset( verts, 0, sizeof( verts ) );
+ memset( indexes, 0, sizeof( indexes ) );
+
+ /* add the first triangle */
+ if( AddMetaTriangleToSurface( ds, seed, qfalse ) )
+ (*numAdded)++;
+
+ /* -----------------------------------------------------------------
+ add triangles
+ ----------------------------------------------------------------- */
+
+ /* progressively walk the list until no more triangles can be added */
+ added = qtrue;
+ while( added )
+ {
+ /* print pacifier */
+ f = 10 * *numAdded / numMetaTriangles;
+ if( f > *fOld )
+ {
+ *fOld = f;
+ Sys_FPrintf( SYS_VRB, "%d...", f );
+ }
+
+ /* reset best score */
+ best = -1;
+ bestScore = 0;
+ added = qfalse;
+
+ /* walk the list of possible candidates for merging */
+ for( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
+ {
+ /* score this triangle */
+ score = AddMetaTriangleToSurface( ds, test, qtrue );
+ if( score > bestScore )
+ {
+ best = j;
+ bestScore = score;
+
+ /* if we have a score over a certain threshold, just use it */
+ if( bestScore >= GOOD_SCORE )
+ {
+ if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
+ (*numAdded)++;
+
+ /* reset */
+ best = -1;
+ bestScore = 0;
+ added = qtrue;
+ }
+ }
+ }
+
+ /* add best candidate */
+ if( best >= 0 && bestScore > ADEQUATE_SCORE )
+ {
+ if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
+ (*numAdded)++;
+
+ /* reset */
+ added = qtrue;
+ }
+ }
+
+ /* copy the verts and indexes to the new surface */
+ ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
+ memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
+ ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
+ memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
+
+ /* classify the surface */
+ ClassifySurfaces( 1, ds );
+
+ /* add to count */
+ numMergedSurfaces++;
+ }
+
+ /* free arrays */
+ free( verts );
+ free( indexes );
+}
+
+
+
+/*
+CompareMetaTriangles()
+compare function for qsort()
+*/
+
+static int CompareMetaTriangles( const void *a, const void *b )
+{
+ int i, j, av, bv;
+ vec3_t aMins, bMins;
+
+
+ /* shader first */
+ if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )
+ return 1;
+ else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )
+ return -1;
+
+ /* then fog */
+ else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )
+ return 1;
+ else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )
+ return -1;
+
+ /* then position in world */
+ else
+ {
+ /* find mins */
+ VectorSet( aMins, 999999, 999999, 999999 );
+ VectorSet( bMins, 999999, 999999, 999999 );
+ for( i = 0; i < 3; i++ )
+ {
+ av = ((metaTriangle_t*) a)->indexes[ i ];
+ bv = ((metaTriangle_t*) b)->indexes[ i ];
+ for( j = 0; j < 3; j++ )
+ {
+ if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )
+ aMins[ j ] = metaVerts[ av ].xyz[ j ];
+ if( metaVerts[ bv ].xyz[ j ] < bMins[ j ] )
+ bMins[ j ] = metaVerts[ bv ].xyz[ j ];
+ }
+ }
+
+ /* test it */
+ for( i = 0; i < 3; i++ )
+ {
+ if( aMins[ i ] < bMins[ i ] )
+ return 1;
+ else if( aMins[ i ] > bMins[ i ] )
+ return -1;
+ }
+ }
+
+ /* functionally equivalent */
+ return 0;
+}
+
+
+
+/*
+MergeMetaTriangles()
+merges meta triangles into drawsurfaces
+*/
+
+void MergeMetaTriangles( void )
+{
+ int i, j, fOld, start, numAdded;
+ metaTriangle_t *head, *end;
+
+
+ /* only do this if there are meta triangles */
+ if( numMetaTriangles <= 0 )
+ return;
+
+ /* note it */
+ Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
+
+ /* sort the triangles by shader major, fognum minor */
+ qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
+
+ /* init pacifier */
+ fOld = -1;
+ start = I_FloatTime();
+ numAdded = 0;
+
+ /* merge */
+ for( i = 0; i < numMetaTriangles; i = j )
+ {
+ /* get head of list */
+ head = &metaTriangles[ i ];
+
+ /* find end */
+ for( j = i + 1; j < numMetaTriangles; j++ )
+ {
+ /* get end of list */
+ end = &metaTriangles[ j ];
+ if( head->si != end->si || head->fogNum != end->fogNum )
+ break;
+ }
+
+ /* try to merge this list of possible merge candidates */
+ MetaTrianglesToSurface( (j - i), head, &fOld, &numAdded );
+ }
+
+ /* clear meta triangle list */
+ ClearMetaTriangles();
+
+ /* print time */
+ if( i )
+ Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
+
+ /* emit some stats */
+ Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
+ Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );
+}
projects / xonotic / netradiant.git / blobdiff