/*
===================
Cull

cull points against given shadow frustum.
Return true of all points are outside the frustum.
===================
*/
bool shadowMapFrustum_t::Cull( const idVec3 points[8] ) const {

	bool outsidePlane[6];

	for (int i = 0; i < numPlanes; i++) {

		bool pointsCulled[8] = { true };
		const idPlane plane = planes[i];

		for (int j = 0; j < 8; j++) {
			const float distance = plane.Distance( points[j] );
			pointsCulled[j] = distance < 0;
		}

		outsidePlane[i] = true;
		for (int j = 0; j < 8; j++) {
			if (!pointsCulled[j]) {
				outsidePlane[i] = false;
			}
		}
	}

	for (int i = 0; i < numPlanes; i++) {
		if (outsidePlane[i])
			return true;
	}

	return false;
}

/*
================
R_CalcInteractionFacing

Determines which triangles of the surface are facing towards the light origin.

The facing array should be allocated with one extra index than
the number of surface triangles, which will be used to handle dangling
edge silhouettes.
================
*/
void R_CalcInteractionFacing( const idRenderEntityLocal *ent, const srfTriangles_t *tri, const idRenderLightLocal *light, srfCullInfo_t &cullInfo ) {
	SCOPED_PROFILE_EVENT( "R_CalcInteractionFacing" );

	if ( cullInfo.facing != NULL ) {
		return;
	}

	idVec3 localLightOrigin;
	R_GlobalPointToLocal( ent->modelMatrix, light->globalLightOrigin, localLightOrigin );

	const int numFaces = tri->numIndexes / 3;
	cullInfo.facing = (byte *) R_StaticAlloc( ( numFaces + 1 ) * sizeof( cullInfo.facing[0] ), TAG_RENDER_INTERACTION );

	// exact geometric cull against face
	for ( int i = 0, face = 0; i < tri->numIndexes; i += 3, face++ ) {
		const idDrawVert & v0 = tri->verts[tri->indexes[i + 0]];
		const idDrawVert & v1 = tri->verts[tri->indexes[i + 1]];
		const idDrawVert & v2 = tri->verts[tri->indexes[i + 2]];

		const idPlane plane( v0.xyz, v1.xyz, v2.xyz );
		const float d = plane.Distance( localLightOrigin );

		cullInfo.facing[face] = ( d >= 0.0f );
	}
	cullInfo.facing[numFaces] = 1;	// for dangling edges to reference
}

void R_LocalPlaneToGlobal( const float modelMatrix[16], const idPlane &in, idPlane &out ) {
	float	offset;

	R_LocalVectorToGlobal( modelMatrix, in.Normal(), out.Normal() );

	offset = modelMatrix[12] * out[0] + modelMatrix[13] * out[1] + modelMatrix[14] * out[2];
	out[3] = in[3] - offset;
}

/*
============
idBrush::FromWinding
============
*/
bool idBrush::FromWinding( const idWinding& w, const idPlane& windingPlane )
{
	int i, j, bestAxis;
	idPlane plane;
	idVec3 normal, axialNormal;
	
	sides.Append( new idBrushSide( windingPlane, -1 ) );
	sides.Append( new idBrushSide( -windingPlane, -1 ) );
	
	bestAxis = 0;
	for( i = 1; i < 3; i++ )
	{
		if( idMath::Fabs( windingPlane.Normal()[i] ) > idMath::Fabs( windingPlane.Normal()[bestAxis] ) )
		{
			bestAxis = i;
		}
	}
	axialNormal = vec3_origin;
	if( windingPlane.Normal()[bestAxis] > 0.0f )
	{
		axialNormal[bestAxis] = 1.0f;
	}
	else
	{
		axialNormal[bestAxis] = -1.0f;
	}
	
	for( i = 0; i < w.GetNumPoints(); i++ )
	{
		j = ( i + 1 ) % w.GetNumPoints();
		normal = ( w[j].ToVec3() - w[i].ToVec3() ).Cross( axialNormal );
		if( normal.Normalize() < 0.5f )
		{
			continue;
		}
		plane.SetNormal( normal );
		plane.FitThroughPoint( w[j].ToVec3() );
		sides.Append( new idBrushSide( plane, -1 ) );
	}
	
	if( sides.Num() < 4 )
	{
		for( i = 0; i < sides.Num(); i++ )
		{
			delete sides[i];
		}
		sides.Clear();
		return false;
	}
	
	sides[0]->winding = w.Copy();
	windingsValid = true;
	BoundBrush();
	
	return true;
}

/*
============
idAASLocal::EdgeSplitPoint

  calculates split point of the edge with the plane
  returns true if the split point is between the edge vertices
============
*/
bool idAASLocal::EdgeSplitPoint( idVec3 &split, int edgeNum, const idPlane &plane ) const {
	const aasEdge_t *edge;
	idVec3 v1, v2;
	float d1, d2;
	edge = &file->GetEdge( edgeNum );
	v1 = file->GetVertex( edge->vertexNum[0] );
	v2 = file->GetVertex( edge->vertexNum[1] );
	d1 = v1 * plane.Normal() - plane.Dist();
	d2 = v2 * plane.Normal() - plane.Dist();
	//if ( (d1 < CM_CLIP_EPSILON && d2 < CM_CLIP_EPSILON) || (d1 > -CM_CLIP_EPSILON && d2 > -CM_CLIP_EPSILON) ) {
	if( FLOATSIGNBITSET( d1 ) == FLOATSIGNBITSET( d2 ) ) {
		return false;
	}
	split = v1 + ( d1 / ( d1 - d2 ) ) * ( v2 - v1 );
	return true;
}

/*
================
idBox::PlaneDistance
================
*/
float idBox::PlaneDistance( const idPlane &plane ) const {
	float d1, d2;

	d1 = plane.Distance( center );
	d2 = idMath::Fabs( extents[0] * plane.Normal()[0] ) +
			idMath::Fabs( extents[1] * plane.Normal()[1] ) +
				idMath::Fabs( extents[2] * plane.Normal()[2] );

	if ( d1 - d2 > 0.0f ) {
		return d1 - d2;
	}
	if ( d1 + d2 < 0.0f ) {
		return d1 + d2;
	}
	return 0.0f;
}

/*
================
idBox::PlaneSide
================
*/
int idBox::PlaneSide( const idPlane &plane, const float epsilon ) const {
	float d1, d2;

	d1 = plane.Distance( center );
	d2 = idMath::Fabs( extents[0] * plane.Normal()[0] ) +
			idMath::Fabs( extents[1] * plane.Normal()[1] ) +
				idMath::Fabs( extents[2] * plane.Normal()[2] );

	if ( d1 - d2 > epsilon ) {
		return PLANESIDE_FRONT;
	}
	if ( d1 + d2 < -epsilon ) {
		return PLANESIDE_BACK;
	}
	return PLANESIDE_CROSS;
}

/*
==================
BrushMostlyOnSide

==================
*/
int BrushMostlyOnSide( uBrush_t *brush, idPlane &plane )
{
	int			i, j;
	idWinding	*w;
	float		d, max = 0;
	int			side = PSIDE_FRONT;
	
	for( i = 0; i < brush->numsides; i++ )
	{
		w = brush->sides[i].winding;
		
		if( !w )
		{
			continue;
		}
		
		for( j = 0; j < w->GetNumPoints(); j++ )
		{
			d = plane.Distance( ( *w ) [j].ToVec3() );
			
			if( d > max )
			{
				max = d;
				side = PSIDE_FRONT;
			}
			
			if( -d > max )
			{
				max = -d;
				side = PSIDE_BACK;
			}
		}
	}
	return side;
}

/*
=============
R_PlaneForSurface

Returns the plane for the first triangle in the surface
FIXME: check for degenerate triangle?
=============
*/
static void R_PlaneForSurface( const srfTriangles_t *tri, idPlane &plane ) {
	idDrawVert		*v1, *v2, *v3;
	v1 = tri->verts + tri->indexes[0];
	v2 = tri->verts + tri->indexes[1];
	v3 = tri->verts + tri->indexes[2];
	plane.FromPoints( v1->xyz, v2->xyz, v3->xyz );
}

