map_q1.c

quakeIII源码这个不用我多说吧

	} //end if*/
	//
	planenum = q1_dnodes[nodenum].planenum;
	planenum = FindFloatPlane(q1_dplanes[planenum].normal, q1_dplanes[planenum].dist);
	//split the brush with the node plane
	Q1_SplitBrush(brush, planenum, nodenum, &front, &back);
	//free the original brush
	FreeBrush(brush);
	//every node must split the brush in two
	if (!front || !back)
	{
		Log_Print("Q1_CreateBrushes_r: WARNING node not splitting brush\n");
		//return NULL;
	} //end if
	//create brushes recursively
	if (front) front = Q1_CreateBrushes_r(front, q1_dnodes[nodenum].children[0]);
	if (back) back = Q1_CreateBrushes_r(back, q1_dnodes[nodenum].children[1]);
	//link the brushes if possible and return them
	if (front)
	{
		for (brush = front; brush->next; brush = brush->next);
		brush->next = back;
		return front;
	} //end if
	else
	{
		return back;
	} //end else
} //end of the function Q1_CreateBrushes_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *Q1_CreateBrushesFromBSP(int modelnum)
{
	bspbrush_t *brushlist;
	bspbrush_t *brush;
	q1_dnode_t *headnode;
	vec3_t mins, maxs;
	int i;

	//
	headnode = &q1_dnodes[q1_dmodels[modelnum].headnode[0]];
	//get the mins and maxs of the world
	VectorCopy(headnode->mins, mins);
	VectorCopy(headnode->maxs, maxs);
	//enlarge these mins and maxs
	for (i = 0; i < 3; i++)
	{
		mins[i] -= 8;
		maxs[i] += 8;
	} //end for
	//NOTE: have to add the BSP tree mins and maxs to the MAP mins and maxs
	AddPointToBounds(mins, map_mins, map_maxs);
	AddPointToBounds(maxs, map_mins, map_maxs);
	//
	if (!modelnum)
	{
		Log_Print("brush size: %5.0f,%5.0f,%5.0f to %5.0f,%5.0f,%5.0f\n",
							map_mins[0], map_mins[1], map_mins[2],
							map_maxs[0], map_maxs[1], map_maxs[2]);
	} //end if
	//create one huge brush containing the whole world
	brush = BrushFromBounds(mins, maxs);
	VectorCopy(mins, brush->mins);
	VectorCopy(maxs, brush->maxs);
	//
#ifdef Q1_PRINT
	qprintf("creating Quake brushes\n");
	qprintf("%5d brushes", q1_numbrushes = 0);
#endif //Q1_PRINT
	//create the brushes
	brushlist = Q1_CreateBrushes_r(brush, q1_dmodels[modelnum].headnode[0]);
	//
#ifdef Q1_PRINT
	qprintf("\n");
#endif //Q1_PRINT
	//now we've got a list with brushes!
	return brushlist;
} //end of the function Q1_CreateBrushesFromBSP
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
q1_dleaf_t *Q1_PointInLeaf(int startnode, vec3_t point)
{
	int nodenum;
	vec_t	dist;
	q1_dnode_t *node;
	q1_dplane_t *plane;

	nodenum = startnode;
	while (nodenum >= 0)
	{
		node = &q1_dnodes[nodenum];
		plane = &q1_dplanes[node->planenum];
		dist = DotProduct(point, plane->normal) - plane->dist;
		if (dist > 0)
			nodenum = node->children[0];
		else
			nodenum = node->children[1];
	} //end while

	return &q1_dleafs[-nodenum - 1];
} //end of the function Q1_PointInLeaf
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
float Q1_FaceArea(q1_dface_t *face)
{
	int i;
	float total;
	vec_t *v;
	vec3_t d1, d2, cross;
	q1_dedge_t *edge;

	edge = &q1_dedges[face->firstedge];
	v = q1_dvertexes[edge->v[0]].point;

	total = 0;
	for (i = 1; i < face->numedges - 1; i++)
	{
		edge = &q1_dedges[face->firstedge + i];
		VectorSubtract(q1_dvertexes[edge->v[0]].point, v, d1);
		VectorSubtract(q1_dvertexes[edge->v[1]].point, v, d2);
		CrossProduct(d1, d2, cross);
		total += 0.5 * VectorLength(cross);
	} //end for
	return total;
} //end of the function AAS_FaceArea
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void Q1_FacePlane(q1_dface_t *face, vec3_t normal, float *dist)
{
	vec_t *v1, *v2, *v3;
	vec3_t vec1, vec2;
	int side, edgenum;

	edgenum = q1_dsurfedges[face->firstedge];
	side = edgenum < 0;
	v1 = q1_dvertexes[q1_dedges[abs(edgenum)].v[side]].point;
	v2 = q1_dvertexes[q1_dedges[abs(edgenum)].v[!side]].point;
	edgenum = q1_dsurfedges[face->firstedge+1];
	side = edgenum < 0;
	v3 = q1_dvertexes[q1_dedges[abs(edgenum)].v[!side]].point;
	//
	VectorSubtract(v2, v1, vec1);
	VectorSubtract(v3, v1, vec2);

	CrossProduct(vec1, vec2, normal);
	VectorNormalize(normal);
	*dist = DotProduct(v1, normal);
} //end of the function Q1_FacePlane
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *Q1_MergeBrushes(bspbrush_t *brushlist, int modelnum)
{
	int nummerges, merged;
	bspbrush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
	bspbrush_t *lastb2;

	if (!brushlist) return NULL;

	if (!modelnum) qprintf("%5d brushes merged", nummerges = 0);
	do
	{
		for (tail = brushlist; tail; tail = tail->next)
		{
			if (!tail->next) break;
		} //end for
		merged = 0;
		newbrushlist = NULL;
		for (b1 = brushlist; b1; b1 = brushlist)
		{
			lastb2 = b1;
			for (b2 = b1->next; b2; b2 = b2->next)
			{
				//can't merge brushes with different contents
				if (b1->side != b2->side) newbrush = NULL;
				else newbrush = TryMergeBrushes(b1, b2);
				//if a merged brush is created
				if (newbrush)
				{
					//copy the brush contents
					newbrush->side = b1->side;
					//add the new brush to the end of the list
					tail->next = newbrush;
					//remove the second brush from the list
					lastb2->next = b2->next;
					//remove the first brush from the list
					brushlist = brushlist->next;
					//free the merged brushes
					FreeBrush(b1);
					FreeBrush(b2);
					//get a new tail brush
					for (tail = brushlist; tail; tail = tail->next)
					{
						if (!tail->next) break;
					} //end for
					merged++;
					if (!modelnum) qprintf("\r%5d", nummerges++);
					break;
				} //end if
				lastb2 = b2;
			} //end for
			//if b1 can't be merged with any of the other brushes
			if (!b2)
			{
				brushlist = brushlist->next;
				//keep b1
				b1->next = newbrushlist;
				newbrushlist = b1;
			} //end else
		} //end for
		brushlist = newbrushlist;
	} while(merged);
	if (!modelnum) qprintf("\n");
	return newbrushlist;
} //end of the function Q1_MergeBrushes
//===========================================================================
// returns the amount the face and the winding overlap
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
float Q1_FaceOnWinding(q1_dface_t *face, winding_t *winding)
{
	int i, edgenum, side;
	float dist, area;
	q1_dplane_t plane;
	vec_t *v1, *v2;
	vec3_t normal, edgevec;
	winding_t *w;

	//
	w = CopyWinding(winding);
	memcpy(&plane, &q1_dplanes[face->planenum], sizeof(q1_dplane_t));
	//check on which side of the plane the face is
	if (face->side)
	{
		VectorNegate(plane.normal, plane.normal);
		plane.dist = -plane.dist;
	} //end if
	for (i = 0; i < face->numedges && w; i++)
	{
		//get the first and second vertex of the edge
		edgenum = q1_dsurfedges[face->firstedge + i];
		side = edgenum > 0;
		//if the face plane is flipped
		v1 = q1_dvertexes[q1_dedges[abs(edgenum)].v[side]].point;
		v2 = q1_dvertexes[q1_dedges[abs(edgenum)].v[!side]].point;
		//create a plane through the edge vector, orthogonal to the face plane
		//and with the normal vector pointing out of the face
		VectorSubtract(v1, v2, edgevec);
		CrossProduct(edgevec, plane.normal, normal);
		VectorNormalize(normal);
		dist = DotProduct(normal, v1);
		//
		ChopWindingInPlace(&w, normal, dist, 0.9); //CLIP_EPSILON
	} //end for
	if (w)
	{
		area = WindingArea(w);
		FreeWinding(w);
		return area;
	} //end if
	return 0;
} //end of the function Q1_FaceOnWinding
//===========================================================================
// returns a list with brushes created by splitting the given brush with
// planes that go through the face edges and are orthogonal to the face plane
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *Q1_SplitBrushWithFace(bspbrush_t *brush, q1_dface_t *face)
{
	int i, edgenum, side, planenum, splits;
	float dist;
	q1_dplane_t plane;
	vec_t *v1, *v2;
	vec3_t normal, edgevec;
	bspbrush_t *front, *back, *brushlist;

	memcpy(&plane, &q1_dplanes[face->planenum], sizeof(q1_dplane_t));
	//check on which side of the plane the face is
	if (face->side)
	{
		VectorNegate(plane.normal, plane.normal);
		plane.dist = -plane.dist;
	} //end if
	splits = 0;
	brushlist = NULL;
	for (i = 0; i < face->numedges; i++)
	{
		//get the first and second vertex of the edge
		edgenum = q1_dsurfedges[face->firstedge + i];
		side = edgenum > 0;
		//if the face plane is flipped
		v1 = q1_dvertexes[q1_dedges[abs(edgenum)].v[side]].point;
		v2 = q1_dvertexes[q1_dedges[abs(edgenum)].v[!side]].point;
		//create a plane through the edge vector, orthogonal to the face plane
		//and with the normal vector pointing out of the face
		VectorSubtract(v1, v2, edgevec);
		CrossProduct(edgevec, plane.normal, normal);
		VectorNormalize(normal);
		dist = DotProduct(normal, v1);
		//
		planenum = FindFloatPlane(normal, dist);
		//split the current brush
		SplitBrush(brush, planenum, &front, &back);
		//if there is a back brush just put it in the list
		if (back)
		{
			//copy the brush contents
			back->side = brush->side;
			//
			back->next = brushlist;
			brushlist = back;
			splits++;
		} //end if
		if (!front)
		{
			Log_Print("Q1_SplitBrushWithFace: no new brush\n");
			FreeBrushList(brushlist);
			return NULL;
		} //end if
		//copy the brush contents
		front->side = brush->side;
		//continue splitting the front brush
		brush = front;
	} //end for
	if (!splits)
	{
		FreeBrush(front);
		return NULL;
	} //end if
	front->next = brushlist;
	brushlist = front;
	return brushlist;
} //end of the function Q1_SplitBrushWithFace
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
bspbrush_t *Q1_TextureBrushes(bspbrush_t *brushlist, int modelnum)
{
	float area, largestarea;
	int i, n, texinfonum, sn, numbrushes, ofs;
	int bestfacenum, sidenodenum;
	side_t *side;
	q1_dmiptexlump_t *miptexlump;
	q1_miptex_t *miptex;
	bspbrush_t *brush, *nextbrush, *prevbrush, *newbrushes, *brushlistend;
	vec_t defaultvec[4] = {1, 0, 0, 0};

	if (!modelnum) qprintf("texturing brushes\n");
	if (!modelnum) qprintf("%5d brushes", numbrushes = 0);
	//get a pointer to the last brush in the list
	for (brushlistend = brushlist; brushlistend; brushlistend = brushlistend->next)
	{
		if (!brushlistend->next) break;
	} //end for
	//there's no previous brush when at the start of the list
	prevbrush = NULL;
	//go over the brush list
	for (brush = brushlist; brush; brush = nextbrush)
	{
		nextbrush = brush->next;
		//find a texinfo for every brush side
		for (sn = 0; sn < brush->numsides; sn++)
		{
			side = &brush->sides[sn];