2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 ----------------------------------------------------------------------------------
23 This code has been altered significantly from its original form, to support
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26 ------------------------------------------------------------------------------- */
31 #define SURFACE_META_C
40 #define LIGHTMAP_EXCEEDED -1
43 #define ST_EXCEEDED -4
44 #define UNSUITABLE_TRIANGLE -10
45 #define VERTS_EXCEEDED -1000
46 #define INDEXES_EXCEEDED -2000
48 #define GROW_META_VERTS 1024
49 #define GROW_META_TRIANGLES 1024
51 static int numMetaSurfaces, numPatchMetaSurfaces;
53 static int maxMetaVerts = 0;
54 static int numMetaVerts = 0;
55 static int firstSearchMetaVert = 0;
56 static bspDrawVert_t *metaVerts = NULL;
58 static int maxMetaTriangles = 0;
59 static int numMetaTriangles = 0;
60 static metaTriangle_t *metaTriangles = NULL;
66 called before staring a new entity to clear out the triangle list
69 void ClearMetaTriangles( void )
79 finds a matching metavertex in the global list, returning its index
82 static int FindMetaVertex( bspDrawVert_t *src )
85 bspDrawVert_t *v, *temp;
88 /* try to find an existing drawvert */
89 for( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
91 if( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 )
96 if( numMetaVerts >= maxMetaVerts )
98 /* reallocate more room */
99 maxMetaVerts += GROW_META_VERTS;
100 temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );
101 if( metaVerts != NULL )
103 memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );
109 /* add the triangle */
110 memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );
113 /* return the count */
114 return (numMetaVerts - 1);
121 adds a new meta triangle, allocating more memory if necessary
124 static int AddMetaTriangle( void )
126 metaTriangle_t *temp;
130 if( numMetaTriangles >= maxMetaTriangles )
132 /* reallocate more room */
133 maxMetaTriangles += GROW_META_TRIANGLES;
134 temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );
135 if( metaTriangles != NULL )
137 memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );
138 free( metaTriangles );
140 metaTriangles = temp;
143 /* increment and return */
145 return numMetaTriangles - 1;
152 finds a matching metatriangle in the global list,
153 otherwise adds it and returns the index to the metatriangle
156 int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum )
163 /* detect degenerate triangles fixme: do something proper here */
164 VectorSubtract( a->xyz, b->xyz, dir );
165 if( VectorLength( dir ) < 0.125f )
167 VectorSubtract( b->xyz, c->xyz, dir );
168 if( VectorLength( dir ) < 0.125f )
170 VectorSubtract( c->xyz, a->xyz, dir );
171 if( VectorLength( dir ) < 0.125f )
177 /* because of precision issues with small triangles, try to use the specified plane */
178 src->planeNum = planeNum;
179 VectorCopy( mapplanes[ planeNum ].normal, src->plane );
180 src->plane[ 3 ] = mapplanes[ planeNum ].dist;
184 /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */
186 if( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse )
190 /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */
191 if( VectorLength( a->normal ) <= 0.0f )
192 VectorCopy( src->plane, a->normal );
193 if( VectorLength( b->normal ) <= 0.0f )
194 VectorCopy( src->plane, b->normal );
195 if( VectorLength( c->normal ) <= 0.0f )
196 VectorCopy( src->plane, c->normal );
198 /* ydnar 2002-10-04: set lightmap axis if not already set */
199 if( !(src->si->compileFlags & C_VERTEXLIT) &&
200 src->lightmapAxis[ 0 ] == 0.0f && src->lightmapAxis[ 1 ] == 0.0f && src->lightmapAxis[ 2 ] == 0.0f )
202 /* the shader can specify an explicit lightmap axis */
203 if( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] )
204 VectorCopy( src->si->lightmapAxis, src->lightmapAxis );
206 /* new axis-finding code */
208 CalcLightmapAxis( src->plane, src->lightmapAxis );
211 /* fill out the src triangle */
212 src->indexes[ 0 ] = FindMetaVertex( a );
213 src->indexes[ 1 ] = FindMetaVertex( b );
214 src->indexes[ 2 ] = FindMetaVertex( c );
216 /* try to find an existing triangle */
217 #ifdef USE_EXHAUSTIVE_SEARCH
223 for( i = 0, tri = metaTriangles; i < numMetaTriangles; i++, tri++ )
225 if( memcmp( src, tri, sizeof( metaTriangle_t ) ) == 0 )
231 /* get a new triangle */
232 triIndex = AddMetaTriangle();
234 /* add the triangle */
235 memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );
237 /* return the triangle index */
244 SurfaceToMetaTriangles()
245 converts a classified surface to metatriangles
248 static void SurfaceToMetaTriangles( mapDrawSurface_t *ds )
252 bspDrawVert_t a, b, c;
255 /* only handle certain types of surfaces */
256 if( ds->type != SURFACE_FACE &&
257 ds->type != SURFACE_META &&
258 ds->type != SURFACE_FORCED_META &&
259 ds->type != SURFACE_DECAL )
262 /* speed at the expense of memory */
263 firstSearchMetaVert = numMetaVerts;
265 /* only handle valid surfaces */
266 if( ds->type != SURFACE_BAD && ds->numVerts >= 3 && ds->numIndexes >= 3 )
268 /* walk the indexes and create triangles */
269 for( i = 0; i < ds->numIndexes; i += 3 )
271 /* sanity check the indexes */
272 if( ds->indexes[ i ] == ds->indexes[ i + 1 ] ||
273 ds->indexes[ i ] == ds->indexes[ i + 2 ] ||
274 ds->indexes[ i + 1 ] == ds->indexes[ i + 2 ] )
276 //% Sys_Printf( "%d! ", ds->numVerts );
280 /* build a metatriangle */
281 src.si = ds->shaderInfo;
282 src.side = (ds->sideRef != NULL ? ds->sideRef->side : NULL);
283 src.entityNum = ds->entityNum;
284 src.surfaceNum = ds->surfaceNum;
285 src.planeNum = ds->planeNum;
286 src.castShadows = ds->castShadows;
287 src.recvShadows = ds->recvShadows;
288 src.fogNum = ds->fogNum;
289 src.sampleSize = ds->sampleSize;
290 VectorCopy( ds->lightmapAxis, src.lightmapAxis );
293 memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );
294 memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );
295 memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );
296 FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );
303 /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */
310 TriangulatePatchSurface()
311 creates triangles from a patch
314 void TriangulatePatchSurface( mapDrawSurface_t *ds )
316 int iterations, x, y, pw[ 5 ], r;
317 mapDrawSurface_t *dsNew;
318 mesh_t src, *subdivided, *mesh;
321 /* try to early out */
322 if( ds->numVerts == 0 || ds->type != SURFACE_PATCH || patchMeta == qfalse )
325 /* make a mesh from the drawsurf */
326 src.width = ds->patchWidth;
327 src.height = ds->patchHeight;
328 src.verts = ds->verts;
329 //% subdivided = SubdivideMesh( src, 8, 999 );
330 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
331 subdivided = SubdivideMesh2( src, iterations ); //% ds->maxIterations
333 /* fit it to the curve and remove colinear verts on rows/columns */
334 PutMeshOnCurve( *subdivided );
335 mesh = RemoveLinearMeshColumnsRows( subdivided );
336 FreeMesh( subdivided );
337 //% MakeMeshNormals( mesh );
339 /* make a copy of the drawsurface */
340 dsNew = AllocDrawSurface( SURFACE_META );
341 memcpy( dsNew, ds, sizeof( *ds ) );
343 /* if the patch is nonsolid, then discard it */
344 if( !(ds->shaderInfo->compileFlags & C_SOLID) )
347 /* set new pointer */
350 /* basic transmogrification */
351 ds->type = SURFACE_META;
353 ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );
355 /* copy the verts in */
356 ds->numVerts = (mesh->width * mesh->height);
357 ds->verts = mesh->verts;
359 /* iterate through the mesh quads */
360 for( y = 0; y < (mesh->height - 1); y++ )
362 for( x = 0; x < (mesh->width - 1); x++ )
365 pw[ 0 ] = x + (y * mesh->width);
366 pw[ 1 ] = x + ((y + 1) * mesh->width);
367 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
368 pw[ 3 ] = x + 1 + (y * mesh->width);
369 pw[ 4 ] = x + (y * mesh->width); /* same as pw[ 0 ] */
374 /* make first triangle */
375 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
376 ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];
377 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
379 /* make second triangle */
380 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
381 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
382 ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];
386 /* free the mesh, but not the verts */
390 numPatchMetaSurfaces++;
393 ClassifySurfaces( 1, ds );
399 FanFaceSurface() - ydnar
400 creates a tri-fan from a brush face winding
401 loosely based on SurfaceAsTriFan()
404 void FanFaceSurface( mapDrawSurface_t *ds )
406 int i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
407 bspDrawVert_t *verts, *centroid, *dv;
411 /* try to early out */
412 if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
415 /* add a new vertex at the beginning of the surface */
416 verts = safe_malloc( (ds->numVerts + 1) * sizeof( bspDrawVert_t ) );
417 memset( verts, 0, sizeof( bspDrawVert_t ) );
418 memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
422 /* add up the drawverts to create a centroid */
423 centroid = &verts[ 0 ];
424 memset( color, 0, 4 * MAX_LIGHTMAPS * sizeof( int ) );
425 for( i = 1, dv = &verts[ 1 ]; i < (ds->numVerts + 1); i++, dv++ )
427 VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
428 VectorAdd( centroid->normal, dv->normal, centroid->normal );
429 for( j = 0; j < 4; j++ )
431 for( k = 0; k < MAX_LIGHTMAPS; k++ )
432 color[ k ][ j ] += dv->color[ k ][ j ];
435 centroid->st[ j ] += dv->st[ j ];
436 for( k = 0; k < MAX_LIGHTMAPS; k++ )
437 centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
442 /* average the centroid */
443 iv = 1.0f / ds->numVerts;
444 VectorScale( centroid->xyz, iv, centroid->xyz );
445 if( VectorNormalize( centroid->normal, centroid->normal ) <= 0 )
446 VectorCopy( verts[ 1 ].normal, centroid->normal );
447 for( j = 0; j < 4; j++ )
449 for( k = 0; k < MAX_LIGHTMAPS; k++ )
451 color[ k ][ j ] /= ds->numVerts;
452 centroid->color[ k ][ j ] = (color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255);
456 centroid->st[ j ] *= iv;
457 for( k = 0; k < MAX_LIGHTMAPS; k++ )
458 centroid->lightmap[ k ][ j ] *= iv;
462 /* add to vert count */
465 /* fill indexes in triangle fan order */
467 ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
468 for( i = 1; i < ds->numVerts; i++ )
472 c = (i + 1) % ds->numVerts;
474 ds->indexes[ ds->numIndexes++ ] = a;
475 ds->indexes[ ds->numIndexes++ ] = b;
476 ds->indexes[ ds->numIndexes++ ] = c;
483 ClassifySurfaces( 1, ds );
489 StripFaceSurface() - ydnar
490 attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
491 based on SurfaceAsTriStrip()
494 #define MAX_INDEXES 1024
496 void StripFaceSurface( mapDrawSurface_t *ds )
498 int i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
502 /* try to early out */
503 if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
506 /* is this a simple triangle? */
507 if( ds->numVerts == 3 )
510 VectorSet( indexes, 0, 1, 2 );
514 /* ydnar: find smallest coordinate */
516 if( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse )
518 for( i = 0; i < ds->numVerts; i++ )
521 v1 = ds->verts[ i ].xyz;
522 v2 = ds->verts[ least ].xyz;
525 if( v1[ 0 ] < v2[ 0 ] ||
526 (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ]) ||
527 (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ]) )
532 /* determine the triangle strip order */
533 numIndexes = (ds->numVerts - 2) * 3;
534 if( numIndexes > MAX_INDEXES )
535 Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
537 /* try all possible orderings of the points looking for a non-degenerate strip order */
538 for( r = 0; r < ds->numVerts; r++ )
541 rotate = (r + least) % ds->numVerts;
543 /* walk the winding in both directions */
544 for( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
547 a = (ds->numVerts - 1 - i + rotate) % ds->numVerts;
548 b = (i + rotate ) % ds->numVerts;
549 c = (ds->numVerts - 2 - i + rotate) % ds->numVerts;
551 /* test this triangle */
552 if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
558 /* handle end case */
559 if( i + 1 != ds->numVerts - 1 - i )
562 a = (ds->numVerts - 2 - i + rotate ) % ds->numVerts;
563 b = (i + rotate ) % ds->numVerts;
564 c = (i + 1 + rotate ) % ds->numVerts;
567 if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
576 if( ni == numIndexes )
580 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
581 if( ni < numIndexes )
583 FanFaceSurface( ds );
588 /* copy strip triangle indexes */
589 ds->numIndexes = numIndexes;
590 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
591 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
597 ClassifySurfaces( 1, ds );
603 MakeEntityMetaTriangles()
604 builds meta triangles from brush faces (tristrips and fans)
607 void MakeEntityMetaTriangles( entity_t *e )
609 int i, f, fOld, start;
610 mapDrawSurface_t *ds;
614 Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
618 start = I_FloatTime();
620 /* walk the list of surfaces in the entity */
621 for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
624 f = 10 * (i - e->firstDrawSurf) / (numMapDrawSurfs - e->firstDrawSurf);
628 Sys_FPrintf( SYS_VRB, "%d...", f );
632 ds = &mapDrawSurfs[ i ];
633 if( ds->numVerts <= 0 )
636 /* ignore autosprite surfaces */
637 if( ds->shaderInfo->autosprite )
640 /* meta this surface? */
641 if( meta == qfalse && ds->shaderInfo->forceMeta == qfalse )
649 StripFaceSurface( ds );
650 SurfaceToMetaTriangles( ds );
654 TriangulatePatchSurface( ds );
657 case SURFACE_TRIANGLES:
660 case SURFACE_FORCED_META:
662 SurfaceToMetaTriangles( ds );
671 if( (numMapDrawSurfs - e->firstDrawSurf) )
672 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
674 /* emit some stats */
675 Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
676 Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
677 Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
678 Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
679 Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
680 Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
683 TidyEntitySurfaces( e );
689 PointTriangleIntersect()
690 assuming that all points lie in plane, determine if pt
691 is inside the triangle abc
692 code originally (c) 2001 softSurfer (www.softsurfer.com)
695 #define MIN_OUTSIDE_EPSILON -0.01f
696 #define MAX_OUTSIDE_EPSILON 1.01f
698 static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )
701 float uu, uv, vv, wu, wv, d;
705 VectorSubtract( b, a, u );
706 VectorSubtract( c, a, v );
707 VectorSubtract( pt, a, w );
710 uu = DotProduct( u, u );
711 uv = DotProduct( u, v );
712 vv = DotProduct( v, v );
713 wu = DotProduct( w, u );
714 wv = DotProduct( w, v );
715 d = uv * uv - uu * vv;
717 /* calculate barycentric coordinates */
718 bary[ 1 ] = (uv * wv - vv * wu) / d;
719 if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )
721 bary[ 2 ] = (uv * wv - uu * wv) / d;
722 if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )
724 bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);
726 /* point is in triangle */
734 sets up an edge structure from a plane and 2 points that the edge ab falls lies in
737 typedef struct edge_s
740 vec_t length, kingpinLength;
746 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge )
748 /* copy edge origin */
749 VectorCopy( a, edge->origin );
751 /* create vector aligned with winding direction of edge */
752 VectorSubtract( b, a, edge->edge );
754 if( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) )
756 else if( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) )
760 edge->kingpinLength = edge->edge[ edge->kingpin ];
762 VectorNormalize( edge->edge, edge->edge );
763 edge->edge[ 3 ] = DotProduct( a, edge->edge );
764 edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
766 /* create perpendicular plane that edge lies in */
767 CrossProduct( plane, edge->edge, edge->plane );
768 edge->plane[ 3 ] = DotProduct( a, edge->plane );
775 fixes t-junctions on meta triangles
778 #define TJ_PLANE_EPSILON (1.0f / 8.0f)
779 #define TJ_EDGE_EPSILON (1.0f / 8.0f)
780 #define TJ_POINT_EPSILON (1.0f / 8.0f)
782 void FixMetaTJunctions( void )
784 int i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
785 metaTriangle_t *tri, *newTri;
787 bspDrawVert_t *a, *b, *c, junc;
794 /* this code is crap; revisit later */
798 Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
802 start = I_FloatTime();
804 /* walk triangle list */
806 for( i = 0; i < numMetaTriangles; i++ )
809 tri = &metaTriangles[ i ];
812 f = 10 * i / numMetaTriangles;
816 Sys_FPrintf( SYS_VRB, "%d...", f );
819 /* attempt to early out */
821 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc )
824 /* calculate planes */
825 VectorCopy( tri->plane, plane );
826 plane[ 3 ] = tri->plane[ 3 ];
827 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
828 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
829 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
831 /* walk meta vert list */
832 for( j = 0; j < numMetaVerts; j++ )
835 VectorCopy( metaVerts[ j ].xyz, pt );
837 /* debug code: darken verts */
839 VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );
841 /* determine if point lies in the triangle's plane */
842 dist = DotProduct( pt, plane ) - plane[ 3 ];
843 if( fabs( dist ) > TJ_PLANE_EPSILON )
846 /* skip this point if it already exists in the triangle */
847 for( k = 0; k < 3; k++ )
849 if( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
850 fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
851 fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON )
858 for( k = 0; k < 3; k++ )
860 /* ignore bogus edges */
861 if( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON )
864 /* determine if point lies on the edge */
865 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
866 if( fabs( dist ) > TJ_EDGE_EPSILON )
869 /* determine how far along the edge the point lies */
870 amount = (pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ]) / edges[ k ].kingpinLength;
871 if( amount <= 0.0f || amount >= 1.0f )
875 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
876 if( dist <= -0.0f || dist >= edges[ k ].length )
878 amount = dist / edges[ k ].length;
881 /* debug code: brighten this point */
882 //% metaVerts[ j ].color[ 0 ][ 0 ] += 5;
883 //% metaVerts[ j ].color[ 0 ][ 1 ] += 4;
884 VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );
885 VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );
888 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
889 a = &metaVerts[ tri->indexes[ k % 3 ] ];
890 b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];
891 c = &metaVerts[ tri->indexes[ (k + 2) % 3 ] ];
894 LerpDrawVertAmount( a, b, amount, &junc );
895 VectorCopy( pt, junc.xyz );
897 /* compare against existing verts */
898 if( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) )
901 /* see if we can just re-use the existing vert */
902 if( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) )
906 /* find new vertex (note: a and b are invalid pointers after this) */
907 firstSearchMetaVert = numMetaVerts;
908 vertIndex = FindMetaVertex( &junc );
913 /* make new triangle */
914 triIndex = AddMetaTriangle();
919 tri = &metaTriangles[ i ];
920 newTri = &metaTriangles[ triIndex ];
922 /* copy the triangle */
923 memcpy( newTri, tri, sizeof( *tri ) );
926 tri->indexes[ (k + 1) % 3 ] = vertIndex;
927 newTri->indexes[ k ] = vertIndex;
929 /* recalculate edges */
930 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
931 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
932 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
935 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
936 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
937 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
939 /* add to counter and end processing of this vert */
947 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
949 /* emit some stats */
950 Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
956 SmoothMetaTriangles()
957 averages coincident vertex normals in the meta triangles
960 #define MAX_SAMPLES 256
961 #define THETA_EPSILON 0.000001
962 #define EQUAL_NORMAL_EPSILON 0.01
964 void SmoothMetaTriangles( void )
966 int i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
967 float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
971 vec3_t average, diff;
972 int indexes[ MAX_SAMPLES ];
973 vec3_t votes[ MAX_SAMPLES ];
977 Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
979 /* allocate shade angle table */
980 shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
981 memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
983 /* allocate smoothed table */
984 cs = (numMetaVerts / 8) + 1;
985 smoothed = safe_malloc( cs );
986 memset( smoothed, 0, cs );
988 /* set default shade angle */
989 defaultShadeAngle = DEG2RAD( npDegrees );
990 maxShadeAngle = 0.0f;
992 /* run through every surface and flag verts belonging to non-lightmapped surfaces
993 and set per-vertex smoothing angle */
994 for( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
996 /* get shader for shade angle */
997 if( tri->si->shadeAngleDegrees > 0.0f )
998 shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1000 shadeAngle = defaultShadeAngle;
1001 if( shadeAngle > maxShadeAngle )
1002 maxShadeAngle = shadeAngle;
1004 /* flag its verts */
1005 for( j = 0; j < 3; j++ )
1007 shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1008 if( shadeAngle <= 0 )
1009 smoothed[ tri->indexes[ j ] >> 3 ] |= (1 << (tri->indexes[ j ] & 7));
1013 /* bail if no surfaces have a shade angle */
1014 if( maxShadeAngle <= 0 )
1016 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1017 free( shadeAngles );
1024 start = I_FloatTime();
1026 /* go through the list of vertexes */
1028 for( i = 0; i < numMetaVerts; i++ )
1030 /* print pacifier */
1031 f = 10 * i / numMetaVerts;
1035 Sys_FPrintf( SYS_VRB, "%d...", f );
1038 /* already smoothed? */
1039 if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
1043 VectorClear( average );
1047 /* build a table of coincident vertexes */
1048 for( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1050 /* already smoothed? */
1051 if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
1055 if( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse )
1058 /* use smallest shade angle */
1059 shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
1061 /* check shade angle */
1062 dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1065 else if( dot < -1.0 )
1067 testAngle = acos( dot ) + THETA_EPSILON;
1068 if( testAngle >= shadeAngle )
1071 /* add to the list */
1072 indexes[ numVerts++ ] = j;
1075 smoothed[ j >> 3 ] |= (1 << (j & 7));
1077 /* see if this normal has already been voted */
1078 for( k = 0; k < numVotes; k++ )
1080 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1081 if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1082 fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1083 fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )
1087 /* add a new vote? */
1088 if( k == numVotes && numVotes < MAX_SAMPLES )
1090 VectorAdd( average, metaVerts[ j ].normal, average );
1091 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1096 /* don't average for less than 2 verts */
1100 /* average normal */
1101 if( VectorNormalize( average, average ) > 0 )
1104 for( j = 0; j < numVerts; j++ )
1105 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1110 /* free the tables */
1111 free( shadeAngles );
1115 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1117 /* emit some stats */
1118 Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1124 AddMetaVertToSurface()
1125 adds a drawvert to a surface unless an existing vert matching already exists
1126 returns the index of that vert (or < 0 on failure)
1129 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident )
1135 /* go through the verts and find a suitable candidate */
1136 for( i = 0; i < ds->numVerts; i++ )
1139 dv2 = &ds->verts[ i ];
1141 /* compare xyz and normal */
1142 if( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse )
1144 if( VectorCompare( dv1->normal, dv2->normal ) == qfalse )
1147 /* good enough at this point */
1150 /* compare texture coordinates and color */
1151 if( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] )
1153 if( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] )
1156 /* found a winner */
1161 /* overflow check */
1162 if( ds->numVerts >= maxSurfaceVerts )
1163 return VERTS_EXCEEDED;
1165 /* made it this far, add the vert and return */
1166 dv2 = &ds->verts[ ds->numVerts++ ];
1168 return (ds->numVerts - 1);
1175 AddMetaTriangleToSurface()
1176 attempts to add a metatriangle to a surface
1177 returns the score of the triangle added
1180 #define AXIS_SCORE 100000
1181 #define AXIS_MIN 100000
1182 #define VERT_SCORE 10000
1183 #define SURFACE_SCORE 1000
1185 #define ST_SCORE2 (2 * (ST_SCORE))
1187 #define ADEQUATE_SCORE ((AXIS_MIN) + 1 * (VERT_SCORE))
1188 #define GOOD_SCORE ((AXIS_MIN) + 2 * (VERT_SCORE) + 4 * (ST_SCORE))
1189 #define PERFECT_SCORE ((AXIS_MIN) + + 3 * (VERT_SCORE) + (SURFACE_SCORE) + 4 * (ST_SCORE))
1191 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd )
1193 int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1196 qboolean inTexRange, es, et;
1197 mapDrawSurface_t old;
1200 /* overflow check */
1201 if( ds->numIndexes >= maxSurfaceIndexes )
1204 /* test the triangle */
1205 if( ds->entityNum != tri->entityNum ) /* ydnar: added 2002-07-06 */
1207 if( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows )
1209 if( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize )
1212 if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1213 //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1214 DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f )
1218 /* planar surfaces will only merge with triangles in the same plane */
1219 if( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 )
1221 if( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] )
1223 if( tri->planeNum >= 0 && tri->planeNum != ds->planeNum )
1227 /* set initial score */
1228 score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1230 /* score the the dot product of lightmap axis to plane */
1231 if( (ds->shaderInfo->compileFlags & C_VERTEXLIT) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) )
1232 score += AXIS_SCORE;
1234 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1236 /* preserve old drawsurface if this fails */
1237 memcpy( &old, ds, sizeof( *ds ) );
1239 /* attempt to add the verts */
1241 ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1242 bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1243 ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1245 /* check vertex underflow */
1246 if( ai < 0 || bi < 0 || ci < 0 )
1248 memcpy( ds, &old, sizeof( *ds ) );
1252 /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1253 score += (coincident * VERT_SCORE);
1255 /* add new vertex bounds to mins/maxs */
1256 VectorCopy( ds->mins, mins );
1257 VectorCopy( ds->maxs, maxs );
1258 AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1259 AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1260 AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1262 /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1263 if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1264 ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1265 (VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse) )
1267 /* set maximum size before lightmap scaling (normally 2032 units) */
1268 lmMax = (ds->sampleSize * (ds->shaderInfo->lmCustomWidth - 1));
1269 for( i = 0; i < 3; i++ )
1271 if( (maxs[ i ] - mins[ i ]) > lmMax )
1273 memcpy( ds, &old, sizeof( *ds ) );
1279 /* check texture range overflow */
1280 oldTexRange[ 0 ] = ds->texRange[ 0 ];
1281 oldTexRange[ 1 ] = ds->texRange[ 1 ];
1282 inTexRange = CalcSurfaceTextureRange( ds );
1284 es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;
1285 et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;
1287 if( inTexRange == qfalse && ds->numIndexes > 0 )
1289 memcpy( ds, &old, sizeof( *ds ) );
1290 return UNSUITABLE_TRIANGLE;
1293 /* score texture range */
1294 if( ds->texRange[ 0 ] <= oldTexRange[ 0 ] )
1296 else if( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] )
1299 if( ds->texRange[ 1 ] <= oldTexRange[ 1 ] )
1301 else if( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] )
1305 /* go through the indexes and try to find an existing triangle that matches abc */
1306 for( i = 0; i < ds->numIndexes; i += 3 )
1308 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1309 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ]) ||
1310 (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ]) ||
1311 (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ]) )
1313 /* triangle already present */
1314 memcpy( ds, &old, sizeof( *ds ) );
1319 /* rotate the triangle 3x to find an inverse triangle (error case) */
1320 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ]) ||
1321 (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ]) ||
1322 (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ]) )
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",
1326 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1327 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1328 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1330 /* reverse triangle already present */
1331 memcpy( ds, &old, sizeof( *ds ) );
1337 /* add the triangle indexes */
1338 if( ds->numIndexes < maxSurfaceIndexes )
1339 ds->indexes[ ds->numIndexes++ ] = ai;
1340 if( ds->numIndexes < maxSurfaceIndexes )
1341 ds->indexes[ ds->numIndexes++ ] = bi;
1342 if( ds->numIndexes < maxSurfaceIndexes )
1343 ds->indexes[ ds->numIndexes++ ] = ci;
1345 /* check index overflow */
1346 if( ds->numIndexes >= maxSurfaceIndexes )
1348 memcpy( ds, &old, sizeof( *ds ) );
1352 /* sanity check the indexes */
1353 if( ds->numIndexes >= 3 &&
1354 (ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1355 ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1356 ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ]) )
1357 Sys_Printf( "DEG:%d! ", ds->numVerts );
1361 memcpy( ds, &old, sizeof( *ds ) );
1364 /* copy bounds back to surface */
1365 VectorCopy( mins, ds->mins );
1366 VectorCopy( maxs, ds->maxs );
1368 /* mark triangle as used */
1372 /* add a side reference */
1373 ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1375 /* return to sender */
1382 MetaTrianglesToSurface()
1383 creates map drawsurface(s) from the list of possibles
1386 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded )
1388 int i, j, f, best, score, bestScore;
1389 metaTriangle_t *seed, *test;
1390 mapDrawSurface_t *ds;
1391 bspDrawVert_t *verts;
1396 /* allocate arrays */
1397 verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1398 indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1400 /* walk the list of triangles */
1401 for( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1403 /* skip this triangle if it has already been merged */
1404 if( seed->si == NULL )
1407 /* -----------------------------------------------------------------
1408 initial drawsurf construction
1409 ----------------------------------------------------------------- */
1411 /* start a new drawsurface */
1412 ds = AllocDrawSurface( SURFACE_META );
1413 ds->entityNum = seed->entityNum;
1414 ds->surfaceNum = seed->surfaceNum;
1415 ds->castShadows = seed->castShadows;
1416 ds->recvShadows = seed->recvShadows;
1418 ds->shaderInfo = seed->si;
1419 ds->planeNum = seed->planeNum;
1420 ds->fogNum = seed->fogNum;
1421 ds->sampleSize = seed->sampleSize;
1423 ds->indexes = indexes;
1424 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1425 ds->sideRef = AllocSideRef( seed->side, NULL );
1427 ClearBounds( ds->mins, ds->maxs );
1429 /* clear verts/indexes */
1430 memset( verts, 0, sizeof( verts ) );
1431 memset( indexes, 0, sizeof( indexes ) );
1433 /* add the first triangle */
1434 if( AddMetaTriangleToSurface( ds, seed, qfalse ) )
1437 /* -----------------------------------------------------------------
1439 ----------------------------------------------------------------- */
1441 /* progressively walk the list until no more triangles can be added */
1445 /* print pacifier */
1446 f = 10 * *numAdded / numMetaTriangles;
1450 Sys_FPrintf( SYS_VRB, "%d...", f );
1453 /* reset best score */
1458 /* walk the list of possible candidates for merging */
1459 for( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1461 /* score this triangle */
1462 score = AddMetaTriangleToSurface( ds, test, qtrue );
1463 if( score > bestScore )
1468 /* if we have a score over a certain threshold, just use it */
1469 if( bestScore >= GOOD_SCORE )
1471 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1482 /* add best candidate */
1483 if( best >= 0 && bestScore > ADEQUATE_SCORE )
1485 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1493 /* copy the verts and indexes to the new surface */
1494 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1495 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1496 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1497 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1499 /* classify the surface */
1500 ClassifySurfaces( 1, ds );
1503 numMergedSurfaces++;
1514 CompareMetaTriangles()
1515 compare function for qsort()
1518 static int CompareMetaTriangles( const void *a, const void *b )
1521 vec3_t aMins, bMins;
1525 if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )
1527 else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )
1531 else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )
1533 else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )
1536 /* then position in world */
1540 VectorSet( aMins, 999999, 999999, 999999 );
1541 VectorSet( bMins, 999999, 999999, 999999 );
1542 for( i = 0; i < 3; i++ )
1544 av = ((metaTriangle_t*) a)->indexes[ i ];
1545 bv = ((metaTriangle_t*) b)->indexes[ i ];
1546 for( j = 0; j < 3; j++ )
1548 if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )
1549 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1550 if( metaVerts[ bv ].xyz[ j ] < bMins[ j ] )
1551 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1556 for( i = 0; i < 3; i++ )
1558 if( aMins[ i ] < bMins[ i ] )
1560 else if( aMins[ i ] > bMins[ i ] )
1565 /* functionally equivalent */
1572 MergeMetaTriangles()
1573 merges meta triangles into drawsurfaces
1576 void MergeMetaTriangles( void )
1578 int i, j, fOld, start, numAdded;
1579 metaTriangle_t *head, *end;
1582 /* only do this if there are meta triangles */
1583 if( numMetaTriangles <= 0 )
1587 Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1589 /* sort the triangles by shader major, fognum minor */
1590 qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1594 start = I_FloatTime();
1598 for( i = 0; i < numMetaTriangles; i = j )
1600 /* get head of list */
1601 head = &metaTriangles[ i ];
1604 for( j = i + 1; j < numMetaTriangles; j++ )
1606 /* get end of list */
1607 end = &metaTriangles[ j ];
1608 if( head->si != end->si || head->fogNum != end->fogNum )
1612 /* try to merge this list of possible merge candidates */
1613 MetaTrianglesToSurface( (j - i), head, &fOld, &numAdded );
1616 /* clear meta triangle list */
1617 ClearMetaTriangles();
1621 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1623 /* emit some stats */
1624 Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1625 Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );