mesh.c

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

		}
		originalWidths[j+3] = originalWidths[j+1];
		originalWidths[j+2] = originalWidths[j+1];
		originalWidths[j+1] = originalWidths[j];

		for ( i = 0 ; i < out.height ; i++ ) {
			LerpDrawVert( &expand[i][j], &expand[i][j+1], &prev );
			LerpDrawVert( &expand[i][j+1], &expand[i][j+2], &next );
			LerpDrawVert( &prev, &next, &mid );

			for ( k = out.width - 1 ; k > j + 3 ; k-- ) {
				expand[i][k] = expand[i][k-2];
			}
			expand[i][j + 1] = prev;
			expand[i][j + 2] = mid;
			expand[i][j + 3] = next;
		}

		// back up and recheck this set again, it may need more subdivision
		j -= 2;

	}

	// vertical subdivisions
	for ( j = 0 ; j + 2 < out.height ; j += 2 ) {
		// check subdivided midpoints against control points
		for ( i = 0 ; i < out.width ; i++ ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prevxyz[l] = expand[j+1][i].xyz[l] - expand[j][i].xyz[l]; 
				nextxyz[l] = expand[j+2][i].xyz[l] - expand[j+1][i].xyz[l]; 
				midxyz[l] = (expand[j][i].xyz[l] + expand[j+1][i].xyz[l] * 2
						+ expand[j+2][i].xyz[l] ) * 0.25;
			}

			// if the span length is too long, force a subdivision
			if ( VectorLength( prevxyz ) > minLength 
				|| VectorLength( nextxyz ) > minLength ) {
				break;
			}
			// see if this midpoint is off far enough to subdivide
			VectorSubtract( expand[j+1][i].xyz, midxyz, delta );
			len = VectorLength( delta );
			if ( len > maxError ) {
				break;
			}
		}

		if ( out.height + 2 >= MAX_EXPANDED_AXIS ) {
			break;	// can't subdivide any more
		}

		if ( i == out.width ) {
			continue;	// didn't need subdivision
		}

		// insert two columns and replace the peak
		out.height += 2;

		for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
			originalHeights[k] = originalHeights[k-2];
		}
		originalHeights[j+3] = originalHeights[j+1];
		originalHeights[j+2] = originalHeights[j+1];
		originalHeights[j+1] = originalHeights[j];

		for ( i = 0 ; i < out.width ; i++ ) {
			LerpDrawVert( &expand[j][i], &expand[j+1][i], &prev );
			LerpDrawVert( &expand[j+1][i], &expand[j+2][i], &next );
			LerpDrawVert( &prev, &next, &mid );

			for ( k = out.height - 1 ; k > j + 3 ; k-- ) {
				expand[k][i] = expand[k-2][i];
			}
			expand[j+1][i] = prev;
			expand[j+2][i] = mid;
			expand[j+3][i] = next;
		}

		// back up and recheck this set again, it may need more subdivision
		j -= 2;

	}

	// collapse the verts

	out.verts = &expand[0][0];
	for ( i = 1 ; i < out.height ; i++ ) {
		memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) );
	}

	return CopyMesh(&out);
}

/*
================
ProjectPointOntoVector
================
*/
void ProjectPointOntoVector( vec3_t point, vec3_t vStart, vec3_t vEnd, vec3_t vProj )
{
	vec3_t pVec, vec;

	VectorSubtract( point, vStart, pVec );
	VectorSubtract( vEnd, vStart, vec );
	VectorNormalize( vec, vec );
	// project onto the directional vector for this segment
	VectorMA( vStart, DotProduct( pVec, vec ), vec, vProj );
}

