🔒 Locked 🎲 GameMaker

2D AABB to moving circle collision detection and response

Started by VBStrider Apr 20, 2009 at 2:00 PM 22 replies 13.3k views

Original Post

Apr 20, 2009 at 2:00 PM

I am currently attempting to write AABB to moving circle collision detection and response in 2D. There is a single moving circle, which most likely has a changing velocity each update, and there are multiple AABBs which the circle is not allowed to move through. The code checks for collision between the moving circle and all of the AABBs that surround it (up to 8). If a collision is detected, the time of collision is calculated using an extended AABB with rounded corners and a ray from the circle's starting position to where it ends up. The circle is moved along the ray to the time of intersection. However, this collision detection system is flawed because the circle is now at the time of intersection which means that it is still intersecting the AABB. So the circle is moved back by an additional 1 pixel (not circular, meaning the magnitude of the vector the circle is additionally moved back by might not be 1). Even this system does not work correctly though. If the circle's movement vector is parallel to an edge/face (this is 2D, so I am unsure which term to use) of the AABB, the circle could be within 1 pixel of the AABB and not be pushed back. To make the response code a bit cleaner, the movement vector that is used is extended by 1 block pixel. This way the "additional" move-back is not required as it is part of being pushed to the point of intersection. This does not solve the previously mention problem however. Here is a graph showing the problem:

If anyone could help, I would greatly appreciate it!

VBStrider

Apr 22, 2009 at 1:03 PM

After further research, there seems to be 2 options for handling the collision detection and response.

The first option is to consider any intersection as a collision which needs to be resolved. This is the option I described in my previous post. This option requires the circle to be completely pushed out of the AABB, which I was doing by pushing it back by an additional pixel. This causes the problem I described earlier; you need to somehow keep a 1 pixel thick border around the AABB without actually making it part of the AABB.

The second option is to consider intersection at "time 0" to be non-intersecting, and simply resting on each other's borders. However, this means that the circle and the AABB will be sharing a point. Resolving this collision is a little easier since you simply move the circle back along it's movement vector to the point of intersection. The drawback to this is that the circle will remain stuck on the edge of the AABB, since even if it tries to move away from the AABB, it will still intersect it at time 0. To fix this, I believe you would need to somehow check if the circle is moving away from the AABB, and disregard any intersection with the AABB if that is the case.

Is all of that correct, or am I wrong? Could someone please explain exactly how this is supposed to work?

Edit: After trying to figure out a method to find out if a circle is moving towards or away from an AABB, I have come to the conclusion that it is probably not possible to do so if the circle is sharing an edge with the AABB... If someone knows how, please let me know!

Zakwayda

Apr 22, 2009 at 1:38 PM

I didn't quite follow the details of the problem you've presented, so I don't have a definite answer, but I will offer one idea to consider.

When I've done this sort of thing in the past, I haven't used any sort of buffer or epsilon, and instead have used both static and dynamic tests.

Basically, I set up my collision detection functions to return a 'package' of information that indicates whether the intersection is static (that is, the objects are already intersecting and possibly penetrating) or dynamic (intersection at t > 0).

If the intersection is static, the minimum translational vector and contact points corresponding to the object configuration after the penetration is resolved are returned. If the intersection is dynamic, the time of intersection and the contact points corresponding to the object configuration at the time of intersection is returned.

The idea is that instead of using epsilons, thresholds, or buffers, you simply handle each type of intersection - static or dynamic - as appropriate.

Disclaimer: I created some 'sandbox' applications using this approach, but I don't think I really ever gave it a thorough workout, so I can't say with certainty that it's the best approach overall.

There are other options you could consider as well (and maybe already have). For example, if the per-update displacement of the circle will always be less than its radius, you could use a static/discrete test only. This approach is *much* simpler to implement than the dynamic version, and gives you nice sliding collision response essentially for free.

VBStrider

Apr 22, 2009 at 2:06 PM