/*
====================
R_LightProjectionMatrix

====================
*/
void R_LightProjectionMatrix( const idVec3 &origin, const idPlane &rearPlane, idVec4 mat[4] ) {
	idVec4		lv;
	float		lg;

	// calculate the homogenious light vector
	lv.x = origin.x;
	lv.y = origin.y;
	lv.z = origin.z;
	lv.w = 1;

	lg = rearPlane.ToVec4() * lv;

	// outer product
	mat[0][0] = lg -rearPlane[0] * lv[0];
	mat[0][1] = -rearPlane[1] * lv[0];
	mat[0][2] = -rearPlane[2] * lv[0];
	mat[0][3] = -rearPlane[3] * lv[0];

	mat[1][0] = -rearPlane[0] * lv[1];
	mat[1][1] = lg -rearPlane[1] * lv[1];
	mat[1][2] = -rearPlane[2] * lv[1];
	mat[1][3] = -rearPlane[3] * lv[1];

	mat[2][0] = -rearPlane[0] * lv[2];
	mat[2][1] = -rearPlane[1] * lv[2];
	mat[2][2] = lg -rearPlane[2] * lv[2];
	mat[2][3] = -rearPlane[3] * lv[2];

	mat[3][0] = -rearPlane[0] * lv[3];
	mat[3][1] = -rearPlane[1] * lv[3];
	mat[3][2] = -rearPlane[2] * lv[3];
	mat[3][3] = lg -rearPlane[3] * lv[3];
}

/*
================
idBounds::PlaneSide
================
*/
int idBounds::PlaneSide( const idPlane &plane, const float epsilon ) const {
	idVec3 center;
	float d1, d2;

	center = ( b[0] + b[1] ) * 0.5f;

	d1 = plane.Distance( center );
	d2 = idMath::Fabs( ( b[1][0] - center[0] ) * plane.Normal()[0] ) +
			idMath::Fabs( ( b[1][1] - center[1] ) * plane.Normal()[1] ) +
				idMath::Fabs( ( b[1][2] - center[2] ) * plane.Normal()[2] );

	if ( d1 - d2 > epsilon ) {
		return PLANESIDE_FRONT;
	}
	if ( d1 + d2 < -epsilon ) {
		return PLANESIDE_BACK;
	}
	return PLANESIDE_CROSS;
}

/*
================
idBounds::PlaneDistance
================
*/
float idBounds::PlaneDistance( const idPlane &plane ) const {
	idVec3 center;
	float d1, d2;

	center = ( b[0] + b[1] ) * 0.5f;

	d1 = plane.Distance( center );
	d2 = idMath::Fabs( ( b[1][0] - center[0] ) * plane.Normal()[0] ) +
			idMath::Fabs( ( b[1][1] - center[1] ) * plane.Normal()[1] ) +
				idMath::Fabs( ( b[1][2] - center[2] ) * plane.Normal()[2] );

	if ( d1 - d2 > 0.0f ) {
		return d1 - d2;
	}
	if ( d1 + d2 < 0.0f ) {
		return d1 + d2;
	}
	return 0.0f;
}

/*
============
idAASBuild::IsLedgeSide_r
============
*/
bool idAASBuild::IsLedgeSide_r( idBrushBSPNode *node, idFixedWinding *w, const idPlane &plane, const idVec3 &normal, const idVec3 &origin, const float radius ) {
	int res, i;
	idFixedWinding back;
	float dist;

	if ( !node ) {
		return false;
	}

	while ( node->GetChild(0) && node->GetChild(1) ) {
		dist = node->GetPlane().Distance( origin );
		if ( dist > radius ) {
			res = SIDE_FRONT;
		}
		else if ( dist < -radius ) {
			res = SIDE_BACK;
		}
		else {
			res = w->Split( &back, node->GetPlane(), LEDGE_EPSILON );
		}
		if ( res == SIDE_FRONT ) {
			node = node->GetChild(0);
		}
		else if ( res == SIDE_BACK ) {
			node = node->GetChild(1);
		}
		else if ( res == SIDE_ON ) {
			// continue with the side the winding faces
			if ( node->GetPlane().Normal() * normal > 0.0f ) {
				node = node->GetChild(0);
			}
			else {
				node = node->GetChild(1);
			}
		}
		else {
			if ( IsLedgeSide_r( node->GetChild(1), &back, plane, normal, origin, radius ) ) {
				return true;
			}
			node = node->GetChild(0);
		}
	}

	if ( node->GetContents() & AREACONTENTS_SOLID ) {
		return false;
	}

	for ( i = 0; i < w->GetNumPoints(); i++ ) {
		if ( plane.Distance( (*w)[i].ToVec3() ) > 0.0f ) {
			return true;
		}
	}

	return false;
}

