#include <stdio.h>#include <stdlib.h>#include <stdarg.h>#include <math.h>#include <gl/glut.h>typedef unsigned char   u_char;typedef unsigned short  u_short;typedef unsigned int    u_int;typedef unsigned long   u_long;float WORLD_SIZE = 100.0f;float mouse_x = 0.0f;float mouse_y = 0.0f;int   mouse_b = 0;float width  = 640;float height = 480;void  GameInit			();void  GameUpdate		(float dt);void  GameRender		(void);void  GameOnKeyCallback	(int keypressed);void  GameMouse			(float x, float y, int buttons);void PrintString		(int x, int y, bool pixelcoords, unsigned int rgba, const char* str, ...);void RenderSegment		(const Vector& A, const Vector& B, u_int uARGBLine, u_short uStipple=0xFF);void RenderBox			(const Vector& Min, const Vector& Max, u_int uARGBFill, u_int uARGBLine);void RenderBox			(const Vector& Pos, const Vector& Ext, float orient, u_int uARGBFill, u_int uARGBLine);void RenderArrow		(const Vector& P, const Vector& D, float length, u_int uARGB);void RenderDisk			(const Vector& xPos, float fRad, u_int uARGBFill, u_int uARGBLine);void RenderPoint		(const Vector& xPos, float fRad, u_int uARGB);void RenderPolygon		(const Vector& xPos, const Vector* Verts, int numverts, u_int uARGBFill, u_int uARGBLine);	//===========================================================================//// MATHS////===========================================================================inline float sign(float x){	return (x < 0.0f)? -1.0f : 1.0f;}inline float frand(float x=1.0f){	return (rand() / (float) RAND_MAX) * x;}inline float frand(float a, float b){	return a + frand(1.0f) * (b - a);}inline void swapf(float& a, float& b){	float c = a;	a = b;	b = c;}inline float Pi(){    static const float pi = atan(1.0f) * 4.0f;	return pi;}inline float TwoPi(){	static const float two_pi = 2.0f * Pi();	return two_pi;}inline float RadiansToDegrees(float rad){	static const float k = 180.0f / Pi();	return rad * k;}inline float DegreesToRadians(float deg){	static const float k = Pi() / 180.0f;	return deg * k;}//===========================================================================//// VECTORS////===========================================================================class Vector{public:	float x,y;	static const Vector& Blank() { static const Vector V(0, 0); return V; }public:	inline Vector(void)	{}	inline Vector(float Ix,float Iy)	: x(Ix)	, y(Iy)	{}	inline Vector &operator /=(const float Scalar)	{ x /= Scalar; y /= Scalar;		return *this; }	inline Vector &operator *=(const float Scalar)	{ x *= Scalar; y *= Scalar;		return *this; }		inline Vector &operator +=(const Vector &Other) { x += Other.x;	y += Other.y;	return *this; }	inline Vector &operator -=(const Vector &Other) { x -= Other.x;	y -= Other.y;	return *this;	}	inline float operator ^ (const Vector &V)	const	{	return (x * V.y) - (y * V.x); } // cross product	inline float operator * (const Vector &V)	const	{	return (x*V.x) + (y*V.y); } // dot product	inline Vector operator * (float  s)			const	{	return Vector(x*s, y*s); }		inline Vector operator / (float  s)			const	{	return Vector(x/s, y/s); }		inline Vector operator + (const Vector &V)	const	{	return Vector(x+V.x, y+V.y); }			inline Vector operator - (const Vector &V)	const	{	return Vector(x-V.x, y-V.y); }	friend Vector operator * (float k, const Vector& V) {	return Vector(V.x*k, V.y*k); }	inline Vector operator -(void) const { return Vector(-x, -y); }	inline float Length(void) const { return (float) sqrt(x*x + y*y); }	Vector& Randomise(const Vector& xMin, const Vector& xMax)	{		x = frand(xMin.x, xMax.x);		y = frand(xMin.y, xMax.y);		return *this;	}	Vector Normalised(void) const	{		Vector Temp(*this);		Temp.Normalise();		return Temp;	}		float Normalise(void) 	{			float fLength = Length();					if (fLength == 0.0f) 			return 0.0f; 				(*this) *= (1.0f / fLength); 			return fLength;		}	Vector& Min(const Vector& A, const Vector& B)	{		x = (A.x < B.x)? A.x : B.x;		y = (A.y < B.y)? A.y : B.y;		return *this;	}	Vector& Max(const Vector& A, const Vector& B)	{		x = (A.x > B.x)? A.x : B.x;		y = (A.y > B.y)? A.y : B.y;		return *this;	}	Vector& Rotate(float fAngle)	{		float tempx = x;		float tempy = y;		float co = (float) cos(fAngle);		float si = (float) sin(fAngle);		x = tempx * co - tempy * si;		y = tempx * si + tempy * co;		return *this;	}		Vector& LocalToWorldCoords(const Vector& xWorldPosition, float fWorldOrientation)	{		Rotate(fWorldOrientation);		*this += xWorldPosition;		return *this;	}};//===========================================================================//// TOOLS////===========================================================================#define ARGB_A(u) (((u)>>24) & 0x000000FF)#define ARGB_R(u) (((u)>>16) & 0x000000FF)#define ARGB_G(u) (((u)>> 8) & 0x000000FF)#define ARGB_B(u) (((u)>> 0) & 0x000000FF)void RenderPoint(const Vector& xPos, float fRad, u_int uARGB){	glColor4ub(ARGB_R(uARGB), ARGB_G(uARGB), ARGB_B(uARGB), ARGB_A(uARGB));	glPointSize(fRad);	glBegin(GL_POINTS);	glVertex2f(xPos.x, xPos.y);	glEnd();}void RenderDisk(const Vector& xPos, float fRad, u_int uARGBFill, u_int uARGBLine){	static int glDiskList = -1;	static int glCircleList = -1;	static int iNumVerts = 64;	if (!glIsList(glCircleList))	{		glCircleList = glGenLists(1);		glNewList(glCircleList, GL_COMPILE_AND_EXECUTE);		glBegin(GL_LINE_LOOP);		for(int i = 0; i < iNumVerts + 1; i ++)		{			Vector P(cos(TwoPi() * (i / (float) iNumVerts)), sin(TwoPi() * (i / (float) iNumVerts)));			glVertex2f(P.x, P.y);		}		glEnd();		glEndList();	}	if (!glIsList(glDiskList))	{		glDiskList = glGenLists(1);		glNewList(glDiskList, GL_COMPILE_AND_EXECUTE);		glBegin(GL_TRIANGLE_FAN);		glVertex2f(0, 0);		for(int i = 0; i < iNumVerts + 1; i ++)		{			Vector P(cos(TwoPi() * (i / (float) iNumVerts)), sin(TwoPi() * (i / (float) iNumVerts)));			glVertex2f(P.x, P.y);		}				glEnd();		glEndList();	}	glPushMatrix();	glTranslatef(xPos.x, xPos.y, 0.0f);	glScalef(fRad, fRad, fRad);	glColor4ub(ARGB_R(uARGBFill), ARGB_G(uARGBFill), ARGB_B(uARGBFill), ARGB_A(uARGBFill));	glCallList(glDiskList);	glColor4ub(ARGB_R(uARGBLine), ARGB_G(uARGBLine), ARGB_B(uARGBLine), ARGB_A(uARGBLine));	glCallList(glCircleList);	glPopMatrix();}void RenderPolygon(const Vector& xPos, const Vector* Verts, int numverts, u_int uARGBFill, u_int uARGBLine){	glPushMatrix();	glTranslatef(xPos.x, xPos.y, 0.0f);	glColor4ub(ARGB_R(uARGBFill), ARGB_G(uARGBFill), ARGB_B(uARGBFill), ARGB_A(uARGBFill));	glBegin(GL_TRIANGLE_FAN);	glVertex2f(0, 0);	for(int i = 0;  i < numverts; i ++)	{		glVertex2f(Verts.x, Verts.y);	}	glVertex2f(Verts[0].x, Verts[0].y);	glEnd();	glColor4ub(ARGB_R(uARGBLine), ARGB_G(uARGBLine), ARGB_B(uARGBLine), ARGB_A(uARGBLine));	glBegin(GL_LINE_LOOP);	for(int i = 0;  i < numverts; i ++)	{		glVertex2f(Verts.x, Verts.y);	}	glEnd();		glPopMatrix();}void RenderArrow(const Vector& P, const Vector& D, float length, u_int uARGB){	float fAngle = atan2(D.y, D.x);	glPushMatrix();	glTranslatef(P.x, P.y, 0.0f);	glRotatef(RadiansToDegrees(fAngle), 0.0f, 0.0f, 1.0f);	glScalef(length, length, 1.0f);	glColor4ub(ARGB_R(uARGB), ARGB_G(uARGB), ARGB_B(uARGB), ARGB_A(uARGB));	glBegin(GL_LINES);	glVertex2f(0.0f, 0.0f);	glVertex2f(1.0f, 0.0f);	glVertex2f(1.0f, 0.0f);	glVertex2f(0.75f, 0.2f);	glVertex2f(1.0f, 0.0f);	glVertex2f(0.75f,-0.2f);	glEnd();	glPopMatrix();}void RenderSegment(const Vector& A, const Vector& B, u_int uARGB, u_short uStipple){	glEnable(GL_LINE_STIPPLE);	glLineStipple(2, uStipple);	glColor4ub(ARGB_R(uARGB), ARGB_G(uARGB), ARGB_B(uARGB), ARGB_A(uARGB));	glBegin(GL_LINES);	glVertex2f(A.x, A.y);	glVertex2f(B.x, B.y);	glEnd();	glDisable(GL_LINE_STIPPLE);}void RenderBox(const Vector& Pos, const Vector& Ext, float orient, u_int uARGBFill, u_int uARGBLine){	glPushMatrix();	glTranslatef(Pos.x, Pos.y, 0.0f);	glRotatef(orient * 180.0f / Pi(), 0, 0, 1);	glScalef(Ext.x, Ext.y, 1.0f);		glColor4ub(ARGB_R(uARGBFill), ARGB_G(uARGBFill), ARGB_B(uARGBFill), ARGB_A(uARGBFill));	glBegin(GL_QUADS);	glVertex2f(-1, -1);	glVertex2f(-1,  1);	glVertex2f( 1,  1);	glVertex2f( 1, -1);	glEnd();	glColor4ub(ARGB_R(uARGBLine), ARGB_G(uARGBLine), ARGB_B(uARGBLine), ARGB_A(uARGBLine));	glBegin(GL_LINE_LOOP);	glVertex2f(-1, -1);	glVertex2f(-1,  1);	glVertex2f( 1,  1);	glVertex2f( 1, -1);	glEnd();	glPopMatrix();}void RenderBox(const Vector& Min, const Vector& Max, u_int uARGBFill, u_int uARGBLine){	glColor4ub(ARGB_R(uARGBFill), ARGB_G(uARGBFill), ARGB_B(uARGBFill), ARGB_A(uARGBFill));	glBegin(GL_QUADS);	glVertex2f(Min.x, Min.y);	glVertex2f(Max.x, Min.y);	glVertex2f(Max.x, Max.y);	glVertex2f(Min.x, Max.y);	glEnd();	glColor4ub(ARGB_R(uARGBLine), ARGB_G(uARGBLine), ARGB_B(uARGBLine), ARGB_A(uARGBLine));	glBegin(GL_LINE_LOOP);	glVertex2f(Min.x, Min.y);	glVertex2f(Max.x, Min.y);	glVertex2f(Max.x, Max.y);	glVertex2f(Min.x, Max.y);	glEnd();}void PrintString(int x, int y, bool pixelcoords, unsigned int rgba, const char* str, ...){	static char buffer[512];	va_list params;	va_start(params, str);	vsprintf_s(buffer, sizeof(buffer), str, params);	va_end(params);	glPushMatrix();	glColor4ubv((unsigned char*) &rgba);	float fx = x;	float fy = y;	if (!pixelcoords)	{		x *= ( 8 * WORLD_SIZE / width);		y *= (13 * WORLD_SIZE / height);		glRasterPos2f(x, y);	}	else	{		glRasterPos2f(x, y);	}	char* c = buffer;	while(*c)	{		glutBitmapCharacter(GLUT_BITMAP_8_BY_13, *c);		c++;	}	glPopMatrix();}//===========================================================================//// OPENGL////===========================================================================void Display(){	//--------------------------------------------------------------------------	// render stuff	//--------------------------------------------------------------------------	glClearColor(0.2f, 0.2f, 0.2f, 0.2f);	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);	float aspect = 	width / (float) height;	glMatrixMode(GL_PROJECTION);	glLoadIdentity();	glOrtho(WORLD_SIZE * aspect * -0.5f, WORLD_SIZE * aspect * 0.5f, WORLD_SIZE * -0.5f, WORLD_SIZE * 0.5f, -100, 100);		//-----------------------------------------------------------------	// Setup the model view matrix	//-----------------------------------------------------------------	glMatrixMode(GL_MODELVIEW);	glLoadIdentity();		float fx = (       (mouse_x / (float) width ) - 0.5f) * WORLD_SIZE * aspect;	float fy = (1.0f - (mouse_y / (float) height) - 0.5f) * WORLD_SIZE;	GameMouse(fx, fy, mouse_b);	GameUpdate(1.0f / 60.0f);		GameRender();	glutSwapBuffers();}void Mouse(int buttons, int state, int x, int y){	mouse_x = x;	mouse_y = y;		if (buttons == GLUT_LEFT_BUTTON)	{		if (state == GLUT_DOWN)			mouse_b |= 1;		else			mouse_b &= ~1;	}	if (buttons == GLUT_RIGHT_BUTTON)	{		if (state == GLUT_DOWN)			mouse_b |= 2;		else			mouse_b &= ~2;	}}void PassiveMotion(int x, int y){	mouse_x = x;	mouse_y = y;}void Motion(int x, int y){	mouse_x = x;	mouse_y = y;}void Idle(){//	Update(1.0f / 60.0f);	Display();}void Timer(int t){	Idle();	glutTimerFunc(t, Timer, (int) 500.0f / 60.0f);}	void Reshape(int w, int h){	width  = w;	height = h;	glViewport(	0, 0, w, h);}void Keyboard(unsigned char key, int x, int y){	if (key == 27)		exit(0);	GameOnKeyCallback(key);}void ExtKeyboard(int key, int x, int y){	GameOnKeyCallback(key);}void main(int argc, char** argv){	//--------------------------------------------------------------------------	// OpenGL / GLUT init	//--------------------------------------------------------------------------    glutInit( &argc, argv );	glutInitDisplayMode		(GLUT_DOUBLE | GLUT_RGBA);		glutInitWindowSize		(width, height);	glutInitWindowPosition	(0, 0);	glutCreateWindow		("Swept volume polygon collision");		glPointSize				(3.0f);	glEnable				(GL_BLEND);	glBlendFunc				(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);	glDisable				(GL_CULL_FACE);	glDisable				(GL_LIGHTING);		glutDisplayFunc			(Display);	glutReshapeFunc			(Reshape);//	glutIdleFunc			(Idle);	glutTimerFunc			(0, Timer, (int) 100.0f / 60.0f);	glutPassiveMotionFunc	(PassiveMotion);	glutMouseFunc			(Mouse);	glutMotionFunc			(Motion);	glutKeyboardFunc		(Keyboard);	glutSpecialFunc			(ExtKeyboard);	GameInit				();	glutMainLoop			();}//===========================================================================//// GAME CODE////===========================================================================// the two orientated boxesVector Verts[32];int    numverts;Vector SpherePos;Vector OldSpherePos;float SphereRad;bool bColliding = false;float tcoll;Vector Ppolygon;Vector Psphere;bool SpherePolygonCollision( const Vector* Verts, int iNumVerts, 							 const Vector& SpherePos, float radius,							 const Vector& Displacement, 							 float& tcoll, Vector& Ncoll, Vector& Dcoll);void CalculateRandomPolygon(Vector* Vertices, int& numverts, float scale){	// random polygon	numverts = rand() % 10 + 3;	float deltangle = TwoPi() / (float) numverts;	float angle = frand(-Pi(), Pi());	float startangle = angle;	float endangle = angle + TwoPi() - 0.01f;		for(int i = 0; i < numverts; i ++)	{		if (angle > endangle)		{			numverts = i;			break;		}		float dist = scale * frand(0.6f, 1.0f);		Vertices = Vector(cos(angle) * dist, sin(angle) * dist);		angle += deltangle * frand(0.9f, 1.1f);	}	if(numverts <= 3)	{		return;	}		// make it convex	for(int count = 0; count < 20; count++)	{		int im2 = numverts - 2;		int im1 = numverts - 1;				for(int i = 0; i < numverts; im2 = im1, im1 = i, i ++)		{			Vector E = Vertices[im1] - Vertices[im2];			Vector F = Vertices   - Vertices[im1];			float angle = atan2(F ^ E, F * E) + Pi();			if (angle > Pi() || angle < 0.0f)			{				Vertices[im1] *= 1.05f;			}		}	}/**/}void GameShutdown(void){}void GameInit(void){	CalculateRandomPolygon(Verts, numverts, WORLD_SIZE * 0.1f);	SpherePos.Randomise(Vector(WORLD_SIZE * 0.30f, WORLD_SIZE * 0.30f), Vector(WORLD_SIZE * 0.70f, WORLD_SIZE * 0.70f));	OldSpherePos = SpherePos;		SphereRad = frand(WORLD_SIZE *0.05f, WORLD_SIZE *0.1f);}	void GameUpdate(float dt){	Vector Displacement = (SpherePos - OldSpherePos);	Vector Dcoll = Vector(0, 0);	float tcoll;	Vector Ncoll;	bColliding = SpherePolygonCollision(Verts, numverts, OldSpherePos, SphereRad, Displacement, tcoll, Ncoll, Dcoll);		// no collision, carry on	if(bColliding)	{		SpherePos = OldSpherePos + Displacement * tcoll + Dcoll;	}}void GameRender(void){	RenderDisk(SpherePos, SphereRad, bColliding? 0x8000FF00 : 0x8080FF80, 0xFFFFFFFF);	RenderDisk(OldSpherePos, SphereRad, bColliding? 0x80FF8000 : 0x80FFFF80, 0xFFFFFFFF);		RenderArrow(OldSpherePos, (SpherePos - OldSpherePos).Normalised(), (SpherePos - OldSpherePos).Length(), 0xffffffff);	RenderPolygon(Vector(0, 0), Verts, numverts, bColliding? 0x80FF0000 : 0x80FF8080, 0xFFFFFFFF);		PrintString(0, 0, true, 0xFFFFFFFF, "Poly");	PrintString(SpherePos.x, SpherePos.y, true, 0xFFFFFFFF, "B");}void GameOnKeyCallback(int keypressed){	switch(keypressed)	{	case ' ':				GameInit();		break;	case GLUT_KEY_DOWN:		SpherePos.y -= 2.0f;	break;	case GLUT_KEY_UP:		SpherePos.y += 2.0f;	break;	case GLUT_KEY_LEFT:		SpherePos.x -= 2.0f;	break;	case GLUT_KEY_RIGHT:	SpherePos.x += 2.0f;	break;	}}void GameMouse(float x, float y, int buttons){	if (buttons & 1)	{		SpherePos = Vector(x, y);	}	if (buttons & 2)	{		OldSpherePos = Vector(x, y);	}}//===========================================================================//// COLLISION CODE////===========================================================================// check if point is in sphere.bool PointInSphere(	const Vector& Vertex, const Vector& SpherePos, float radius){	Vector Delta = (Vertex - SpherePos);	float d2 = Delta * Delta;	float r2 = radius * radius;	return (d2 <= r2);}// find point on segment closest to an arbitrary point.Vector ClosestPointOnSegment(const Vector& P, const Vector& A, const Vector& B){	Vector AP = P - A;	Vector AB = B - A;	float t = (AP * AB) / (AB * AB);	if(t < 0) t = 0; else if (t > 1) t = 1;	return A + t * AB;}// find what side of a segment a point lies.bool BackFacingSegment(const Vector& P, const Vector& A, const Vector& B){	Vector AP = P - A;	Vector AB = B - A;	return ((AP ^ AB) <= 0);}// distance between two points, squaredfloat DistanceSquared(const Vector& P, const Vector& Q){	Vector PQ = Q - P;	return (PQ * PQ);}// find the closest point on sphere. also tells if the point is inside the sphere.Vector ClosestPointOnSphere(const Vector& P, const Vector& Centre, float radius, bool* inside){	Vector Delta = (P - Centre);		float dist2 = (Delta * Delta);		if(inside)		*inside = (dist2 <= radius * radius);	if(dist2 > 0.0000001f)		Delta /= sqrt(dist2);	return Centre + Delta * radius;}// find the closest point on polygon. also tells if the point is inside the polygon boundaries.Vector ClosestPointOnPolygon(const Vector& P, const Vector* V, int Vnum, bool* inside){	// the closest point found on polygon	Vector closest;	float closestDistanceSquared = -1;	// check on what side of the edges the point lies.	// depending if the polygon is wound clockwise	// or counter-clockwise, we'll need two bitfields.	int ccwPartition = 0;	int cwPartition = 0;	for(int j = Vnum-1, i = 0; i < Vnum; j=i, i++)	{		Vector edgeClosest = ClosestPointOnSegment(P, V[j], V);		if(BackFacingSegment(P, V[j], V))			ccwPartition |= (1 << i);		else			cwPartition |= (1 << i);		// check distance of point ot edge. 		// if this is the closest, use that edge		float edgeClosestDistanceSquared = DistanceSquared(P, edgeClosest);		if(closestDistanceSquared < 0 || edgeClosestDistanceSquared < closestDistanceSquared)		{			closest = edgeClosest;			closestDistanceSquared = edgeClosestDistanceSquared;		}	}	// check if point is inside (either cw or ccw aprtitions will be 0).	if(inside)		*inside = (ccwPartition == 0 || cwPartition == 0);	return closest;}// compute time of impact of a spehre against a vertex.// time of impact will be negative if vertex inside teh sphere.//// point trajectory is P = O + D.t// point on sphere if [P - C]^2 = r^2// which transforms into // [(O - C) + D.t]^2 = r^2// a = (D * D)// b = 2 . (O - C) * D// c = (O - C)^2 - r^2bool SphereVertexCollision ( const Vector& Vertex,							 const Vector& SpherePos, float radius,							 const Vector& Displacement, 							 float& tcoll){	// equation parameters	Vector Pvertex = SpherePos;	Vector H(SpherePos - Vertex);	float r2 = radius * radius;		float a = Displacement * Displacement;	float b = 2.0f * (Displacement * H);	float c = (H * H) - r2;	float d = (b*b) - (4.0f * a * c);		// point missed by infinite ray	if (d < 0.0f)		return false;		d = sqrt(d);	float t0 = (-b - d) / (2.0f * a);	float t1 = (-b + d) / (2.0f * a);	// sort times	if (t0 > t1)		swapf(t0, t1);		// point missed by ray range	if (t1 < 0.0f || t0 > 1.0f)		return false;		// okey dokey	tcoll = t0;	return true;}// find time of collision of a sphere against a segment// time will be negative if edge intersected.//// first, sphere / line collision// convert it to a point / cylinder collision// where point trajectory is P = O + D.t// point on cylinder if [(P - C) x L]^2 = r^2// which transforms into // [(O - C) x L + (D x L).t]^2 = r^2//// second order equation to solve// a.t^2 = b.t + c = 0;// where// a = (D x L)^2// b = 2 . (D x L) . ((O - C) x L)// c = ((O - C) x L)^2 - r^2bool SphereSegmentCollision( const Vector& Start, const Vector& End,							 const Vector& SpherePos, float radius,							 const Vector& Displacement, 							 float& tcoll){	// equation parameters	Vector L(End - Start);	Vector H(SpherePos - Start);	float l2 = L * L;	float r2 = radius * radius;	float DxL = Displacement ^ L;	float HxL = H ^ L;	float a = DxL * DxL;	float b = 2.0f * HxL * DxL;	float c = HxL * HxL - (r2 * l2);	float d = (b*b) - (4.0f * a * c);	// infinite line missed by infinite ray.	if (d < 0.0f)		return false;	d = sqrt(d);	float t0 = (-b - d) / (2.0f * a);	float t1 = (-b + d) / (2.0f * a);	// sort times.	if (t0 > t1)		swapf(t0, t1);	// line missed by ray range.	if (t1 < 0.0f || t0 > 1.0f)		return false;	// find what part of the ray was collided.	float tedge = t0;	if(tedge < 0.0f) tedge = 0.0f;	Vector Pedge = SpherePos + Displacement * tedge;		H = (Pedge - Start);	float e = (H * L) / l2;	// the start vertex should be checked	if (e < 0.0f)	{		return SphereVertexCollision(Start,									 SpherePos, radius,Displacement, 									 tcoll);	}	// the end vertex should be checked	else if (e > 1.0f)	{		return SphereVertexCollision(End,									 SpherePos, radius,Displacement, 									 tcoll);	}	// we've hit the segment. 	else	{		tcoll = t0;		return true;	}}bool SpherePolygonCollision( const Vector* Verts, int iNumVerts, 							 const Vector& SpherePos, float radius,							 const Vector& Displacement, 							 float& tcoll){	bool inside; // is the point inside the polygon		// find closest point on polygo to sphere centre	Vector closest = ClosestPointOnPolygon(SpherePos, Verts, iNumVerts, &inside);	// test for intersection.	if(inside || PointInSphere(closest, SpherePos, radius))	{		// we found an intersection. return then.		tcoll = 0; 		return true;	}	// test collisions. find edge which colllides first.	bool collided = false;	for(int j =iNumVerts-1, i = 0; i < iNumVerts; j=i, i++)	{		float tedge;		if(SphereSegmentCollision(Verts[j], Verts, SpherePos, radius, Displacement, tedge))		{			if(!collided || tedge < tcoll)			{				tcoll = tedge;				collided = true;			}		}	}	return collided;}// find time of collision, normal of collision, and // intersection depth of a sphere against a segmentbool SpherePolygonCollision( const Vector* Verts, int iNumVerts, 							 const Vector& SpherePos, float radius,							 const Vector& Displacement, 							 float& tcoll, Vector& Ncoll, Vector& Dcoll){	Dcoll = Vector(0, 0);	tcoll = 0.0f;	Ncoll = Vector(0, 0);	// time of collision	bool bColliding = SpherePolygonCollision(Verts, numverts, SpherePos, SphereRad, Displacement, tcoll);	if(!bColliding)		return false;	// position of the sphere at collision time.	Vector CollSpherePos = SpherePos + Displacement * tcoll;		// find contact points.	bool pointInsidePolygon;	bool pointInsideSphere;	Ppolygon = ClosestPointOnPolygon(CollSpherePos, Verts, numverts, &pointInsidePolygon);	Psphere  = ClosestPointOnSphere(Ppolygon, CollSpherePos, SphereRad, &pointInsideSphere);		// calculate the MTD and normal	Dcoll = (Ppolygon - Psphere);	Ncoll = (CollSpherePos - Ppolygon).Normalised();		// sphere centre was inside polygon, 	// Psphere should be on the other side of the sphere.	if(pointInsidePolygon)	{		// we're pretty deeply embedded into teh polygon. Need to flip the normal.		if(!pointInsideSphere) 			Ncoll = -Ncoll; 		// point on sphere opposite the contact point on polygon.		Psphere = CollSpherePos + Ncoll * SphereRad;		Dcoll = (Ppolygon - Psphere);	}	return true;}