mesh.bak

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

#include "qbsp.h"


/*
===============================================================

MESH SUBDIVISION

===============================================================
*/


int	originalWidths[MAX_EXPANDED_AXIS];
int	originalHeights[MAX_EXPANDED_AXIS];

int	neighbors[8][2] = {
	{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
};

void FreeMesh( mesh_t *m ) {
	free( m->verts );
	free( m );
}

void PrintMesh( mesh_t *m ) {
	int		i, j;

	for ( i = 0 ; i < m->height ; i++ ) {
		for ( j = 0 ; j < m->width ; j++ ) {
			printf("(%5.2f %5.2f %5.2f) "
				, m->verts[i*m->width+j].xyz[0]
				, m->verts[i*m->width+j].xyz[1]
				, m->verts[i*m->width+j].xyz[2] );
		}
		printf("\n");
	}
}


/*
=================
TransposeMesh

Returns a transposed copy of the mesh, freeing the original
=================
*/
mesh_t *TransposeMesh( mesh_t *in ) {
	int			w, h;
	mesh_t		*out;

	out = malloc( sizeof( *out ) );
	out->width = in->height;
	out->height = in->width;
	out->verts = malloc( out->width * out->height * sizeof( drawVert_t ) );

	for ( h = 0 ; h < in->height ; h++ ) {
		for ( w = 0 ; w < in->width ; w++ ) {
			out->verts[ w * in->height + h ] = in->verts[ h * in->width + w ];
		}
	}

	FreeMesh( in );

	return out;
}

void InvertMesh( mesh_t *in ) {
	int			w, h;
	drawVert_t	temp;

	for ( h = 0 ; h < in->height ; h++ ) {
		for ( w = 0 ; w < in->width / 2 ; w++ ) {
			temp = in->verts[ h * in->width + w ];
			in->verts[ h * in->width + w ] = in->verts[ h * in->width + in->width - 1 - w ];
			in->verts[ h * in->width + in->width - 1 - w ] = temp;
		}
	}
}

/*
=================
MakeMeshNormals

=================
*/
void MakeMeshNormals( mesh_t in ) {
	int		i, j, k, dist;
	vec3_t	normal;
	vec3_t	sum;
	int		count;
	vec3_t	base;
	vec3_t	delta;
	int		x, y;
	drawVert_t	*dv;
	vec3_t		around[8], temp;
	qboolean	good[8];
	qboolean	wrapWidth, wrapHeight;
	float		len;

	wrapWidth = false;
	for ( i = 0 ; i < in.height ; i++ ) {
		VectorSubtract( in.verts[i*in.width].xyz, 
			in.verts[i*in.width+in.width-1].xyz, delta );
		len = VectorLength( delta );
		if ( len > 1.0 ) {
			break;
		}
	}
	if ( i == in.height ) {
		wrapWidth = true;
	}

	wrapHeight = false;
	for ( i = 0 ; i < in.width ; i++ ) {
		VectorSubtract( in.verts[i].xyz, 
			in.verts[i + (in.height-1)*in.width].xyz, delta );
		len = VectorLength( delta );
		if ( len > 1.0 ) {
			break;
		}
	}
	if ( i == in.width) {
		wrapHeight = true;
	}


	for ( i = 0 ; i < in.width ; i++ ) {
		for ( j = 0 ; j < in.height ; j++ ) {
			count = 0;
			dv = &in.verts[j*in.width+i];
			VectorCopy( dv->xyz, base );
			for ( k = 0 ; k < 8 ; k++ ) {
				VectorClear( around[k] );
				good[k] = false;

				for ( dist = 1 ; dist <= 3 ; dist++ ) {
					x = i + neighbors[k][0] * dist;
					y = j + neighbors[k][1] * dist;
					if ( wrapWidth ) {
						if ( x < 0 ) {
							x = in.width - 1 + x;
						} else if ( x >= in.width ) {
							x = 1 + x - in.width;
						}
					}
					if ( wrapHeight ) {
						if ( y < 0 ) {
							y = in.height - 1 + y;
						} else if ( y >= in.height ) {
							y = 1 + y - in.height;
						}
					}

					if ( x < 0 || x >= in.width || y < 0 || y >= in.height ) {
						break;					// edge of patch
					}
					VectorSubtract( in.verts[y*in.width+x].xyz, base, temp );
					if ( VectorNormalize( temp, temp ) == 0 ) {
						continue;				// degenerate edge, get more dist
					} else {
						good[k] = true;
						VectorCopy( temp, around[k] );
						break;					// good edge
					}
				}
			}

			VectorClear( sum );
			for ( k = 0 ; k < 8 ; k++ ) {
				if ( !good[k] || !good[(k+1)&7] ) {
					continue;	// didn't get two points
				}
				CrossProduct( around[(k+1)&7], around[k], normal );
				if ( VectorNormalize( normal, normal ) == 0 ) {
					continue;
				}
				VectorAdd( normal, sum, sum );
				count++;
			}
			if ( count == 0 ) {
//printf("bad normal\n");
				count = 1;
			}
			VectorNormalize( sum, dv->normal );
		}
	}
}

/*
=================
PutMeshOnCurve

Drops the aproximating points onto the curve
=================
*/
void PutMeshOnCurve( mesh_t in ) {
	int		i, j, l;
	float	prev, next;

	// put all the aproximating points on the curve
	for ( i = 0 ; i < in.width ; i++ ) {
		for ( j = 1 ; j < in.height ; j += 2 ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j+1)*in.width+i].xyz[l] ) * 0.5;
				next = ( in.verts[j*in.width+i].xyz[l] + in.verts[(j-1)*in.width+i].xyz[l] ) * 0.5;
				in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
			}
		}
	}

	for ( j = 0 ; j < in.height ; j++ ) {
		for ( i = 1 ; i < in.width ; i += 2 ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prev = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i+1].xyz[l] ) * 0.5;
				next = ( in.verts[j*in.width+i].xyz[l] + in.verts[j*in.width+i-1].xyz[l] ) * 0.5;
				in.verts[j*in.width+i].xyz[l] = ( prev + next ) * 0.5;
			}
		}
	}
}