/*
================
idPlane::PlaneIntersection
================
*/
bool idPlane::PlaneIntersection( const idPlane &plane, idVec3 &start, idVec3 &dir ) const {
	double n00, n01, n11, det, invDet, f0, f1;

	n00 = Normal().LengthSqr();
	n01 = Normal() * plane.Normal();
	n11 = plane.Normal().LengthSqr();
	det = n00 * n11 - n01 * n01;

	if ( idMath::Fabs(det) < 1e-6f ) {
		return false;
	}

	invDet = 1.0f / det;
	f0 = ( n01 * plane.d - n11 * d ) * invDet;
	f1 = ( n01 * d - n00 * plane.d ) * invDet;

	dir = Normal().Cross( plane.Normal() );
	start = f0 * Normal() + f1 * plane.Normal();
	return true;
}

/*
================
idSphere::PlaneDistance
================
*/
float idSphere::PlaneDistance( const idPlane &plane ) const {
	float d;

	d = plane.Distance( origin );
	if ( d > radius ) {
		return d - radius;
	}
	if ( d < -radius ) {
		return d + radius;
	}
	return 0.0f;
}

/*
================
idSphere::PlaneSide
================
*/
int idSphere::PlaneSide( const idPlane &plane, const float epsilon ) const {
	float d;

	d = plane.Distance( origin );
	if ( d > radius + epsilon ) {
		return PLANESIDE_FRONT;
	}
	if ( d < -radius - epsilon ) {
		return PLANESIDE_BACK;
	}
	return PLANESIDE_CROSS;
}

/*
============
idAASLocal::FloorEdgeSplitPoint

  calculates either the closest or furthest point on the floor of the area which also lies on the pathPlane
  the point has to be on the front side of the frontPlane to be valid
============
*/
bool idAASLocal::FloorEdgeSplitPoint( idVec3 &bestSplit, int areaNum, const idPlane &pathPlane, const idPlane &frontPlane, bool closest ) const {
	int i, j, faceNum, edgeNum;
	const aasArea_t *area;
	const aasFace_t *face;
	idVec3 split;
	float dist, bestDist;

	if ( closest ) {
		bestDist = maxWalkPathDistance;
	} else {
		bestDist = -0.1f;
	}

	area = &file->GetArea( areaNum );

	for ( i = 0; i < area->numFaces; i++ ) {
		faceNum = file->GetFaceIndex( area->firstFace + i );
		face = &file->GetFace( abs(faceNum) );

		if ( !(face->flags & FACE_FLOOR ) ) {
			continue;
		}

		for ( j = 0; j < face->numEdges; j++ ) {
			edgeNum = file->GetEdgeIndex( face->firstEdge + j );

			if ( !EdgeSplitPoint( split, abs( edgeNum ), pathPlane ) ) {
				continue;
			}
			dist = frontPlane.Distance( split );
			if ( closest ) {
				if ( dist >= -0.1f && dist < bestDist ) {
					bestDist = dist;
					bestSplit = split;
				}
			} else {
				if ( dist > bestDist ) {
					bestDist = dist;
					bestSplit = split;
				}
			}
		}
	}

	if ( closest ) {
		return ( bestDist < maxWalkPathDistance );
	} else {
		return ( bestDist > -0.1f );
	}
}

/*
=============
R_ChopWinding

Clips a triangle from one buffer to another, setting edge flags
The returned buffer may be the same as inNum if no clipping is done
If entirely clipped away, clipTris[returned].numVerts == 0

I have some worries about edge flag cases when polygons are clipped
multiple times near the epsilon.
=============
*/
static int R_ChopWinding( clipTri_t clipTris[2], int inNum, const idPlane plane ) {
	clipTri_t	*in, *out;
	float	dists[MAX_CLIPPED_POINTS];
	int		sides[MAX_CLIPPED_POINTS];
	int		counts[3];
	float	dot;
	int		i, j;
	idVec3	mid;
	bool	front;

	in = &clipTris[inNum];
	out = &clipTris[inNum^1];
	counts[0] = counts[1] = counts[2] = 0;

	// determine sides for each point
	front = false;
	for ( i = 0; i < in->numVerts; i++ ) {
		dot = in->verts[i] * plane.Normal() + plane[3];
		dists[i] = dot;
		if ( dot < LIGHT_CLIP_EPSILON ) {	// slop onto the back
			sides[i] = SIDE_BACK;
		} else {
			sides[i] = SIDE_FRONT;
			if ( dot > LIGHT_CLIP_EPSILON ) {
				front = true;
			}
		}
		counts[sides[i]]++;
	}

	// if none in front, it is completely clipped away
	if ( !front ) {
		in->numVerts = 0;
		return inNum;
	}
	if ( !counts[SIDE_BACK] ) {
		return inNum;		// inout stays the same
	}

	// avoid wrapping checks by duplicating first value to end
	sides[i] = sides[0];
	dists[i] = dists[0];
	in->verts[in->numVerts] = in->verts[0];

	out->numVerts = 0;
	for ( i = 0 ; i < in->numVerts ; i++ ) {
		idVec3 &p1 = in->verts[i];
		
		if ( sides[i] == SIDE_FRONT ) {
			out->verts[out->numVerts] = p1;
			out->numVerts++;
		}

		if ( sides[i+1] == sides[i] ) {
			continue;
		}
			
		// generate a split point
		idVec3 &p2 = in->verts[i+1];
		
		dot = dists[i] / ( dists[i] - dists[i+1] );
		for ( j = 0; j < 3; j++ ) {
			mid[j] = p1[j] + dot * ( p2[j] - p1[j] );
		}
			
		out->verts[out->numVerts] = mid;

		out->numVerts++;
	}

	return inNum ^ 1;
}

