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