Unfortunately, the circle's movement vector magnitude could be (and usually is) greater than the circle's radius, so I have to handle the "dynamic" situation.

Thanks for the reply, but the problem mostly lies with resolving the collision. Lets say a dynamic collision is detected. How is this collision corrected? Do you move the circle back to the point of intersection (option #2 in my previous post), or move the circle back to the point of intersection and a little further (option #1)?

I am fairly new to this form of collision detection/response, so I could be going about this the wrong way. I've got this far mostly based off of what I have read and results I have gathered from numerous tests...

Zakwayda

Apr 22, 2009 at 2:14 PM

Quote:
Thanks for the reply, but the problem mostly lies with resolving the collision. Lets say a dynamic collision is detected. How is this collision corrected? Do you move the circle back to the point of intersection (option #2 in my previous post), or move the circle back to the point of intersection and a little further (option #1)?

What do you want to happen when the circle collides with a box? Should it slide? Bounce? Or just come to a stop?

VBStrider

Apr 22, 2009 at 2:46 PM

The eventual goal is to make the circle slide. However, from what I understand of sliding techniques, the first step is to resolve the collision. So right now I just want to make the circle stop. I'll add the sliding technique after that is working correctly.

The sliding technique I'm planning on using is described here, if you are interested: http://www.peroxide.dk/download/tutorials/tut10/pxdtut10.html

ValMan

Apr 22, 2009 at 2:59 PM

What if you try to maintain the contact info (each object has a list of objects it currently touches)? This is something you probably need anyway (so you can detect player standing on a moving elevator in a platformer game, for instance).

Collision queries could also return 3 states: intersecting, touching and no collision. If a collision status is intersecting, you handle that first and move the object(s) to unpenetrate (collision validation), then change collision status to touching. Once that done (or if collision is already touching), apply forces to both objects (collision response).

The "touching" state would be caused by the smallest separation distance being less than 2 pixels - I guess - since it's a 2D game.

One last thing you can try is using a combination of sweep test and sampling test somehow. Sampling test is when you choose a fixed step size (let's say 1/2 if your cicle's radius) and then figure out how much time must pass during that step, based on relative speeds. Then sample over a certain time span with that time increment - each time the collision detection would be 100% static, so do need to worry about dynamic collision. I know you said dynamic collisions are not the problem, but I thought I would mention this to give you more tools, in case you don't already know.

VBStrider

Apr 22, 2009 at 3:23 PM

Thanks for the suggestions, but your solution is basically what I already do. If the circle is intersecting the AABB, it is moved back to the intersection point + 1 pixel. However, this causes the problem I mentioned in the first post.

oliii

Apr 22, 2009 at 5:53 PM

if that's any help to you, I have some 2D swept sphere - polygon collision code.

The method is more complicated than what's explained in the doc you provided, however I believe the algorithm presented there is flawed.

Erik Rufelt

Apr 22, 2009 at 6:07 PM

Are you doing this in the integers, or with floating point math?
You are talking about pixels, but still you use spheres, that don't seem to be approximated by pixels.

VBStrider

Apr 22, 2009 at 6:50 PM

Quote:
if that's any help to you, I have some 2D swept sphere - polygon collision code.

The code was helpful, but I can't quite make out what it is doing. Could you please tell me what it is supposed to be doing exactly?

Quote:
The method is more complicated than what's explained in the doc you provided, however I believe the algorithm presented there is flawed.

Alright, thanks for pointing that out. Do you have another article I could read on the subject that is more accurate?

Quote:
Are you doing this in the integers, or with floating point math?

Floating point math.

Quote:
You are talking about pixels, but still you use spheres, that don't seem to be approximated by pixels.

I want to keep the circle outside of the AABB by 1 pixel so that the circle does not appear to be inside of the AABB. There needed to be a buffer anyways, so I went with making it 1 pixel thick.

VBStrider

Apr 23, 2009 at 4:24 PM

oliii, I went through the source code your linked to and changed it to have a similar structure to mine (as far as updating the sphere's position goes). From what I can tell, the same problem I am having is now present in your demo. This leads me to believe that at least one of three things is happening:
1. I am handling moving the sphere incorrectly.
2. I am using the collision detection/response code incorrectly.
3. Since your code did not really prevent intersection to start with (it only displayed where the sphere would end up if it was moved back) it is possible that your code did not contain a solution to the problem.

Here is my version of your demo: http://www.ifthensoftware.net/invisibleman/SpherePolygonCollision.cpp

What am I doing wrong? :S

oliii

Apr 23, 2009 at 4:37 PM

The peroxyde method will do the same (except miss some cases).

I can outline the algorithm, It's quite simple

1) find which edge is 'front facing' the sphere centre.
2) do a swept test of the sphere against those edges.
- this is like doing a ray-capsule test.
- so break down the edge into spheres at the end points, and the central area, and test against those.

if the centre of the sphere is inside the polygon, compute the intersection vector by finding the closest edge and the distance from the sphere cenrte to the edge.

the peroxyde algo will find the closest point on the polygon to the sphere centre, then do a sphere-point collision test against that point.

That fails when the closest point on the polygon is not actually nearby the actual point of collision (when the sphere path is almost parallel to an edge).

I'll have a read at what you do again, but I'm not sure if that can be solved simply.

VBStrider

Apr 23, 2009 at 4:45 PM

There must be a solution... I mean, I figured I was taking it easy by doing moving circle-AABB collision detection and intersection with just blocking and no sliding... It seems like a fairly basic situation.

oliii

Apr 24, 2009 at 3:02 AM

well, you could always make the sphere radius 1 pixel bigger.

The problem seems to be with having a integer resolution. If the case you present, the sphere does miss the box, by a fraction of a pixel. If you wanted the sphere to hit the box, the sphere would just hit the corner of box, if the sphere was slightly bigger (or the box), that case would be accounted for.

oliii

Apr 24, 2009 at 3:20 AM

BTW, the problem of never allowing intersections to occur is a tricky one. You need all kinds of fail-safe, thresholds to make it happen. And what do you do if one does occur?

Quake3 has such system, iirc, intersections are just ignored until the object moves out of the intersection. I remember a map where a spawn point would be placed within a brush, thus making you fall through the floor. So it's not ideal.

VBStrider

Apr 24, 2009 at 9:14 AM

Would it be best to go with option #2 then? If so, how do I fix the problem in the demo I posted earlier (your altered source)? That demo made use of option #2 rather than option #1 which my first post in this thread was about.

If I have to go with option #2, it's fairly simple to prevent the pixel problem. Simply increase the sphere's collision area by 1 pixel (increase the collision sphere's radius by 1 pixel). However, the reason I have not done this is because of the "sticky" problem that I have described and that is demonstrated in the source code I posted.

oliii

Apr 24, 2009 at 10:54 AM

Quote:
Original post by VBStrider
Would it be best to go with option #2 then? If so, how do I fix the problem in the demo I posted earlier (your altered source)? That demo made use of option #2 rather than option #1 which my first post in this thread was about.

If I have to go with option #2, it's fairly simple to prevent the pixel problem. Simply increase the sphere's collision area by 1 pixel (increase the collision sphere's radius by 1 pixel). However, the reason I have not done this is because of the "sticky" problem that I have described and that is demonstrated in the source code I posted.

I'll have a look at your sample.

VBStrider

Apr 28, 2009 at 9:33 AM

I don't mean to nag, but have you had a look at the code yet? I really need this fixed soon...

oliii

Apr 28, 2009 at 10:35 AM

yup I did, however, I changed the algorithm

#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;}

My web space is buggered, so it has to be a code dump. To fix the old code would require a bit of surgery (there are a couple of bugs).

[Edited by - oliii on April 28, 2009 11:35:16 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.