/*
================
RemoveLinearMeshColumsRows
================
*/
mesh_t *RemoveLinearMeshColumnsRows( mesh_t *in ) {
	int i, j, k;
	float len, maxLength;
	vec3_t proj, dir;
	mesh_t out;
	drawVert_t	expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];

	out.width = in->width;
	out.height = in->height;

	for ( i = 0 ; i < in->width ; i++ ) {
		for ( j = 0 ; j < in->height ; j++ ) {
			expand[j][i] = in->verts[j*in->width+i];
		}
	}

	for ( j = 1 ; j < out.width - 1; j++ ) {
		maxLength = 0;
		for ( i = 0 ; i < out.height ; i++ ) {
			ProjectPointOntoVector(expand[i][j].xyz, expand[i][j-1].xyz, expand[i][j+1].xyz, proj);
			VectorSubtract(expand[i][j].xyz, proj, dir);
			len = VectorLength(dir);
			if (len > maxLength) {
				maxLength = len;
			}
		}
		if (maxLength < 0.1)
		{
			out.width--;
			for ( i = 0 ; i < out.height ; i++ ) {
				for (k = j; k < out.width; k++) {
					expand[i][k] = expand[i][k+1];
				}
			}
			for (k = j; k < out.width; k++) {
				originalWidths[k] = originalWidths[k+1];
			}
			j--;
		}
	}
	for ( j = 1 ; j < out.height - 1; j++ ) {
		maxLength = 0;
		for ( i = 0 ; i < out.width ; i++ ) {
			ProjectPointOntoVector(expand[j][i].xyz, expand[j-1][i].xyz, expand[j+1][i].xyz, proj);
			VectorSubtract(expand[j][i].xyz, proj, dir);
			len = VectorLength(dir);
			if (len > maxLength) {
				maxLength = len;
			}
		}
		if (maxLength < 0.1)
		{
			out.height--;
			for ( i = 0 ; i < out.width ; i++ ) {
				for (k = j; k < out.height; k++) {
					expand[k][i] = expand[k+1][i];
				}
			}
			for (k = j; k < out.height; k++) {
				originalHeights[k] = originalHeights[k+1];
			}
			j--;
		}
	}
	// collapse the verts
	out.verts = &expand[0][0];
	for ( i = 1 ; i < out.height ; i++ ) {
		memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) );
	}

	return CopyMesh(&out);
}

/*
============
LerpDrawVertAmount
============
*/
void LerpDrawVertAmount( drawVert_t *a, drawVert_t *b, float amount, drawVert_t *out ) {
	out->xyz[0] = a->xyz[0] + amount * (b->xyz[0] - a->xyz[0]);
	out->xyz[1] = a->xyz[1] + amount * (b->xyz[1] - a->xyz[1]);
	out->xyz[2] = a->xyz[2] + amount * (b->xyz[2] - a->xyz[2]);

	out->st[0] = a->st[0] + amount * (b->st[0] - a->st[0]);
	out->st[1] = a->st[1] + amount * (b->st[1] - a->st[1]);

	out->lightmap[0] = a->lightmap[0] + amount * (b->lightmap[0] - a->lightmap[0]);
	out->lightmap[1] = a->lightmap[1] + amount * (b->lightmap[1] - a->lightmap[1]);

	out->color[0] = a->color[0] + amount * (b->color[0] - a->color[0]);
	out->color[1] = a->color[1] + amount * (b->color[1] - a->color[1]);
	out->color[2] = a->color[2] + amount * (b->color[2] - a->color[2]);
	out->color[3] = a->color[3] + amount * (b->color[3] - a->color[3]);

	out->normal[0] = a->normal[0] + amount * (b->normal[0] - a->normal[0]);
	out->normal[1] = a->normal[1] + amount * (b->normal[1] - a->normal[1]);
	out->normal[2] = a->normal[2] + amount * (b->normal[2] - a->normal[2]);
	VectorNormalize(out->normal, out->normal);
}

