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 ){
79 finds a matching metavertex in the global list, returning its index
82 static int FindMetaVertex( bspDrawVert_t *src ){
84 bspDrawVert_t *v, *temp;
87 /* try to find an existing drawvert */
88 for ( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
90 if ( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 ) {
96 if ( numMetaVerts >= maxMetaVerts ) {
97 /* reallocate more room */
98 maxMetaVerts += GROW_META_VERTS;
99 temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );
100 if ( metaVerts != NULL ) {
101 memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );
107 /* add the triangle */
108 memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );
111 /* return the count */
112 return ( numMetaVerts - 1 );
119 adds a new meta triangle, allocating more memory if necessary
122 static int AddMetaTriangle( void ){
123 metaTriangle_t *temp;
127 if ( numMetaTriangles >= maxMetaTriangles ) {
128 /* reallocate more room */
129 maxMetaTriangles += GROW_META_TRIANGLES;
130 temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );
131 if ( metaTriangles != NULL ) {
132 memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );
133 free( metaTriangles );
135 metaTriangles = temp;
138 /* increment and return */
140 return numMetaTriangles - 1;
147 finds a matching metatriangle in the global list,
148 otherwise adds it and returns the index to the metatriangle
151 int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum ){
157 /* detect degenerate triangles fixme: do something proper here */
158 VectorSubtract( a->xyz, b->xyz, dir );
159 if ( VectorLength( dir ) < 0.125f ) {
162 VectorSubtract( b->xyz, c->xyz, dir );
163 if ( VectorLength( dir ) < 0.125f ) {
166 VectorSubtract( c->xyz, a->xyz, dir );
167 if ( VectorLength( dir ) < 0.125f ) {
172 if ( planeNum >= 0 ) {
173 /* because of precision issues with small triangles, try to use the specified plane */
174 src->planeNum = planeNum;
175 VectorCopy( mapplanes[ planeNum ].normal, src->plane );
176 src->plane[ 3 ] = mapplanes[ planeNum ].dist;
180 /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */
182 if ( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse ) {
187 /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */
188 if ( VectorLength( a->normal ) <= 0.0f ) {
189 VectorCopy( src->plane, a->normal );
191 if ( VectorLength( b->normal ) <= 0.0f ) {
192 VectorCopy( src->plane, b->normal );
194 if ( VectorLength( c->normal ) <= 0.0f ) {
195 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 ) {
201 /* the shader can specify an explicit lightmap axis */
202 if ( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] ) {
203 VectorCopy( src->si->lightmapAxis, src->lightmapAxis );
206 /* new axis-finding code */
208 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 ) {
233 /* get a new triangle */
234 triIndex = AddMetaTriangle();
236 /* add the triangle */
237 memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );
239 /* return the triangle index */
246 SurfaceToMetaTriangles()
247 converts a classified surface to metatriangles
250 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 ) {
264 /* speed at the expense of memory */
265 firstSearchMetaVert = numMetaVerts;
267 /* only handle valid surfaces */
268 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 ] ) {
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 src.shadeAngleDegrees = ds->shadeAngleDegrees;
291 VectorCopy( ds->lightmapAxis, src.lightmapAxis );
294 memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );
295 memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );
296 memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );
297 FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );
304 /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */
311 TriangulatePatchSurface()
312 creates triangles from a patch
315 void TriangulatePatchSurface( entity_t *e, mapDrawSurface_t *ds ){
316 int iterations, x, y, pw[ 5 ], r;
317 mapDrawSurface_t *dsNew;
318 mesh_t src, *subdivided, *mesh;
321 int patchSubdivision;
323 /* vortex: _patchMeta, _patchQuality, _patchSubdivide support */
324 forcePatchMeta = IntForKey( e, "_patchMeta" );
325 if ( !forcePatchMeta ) {
326 forcePatchMeta = IntForKey( e, "patchMeta" );
328 patchQuality = IntForKey( e, "_patchQuality" );
329 if ( !patchQuality ) {
330 patchQuality = IntForKey( e, "patchQuality" );
332 if ( !patchQuality ) {
335 patchSubdivision = IntForKey( e, "_patchSubdivide" );
336 if ( !patchSubdivision ) {
337 patchSubdivision = IntForKey( e, "patchSubdivide" );
340 /* try to early out */
341 if ( ds->numVerts == 0 || ds->type != SURFACE_PATCH || ( patchMeta == qfalse && !forcePatchMeta ) ) {
345 /* make a mesh from the drawsurf */
346 src.width = ds->patchWidth;
347 src.height = ds->patchHeight;
348 src.verts = ds->verts;
349 //% subdivided = SubdivideMesh( src, 8, 999 );
350 if ( patchSubdivision ) {
351 iterations = IterationsForCurve( ds->longestCurve, patchSubdivision );
354 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions / patchQuality );
357 subdivided = SubdivideMesh2( src, iterations ); //% ds->maxIterations
359 /* fit it to the curve and remove colinear verts on rows/columns */
360 PutMeshOnCurve( *subdivided );
361 mesh = RemoveLinearMeshColumnsRows( subdivided );
362 FreeMesh( subdivided );
363 //% MakeMeshNormals( mesh );
365 /* make a copy of the drawsurface */
366 dsNew = AllocDrawSurface( SURFACE_META );
367 memcpy( dsNew, ds, sizeof( *ds ) );
369 /* if the patch is nonsolid, then discard it */
370 if ( !( ds->shaderInfo->compileFlags & C_SOLID ) ) {
374 /* set new pointer */
377 /* basic transmogrification */
378 ds->type = SURFACE_META;
380 ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );
382 /* copy the verts in */
383 ds->numVerts = ( mesh->width * mesh->height );
384 ds->verts = mesh->verts;
386 /* iterate through the mesh quads */
387 for ( y = 0; y < ( mesh->height - 1 ); y++ )
389 for ( x = 0; x < ( mesh->width - 1 ); x++ )
392 pw[ 0 ] = x + ( y * mesh->width );
393 pw[ 1 ] = x + ( ( y + 1 ) * mesh->width );
394 pw[ 2 ] = x + 1 + ( ( y + 1 ) * mesh->width );
395 pw[ 3 ] = x + 1 + ( y * mesh->width );
396 pw[ 4 ] = x + ( y * mesh->width ); /* same as pw[ 0 ] */
401 /* make first triangle */
402 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
403 ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];
404 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
406 /* make second triangle */
407 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
408 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
409 ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];
413 /* free the mesh, but not the verts */
417 numPatchMetaSurfaces++;
420 ClassifySurfaces( 1, ds );
425 #define TINY_AREA 1.0f
426 #define MAXAREA_MAXTRIES 8
427 int MaxAreaIndexes( bspDrawVert_t *vert, int cnt, int *indexes ){
428 int r, s, t, bestR = 0, bestS = 1, bestT = 2;
430 double A, bestA = -1, V, bestV = -1;
431 vec3_t ab, ac, bc, cross;
439 /* calculate total area */
441 for ( i = 1; i + 1 < cnt; ++i )
443 VectorSubtract( vert[i].xyz, vert[0].xyz, ab );
444 VectorSubtract( vert[i + 1].xyz, vert[0].xyz, ac );
445 CrossProduct( ab, ac, cross );
446 A += VectorLength( cross );
449 for ( i = 0; i < cnt; ++i )
451 VectorSubtract( vert[( i + 1 ) % cnt].xyz, vert[i].xyz, ab );
452 V += VectorLength( ab );
455 /* calculate shift width from the area sensibly, assuming the polygon
456 * fits about 25% of the screen in both dimensions
457 * we assume 1280x1024
458 * 1 pixel is then about sqrt(A) / (0.25 * screenwidth)
459 * 8 pixels are then about sqrt(A) / (0.25 * 1280) * 8
460 * 8 pixels are then about sqrt(A) * 0.025
462 shiftWidth = sqrt( A ) * 0.0125;
463 /* 3->1 6->2 12->3 ... */
464 if ( A - ceil( log( cnt / 1.5 ) / log( 2 ) ) * V * shiftWidth * 2 < 0 ) {
465 /* printf("Small triangle detected (area %f, circumference %f), adjusting shiftWidth from %f to ", A, V, shiftWidth); */
466 shiftWidth = A / ( ceil( log( cnt / 1.5 ) / log( 2 ) ) * V * 2 );
467 /* printf("%f\n", shiftWidth); */
470 /* find the triangle with highest area */
471 for ( r = 0; r + 2 < cnt; ++r )
472 for ( s = r + 1; s + 1 < cnt; ++s )
473 for ( t = s + 1; t < cnt; ++t )
475 VectorSubtract( vert[s].xyz, vert[r].xyz, ab );
476 VectorSubtract( vert[t].xyz, vert[r].xyz, ac );
477 VectorSubtract( vert[t].xyz, vert[s].xyz, bc );
478 CrossProduct( ab, ac, cross );
479 A = VectorLength( cross );
481 V = A - ( VectorLength( ab ) - VectorLength( ac ) - VectorLength( bc ) ) * shiftWidth;
482 /* value = A - circumference * shiftWidth, i.e. we back out by shiftWidth units from each side, to prevent too acute triangles */
483 /* this kind of simulates "number of shiftWidth*shiftWidth fragments in the triangle not touched by an edge" */
485 if ( bestA < 0 || V > bestV ) {
496 printf("value was REALLY bad\n");
499 for ( try = 0; try < MAXAREA_MAXTRIES; ++try )
502 bestR = rand() % cnt;
503 bestS = rand() % cnt;
504 bestT = rand() % cnt;
505 if ( bestR == bestS || bestR == bestT || bestS == bestT ) {
509 // abc acb bac bca cab cba
510 if ( bestR > bestS ) {
515 // abc acb abc bca acb bca
516 if ( bestS > bestT ) {
521 // abc abc abc bac abc bac
522 if ( bestR > bestS ) {
527 // abc abc abc abc abc abc
529 VectorSubtract( vert[bestS].xyz, vert[bestR].xyz, ab );
530 VectorSubtract( vert[bestT].xyz, vert[bestR].xyz, ac );
531 CrossProduct( ab, ac, cross );
532 bestA = VectorLength( cross );
535 if ( bestA < TINY_AREA ) {
536 /* the biggest triangle is degenerate - then every other is too, and the other algorithms wouldn't generate anything useful either */
541 indexes[i++] = bestR;
542 indexes[i++] = bestS;
543 indexes[i++] = bestT;
546 /* identify the other fragments */
548 /* full polygon without triangle (bestR,bestS,bestT) = three new polygons:
554 j = MaxAreaIndexes( vert + bestR, bestS - bestR + 1, indexes + i );
561 /* uses 3*(bestS-bestR+1)-6 */
562 j = MaxAreaIndexes( vert + bestS, bestT - bestS + 1, indexes + i );
569 /* uses 3*(bestT-bestS+1)-6 */
571 /* can'bestT recurse this one directly... therefore, buffering */
572 if ( cnt + bestR - bestT + 1 >= 3 ) {
573 buf = safe_malloc( sizeof( *vert ) * ( cnt + bestR - bestT + 1 ) );
574 memcpy( buf, vert + bestT, sizeof( *vert ) * ( cnt - bestT ) );
575 memcpy( buf + ( cnt - bestT ), vert, sizeof( *vert ) * ( bestR + 1 ) );
576 j = MaxAreaIndexes( buf, cnt + bestR - bestT + 1, indexes + i );
583 indexes[i] = ( indexes[i] + bestT ) % cnt;
584 /* uses 3*(cnt+bestR-bestT+1)-6 */
588 /* together 3 + 3*(cnt+3) - 18 = 3*cnt-6 q.e.d. */
598 MaxAreaFaceSurface() - divVerent
599 creates a triangle list using max area indexes
602 void MaxAreaFaceSurface( mapDrawSurface_t *ds ){
604 /* try to early out */
605 if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
609 /* is this a simple triangle? */
610 if ( ds->numVerts == 3 ) {
612 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
613 VectorSet( ds->indexes, 0, 1, 2 );
614 numMaxAreaSurfaces++;
619 ds->numIndexes = 3 * ds->numVerts - 6;
620 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
621 n = MaxAreaIndexes( ds->verts, ds->numVerts, ds->indexes );
623 /* whatever we do, it's degenerate */
626 StripFaceSurface( ds );
632 numMaxAreaSurfaces++;
635 ClassifySurfaces( 1, ds );
641 FanFaceSurface() - ydnar
642 creates a tri-fan from a brush face winding
643 loosely based on SurfaceAsTriFan()
646 void FanFaceSurface( mapDrawSurface_t *ds ){
647 int i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
648 bspDrawVert_t *verts, *centroid, *dv;
652 /* try to early out */
653 if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
657 /* add a new vertex at the beginning of the surface */
658 verts = safe_malloc( ( ds->numVerts + 1 ) * sizeof( bspDrawVert_t ) );
659 memset( verts, 0, sizeof( bspDrawVert_t ) );
660 memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
664 /* add up the drawverts to create a centroid */
665 centroid = &verts[ 0 ];
666 memset( color, 0, 4 * MAX_LIGHTMAPS * sizeof( int ) );
667 for ( i = 1, dv = &verts[ 1 ]; i < ( ds->numVerts + 1 ); i++, dv++ )
669 VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
670 VectorAdd( centroid->normal, dv->normal, centroid->normal );
671 for ( j = 0; j < 4; j++ )
673 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
674 color[ k ][ j ] += dv->color[ k ][ j ];
676 centroid->st[ j ] += dv->st[ j ];
677 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
678 centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
683 /* average the centroid */
684 iv = 1.0f / ds->numVerts;
685 VectorScale( centroid->xyz, iv, centroid->xyz );
686 if ( VectorNormalize( centroid->normal, centroid->normal ) <= 0 ) {
687 VectorCopy( verts[ 1 ].normal, centroid->normal );
689 for ( j = 0; j < 4; j++ )
691 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
693 color[ k ][ j ] /= ds->numVerts;
694 centroid->color[ k ][ j ] = ( color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255 );
697 centroid->st[ j ] *= iv;
698 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
699 centroid->lightmap[ k ][ j ] *= iv;
703 /* add to vert count */
706 /* fill indexes in triangle fan order */
708 ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
709 for ( i = 1; i < ds->numVerts; i++ )
713 c = ( i + 1 ) % ds->numVerts;
715 ds->indexes[ ds->numIndexes++ ] = a;
716 ds->indexes[ ds->numIndexes++ ] = b;
717 ds->indexes[ ds->numIndexes++ ] = c;
724 ClassifySurfaces( 1, ds );
730 StripFaceSurface() - ydnar
731 attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
732 based on SurfaceAsTriStrip()
735 #define MAX_INDEXES 1024
737 void StripFaceSurface( mapDrawSurface_t *ds ){
738 int i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
742 /* try to early out */
743 if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
747 /* is this a simple triangle? */
748 if ( ds->numVerts == 3 ) {
750 VectorSet( indexes, 0, 1, 2 );
754 /* ydnar: find smallest coordinate */
756 if ( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse ) {
757 for ( i = 0; i < ds->numVerts; i++ )
760 v1 = ds->verts[ i ].xyz;
761 v2 = ds->verts[ least ].xyz;
764 if ( v1[ 0 ] < v2[ 0 ] ||
765 ( v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ] ) ||
766 ( v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ] ) ) {
772 /* determine the triangle strip order */
773 numIndexes = ( ds->numVerts - 2 ) * 3;
774 if ( numIndexes > MAX_INDEXES ) {
775 Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
778 /* try all possible orderings of the points looking for a non-degenerate strip order */
780 for ( r = 0; r < ds->numVerts; r++ )
783 rotate = ( r + least ) % ds->numVerts;
785 /* walk the winding in both directions */
786 for ( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
789 a = ( ds->numVerts - 1 - i + rotate ) % ds->numVerts;
790 b = ( i + rotate ) % ds->numVerts;
791 c = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
793 /* test this triangle */
794 if ( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) ) {
801 /* handle end case */
802 if ( i + 1 != ds->numVerts - 1 - i ) {
804 a = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
805 b = ( i + rotate ) % ds->numVerts;
806 c = ( i + 1 + rotate ) % ds->numVerts;
809 if ( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) ) {
819 if ( ni == numIndexes ) {
824 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
825 if ( ni < numIndexes ) {
826 FanFaceSurface( ds );
831 /* copy strip triangle indexes */
832 ds->numIndexes = numIndexes;
833 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
834 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
840 ClassifySurfaces( 1, ds );
847 vortex: prints meta statistics in general output
850 void EmitMetaStats(){
851 Sys_Printf( "--- EmitMetaStats ---\n" );
852 Sys_Printf( "%9d total meta surfaces\n", numMetaSurfaces );
853 Sys_Printf( "%9d stripped surfaces\n", numStripSurfaces );
854 Sys_Printf( "%9d fanned surfaces\n", numFanSurfaces );
855 Sys_Printf( "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
856 Sys_Printf( "%9d patch meta surfaces\n", numPatchMetaSurfaces );
857 Sys_Printf( "%9d meta verts\n", numMetaVerts );
858 Sys_Printf( "%9d meta triangles\n", numMetaTriangles );
864 MakeEntityMetaTriangles()
865 builds meta triangles from brush faces (tristrips and fans)
868 void MakeEntityMetaTriangles( entity_t *e ){
869 int i, f, fOld, start;
870 mapDrawSurface_t *ds;
874 Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
878 start = I_FloatTime();
880 /* walk the list of surfaces in the entity */
881 for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
884 f = 10 * ( i - e->firstDrawSurf ) / ( numMapDrawSurfs - e->firstDrawSurf );
887 Sys_FPrintf( SYS_VRB, "%d...", f );
891 ds = &mapDrawSurfs[ i ];
892 if ( ds->numVerts <= 0 ) {
896 /* ignore autosprite surfaces */
897 if ( ds->shaderInfo->autosprite ) {
901 /* meta this surface? */
902 if ( meta == qfalse && ds->shaderInfo->forceMeta == qfalse ) {
911 if ( maxAreaFaceSurface ) {
912 MaxAreaFaceSurface( ds );
915 StripFaceSurface( ds );
917 SurfaceToMetaTriangles( ds );
921 TriangulatePatchSurface( e, ds );
924 case SURFACE_TRIANGLES:
927 case SURFACE_FORCED_META:
929 SurfaceToMetaTriangles( ds );
938 if ( ( numMapDrawSurfs - e->firstDrawSurf ) ) {
939 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
942 /* emit some stats */
943 Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
944 Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
945 Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
946 Sys_FPrintf( SYS_VRB, "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
947 Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
948 Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
949 Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
952 TidyEntitySurfaces( e );
959 sets up an edge structure from a plane and 2 points that the edge ab falls lies in
962 typedef struct edge_s
966 vec_t length, kingpinLength;
972 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge ){
973 /* copy edge origin */
974 VectorCopy( a, edge->origin );
976 /* create vector aligned with winding direction of edge */
977 VectorSubtract( b, a, edge->edge );
979 if ( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) ) {
982 else if ( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) ) {
988 edge->kingpinLength = edge->edge[ edge->kingpin ];
990 VectorNormalize( edge->edge, edge->edge );
991 edge->edge[ 3 ] = DotProduct( a, edge->edge );
992 edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
994 /* create perpendicular plane that edge lies in */
995 CrossProduct( plane, edge->edge, edge->plane );
996 edge->plane[ 3 ] = DotProduct( a, edge->plane );
1003 fixes t-junctions on meta triangles
1006 #define TJ_PLANE_EPSILON ( 1.0f / 8.0f )
1007 #define TJ_EDGE_EPSILON ( 1.0f / 8.0f )
1008 #define TJ_POINT_EPSILON ( 1.0f / 8.0f )
1010 void FixMetaTJunctions( void ){
1011 int i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
1012 metaTriangle_t *tri, *newTri;
1014 bspDrawVert_t *a, *b, *c, junc;
1021 /* this code is crap; revisit later */
1025 Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
1029 start = I_FloatTime();
1031 /* walk triangle list */
1033 for ( i = 0; i < numMetaTriangles; i++ )
1036 tri = &metaTriangles[ i ];
1038 /* print pacifier */
1039 f = 10 * i / numMetaTriangles;
1042 Sys_FPrintf( SYS_VRB, "%d...", f );
1045 /* attempt to early out */
1047 if ( ( si->compileFlags & C_NODRAW ) || si->autosprite || si->notjunc ) {
1051 /* calculate planes */
1052 VectorCopy( tri->plane, plane );
1053 plane[ 3 ] = tri->plane[ 3 ];
1054 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1055 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1056 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1058 /* walk meta vert list */
1059 for ( j = 0; j < numMetaVerts; j++ )
1062 VectorCopy( metaVerts[ j ].xyz, pt );
1064 /* determine if point lies in the triangle's plane */
1065 dist = DotProduct( pt, plane ) - plane[ 3 ];
1066 if ( fabs( dist ) > TJ_PLANE_EPSILON ) {
1070 /* skip this point if it already exists in the triangle */
1071 for ( k = 0; k < 3; k++ )
1073 if ( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
1074 fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
1075 fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON ) {
1084 for ( k = 0; k < 3; k++ )
1086 /* ignore bogus edges */
1087 if ( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON ) {
1091 /* determine if point lies on the edge */
1092 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
1093 if ( fabs( dist ) > TJ_EDGE_EPSILON ) {
1097 /* determine how far along the edge the point lies */
1098 amount = ( pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ] ) / edges[ k ].kingpinLength;
1099 if ( amount <= 0.0f || amount >= 1.0f ) {
1104 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
1105 if ( dist <= -0.0f || dist >= edges[ k ].length ) {
1108 amount = dist / edges[ k ].length;
1111 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
1112 a = &metaVerts[ tri->indexes[ k % 3 ] ];
1113 b = &metaVerts[ tri->indexes[ ( k + 1 ) % 3 ] ];
1114 c = &metaVerts[ tri->indexes[ ( k + 2 ) % 3 ] ];
1117 LerpDrawVertAmount( a, b, amount, &junc );
1118 VectorCopy( pt, junc.xyz );
1120 /* compare against existing verts */
1121 if ( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) ) {
1125 /* see if we can just re-use the existing vert */
1126 if ( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) ) {
1131 /* find new vertex (note: a and b are invalid pointers after this) */
1132 firstSearchMetaVert = numMetaVerts;
1133 vertIndex = FindMetaVertex( &junc );
1134 if ( vertIndex < 0 ) {
1139 /* make new triangle */
1140 triIndex = AddMetaTriangle();
1141 if ( triIndex < 0 ) {
1146 tri = &metaTriangles[ i ];
1147 newTri = &metaTriangles[ triIndex ];
1149 /* copy the triangle */
1150 memcpy( newTri, tri, sizeof( *tri ) );
1153 tri->indexes[ ( k + 1 ) % 3 ] = vertIndex;
1154 newTri->indexes[ k ] = vertIndex;
1156 /* recalculate edges */
1157 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1158 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1159 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1162 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
1163 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
1164 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
1166 /* add to counter and end processing of this vert */
1174 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1176 /* emit some stats */
1177 Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
1183 SmoothMetaTriangles()
1184 averages coincident vertex normals in the meta triangles
1187 #define MAX_SAMPLES 256
1188 #define THETA_EPSILON 0.000001
1189 #define EQUAL_NORMAL_EPSILON 0.01
1191 void SmoothMetaTriangles( void ){
1192 int i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
1193 float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
1194 metaTriangle_t *tri;
1197 vec3_t average, diff;
1198 int indexes[ MAX_SAMPLES ];
1199 vec3_t votes[ MAX_SAMPLES ];
1202 Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
1204 /* allocate shade angle table */
1205 shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
1206 memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
1208 /* allocate smoothed table */
1209 cs = ( numMetaVerts / 8 ) + 1;
1210 smoothed = safe_malloc( cs );
1211 memset( smoothed, 0, cs );
1213 /* set default shade angle */
1214 defaultShadeAngle = DEG2RAD( npDegrees );
1215 maxShadeAngle = 0.0f;
1217 /* run through every surface and flag verts belonging to non-lightmapped surfaces
1218 and set per-vertex smoothing angle */
1219 for ( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
1221 shadeAngle = defaultShadeAngle;
1223 /* get shade angle from shader */
1224 if ( tri->si->shadeAngleDegrees > 0.0f ) {
1225 shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1227 /* get shade angle from entity */
1228 else if ( tri->shadeAngleDegrees > 0.0f ) {
1229 shadeAngle = DEG2RAD( tri->shadeAngleDegrees );
1232 if ( shadeAngle <= 0.0f ) {
1233 shadeAngle = defaultShadeAngle;
1236 if ( shadeAngle > maxShadeAngle ) {
1237 maxShadeAngle = shadeAngle;
1240 /* flag its verts */
1241 for ( j = 0; j < 3; j++ )
1243 shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1244 if ( shadeAngle <= 0 ) {
1245 smoothed[ tri->indexes[ j ] >> 3 ] |= ( 1 << ( tri->indexes[ j ] & 7 ) );
1250 /* bail if no surfaces have a shade angle */
1251 if ( maxShadeAngle <= 0 ) {
1252 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1253 free( shadeAngles );
1260 start = I_FloatTime();
1262 /* go through the list of vertexes */
1264 for ( i = 0; i < numMetaVerts; i++ )
1266 /* print pacifier */
1267 f = 10 * i / numMetaVerts;
1270 Sys_FPrintf( SYS_VRB, "%d...", f );
1273 /* already smoothed? */
1274 if ( smoothed[ i >> 3 ] & ( 1 << ( i & 7 ) ) ) {
1279 VectorClear( average );
1283 /* build a table of coincident vertexes */
1284 for ( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1286 /* already smoothed? */
1287 if ( smoothed[ j >> 3 ] & ( 1 << ( j & 7 ) ) ) {
1292 if ( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse ) {
1296 /* use smallest shade angle */
1297 shadeAngle = ( shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ] );
1299 /* check shade angle */
1300 dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1304 else if ( dot < -1.0 ) {
1307 testAngle = acos( dot ) + THETA_EPSILON;
1308 if ( testAngle >= shadeAngle ) {
1312 /* add to the list */
1313 indexes[ numVerts++ ] = j;
1316 smoothed[ j >> 3 ] |= ( 1 << ( j & 7 ) );
1318 /* see if this normal has already been voted */
1319 for ( k = 0; k < numVotes; k++ )
1321 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1322 if ( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1323 fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1324 fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON ) {
1329 /* add a new vote? */
1330 if ( k == numVotes && numVotes < MAX_SAMPLES ) {
1331 VectorAdd( average, metaVerts[ j ].normal, average );
1332 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1337 /* don't average for less than 2 verts */
1338 if ( numVerts < 2 ) {
1342 /* average normal */
1343 if ( VectorNormalize( average, average ) > 0 ) {
1345 for ( j = 0; j < numVerts; j++ )
1346 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1351 /* free the tables */
1352 free( shadeAngles );
1356 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1358 /* emit some stats */
1359 Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1365 AddMetaVertToSurface()
1366 adds a drawvert to a surface unless an existing vert matching already exists
1367 returns the index of that vert (or < 0 on failure)
1370 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident ){
1375 /* go through the verts and find a suitable candidate */
1376 for ( i = 0; i < ds->numVerts; i++ )
1379 dv2 = &ds->verts[ i ];
1381 /* compare xyz and normal */
1382 if ( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse ) {
1385 if ( VectorCompare( dv1->normal, dv2->normal ) == qfalse ) {
1389 /* good enough at this point */
1392 /* compare texture coordinates and color */
1393 if ( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] ) {
1396 if ( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] ) {
1400 /* found a winner */
1405 /* overflow check */
1406 if ( ds->numVerts >= ( ( ds->shaderInfo->compileFlags & C_VERTEXLIT ) ? maxSurfaceVerts : maxLMSurfaceVerts ) ) {
1407 return VERTS_EXCEEDED;
1410 /* made it this far, add the vert and return */
1411 dv2 = &ds->verts[ ds->numVerts++ ];
1413 return ( ds->numVerts - 1 );
1420 AddMetaTriangleToSurface()
1421 attempts to add a metatriangle to a surface
1422 returns the score of the triangle added
1425 #define AXIS_SCORE 100000
1426 #define AXIS_MIN 100000
1427 #define VERT_SCORE 10000
1428 #define SURFACE_SCORE 1000
1430 #define ST_SCORE2 ( 2 * ( ST_SCORE ) )
1432 #define DEFAULT_ADEQUATE_SCORE ( (AXIS_MIN) +1 * ( VERT_SCORE ) )
1433 #define DEFAULT_GOOD_SCORE ( (AXIS_MIN) +2 * (VERT_SCORE) +4 * ( ST_SCORE ) )
1434 #define PERFECT_SCORE ( (AXIS_MIN) +3 * ( VERT_SCORE ) + (SURFACE_SCORE) +4 * ( ST_SCORE ) )
1436 #define ADEQUATE_SCORE ( metaAdequateScore >= 0 ? metaAdequateScore : DEFAULT_ADEQUATE_SCORE )
1437 #define GOOD_SCORE ( metaGoodScore >= 0 ? metaGoodScore : DEFAULT_GOOD_SCORE )
1439 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd ){
1441 int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1444 qboolean inTexRange;
1445 mapDrawSurface_t old;
1448 /* overflow check */
1449 if ( ds->numIndexes >= maxSurfaceIndexes ) {
1453 /* test the triangle */
1454 if ( ds->entityNum != tri->entityNum ) { /* ydnar: added 2002-07-06 */
1457 if ( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows ) {
1460 if ( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize ) {
1464 if ( !( ds->shaderInfo->compileFlags & C_VERTEXLIT ) &&
1465 //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1466 DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f ) {
1471 /* planar surfaces will only merge with triangles in the same plane */
1472 if ( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 ) {
1473 if ( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] ) {
1476 if ( tri->planeNum >= 0 && tri->planeNum != ds->planeNum ) {
1481 if ( metaMaxBBoxDistance >= 0 ) {
1482 if ( ds->numIndexes > 0 ) {
1483 VectorCopy( ds->mins, mins );
1484 VectorCopy( ds->maxs, maxs );
1485 mins[0] -= metaMaxBBoxDistance;
1486 mins[1] -= metaMaxBBoxDistance;
1487 mins[2] -= metaMaxBBoxDistance;
1488 maxs[0] += metaMaxBBoxDistance;
1489 maxs[1] += metaMaxBBoxDistance;
1490 maxs[2] += metaMaxBBoxDistance;
1491 #define CHECK_1D( mins, v, maxs ) ( ( mins ) <= ( v ) && ( v ) <= ( maxs ) )
1492 #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] ) )
1493 VectorCopy( metaVerts[ tri->indexes[ 0 ] ].xyz, p );
1494 if ( !CHECK_3D( mins, p, maxs ) ) {
1495 VectorCopy( metaVerts[ tri->indexes[ 1 ] ].xyz, p );
1496 if ( !CHECK_3D( mins, p, maxs ) ) {
1497 VectorCopy( metaVerts[ tri->indexes[ 2 ] ].xyz, p );
1498 if ( !CHECK_3D( mins, p, maxs ) ) {
1508 /* set initial score */
1509 score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1511 /* score the the dot product of lightmap axis to plane */
1512 if ( ( ds->shaderInfo->compileFlags & C_VERTEXLIT ) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) ) {
1513 score += AXIS_SCORE;
1516 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1519 /* preserve old drawsurface if this fails */
1520 memcpy( &old, ds, sizeof( *ds ) );
1522 /* attempt to add the verts */
1524 ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1525 bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1526 ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1528 /* check vertex underflow */
1529 if ( ai < 0 || bi < 0 || ci < 0 ) {
1530 memcpy( ds, &old, sizeof( *ds ) );
1534 /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1535 score += ( coincident * VERT_SCORE );
1537 /* add new vertex bounds to mins/maxs */
1538 VectorCopy( ds->mins, mins );
1539 VectorCopy( ds->maxs, maxs );
1540 AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1541 AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1542 AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1544 /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1545 if ( !( ds->shaderInfo->compileFlags & C_VERTEXLIT ) &&
1546 ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1547 ( VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse ) ) {
1548 /* set maximum size before lightmap scaling (normally 2032 units) */
1549 /* 2004-02-24: scale lightmap test size by 2 to catch larger brush faces */
1550 /* 2004-04-11: reverting to actual lightmap size */
1551 lmMax = ( ds->sampleSize * ( ds->shaderInfo->lmCustomWidth - 1 ) );
1552 for ( i = 0; i < 3; i++ )
1554 if ( ( maxs[ i ] - mins[ i ] ) > lmMax ) {
1555 memcpy( ds, &old, sizeof( *ds ) );
1561 /* check texture range overflow */
1562 oldTexRange[ 0 ] = ds->texRange[ 0 ];
1563 oldTexRange[ 1 ] = ds->texRange[ 1 ];
1564 inTexRange = CalcSurfaceTextureRange( ds );
1566 if ( inTexRange == qfalse && ds->numIndexes > 0 ) {
1567 memcpy( ds, &old, sizeof( *ds ) );
1568 return UNSUITABLE_TRIANGLE;
1571 /* score texture range */
1572 if ( ds->texRange[ 0 ] <= oldTexRange[ 0 ] ) {
1575 else if ( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] ) {
1579 if ( ds->texRange[ 1 ] <= oldTexRange[ 1 ] ) {
1582 else if ( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] ) {
1587 /* go through the indexes and try to find an existing triangle that matches abc */
1588 for ( i = 0; i < ds->numIndexes; i += 3 )
1590 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1591 if ( ( ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ] ) ||
1592 ( bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ] ) ||
1593 ( ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ] ) ) {
1594 /* triangle already present */
1595 memcpy( ds, &old, sizeof( *ds ) );
1600 /* rotate the triangle 3x to find an inverse triangle (error case) */
1601 if ( ( ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ] ) ||
1602 ( bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ] ) ||
1603 ( ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ] ) ) {
1605 Sys_FPrintf( SYS_WRN, "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
1606 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1607 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1608 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1610 /* reverse triangle already present */
1611 memcpy( ds, &old, sizeof( *ds ) );
1617 /* add the triangle indexes */
1618 if ( ds->numIndexes < maxSurfaceIndexes ) {
1619 ds->indexes[ ds->numIndexes++ ] = ai;
1621 if ( ds->numIndexes < maxSurfaceIndexes ) {
1622 ds->indexes[ ds->numIndexes++ ] = bi;
1624 if ( ds->numIndexes < maxSurfaceIndexes ) {
1625 ds->indexes[ ds->numIndexes++ ] = ci;
1628 /* check index overflow */
1629 if ( ds->numIndexes >= maxSurfaceIndexes ) {
1630 memcpy( ds, &old, sizeof( *ds ) );
1634 /* sanity check the indexes */
1635 if ( ds->numIndexes >= 3 &&
1636 ( ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1637 ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1638 ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ] ) ) {
1639 Sys_Printf( "DEG:%d! ", ds->numVerts );
1644 memcpy( ds, &old, sizeof( *ds ) );
1648 /* copy bounds back to surface */
1649 VectorCopy( mins, ds->mins );
1650 VectorCopy( maxs, ds->maxs );
1652 /* mark triangle as used */
1656 /* add a side reference */
1657 ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1659 /* return to sender */
1666 MetaTrianglesToSurface()
1667 creates map drawsurface(s) from the list of possibles
1670 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded ){
1671 int i, j, f, best, score, bestScore;
1672 metaTriangle_t *seed, *test;
1673 mapDrawSurface_t *ds;
1674 bspDrawVert_t *verts;
1679 /* allocate arrays */
1680 verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1681 indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1683 /* walk the list of triangles */
1684 for ( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1686 /* skip this triangle if it has already been merged */
1687 if ( seed->si == NULL ) {
1691 /* -----------------------------------------------------------------
1692 initial drawsurf construction
1693 ----------------------------------------------------------------- */
1695 /* start a new drawsurface */
1696 ds = AllocDrawSurface( SURFACE_META );
1697 ds->entityNum = seed->entityNum;
1698 ds->surfaceNum = seed->surfaceNum;
1699 ds->castShadows = seed->castShadows;
1700 ds->recvShadows = seed->recvShadows;
1702 ds->shaderInfo = seed->si;
1703 ds->planeNum = seed->planeNum;
1704 ds->fogNum = seed->fogNum;
1705 ds->sampleSize = seed->sampleSize;
1706 ds->shadeAngleDegrees = seed->shadeAngleDegrees;
1708 ds->indexes = indexes;
1709 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1710 ds->sideRef = AllocSideRef( seed->side, NULL );
1712 ClearBounds( ds->mins, ds->maxs );
1714 /* clear verts/indexes */
1715 memset( verts, 0, sizeof( *verts ) * maxSurfaceVerts );
1716 memset( indexes, 0, sizeof( *indexes ) * maxSurfaceIndexes );
1718 /* add the first triangle */
1719 if ( AddMetaTriangleToSurface( ds, seed, qfalse ) ) {
1723 /* -----------------------------------------------------------------
1725 ----------------------------------------------------------------- */
1727 /* progressively walk the list until no more triangles can be added */
1731 /* print pacifier */
1732 f = 10 * *numAdded / numMetaTriangles;
1735 Sys_FPrintf( SYS_VRB, "%d...", f );
1738 /* reset best score */
1743 /* walk the list of possible candidates for merging */
1744 for ( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1746 /* skip this triangle if it has already been merged */
1747 if ( test->si == NULL ) {
1751 /* score this triangle */
1752 score = AddMetaTriangleToSurface( ds, test, qtrue );
1753 if ( score > bestScore ) {
1757 /* if we have a score over a certain threshold, just use it */
1758 if ( bestScore >= GOOD_SCORE ) {
1759 if ( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) ) {
1771 /* add best candidate */
1772 if ( best >= 0 && bestScore > ADEQUATE_SCORE ) {
1773 if ( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) ) {
1782 /* copy the verts and indexes to the new surface */
1783 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1784 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1785 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1786 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1788 /* classify the surface */
1789 ClassifySurfaces( 1, ds );
1792 numMergedSurfaces++;
1803 CompareMetaTriangles()
1804 compare function for qsort()
1807 static int CompareMetaTriangles( const void *a, const void *b ){
1809 vec3_t aMins, bMins;
1813 if ( ( (const metaTriangle_t*) a )->si < ( (const metaTriangle_t*) b )->si ) {
1816 else if ( ( (const metaTriangle_t*) a )->si > ( (const metaTriangle_t*) b )->si ) {
1821 else if ( ( (const metaTriangle_t*) a )->fogNum < ( (const metaTriangle_t*) b )->fogNum ) {
1824 else if ( ( (const metaTriangle_t*) a )->fogNum > ( (const metaTriangle_t*) b )->fogNum ) {
1830 else if ( npDegrees == 0.0f && ( (const metaTriangle_t*) a )->si->nonplanar == qfalse &&
1831 ( (const metaTriangle_t*) a )->planeNum >= 0 && ( (const metaTriangle_t*) a )->planeNum >= 0 ) {
1832 if ( ( (const metaTriangle_t*) a )->plane[ 3 ] < ( (const metaTriangle_t*) b )->plane[ 3 ] ) {
1835 else if ( ( (const metaTriangle_t*) a )->plane[ 3 ] > ( (const metaTriangle_t*) b )->plane[ 3 ] ) {
1838 else if ( ( (const metaTriangle_t*) a )->plane[ 0 ] < ( (const metaTriangle_t*) b )->plane[ 0 ] ) {
1841 else if ( ( (const metaTriangle_t*) a )->plane[ 0 ] > ( (const metaTriangle_t*) b )->plane[ 0 ] ) {
1844 else if ( ( (const metaTriangle_t*) a )->plane[ 1 ] < ( (const metaTriangle_t*) b )->plane[ 1 ] ) {
1847 else if ( ( (const metaTriangle_t*) a )->plane[ 1 ] > ( (const metaTriangle_t*) b )->plane[ 1 ] ) {
1850 else if ( ( (const metaTriangle_t*) a )->plane[ 2 ] < ( (const metaTriangle_t*) b )->plane[ 2 ] ) {
1853 else if ( ( (const metaTriangle_t*) a )->plane[ 2 ] > ( (const metaTriangle_t*) b )->plane[ 2 ] ) {
1859 /* then position in world */
1862 VectorSet( aMins, 999999, 999999, 999999 );
1863 VectorSet( bMins, 999999, 999999, 999999 );
1864 for ( i = 0; i < 3; i++ )
1866 av = ( (const metaTriangle_t*) a )->indexes[ i ];
1867 bv = ( (const metaTriangle_t*) b )->indexes[ i ];
1868 for ( j = 0; j < 3; j++ )
1870 if ( metaVerts[ av ].xyz[ j ] < aMins[ j ] ) {
1871 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1873 if ( metaVerts[ bv ].xyz[ j ] < bMins[ j ] ) {
1874 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1880 for ( i = 0; i < 3; i++ )
1882 if ( aMins[ i ] < bMins[ i ] ) {
1885 else if ( aMins[ i ] > bMins[ i ] ) {
1890 /* functionally equivalent */
1897 MergeMetaTriangles()
1898 merges meta triangles into drawsurfaces
1901 void MergeMetaTriangles( void ){
1902 int i, j, fOld, start, numAdded;
1903 metaTriangle_t *head, *end;
1906 /* only do this if there are meta triangles */
1907 if ( numMetaTriangles <= 0 ) {
1912 Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1914 /* sort the triangles by shader major, fognum minor */
1915 qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1919 start = I_FloatTime();
1923 for ( i = 0, j = 0; i < numMetaTriangles; i = j )
1925 /* get head of list */
1926 head = &metaTriangles[ i ];
1928 /* skip this triangle if it has already been merged */
1929 if ( head->si == NULL ) {
1935 for ( j = i + 1; j < numMetaTriangles; j++ )
1937 /* get end of list */
1938 end = &metaTriangles[ j ];
1939 if ( head->si != end->si || head->fogNum != end->fogNum ) {
1945 /* try to merge this list of possible merge candidates */
1946 MetaTrianglesToSurface( ( j - i ), head, &fOld, &numAdded );
1949 /* clear meta triangle list */
1950 ClearMetaTriangles();
1954 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1957 /* emit some stats */
1958 Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1959 Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );