Quake-III-Arena

cm_patch.c (43759B)

---

 /*
 ===========================================================================
 Copyright (C) 1999-2005 Id Software, Inc.
 
 This file is part of Quake III Arena source code.
 
 Quake III Arena source code is free software; you can redistribute it
 and/or modify it under the terms of the GNU General Public License as
 published by the Free Software Foundation; either version 2 of the License,
 or (at your option) any later version.
 
 Quake III Arena source code is distributed in the hope that it will be
 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with Foobar; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 ===========================================================================
 */
 
 #include "cm_local.h"
 #include "cm_patch.h"
 
 /*
 
 This file does not reference any globals, and has these entry points:
 
 void CM_ClearLevelPatches( void );
 struct patchCollide_s	*CM_GeneratePatchCollide( int width, int height, const vec3_t *points );
 void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc );
 qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc );
 void CM_DrawDebugSurface( void (*drawPoly)(int color, int numPoints, flaot *points) );
 
 
 WARNING: this may misbehave with meshes that have rows or columns that only
 degenerate a few triangles.  Completely degenerate rows and columns are handled
 properly.
 */
 
 /*
 #define	MAX_FACETS			1024
 #define	MAX_PATCH_PLANES	2048
 
 typedef struct {
 	float	plane[4];
 	int		signbits;		// signx + (signy<<1) + (signz<<2), used as lookup during collision
 } patchPlane_t;
 
 typedef struct {
 	int			surfacePlane;
 	int			numBorders;		// 3 or four + 6 axial bevels + 4 or 3 * 4 edge bevels
 	int			borderPlanes[4+6+16];
 	int			borderInward[4+6+16];
 	qboolean	borderNoAdjust[4+6+16];
 } facet_t;
 
 typedef struct patchCollide_s {
 	vec3_t	bounds[2];
 	int		numPlanes;			// surface planes plus edge planes
 	patchPlane_t	*planes;
 	int		numFacets;
 	facet_t	*facets;
 } patchCollide_t;
 
 
 #define	MAX_GRID_SIZE	129
 
 typedef struct {
 	int			width;
 	int			height;
 	qboolean	wrapWidth;
 	qboolean	wrapHeight;
 	vec3_t	points[MAX_GRID_SIZE][MAX_GRID_SIZE];	// [width][height]
 } cGrid_t;
 
 #define	SUBDIVIDE_DISTANCE	16	//4	// never more than this units away from curve
 #define	PLANE_TRI_EPSILON	0.1
 #define	WRAP_POINT_EPSILON	0.1
 */
 
 int	c_totalPatchBlocks;
 int	c_totalPatchSurfaces;
 int	c_totalPatchEdges;
 
 static const patchCollide_t	*debugPatchCollide;
 static const facet_t		*debugFacet;
 static qboolean		debugBlock;
 static vec3_t		debugBlockPoints[4];
 
 /*
 =================
 CM_ClearLevelPatches
 =================
 */
 void CM_ClearLevelPatches( void ) {
 	debugPatchCollide = NULL;
 	debugFacet = NULL;
 }
 
 /*
 =================
 CM_SignbitsForNormal
 =================
 */
 static int CM_SignbitsForNormal( vec3_t normal ) {
 	int	bits, j;
 
 	bits = 0;
 	for (j=0 ; j<3 ; j++) {
 		if ( normal[j] < 0 ) {
 			bits |= 1<<j;
 		}
 	}
 	return bits;
 }
 
 /*
 =====================
 CM_PlaneFromPoints
 
 Returns false if the triangle is degenrate.
 The normal will point out of the clock for clockwise ordered points
 =====================
 */
 static qboolean CM_PlaneFromPoints( vec4_t plane, vec3_t a, vec3_t b, vec3_t c ) {
 	vec3_t	d1, d2;
 
 	VectorSubtract( b, a, d1 );
 	VectorSubtract( c, a, d2 );
 	CrossProduct( d2, d1, plane );
 	if ( VectorNormalize( plane ) == 0 ) {
 		return qfalse;
 	}
 
 	plane[3] = DotProduct( a, plane );
 	return qtrue;
 }
 
 
 /*
 ================================================================================
 
 GRID SUBDIVISION
 
 ================================================================================
 */
 
 /*
 =================
 CM_NeedsSubdivision
 
 Returns true if the given quadratic curve is not flat enough for our
 collision detection purposes
 =================
 */
 static qboolean	CM_NeedsSubdivision( vec3_t a, vec3_t b, vec3_t c ) {
 	vec3_t		cmid;
 	vec3_t		lmid;
 	vec3_t		delta;
 	float		dist;
 	int			i;
 
 	// calculate the linear midpoint
 	for ( i = 0 ; i < 3 ; i++ ) {
 		lmid[i] = 0.5*(a[i] + c[i]);
 	}
 
 	// calculate the exact curve midpoint
 	for ( i = 0 ; i < 3 ; i++ ) {
 		cmid[i] = 0.5 * ( 0.5*(a[i] + b[i]) + 0.5*(b[i] + c[i]) );
 	}
 
 	// see if the curve is far enough away from the linear mid
 	VectorSubtract( cmid, lmid, delta );
 	dist = VectorLength( delta );
 	
 	return dist >= SUBDIVIDE_DISTANCE;
 }
 
 /*
 ===============
 CM_Subdivide
 
 a, b, and c are control points.
 the subdivided sequence will be: a, out1, out2, out3, c
 ===============
 */
 static void CM_Subdivide( vec3_t a, vec3_t b, vec3_t c, vec3_t out1, vec3_t out2, vec3_t out3 ) {
 	int		i;
 
 	for ( i = 0 ; i < 3 ; i++ ) {
 		out1[i] = 0.5 * (a[i] + b[i]);
 		out3[i] = 0.5 * (b[i] + c[i]);
 		out2[i] = 0.5 * (out1[i] + out3[i]);
 	}
 }
 
 /*
 =================
 CM_TransposeGrid
 
 Swaps the rows and columns in place
 =================
 */
 static void CM_TransposeGrid( cGrid_t *grid ) {
 	int			i, j, l;
 	vec3_t		temp;
 	qboolean	tempWrap;
 
 	if ( grid->width > grid->height ) {
 		for ( i = 0 ; i < grid->height ; i++ ) {
 			for ( j = i + 1 ; j < grid->width ; j++ ) {
 				if ( j < grid->height ) {
 					// swap the value
 					VectorCopy( grid->points[i][j], temp );
 					VectorCopy( grid->points[j][i], grid->points[i][j] );
 					VectorCopy( temp, grid->points[j][i] );
 				} else {
 					// just copy
 					VectorCopy( grid->points[j][i], grid->points[i][j] );
 				}
 			}
 		}
 	} else {
 		for ( i = 0 ; i < grid->width ; i++ ) {
 			for ( j = i + 1 ; j < grid->height ; j++ ) {
 				if ( j < grid->width ) {
 					// swap the value
 					VectorCopy( grid->points[j][i], temp );
 					VectorCopy( grid->points[i][j], grid->points[j][i] );
 					VectorCopy( temp, grid->points[i][j] );
 				} else {
 					// just copy
 					VectorCopy( grid->points[i][j], grid->points[j][i] );
 				}
 			}
 		}
 	}
 
 	l = grid->width;
 	grid->width = grid->height;
 	grid->height = l;
 
 	tempWrap = grid->wrapWidth;
 	grid->wrapWidth = grid->wrapHeight;
 	grid->wrapHeight = tempWrap;
 }
 
 /*
 ===================
 CM_SetGridWrapWidth
 
 If the left and right columns are exactly equal, set grid->wrapWidth qtrue
 ===================
 */
 static void CM_SetGridWrapWidth( cGrid_t *grid ) {
 	int		i, j;
 	float	d;
 
 	for ( i = 0 ; i < grid->height ; i++ ) {
 		for ( j = 0 ; j < 3 ; j++ ) {
 			d = grid->points[0][i][j] - grid->points[grid->width-1][i][j];
 			if ( d < -WRAP_POINT_EPSILON || d > WRAP_POINT_EPSILON ) {
 				break;
 			}
 		}
 		if ( j != 3 ) {
 			break;
 		}
 	}
 	if ( i == grid->height ) {
 		grid->wrapWidth = qtrue;
 	} else {
 		grid->wrapWidth = qfalse;
 	}
 }
 
 /*
 =================
 CM_SubdivideGridColumns
 
 Adds columns as necessary to the grid until
 all the aproximating points are within SUBDIVIDE_DISTANCE
 from the true curve
 =================
 */
 static void CM_SubdivideGridColumns( cGrid_t *grid ) {
 	int		i, j, k;
 
 	for ( i = 0 ; i < grid->width - 2 ;  ) {
 		// grid->points[i][x] is an interpolating control point
 		// grid->points[i+1][x] is an aproximating control point
 		// grid->points[i+2][x] is an interpolating control point
 
 		//
 		// first see if we can collapse the aproximating collumn away
 		//
 		for ( j = 0 ; j < grid->height ; j++ ) {
 			if ( CM_NeedsSubdivision( grid->points[i][j], grid->points[i+1][j], grid->points[i+2][j] ) ) {
 				break;
 			}
 		}
 		if ( j == grid->height ) {
 			// all of the points were close enough to the linear midpoints
 			// that we can collapse the entire column away
 			for ( j = 0 ; j < grid->height ; j++ ) {
 				// remove the column
 				for ( k = i + 2 ; k < grid->width ; k++ ) {
 					VectorCopy( grid->points[k][j], grid->points[k-1][j] );
 				}
 			}
 
 			grid->width--;
 
 			// go to the next curve segment
 			i++;
 			continue;
 		}
 
 		//
 		// we need to subdivide the curve
 		//
 		for ( j = 0 ; j < grid->height ; j++ ) {
 			vec3_t	prev, mid, next;
 
 			// save the control points now
 			VectorCopy( grid->points[i][j], prev );
 			VectorCopy( grid->points[i+1][j], mid );
 			VectorCopy( grid->points[i+2][j], next );
 
 			// make room for two additional columns in the grid
 			// columns i+1 will be replaced, column i+2 will become i+4
 			// i+1, i+2, and i+3 will be generated
 			for ( k = grid->width - 1 ; k > i + 1 ; k-- ) {
 				VectorCopy( grid->points[k][j], grid->points[k+2][j] );
 			}
 
 			// generate the subdivided points
 			CM_Subdivide( prev, mid, next, grid->points[i+1][j], grid->points[i+2][j], grid->points[i+3][j] );
 		}
 
 		grid->width += 2;
 
 		// the new aproximating point at i+1 may need to be removed
 		// or subdivided farther, so don't advance i
 	}
 }
 
 /*
 ======================
 CM_ComparePoints
 ======================
 */
 #define	POINT_EPSILON	0.1
 static qboolean CM_ComparePoints( float *a, float *b ) {
 	float		d;
 
 	d = a[0] - b[0];
 	if ( d < -POINT_EPSILON || d > POINT_EPSILON ) {
 		return qfalse;
 	}
 	d = a[1] - b[1];
 	if ( d < -POINT_EPSILON || d > POINT_EPSILON ) {
 		return qfalse;
 	}
 	d = a[2] - b[2];
 	if ( d < -POINT_EPSILON || d > POINT_EPSILON ) {
 		return qfalse;
 	}
 	return qtrue;
 }
 
 /*
 =================
 CM_RemoveDegenerateColumns
 
 If there are any identical columns, remove them
 =================
 */
 static void CM_RemoveDegenerateColumns( cGrid_t *grid ) {
 	int		i, j, k;
 
 	for ( i = 0 ; i < grid->width - 1 ; i++ ) {
 		for ( j = 0 ; j < grid->height ; j++ ) {
 			if ( !CM_ComparePoints( grid->points[i][j], grid->points[i+1][j] ) ) {
 				break;
 			}
 		}
 
 		if ( j != grid->height ) {
 			continue;	// not degenerate
 		}
 
 		for ( j = 0 ; j < grid->height ; j++ ) {
 			// remove the column
 			for ( k = i + 2 ; k < grid->width ; k++ ) {
 				VectorCopy( grid->points[k][j], grid->points[k-1][j] );
 			}
 		}
 		grid->width--;
 
 		// check against the next column
 		i--;
 	}
 }
 
 /*
 ================================================================================
 
 PATCH COLLIDE GENERATION
 
 ================================================================================
 */
 
 static	int				numPlanes;
 static	patchPlane_t	planes[MAX_PATCH_PLANES];
 
 static	int				numFacets;
 static	facet_t			facets[MAX_PATCH_PLANES]; //maybe MAX_FACETS ??
 
 #define	NORMAL_EPSILON	0.0001
 #define	DIST_EPSILON	0.02
 
 /*
 ==================
 CM_PlaneEqual
 ==================
 */
 int CM_PlaneEqual(patchPlane_t *p, float plane[4], int *flipped) {
 	float invplane[4];
 
 	if (
 	   fabs(p->plane[0] - plane[0]) < NORMAL_EPSILON
 	&& fabs(p->plane[1] - plane[1]) < NORMAL_EPSILON
 	&& fabs(p->plane[2] - plane[2]) < NORMAL_EPSILON
 	&& fabs(p->plane[3] - plane[3]) < DIST_EPSILON )
 	{
 		*flipped = qfalse;
 		return qtrue;
 	}
 
 	VectorNegate(plane, invplane);
 	invplane[3] = -plane[3];
 
 	if (
 	   fabs(p->plane[0] - invplane[0]) < NORMAL_EPSILON
 	&& fabs(p->plane[1] - invplane[1]) < NORMAL_EPSILON
 	&& fabs(p->plane[2] - invplane[2]) < NORMAL_EPSILON
 	&& fabs(p->plane[3] - invplane[3]) < DIST_EPSILON )
 	{
 		*flipped = qtrue;
 		return qtrue;
 	}
 
 	return qfalse;
 }
 
 /*
 ==================
 CM_SnapVector
 ==================
 */
 void CM_SnapVector(vec3_t normal) {
 	int		i;
 
 	for (i=0 ; i<3 ; i++)
 	{
 		if ( fabs(normal[i] - 1) < NORMAL_EPSILON )
 		{
 			VectorClear (normal);
 			normal[i] = 1;
 			break;
 		}
 		if ( fabs(normal[i] - -1) < NORMAL_EPSILON )
 		{
 			VectorClear (normal);
 			normal[i] = -1;
 			break;
 		}
 	}
 }
 
 /*
 ==================
 CM_FindPlane2
 ==================
 */
 int CM_FindPlane2(float plane[4], int *flipped) {
 	int i;
 
 	// see if the points are close enough to an existing plane
 	for ( i = 0 ; i < numPlanes ; i++ ) {
 		if (CM_PlaneEqual(&planes[i], plane, flipped)) return i;
 	}
 
 	// add a new plane
 	if ( numPlanes == MAX_PATCH_PLANES ) {
 		Com_Error( ERR_DROP, "MAX_PATCH_PLANES" );
 	}
 
 	Vector4Copy( plane, planes[numPlanes].plane );
 	planes[numPlanes].signbits = CM_SignbitsForNormal( plane );
 
 	numPlanes++;
 
 	*flipped = qfalse;
 
 	return numPlanes-1;
 }
 
 /*
 ==================
 CM_FindPlane
 ==================
 */
 static int CM_FindPlane( float *p1, float *p2, float *p3 ) {
 	float	plane[4];
 	int		i;
 	float	d;
 
 	if ( !CM_PlaneFromPoints( plane, p1, p2, p3 ) ) {
 		return -1;
 	}
 
 	// see if the points are close enough to an existing plane
 	for ( i = 0 ; i < numPlanes ; i++ ) {
 		if ( DotProduct( plane, planes[i].plane ) < 0 ) {
 			continue;	// allow backwards planes?
 		}
 
 		d = DotProduct( p1, planes[i].plane ) - planes[i].plane[3];
 		if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
 			continue;
 		}
 
 		d = DotProduct( p2, planes[i].plane ) - planes[i].plane[3];
 		if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
 			continue;
 		}
 
 		d = DotProduct( p3, planes[i].plane ) - planes[i].plane[3];
 		if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) {
 			continue;
 		}
 
 		// found it
 		return i;
 	}
 
 	// add a new plane
 	if ( numPlanes == MAX_PATCH_PLANES ) {
 		Com_Error( ERR_DROP, "MAX_PATCH_PLANES" );
 	}
 
 	Vector4Copy( plane, planes[numPlanes].plane );
 	planes[numPlanes].signbits = CM_SignbitsForNormal( plane );
 
 	numPlanes++;
 
 	return numPlanes-1;
 }
 
 /*
 ==================
 CM_PointOnPlaneSide
 ==================
 */
 static int CM_PointOnPlaneSide( float *p, int planeNum ) {
 	float	*plane;
 	float	d;
 
 	if ( planeNum == -1 ) {
 		return SIDE_ON;
 	}
 	plane = planes[ planeNum ].plane;
 
 	d = DotProduct( p, plane ) - plane[3];
 
 	if ( d > PLANE_TRI_EPSILON ) {
 		return SIDE_FRONT;
 	}
 
 	if ( d < -PLANE_TRI_EPSILON ) {
 		return SIDE_BACK;
 	}
 
 	return SIDE_ON;
 }
 
 /*
 ==================
 CM_GridPlane
 ==================
 */
 static int	CM_GridPlane( int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2], int i, int j, int tri ) {
 	int		p;
 
 	p = gridPlanes[i][j][tri];
 	if ( p != -1 ) {
 		return p;
 	}
 	p = gridPlanes[i][j][!tri];
 	if ( p != -1 ) {
 		return p;
 	}
 
 	// should never happen
 	Com_Printf( "WARNING: CM_GridPlane unresolvable\n" );
 	return -1;
 }
 
 /*
 ==================
 CM_EdgePlaneNum
 ==================
 */
 static int CM_EdgePlaneNum( cGrid_t *grid, int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2], int i, int j, int k ) {
 	float	*p1, *p2;
 	vec3_t		up;
 	int			p;
 
 	switch ( k ) {
 	case 0:	// top border
 		p1 = grid->points[i][j];
 		p2 = grid->points[i+1][j];
 		p = CM_GridPlane( gridPlanes, i, j, 0 );
 		VectorMA( p1, 4, planes[ p ].plane, up );
 		return CM_FindPlane( p1, p2, up );
 
 	case 2:	// bottom border
 		p1 = grid->points[i][j+1];
 		p2 = grid->points[i+1][j+1];
 		p = CM_GridPlane( gridPlanes, i, j, 1 );
 		VectorMA( p1, 4, planes[ p ].plane, up );
 		return CM_FindPlane( p2, p1, up );
 
 	case 3: // left border
 		p1 = grid->points[i][j];
 		p2 = grid->points[i][j+1];
 		p = CM_GridPlane( gridPlanes, i, j, 1 );
 		VectorMA( p1, 4, planes[ p ].plane, up );
 		return CM_FindPlane( p2, p1, up );
 
 	case 1:	// right border
 		p1 = grid->points[i+1][j];
 		p2 = grid->points[i+1][j+1];
 		p = CM_GridPlane( gridPlanes, i, j, 0 );
 		VectorMA( p1, 4, planes[ p ].plane, up );
 		return CM_FindPlane( p1, p2, up );
 
 	case 4:	// diagonal out of triangle 0
 		p1 = grid->points[i+1][j+1];
 		p2 = grid->points[i][j];
 		p = CM_GridPlane( gridPlanes, i, j, 0 );
 		VectorMA( p1, 4, planes[ p ].plane, up );
 		return CM_FindPlane( p1, p2, up );
 
 	case 5:	// diagonal out of triangle 1
 		p1 = grid->points[i][j];
 		p2 = grid->points[i+1][j+1];
 		p = CM_GridPlane( gridPlanes, i, j, 1 );
 		VectorMA( p1, 4, planes[ p ].plane, up );
 		return CM_FindPlane( p1, p2, up );
 
 	}
 
 	Com_Error( ERR_DROP, "CM_EdgePlaneNum: bad k" );
 	return -1;
 }
 
 /*
 ===================
 CM_SetBorderInward
 ===================
 */
 static void CM_SetBorderInward( facet_t *facet, cGrid_t *grid, int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2],
 						  int i, int j, int which ) {
 	int		k, l;
 	float	*points[4];
 	int		numPoints;
 
 	switch ( which ) {
 	case -1:
 		points[0] = grid->points[i][j];
 		points[1] = grid->points[i+1][j];
 		points[2] = grid->points[i+1][j+1];
 		points[3] = grid->points[i][j+1];
 		numPoints = 4;
 		break;
 	case 0:
 		points[0] = grid->points[i][j];
 		points[1] = grid->points[i+1][j];
 		points[2] = grid->points[i+1][j+1];
 		numPoints = 3;
 		break;
 	case 1:
 		points[0] = grid->points[i+1][j+1];
 		points[1] = grid->points[i][j+1];
 		points[2] = grid->points[i][j];
 		numPoints = 3;
 		break;
 	default:
 		Com_Error( ERR_FATAL, "CM_SetBorderInward: bad parameter" );
 		numPoints = 0;
 		break;
 	}
 
 	for ( k = 0 ; k < facet->numBorders ; k++ ) {
 		int		front, back;
 
 		front = 0;
 		back = 0;
 
 		for ( l = 0 ; l < numPoints ; l++ ) {
 			int		side;
 
 			side = CM_PointOnPlaneSide( points[l], facet->borderPlanes[k] );
 			if ( side == SIDE_FRONT ) {
 				front++;
 			} if ( side == SIDE_BACK ) {
 				back++;
 			}
 		}
 
 		if ( front && !back ) {
 			facet->borderInward[k] = qtrue;
 		} else if ( back && !front ) {
 			facet->borderInward[k] = qfalse;
 		} else if ( !front && !back ) {
 			// flat side border
 			facet->borderPlanes[k] = -1;
 		} else {
 			// bisecting side border
 			Com_DPrintf( "WARNING: CM_SetBorderInward: mixed plane sides\n" );
 			facet->borderInward[k] = qfalse;
 			if ( !debugBlock ) {
 				debugBlock = qtrue;
 				VectorCopy( grid->points[i][j], debugBlockPoints[0] );
 				VectorCopy( grid->points[i+1][j], debugBlockPoints[1] );
 				VectorCopy( grid->points[i+1][j+1], debugBlockPoints[2] );
 				VectorCopy( grid->points[i][j+1], debugBlockPoints[3] );
 			}
 		}
 	}
 }
 
 /*
 ==================
 CM_ValidateFacet
 
 If the facet isn't bounded by its borders, we screwed up.
 ==================
 */
 static qboolean CM_ValidateFacet( facet_t *facet ) {
 	float		plane[4];
 	int			j;
 	winding_t	*w;
 	vec3_t		bounds[2];
 
 	if ( facet->surfacePlane == -1 ) {
 		return qfalse;
 	}
 
 	Vector4Copy( planes[ facet->surfacePlane ].plane, plane );
 	w = BaseWindingForPlane( plane,  plane[3] );
 	for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
 		if ( facet->borderPlanes[j] == -1 ) {
 			return qfalse;
 		}
 		Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane );
 		if ( !facet->borderInward[j] ) {
 			VectorSubtract( vec3_origin, plane, plane );
 			plane[3] = -plane[3];
 		}
 		ChopWindingInPlace( &w, plane, plane[3], 0.1f );
 	}
 
 	if ( !w ) {
 		return qfalse;		// winding was completely chopped away
 	}
 
 	// see if the facet is unreasonably large
 	WindingBounds( w, bounds[0], bounds[1] );
 	FreeWinding( w );
 	
 	for ( j = 0 ; j < 3 ; j++ ) {
 		if ( bounds[1][j] - bounds[0][j] > MAX_MAP_BOUNDS ) {
 			return qfalse;		// we must be missing a plane
 		}
 		if ( bounds[0][j] >= MAX_MAP_BOUNDS ) {
 			return qfalse;
 		}
 		if ( bounds[1][j] <= -MAX_MAP_BOUNDS ) {
 			return qfalse;
 		}
 	}
 	return qtrue;		// winding is fine
 }
 
 /*
 ==================
 CM_AddFacetBevels
 ==================
 */
 void CM_AddFacetBevels( facet_t *facet ) {
 
 	int i, j, k, l;
 	int axis, dir, order, flipped;
 	float plane[4], d, newplane[4];
 	winding_t *w, *w2;
 	vec3_t mins, maxs, vec, vec2;
 
 	Vector4Copy( planes[ facet->surfacePlane ].plane, plane );
 
 	w = BaseWindingForPlane( plane,  plane[3] );
 	for ( j = 0 ; j < facet->numBorders && w ; j++ ) {
 		if (facet->borderPlanes[j] == facet->surfacePlane) continue;
 		Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane );
 
 		if ( !facet->borderInward[j] ) {
 			VectorSubtract( vec3_origin, plane, plane );
 			plane[3] = -plane[3];
 		}
 
 		ChopWindingInPlace( &w, plane, plane[3], 0.1f );
 	}
 	if ( !w ) {
 		return;
 	}
 
 	WindingBounds(w, mins, maxs);
 
 	// add the axial planes
 	order = 0;
 	for ( axis = 0 ; axis < 3 ; axis++ )
 	{
 		for ( dir = -1 ; dir <= 1 ; dir += 2, order++ )
 		{
 			VectorClear(plane);
 			plane[axis] = dir;
 			if (dir == 1) {
 				plane[3] = maxs[axis];
 			}
 			else {
 				plane[3] = -mins[axis];
 			}
 			//if it's the surface plane
 			if (CM_PlaneEqual(&planes[facet->surfacePlane], plane, &flipped)) {
 				continue;
 			}
 			// see if the plane is allready present
 			for ( i = 0 ; i < facet->numBorders ; i++ ) {
 				if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped))
 					break;
 			}
 
 			if ( i == facet->numBorders ) {
 				if (facet->numBorders > 4 + 6 + 16) Com_Printf("ERROR: too many bevels\n");
 				facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped);
 				facet->borderNoAdjust[facet->numBorders] = 0;
 				facet->borderInward[facet->numBorders] = flipped;
 				facet->numBorders++;
 			}
 		}
 	}
 	//
 	// add the edge bevels
 	//
 	// test the non-axial plane edges
 	for ( j = 0 ; j < w->numpoints ; j++ )
 	{
 		k = (j+1)%w->numpoints;
 		VectorSubtract (w->p[j], w->p[k], vec);
 		//if it's a degenerate edge
 		if (VectorNormalize (vec) < 0.5)
 			continue;
 		CM_SnapVector(vec);
 		for ( k = 0; k < 3 ; k++ )
 			if ( vec[k] == -1 || vec[k] == 1 )
 				break;	// axial
 		if ( k < 3 )
 			continue;	// only test non-axial edges
 
 		// try the six possible slanted axials from this edge
 		for ( axis = 0 ; axis < 3 ; axis++ )
 		{
 			for ( dir = -1 ; dir <= 1 ; dir += 2 )
 			{
 				// construct a plane
 				VectorClear (vec2);
 				vec2[axis] = dir;
 				CrossProduct (vec, vec2, plane);
 				if (VectorNormalize (plane) < 0.5)
 					continue;
 				plane[3] = DotProduct (w->p[j], plane);
 
 				// if all the points of the facet winding are
 				// behind this plane, it is a proper edge bevel
 				for ( l = 0 ; l < w->numpoints ; l++ )
 				{
 					d = DotProduct (w->p[l], plane) - plane[3];
 					if (d > 0.1)
 						break;	// point in front
 				}
 				if ( l < w->numpoints )
 					continue;
 
 				//if it's the surface plane
 				if (CM_PlaneEqual(&planes[facet->surfacePlane], plane, &flipped)) {
 					continue;
 				}
 				// see if the plane is allready present
 				for ( i = 0 ; i < facet->numBorders ; i++ ) {
 					if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped)) {
 							break;
 					}
 				}
 
 				if ( i == facet->numBorders ) {
 					if (facet->numBorders > 4 + 6 + 16) Com_Printf("ERROR: too many bevels\n");
 					facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped);
 
 					for ( k = 0 ; k < facet->numBorders ; k++ ) {
 						if (facet->borderPlanes[facet->numBorders] ==
 							facet->borderPlanes[k]) Com_Printf("WARNING: bevel plane already used\n");
 					}
 
 					facet->borderNoAdjust[facet->numBorders] = 0;
 					facet->borderInward[facet->numBorders] = flipped;
 					//
 					w2 = CopyWinding(w);
 					Vector4Copy(planes[facet->borderPlanes[facet->numBorders]].plane, newplane);
 					if (!facet->borderInward[facet->numBorders])
 					{
 						VectorNegate(newplane, newplane);
 						newplane[3] = -newplane[3];
 					} //end if
 					ChopWindingInPlace( &w2, newplane, newplane[3], 0.1f );
 					if (!w2) {
 						Com_DPrintf("WARNING: CM_AddFacetBevels... invalid bevel\n");
 						continue;
 					}
 					else {
 						FreeWinding(w2);
 					}
 					//
 					facet->numBorders++;
 					//already got a bevel
 //					break;
 				}
 			}
 		}
 	}
 	FreeWinding( w );
 
 #ifndef BSPC
 	//add opposite plane
 	facet->borderPlanes[facet->numBorders] = facet->surfacePlane;
 	facet->borderNoAdjust[facet->numBorders] = 0;
 	facet->borderInward[facet->numBorders] = qtrue;
 	facet->numBorders++;
 #endif //BSPC
 
 }
 
 typedef enum {
 	EN_TOP,
 	EN_RIGHT,
 	EN_BOTTOM,
 	EN_LEFT
 } edgeName_t;
 
 /*
 ==================
 CM_PatchCollideFromGrid
 ==================
 */
 static void CM_PatchCollideFromGrid( cGrid_t *grid, patchCollide_t *pf ) {
 	int				i, j;
 	float			*p1, *p2, *p3;
 	MAC_STATIC int				gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2];
 	facet_t			*facet;
 	int				borders[4];
 	int				noAdjust[4];
 
 	numPlanes = 0;
 	numFacets = 0;
 
 	// find the planes for each triangle of the grid
 	for ( i = 0 ; i < grid->width - 1 ; i++ ) {
 		for ( j = 0 ; j < grid->height - 1 ; j++ ) {
 			p1 = grid->points[i][j];
 			p2 = grid->points[i+1][j];
 			p3 = grid->points[i+1][j+1];
 			gridPlanes[i][j][0] = CM_FindPlane( p1, p2, p3 );
 
 			p1 = grid->points[i+1][j+1];
 			p2 = grid->points[i][j+1];
 			p3 = grid->points[i][j];
 			gridPlanes[i][j][1] = CM_FindPlane( p1, p2, p3 );
 		}
 	}
 
 	// create the borders for each facet
 	for ( i = 0 ; i < grid->width - 1 ; i++ ) {
 		for ( j = 0 ; j < grid->height - 1 ; j++ ) {
 			 
 			borders[EN_TOP] = -1;
 			if ( j > 0 ) {
 				borders[EN_TOP] = gridPlanes[i][j-1][1];
 			} else if ( grid->wrapHeight ) {
 				borders[EN_TOP] = gridPlanes[i][grid->height-2][1];
 			} 
 			noAdjust[EN_TOP] = ( borders[EN_TOP] == gridPlanes[i][j][0] );
 			if ( borders[EN_TOP] == -1 || noAdjust[EN_TOP] ) {
 				borders[EN_TOP] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 0 );
 			}
 
 			borders[EN_BOTTOM] = -1;
 			if ( j < grid->height - 2 ) {
 				borders[EN_BOTTOM] = gridPlanes[i][j+1][0];
 			} else if ( grid->wrapHeight ) {
 				borders[EN_BOTTOM] = gridPlanes[i][0][0];
 			}
 			noAdjust[EN_BOTTOM] = ( borders[EN_BOTTOM] == gridPlanes[i][j][1] );
 			if ( borders[EN_BOTTOM] == -1 || noAdjust[EN_BOTTOM] ) {
 				borders[EN_BOTTOM] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 2 );
 			}
 
 			borders[EN_LEFT] = -1;
 			if ( i > 0 ) {
 				borders[EN_LEFT] = gridPlanes[i-1][j][0];
 			} else if ( grid->wrapWidth ) {
 				borders[EN_LEFT] = gridPlanes[grid->width-2][j][0];
 			}
 			noAdjust[EN_LEFT] = ( borders[EN_LEFT] == gridPlanes[i][j][1] );
 			if ( borders[EN_LEFT] == -1 || noAdjust[EN_LEFT] ) {
 				borders[EN_LEFT] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 3 );
 			}
 
 			borders[EN_RIGHT] = -1;
 			if ( i < grid->width - 2 ) {
 				borders[EN_RIGHT] = gridPlanes[i+1][j][1];
 			} else if ( grid->wrapWidth ) {
 				borders[EN_RIGHT] = gridPlanes[0][j][1];
 			}
 			noAdjust[EN_RIGHT] = ( borders[EN_RIGHT] == gridPlanes[i][j][0] );
 			if ( borders[EN_RIGHT] == -1 || noAdjust[EN_RIGHT] ) {
 				borders[EN_RIGHT] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 1 );
 			}
 
 			if ( numFacets == MAX_FACETS ) {
 				Com_Error( ERR_DROP, "MAX_FACETS" );
 			}
 			facet = &facets[numFacets];
 			Com_Memset( facet, 0, sizeof( *facet ) );
 
 			if ( gridPlanes[i][j][0] == gridPlanes[i][j][1] ) {
 				if ( gridPlanes[i][j][0] == -1 ) {
 					continue;		// degenrate
 				}
 				facet->surfacePlane = gridPlanes[i][j][0];
 				facet->numBorders = 4;
 				facet->borderPlanes[0] = borders[EN_TOP];
 				facet->borderNoAdjust[0] = noAdjust[EN_TOP];
 				facet->borderPlanes[1] = borders[EN_RIGHT];
 				facet->borderNoAdjust[1] = noAdjust[EN_RIGHT];
 				facet->borderPlanes[2] = borders[EN_BOTTOM];
 				facet->borderNoAdjust[2] = noAdjust[EN_BOTTOM];
 				facet->borderPlanes[3] = borders[EN_LEFT];
 				facet->borderNoAdjust[3] = noAdjust[EN_LEFT];
 				CM_SetBorderInward( facet, grid, gridPlanes, i, j, -1 );
 				if ( CM_ValidateFacet( facet ) ) {
 					CM_AddFacetBevels( facet );
 					numFacets++;
 				}
 			} else {
 				// two seperate triangles
 				facet->surfacePlane = gridPlanes[i][j][0];
 				facet->numBorders = 3;
 				facet->borderPlanes[0] = borders[EN_TOP];
 				facet->borderNoAdjust[0] = noAdjust[EN_TOP];
 				facet->borderPlanes[1] = borders[EN_RIGHT];
 				facet->borderNoAdjust[1] = noAdjust[EN_RIGHT];
 				facet->borderPlanes[2] = gridPlanes[i][j][1];
 				if ( facet->borderPlanes[2] == -1 ) {
 					facet->borderPlanes[2] = borders[EN_BOTTOM];
 					if ( facet->borderPlanes[2] == -1 ) {
 						facet->borderPlanes[2] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 4 );
 					}
 				}
  				CM_SetBorderInward( facet, grid, gridPlanes, i, j, 0 );
 				if ( CM_ValidateFacet( facet ) ) {
 					CM_AddFacetBevels( facet );
 					numFacets++;
 				}
 
 				if ( numFacets == MAX_FACETS ) {
 					Com_Error( ERR_DROP, "MAX_FACETS" );
 				}
 				facet = &facets[numFacets];
 				Com_Memset( facet, 0, sizeof( *facet ) );
 
 				facet->surfacePlane = gridPlanes[i][j][1];
 				facet->numBorders = 3;
 				facet->borderPlanes[0] = borders[EN_BOTTOM];
 				facet->borderNoAdjust[0] = noAdjust[EN_BOTTOM];
 				facet->borderPlanes[1] = borders[EN_LEFT];
 				facet->borderNoAdjust[1] = noAdjust[EN_LEFT];
 				facet->borderPlanes[2] = gridPlanes[i][j][0];
 				if ( facet->borderPlanes[2] == -1 ) {
 					facet->borderPlanes[2] = borders[EN_TOP];
 					if ( facet->borderPlanes[2] == -1 ) {
 						facet->borderPlanes[2] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 5 );
 					}
 				}
 				CM_SetBorderInward( facet, grid, gridPlanes, i, j, 1 );
 				if ( CM_ValidateFacet( facet ) ) {
 					CM_AddFacetBevels( facet );
 					numFacets++;
 				}
 			}
 		}
 	}
 
 	// copy the results out
 	pf->numPlanes = numPlanes;
 	pf->numFacets = numFacets;
 	pf->facets = Hunk_Alloc( numFacets * sizeof( *pf->facets ), h_high );
 	Com_Memcpy( pf->facets, facets, numFacets * sizeof( *pf->facets ) );
 	pf->planes = Hunk_Alloc( numPlanes * sizeof( *pf->planes ), h_high );
 	Com_Memcpy( pf->planes, planes, numPlanes * sizeof( *pf->planes ) );
 }
 
 
 /*
 ===================
 CM_GeneratePatchCollide
 
 Creates an internal structure that will be used to perform
 collision detection with a patch mesh.
 
 Points is packed as concatenated rows.
 ===================
 */
 struct patchCollide_s	*CM_GeneratePatchCollide( int width, int height, vec3_t *points ) {
 	patchCollide_t	*pf;
 	MAC_STATIC cGrid_t			grid;
 	int				i, j;
 
 	if ( width <= 2 || height <= 2 || !points ) {
 		Com_Error( ERR_DROP, "CM_GeneratePatchFacets: bad parameters: (%i, %i, %p)",
 			width, height, points );
 	}
 
 	if ( !(width & 1) || !(height & 1) ) {
 		Com_Error( ERR_DROP, "CM_GeneratePatchFacets: even sizes are invalid for quadratic meshes" );
 	}
 
 	if ( width > MAX_GRID_SIZE || height > MAX_GRID_SIZE ) {
 		Com_Error( ERR_DROP, "CM_GeneratePatchFacets: source is > MAX_GRID_SIZE" );
 	}
 
 	// build a grid
 	grid.width = width;
 	grid.height = height;
 	grid.wrapWidth = qfalse;
 	grid.wrapHeight = qfalse;
 	for ( i = 0 ; i < width ; i++ ) {
 		for ( j = 0 ; j < height ; j++ ) {
 			VectorCopy( points[j*width + i], grid.points[i][j] );
 		}
 	}
 
 	// subdivide the grid
 	CM_SetGridWrapWidth( &grid );
 	CM_SubdivideGridColumns( &grid );
 	CM_RemoveDegenerateColumns( &grid );
 
 	CM_TransposeGrid( &grid );
 
 	CM_SetGridWrapWidth( &grid );
 	CM_SubdivideGridColumns( &grid );
 	CM_RemoveDegenerateColumns( &grid );
 
 	// we now have a grid of points exactly on the curve
 	// the aproximate surface defined by these points will be
 	// collided against
 	pf = Hunk_Alloc( sizeof( *pf ), h_high );
 	ClearBounds( pf->bounds[0], pf->bounds[1] );
 	for ( i = 0 ; i < grid.width ; i++ ) {
 		for ( j = 0 ; j < grid.height ; j++ ) {
 			AddPointToBounds( grid.points[i][j], pf->bounds[0], pf->bounds[1] );
 		}
 	}
 
 	c_totalPatchBlocks += ( grid.width - 1 ) * ( grid.height - 1 );
 
 	// generate a bsp tree for the surface
 	CM_PatchCollideFromGrid( &grid, pf );
 
 	// expand by one unit for epsilon purposes
 	pf->bounds[0][0] -= 1;
 	pf->bounds[0][1] -= 1;
 	pf->bounds[0][2] -= 1;
 
 	pf->bounds[1][0] += 1;
 	pf->bounds[1][1] += 1;
 	pf->bounds[1][2] += 1;
 
 	return pf;
 }
 
 /*
 ================================================================================
 
 TRACE TESTING
 
 ================================================================================
 */
 
 /*
 ====================
 CM_TracePointThroughPatchCollide
 
   special case for point traces because the patch collide "brushes" have no volume
 ====================
 */
 void CM_TracePointThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) {
 	qboolean	frontFacing[MAX_PATCH_PLANES];
 	float		intersection[MAX_PATCH_PLANES];
 	float		intersect;
 	const patchPlane_t	*planes;
 	const facet_t	*facet;
 	int			i, j, k;
 	float		offset;
 	float		d1, d2;
 #ifndef BSPC
 	static cvar_t *cv;
 #endif //BSPC
 
 #ifndef BSPC
 	if ( !cm_playerCurveClip->integer || !tw->isPoint ) {
 		return;
 	}
 #endif
 
 	// determine the trace's relationship to all planes
 	planes = pc->planes;
 	for ( i = 0 ; i < pc->numPlanes ; i++, planes++ ) {
 		offset = DotProduct( tw->offsets[ planes->signbits ], planes->plane );
 		d1 = DotProduct( tw->start, planes->plane ) - planes->plane[3] + offset;
 		d2 = DotProduct( tw->end, planes->plane ) - planes->plane[3] + offset;
 		if ( d1 <= 0 ) {
 			frontFacing[i] = qfalse;
 		} else {
 			frontFacing[i] = qtrue;
 		}
 		if ( d1 == d2 ) {
 			intersection[i] = 99999;
 		} else {
 			intersection[i] = d1 / ( d1 - d2 );
 			if ( intersection[i] <= 0 ) {
 				intersection[i] = 99999;
 			}
 		}
 	}
 
 
 	// see if any of the surface planes are intersected
 	facet = pc->facets;
 	for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) {
 		if ( !frontFacing[facet->surfacePlane] ) {
 			continue;
 		}
 		intersect = intersection[facet->surfacePlane];
 		if ( intersect < 0 ) {
 			continue;		// surface is behind the starting point
 		}
 		if ( intersect > tw->trace.fraction ) {
 			continue;		// already hit something closer
 		}
 		for ( j = 0 ; j < facet->numBorders ; j++ ) {
 			k = facet->borderPlanes[j];
 			if ( frontFacing[k] ^ facet->borderInward[j] ) {
 				if ( intersection[k] > intersect ) {
 					break;
 				}
 			} else {
 				if ( intersection[k] < intersect ) {
 					break;
 				}
 			}
 		}
 		if ( j == facet->numBorders ) {
 			// we hit this facet
 #ifndef BSPC
 			if (!cv) {
 				cv = Cvar_Get( "r_debugSurfaceUpdate", "1", 0 );
 			}
 			if (cv->integer) {
 				debugPatchCollide = pc;
 				debugFacet = facet;
 			}
 #endif //BSPC
 			planes = &pc->planes[facet->surfacePlane];
 
 			// calculate intersection with a slight pushoff
 			offset = DotProduct( tw->offsets[ planes->signbits ], planes->plane );
 			d1 = DotProduct( tw->start, planes->plane ) - planes->plane[3] + offset;
 			d2 = DotProduct( tw->end, planes->plane ) - planes->plane[3] + offset;
 			tw->trace.fraction = ( d1 - SURFACE_CLIP_EPSILON ) / ( d1 - d2 );
 
 			if ( tw->trace.fraction < 0 ) {
 				tw->trace.fraction = 0;
 			}
 
 			VectorCopy( planes->plane,  tw->trace.plane.normal );
 			tw->trace.plane.dist = planes->plane[3];
 		}
 	}
 }
 
 /*
 ====================
 CM_CheckFacetPlane
 ====================
 */
 int CM_CheckFacetPlane(float *plane, vec3_t start, vec3_t end, float *enterFrac, float *leaveFrac, int *hit) {
 	float d1, d2, f;
 
 	*hit = qfalse;
 
 	d1 = DotProduct( start, plane ) - plane[3];
 	d2 = DotProduct( end, plane ) - plane[3];
 
 	// if completely in front of face, no intersection with the entire facet
 	if (d1 > 0 && ( d2 >= SURFACE_CLIP_EPSILON || d2 >= d1 )  ) {
 		return qfalse;
 	}
 
 	// if it doesn't cross the plane, the plane isn't relevent
 	if (d1 <= 0 && d2 <= 0 ) {
 		return qtrue;
 	}
 
 	// crosses face
 	if (d1 > d2) {	// enter
 		f = (d1-SURFACE_CLIP_EPSILON) / (d1-d2);
 		if ( f < 0 ) {
 			f = 0;
 		}
 		//always favor previous plane hits and thus also the surface plane hit
 		if (f > *enterFrac) {
 			*enterFrac = f;
 			*hit = qtrue;
 		}
 	} else {	// leave
 		f = (d1+SURFACE_CLIP_EPSILON) / (d1-d2);
 		if ( f > 1 ) {
 			f = 1;
 		}
 		if (f < *leaveFrac) {
 			*leaveFrac = f;
 		}
 	}
 	return qtrue;
 }
 
 /*
 ====================
 CM_TraceThroughPatchCollide
 ====================
 */
 void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) {
 	int i, j, hit, hitnum;
 	float offset, enterFrac, leaveFrac, t;
 	patchPlane_t *planes;
 	facet_t	*facet;
 	float plane[4], bestplane[4];
 	vec3_t startp, endp;
 #ifndef BSPC
 	static cvar_t *cv;
 #endif //BSPC
 
 	if (tw->isPoint) {
 		CM_TracePointThroughPatchCollide( tw, pc );
 		return;
 	}
 
 	facet = pc->facets;
 	for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) {
 		enterFrac = -1.0;
 		leaveFrac = 1.0;
 		hitnum = -1;
 		//
 		planes = &pc->planes[ facet->surfacePlane ];
 		VectorCopy(planes->plane, plane);
 		plane[3] = planes->plane[3];
 		if ( tw->sphere.use ) {
 			// adjust the plane distance apropriately for radius
 			plane[3] += tw->sphere.radius;
 
 			// find the closest point on the capsule to the plane
 			t = DotProduct( plane, tw->sphere.offset );
 			if ( t > 0.0f ) {
 				VectorSubtract( tw->start, tw->sphere.offset, startp );
 				VectorSubtract( tw->end, tw->sphere.offset, endp );
 			}
 			else {
 				VectorAdd( tw->start, tw->sphere.offset, startp );
 				VectorAdd( tw->end, tw->sphere.offset, endp );
 			}
 		}
 		else {
 			offset = DotProduct( tw->offsets[ planes->signbits ], plane);
 			plane[3] -= offset;
 			VectorCopy( tw->start, startp );
 			VectorCopy( tw->end, endp );
 		}
 
 		if (!CM_CheckFacetPlane(plane, startp, endp, &enterFrac, &leaveFrac, &hit)) {
 			continue;
 		}
 		if (hit) {
 			Vector4Copy(plane, bestplane);
 		}
 
 		for ( j = 0; j < facet->numBorders; j++ ) {
 			planes = &pc->planes[ facet->borderPlanes[j] ];
 			if (facet->borderInward[j]) {
 				VectorNegate(planes->plane, plane);
 				plane[3] = -planes->plane[3];
 			}
 			else {
 				VectorCopy(planes->plane, plane);
 				plane[3] = planes->plane[3];
 			}
 			if ( tw->sphere.use ) {
 				// adjust the plane distance apropriately for radius
 				plane[3] += tw->sphere.radius;
 
 				// find the closest point on the capsule to the plane
 				t = DotProduct( plane, tw->sphere.offset );
 				if ( t > 0.0f ) {
 					VectorSubtract( tw->start, tw->sphere.offset, startp );
 					VectorSubtract( tw->end, tw->sphere.offset, endp );
 				}
 				else {
 					VectorAdd( tw->start, tw->sphere.offset, startp );
 					VectorAdd( tw->end, tw->sphere.offset, endp );
 				}
 			}
 			else {
 				// NOTE: this works even though the plane might be flipped because the bbox is centered
 				offset = DotProduct( tw->offsets[ planes->signbits ], plane);
 				plane[3] += fabs(offset);
 				VectorCopy( tw->start, startp );
 				VectorCopy( tw->end, endp );
 			}
 
 			if (!CM_CheckFacetPlane(plane, startp, endp, &enterFrac, &leaveFrac, &hit)) {
 				break;
 			}
 			if (hit) {
 				hitnum = j;
 				Vector4Copy(plane, bestplane);
 			}
 		}
 		if (j < facet->numBorders) continue;
 		//never clip against the back side
 		if (hitnum == facet->numBorders - 1) continue;
 
 		if (enterFrac < leaveFrac && enterFrac >= 0) {
 			if (enterFrac < tw->trace.fraction) {
 				if (enterFrac < 0) {
 					enterFrac = 0;
 				}
 #ifndef BSPC
 				if (!cv) {
 					cv = Cvar_Get( "r_debugSurfaceUpdate", "1", 0 );
 				}
 				if (cv && cv->integer) {
 					debugPatchCollide = pc;
 					debugFacet = facet;
 				}
 #endif //BSPC
 
 				tw->trace.fraction = enterFrac;
 				VectorCopy( bestplane, tw->trace.plane.normal );
 				tw->trace.plane.dist = bestplane[3];
 			}
 		}
 	}
 }
 
 
 /*
 =======================================================================
 
 POSITION TEST
 
 =======================================================================
 */
 
 /*
 ====================
 CM_PositionTestInPatchCollide
 ====================
 */
 qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) {
 	int i, j;
 	float offset, t;
 	patchPlane_t *planes;
 	facet_t	*facet;
 	float plane[4];
 	vec3_t startp;
 
 	if (tw->isPoint) {
 		return qfalse;
 	}
 	//
 	facet = pc->facets;
 	for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) {
 		planes = &pc->planes[ facet->surfacePlane ];
 		VectorCopy(planes->plane, plane);
 		plane[3] = planes->plane[3];
 		if ( tw->sphere.use ) {
 			// adjust the plane distance apropriately for radius
 			plane[3] += tw->sphere.radius;
 
 			// find the closest point on the capsule to the plane
 			t = DotProduct( plane, tw->sphere.offset );
 			if ( t > 0 ) {
 				VectorSubtract( tw->start, tw->sphere.offset, startp );
 			}
 			else {
 				VectorAdd( tw->start, tw->sphere.offset, startp );
 			}
 		}
 		else {
 			offset = DotProduct( tw->offsets[ planes->signbits ], plane);
 			plane[3] -= offset;
 			VectorCopy( tw->start, startp );
 		}
 
 		if ( DotProduct( plane, startp ) - plane[3] > 0.0f ) {
 			continue;
 		}
 
 		for ( j = 0; j < facet->numBorders; j++ ) {
 			planes = &pc->planes[ facet->borderPlanes[j] ];
 			if (facet->borderInward[j]) {
 				VectorNegate(planes->plane, plane);
 				plane[3] = -planes->plane[3];
 			}
 			else {
 				VectorCopy(planes->plane, plane);
 				plane[3] = planes->plane[3];
 			}
 			if ( tw->sphere.use ) {
 				// adjust the plane distance apropriately for radius
 				plane[3] += tw->sphere.radius;
 
 				// find the closest point on the capsule to the plane
 				t = DotProduct( plane, tw->sphere.offset );
 				if ( t > 0.0f ) {
 					VectorSubtract( tw->start, tw->sphere.offset, startp );
 				}
 				else {
 					VectorAdd( tw->start, tw->sphere.offset, startp );
 				}
 			}
 			else {
 				// NOTE: this works even though the plane might be flipped because the bbox is centered
 				offset = DotProduct( tw->offsets[ planes->signbits ], plane);
 				plane[3] += fabs(offset);
 				VectorCopy( tw->start, startp );
 			}
 
 			if ( DotProduct( plane, startp ) - plane[3] > 0.0f ) {
 				break;
 			}
 		}
 		if (j < facet->numBorders) {
 			continue;
 		}
 		// inside this patch facet
 		return qtrue;
 	}
 	return qfalse;
 }
 
 /*
 =======================================================================
 
 DEBUGGING
 
 =======================================================================
 */
 
 
 /*
 ==================
 CM_DrawDebugSurface
 
 Called from the renderer
 ==================
 */
 #ifndef BSPC
 void BotDrawDebugPolygons(void (*drawPoly)(int color, int numPoints, float *points), int value);
 #endif
 
 void CM_DrawDebugSurface( void (*drawPoly)(int color, int numPoints, float *points) ) {
 	static cvar_t	*cv;
 #ifndef BSPC
 	static cvar_t	*cv2;
 #endif
 	const patchCollide_t	*pc;
 	facet_t			*facet;
 	winding_t		*w;
 	int				i, j, k, n;
 	int				curplanenum, planenum, curinward, inward;
 	float			plane[4];
 	vec3_t mins = {-15, -15, -28}, maxs = {15, 15, 28};
 	//vec3_t mins = {0, 0, 0}, maxs = {0, 0, 0};
 	vec3_t v1, v2;
 
 #ifndef BSPC
 	if ( !cv2 )
 	{
 		cv2 = Cvar_Get( "r_debugSurface", "0", 0 );
 	}
 
 	if (cv2->integer != 1)
 	{
 		BotDrawDebugPolygons(drawPoly, cv2->integer);
 		return;
 	}
 #endif
 
 	if ( !debugPatchCollide ) {
 		return;
 	}
 
 #ifndef BSPC
 	if ( !cv ) {
 		cv = Cvar_Get( "cm_debugSize", "2", 0 );
 	}
 #endif
 	pc = debugPatchCollide;
 
 	for ( i = 0, facet = pc->facets ; i < pc->numFacets ; i++, facet++ ) {
 
 		for ( k = 0 ; k < facet->numBorders + 1; k++ ) {
 			//
 			if (k < facet->numBorders) {
 				planenum = facet->borderPlanes[k];
 				inward = facet->borderInward[k];
 			}
 			else {
 				planenum = facet->surfacePlane;
 				inward = qfalse;
 				//continue;
 			}
 
 			Vector4Copy( pc->planes[ planenum ].plane, plane );
 
 			//planenum = facet->surfacePlane;
 			if ( inward ) {
 				VectorSubtract( vec3_origin, plane, plane );
 				plane[3] = -plane[3];
 			}
 
 			plane[3] += cv->value;
 			//*
 			for (n = 0; n < 3; n++)
 			{
 				if (plane[n] > 0) v1[n] = maxs[n];
 				else v1[n] = mins[n];
 			} //end for
 			VectorNegate(plane, v2);
 			plane[3] += fabs(DotProduct(v1, v2));
 			//*/
 
 			w = BaseWindingForPlane( plane,  plane[3] );
 			for ( j = 0 ; j < facet->numBorders + 1 && w; j++ ) {
 				//
 				if (j < facet->numBorders) {
 					curplanenum = facet->borderPlanes[j];
 					curinward = facet->borderInward[j];
 				}
 				else {
 					curplanenum = facet->surfacePlane;
 					curinward = qfalse;
 					//continue;
 				}
 				//
 				if (curplanenum == planenum) continue;
 
 				Vector4Copy( pc->planes[ curplanenum ].plane, plane );
 				if ( !curinward ) {
 					VectorSubtract( vec3_origin, plane, plane );
 					plane[3] = -plane[3];
 				}
 		//			if ( !facet->borderNoAdjust[j] ) {
 					plane[3] -= cv->value;
 		//			}
 				for (n = 0; n < 3; n++)
 				{
 					if (plane[n] > 0) v1[n] = maxs[n];
 					else v1[n] = mins[n];
 				} //end for
 				VectorNegate(plane, v2);
 				plane[3] -= fabs(DotProduct(v1, v2));
 
 				ChopWindingInPlace( &w, plane, plane[3], 0.1f );
 			}
 			if ( w ) {
 				if ( facet == debugFacet ) {
 					drawPoly( 4, w->numpoints, w->p[0] );
 					//Com_Printf("blue facet has %d border planes\n", facet->numBorders);
 				} else {
 					drawPoly( 1, w->numpoints, w->p[0] );
 				}
 				FreeWinding( w );
 			}
 			else
 				Com_Printf("winding chopped away by border planes\n");
 		}
 	}
 
 	// draw the debug block
 	{
 		vec3_t			v[3];
 
 		VectorCopy( debugBlockPoints[0], v[0] );
 		VectorCopy( debugBlockPoints[1], v[1] );
 		VectorCopy( debugBlockPoints[2], v[2] );
 		drawPoly( 2, 3, v[0] );
 
 		VectorCopy( debugBlockPoints[2], v[0] );
 		VectorCopy( debugBlockPoints[3], v[1] );
 		VectorCopy( debugBlockPoints[0], v[2] );
 		drawPoly( 2, 3, v[0] );
 	}
 
 #if 0
 	vec3_t			v[4];
 
 	v[0][0] = pc->bounds[1][0];
 	v[0][1] = pc->bounds[1][1];
 	v[0][2] = pc->bounds[1][2];
 
 	v[1][0] = pc->bounds[1][0];
 	v[1][1] = pc->bounds[0][1];
 	v[1][2] = pc->bounds[1][2];
 
 	v[2][0] = pc->bounds[0][0];
 	v[2][1] = pc->bounds[0][1];
 	v[2][2] = pc->bounds[1][2];
 
 	v[3][0] = pc->bounds[0][0];
 	v[3][1] = pc->bounds[1][1];
 	v[3][2] = pc->bounds[1][2];
 
 	drawPoly( 4, v[0] );
 #endif
 }