1 /* -------------------------------------------------------------------------------
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
6 This file is part of GtkRadiant.
8 GtkRadiant is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 GtkRadiant is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GtkRadiant; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 ----------------------------------------------------------------------------------
24 This code has been altered significantly from its original form, to support
25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
27 ------------------------------------------------------------------------------- */
32 #define SURFACE_META_C
41 #define LIGHTMAP_EXCEEDED -1
44 #define ST_EXCEEDED -4
45 #define UNSUITABLE_TRIANGLE -10
46 #define VERTS_EXCEEDED -1000
47 #define INDEXES_EXCEEDED -2000
49 #define GROW_META_VERTS 1024
50 #define GROW_META_TRIANGLES 1024
52 static int numMetaSurfaces, numPatchMetaSurfaces;
54 static int maxMetaVerts = 0;
55 static int numMetaVerts = 0;
56 static int firstSearchMetaVert = 0;
57 static bspDrawVert_t *metaVerts = NULL;
59 static int maxMetaTriangles = 0;
60 static int numMetaTriangles = 0;
61 static metaTriangle_t *metaTriangles = NULL;
67 called before staring a new entity to clear out the triangle list
70 void ClearMetaTriangles( void )
80 finds a matching metavertex in the global list, returning its index
83 static int FindMetaVertex( bspDrawVert_t *src )
86 bspDrawVert_t *v, *temp;
89 /* try to find an existing drawvert */
90 for( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
92 if( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 )
97 if( numMetaVerts >= maxMetaVerts )
99 /* reallocate more room */
100 maxMetaVerts += GROW_META_VERTS;
101 temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );
102 if( metaVerts != NULL )
104 memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );
110 /* add the triangle */
111 memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );
114 /* return the count */
115 return (numMetaVerts - 1);
122 adds a new meta triangle, allocating more memory if necessary
125 static int AddMetaTriangle( void )
127 metaTriangle_t *temp;
131 if( numMetaTriangles >= maxMetaTriangles )
133 /* reallocate more room */
134 maxMetaTriangles += GROW_META_TRIANGLES;
135 temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );
136 if( metaTriangles != NULL )
138 memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );
139 free( metaTriangles );
141 metaTriangles = temp;
144 /* increment and return */
146 return numMetaTriangles - 1;
153 finds a matching metatriangle in the global list,
154 otherwise adds it and returns the index to the metatriangle
157 int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum )
164 /* detect degenerate triangles fixme: do something proper here */
165 VectorSubtract( a->xyz, b->xyz, dir );
166 if( VectorLength( dir ) < 0.125f )
168 VectorSubtract( b->xyz, c->xyz, dir );
169 if( VectorLength( dir ) < 0.125f )
171 VectorSubtract( c->xyz, a->xyz, dir );
172 if( VectorLength( dir ) < 0.125f )
178 /* because of precision issues with small triangles, try to use the specified plane */
179 src->planeNum = planeNum;
180 VectorCopy( mapplanes[ planeNum ].normal, src->plane );
181 src->plane[ 3 ] = mapplanes[ planeNum ].dist;
185 /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */
187 if( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse )
191 /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */
192 if( VectorLength( a->normal ) <= 0.0f )
193 VectorCopy( src->plane, a->normal );
194 if( VectorLength( b->normal ) <= 0.0f )
195 VectorCopy( src->plane, b->normal );
196 if( VectorLength( c->normal ) <= 0.0f )
197 VectorCopy( src->plane, c->normal );
199 /* ydnar 2002-10-04: set lightmap axis if not already set */
200 if( !(src->si->compileFlags & C_VERTEXLIT) &&
201 src->lightmapAxis[ 0 ] == 0.0f && src->lightmapAxis[ 1 ] == 0.0f && src->lightmapAxis[ 2 ] == 0.0f )
203 /* the shader can specify an explicit lightmap axis */
204 if( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] )
205 VectorCopy( src->si->lightmapAxis, src->lightmapAxis );
207 /* new axis-finding code */
209 CalcLightmapAxis( src->plane, src->lightmapAxis );
212 /* fill out the src triangle */
213 src->indexes[ 0 ] = FindMetaVertex( a );
214 src->indexes[ 1 ] = FindMetaVertex( b );
215 src->indexes[ 2 ] = FindMetaVertex( c );
217 /* try to find an existing triangle */
218 #ifdef USE_EXHAUSTIVE_SEARCH
224 for( i = 0, tri = metaTriangles; i < numMetaTriangles; i++, tri++ )
226 if( memcmp( src, tri, sizeof( metaTriangle_t ) ) == 0 )
232 /* get a new triangle */
233 triIndex = AddMetaTriangle();
235 /* add the triangle */
236 memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );
238 /* return the triangle index */
245 SurfaceToMetaTriangles()
246 converts a classified surface to metatriangles
249 static void SurfaceToMetaTriangles( mapDrawSurface_t *ds )
253 bspDrawVert_t a, b, c;
256 /* only handle certain types of surfaces */
257 if( ds->type != SURFACE_FACE &&
258 ds->type != SURFACE_META &&
259 ds->type != SURFACE_FORCED_META &&
260 ds->type != SURFACE_DECAL )
263 /* speed at the expense of memory */
264 firstSearchMetaVert = numMetaVerts;
266 /* only handle valid surfaces */
267 if( ds->type != SURFACE_BAD && ds->numVerts >= 3 && ds->numIndexes >= 3 )
269 /* walk the indexes and create triangles */
270 for( i = 0; i < ds->numIndexes; i += 3 )
272 /* sanity check the indexes */
273 if( ds->indexes[ i ] == ds->indexes[ i + 1 ] ||
274 ds->indexes[ i ] == ds->indexes[ i + 2 ] ||
275 ds->indexes[ i + 1 ] == ds->indexes[ i + 2 ] )
277 //% Sys_Printf( "%d! ", ds->numVerts );
281 /* build a metatriangle */
282 src.si = ds->shaderInfo;
283 src.side = (ds->sideRef != NULL ? ds->sideRef->side : NULL);
284 src.entityNum = ds->entityNum;
285 src.surfaceNum = ds->surfaceNum;
286 src.planeNum = ds->planeNum;
287 src.castShadows = ds->castShadows;
288 src.recvShadows = ds->recvShadows;
289 src.fogNum = ds->fogNum;
290 src.sampleSize = ds->sampleSize;
291 src.shadeAngleDegrees = ds->shadeAngleDegrees;
292 VectorCopy( ds->lightmapAxis, src.lightmapAxis );
295 memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );
296 memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );
297 memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );
298 FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );
305 /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */
312 TriangulatePatchSurface()
313 creates triangles from a patch
316 void TriangulatePatchSurface( entity_t *e , mapDrawSurface_t *ds )
318 int iterations, x, y, pw[ 5 ], r;
319 mapDrawSurface_t *dsNew;
320 mesh_t src, *subdivided, *mesh;
323 int patchSubdivision;
325 /* vortex: _patchMeta, _patchQuality, _patchSubdivide support */
326 forcePatchMeta = IntForKey(e, "_patchMeta" );
328 forcePatchMeta = IntForKey(e, "patchMeta" );
329 patchQuality = IntForKey(e, "_patchQuality" );
331 patchQuality = IntForKey(e, "patchQuality" );
334 patchSubdivision = IntForKey(e, "_patchSubdivide" );
335 if (!patchSubdivision)
336 patchSubdivision = IntForKey(e, "patchSubdivide" );
338 /* try to early out */
339 if(ds->numVerts == 0 || ds->type != SURFACE_PATCH || ( patchMeta == qfalse && !forcePatchMeta) )
341 /* make a mesh from the drawsurf */
342 src.width = ds->patchWidth;
343 src.height = ds->patchHeight;
344 src.verts = ds->verts;
345 //% subdivided = SubdivideMesh( src, 8, 999 );
346 if (patchSubdivision)
347 iterations = IterationsForCurve( ds->longestCurve, patchSubdivision );
349 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions / patchQuality );
351 subdivided = SubdivideMesh2( src, iterations ); //% ds->maxIterations
353 /* fit it to the curve and remove colinear verts on rows/columns */
354 PutMeshOnCurve( *subdivided );
355 mesh = RemoveLinearMeshColumnsRows( subdivided );
356 FreeMesh( subdivided );
357 //% MakeMeshNormals( mesh );
359 /* make a copy of the drawsurface */
360 dsNew = AllocDrawSurface( SURFACE_META );
361 memcpy( dsNew, ds, sizeof( *ds ) );
363 /* if the patch is nonsolid, then discard it */
364 if( !(ds->shaderInfo->compileFlags & C_SOLID) )
367 /* set new pointer */
370 /* basic transmogrification */
371 ds->type = SURFACE_META;
373 ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );
375 /* copy the verts in */
376 ds->numVerts = (mesh->width * mesh->height);
377 ds->verts = mesh->verts;
379 /* iterate through the mesh quads */
380 for( y = 0; y < (mesh->height - 1); y++ )
382 for( x = 0; x < (mesh->width - 1); x++ )
385 pw[ 0 ] = x + (y * mesh->width);
386 pw[ 1 ] = x + ((y + 1) * mesh->width);
387 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
388 pw[ 3 ] = x + 1 + (y * mesh->width);
389 pw[ 4 ] = x + (y * mesh->width); /* same as pw[ 0 ] */
394 /* make first triangle */
395 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
396 ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];
397 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
399 /* make second triangle */
400 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
401 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
402 ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];
406 /* free the mesh, but not the verts */
410 numPatchMetaSurfaces++;
413 ClassifySurfaces( 1, ds );
416 #define TINY_AREA 1.0f
417 #define MAXAREA_MAXTRIES 8
418 int MaxAreaIndexes(bspDrawVert_t *vert, int cnt, int *indexes)
420 int r, s, t, bestR = 0, bestS = 1, bestT = 2;
422 double A, bestA = -1, V, bestV = -1;
423 vec3_t ab, ac, bc, cross;
430 /* calculate total area */
432 for(i = 1; i+1 < cnt; ++i)
434 VectorSubtract(vert[i].xyz, vert[0].xyz, ab);
435 VectorSubtract(vert[i+1].xyz, vert[0].xyz, ac);
436 CrossProduct(ab, ac, cross);
437 A += VectorLength(cross);
440 for(i = 0; i < cnt; ++i)
442 VectorSubtract(vert[(i+1)%cnt].xyz, vert[i].xyz, ab);
443 V += VectorLength(ab);
446 /* calculate shift width from the area sensibly, assuming the polygon
447 * fits about 25% of the screen in both dimensions
448 * we assume 1280x1024
449 * 1 pixel is then about sqrt(A) / (0.25 * screenwidth)
450 * 8 pixels are then about sqrt(A) / (0.25 * 1280) * 8
451 * 8 pixels are then about sqrt(A) * 0.025
453 shiftWidth = sqrt(A) * 0.0125;
454 /* 3->1 6->2 12->3 ... */
455 if(A - ceil(log(cnt/1.5) / log(2)) * V * shiftWidth * 2 < 0)
457 /* printf("Small triangle detected (area %f, circumference %f), adjusting shiftWidth from %f to ", A, V, shiftWidth); */
458 shiftWidth = A / (ceil(log(cnt/1.5) / log(2)) * V * 2);
459 /* printf("%f\n", shiftWidth); */
462 /* find the triangle with highest area */
463 for(r = 0; r+2 < cnt; ++r)
464 for(s = r+1; s+1 < cnt; ++s)
465 for(t = s+1; t < cnt; ++t)
467 VectorSubtract(vert[s].xyz, vert[r].xyz, ab);
468 VectorSubtract(vert[t].xyz, vert[r].xyz, ac);
469 VectorSubtract(vert[t].xyz, vert[s].xyz, bc);
470 CrossProduct(ab, ac, cross);
471 A = VectorLength(cross);
473 V = A - (VectorLength(ab) - VectorLength(ac) - VectorLength(bc)) * shiftWidth;
474 /* value = A - circumference * shiftWidth, i.e. we back out by shiftWidth units from each side, to prevent too acute triangles */
475 /* this kind of simulates "number of shiftWidth*shiftWidth fragments in the triangle not touched by an edge" */
477 if(bestA < 0 || V > bestV)
489 printf("value was REALLY bad\n");
492 for(try = 0; try < MAXAREA_MAXTRIES; ++try)
496 bestR = rand() % cnt;
497 bestS = rand() % cnt;
498 bestT = rand() % cnt;
499 if(bestR == bestS || bestR == bestT || bestS == bestT)
502 // abc acb bac bca cab cba
509 // abc acb abc bca acb bca
516 // abc abc abc bac abc bac
523 // abc abc abc abc abc abc
525 VectorSubtract(vert[bestS].xyz, vert[bestR].xyz, ab);
526 VectorSubtract(vert[bestT].xyz, vert[bestR].xyz, ac);
527 CrossProduct(ab, ac, cross);
528 bestA = VectorLength(cross);
531 if(bestA < TINY_AREA)
532 /* the biggest triangle is degenerate - then every other is too, and the other algorithms wouldn't generate anything useful either */
536 indexes[i++] = bestR;
537 indexes[i++] = bestS;
538 indexes[i++] = bestT;
541 /* identify the other fragments */
543 /* full polygon without triangle (bestR,bestS,bestT) = three new polygons:
549 j = MaxAreaIndexes(vert + bestR, bestS - bestR + 1, indexes + i);
555 /* uses 3*(bestS-bestR+1)-6 */
556 j = MaxAreaIndexes(vert + bestS, bestT - bestS + 1, indexes + i);
562 /* uses 3*(bestT-bestS+1)-6 */
564 /* can'bestT recurse this one directly... therefore, buffering */
565 if(cnt + bestR - bestT + 1 >= 3)
567 buf = safe_malloc(sizeof(*vert) * (cnt + bestR - bestT + 1));
568 memcpy(buf, vert + bestT, sizeof(*vert) * (cnt - bestT));
569 memcpy(buf + (cnt - bestT), vert, sizeof(*vert) * (bestR + 1));
570 j = MaxAreaIndexes(buf, cnt + bestR - bestT + 1, indexes + i);
578 indexes[i] = (indexes[i] + bestT) % cnt;
579 /* uses 3*(cnt+bestR-bestT+1)-6 */
583 /* together 3 + 3*(cnt+3) - 18 = 3*cnt-6 q.e.d. */
591 MaxAreaFaceSurface() - divVerent
592 creates a triangle list using max area indexes
595 void MaxAreaFaceSurface(mapDrawSurface_t *ds)
598 /* try to early out */
599 if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
602 /* is this a simple triangle? */
603 if( ds->numVerts == 3 )
606 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
607 VectorSet( ds->indexes, 0, 1, 2 );
608 numMaxAreaSurfaces++;
613 ds->numIndexes = 3 * ds->numVerts - 6;
614 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
615 n = MaxAreaIndexes(ds->verts, ds->numVerts, ds->indexes);
618 /* whatever we do, it's degenerate */
621 StripFaceSurface(ds);
627 numMaxAreaSurfaces++;
630 ClassifySurfaces( 1, ds );
635 FanFaceSurface() - ydnar
636 creates a tri-fan from a brush face winding
637 loosely based on SurfaceAsTriFan()
640 void FanFaceSurface( mapDrawSurface_t *ds )
642 int i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
643 bspDrawVert_t *verts, *centroid, *dv;
647 /* try to early out */
648 if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
651 /* add a new vertex at the beginning of the surface */
652 verts = safe_malloc( (ds->numVerts + 1) * sizeof( bspDrawVert_t ) );
653 memset( verts, 0, sizeof( bspDrawVert_t ) );
654 memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
658 /* add up the drawverts to create a centroid */
659 centroid = &verts[ 0 ];
660 memset( color, 0, 4 * MAX_LIGHTMAPS * sizeof( int ) );
661 for( i = 1, dv = &verts[ 1 ]; i < (ds->numVerts + 1); i++, dv++ )
663 VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
664 VectorAdd( centroid->normal, dv->normal, centroid->normal );
665 for( j = 0; j < 4; j++ )
667 for( k = 0; k < MAX_LIGHTMAPS; k++ )
668 color[ k ][ j ] += dv->color[ k ][ j ];
671 centroid->st[ j ] += dv->st[ j ];
672 for( k = 0; k < MAX_LIGHTMAPS; k++ )
673 centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
678 /* average the centroid */
679 iv = 1.0f / ds->numVerts;
680 VectorScale( centroid->xyz, iv, centroid->xyz );
681 if( VectorNormalize( centroid->normal, centroid->normal ) <= 0 )
682 VectorCopy( verts[ 1 ].normal, centroid->normal );
683 for( j = 0; j < 4; j++ )
685 for( k = 0; k < MAX_LIGHTMAPS; k++ )
687 color[ k ][ j ] /= ds->numVerts;
688 centroid->color[ k ][ j ] = (color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255);
692 centroid->st[ j ] *= iv;
693 for( k = 0; k < MAX_LIGHTMAPS; k++ )
694 centroid->lightmap[ k ][ j ] *= iv;
698 /* add to vert count */
701 /* fill indexes in triangle fan order */
703 ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
704 for( i = 1; i < ds->numVerts; i++ )
708 c = (i + 1) % ds->numVerts;
710 ds->indexes[ ds->numIndexes++ ] = a;
711 ds->indexes[ ds->numIndexes++ ] = b;
712 ds->indexes[ ds->numIndexes++ ] = c;
719 ClassifySurfaces( 1, ds );
725 StripFaceSurface() - ydnar
726 attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
727 based on SurfaceAsTriStrip()
730 #define MAX_INDEXES 1024
732 void StripFaceSurface( mapDrawSurface_t *ds )
734 int i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
738 /* try to early out */
739 if( !ds->numVerts || (ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL) )
742 /* is this a simple triangle? */
743 if( ds->numVerts == 3 )
746 VectorSet( indexes, 0, 1, 2 );
750 /* ydnar: find smallest coordinate */
752 if( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse )
754 for( i = 0; i < ds->numVerts; i++ )
757 v1 = ds->verts[ i ].xyz;
758 v2 = ds->verts[ least ].xyz;
761 if( v1[ 0 ] < v2[ 0 ] ||
762 (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ]) ||
763 (v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ]) )
768 /* determine the triangle strip order */
769 numIndexes = (ds->numVerts - 2) * 3;
770 if( numIndexes > MAX_INDEXES )
771 Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
773 /* try all possible orderings of the points looking for a non-degenerate strip order */
774 for( r = 0; r < ds->numVerts; r++ )
777 rotate = (r + least) % ds->numVerts;
779 /* walk the winding in both directions */
780 for( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
783 a = (ds->numVerts - 1 - i + rotate) % ds->numVerts;
784 b = (i + rotate ) % ds->numVerts;
785 c = (ds->numVerts - 2 - i + rotate) % ds->numVerts;
787 /* test this triangle */
788 if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
794 /* handle end case */
795 if( i + 1 != ds->numVerts - 1 - i )
798 a = (ds->numVerts - 2 - i + rotate ) % ds->numVerts;
799 b = (i + rotate ) % ds->numVerts;
800 c = (i + 1 + rotate ) % ds->numVerts;
803 if( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) )
812 if( ni == numIndexes )
816 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
817 if( ni < numIndexes )
819 FanFaceSurface( ds );
824 /* copy strip triangle indexes */
825 ds->numIndexes = numIndexes;
826 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
827 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
833 ClassifySurfaces( 1, ds );
839 vortex: prints meta statistics in general output
844 Sys_Printf( "--- EmitMetaStats ---\n" );
845 Sys_Printf( "%9d total meta surfaces\n", numMetaSurfaces );
846 Sys_Printf( "%9d stripped surfaces\n", numStripSurfaces );
847 Sys_Printf( "%9d fanned surfaces\n", numFanSurfaces );
848 Sys_Printf( "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
849 Sys_Printf( "%9d patch meta surfaces\n", numPatchMetaSurfaces );
850 Sys_Printf( "%9d meta verts\n", numMetaVerts );
851 Sys_Printf( "%9d meta triangles\n", numMetaTriangles );
855 MakeEntityMetaTriangles()
856 builds meta triangles from brush faces (tristrips and fans)
859 void MakeEntityMetaTriangles( entity_t *e )
861 int i, f, fOld, start;
862 mapDrawSurface_t *ds;
866 Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
870 start = I_FloatTime();
872 /* walk the list of surfaces in the entity */
873 for( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
876 f = 10 * (i - e->firstDrawSurf) / (numMapDrawSurfs - e->firstDrawSurf);
880 Sys_FPrintf( SYS_VRB, "%d...", f );
884 ds = &mapDrawSurfs[ i ];
885 if( ds->numVerts <= 0 )
888 /* ignore autosprite surfaces */
889 if( ds->shaderInfo->autosprite )
892 /* meta this surface? */
893 if( meta == qfalse && ds->shaderInfo->forceMeta == qfalse )
901 if(maxAreaFaceSurface)
902 MaxAreaFaceSurface( ds );
904 StripFaceSurface( ds );
905 SurfaceToMetaTriangles( ds );
909 TriangulatePatchSurface(e, ds );
912 case SURFACE_TRIANGLES:
915 case SURFACE_FORCED_META:
917 SurfaceToMetaTriangles( ds );
926 if( (numMapDrawSurfs - e->firstDrawSurf) )
927 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
929 /* emit some stats */
930 Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
931 Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
932 Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
933 Sys_FPrintf( SYS_VRB, "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
934 Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
935 Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
936 Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
939 TidyEntitySurfaces( e );
945 PointTriangleIntersect()
946 assuming that all points lie in plane, determine if pt
947 is inside the triangle abc
948 code originally (c) 2001 softSurfer (www.softsurfer.com)
951 #define MIN_OUTSIDE_EPSILON -0.01f
952 #define MAX_OUTSIDE_EPSILON 1.01f
954 static qboolean PointTriangleIntersect( vec3_t pt, vec4_t plane, vec3_t a, vec3_t b, vec3_t c, vec3_t bary )
957 float uu, uv, vv, wu, wv, d;
961 VectorSubtract( b, a, u );
962 VectorSubtract( c, a, v );
963 VectorSubtract( pt, a, w );
966 uu = DotProduct( u, u );
967 uv = DotProduct( u, v );
968 vv = DotProduct( v, v );
969 wu = DotProduct( w, u );
970 wv = DotProduct( w, v );
971 d = uv * uv - uu * vv;
973 /* calculate barycentric coordinates */
974 bary[ 1 ] = (uv * wv - vv * wu) / d;
975 if( bary[ 1 ] < MIN_OUTSIDE_EPSILON || bary[ 1 ] > MAX_OUTSIDE_EPSILON )
977 bary[ 2 ] = (uv * wv - uu * wv) / d;
978 if( bary[ 2 ] < MIN_OUTSIDE_EPSILON || bary[ 2 ] > MAX_OUTSIDE_EPSILON )
980 bary[ 0 ] = 1.0f - (bary[ 1 ] + bary[ 2 ]);
982 /* point is in triangle */
990 sets up an edge structure from a plane and 2 points that the edge ab falls lies in
993 typedef struct edge_s
996 vec_t length, kingpinLength;
1002 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge )
1004 /* copy edge origin */
1005 VectorCopy( a, edge->origin );
1007 /* create vector aligned with winding direction of edge */
1008 VectorSubtract( b, a, edge->edge );
1010 if( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) )
1012 else if( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) )
1016 edge->kingpinLength = edge->edge[ edge->kingpin ];
1018 VectorNormalize( edge->edge, edge->edge );
1019 edge->edge[ 3 ] = DotProduct( a, edge->edge );
1020 edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
1022 /* create perpendicular plane that edge lies in */
1023 CrossProduct( plane, edge->edge, edge->plane );
1024 edge->plane[ 3 ] = DotProduct( a, edge->plane );
1031 fixes t-junctions on meta triangles
1034 #define TJ_PLANE_EPSILON (1.0f / 8.0f)
1035 #define TJ_EDGE_EPSILON (1.0f / 8.0f)
1036 #define TJ_POINT_EPSILON (1.0f / 8.0f)
1038 void FixMetaTJunctions( void )
1040 int i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
1041 metaTriangle_t *tri, *newTri;
1043 bspDrawVert_t *a, *b, *c, junc;
1050 /* this code is crap; revisit later */
1054 Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
1058 start = I_FloatTime();
1060 /* walk triangle list */
1062 for( i = 0; i < numMetaTriangles; i++ )
1065 tri = &metaTriangles[ i ];
1067 /* print pacifier */
1068 f = 10 * i / numMetaTriangles;
1072 Sys_FPrintf( SYS_VRB, "%d...", f );
1075 /* attempt to early out */
1077 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc )
1080 /* calculate planes */
1081 VectorCopy( tri->plane, plane );
1082 plane[ 3 ] = tri->plane[ 3 ];
1083 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1084 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1085 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1087 /* walk meta vert list */
1088 for( j = 0; j < numMetaVerts; j++ )
1091 VectorCopy( metaVerts[ j ].xyz, pt );
1093 /* debug code: darken verts */
1095 VectorSet( metaVerts[ j ].color[ 0 ], 8, 8, 8 );
1097 /* determine if point lies in the triangle's plane */
1098 dist = DotProduct( pt, plane ) - plane[ 3 ];
1099 if( fabs( dist ) > TJ_PLANE_EPSILON )
1102 /* skip this point if it already exists in the triangle */
1103 for( k = 0; k < 3; k++ )
1105 if( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
1106 fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
1107 fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON )
1114 for( k = 0; k < 3; k++ )
1116 /* ignore bogus edges */
1117 if( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON )
1120 /* determine if point lies on the edge */
1121 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
1122 if( fabs( dist ) > TJ_EDGE_EPSILON )
1125 /* determine how far along the edge the point lies */
1126 amount = (pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ]) / edges[ k ].kingpinLength;
1127 if( amount <= 0.0f || amount >= 1.0f )
1131 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
1132 if( dist <= -0.0f || dist >= edges[ k ].length )
1134 amount = dist / edges[ k ].length;
1137 /* debug code: brighten this point */
1138 //% metaVerts[ j ].color[ 0 ][ 0 ] += 5;
1139 //% metaVerts[ j ].color[ 0 ][ 1 ] += 4;
1140 VectorSet( metaVerts[ tri->indexes[ k ] ].color[ 0 ], 255, 204, 0 );
1141 VectorSet( metaVerts[ tri->indexes[ (k + 1) % 3 ] ].color[ 0 ], 255, 204, 0 );
1144 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
1145 a = &metaVerts[ tri->indexes[ k % 3 ] ];
1146 b = &metaVerts[ tri->indexes[ (k + 1) % 3 ] ];
1147 c = &metaVerts[ tri->indexes[ (k + 2) % 3 ] ];
1150 LerpDrawVertAmount( a, b, amount, &junc );
1151 VectorCopy( pt, junc.xyz );
1153 /* compare against existing verts */
1154 if( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) )
1157 /* see if we can just re-use the existing vert */
1158 if( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) )
1162 /* find new vertex (note: a and b are invalid pointers after this) */
1163 firstSearchMetaVert = numMetaVerts;
1164 vertIndex = FindMetaVertex( &junc );
1169 /* make new triangle */
1170 triIndex = AddMetaTriangle();
1175 tri = &metaTriangles[ i ];
1176 newTri = &metaTriangles[ triIndex ];
1178 /* copy the triangle */
1179 memcpy( newTri, tri, sizeof( *tri ) );
1182 tri->indexes[ (k + 1) % 3 ] = vertIndex;
1183 newTri->indexes[ k ] = vertIndex;
1185 /* recalculate edges */
1186 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1187 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1188 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1191 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
1192 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
1193 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
1195 /* add to counter and end processing of this vert */
1203 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1205 /* emit some stats */
1206 Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
1212 SmoothMetaTriangles()
1213 averages coincident vertex normals in the meta triangles
1216 #define MAX_SAMPLES 256
1217 #define THETA_EPSILON 0.000001
1218 #define EQUAL_NORMAL_EPSILON 0.01
1220 void SmoothMetaTriangles( void )
1222 int i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
1223 float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
1224 metaTriangle_t *tri;
1227 vec3_t average, diff;
1228 int indexes[ MAX_SAMPLES ];
1229 vec3_t votes[ MAX_SAMPLES ];
1232 Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
1234 /* allocate shade angle table */
1235 shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
1236 memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
1238 /* allocate smoothed table */
1239 cs = (numMetaVerts / 8) + 1;
1240 smoothed = safe_malloc( cs );
1241 memset( smoothed, 0, cs );
1243 /* set default shade angle */
1244 defaultShadeAngle = DEG2RAD( npDegrees );
1245 maxShadeAngle = 0.0f;
1247 /* run through every surface and flag verts belonging to non-lightmapped surfaces
1248 and set per-vertex smoothing angle */
1249 for( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
1251 shadeAngle = defaultShadeAngle;
1253 /* get shade angle from shader */
1254 if( tri->si->shadeAngleDegrees > 0.0f )
1255 shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1256 /* get shade angle from entity */
1257 else if( tri->shadeAngleDegrees > 0.0f )
1258 shadeAngle = DEG2RAD( tri->shadeAngleDegrees );
1260 if( shadeAngle <= 0.0f )
1261 shadeAngle = defaultShadeAngle;
1263 if( shadeAngle > maxShadeAngle )
1264 maxShadeAngle = shadeAngle;
1266 /* flag its verts */
1267 for( j = 0; j < 3; j++ )
1269 shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1270 if( shadeAngle <= 0 )
1271 smoothed[ tri->indexes[ j ] >> 3 ] |= (1 << (tri->indexes[ j ] & 7));
1275 /* bail if no surfaces have a shade angle */
1276 if( maxShadeAngle <= 0 )
1278 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1279 free( shadeAngles );
1286 start = I_FloatTime();
1288 /* go through the list of vertexes */
1290 for( i = 0; i < numMetaVerts; i++ )
1292 /* print pacifier */
1293 f = 10 * i / numMetaVerts;
1297 Sys_FPrintf( SYS_VRB, "%d...", f );
1300 /* already smoothed? */
1301 if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
1305 VectorClear( average );
1309 /* build a table of coincident vertexes */
1310 for( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1312 /* already smoothed? */
1313 if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
1317 if( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse )
1320 /* use smallest shade angle */
1321 shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
1323 /* check shade angle */
1324 dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1327 else if( dot < -1.0 )
1329 testAngle = acos( dot ) + THETA_EPSILON;
1330 if( testAngle >= shadeAngle )
1333 /* add to the list */
1334 indexes[ numVerts++ ] = j;
1337 smoothed[ j >> 3 ] |= (1 << (j & 7));
1339 /* see if this normal has already been voted */
1340 for( k = 0; k < numVotes; k++ )
1342 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1343 if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1344 fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1345 fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )
1349 /* add a new vote? */
1350 if( k == numVotes && numVotes < MAX_SAMPLES )
1352 VectorAdd( average, metaVerts[ j ].normal, average );
1353 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1358 /* don't average for less than 2 verts */
1362 /* average normal */
1363 if( VectorNormalize( average, average ) > 0 )
1366 for( j = 0; j < numVerts; j++ )
1367 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1372 /* free the tables */
1373 free( shadeAngles );
1377 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1379 /* emit some stats */
1380 Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1386 AddMetaVertToSurface()
1387 adds a drawvert to a surface unless an existing vert matching already exists
1388 returns the index of that vert (or < 0 on failure)
1391 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident )
1397 /* go through the verts and find a suitable candidate */
1398 for( i = 0; i < ds->numVerts; i++ )
1401 dv2 = &ds->verts[ i ];
1403 /* compare xyz and normal */
1404 if( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse )
1406 if( VectorCompare( dv1->normal, dv2->normal ) == qfalse )
1409 /* good enough at this point */
1412 /* compare texture coordinates and color */
1413 if( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] )
1415 if( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] )
1418 /* found a winner */
1423 /* overflow check */
1424 if( ds->numVerts >= ((ds->shaderInfo->compileFlags & C_VERTEXLIT) ? maxSurfaceVerts : maxLMSurfaceVerts) )
1425 return VERTS_EXCEEDED;
1427 /* made it this far, add the vert and return */
1428 dv2 = &ds->verts[ ds->numVerts++ ];
1430 return (ds->numVerts - 1);
1437 AddMetaTriangleToSurface()
1438 attempts to add a metatriangle to a surface
1439 returns the score of the triangle added
1442 #define AXIS_SCORE 100000
1443 #define AXIS_MIN 100000
1444 #define VERT_SCORE 10000
1445 #define SURFACE_SCORE 1000
1447 #define ST_SCORE2 (2 * (ST_SCORE))
1449 #define ADEQUATE_SCORE ((AXIS_MIN) + 1 * (VERT_SCORE))
1450 #define GOOD_SCORE ((AXIS_MIN) + 2 * (VERT_SCORE) + 4 * (ST_SCORE))
1451 #define PERFECT_SCORE ((AXIS_MIN) + 3 * (VERT_SCORE) + (SURFACE_SCORE) + 4 * (ST_SCORE))
1452 //#define MAX_BBOX_DISTANCE 16
1454 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd )
1456 int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1458 vec3_t mins, maxs, p;
1459 qboolean inTexRange, es, et;
1460 mapDrawSurface_t old;
1463 /* overflow check */
1464 if( ds->numIndexes >= maxSurfaceIndexes )
1467 /* test the triangle */
1468 if( ds->entityNum != tri->entityNum ) /* ydnar: added 2002-07-06 */
1470 if( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows )
1472 if( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize )
1475 if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1476 //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1477 DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f )
1481 /* planar surfaces will only merge with triangles in the same plane */
1482 if( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 )
1484 if( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] )
1486 if( tri->planeNum >= 0 && tri->planeNum != ds->planeNum )
1490 #if MAX_BBOX_DISTANCE > 0
1491 VectorCopy( ds->mins, mins );
1492 VectorCopy( ds->maxs, maxs );
1493 mins[0] -= MAX_BBOX_DISTANCE;
1494 mins[1] -= MAX_BBOX_DISTANCE;
1495 mins[2] -= MAX_BBOX_DISTANCE;
1496 maxs[0] += MAX_BBOX_DISTANCE;
1497 maxs[1] += MAX_BBOX_DISTANCE;
1498 maxs[2] += MAX_BBOX_DISTANCE;
1499 #define CHECK_1D(mins, v, maxs) ((mins) <= (v) && (v) <= (maxs))
1500 #define CHECK_3D(mins, v, maxs) (CHECK_1D((mins)[0], (v)[0], (maxs)[0]) && CHECK_1D((mins)[1], (v)[1], (maxs)[1]) && CHECK_1D((mins)[2], (v)[2], (maxs)[2]))
1501 VectorCopy(metaVerts[ tri->indexes[ 0 ] ].xyz, p);
1502 if(!CHECK_3D(mins, p, maxs))
1504 VectorCopy(metaVerts[ tri->indexes[ 1 ] ].xyz, p);
1505 if(!CHECK_3D(mins, p, maxs))
1507 VectorCopy(metaVerts[ tri->indexes[ 2 ] ].xyz, p);
1508 if(!CHECK_3D(mins, p, maxs))
1516 /* set initial score */
1517 score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1519 /* score the the dot product of lightmap axis to plane */
1520 if( (ds->shaderInfo->compileFlags & C_VERTEXLIT) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) )
1521 score += AXIS_SCORE;
1523 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1525 /* preserve old drawsurface if this fails */
1526 memcpy( &old, ds, sizeof( *ds ) );
1528 /* attempt to add the verts */
1530 ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1531 bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1532 ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1534 /* check vertex underflow */
1535 if( ai < 0 || bi < 0 || ci < 0 )
1537 memcpy( ds, &old, sizeof( *ds ) );
1541 /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1542 score += (coincident * VERT_SCORE);
1544 /* add new vertex bounds to mins/maxs */
1545 VectorCopy( ds->mins, mins );
1546 VectorCopy( ds->maxs, maxs );
1547 AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1548 AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1549 AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1551 /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1552 if( !(ds->shaderInfo->compileFlags & C_VERTEXLIT) &&
1553 ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1554 (VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse) )
1556 /* set maximum size before lightmap scaling (normally 2032 units) */
1557 /* 2004-02-24: scale lightmap test size by 2 to catch larger brush faces */
1558 /* 2004-04-11: reverting to actual lightmap size */
1559 lmMax = (ds->sampleSize * (ds->shaderInfo->lmCustomWidth - 1));
1560 for( i = 0; i < 3; i++ )
1562 if( (maxs[ i ] - mins[ i ]) > lmMax )
1564 memcpy( ds, &old, sizeof( *ds ) );
1570 /* check texture range overflow */
1571 oldTexRange[ 0 ] = ds->texRange[ 0 ];
1572 oldTexRange[ 1 ] = ds->texRange[ 1 ];
1573 inTexRange = CalcSurfaceTextureRange( ds );
1575 es = (ds->texRange[ 0 ] > oldTexRange[ 0 ]) ? qtrue : qfalse;
1576 et = (ds->texRange[ 1 ] > oldTexRange[ 1 ]) ? qtrue : qfalse;
1578 if( inTexRange == qfalse && ds->numIndexes > 0 )
1580 memcpy( ds, &old, sizeof( *ds ) );
1581 return UNSUITABLE_TRIANGLE;
1584 /* score texture range */
1585 if( ds->texRange[ 0 ] <= oldTexRange[ 0 ] )
1587 else if( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] )
1590 if( ds->texRange[ 1 ] <= oldTexRange[ 1 ] )
1592 else if( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] )
1596 /* go through the indexes and try to find an existing triangle that matches abc */
1597 for( i = 0; i < ds->numIndexes; i += 3 )
1599 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1600 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ]) ||
1601 (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ]) ||
1602 (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ]) )
1604 /* triangle already present */
1605 memcpy( ds, &old, sizeof( *ds ) );
1610 /* rotate the triangle 3x to find an inverse triangle (error case) */
1611 if( (ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ]) ||
1612 (bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ]) ||
1613 (ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ]) )
1616 Sys_Printf( "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
1617 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1618 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1619 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1621 /* reverse triangle already present */
1622 memcpy( ds, &old, sizeof( *ds ) );
1628 /* add the triangle indexes */
1629 if( ds->numIndexes < maxSurfaceIndexes )
1630 ds->indexes[ ds->numIndexes++ ] = ai;
1631 if( ds->numIndexes < maxSurfaceIndexes )
1632 ds->indexes[ ds->numIndexes++ ] = bi;
1633 if( ds->numIndexes < maxSurfaceIndexes )
1634 ds->indexes[ ds->numIndexes++ ] = ci;
1636 /* check index overflow */
1637 if( ds->numIndexes >= maxSurfaceIndexes )
1639 memcpy( ds, &old, sizeof( *ds ) );
1643 /* sanity check the indexes */
1644 if( ds->numIndexes >= 3 &&
1645 (ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1646 ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1647 ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ]) )
1648 Sys_Printf( "DEG:%d! ", ds->numVerts );
1652 memcpy( ds, &old, sizeof( *ds ) );
1655 /* copy bounds back to surface */
1656 VectorCopy( mins, ds->mins );
1657 VectorCopy( maxs, ds->maxs );
1659 /* mark triangle as used */
1663 /* add a side reference */
1664 ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1666 /* return to sender */
1673 MetaTrianglesToSurface()
1674 creates map drawsurface(s) from the list of possibles
1677 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded )
1679 int i, j, f, best, score, bestScore;
1680 metaTriangle_t *seed, *test;
1681 mapDrawSurface_t *ds;
1682 bspDrawVert_t *verts;
1687 /* allocate arrays */
1688 verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1689 indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1691 /* walk the list of triangles */
1692 for( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1694 /* skip this triangle if it has already been merged */
1695 if( seed->si == NULL )
1698 /* -----------------------------------------------------------------
1699 initial drawsurf construction
1700 ----------------------------------------------------------------- */
1702 /* start a new drawsurface */
1703 ds = AllocDrawSurface( SURFACE_META );
1704 ds->entityNum = seed->entityNum;
1705 ds->surfaceNum = seed->surfaceNum;
1706 ds->castShadows = seed->castShadows;
1707 ds->recvShadows = seed->recvShadows;
1709 ds->shaderInfo = seed->si;
1710 ds->planeNum = seed->planeNum;
1711 ds->fogNum = seed->fogNum;
1712 ds->sampleSize = seed->sampleSize;
1713 ds->shadeAngleDegrees = seed->shadeAngleDegrees;
1715 ds->indexes = indexes;
1716 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1717 ds->sideRef = AllocSideRef( seed->side, NULL );
1719 ClearBounds( ds->mins, ds->maxs );
1721 /* clear verts/indexes */
1722 memset( verts, 0, sizeof( verts ) );
1723 memset( indexes, 0, sizeof( indexes ) );
1725 /* add the first triangle */
1726 if( AddMetaTriangleToSurface( ds, seed, qfalse ) )
1729 /* -----------------------------------------------------------------
1731 ----------------------------------------------------------------- */
1733 /* progressively walk the list until no more triangles can be added */
1737 /* print pacifier */
1738 f = 10 * *numAdded / numMetaTriangles;
1742 Sys_FPrintf( SYS_VRB, "%d...", f );
1745 /* reset best score */
1750 /* walk the list of possible candidates for merging */
1751 for( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1753 /* skip this triangle if it has already been merged */
1754 if( test->si == NULL )
1757 /* score this triangle */
1758 score = AddMetaTriangleToSurface( ds, test, qtrue );
1759 if( score > bestScore )
1764 /* if we have a score over a certain threshold, just use it */
1765 if( bestScore >= GOOD_SCORE )
1767 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1778 /* add best candidate */
1779 if( best >= 0 && bestScore > ADEQUATE_SCORE )
1781 if( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) )
1789 /* copy the verts and indexes to the new surface */
1790 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1791 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1792 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1793 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1795 /* classify the surface */
1796 ClassifySurfaces( 1, ds );
1799 numMergedSurfaces++;
1810 CompareMetaTriangles()
1811 compare function for qsort()
1814 static int CompareMetaTriangles( const void *a, const void *b )
1817 vec3_t aMins, bMins;
1821 if( ((metaTriangle_t*) a)->si < ((metaTriangle_t*) b)->si )
1823 else if( ((metaTriangle_t*) a)->si > ((metaTriangle_t*) b)->si )
1827 else if( ((metaTriangle_t*) a)->fogNum < ((metaTriangle_t*) b)->fogNum )
1829 else if( ((metaTriangle_t*) a)->fogNum > ((metaTriangle_t*) b)->fogNum )
1834 else if( npDegrees == 0.0f && ((metaTriangle_t*) a)->si->nonplanar == qfalse &&
1835 ((metaTriangle_t*) a)->planeNum >= 0 && ((metaTriangle_t*) a)->planeNum >= 0 )
1837 if( ((metaTriangle_t*) a)->plane[ 3 ] < ((metaTriangle_t*) b)->plane[ 3 ] )
1839 else if( ((metaTriangle_t*) a)->plane[ 3 ] > ((metaTriangle_t*) b)->plane[ 3 ] )
1841 else if( ((metaTriangle_t*) a)->plane[ 0 ] < ((metaTriangle_t*) b)->plane[ 0 ] )
1843 else if( ((metaTriangle_t*) a)->plane[ 0 ] > ((metaTriangle_t*) b)->plane[ 0 ] )
1845 else if( ((metaTriangle_t*) a)->plane[ 1 ] < ((metaTriangle_t*) b)->plane[ 1 ] )
1847 else if( ((metaTriangle_t*) a)->plane[ 1 ] > ((metaTriangle_t*) b)->plane[ 1 ] )
1849 else if( ((metaTriangle_t*) a)->plane[ 2 ] < ((metaTriangle_t*) b)->plane[ 2 ] )
1851 else if( ((metaTriangle_t*) a)->plane[ 2 ] > ((metaTriangle_t*) b)->plane[ 2 ] )
1856 /* then position in world */
1859 VectorSet( aMins, 999999, 999999, 999999 );
1860 VectorSet( bMins, 999999, 999999, 999999 );
1861 for( i = 0; i < 3; i++ )
1863 av = ((metaTriangle_t*) a)->indexes[ i ];
1864 bv = ((metaTriangle_t*) b)->indexes[ i ];
1865 for( j = 0; j < 3; j++ )
1867 if( metaVerts[ av ].xyz[ j ] < aMins[ j ] )
1868 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1869 if( metaVerts[ bv ].xyz[ j ] < bMins[ j ] )
1870 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1875 for( i = 0; i < 3; i++ )
1877 if( aMins[ i ] < bMins[ i ] )
1879 else if( aMins[ i ] > bMins[ i ] )
1883 /* functionally equivalent */
1890 MergeMetaTriangles()
1891 merges meta triangles into drawsurfaces
1894 void MergeMetaTriangles( void )
1896 int i, j, fOld, start, numAdded;
1897 metaTriangle_t *head, *end;
1900 /* only do this if there are meta triangles */
1901 if( numMetaTriangles <= 0 )
1905 Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1907 /* sort the triangles by shader major, fognum minor */
1908 qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1912 start = I_FloatTime();
1916 for( i = 0, j = 0; i < numMetaTriangles; i = j )
1918 /* get head of list */
1919 head = &metaTriangles[ i ];
1921 /* skip this triangle if it has already been merged */
1922 if( head->si == NULL )
1928 for( j = i + 1; j < numMetaTriangles; j++ )
1930 /* get end of list */
1931 end = &metaTriangles[ j ];
1932 if( head->si != end->si || head->fogNum != end->fogNum )
1937 /* try to merge this list of possible merge candidates */
1938 MetaTrianglesToSurface( (j - i), head, &fOld, &numAdded );
1941 /* clear meta triangle list */
1942 ClearMetaTriangles();
1946 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
1948 /* emit some stats */
1949 Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1950 Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );