surface.c

quake3工具源码。包括生成bsp文件

#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;
			}
			// 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 );