From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- q3map/surface.c | 2274 +++++++++++++++++++++++++++---------------------------- 1 file changed, 1137 insertions(+), 1137 deletions(-) (limited to 'q3map/surface.c') diff --git a/q3map/surface.c b/q3map/surface.c index 462449d..75daf1c 100755 --- a/q3map/surface.c +++ b/q3map/surface.c @@ -19,1140 +19,1140 @@ along with Foobar; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA =========================================================================== */ - -#include "qbsp.h" - - -mapDrawSurface_t mapDrawSurfs[MAX_MAP_DRAW_SURFS]; -int numMapDrawSurfs; - -/* -============================================================================= - -DRAWSURF CONSTRUCTION - -============================================================================= -*/ - -/* -================= -AllocDrawSurf -================= -*/ -mapDrawSurface_t *AllocDrawSurf( void ) { - mapDrawSurface_t *ds; - - if ( numMapDrawSurfs >= MAX_MAP_DRAW_SURFS ) { - Error( "MAX_MAP_DRAW_SURFS"); - } - ds = &mapDrawSurfs[ numMapDrawSurfs ]; - numMapDrawSurfs++; - - return ds; -} - -/* -================= -DrawSurfaceForSide -================= -*/ -#define SNAP_FLOAT_TO_INT 8 -#define SNAP_INT_TO_FLOAT (1.0/SNAP_FLOAT_TO_INT) - -mapDrawSurface_t *DrawSurfaceForSide( bspbrush_t *b, side_t *s, winding_t *w ) { - mapDrawSurface_t *ds; - int i, j; - shaderInfo_t *si; - drawVert_t *dv; - float mins[2], maxs[2]; - - // brush primitive : - // axis base - vec3_t texX,texY; - vec_t x,y; - - if ( w->numpoints > 64 ) { - Error( "DrawSurfaceForSide: w->numpoints = %i", w->numpoints ); - } - - si = s->shaderInfo; - - ds = AllocDrawSurf(); - - ds->shaderInfo = si; - ds->mapBrush = b; - ds->side = s; - ds->fogNum = -1; - ds->numVerts = w->numpoints; - ds->verts = malloc( ds->numVerts * sizeof( *ds->verts ) ); - memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) ); - - mins[0] = mins[1] = 99999; - maxs[0] = maxs[1] = -99999; - - // compute s/t coordinates from brush primitive texture matrix - // compute axis base - ComputeAxisBase( mapplanes[s->planenum].normal, texX, texY ); - - for ( j = 0 ; j < w->numpoints ; j++ ) { - dv = ds->verts + j; - - // round the xyz to a given precision - for ( i = 0 ; i < 3 ; i++ ) { - dv->xyz[i] = SNAP_INT_TO_FLOAT * floor( w->p[j][i] * SNAP_FLOAT_TO_INT + 0.5 ); - } - - if (g_bBrushPrimit==BPRIMIT_OLDBRUSHES) - { - // calculate texture s/t - dv->st[0] = s->vecs[0][3] + DotProduct( s->vecs[0], dv->xyz ); - dv->st[1] = s->vecs[1][3] + DotProduct( s->vecs[1], dv->xyz ); - dv->st[0] /= si->width; - dv->st[1] /= si->height; - } - else - { - // calculate texture s/t from brush primitive texture matrix - x = DotProduct( dv->xyz, texX ); - y = DotProduct( dv->xyz, texY ); - dv->st[0]=s->texMat[0][0]*x+s->texMat[0][1]*y+s->texMat[0][2]; - dv->st[1]=s->texMat[1][0]*x+s->texMat[1][1]*y+s->texMat[1][2]; - } - - for ( i = 0 ; i < 2 ; i++ ) { - if ( dv->st[i] < mins[i] ) { - mins[i] = dv->st[i]; - } - if ( dv->st[i] > maxs[i] ) { - maxs[i] = dv->st[i]; - } - } - - // copy normal - VectorCopy ( mapplanes[s->planenum].normal, dv->normal ); - } - - // adjust the texture coordinates to be as close to 0 as possible - if ( !si->globalTexture ) { - mins[0] = floor( mins[0] ); - mins[1] = floor( mins[1] ); - for ( i = 0 ; i < w->numpoints ; i++ ) { - dv = ds->verts + i; - dv->st[0] -= mins[0]; - dv->st[1] -= mins[1]; - } - } - - return ds; -} - - -//========================================================================= - - - - -typedef struct { - int planenum; - shaderInfo_t *shaderInfo; - int count; -} sideRef_t; - -#define MAX_SIDE_REFS MAX_MAP_PLANES - -sideRef_t sideRefs[MAX_SIDE_REFS]; -int numSideRefs; - -void AddSideRef( side_t *side ) { - int i; - - for ( i = 0 ; i < numSideRefs ; i++ ) { - if ( side->planenum == sideRefs[i].planenum - && side->shaderInfo == sideRefs[i].shaderInfo ) { - sideRefs[i].count++; - return; - } - } - - if ( numSideRefs == MAX_SIDE_REFS ) { - Error( "MAX_SIDE_REFS" ); - } - - sideRefs[i].planenum = side->planenum; - sideRefs[i].shaderInfo = side->shaderInfo; - sideRefs[i].count++; - numSideRefs++; -} - - -/* -===================== -MergeSides - -===================== -*/ -void MergeSides( entity_t *e, tree_t *tree ) { - int i; - - qprintf( "----- MergeSides -----\n"); - - for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) { -// AddSideRef( side ); - } - - qprintf( "%5i siderefs\n", numSideRefs ); -} - -//===================================================================== - -/* -=================== -SubdivideDrawSurf -=================== -*/ -void SubdivideDrawSurf( mapDrawSurface_t *ds, winding_t *w, float subdivisions ) { - int i; - int axis; - vec3_t bounds[2]; - const float epsilon = 0.1; - int subFloor, subCeil; - winding_t *frontWinding, *backWinding; - mapDrawSurface_t *newds; - - if ( !w ) { - return; - } - if ( w->numpoints < 3 ) { - Error( "SubdivideDrawSurf: Bad w->numpoints" ); - } - - ClearBounds( bounds[0], bounds[1] ); - for ( i = 0 ; i < w->numpoints ; i++ ) { - AddPointToBounds( w->p[i], bounds[0], bounds[1] ); - } - - for ( axis = 0 ; axis < 3 ; axis++ ) { - vec3_t planePoint = { 0, 0, 0 }; - vec3_t planeNormal = { 0, 0, 0 }; - float d; - - subFloor = floor( bounds[0][axis] / subdivisions ) * subdivisions; - subCeil = ceil( bounds[1][axis] / subdivisions ) * subdivisions; - - planePoint[axis] = subFloor + subdivisions; - planeNormal[axis] = -1; - - d = DotProduct( planePoint, planeNormal ); - - // subdivide if necessary - if ( subCeil - subFloor > subdivisions ) { - // gotta clip polygon into two polygons - ClipWindingEpsilon( w, planeNormal, d, epsilon, &frontWinding, &backWinding ); - - // the clip may not produce two polygons if it was epsilon close - if ( !frontWinding ) { - w = backWinding; - } else if ( !backWinding ) { - w = frontWinding; - } else { - SubdivideDrawSurf( ds, frontWinding, subdivisions ); - SubdivideDrawSurf( ds, backWinding, subdivisions ); - - return; - } - } - } - - // emit this polygon - newds = DrawSurfaceForSide( ds->mapBrush, ds->side, w ); - newds->fogNum = ds->fogNum; -} - - -/* -===================== -SubdivideDrawSurfs - -Chop up surfaces that have subdivision attributes -===================== -*/ -void SubdivideDrawSurfs( entity_t *e, tree_t *tree ) { - int i; - mapDrawSurface_t *ds; - int numBaseDrawSurfs; - winding_t *w; - float subdivision; - shaderInfo_t *si; - - qprintf( "----- SubdivideDrawSurfs -----\n"); - numBaseDrawSurfs = numMapDrawSurfs; - for ( i = e->firstDrawSurf ; i < numBaseDrawSurfs ; i++ ) { - ds = &mapDrawSurfs[i]; - - // only subdivide brush sides, not patches or misc_models - if ( !ds->side ) { - continue; - } - - // check subdivision for shader - si = ds->side->shaderInfo; - if ( !si ) { - continue; - } - - if (ds->shaderInfo->autosprite || si->autosprite) { - continue; - } - - subdivision = si->subdivisions; - if ( !subdivision ) { - continue; - } - - w = WindingFromDrawSurf( ds ); - ds->numVerts = 0; // remove this reference - SubdivideDrawSurf( ds, w, subdivision ); - } - -} - - -//=================================================================================== - -/* -==================== -ClipSideIntoTree_r - -Adds non-opaque leaf fragments to the convex hull -==================== -*/ -void ClipSideIntoTree_r( winding_t *w, side_t *side, node_t *node ) { - plane_t *plane; - winding_t *front, *back; - - if ( !w ) { - return; - } - - if ( node->planenum != PLANENUM_LEAF ) { - if ( side->planenum == node->planenum ) { - ClipSideIntoTree_r( w, side, node->children[0] ); - return; - } - if ( side->planenum == ( node->planenum ^ 1) ) { - ClipSideIntoTree_r( w, side, node->children[1] ); - return; - } - - plane = &mapplanes[ node->planenum ]; - ClipWindingEpsilon ( w, plane->normal, plane->dist, - ON_EPSILON, &front, &back ); - FreeWinding( w ); - - ClipSideIntoTree_r( front, side, node->children[0] ); - ClipSideIntoTree_r( back, side, node->children[1] ); - - return; - } - - // if opaque leaf, don't add - if ( !node->opaque ) { - AddWindingToConvexHull( w, &side->visibleHull, mapplanes[ side->planenum ].normal ); - } - - FreeWinding( w ); - return; -} - - -/* -===================== -ClipSidesIntoTree - -Creates side->visibleHull for all visible sides - -The drawsurf for a side will consist of the convex hull of -all points in non-opaque clusters, which allows overlaps -to be trimmed off automatically. -===================== -*/ -void ClipSidesIntoTree( entity_t *e, tree_t *tree ) { - bspbrush_t *b; - int i; - winding_t *w; - side_t *side, *newSide; - shaderInfo_t *si; - - qprintf( "----- ClipSidesIntoTree -----\n"); - - for ( b = e->brushes ; b ; b = b->next ) { - for ( i = 0 ; i < b->numsides ; i++ ) { - side = &b->sides[i]; - if ( !side->winding) { - continue; - } - w = CopyWinding( side->winding ); - side->visibleHull = NULL; - ClipSideIntoTree_r( w, side, tree->headnode ); - - w = side->visibleHull; - if ( !w ) { - continue; - } - si = side->shaderInfo; - if ( !si ) { - continue; - } - // don't create faces for non-visible sides - if ( si->surfaceFlags & SURF_NODRAW ) { - continue; - } - - // always use the original quad winding for auto sprites - if ( side->shaderInfo->autosprite ) { - w = side->winding; - } - // - if ( side->bevel ) { - Error( "monkey tried to create draw surface for brush bevel" ); - } - // save this winding as a visible surface - DrawSurfaceForSide( b, side, w ); - - // make a back side for it if needed - if ( !(si->contents & CONTENTS_FOG) ) { - continue; - } - - // duplicate the up-facing side - w = ReverseWinding( w ); - - newSide = malloc( sizeof( *side ) ); - *newSide = *side; - newSide->visibleHull = w; - newSide->planenum ^= 1; - - // save this winding as a visible surface - DrawSurfaceForSide( b, newSide, w ); - - } - } -} - -/* -=================================================================================== - - FILTER REFERENCES DOWN THE TREE - -=================================================================================== -*/ - -/* -==================== -FilterDrawSurfIntoTree - -Place a reference to the given drawsurf in every leaf it contacts -We assume that the point mesh aproximation to the curve will get a -reference into all the leafs we need. -==================== -*/ -int FilterMapDrawSurfIntoTree( vec3_t point, mapDrawSurface_t *ds, node_t *node ) { - drawSurfRef_t *dsr; - float d; - plane_t *plane; - int c; - - if ( node->planenum != PLANENUM_LEAF ) { - plane = &mapplanes[ node->planenum ]; - d = DotProduct( point, plane->normal ) - plane->dist; - c = 0; - if ( d >= -ON_EPSILON ) { - c += FilterMapDrawSurfIntoTree( point, ds, node->children[0] ); - } - if ( d <= ON_EPSILON ) { - c += FilterMapDrawSurfIntoTree( point, ds, node->children[1] ); - } - return c; - } - - // if opaque leaf, don't add - if ( node->opaque ) { - return 0; - } - - // add the drawsurf if it hasn't been already - for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) { - if ( dsr->outputNumber == numDrawSurfaces ) { - return 0; // already referenced - } - } - - dsr = malloc( sizeof( *dsr ) ); - dsr->outputNumber = numDrawSurfaces; - dsr->nextRef = node->drawSurfReferences; - node->drawSurfReferences = dsr; - return 1; -} - -/* -==================== -FilterDrawSurfIntoTree_r - -Place a reference to the given drawsurf in every leaf it is in -==================== -*/ -int FilterMapDrawSurfIntoTree_r( winding_t *w, mapDrawSurface_t *ds, node_t *node ) { - drawSurfRef_t *dsr; - plane_t *plane; - int total; - winding_t *front, *back; - - if ( node->planenum != PLANENUM_LEAF ) { - plane = &mapplanes[ node->planenum ]; - ClipWindingEpsilon ( w, plane->normal, plane->dist, - ON_EPSILON, &front, &back ); - - total = 0; - if ( front ) { - total += FilterMapDrawSurfIntoTree_r( front, ds, node->children[0] ); - } - if ( back ) { - total += FilterMapDrawSurfIntoTree_r( back, ds, node->children[1] ); - } - - FreeWinding( w ); - return total; - } - - // if opaque leaf, don't add - if ( node->opaque ) { - return 0; - } - - // add the drawsurf if it hasn't been already - for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) { - if ( dsr->outputNumber == numDrawSurfaces ) { - return 0; // already referenced - } - } - - dsr = malloc( sizeof( *dsr ) ); - dsr->outputNumber = numDrawSurfaces; - dsr->nextRef = node->drawSurfReferences; - node->drawSurfReferences = dsr; - return 1; -} - -/* -==================== -FilterSideIntoTree_r - -Place a reference to the given drawsurf in every leaf it contacts -==================== -*/ -int FilterSideIntoTree_r( winding_t *w, side_t *side, mapDrawSurface_t *ds, node_t *node ) { - drawSurfRef_t *dsr; - plane_t *plane; - winding_t *front, *back; - int total; - - if ( !w ) { - return 0; - } - - if ( node->planenum != PLANENUM_LEAF ) { - if ( side->planenum == node->planenum ) { - return FilterSideIntoTree_r( w, side, ds, node->children[0] ); - } - if ( side->planenum == ( node->planenum ^ 1) ) { - return FilterSideIntoTree_r( w, side, ds, node->children[1] ); - } - - plane = &mapplanes[ node->planenum ]; - ClipWindingEpsilon ( w, plane->normal, plane->dist, - ON_EPSILON, &front, &back ); - - total = FilterSideIntoTree_r( front, side, ds, node->children[0] ); - total += FilterSideIntoTree_r( back, side, ds, node->children[1] ); - - FreeWinding( w ); - return total; - } - - // if opaque leaf, don't add - if ( node->opaque ) { - return 0; - } - - dsr = malloc( sizeof( *dsr ) ); - dsr->outputNumber = numDrawSurfaces; - dsr->nextRef = node->drawSurfReferences; - node->drawSurfReferences = dsr; - - FreeWinding( w ); - return 1; -} - - -/* -===================== -FilterFaceIntoTree -===================== -*/ -int FilterFaceIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { - int l; - winding_t *w; - - w = WindingFromDrawSurf( ds ); - l = FilterSideIntoTree_r( w, ds->side, ds, tree->headnode ); - - return l; -} - - - -/* -===================== -FilterPatchSurfIntoTree -===================== -*/ -#define SUBDIVISION_LIMIT 8.0 -int FilterPatchSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { - int i, j; - int l; - mesh_t baseMesh, *subdividedMesh; - winding_t *w; - - baseMesh.width = ds->patchWidth; - baseMesh.height = ds->patchHeight; - baseMesh.verts = ds->verts; - subdividedMesh = SubdivideMesh( baseMesh, SUBDIVISION_LIMIT, 32 ); - - l = 0; - for (i = 0; i < subdividedMesh->width-1; i++) { - for (j = 0; j < subdividedMesh->height-1; j++) { - w = AllocWinding(3); - VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i].xyz, w->p[0]); - VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i + 1].xyz, w->p[1]); - VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i].xyz, w->p[2]); - w->numpoints = 3; - l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode ); - w = AllocWinding(3); - VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i + 1].xyz, w->p[0]); - VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i + 1].xyz, w->p[1]); - VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i].xyz, w->p[2]); - w->numpoints = 3; - l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode ); - } - } - - // also use the old point filtering into the tree - for ( i = 0 ; i < subdividedMesh->width * subdividedMesh->height ; i++ ) { - l += FilterMapDrawSurfIntoTree( subdividedMesh->verts[i].xyz, ds, tree->headnode ); - } - - free(subdividedMesh); - - return l; -} - - -/* -===================== -FilterMiscModelSurfIntoTree -===================== -*/ -int FilterMiscModelSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { - int i; - int l; - winding_t *w; - - l = 0; - for (i = 0; i < ds->numIndexes-2; i++) { - w = AllocWinding(3); - VectorCopy(ds->verts[ds->indexes[i]].xyz, w->p[0]); - VectorCopy(ds->verts[ds->indexes[i+1]].xyz, w->p[1]); - VectorCopy(ds->verts[ds->indexes[i+2]].xyz, w->p[2]); - w->numpoints = 3; - l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode ); - } - - // also use the old point filtering into the tree - for ( i = 0 ; i < ds->numVerts ; i++ ) { - l += FilterMapDrawSurfIntoTree( ds->verts[i].xyz, ds, tree->headnode ); - } - - return l; -} - -/* -===================== -FilterFlareSurfIntoTree -===================== -*/ -int FilterFlareSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { - return FilterMapDrawSurfIntoTree( ds->lightmapOrigin, ds, tree->headnode ); -} - - -//====================================================================== - -int c_stripSurfaces, c_fanSurfaces; - -/* -================== -IsTriangleDegenerate - -Returns qtrue if all three points are collinear or backwards -=================== -*/ -#define COLINEAR_AREA 10 -static qboolean IsTriangleDegenerate( drawVert_t *points, int a, int b, int c ) { - vec3_t v1, v2, v3; - float d; - - VectorSubtract( points[b].xyz, points[a].xyz, v1 ); - VectorSubtract( points[c].xyz, points[a].xyz, v2 ); - CrossProduct( v1, v2, v3 ); - d = VectorLength( v3 ); - - // assume all very small or backwards triangles will cause problems - if ( d < COLINEAR_AREA ) { - return qtrue; - } - - return qfalse; -} - -/* -=============== -SurfaceAsTriFan - -The surface can't be represented as a single tristrip without -leaving a degenerate triangle (and therefore a crack), so add -a point in the middle and create (points-1) triangles in fan order -=============== -*/ -static void SurfaceAsTriFan( dsurface_t *ds ) { - int i; - int colorSum[4]; - drawVert_t *mid, *v; - - // create a new point in the center of the face - if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { - Error( "MAX_MAP_DRAW_VERTS" ); - } - mid = &drawVerts[ numDrawVerts ]; - numDrawVerts++; - - colorSum[0] = colorSum[1] = colorSum[2] = colorSum[3] = 0; - - v = drawVerts + ds->firstVert; - for (i = 0 ; i < ds->numVerts ; i++, v++ ) { - VectorAdd( mid->xyz, v->xyz, mid->xyz ); - mid->st[0] += v->st[0]; - mid->st[1] += v->st[1]; - mid->lightmap[0] += v->lightmap[0]; - mid->lightmap[1] += v->lightmap[1]; - - colorSum[0] += v->color[0]; - colorSum[1] += v->color[1]; - colorSum[2] += v->color[2]; - colorSum[3] += v->color[3]; - } - - mid->xyz[0] /= ds->numVerts; - mid->xyz[1] /= ds->numVerts; - mid->xyz[2] /= ds->numVerts; - - mid->st[0] /= ds->numVerts; - mid->st[1] /= ds->numVerts; - - mid->lightmap[0] /= ds->numVerts; - mid->lightmap[1] /= ds->numVerts; - - mid->color[0] = colorSum[0] / ds->numVerts; - mid->color[1] = colorSum[1] / ds->numVerts; - mid->color[2] = colorSum[2] / ds->numVerts; - mid->color[3] = colorSum[3] / ds->numVerts; - - VectorCopy((drawVerts+ds->firstVert)->normal, mid->normal ); - - // fill in indices in trifan order - if ( numDrawIndexes + ds->numVerts*3 > MAX_MAP_DRAW_INDEXES ) { - Error( "MAX_MAP_DRAWINDEXES" ); - } - ds->firstIndex = numDrawIndexes; - ds->numIndexes = ds->numVerts*3; - - //FIXME - // should be: for ( i = 0 ; i < ds->numVerts ; i++ ) { - // set a break point and test this in a map - //for ( i = 0 ; i < ds->numVerts*3 ; i++ ) { - for ( i = 0 ; i < ds->numVerts ; i++ ) { - drawIndexes[numDrawIndexes++] = ds->numVerts; - drawIndexes[numDrawIndexes++] = i; - drawIndexes[numDrawIndexes++] = (i+1) % ds->numVerts; - } - - ds->numVerts++; -} - - -/* -================ -SurfaceAsTristrip - -Try to create indices that make (points-2) triangles in tristrip order -================ -*/ -#define MAX_INDICES 1024 -static void SurfaceAsTristrip( dsurface_t *ds ) { - int i; - int rotate; - int numIndices; - int ni; - int a, b, c; - int indices[MAX_INDICES]; - - // determine the triangle strip order - numIndices = ( ds->numVerts - 2 ) * 3; - if ( numIndices > MAX_INDICES ) { - Error( "MAX_INDICES exceeded for surface" ); - } - - // try all possible orderings of the points looking - // for a strip order that isn't degenerate - for ( rotate = 0 ; rotate < ds->numVerts ; rotate++ ) { - for ( ni = 0, i = 0 ; i < ds->numVerts - 2 - i ; i++ ) { - a = ( ds->numVerts - 1 - i + rotate ) % ds->numVerts; - b = ( i + rotate ) % ds->numVerts; - c = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts; - - if ( IsTriangleDegenerate( drawVerts + ds->firstVert, a, b, c ) ) { - break; - } - indices[ni++] = a; - indices[ni++] = b; - indices[ni++] = c; - - if ( i + 1 != ds->numVerts - 1 - i ) { - a = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts; - b = ( i + rotate ) % ds->numVerts; - c = ( i + 1 + rotate ) % ds->numVerts; - - if ( IsTriangleDegenerate( drawVerts + ds->firstVert, a, b, c ) ) { - break; - } - indices[ni++] = a; - indices[ni++] = b; - indices[ni++] = c; - } - } - if ( ni == numIndices ) { - break; // got it done without degenerate triangles - } - } - - // if any triangle in the strip is degenerate, - // render from a centered fan point instead - if ( ni < numIndices ) { - c_fanSurfaces++; - SurfaceAsTriFan( ds ); - return; - } - - // a normal tristrip - c_stripSurfaces++; - - if ( numDrawIndexes + ni > MAX_MAP_DRAW_INDEXES ) { - Error( "MAX_MAP_DRAW_INDEXES" ); - } - ds->firstIndex = numDrawIndexes; - ds->numIndexes = ni; - - memcpy( drawIndexes + numDrawIndexes, indices, ni * sizeof(int) ); - numDrawIndexes += ni; -} - -/* -=============== -EmitPlanarSurf -=============== -*/ -void EmitPlanarSurf( mapDrawSurface_t *ds ) { - int j; - dsurface_t *out; - drawVert_t *outv; - - if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { - Error( "MAX_MAP_DRAW_SURFS" ); - } - out = &drawSurfaces[ numDrawSurfaces ]; - numDrawSurfaces++; - - out->surfaceType = MST_PLANAR; - out->shaderNum = EmitShader( ds->shaderInfo->shader ); - out->firstVert = numDrawVerts; - out->numVerts = ds->numVerts; - out->fogNum = ds->fogNum; - out->lightmapNum = ds->lightmapNum; - out->lightmapX = ds->lightmapX; - out->lightmapY = ds->lightmapY; - out->lightmapWidth = ds->lightmapWidth; - out->lightmapHeight = ds->lightmapHeight; - - VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); - VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); - VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] ); - VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); - - for ( j = 0 ; j < ds->numVerts ; j++ ) { - if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { - Error( "MAX_MAP_DRAW_VERTS" ); - } - outv = &drawVerts[ numDrawVerts ]; - numDrawVerts++; - memcpy( outv, &ds->verts[ j ], sizeof( *outv ) ); - outv->color[0] = 255; - outv->color[1] = 255; - outv->color[2] = 255; - outv->color[3] = 255; - } - - // create the indexes - SurfaceAsTristrip( out ); -} - - -/* -=============== -EmitPatchSurf -=============== -*/ -void EmitPatchSurf( mapDrawSurface_t *ds ) { - int j; - dsurface_t *out; - drawVert_t *outv; - - if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { - Error( "MAX_MAP_DRAW_SURFS" ); - } - out = &drawSurfaces[ numDrawSurfaces ]; - numDrawSurfaces++; - - out->surfaceType = MST_PATCH; - out->shaderNum = EmitShader( ds->shaderInfo->shader ); - out->firstVert = numDrawVerts; - out->numVerts = ds->numVerts; - out->firstIndex = numDrawIndexes; - out->numIndexes = ds->numIndexes; - out->patchWidth = ds->patchWidth; - out->patchHeight = ds->patchHeight; - out->fogNum = ds->fogNum; - out->lightmapNum = ds->lightmapNum; - out->lightmapX = ds->lightmapX; - out->lightmapY = ds->lightmapY; - out->lightmapWidth = ds->lightmapWidth; - out->lightmapHeight = ds->lightmapHeight; - - VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); - VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); - VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] ); - VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); - - for ( j = 0 ; j < ds->numVerts ; j++ ) { - if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { - Error( "MAX_MAP_DRAW_VERTS" ); - } - outv = &drawVerts[ numDrawVerts ]; - numDrawVerts++; - memcpy( outv, &ds->verts[ j ], sizeof( *outv ) ); - outv->color[0] = 255; - outv->color[1] = 255; - outv->color[2] = 255; - outv->color[3] = 255; - } - - for ( j = 0 ; j < ds->numIndexes ; j++ ) { - if ( numDrawIndexes == MAX_MAP_DRAW_INDEXES ) { - Error( "MAX_MAP_DRAW_INDEXES" ); - } - drawIndexes[ numDrawIndexes ] = ds->indexes[ j ]; - numDrawIndexes++; - } -} - -/* -=============== -EmitFlareSurf -=============== -*/ -void EmitFlareSurf( mapDrawSurface_t *ds ) { - dsurface_t *out; - - if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { - Error( "MAX_MAP_DRAW_SURFS" ); - } - out = &drawSurfaces[ numDrawSurfaces ]; - numDrawSurfaces++; - - out->surfaceType = MST_FLARE; - out->shaderNum = EmitShader( ds->shaderInfo->shader ); - out->fogNum = ds->fogNum; - - VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); - VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); // color - VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); -} - - -/* -=============== -EmitModelSurf -=============== -*/ -void EmitModelSurf( mapDrawSurface_t *ds ) { - int j; - dsurface_t *out; - drawVert_t *outv; - - if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { - Error( "MAX_MAP_DRAW_SURFS" ); - } - out = &drawSurfaces[ numDrawSurfaces ]; - numDrawSurfaces++; - - out->surfaceType = MST_TRIANGLE_SOUP; - out->shaderNum = EmitShader( ds->shaderInfo->shader ); - out->firstVert = numDrawVerts; - out->numVerts = ds->numVerts; - out->firstIndex = numDrawIndexes; - out->numIndexes = ds->numIndexes; - out->patchWidth = ds->patchWidth; - out->patchHeight = ds->patchHeight; - out->fogNum = ds->fogNum; - out->lightmapNum = ds->lightmapNum; - out->lightmapX = ds->lightmapX; - out->lightmapY = ds->lightmapY; - out->lightmapWidth = ds->lightmapWidth; - out->lightmapHeight = ds->lightmapHeight; - - VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); - VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); - VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] ); - VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); - - for ( j = 0 ; j < ds->numVerts ; j++ ) { - if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { - Error( "MAX_MAP_DRAW_VERTS" ); - } - outv = &drawVerts[ numDrawVerts ]; - numDrawVerts++; - memcpy( outv, &ds->verts[ j ], sizeof( *outv ) ); - outv->color[0] = 255; - outv->color[1] = 255; - outv->color[2] = 255; - } - - for ( j = 0 ; j < ds->numIndexes ; j++ ) { - if ( numDrawIndexes == MAX_MAP_DRAW_INDEXES ) { - Error( "MAX_MAP_DRAW_INDEXES" ); - } - drawIndexes[ numDrawIndexes ] = ds->indexes[ j ]; - numDrawIndexes++; - } -} - -//====================================================================== - -/* -================== -CreateFlareSurface - -Light flares from surface lights become -================== -*/ -void CreateFlareSurface( mapDrawSurface_t *faceDs ) { - mapDrawSurface_t *ds; - int i; - - ds = AllocDrawSurf(); - - if ( faceDs->shaderInfo->flareShader[0] ) { - ds->shaderInfo = ShaderInfoForShader( faceDs->shaderInfo->flareShader ); - } else { - ds->shaderInfo = ShaderInfoForShader( "flareshader" ); - } - ds->flareSurface = qtrue; - VectorCopy( faceDs->lightmapVecs[2], ds->lightmapVecs[2] ); - - // find midpoint - VectorClear( ds->lightmapOrigin ); - for ( i = 0 ; i < faceDs->numVerts ; i++ ) { - VectorAdd( ds->lightmapOrigin, faceDs->verts[i].xyz, ds->lightmapOrigin ); - } - VectorScale( ds->lightmapOrigin, 1.0/faceDs->numVerts, ds->lightmapOrigin ); - - VectorMA( ds->lightmapOrigin, 2, ds->lightmapVecs[2], ds->lightmapOrigin ); - - VectorCopy( faceDs->shaderInfo->color, ds->lightmapVecs[0] ); - - // FIXME: fog -} - -/* -===================== -FilterDrawsurfsIntoTree - -Upon completion, all drawsurfs that actually generate a reference -will have been emited to the bspfile arrays, and the references -will have valid final indexes -===================== -*/ -void FilterDrawsurfsIntoTree( entity_t *e, tree_t *tree ) { - int i; - mapDrawSurface_t *ds; - int refs; - int c_surfs, c_refs; - - qprintf( "----- FilterDrawsurfsIntoTree -----\n"); - - c_surfs = 0; - c_refs = 0; - for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) { - ds = &mapDrawSurfs[i]; - - if ( !ds->numVerts && !ds->flareSurface ) { - continue; - } - if ( ds->miscModel ) { - refs = FilterMiscModelSurfIntoTree( ds, tree ); - EmitModelSurf( ds ); - } else if ( ds->patch ) { - refs = FilterPatchSurfIntoTree( ds, tree ); - EmitPatchSurf( ds ); - } else if ( ds->flareSurface ) { - refs = FilterFlareSurfIntoTree( ds, tree ); - EmitFlareSurf( ds ); - } else { - refs = FilterFaceIntoTree( ds, tree ); -// if ( ds->shaderInfo->value >= 1000 ) { // ds->shaderInfo->flareShader[0] ) { - if ( ds->shaderInfo->flareShader[0] ) { - CreateFlareSurface( ds ); - } - EmitPlanarSurf( ds ); - } - if ( refs > 0 ) { - c_surfs++; - c_refs += refs; - } - } - qprintf( "%5i emited drawsurfs\n", c_surfs ); - qprintf( "%5i references\n", c_refs ); - qprintf( "%5i stripfaces\n", c_stripSurfaces ); - qprintf( "%5i fanfaces\n", c_fanSurfaces ); -} - - - + +#include "qbsp.h" + + +mapDrawSurface_t mapDrawSurfs[MAX_MAP_DRAW_SURFS]; +int numMapDrawSurfs; + +/* +============================================================================= + +DRAWSURF CONSTRUCTION + +============================================================================= +*/ + +/* +================= +AllocDrawSurf +================= +*/ +mapDrawSurface_t *AllocDrawSurf( void ) { + mapDrawSurface_t *ds; + + if ( numMapDrawSurfs >= MAX_MAP_DRAW_SURFS ) { + Error( "MAX_MAP_DRAW_SURFS"); + } + ds = &mapDrawSurfs[ numMapDrawSurfs ]; + numMapDrawSurfs++; + + return ds; +} + +/* +================= +DrawSurfaceForSide +================= +*/ +#define SNAP_FLOAT_TO_INT 8 +#define SNAP_INT_TO_FLOAT (1.0/SNAP_FLOAT_TO_INT) + +mapDrawSurface_t *DrawSurfaceForSide( bspbrush_t *b, side_t *s, winding_t *w ) { + mapDrawSurface_t *ds; + int i, j; + shaderInfo_t *si; + drawVert_t *dv; + float mins[2], maxs[2]; + + // brush primitive : + // axis base + vec3_t texX,texY; + vec_t x,y; + + if ( w->numpoints > 64 ) { + Error( "DrawSurfaceForSide: w->numpoints = %i", w->numpoints ); + } + + si = s->shaderInfo; + + ds = AllocDrawSurf(); + + ds->shaderInfo = si; + ds->mapBrush = b; + ds->side = s; + ds->fogNum = -1; + ds->numVerts = w->numpoints; + ds->verts = malloc( ds->numVerts * sizeof( *ds->verts ) ); + memset( ds->verts, 0, ds->numVerts * sizeof( *ds->verts ) ); + + mins[0] = mins[1] = 99999; + maxs[0] = maxs[1] = -99999; + + // compute s/t coordinates from brush primitive texture matrix + // compute axis base + ComputeAxisBase( mapplanes[s->planenum].normal, texX, texY ); + + for ( j = 0 ; j < w->numpoints ; j++ ) { + dv = ds->verts + j; + + // round the xyz to a given precision + for ( i = 0 ; i < 3 ; i++ ) { + dv->xyz[i] = SNAP_INT_TO_FLOAT * floor( w->p[j][i] * SNAP_FLOAT_TO_INT + 0.5 ); + } + + if (g_bBrushPrimit==BPRIMIT_OLDBRUSHES) + { + // calculate texture s/t + dv->st[0] = s->vecs[0][3] + DotProduct( s->vecs[0], dv->xyz ); + dv->st[1] = s->vecs[1][3] + DotProduct( s->vecs[1], dv->xyz ); + dv->st[0] /= si->width; + dv->st[1] /= si->height; + } + else + { + // calculate texture s/t from brush primitive texture matrix + x = DotProduct( dv->xyz, texX ); + y = DotProduct( dv->xyz, texY ); + dv->st[0]=s->texMat[0][0]*x+s->texMat[0][1]*y+s->texMat[0][2]; + dv->st[1]=s->texMat[1][0]*x+s->texMat[1][1]*y+s->texMat[1][2]; + } + + for ( i = 0 ; i < 2 ; i++ ) { + if ( dv->st[i] < mins[i] ) { + mins[i] = dv->st[i]; + } + if ( dv->st[i] > maxs[i] ) { + maxs[i] = dv->st[i]; + } + } + + // copy normal + VectorCopy ( mapplanes[s->planenum].normal, dv->normal ); + } + + // adjust the texture coordinates to be as close to 0 as possible + if ( !si->globalTexture ) { + mins[0] = floor( mins[0] ); + mins[1] = floor( mins[1] ); + for ( i = 0 ; i < w->numpoints ; i++ ) { + dv = ds->verts + i; + dv->st[0] -= mins[0]; + dv->st[1] -= mins[1]; + } + } + + return ds; +} + + +//========================================================================= + + + + +typedef struct { + int planenum; + shaderInfo_t *shaderInfo; + int count; +} sideRef_t; + +#define MAX_SIDE_REFS MAX_MAP_PLANES + +sideRef_t sideRefs[MAX_SIDE_REFS]; +int numSideRefs; + +void AddSideRef( side_t *side ) { + int i; + + for ( i = 0 ; i < numSideRefs ; i++ ) { + if ( side->planenum == sideRefs[i].planenum + && side->shaderInfo == sideRefs[i].shaderInfo ) { + sideRefs[i].count++; + return; + } + } + + if ( numSideRefs == MAX_SIDE_REFS ) { + Error( "MAX_SIDE_REFS" ); + } + + sideRefs[i].planenum = side->planenum; + sideRefs[i].shaderInfo = side->shaderInfo; + sideRefs[i].count++; + numSideRefs++; +} + + +/* +===================== +MergeSides + +===================== +*/ +void MergeSides( entity_t *e, tree_t *tree ) { + int i; + + qprintf( "----- MergeSides -----\n"); + + for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) { +// AddSideRef( side ); + } + + qprintf( "%5i siderefs\n", numSideRefs ); +} + +//===================================================================== + +/* +=================== +SubdivideDrawSurf +=================== +*/ +void SubdivideDrawSurf( mapDrawSurface_t *ds, winding_t *w, float subdivisions ) { + int i; + int axis; + vec3_t bounds[2]; + const float epsilon = 0.1; + int subFloor, subCeil; + winding_t *frontWinding, *backWinding; + mapDrawSurface_t *newds; + + if ( !w ) { + return; + } + if ( w->numpoints < 3 ) { + Error( "SubdivideDrawSurf: Bad w->numpoints" ); + } + + ClearBounds( bounds[0], bounds[1] ); + for ( i = 0 ; i < w->numpoints ; i++ ) { + AddPointToBounds( w->p[i], bounds[0], bounds[1] ); + } + + for ( axis = 0 ; axis < 3 ; axis++ ) { + vec3_t planePoint = { 0, 0, 0 }; + vec3_t planeNormal = { 0, 0, 0 }; + float d; + + subFloor = floor( bounds[0][axis] / subdivisions ) * subdivisions; + subCeil = ceil( bounds[1][axis] / subdivisions ) * subdivisions; + + planePoint[axis] = subFloor + subdivisions; + planeNormal[axis] = -1; + + d = DotProduct( planePoint, planeNormal ); + + // subdivide if necessary + if ( subCeil - subFloor > subdivisions ) { + // gotta clip polygon into two polygons + ClipWindingEpsilon( w, planeNormal, d, epsilon, &frontWinding, &backWinding ); + + // the clip may not produce two polygons if it was epsilon close + if ( !frontWinding ) { + w = backWinding; + } else if ( !backWinding ) { + w = frontWinding; + } else { + SubdivideDrawSurf( ds, frontWinding, subdivisions ); + SubdivideDrawSurf( ds, backWinding, subdivisions ); + + return; + } + } + } + + // emit this polygon + newds = DrawSurfaceForSide( ds->mapBrush, ds->side, w ); + newds->fogNum = ds->fogNum; +} + + +/* +===================== +SubdivideDrawSurfs + +Chop up surfaces that have subdivision attributes +===================== +*/ +void SubdivideDrawSurfs( entity_t *e, tree_t *tree ) { + int i; + mapDrawSurface_t *ds; + int numBaseDrawSurfs; + winding_t *w; + float subdivision; + shaderInfo_t *si; + + qprintf( "----- SubdivideDrawSurfs -----\n"); + numBaseDrawSurfs = numMapDrawSurfs; + for ( i = e->firstDrawSurf ; i < numBaseDrawSurfs ; i++ ) { + ds = &mapDrawSurfs[i]; + + // only subdivide brush sides, not patches or misc_models + if ( !ds->side ) { + continue; + } + + // check subdivision for shader + si = ds->side->shaderInfo; + if ( !si ) { + continue; + } + + if (ds->shaderInfo->autosprite || si->autosprite) { + continue; + } + + subdivision = si->subdivisions; + if ( !subdivision ) { + continue; + } + + w = WindingFromDrawSurf( ds ); + ds->numVerts = 0; // remove this reference + SubdivideDrawSurf( ds, w, subdivision ); + } + +} + + +//=================================================================================== + +/* +==================== +ClipSideIntoTree_r + +Adds non-opaque leaf fragments to the convex hull +==================== +*/ +void ClipSideIntoTree_r( winding_t *w, side_t *side, node_t *node ) { + plane_t *plane; + winding_t *front, *back; + + if ( !w ) { + return; + } + + if ( node->planenum != PLANENUM_LEAF ) { + if ( side->planenum == node->planenum ) { + ClipSideIntoTree_r( w, side, node->children[0] ); + return; + } + if ( side->planenum == ( node->planenum ^ 1) ) { + ClipSideIntoTree_r( w, side, node->children[1] ); + return; + } + + plane = &mapplanes[ node->planenum ]; + ClipWindingEpsilon ( w, plane->normal, plane->dist, + ON_EPSILON, &front, &back ); + FreeWinding( w ); + + ClipSideIntoTree_r( front, side, node->children[0] ); + ClipSideIntoTree_r( back, side, node->children[1] ); + + return; + } + + // if opaque leaf, don't add + if ( !node->opaque ) { + AddWindingToConvexHull( w, &side->visibleHull, mapplanes[ side->planenum ].normal ); + } + + FreeWinding( w ); + return; +} + + +/* +===================== +ClipSidesIntoTree + +Creates side->visibleHull for all visible sides + +The drawsurf for a side will consist of the convex hull of +all points in non-opaque clusters, which allows overlaps +to be trimmed off automatically. +===================== +*/ +void ClipSidesIntoTree( entity_t *e, tree_t *tree ) { + bspbrush_t *b; + int i; + winding_t *w; + side_t *side, *newSide; + shaderInfo_t *si; + + qprintf( "----- ClipSidesIntoTree -----\n"); + + for ( b = e->brushes ; b ; b = b->next ) { + for ( i = 0 ; i < b->numsides ; i++ ) { + side = &b->sides[i]; + if ( !side->winding) { + continue; + } + w = CopyWinding( side->winding ); + side->visibleHull = NULL; + ClipSideIntoTree_r( w, side, tree->headnode ); + + w = side->visibleHull; + if ( !w ) { + continue; + } + si = side->shaderInfo; + if ( !si ) { + continue; + } + // don't create faces for non-visible sides + if ( si->surfaceFlags & SURF_NODRAW ) { + continue; + } + + // always use the original quad winding for auto sprites + if ( side->shaderInfo->autosprite ) { + w = side->winding; + } + // + if ( side->bevel ) { + Error( "monkey tried to create draw surface for brush bevel" ); + } + // save this winding as a visible surface + DrawSurfaceForSide( b, side, w ); + + // make a back side for it if needed + if ( !(si->contents & CONTENTS_FOG) ) { + continue; + } + + // duplicate the up-facing side + w = ReverseWinding( w ); + + newSide = malloc( sizeof( *side ) ); + *newSide = *side; + newSide->visibleHull = w; + newSide->planenum ^= 1; + + // save this winding as a visible surface + DrawSurfaceForSide( b, newSide, w ); + + } + } +} + +/* +=================================================================================== + + FILTER REFERENCES DOWN THE TREE + +=================================================================================== +*/ + +/* +==================== +FilterDrawSurfIntoTree + +Place a reference to the given drawsurf in every leaf it contacts +We assume that the point mesh aproximation to the curve will get a +reference into all the leafs we need. +==================== +*/ +int FilterMapDrawSurfIntoTree( vec3_t point, mapDrawSurface_t *ds, node_t *node ) { + drawSurfRef_t *dsr; + float d; + plane_t *plane; + int c; + + if ( node->planenum != PLANENUM_LEAF ) { + plane = &mapplanes[ node->planenum ]; + d = DotProduct( point, plane->normal ) - plane->dist; + c = 0; + if ( d >= -ON_EPSILON ) { + c += FilterMapDrawSurfIntoTree( point, ds, node->children[0] ); + } + if ( d <= ON_EPSILON ) { + c += FilterMapDrawSurfIntoTree( point, ds, node->children[1] ); + } + return c; + } + + // if opaque leaf, don't add + if ( node->opaque ) { + return 0; + } + + // add the drawsurf if it hasn't been already + for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) { + if ( dsr->outputNumber == numDrawSurfaces ) { + return 0; // already referenced + } + } + + dsr = malloc( sizeof( *dsr ) ); + dsr->outputNumber = numDrawSurfaces; + dsr->nextRef = node->drawSurfReferences; + node->drawSurfReferences = dsr; + return 1; +} + +/* +==================== +FilterDrawSurfIntoTree_r + +Place a reference to the given drawsurf in every leaf it is in +==================== +*/ +int FilterMapDrawSurfIntoTree_r( winding_t *w, mapDrawSurface_t *ds, node_t *node ) { + drawSurfRef_t *dsr; + plane_t *plane; + int total; + winding_t *front, *back; + + if ( node->planenum != PLANENUM_LEAF ) { + plane = &mapplanes[ node->planenum ]; + ClipWindingEpsilon ( w, plane->normal, plane->dist, + ON_EPSILON, &front, &back ); + + total = 0; + if ( front ) { + total += FilterMapDrawSurfIntoTree_r( front, ds, node->children[0] ); + } + if ( back ) { + total += FilterMapDrawSurfIntoTree_r( back, ds, node->children[1] ); + } + + FreeWinding( w ); + return total; + } + + // if opaque leaf, don't add + if ( node->opaque ) { + return 0; + } + + // add the drawsurf if it hasn't been already + for ( dsr = node->drawSurfReferences ; dsr ; dsr = dsr->nextRef ) { + if ( dsr->outputNumber == numDrawSurfaces ) { + return 0; // already referenced + } + } + + dsr = malloc( sizeof( *dsr ) ); + dsr->outputNumber = numDrawSurfaces; + dsr->nextRef = node->drawSurfReferences; + node->drawSurfReferences = dsr; + return 1; +} + +/* +==================== +FilterSideIntoTree_r + +Place a reference to the given drawsurf in every leaf it contacts +==================== +*/ +int FilterSideIntoTree_r( winding_t *w, side_t *side, mapDrawSurface_t *ds, node_t *node ) { + drawSurfRef_t *dsr; + plane_t *plane; + winding_t *front, *back; + int total; + + if ( !w ) { + return 0; + } + + if ( node->planenum != PLANENUM_LEAF ) { + if ( side->planenum == node->planenum ) { + return FilterSideIntoTree_r( w, side, ds, node->children[0] ); + } + if ( side->planenum == ( node->planenum ^ 1) ) { + return FilterSideIntoTree_r( w, side, ds, node->children[1] ); + } + + plane = &mapplanes[ node->planenum ]; + ClipWindingEpsilon ( w, plane->normal, plane->dist, + ON_EPSILON, &front, &back ); + + total = FilterSideIntoTree_r( front, side, ds, node->children[0] ); + total += FilterSideIntoTree_r( back, side, ds, node->children[1] ); + + FreeWinding( w ); + return total; + } + + // if opaque leaf, don't add + if ( node->opaque ) { + return 0; + } + + dsr = malloc( sizeof( *dsr ) ); + dsr->outputNumber = numDrawSurfaces; + dsr->nextRef = node->drawSurfReferences; + node->drawSurfReferences = dsr; + + FreeWinding( w ); + return 1; +} + + +/* +===================== +FilterFaceIntoTree +===================== +*/ +int FilterFaceIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { + int l; + winding_t *w; + + w = WindingFromDrawSurf( ds ); + l = FilterSideIntoTree_r( w, ds->side, ds, tree->headnode ); + + return l; +} + + + +/* +===================== +FilterPatchSurfIntoTree +===================== +*/ +#define SUBDIVISION_LIMIT 8.0 +int FilterPatchSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { + int i, j; + int l; + mesh_t baseMesh, *subdividedMesh; + winding_t *w; + + baseMesh.width = ds->patchWidth; + baseMesh.height = ds->patchHeight; + baseMesh.verts = ds->verts; + subdividedMesh = SubdivideMesh( baseMesh, SUBDIVISION_LIMIT, 32 ); + + l = 0; + for (i = 0; i < subdividedMesh->width-1; i++) { + for (j = 0; j < subdividedMesh->height-1; j++) { + w = AllocWinding(3); + VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i].xyz, w->p[0]); + VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i + 1].xyz, w->p[1]); + VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i].xyz, w->p[2]); + w->numpoints = 3; + l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode ); + w = AllocWinding(3); + VectorCopy(subdividedMesh->verts[j * subdividedMesh->width + i + 1].xyz, w->p[0]); + VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i + 1].xyz, w->p[1]); + VectorCopy(subdividedMesh->verts[(j+1) * subdividedMesh->width + i].xyz, w->p[2]); + w->numpoints = 3; + l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode ); + } + } + + // also use the old point filtering into the tree + for ( i = 0 ; i < subdividedMesh->width * subdividedMesh->height ; i++ ) { + l += FilterMapDrawSurfIntoTree( subdividedMesh->verts[i].xyz, ds, tree->headnode ); + } + + free(subdividedMesh); + + return l; +} + + +/* +===================== +FilterMiscModelSurfIntoTree +===================== +*/ +int FilterMiscModelSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { + int i; + int l; + winding_t *w; + + l = 0; + for (i = 0; i < ds->numIndexes-2; i++) { + w = AllocWinding(3); + VectorCopy(ds->verts[ds->indexes[i]].xyz, w->p[0]); + VectorCopy(ds->verts[ds->indexes[i+1]].xyz, w->p[1]); + VectorCopy(ds->verts[ds->indexes[i+2]].xyz, w->p[2]); + w->numpoints = 3; + l += FilterMapDrawSurfIntoTree_r( w, ds, tree->headnode ); + } + + // also use the old point filtering into the tree + for ( i = 0 ; i < ds->numVerts ; i++ ) { + l += FilterMapDrawSurfIntoTree( ds->verts[i].xyz, ds, tree->headnode ); + } + + return l; +} + +/* +===================== +FilterFlareSurfIntoTree +===================== +*/ +int FilterFlareSurfIntoTree( mapDrawSurface_t *ds, tree_t *tree ) { + return FilterMapDrawSurfIntoTree( ds->lightmapOrigin, ds, tree->headnode ); +} + + +//====================================================================== + +int c_stripSurfaces, c_fanSurfaces; + +/* +================== +IsTriangleDegenerate + +Returns qtrue if all three points are collinear or backwards +=================== +*/ +#define COLINEAR_AREA 10 +static qboolean IsTriangleDegenerate( drawVert_t *points, int a, int b, int c ) { + vec3_t v1, v2, v3; + float d; + + VectorSubtract( points[b].xyz, points[a].xyz, v1 ); + VectorSubtract( points[c].xyz, points[a].xyz, v2 ); + CrossProduct( v1, v2, v3 ); + d = VectorLength( v3 ); + + // assume all very small or backwards triangles will cause problems + if ( d < COLINEAR_AREA ) { + return qtrue; + } + + return qfalse; +} + +/* +=============== +SurfaceAsTriFan + +The surface can't be represented as a single tristrip without +leaving a degenerate triangle (and therefore a crack), so add +a point in the middle and create (points-1) triangles in fan order +=============== +*/ +static void SurfaceAsTriFan( dsurface_t *ds ) { + int i; + int colorSum[4]; + drawVert_t *mid, *v; + + // create a new point in the center of the face + if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { + Error( "MAX_MAP_DRAW_VERTS" ); + } + mid = &drawVerts[ numDrawVerts ]; + numDrawVerts++; + + colorSum[0] = colorSum[1] = colorSum[2] = colorSum[3] = 0; + + v = drawVerts + ds->firstVert; + for (i = 0 ; i < ds->numVerts ; i++, v++ ) { + VectorAdd( mid->xyz, v->xyz, mid->xyz ); + mid->st[0] += v->st[0]; + mid->st[1] += v->st[1]; + mid->lightmap[0] += v->lightmap[0]; + mid->lightmap[1] += v->lightmap[1]; + + colorSum[0] += v->color[0]; + colorSum[1] += v->color[1]; + colorSum[2] += v->color[2]; + colorSum[3] += v->color[3]; + } + + mid->xyz[0] /= ds->numVerts; + mid->xyz[1] /= ds->numVerts; + mid->xyz[2] /= ds->numVerts; + + mid->st[0] /= ds->numVerts; + mid->st[1] /= ds->numVerts; + + mid->lightmap[0] /= ds->numVerts; + mid->lightmap[1] /= ds->numVerts; + + mid->color[0] = colorSum[0] / ds->numVerts; + mid->color[1] = colorSum[1] / ds->numVerts; + mid->color[2] = colorSum[2] / ds->numVerts; + mid->color[3] = colorSum[3] / ds->numVerts; + + VectorCopy((drawVerts+ds->firstVert)->normal, mid->normal ); + + // fill in indices in trifan order + if ( numDrawIndexes + ds->numVerts*3 > MAX_MAP_DRAW_INDEXES ) { + Error( "MAX_MAP_DRAWINDEXES" ); + } + ds->firstIndex = numDrawIndexes; + ds->numIndexes = ds->numVerts*3; + + //FIXME + // should be: for ( i = 0 ; i < ds->numVerts ; i++ ) { + // set a break point and test this in a map + //for ( i = 0 ; i < ds->numVerts*3 ; i++ ) { + for ( i = 0 ; i < ds->numVerts ; i++ ) { + drawIndexes[numDrawIndexes++] = ds->numVerts; + drawIndexes[numDrawIndexes++] = i; + drawIndexes[numDrawIndexes++] = (i+1) % ds->numVerts; + } + + ds->numVerts++; +} + + +/* +================ +SurfaceAsTristrip + +Try to create indices that make (points-2) triangles in tristrip order +================ +*/ +#define MAX_INDICES 1024 +static void SurfaceAsTristrip( dsurface_t *ds ) { + int i; + int rotate; + int numIndices; + int ni; + int a, b, c; + int indices[MAX_INDICES]; + + // determine the triangle strip order + numIndices = ( ds->numVerts - 2 ) * 3; + if ( numIndices > MAX_INDICES ) { + Error( "MAX_INDICES exceeded for surface" ); + } + + // try all possible orderings of the points looking + // for a strip order that isn't degenerate + for ( rotate = 0 ; rotate < ds->numVerts ; rotate++ ) { + for ( ni = 0, i = 0 ; i < ds->numVerts - 2 - i ; i++ ) { + a = ( ds->numVerts - 1 - i + rotate ) % ds->numVerts; + b = ( i + rotate ) % ds->numVerts; + c = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts; + + if ( IsTriangleDegenerate( drawVerts + ds->firstVert, a, b, c ) ) { + break; + } + indices[ni++] = a; + indices[ni++] = b; + indices[ni++] = c; + + if ( i + 1 != ds->numVerts - 1 - i ) { + a = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts; + b = ( i + rotate ) % ds->numVerts; + c = ( i + 1 + rotate ) % ds->numVerts; + + if ( IsTriangleDegenerate( drawVerts + ds->firstVert, a, b, c ) ) { + break; + } + indices[ni++] = a; + indices[ni++] = b; + indices[ni++] = c; + } + } + if ( ni == numIndices ) { + break; // got it done without degenerate triangles + } + } + + // if any triangle in the strip is degenerate, + // render from a centered fan point instead + if ( ni < numIndices ) { + c_fanSurfaces++; + SurfaceAsTriFan( ds ); + return; + } + + // a normal tristrip + c_stripSurfaces++; + + if ( numDrawIndexes + ni > MAX_MAP_DRAW_INDEXES ) { + Error( "MAX_MAP_DRAW_INDEXES" ); + } + ds->firstIndex = numDrawIndexes; + ds->numIndexes = ni; + + memcpy( drawIndexes + numDrawIndexes, indices, ni * sizeof(int) ); + numDrawIndexes += ni; +} + +/* +=============== +EmitPlanarSurf +=============== +*/ +void EmitPlanarSurf( mapDrawSurface_t *ds ) { + int j; + dsurface_t *out; + drawVert_t *outv; + + if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { + Error( "MAX_MAP_DRAW_SURFS" ); + } + out = &drawSurfaces[ numDrawSurfaces ]; + numDrawSurfaces++; + + out->surfaceType = MST_PLANAR; + out->shaderNum = EmitShader( ds->shaderInfo->shader ); + out->firstVert = numDrawVerts; + out->numVerts = ds->numVerts; + out->fogNum = ds->fogNum; + out->lightmapNum = ds->lightmapNum; + out->lightmapX = ds->lightmapX; + out->lightmapY = ds->lightmapY; + out->lightmapWidth = ds->lightmapWidth; + out->lightmapHeight = ds->lightmapHeight; + + VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); + VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); + VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] ); + VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); + + for ( j = 0 ; j < ds->numVerts ; j++ ) { + if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { + Error( "MAX_MAP_DRAW_VERTS" ); + } + outv = &drawVerts[ numDrawVerts ]; + numDrawVerts++; + memcpy( outv, &ds->verts[ j ], sizeof( *outv ) ); + outv->color[0] = 255; + outv->color[1] = 255; + outv->color[2] = 255; + outv->color[3] = 255; + } + + // create the indexes + SurfaceAsTristrip( out ); +} + + +/* +=============== +EmitPatchSurf +=============== +*/ +void EmitPatchSurf( mapDrawSurface_t *ds ) { + int j; + dsurface_t *out; + drawVert_t *outv; + + if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { + Error( "MAX_MAP_DRAW_SURFS" ); + } + out = &drawSurfaces[ numDrawSurfaces ]; + numDrawSurfaces++; + + out->surfaceType = MST_PATCH; + out->shaderNum = EmitShader( ds->shaderInfo->shader ); + out->firstVert = numDrawVerts; + out->numVerts = ds->numVerts; + out->firstIndex = numDrawIndexes; + out->numIndexes = ds->numIndexes; + out->patchWidth = ds->patchWidth; + out->patchHeight = ds->patchHeight; + out->fogNum = ds->fogNum; + out->lightmapNum = ds->lightmapNum; + out->lightmapX = ds->lightmapX; + out->lightmapY = ds->lightmapY; + out->lightmapWidth = ds->lightmapWidth; + out->lightmapHeight = ds->lightmapHeight; + + VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); + VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); + VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] ); + VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); + + for ( j = 0 ; j < ds->numVerts ; j++ ) { + if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { + Error( "MAX_MAP_DRAW_VERTS" ); + } + outv = &drawVerts[ numDrawVerts ]; + numDrawVerts++; + memcpy( outv, &ds->verts[ j ], sizeof( *outv ) ); + outv->color[0] = 255; + outv->color[1] = 255; + outv->color[2] = 255; + outv->color[3] = 255; + } + + for ( j = 0 ; j < ds->numIndexes ; j++ ) { + if ( numDrawIndexes == MAX_MAP_DRAW_INDEXES ) { + Error( "MAX_MAP_DRAW_INDEXES" ); + } + drawIndexes[ numDrawIndexes ] = ds->indexes[ j ]; + numDrawIndexes++; + } +} + +/* +=============== +EmitFlareSurf +=============== +*/ +void EmitFlareSurf( mapDrawSurface_t *ds ) { + dsurface_t *out; + + if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { + Error( "MAX_MAP_DRAW_SURFS" ); + } + out = &drawSurfaces[ numDrawSurfaces ]; + numDrawSurfaces++; + + out->surfaceType = MST_FLARE; + out->shaderNum = EmitShader( ds->shaderInfo->shader ); + out->fogNum = ds->fogNum; + + VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); + VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); // color + VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); +} + + +/* +=============== +EmitModelSurf +=============== +*/ +void EmitModelSurf( mapDrawSurface_t *ds ) { + int j; + dsurface_t *out; + drawVert_t *outv; + + if ( numDrawSurfaces == MAX_MAP_DRAW_SURFS ) { + Error( "MAX_MAP_DRAW_SURFS" ); + } + out = &drawSurfaces[ numDrawSurfaces ]; + numDrawSurfaces++; + + out->surfaceType = MST_TRIANGLE_SOUP; + out->shaderNum = EmitShader( ds->shaderInfo->shader ); + out->firstVert = numDrawVerts; + out->numVerts = ds->numVerts; + out->firstIndex = numDrawIndexes; + out->numIndexes = ds->numIndexes; + out->patchWidth = ds->patchWidth; + out->patchHeight = ds->patchHeight; + out->fogNum = ds->fogNum; + out->lightmapNum = ds->lightmapNum; + out->lightmapX = ds->lightmapX; + out->lightmapY = ds->lightmapY; + out->lightmapWidth = ds->lightmapWidth; + out->lightmapHeight = ds->lightmapHeight; + + VectorCopy( ds->lightmapOrigin, out->lightmapOrigin ); + VectorCopy( ds->lightmapVecs[0], out->lightmapVecs[0] ); + VectorCopy( ds->lightmapVecs[1], out->lightmapVecs[1] ); + VectorCopy( ds->lightmapVecs[2], out->lightmapVecs[2] ); + + for ( j = 0 ; j < ds->numVerts ; j++ ) { + if ( numDrawVerts == MAX_MAP_DRAW_VERTS ) { + Error( "MAX_MAP_DRAW_VERTS" ); + } + outv = &drawVerts[ numDrawVerts ]; + numDrawVerts++; + memcpy( outv, &ds->verts[ j ], sizeof( *outv ) ); + outv->color[0] = 255; + outv->color[1] = 255; + outv->color[2] = 255; + } + + for ( j = 0 ; j < ds->numIndexes ; j++ ) { + if ( numDrawIndexes == MAX_MAP_DRAW_INDEXES ) { + Error( "MAX_MAP_DRAW_INDEXES" ); + } + drawIndexes[ numDrawIndexes ] = ds->indexes[ j ]; + numDrawIndexes++; + } +} + +//====================================================================== + +/* +================== +CreateFlareSurface + +Light flares from surface lights become +================== +*/ +void CreateFlareSurface( mapDrawSurface_t *faceDs ) { + mapDrawSurface_t *ds; + int i; + + ds = AllocDrawSurf(); + + if ( faceDs->shaderInfo->flareShader[0] ) { + ds->shaderInfo = ShaderInfoForShader( faceDs->shaderInfo->flareShader ); + } else { + ds->shaderInfo = ShaderInfoForShader( "flareshader" ); + } + ds->flareSurface = qtrue; + VectorCopy( faceDs->lightmapVecs[2], ds->lightmapVecs[2] ); + + // find midpoint + VectorClear( ds->lightmapOrigin ); + for ( i = 0 ; i < faceDs->numVerts ; i++ ) { + VectorAdd( ds->lightmapOrigin, faceDs->verts[i].xyz, ds->lightmapOrigin ); + } + VectorScale( ds->lightmapOrigin, 1.0/faceDs->numVerts, ds->lightmapOrigin ); + + VectorMA( ds->lightmapOrigin, 2, ds->lightmapVecs[2], ds->lightmapOrigin ); + + VectorCopy( faceDs->shaderInfo->color, ds->lightmapVecs[0] ); + + // FIXME: fog +} + +/* +===================== +FilterDrawsurfsIntoTree + +Upon completion, all drawsurfs that actually generate a reference +will have been emited to the bspfile arrays, and the references +will have valid final indexes +===================== +*/ +void FilterDrawsurfsIntoTree( entity_t *e, tree_t *tree ) { + int i; + mapDrawSurface_t *ds; + int refs; + int c_surfs, c_refs; + + qprintf( "----- FilterDrawsurfsIntoTree -----\n"); + + c_surfs = 0; + c_refs = 0; + for ( i = e->firstDrawSurf ; i < numMapDrawSurfs ; i++ ) { + ds = &mapDrawSurfs[i]; + + if ( !ds->numVerts && !ds->flareSurface ) { + continue; + } + if ( ds->miscModel ) { + refs = FilterMiscModelSurfIntoTree( ds, tree ); + EmitModelSurf( ds ); + } else if ( ds->patch ) { + refs = FilterPatchSurfIntoTree( ds, tree ); + EmitPatchSurf( ds ); + } else if ( ds->flareSurface ) { + refs = FilterFlareSurfIntoTree( ds, tree ); + EmitFlareSurf( ds ); + } else { + refs = FilterFaceIntoTree( ds, tree ); +// if ( ds->shaderInfo->value >= 1000 ) { // ds->shaderInfo->flareShader[0] ) { + if ( ds->shaderInfo->flareShader[0] ) { + CreateFlareSurface( ds ); + } + EmitPlanarSurf( ds ); + } + if ( refs > 0 ) { + c_surfs++; + c_refs += refs; + } + } + qprintf( "%5i emited drawsurfs\n", c_surfs ); + qprintf( "%5i references\n", c_refs ); + qprintf( "%5i stripfaces\n", c_stripSurfaces ); + qprintf( "%5i fanfaces\n", c_fanSurfaces ); +} + + + -- cgit v1.2.3