level/winding.c
/*
==================
DivideWindingEpsilon

Divides a winding by a plane, producing one or two windings. The
original winding is not damaged or freed. If only on one side, the
returned winding will be the input winding. If on both sides, two
new windings will be created.
==================
*/
DivideWindingEpsilon
Divides a winding by a plane, producing one or two windings. The
original winding is not damaged or freed. If only on one side, the
returned winding will be the input winding. If on both sides, two
new windings will be created.
DivideWindingEpsilon Divides a winding by a plane producing one or two windings . The original winding is not damaged or freed . If only on one side the returned winding will be the input winding . If on both sides two new windings will be created .
void DivideWindingEpsilon( winding_t *in, plane_t *split, winding_t **front, winding_t **back, vec_t epsilon )
{
	int			i, j;
	vec_t		dists[MAX_POINTS_ON_WINDING + 1];
	int			sides[MAX_POINTS_ON_WINDING + 1];
	int			counts[3];
	vec_t		dot;
	vec_t		*p1, *p2;
	vec3_t		mid;
	winding_t	*f, *b;
	int			maxpts;
	counts[0] = counts[1] = counts[2] = 0;
	for( i = 0; i < in->numpoints; i++ ) {
		dists[i] = dot = DotProduct (in->points[i], split->normal) - split->dist;
		if( dot > epsilon )
			sides[i] = SIDE_FRONT;
		else if( dot < -epsilon )
			sides[i] = SIDE_BACK;
		else
			sides[i] = SIDE_ON;
		counts[sides[i]]++;
	}
	sides[i] = sides[0];
	dists[i] = dists[0];
	*front = *back = NULL;
	if( !counts[SIDE_FRONT] ) {
		*back = in;
		return;
	}
	if( !counts[SIDE_BACK] ) {
		*front = in;
		return;
	}
	maxpts = in->numpoints + 4;	
	*front = f = AllocWinding( maxpts );
	*back = b = AllocWinding( maxpts );
	for( i = 0; i < in->numpoints; i++ ) {
		p1 = in->points[i];
		if( sides[i] == SIDE_ON ) {
			VectorCopy( p1, f->points[f->numpoints] );
			f->numpoints++;
			VectorCopy( p1, b->points[b->numpoints] );
			b->numpoints++;
			continue;
		}
		if( sides[i] == SIDE_FRONT ) {
			VectorCopy( p1, f->points[f->numpoints] );
			f->numpoints++;
		} else if( sides[i] == SIDE_BACK ) {
			VectorCopy( p1, b->points[b->numpoints] );
			b->numpoints++;
		}
		if( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] )
			continue;
		p2 = in->points[(i+1) % in->numpoints];
		dot = dists[i] / (dists[i] - dists[i+1]);
		for( j = 0;j  < 3; j++) {
			if( split->normal[j] == 1 )
				mid[j] = split->dist;
			else if( split->normal[j] == -1 )
				mid[j] = -split->dist;
			else
				mid[j] = p1[j] + dot * (p2[j] - p1[j]);
		}
		VectorCopy( mid, f->points[f->numpoints] );
		f->numpoints++;
		VectorCopy( mid, b->points[b->numpoints] );
		b->numpoints++;
	}
	if( f->numpoints > maxpts || b->numpoints > maxpts )
		Error ("ClipWinding: points exceeded estimate");
}
void DivideWindingEpsilon ( winding_t * in , plane_t * split , winding_t * * front , winding_t * * back , vec_t epsilon ) { int i , j ; vec_t dists [ MAX_POINTS_ON_WINDING + 1 ] ; int sides [ MAX_POINTS_ON_WINDING + 1 ] ; int counts [ 3 ] ; vec_t dot ; vec_t * p1 , * p2 ; vec3_t mid ; winding_t * f , * b ; int maxpts ; counts [ 0 ] = counts [ 1 ] = counts [ 2 ] = 0 ; for ( i = 0 ; i < in -> numpoints ; i ++ ) { dists [ i ] = dot = DotProduct ( in -> points [ i ] , split -> normal ) - split -> dist ; if ( dot > epsilon ) sides [ i ] = SIDE_FRONT ; else if ( dot < - epsilon ) sides [ i ] = SIDE_BACK ; else sides [ i ] = SIDE_ON ; counts [ sides [ i ] ] ++ ; } sides [ i ] = sides [ 0 ] ; dists [ i ] = dists [ 0 ] ; * front = * back = NULL ; if ( ! counts [ SIDE_FRONT ] ) { * back = in ; return ; } if ( ! counts [ SIDE_BACK ] ) { * front = in ; return ; } maxpts = in -> numpoints + 4 ; * front = f = AllocWinding ( maxpts ) ; * back = b = AllocWinding ( maxpts ) ; for ( i = 0 ; i < in -> numpoints ; i ++ ) { p1 = in -> points [ i ] ; if ( sides [ i ] == SIDE_ON ) { VectorCopy ( p1 , f -> points [ f -> numpoints ] ) ; f -> numpoints ++ ; VectorCopy ( p1 , b -> points [ b -> numpoints ] ) ; b -> numpoints ++ ; continue ; } if ( sides [ i ] == SIDE_FRONT ) { VectorCopy ( p1 , f -> points [ f -> numpoints ] ) ; f -> numpoints ++ ; } else if ( sides [ i ] == SIDE_BACK ) { VectorCopy ( p1 , b -> points [ b -> numpoints ] ) ; b -> numpoints ++ ; } if ( sides [ i + 1 ] == SIDE_ON || sides [ i + 1 ] == sides [ i ] ) continue ; p2 = in -> points [ ( i + 1 ) % in -> numpoints ] ; dot = dists [ i ] / ( dists [ i ] - dists [ i + 1 ] ) ; for ( j = 0 ; j < 3 ; j ++ ) { if ( split -> normal [ j ] == 1 ) mid [ j ] = split -> dist ; else if ( split -> normal [ j ] == -1 ) mid [ j ] = - split -> dist ; else mid [ j ] = p1 [ j ] + dot * ( p2 [ j ] - p1 [ j ] ) ; } VectorCopy ( mid , f -> points [ f -> numpoints ] ) ; f -> numpoints ++ ; VectorCopy ( mid , b -> points [ b -> numpoints ] ) ; b -> numpoints ++ ; } if ( f -> numpoints > maxpts || b -> numpoints > maxpts ) Error ( " " ) ; }
DivideWindingEpsilon
Divides a winding by a plane, producing one or two windings.
DivideWindingEpsilon Divides a winding by a plane producing one or two windings .
// determine sides for each point // can't use counts[0]+2 because of fp grouping errors // generate a split point // avoid round off error when possible