tech
/
worldspawn
2
0
Fork 0
Code Issues 16 Pull Requests Projects Releases Wiki Activity
worldspawn/tools/vmap/surface_meta.c

1970 lines
52 KiB
C
Raw Permalink Blame History

/* -------------------------------------------------------------------------------
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 "vmap.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.cubemapNum = ds->cubemapNum;
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, tryy;
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 ( tryy = 0; tryy < MAXAREA_MAXTRIES; ++tryy )
{
if ( tryy ) {
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 DEFAULT_ADEQUATE_SCORE ( (AXIS_MIN) +1 * ( VERT_SCORE ) )
#define DEFAULT_GOOD_SCORE ( (AXIS_MIN) +2 * (VERT_SCORE) +4 * ( ST_SCORE ) )
#define PERFECT_SCORE ( (AXIS_MIN) +3 * ( VERT_SCORE ) + (SURFACE_SCORE) +4 * ( ST_SCORE ) )
#define ADEQUATE_SCORE ( metaAdequateScore >= 0 ? metaAdequateScore : DEFAULT_ADEQUATE_SCORE )
#define GOOD_SCORE ( metaGoodScore >= 0 ? metaGoodScore : DEFAULT_GOOD_SCORE )
static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd ){
vec3_t p;
int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
float lmMax;
vec3_t mins, maxs;
qboolean inTexRange;
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->cubemapNum != tri->cubemapNum || 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 ( metaMaxBBoxDistance >= 0 ) {
if ( ds->numIndexes > 0 ) {
VectorCopy( ds->mins, mins );
VectorCopy( ds->maxs, maxs );
mins[0] -= metaMaxBBoxDistance;
mins[1] -= metaMaxBBoxDistance;
mins[2] -= metaMaxBBoxDistance;
maxs[0] += metaMaxBBoxDistance;
maxs[1] += metaMaxBBoxDistance;
maxs[2] += metaMaxBBoxDistance;
#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
}
}
/* 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 );
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_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",
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->cubemapNum = seed->cubemapNum;
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 ) * maxSurfaceVerts );
memset( indexes, 0, sizeof( *indexes ) * maxSurfaceIndexes );
/* 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 cubemaps */
else if ( ( (const metaTriangle_t*) a )->cubemapNum < ( (const metaTriangle_t*) b )->cubemapNum ) {
return 1;
}
else if ( ( (const metaTriangle_t*) a )->cubemapNum > ( (const metaTriangle_t*) b )->cubemapNum ) {
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 || head->cubemapNum != end->cubemapNum ) {
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 );
}
Reference in New Issue View Git Blame Copy Permalink