/*
=================
SubdivideMeshQuads
=================
*/
mesh_t *SubdivideMeshQuads( mesh_t *in, float minLength, int maxsize, int widthtable[], int heighttable[]) {
	int			i, j, k, w, h, maxsubdivisions, subdivisions;
	vec3_t		dir;
	float		length, maxLength, amount;
	mesh_t		out;
	drawVert_t	expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS];

	out.width = in->width;
	out.height = in->height;

	for ( i = 0 ; i < in->width ; i++ ) {
		for ( j = 0 ; j < in->height ; j++ ) {
			expand[j][i] = in->verts[j*in->width+i];
		}
	}

	if (maxsize > MAX_EXPANDED_AXIS)
		Error("SubdivideMeshQuads: maxsize > MAX_EXPANDED_AXIS");

	// horizontal subdivisions

	maxsubdivisions = (maxsize - in->width) / (in->width - 1);

	for ( w = 0, j = 0 ; w < in->width - 1; w++, j += subdivisions + 1) {
		maxLength = 0;
		for ( i = 0 ; i < out.height ; i++ ) {
			VectorSubtract(expand[i][j+1].xyz, expand[i][j].xyz, dir);
			length = VectorLength( dir );
			if (length > maxLength) {
				maxLength = length;
			}
		}
		
		subdivisions = (int) (maxLength / minLength);
		if (subdivisions > maxsubdivisions)
			subdivisions = maxsubdivisions;

		widthtable[w] = subdivisions + 1;
		if (subdivisions <= 0)
			continue;

		out.width += subdivisions;

		for ( k = out.width - 1; k >= j + subdivisions; k-- ) {
			originalWidths[k] = originalWidths[k-subdivisions];
		}
		for (k = 1; k <= subdivisions; k++) {
			originalWidths[j+k] = originalWidths[j];
		}

		for ( i = 0 ; i < out.height ; i++ ) {
			for ( k = out.width - 1 ; k > j + subdivisions; k-- ) {
				expand[i][k] = expand[i][k-subdivisions];
			}
			for (k = 1; k <= subdivisions; k++)
			{
				amount = (float) k / (subdivisions + 1);
				LerpDrawVertAmount(&expand[i][j], &expand[i][j+subdivisions+1], amount, &expand[i][j+k]);
			}
		}
	}

	maxsubdivisions = (maxsize - in->height) / (in->height - 1);

	for ( h = 0, j = 0 ; h < in->height - 1; h++, j += subdivisions + 1) {
		maxLength = 0;
		for ( i = 0 ; i < out.width ; i++ ) {
			VectorSubtract(expand[j+1][i].xyz, expand[j][i].xyz, dir);
			length = VectorLength( dir );
			if (length  > maxLength) {
				maxLength = length;
			}
		}
		
		subdivisions = (int) (maxLength / minLength);
		if (subdivisions > maxsubdivisions)
			subdivisions = maxsubdivisions;

		heighttable[h] = subdivisions + 1;
		if (subdivisions <= 0)
			continue;

		out.height += subdivisions;

		for ( k = out.height - 1; k >= j + subdivisions; k-- ) {
			originalHeights[k] = originalHeights[k-subdivisions];
		}
		for (k = 1; k <= subdivisions; k++) {
			originalHeights[j+k] = originalHeights[j];
		}

		for ( i = 0 ; i < out.width ; i++ ) {
			for ( k = out.height - 1 ; k > j + subdivisions; k-- ) {
				expand[k][i] = expand[k-subdivisions][i];
			}
			for (k = 1; k <= subdivisions; k++)
			{
				amount = (float) k / (subdivisions + 1);
				LerpDrawVertAmount(&expand[j][i], &expand[j+subdivisions+1][i], amount, &expand[j+k][i]);
			}
		}
	}

	// collapse the verts
	out.verts = &expand[0][0];
	for ( i = 1 ; i < out.height ; i++ ) {
		memmove( &out.verts[i*out.width], expand[i], out.width * sizeof(drawVert_t) );
	}

	return CopyMesh(&out);
}