level/winding.c
/*
=============
TryMergeWinding

If two polygons share a common edge and the edges that meet at the
common points are both inside the other polygons, merge them

Returns NULL if the windings couldn't be merged, or the new winding.
The originals will NOT be freed.
=============
*/
TryMergeWinding
If two polygons share a common edge and the edges that meet at the
common points are both inside the other polygons, merge them

Returns NULL if the windings couldn't be merged, or the new winding.
The originals will NOT be freed.
TryMergeWinding If two polygons share a common edge and the edges that meet at the common points are both inside the other polygons merge them Returns NULL if the windings couldn ' t be merged or the new winding . The originals will NOT be freed .
winding_t *TryMergeWinding( winding_t *w1, winding_t *w2, vec3_t planenormal )
{
	int			i, j = 0, k, l;
	vec_t		*p1 = NULL, *p2 = NULL, *p3, *p4, *back;
	winding_t	*neww;
	vec3_t		normal, delta;
	vec_t		dot;
	bool		keep1, keep2;
	 find a common edge
	for( i = 0; i < w1->numpoints; i++ ) {
		p1 = w1->points[i];
		p2 = w1->points[(i + 1) % w1->numpoints];
		for( j = 0; j < w2->numpoints; j++ ) {
			p3 = w2->points[j];
			p4 = w2->points[(j + 1) % w2->numpoints];
			for( k = 0; k < 3; k++ ) {
				if( fabs( p1[k] - p4[k] ) > pMath_EPSILON_EQUAL ||
					fabs( p2[k] - p3[k] ) > pMath_EPSILON_EQUAL )
					break;
			}
			if( k == 3 )
				break;
		}
		if( j < w2->numpoints )
			break;
	}
	if( i == w1->numpoints )
		return NULL;			 no matching edges
	 check slope of connected lines
	 if the slopes are colinear, the point can be removed
	back = w1->points[(i + w1->numpoints - 1) % w1->numpoints];
	VectorSubtract( p1, back, delta );
	CrossProduct( planenormal, delta, normal );
	VectorNormalize( normal );
	back = w2->points[(j + 2) % w2->numpoints];
	VectorSubtract( back, p1, delta );
	dot = DotProduct( delta, normal );
	if( dot > CONTINUOUS_EPSILON )
		return NULL;			 not a convex polygon
	keep1 = dot < -CONTINUOUS_EPSILON;
	back = w1->points[(i + 2) % w1->numpoints];
	VectorSubtract( back, p2, delta );
	CrossProduct( planenormal, delta, normal );
	VectorNormalize( normal );
	back = w2->points[(j + w2->numpoints - 1) % w2->numpoints];
	VectorSubtract( back, p2, delta );
	dot = DotProduct( delta, normal );
	if( dot > CONTINUOUS_EPSILON )
		return NULL;			 not a convex polygon
	keep2 = dot < -CONTINUOUS_EPSILON;
	 build the new polygon
	neww = AllocWinding( w1->numpoints + w2->numpoints - 4 + keep1 + keep2 );
	 copy first polygon
	for( k = (i + 1) % w1->numpoints; k != i; k = (k + 1)%w1->numpoints ) {
		if( k == (i + 1) % w1->numpoints && !keep2 )
			continue;
		VectorCopy( w1->points[k], neww->points[neww->numpoints] );
		neww->numpoints++;
	}
	 copy second polygon
	for( l = (j + 1) % w2->numpoints; l != j; l = (l + 1) % w2->numpoints ) {
		if( l == (j + 1) % w2->numpoints && !keep1 )
			continue;
		VectorCopy( w2->points[l], neww->points[neww->numpoints] );
		neww->numpoints++;
	}
	return neww;
}
winding_t * TryMergeWinding ( winding_t * w1 , winding_t * w2 , vec3_t planenormal ) { int i , j = 0 , k , l ; vec_t * p1 = NULL , * p2 = NULL , * p3 , * p4 , * back ; winding_t * neww ; vec3_t normal , delta ; vec_t dot ; bool keep1 , keep2 ; for ( i = 0 ; i < w1 -> numpoints ; i ++ ) { p1 = w1 -> points [ i ] ; p2 = w1 -> points [ ( i + 1 ) % w1 -> numpoints ] ; for ( j = 0 ; j < w2 -> numpoints ; j ++ ) { p3 = w2 -> points [ j ] ; p4 = w2 -> points [ ( j + 1 ) % w2 -> numpoints ] ; for ( k = 0 ; k < 3 ; k ++ ) { if ( fabs ( p1 [ k ] - p4 [ k ] ) > pMath_EPSILON_EQUAL || fabs ( p2 [ k ] - p3 [ k ] ) > pMath_EPSILON_EQUAL ) break ; } if ( k == 3 ) break ; } if ( j < w2 -> numpoints ) break ; } if ( i == w1 -> numpoints ) return NULL ; back = w1 -> points [ ( i + w1 -> numpoints - 1 ) % w1 -> numpoints ] ; VectorSubtract ( p1 , back , delta ) ; CrossProduct ( planenormal , delta , normal ) ; VectorNormalize ( normal ) ; back = w2 -> points [ ( j + 2 ) % w2 -> numpoints ] ; VectorSubtract ( back , p1 , delta ) ; dot = DotProduct ( delta , normal ) ; if ( dot > CONTINUOUS_EPSILON ) return NULL ; keep1 = dot < - CONTINUOUS_EPSILON ; back = w1 -> points [ ( i + 2 ) % w1 -> numpoints ] ; VectorSubtract ( back , p2 , delta ) ; CrossProduct ( planenormal , delta , normal ) ; VectorNormalize ( normal ) ; back = w2 -> points [ ( j + w2 -> numpoints - 1 ) % w2 -> numpoints ] ; VectorSubtract ( back , p2 , delta ) ; dot = DotProduct ( delta , normal ) ; if ( dot > CONTINUOUS_EPSILON ) return NULL ; keep2 = dot < - CONTINUOUS_EPSILON ; neww = AllocWinding ( w1 -> numpoints + w2 -> numpoints - 4 + keep1 + keep2 ) ; for ( k = ( i + 1 ) % w1 -> numpoints ; k != i ; k = ( k + 1 ) % w1 -> numpoints ) { if ( k == ( i + 1 ) % w1 -> numpoints && ! keep2 ) continue ; VectorCopy ( w1 -> points [ k ] , neww -> points [ neww -> numpoints ] ) ; neww -> numpoints ++ ; } for ( l = ( j + 1 ) % w2 -> numpoints ; l != j ; l = ( l + 1 ) % w2 -> numpoints ) { if ( l == ( j + 1 ) % w2 -> numpoints && ! keep1 ) continue ; VectorCopy ( w2 -> points [ l ] , neww -> points [ neww -> numpoints ] ) ; neww -> numpoints ++ ; } return neww ; }
TryMergeWinding
If two polygons share a common edge and the edges that meet at the
common points are both inside the other polygons, merge them
TryMergeWinding If two polygons share a common edge and the edges that meet at the common points are both inside the other polygons merge them
// // find a common edge // // no matching edges // // check slope of connected lines // if the slopes are colinear, the point can be removed // // not a convex polygon // not a convex polygon // // build the new polygon // // copy first polygon // copy second polygon