/*
=================
SubdivideMesh

=================
*/
mesh_t SubdivideMesh( mesh_t in, float maxError, float minLength ) {
	int			i, j, k, l;
	vec_t		prev[10], next[10], mid[10], delta[10];
	float		len;
	mesh_t		out;
	vec_t		expand[MAX_EXPANDED_AXIS][MAX_EXPANDED_AXIS][10];

	out.width = in.width;
	out.height = in.height;

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

	for ( i = 0 ; i < in.height ; i++ ) {
		originalHeights[i] = i;
	}
	for ( i = 0 ; i < in.width ; i++ ) {
		originalWidths[i] = i;
	}

	// horizontal subdivisions
	for ( j = 0 ; j + 2 < out.width ; j += 2 ) {
		// check subdivided midpoints against control points
		for ( i = 0 ; i < out.height ; i++ ) {
			for ( l = 0 ; l < 3 ; l++ ) {
				prev[l] = expand[i][j+1][l] - expand[i][j][l]; 
				next[l] = expand[i][j+2][l] - expand[i][j+1][l]; 
				mid[l] = (expand[i][j][l] + expand[i][j+1][l] * 2
						+ expand[i][j+2][l] ) * 0.25;
			}

			// if the span length is too long, force a subdivision
			if ( VectorLength( prev ) > minLength 
				|| VectorLength( next ) > minLength ) {
				break;
			}

			// see if this midpoint is off far enough to subdivide
			VectorSubtract( expand[i][j+1], mid, delta );
			len = VectorLength( delta );
			if ( len > maxError ) {
				break;
			}
		}

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

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

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

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

		for ( i = 0 ; i < out.height ; i++ ) {
			for ( l = 0 ; l < 10 ; l++ ) {
				prev[l] = ( expand[i][j][l] + expand[i][j+1][l] ) * 0.5;
				next[l] = ( expand[i][j+1][l] + expand[i][j+2][l] ) * 0.5;
				mid[l] = ( prev[l] + next[l] ) * 0.5;
			}

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

		// 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++ ) {
				prev[l] = expand[j+1][i][l] - expand[j][i][l]; 
				next[l] = expand[j+2][i][l] - expand[j+1][i][l]; 
				mid[l] = (expand[j][i][l] + expand[j+1][i][l] * 2
						+ expand[j+2][i][l] ) * 0.25;
			}

			// if the span length is too long, force a subdivision
			if ( VectorLength( prev ) > minLength 
				|| VectorLength( next ) > minLength ) {
				break;
			}
			// see if this midpoint is off far enough to subdivide
			VectorSubtract( expand[j+1][i], mid, 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++ ) {
			for ( l = 0 ; l < 10 ; l++ ) {
				prev[l] = ( expand[j][i][l] + expand[j+1][i][l] ) * 0.5;
				next[l] = ( expand[j+1][i][l] + expand[j+2][i][l] ) * 0.5;
				mid[l] = ( prev[l] + next[l] ) * 0.5;
			}

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

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

	}

	// collapse the verts

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

	return out;
}