surface.c

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

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