/*
============
idBrush::Split
============
*/
int idBrush::Split( const idPlane& plane, int planeNum, idBrush** front, idBrush** back ) const
{
	int res, i, j;
	idBrushSide* side, *frontSide, *backSide;
	float dist, maxBack, maxFront, *maxBackWinding, *maxFrontWinding;
	idWinding* w, *mid;
	
	assert( windingsValid );
	
	if( front )
	{
		*front = NULL;
	}
	if( back )
	{
		*back = NULL;
	}
	
	res = bounds.PlaneSide( plane, -BRUSH_EPSILON );
	if( res == PLANESIDE_FRONT )
	{
		if( front )
		{
			*front = Copy();
		}
		return res;
	}
	if( res == PLANESIDE_BACK )
	{
		if( back )
		{
			*back = Copy();
		}
		return res;
	}
	
	maxBackWinding = ( float* ) _alloca16( sides.Num() * sizeof( float ) );
	maxFrontWinding = ( float* ) _alloca16( sides.Num() * sizeof( float ) );
	
	maxFront = maxBack = 0.0f;
	for( i = 0; i < sides.Num(); i++ )
	{
		side = sides[i];
		
		w = side->winding;
		
		if( !w )
		{
			continue;
		}
		
		maxBackWinding[i] = 10.0f;
		maxFrontWinding[i] = -10.0f;
		
		for( j = 0; j < w->GetNumPoints(); j++ )
		{
		
			dist = plane.Distance( ( *w )[j].ToVec3() );
			if( dist > maxFrontWinding[i] )
			{
				maxFrontWinding[i] = dist;
			}
			if( dist < maxBackWinding[i] )
			{
				maxBackWinding[i] = dist;
			}
		}
		
		if( maxFrontWinding[i] > maxFront )
		{
			maxFront = maxFrontWinding[i];
		}
		if( maxBackWinding[i] < maxBack )
		{
			maxBack = maxBackWinding[i];
		}
	}
	
	if( maxFront < BRUSH_EPSILON )
	{
		if( back )
		{
			*back = Copy();
		}
		return PLANESIDE_BACK;
	}
	
	if( maxBack > -BRUSH_EPSILON )
	{
		if( front )
		{
			*front = Copy();
		}
		return PLANESIDE_FRONT;
	}
//.........这里部分代码省略.........

/*
================
idCollisionModelManagerLocal::RotatePointThroughPlane

  calculates the tangent of half the rotation angle at which the point collides with the plane
================
*/
int idCollisionModelManagerLocal::RotatePointThroughPlane( const cm_traceWork_t *tw, const idVec3 &point, const idPlane &plane,
													const float angle, const float minTan, float &tanHalfAngle ) {
	double v0, v1, v2, a, b, c, d, sqrtd, q, frac1, frac2;
	idVec3 p, normal;

	/*

	p[0] = point[0] * cos(t) + point[1] * sin(t)
	p[1] = point[0] * -sin(t) + point[1] * cos(t)
	p[2] = point[2];

	normal[0] * (p[0] * cos(t) + p[1] * sin(t)) +
		normal[1] * (p[0] * -sin(t) + p[1] * cos(t)) +
			normal[2] * p[2] + dist = 0

	normal[0] * p[0] * cos(t) + normal[0] * p[1] * sin(t) +
		-normal[1] * p[0] * sin(t) + normal[1] * p[1] * cos(t) +
			normal[2] * p[2] + dist = 0

	v2 * cos(t) + v1 * sin(t) + v0

	// rotation about the z-axis
	v0 = normal[2] * p[2] + dist
	v1 = normal[0] * p[1] - normal[1] * p[0]
	v2 = normal[0] * p[0] + normal[1] * p[1]

	r = tan(t / 2);
	sin(t) = 2*r/(1+r*r);
	cos(t) = (1-r*r)/(1+r*r);

	v1 * 2 * r / (1 + r*r) + v2 * (1 - r*r) / (1 + r*r) + v0 = 0
	(v1 * 2 * r + v2 * (1 - r*r)) / (1 + r*r) = -v0
	(v1 * 2 * r + v2 - v2 * r*r) / (1 + r*r) = -v0
	v1 * 2 * r + v2 - v2 * r*r = -v0 * (1 + r*r)
	v1 * 2 * r + v2 - v2 * r*r = -v0 + -v0 * r*r
	(v0 - v2) * r * r + (2 * v1) * r + (v0 + v2) = 0;

	*/

	tanHalfAngle = tw->maxTan;

	// transform rotation axis to z-axis
	p = (point - tw->origin) * tw->matrix;
	d = plane[3] + plane.Normal() * tw->origin;
	normal = plane.Normal() * tw->matrix;

	v0 = normal[2] * p[2] + d;
	v1 = normal[0] * p[1] - normal[1] * p[0];
	v2 = normal[0] * p[0] + normal[1] * p[1];

	a = v0 - v2;
	b = v1;
	c = v0 + v2;
	if ( a == 0.0f ) {
		if ( b == 0.0f ) {
			return false;
		}
		frac1 = -c / ( 2.0f * b );
		frac2 = 1e10;	// = tan( idMath::HALF_PI )
	}
	else {
		d = b * b - c * a;
		if ( d <= 0.0f ) {
			return false;
		}
		sqrtd = sqrt( d );
		if ( b > 0.0f ) {
			q = - b + sqrtd;
		}
		else {
			q = - b - sqrtd;
		}
		frac1 = q / a;
		frac2 = c / q;
	}

	if ( angle < 0.0f ) {
		frac1 = -frac1;
		frac2 = -frac2;
	}

	// get smallest tangent for which a collision occurs
	if ( frac1 >= minTan && frac1 < tanHalfAngle ) {
		tanHalfAngle = frac1;
	}
	if ( frac2 >= minTan && frac2 < tanHalfAngle ) {
		tanHalfAngle = frac2;
	}

	if ( angle < 0.0f ) {
		tanHalfAngle = -tanHalfAngle;
	}

//.........这里部分代码省略.........