Collision Handling
Author
Hi!
I am programming a 3D space shooter. I am at the point where I can do interscetion tests for my spaceships now and get reported back whether an intersection has taken place and what the line segments of intersection are.
I also read a bit of Chris Hecker's articles and the wikipedia article on collision response and I am not sure if I get the next steps quite together.
I guess I need to determine the exact time of collision, probaly using a binary search by adjusting the timestep. How do I deal with the line segments though? Is it possible to condense this to one central collisiob point? And how do I find the plane of collision given that I am colliding two arbitrary meshes?
I'm trying to get the basics implemented without things getting too complicated here.
(And: how do deal with a colliding spaceship possibly getting tossed back into *another* spaceship causing a *secondary* collision in the same timestep?)
Plenty of questions, I know, but if you could lift my uncertainty about some of them, I'd be grateful.
Alex
Quote:Original post by ak-73
I guess I need to determine the exact time of collision..
It sounds like you're doing several physics timesteps for every collision detection call. If so, it won't be perfectly smooth, but that may be acceptable. When a collision is detected (don't know what line segments you may be determining), the bodies will have interpenetrated. Calculate the point of intersection, the depth of penetration and a normal vector at the collision point. That gives you the plane of collision. Only after all collisions have been detected, calculate the force on each body due to all collisions on that body that timestep. Use those forces to change the body's velocity and torque (if you use torque).
Quote:And: how do deal with a colliding spaceship possibly getting tossed back into *another* spaceship causing a *secondary* collision in the same timestep?
You don't. You don't apply physics ("getting tossed back") until after all collisions have been detected. When you detect collisions, there's either a collision between two bodies or not in that timestep. If there's going to be a "secondary" collision, that will be detected during the next collision detection cycle.
If the actions of your bodies seem too coarse for your taste (e.g., too much interpenetration), perform the collision detection more often.
Author
Quote:Original post by Buckeye
It sounds like you're doing several physics timesteps for every collision detection call. If so, it won't be perfectly smooth, but that may be acceptable. When a collision is detected (don't know what line segments you may be determining), the bodies will have interpenetrated. Calculate the point of intersection, the depth of penetration and a normal vector at the collision point. That gives you the plane of collision.
Between two arbitrarily intersecting triangles, I suppose I can take the middle of the intersection line segment as collision point. How do I derive the normal vector of the collision though?
Quote:
Only after all collisions have been detected, calculate the force on each body due to all collisions on that body that timestep. Use those forces to change the body's velocity and torque (if you use torque).
So I am going to let the bodies interpenetrate in that timestep?
Wouldn't I have to calculate the time of collision and integrate with the post-collision forces only for the remaining time interval within the the current timestep?
Quote:
You don't. You don't apply physics ("getting tossed back") until after all collisions have been detected. When you detect collisions, there's either a collision between two bodies or not in that timestep. If there's going to be a "secondary" collision, that will be detected during the next collision detection cycle.
If the actions of your bodies seem too coarse for your taste (e.g., too much interpenetration), perform the collision detection more often.
Oh, okay. thanks.
Alex
I'll put forward another example for collision detection with convex shapes (triangles, boxes, polygons, ...) here.
and some explanation.
and some explanation.
hey!
[Edited by - oliii on March 9, 2010 2:28:05 PM]
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// POLYGON / POLYGON COLLISION////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// maths#include <math.h>struct Vector{ float x, y;};float vector_dot_product(const Vector& a, const Vector& b){ return (a.x*b.x + a.y*b.y);}float vector_length(const Vector& a){ return sqrt(a.x*a.x+a.y*a.y);}Vector vector_subtract(const Vector& a, const Vector& b){ Vector result; result.x = a.x - b.x; result.y = a.y - b.y; return result;}Vector vector_direction(const Vector& a){ float l = vector_length(a); Vector dir; dir.x = a.x/l; dir.y = a.y/l; return dir;}// results of a collisoin test between polygons.struct CollisionResult{ CollisionResult() : m_collision_found(false) , m_intersection_found(false) {} bool m_collision_found; float m_collision_time; Vector m_collision_normal; bool m_intersection_found; Vector m_intersection_direction; float m_intersection_depth;};// parameters used for polygon collision tests.struct CollisionParams{ CollisionParams(float max_time, const Vector& velocity) : m_collide_max_time(max_time) , m_collide_velocity(velocity) , m_enter_valid(false) , m_exit_valid(false) , m_intersect_valid(false) , m_intersection_failed(false) , m_collision_failed(false) {} // parameters for objects entering collision state. bool m_enter_valid; float m_enter_time; Vector m_enter_axis; // parameters for objects leaving collision state. bool m_exit_valid; float m_exit_time; Vector m_exit_axis; // parameters for objects intersecting. bool m_intersect_valid; float m_intersect_depth_squared; Vector m_intersect_axis; // objects intersect or collide? bool m_intersection_failed; bool m_collision_failed; // collision input parameters. const float m_collide_max_time; // maximum time allowed for detecting collisions. const Vector m_collide_velocity; // relative velocity of objects.}; // find how far a polygon extends along a directionfloat FindPolygonSupport(const Vector& axis, const Vector* v, const int v_count, bool positive){ float support = vector_dot_product(axis, v[0]); for(int i = 1; i < v_count; i ++) { float project = vector_dot_product(axis, v); if( project > support && positive || project < support && !positive) support = project; } return support;} // check if two polygons can collide along a direction.void CollidePolygonsAlongAxis( const Vector& axis, const Vector* a, const int a_count, const Vector* b, const int b_count, CollisionParams& params){ // support information about the objects along that axis. float support_a = FindPolygonSupport(axis, a, a_count, true); float support_b = FindPolygonSupport(axis, b, b_count, false); float delta = (support_a - support_b); // objects intersect along that axis? bool intersecting = (support_a >= support_b); // if not intersecting on that axis, objects wont intersect at all. if(!intersecting) params.m_intersection_failed = true; //------------------------------------------------------------ // intersection test. //------------------------------------------------------------ if(!params.m_intersection_failed) { // yet, intersecting. Check if our intersection depth is smaller than // previously found. if(intersecting) { // calcualte the amount of intersection along that axis. float axis_length_squared = vector_dot_product(axis, axis); float intersection_length_squared = (delta * delta) / axis_length_squared; // this amount is less that our current intersection candidate. // that will be our new intersection candidate. if(!params.m_intersect_valid || (intersection_length_squared < params.m_intersect_depth_squared)) { // update SAT intersection params params.m_intersect_valid = true; params.m_intersect_depth_squared = intersection_length_squared; params.m_intersect_axis = axis; } } } //------------------------------------------------------------ // collision test. //------------------------------------------------------------ if(!params.m_collision_failed) { // velocity projected on axis. float vel = vector_dot_product(axis, params.m_collide_velocity); // velocity perpendicular to axis (or no velocity at all). // objects will potentially collide only // if objects intersect along that axis. if(fabs(vel) < 0.0001f) { // but we are not intersecting along that axis // so we'll miss collisions. if(!intersecting) params.m_collision_failed = true; return; } // time of collision along that axis. float t = delta / vel; // objects moving towards each other // we'll be entering a collision if(vel < 0.0f) { // the objects are too far away. if(t > params.m_collide_max_time) { params.m_collision_failed = true; return; } // time of collision greater than our last entry time. update. if((!params.m_enter_valid) || (t > params.m_enter_time)) { params.m_enter_valid = true; params.m_enter_time = t; params.m_enter_axis = axis; } } // objects moving away from each other // we'll be leaving a collision. else { // time of collision greater than our entry time. update. if((!params.m_exit_valid) || (t < params.m_exit_time)) { params.m_exit_valid = true; params.m_exit_time = t; params.m_exit_axis = axis; } } // collision enter and exit time inconsistent. // It means objects missed each other. if( (params.m_enter_valid) && (params.m_exit_valid) && (params.m_enter_time > params.m_exit_time)) { params.m_collision_failed = true; } }}//------------------------------------------------------------------------------------------------------------// collide two polygons. returns the time of collision, normal of collision, intersection depth and so on.// [a, a_count]. first polygon vertices.// va : first polygon velocity.// a_winding : winding of the vertices of first polygon (counter_clockwise -> 1.0f, clockwise -> -1.0f).// [b, b_count]. second polygon vertices.// vb : second polygon velocity.// b_winding : winding of the vertices of second polygon (counter_clockwise -> 1.0f, clockwise -> -1.0f).//------------------------------------------------------------------------------------------------------------bool CollidePolygons( const Vector* a, const int a_count, const Vector& va, float a_winding, const Vector* b, const int b_count, const Vector& vb, float b_winding, float max_time, CollisionResult& results){ // reset collision report. results.m_collision_found = false; results.m_intersection_found = false; // reset collision params. CollisionParams params(max_time, vector_subtract(vb, va)); // test edge normals of object a. for(int i = 0, j=(a_count-1); i < a_count; j=i, i ++) { Vector e = vector_subtract(a, a[j]); Vector axis; axis.x = (-e.y * a_winding); axis.y = ( e.x * a_winding); // check collision along the edge normal. CollidePolygonsAlongAxis(axis, a, a_count, b, b_count, params); // no point continuing tests if we already know there is no overlap // and no collisions possible. if(params.m_intersection_failed && params.m_collision_failed) return false; } // test edge normals of object b. for(int i = 0, j=(b_count-1); i < b_count; j=i, i ++) { Vector e = vector_subtract(b, b[j]); Vector axis; axis.x = ( e.y * a_winding); axis.y = (-e.x * a_winding); // check collision along the edge normal. CollidePolygonsAlongAxis(axis, a, a_count, b, b_count, params); // no point continuing tests if we already know there is no overlap // and no collisions possible. if(params.m_intersection_failed && params.m_collision_failed) return false; } // intersection is valid. setup intersection data. if(!params.m_intersection_failed && params.m_intersect_valid) { results.m_intersection_found = true; results.m_intersection_depth = sqrt(params.m_intersect_depth_squared); results.m_intersection_direction = vector_direction(params.m_intersect_axis); } // collision is valid. setup collision data. if(!params.m_collision_failed && params.m_exit_valid && params.m_enter_valid) { results.m_collision_found = true; results.m_collision_normal = vector_direction(params.m_enter_axis); results.m_collision_time = params.m_enter_time; } // we found an intersection, or a collision (or both). return (results.m_collision_found || results.m_intersection_found);}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// END OF POLYGON / POLYGON COLLISION////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// DEMO MAIN////////////////////////////////////////////////////////////////////////////////////////////#include <stdio.h>#include <stdlib.h>#include <math.h>#include <gl/glut.h>//--------------------------------------------------------------------------// window size//--------------------------------------------------------------------------int width = 640;int height = 480;void Reset(float polygonSize, float width, float height);void Render();void StartDrag(int x, int y);void UpdateDrag(int x, int y);void StopDrag();//-----------------------------------------------------// displays the objects//-----------------------------------------------------void Display(){ //-------------------------------------------------------------------------- // render stuff //-------------------------------------------------------------------------- glViewport( 0, 0, width, height); glClearColor(0.2f, 0.2f, 0.2f, 0.2f); glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glMatrixMode(GL_PROJECTION); glLoadIdentity(); gluOrtho2D(0, width, 0, height); //----------------------------------------------------------------- // Setup the model view matrix //----------------------------------------------------------------- glMatrixMode(GL_MODELVIEW); glLoadIdentity(); Render(); glutSwapBuffers();}void Mouse(int buttons, int state, int x, int y){ if (buttons == GLUT_LEFT_BUTTON) { if(state == GLUT_DOWN) StartDrag(x, height-y); else StopDrag(); }}void Motion(int x, int y){ UpdateDrag(x, height-y);}void Timer(int t){ Display(); glutTimerFunc(t, Timer, (int) 500.0f / 60.0f);} void Reshape(int w, int h){ width = w; height = h;}void Keyboard(unsigned char key, int x, int y){ if (key == 27) exit(0); if(key == ' ') Reset(width / 20.0f, width, height);}void main(int argc, char** argv){ //-------------------------------------------------------------------------- // OpenGL / GLUT init //-------------------------------------------------------------------------- glutInit( &argc, argv ); glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGBA | GLUT_DEPTH); glutInitWindowSize (width, height); glutInitWindowPosition (0, 0); glutCreateWindow ("Polygon Collision"); glPointSize(3.0f); glEnable (GL_BLEND); glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); glDisable (GL_DEPTH_TEST); glDisable (GL_LIGHTING); glutDisplayFunc (Display); glutReshapeFunc (Reshape); glutTimerFunc (0, Timer, (int) 100.0f / 60.0f); glutMouseFunc (Mouse); glutMotionFunc (Motion); glutKeyboardFunc (Keyboard); Reset(width / 15.0f, width, height); glutMainLoop();}////////////////////////////////////////////////////////////////////////////////////////////// DEMO CODE////////////////////////////////////////////////////////////////////////////////////////////Vector FindPolygonSupport(const Vector& axis, const Vector* v, const int v_count){ float support = vector_dot_product(axis, v[0]); Vector vertex = v[0]; for(int i = 1; i < v_count; i ++) { float project = vector_dot_product(axis, v); if( project > support) { vertex = v; support = project; } } return vertex;}float TwoPi(){ static const float two_pi = atan(1.0f) * 8.0f; return two_pi;}float Random(float min, float max) { return min + (rand() / (float)(RAND_MAX)) * (max - min);}// extended vector structure// WARNING. Lazy use of C++. do not emulate!struct Vector2: public Vector{ inline Vector2(void){} inline Vector2(const Vector& v) { x = v.x; y = v.y; } inline Vector2(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 Vector2 &other) { x += other.x; y += other.y; return *this; } inline Vector &operator -=(const Vector2 &other) { x -= other.x; y -= other.y; return *this; } inline float operator ^ (const Vector2 &other) const { return (x * other.y) - (y * other.x); } // cross product inline float operator * (const Vector2 &other) const { return (x * other.x) + (y * other.y); } // dot product inline Vector2 operator * (float scalar) const { return Vector2(x * scalar, y * scalar); } inline Vector2 operator / (float scalar) const { return Vector2(x / scalar, y / scalar); } inline Vector2 operator + (const Vector2 &other) const { return Vector2(x + other.x, y + other.y); } inline Vector2 operator - (const Vector2 &other) const { return Vector2(x - other.x, y - other.y); } inline Vector2 operator -(void) const { return Vector2(-x, -y); } inline float length(void) const { return (float) sqrt(x*x + y*y); } inline Vector2 direction(void) const { return (*this) / length(); } inline float normalise(void) { float l = length(); if (l < 0.00001f) return l; (*this) /= l; return l; } friend Vector2 operator * (float scalar, const Vector& other) { return Vector2(other.x * scalar, other.y * scalar); }};Vector2 a[32];Vector2 b[32];int a_count = 0;int b_count = 0;float a_winding=0.0f;float b_winding=0.0f;Vector2 a0, a1;Vector2 b0, b1;Vector2* drag=NULL;void Reset(float size, float width, float height){ drag = NULL; a0.x = Random(0, width); a0.y = Random(0, height); a1.x = Random(0, width); a1.y = Random(0, height); b0.x = Random(0, width); b0.y = Random(0, height); b1.x = Random(0, width); b1.y = Random(0, height); // reset polygon a (vertices are wound anti-clockwise). a_count = (3 + rand() % 6); a_winding = (rand() % 10 < 5)? -1.0f : 1.0f; float angle = Random(0.0f, TwoPi()); float radius = Random(size / 2.0f, size) + size / 2.0f; float delta_angle = -(TwoPi() / a_count) * a_winding; for(int i = 0; i < a_count; i++, angle += delta_angle) { a = a0 + Vector2(cos(angle), sin(angle)) * radius; } // reset polygon b (vertices are wound anti-clockwise). b_count = (3 + rand() % 6); b_winding = (rand() % 10 < 5)? -1.0f : 1.0f; angle = Random(0.0f, TwoPi()); radius = Random(size / 2.0f, size) + size / 2.0f; delta_angle = -(TwoPi() / b_count) * b_winding; for(int i = 0; i < b_count; i++, angle += delta_angle) { b = b0 + Vector2(cos(angle), sin(angle)) * radius; }}void renderLine(const Vector2& a, const Vector2& b, unsigned int colour){ glColor4ub( (colour >> 16) & 0xff, (colour >> 8) & 0xff, (colour >> 0) & 0xff, (colour >> 24) & 0xff); glBegin(GL_LINES); glVertex2f(a.x, a.y); glVertex2f(b.x, b.y); glEnd();}void renderPolygon(const Vector2* v, int v_count, const Vector2& pos, unsigned int colour, bool solid){ glColor4ub( (colour >> 16) & 0xff, (colour >> 8) & 0xff, (colour >> 0) & 0xff, (colour >> 24) & 0xff); glPushMatrix(); glTranslatef(pos.x, pos.y, 0.0f); glBegin(solid? GL_POLYGON : GL_LINE_LOOP); for(int i = 0; i < v_count; i++) glVertex2f(v.x, v.y); glEnd(); glPopMatrix();}void renderArrow(const Vector2& start, const Vector2& end, unsigned int colour){ glColor4ub( (colour >> 16) & 0xff, (colour >> 8) & 0xff, (colour >> 0) & 0xff, (colour >> 24) & 0xff); Vector2 dir = (end - start); float length = dir.normalise(); float thick = 4.0f; Vector2 side = Vector2(-dir.y, dir.x); Vector2 left = end - (dir * thick * 2) + (side * thick); Vector2 right = end - (dir * thick * 2) - (side * thick); glBegin(GL_LINES); glVertex2f(start.x, start.y); glVertex2f(end.x, end.y); glEnd(); glBegin(GL_TRIANGLES); glVertex2f(end.x, end.y); glVertex2f(left.x, left.y); glVertex2f(right.x, right.y); glEnd();}void renderPoint(const Vector2& pos, float size, unsigned int colour){ glColor4ub( (colour >> 16) & 0xff, (colour >> 8) & 0xff, (colour >> 0) & 0xff, (colour >> 24) & 0xff); glPointSize(size); glEnable(GL_POINT_SMOOTH); glBegin(GL_POINTS); glVertex2f(pos.x, pos.y); glEnd(); glPointSize(1.0f); }void renderPlane(const Vector2& pos, const Vector2& norm, unsigned int colour){ glColor4ub( (colour >> 16) & 0xff, (colour >> 8) & 0xff, (colour >> 0) & 0xff, (colour >> 24) & 0xff); Vector2 side = Vector2(-norm.y, norm.x); Vector2 plane_left = pos + side * 4.0f; Vector2 plane_right = pos - side * 4.0f; renderArrow(pos, pos + norm, colour); glEnable(GL_LINE_STIPPLE); glLineStipple(1, 0xf0); renderLine(plane_left, plane_right, colour); glDisable(GL_LINE_STIPPLE);}void Render(){ bool render_collision = false; float tcoll = 0.0f; Vector2 dcoll(0.0f, 0.0f); Vector2 ncoll(0.0f, 0.0f); CollisionResult result; if(CollidePolygons( a, a_count, (a1 - a0), a_winding, b, b_count, (b1 - b0), b_winding, 1.0f, result)) { if(result.m_intersection_found) { render_collision = true; ncoll = result.m_intersection_direction; dcoll = Vector2(result.m_intersection_direction) * result.m_intersection_depth; tcoll = 0.0f; } else if(result.m_collision_found) { render_collision = true; ncoll = result.m_collision_normal; tcoll = (result.m_collision_time < 0.0f)? 0.0f : result.m_collision_time; dcoll = Vector2(0.0f, 0.0f); } } glLineWidth(2.0f); renderPolygon(a, a_count, Vector2(0, 0), 0x500000ff, true); renderPolygon(b, b_count, Vector2(0, 0), 0x5000ff00, true); renderPolygon(a, a_count, Vector2(0, 0), 0xffffffff, false); renderPolygon(b, b_count, Vector2(0, 0), 0xffffffff, false); if(render_collision) { Vector2 acoll = (a1 - a0) * tcoll; Vector2 bcoll = (b1 - b0) * tcoll + dcoll; glLineWidth(2.0f); renderPolygon(a, a_count, (acoll), 0x200000ff, true); renderPolygon(b, b_count, (bcoll), 0x2000ff00, true); renderPolygon(a, a_count, (acoll), 0x80ffffff, false); renderPolygon(b, b_count, (bcoll), 0x80ffffff, false); glLineWidth(1.0f); renderLine(a0, a1, 0x80ffffff); renderLine(b0, b1, 0x80ffffff); renderArrow(a0, a0 + acoll, 0xffffffff); renderArrow(b0, b0 + bcoll, 0xffffffff); // render collision plane Vector2 support = FindPolygonSupport(-ncoll, b, b_count); Vector2 plane_pos = bcoll + b0 + ((support - b0) * ncoll) * ncoll; Vector2 plane_norm = ncoll * 50; glLineWidth(1.0f); renderPlane(plane_pos, plane_norm, 0xffff8080); } else { glLineWidth(1.0f); renderArrow(a0, a1, 0xffffffff); renderArrow(b0, b1, 0xffffffff); } renderPoint(a0, 8.0f, 0x40ffffff); renderPoint(b0, 8.0f, 0x40ffffff); renderPoint(a1, 8.0f, 0x40ffffff); renderPoint(b1, 8.0f, 0x40ffffff);}void StartDrag(int x, int y){ Vector2 pick(x, y); drag = &a0; if((pick - a1).length() < (pick - *drag).length()) drag = &a1; if((pick - b0).length() < (pick - *drag).length()) drag = &b0; if((pick - b1).length() < (pick - *drag).length()) drag = &b1;}void UpdateDrag(int x, int y){ if(drag) { if(drag == &a0) { for(int i = 0; i < a_count; i++) a += (Vector2(x, y) - a0); } if(drag == &b0) { for(int i = 0; i < b_count; i++) b += (Vector2(x, y) - b0); } drag->x = x; drag->y = y; }}void StopDrag(){ drag = NULL;}[Edited by - oliii on March 9, 2010 2:28:05 PM]
Quote:
How does that translate (lol, no pun intended) into 3 dimensions though?
Alex
Pretty much the same, when you have two convex polytopes (box, pyramid, prism, even triangles and convex polygons).
in 3D, what you need from both objects are a list of face normals, and edge directions. the axes to tests are face normals and cross products of edges.
However for the 3D version, I would use the object's projected intervals though to calculate the intersection and collision data.
that's the code working with intervals
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// POLYGON / POLYGON COLLISION////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// maths#include <math.h>struct Vector{ float x, y;};float vector_dot_product(const Vector& a, const Vector& b){ return (a.x*b.x + a.y*b.y);}float vector_length(const Vector& a){ return sqrt(a.x*a.x+a.y*a.y);}Vector vector_opposite(const Vector& a){ Vector result; result.x = -a.x; result.y = -a.y; return result;}Vector vector_subtract(const Vector& a, const Vector& b){ Vector result; result.x = a.x - b.x; result.y = a.y - b.y; return result;}Vector vector_direction(const Vector& a){ float l = vector_length(a); Vector dir; dir.x = a.x/l; dir.y = a.y/l; return dir;}// results of a collisoin test between polygons.struct CollisionResult{ CollisionResult() : m_collision_found(false) , m_intersection_found(false) {} bool m_collision_found; float m_collision_time; Vector m_collision_normal; bool m_intersection_found; Vector m_intersection_direction; float m_intersection_depth;};// parameters used for polygon collision tests.struct CollisionParams{ CollisionParams(float max_time, const Vector& velocity) : m_collide_max_time(max_time) , m_collide_velocity(velocity) , m_enter_valid(false) , m_exit_valid(false) , m_intersect_valid(false) , m_intersection_failed(false) , m_collision_failed(false) {} // parameters for objects entering collision state. bool m_enter_valid; float m_enter_time; Vector m_enter_axis; // parameters for objects leaving collision state. bool m_exit_valid; float m_exit_time; Vector m_exit_axis; // parameters for objects intersecting. bool m_intersect_valid; float m_intersect_depth_squared; Vector m_intersect_axis; // objects intersect or collide? bool m_intersection_failed; bool m_collision_failed; // collision input parameters. const float m_collide_max_time; // maximum time allowed for detecting collisions. const Vector m_collide_velocity; // relative velocity of objects.}; // find how far a polygon extends along a directionvoid FindPolygonInterval(const Vector& axis, const Vector* v, const int v_count, float& min, float& max){ float project = vector_dot_product(axis, v[0]); min = max = project; for(int i = 1; i < v_count; i ++) { float project = vector_dot_product(axis, v); if(project < min) min = project; else if(project > max) max = project; }} // check if two polygons can collide along a direction.void CollidePolygonsAlongAxis( const Vector& axis, const Vector* a, const int a_count, const Vector* b, const int b_count, CollisionParams& params){ float mina, maxa; float minb, maxb; FindPolygonInterval(axis, a, a_count, mina, maxa); FindPolygonInterval(axis, b, b_count, minb, maxb); // objects intersect along that axis? bool intersecting = (mina <= maxb && maxa >= minb); // if not intersecting on that axis, objects wont intersect at all. if(!intersecting) params.m_intersection_failed = true; //------------------------------------------------------------ // intersection test. //------------------------------------------------------------ if(!params.m_intersection_failed) { // yet, intersecting. Check if our intersection depth is smaller than // previously found. // calcualte the amount of intersection along that axis. float delta1 = (maxa - minb); float delta2 = (maxb - mina); float delta = (delta1 < delta2)? delta1 : delta2; float axis_length_squared = vector_dot_product(axis, axis); float intersection_length_squared = (delta * delta) / axis_length_squared; // this amount is less that our current intersection candidate. // that will be our new intersection candidate. if(!params.m_intersect_valid || (intersection_length_squared < params.m_intersect_depth_squared)) { // update SAT intersection params params.m_intersect_depth_squared = intersection_length_squared; params.m_intersect_valid = true; params.m_intersect_axis = (delta1 > delta2)? vector_opposite(axis) : axis; } } //------------------------------------------------------------ // collision test. //------------------------------------------------------------ if(!params.m_collision_failed) { // velocity projected on axis. float vel = vector_dot_product(axis, params.m_collide_velocity); // velocity perpendicular to axis (or no velocity at all). // objects will potentially collide only // if objects intersect along that axis. if(fabs(vel) < 0.0001f) { // but we are not intersecting along that axis // so we'll miss collisions. if(!intersecting) params.m_collision_failed = true; return; } // collision times when intervals are just touching float t0 = (maxa - minb) / vel; float t1 = (mina - maxb) / vel; // sort times for when intervals start intersecting // and when intervals stop intersecting. float t_enter; float t_exit; Vector n_enter; Vector n_exit; if(t0 < t1) { t_enter = t0; t_exit = t1; n_enter = axis; n_exit = vector_opposite(axis); } else { t_enter = t1; t_exit = t0; n_enter = vector_opposite(axis); n_exit = axis; } // the objects are too far away. if(t_enter > params.m_collide_max_time) { params.m_collision_failed = true; return; } // the objects are behind each other. if(t_exit < 0.0f) { params.m_collision_failed = true; return; } // time of collision greater than our entry time. update. if((!params.m_exit_valid) || (t_exit < params.m_exit_time)) { params.m_exit_valid = true; params.m_exit_time = t_exit; params.m_exit_axis = n_exit; } // time of collision greater than our last entry time. update. if((!params.m_enter_valid) || (t_enter > params.m_enter_time)) { params.m_enter_valid = true; params.m_enter_time = t_enter; params.m_enter_axis = n_enter; } // collision enter and exit time inconsistent. // It means objects missed each other. if( (params.m_enter_valid) && (params.m_exit_valid) && (params.m_enter_time > params.m_exit_time)) { params.m_collision_failed = true; } }}//------------------------------------------------------------------------------------------------------------// collide two polygons. returns the time of collision, normal of collision, intersection depth and so on.// [a, a_count]. first polygon vertices.// va : first polygon velocity.// a_winding : winding of the vertices of first polygon (counter_clockwise -> 1.0f, clockwise -> -1.0f).// [b, b_count]. second polygon vertices.// vb : second polygon velocity.// b_winding : winding of the vertices of second polygon (counter_clockwise -> 1.0f, clockwise -> -1.0f).//------------------------------------------------------------------------------------------------------------bool CollidePolygons( const Vector* a, const int a_count, const Vector& va, const Vector* b, const int b_count, const Vector& vb, float max_time, CollisionResult& results){ // reset collision report. results.m_collision_found = false; results.m_intersection_found = false; // reset collision params. CollisionParams params(max_time, vector_subtract(vb, va)); // test edge normals of object a. for(int i = 0, j=(a_count-1); i < a_count; j=i, i ++) { Vector e = vector_subtract(a, a[j]); Vector axis; axis.x = (-e.y); axis.y = ( e.x); // check collision along the edge normal. CollidePolygonsAlongAxis(axis, a, a_count, b, b_count, params); // no point continuing tests if we already know there is no overlap // and no collisions possible. if(params.m_intersection_failed && params.m_collision_failed) return false; } // test edge normals of object b. for(int i = 0, j=(b_count-1); i < b_count; j=i, i ++) { Vector e = vector_subtract(b, b[j]); Vector axis; axis.x = ( e.y); axis.y = (-e.x); // check collision along the edge normal. CollidePolygonsAlongAxis(axis, a, a_count, b, b_count, params); // no point continuing tests if we already know there is no overlap // and no collisions possible. if(params.m_intersection_failed && params.m_collision_failed) return false; } // intersection is valid. setup intersection data. if(!params.m_intersection_failed && params.m_intersect_valid) { results.m_intersection_found = true; results.m_intersection_depth = sqrt(params.m_intersect_depth_squared); results.m_intersection_direction = vector_direction(params.m_intersect_axis); } // collision is valid. setup collision data. if(!params.m_collision_failed && params.m_exit_valid && params.m_enter_valid) { results.m_collision_found = true; results.m_collision_normal = vector_direction(params.m_enter_axis); results.m_collision_time = params.m_enter_time; } // we found an intersection, or a collision (or both). return (results.m_collision_found || results.m_intersection_found);}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// END OF POLYGON / POLYGON COLLISION////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
nd a 3D example (box versus polygon)
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// POLYGON / POLYGON COLLISION////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// maths#include <math.h>struct Vector{ float x, y, z;};float vector_dot_product(const Vector& a, const Vector& b){ return (a.x*b.x + a.y*b.y + a.z*b.z);}Vector vector_cross_product(const Vector& a, const Vector& b){ Vector cross; cross.x = (a.y*b.z - a.z*b.y); cross.y = (a.z*b.x - a.x*b.z); cross.z = (a.x*b.y - a.y*b.x); return cross;}float vector_length(const Vector& a){ return sqrt(a.x*a.x+a.y*a.y + a.z*a.z);}Vector vector_opposite(const Vector& a){ Vector result; result.x = -a.x; result.y = -a.y; result.z = -a.z; return result;}Vector vector_subtract(const Vector& a, const Vector& b){ Vector result; result.x = a.x - b.x; result.y = a.y - b.y; result.z = a.z - b.z; return result;}Vector vector_direction(const Vector& a){ float l = vector_length(a); Vector dir; dir.x = a.x/l; dir.y = a.y/l; dir.z = a.z/l; return dir;}// results of a collisoin test between polygons.struct CollisionResult{ CollisionResult() : m_collision_found(false) , m_intersection_found(false) {} bool m_collision_found; float m_collision_time; Vector m_collision_normal; bool m_intersection_found; Vector m_intersection_direction; float m_intersection_depth;};// parameters used for polygon collision tests.struct CollisionParams{ CollisionParams(float max_time, const Vector& velocity) : m_collide_max_time(max_time) , m_collide_velocity(velocity) , m_enter_valid(false) , m_exit_valid(false) , m_intersect_valid(false) , m_intersection_failed(false) , m_collision_failed(false) {} // parameters for objects entering collision state. bool m_enter_valid; float m_enter_time; Vector m_enter_axis; // parameters for objects leaving collision state. bool m_exit_valid; float m_exit_time; Vector m_exit_axis; // parameters for objects intersecting. bool m_intersect_valid; float m_intersect_depth_squared; Vector m_intersect_axis; // objects intersect or collide? bool m_intersection_failed; bool m_collision_failed; // collision input parameters. const float m_collide_max_time; // maximum time allowed for detecting collisions. const Vector m_collide_velocity; // relative velocity of objects.}; void FindBoxInterval(const Vector& axis, const Vector& centre, const Vector& halfsize, float& min, float& max){ float p = vector_dot_product(axis, centre); float dx = fabs(axis.x) * halfsize.x; float dy = fabs(axis.y) * halfsize.y; float dz = fabs(axis.z) * halfsize.z; float dr = dx + dy + dz; min = p - dr; max = p + dr;}// find how far a polygon extends along a directionvoid FindPolygonInterval(const Vector& axis, const Vector* v, const int v_count, float& min, float& max){ float project = vector_dot_product(axis, v[0]); min = max = project; for(int i = 1; i < v_count; i ++) { float project = vector_dot_product(axis, v); if(project < min) min = project; else if(project > max) max = project; }}// check if two polygons can collide along a direction.void CollideIntervalsAlongAxis( const Vector& axis, float mina, float maxa, float minb, float maxb, CollisionParams& params){ // objects intersect along that axis? bool intersecting = (mina <= maxb && maxa >= minb); // if not intersecting on that axis, objects wont intersect at all. if(!intersecting) params.m_intersection_failed = true; //------------------------------------------------------------ // intersection test. //------------------------------------------------------------ if(!params.m_intersection_failed) { // yet, intersecting. Check if our intersection depth is smaller than // previously found. // calcualte the amount of intersection along that axis. float delta1 = (maxa - minb); float delta2 = (maxb - mina); float delta = (delta1 < delta2)? delta1 : delta2; float axis_length_squared = vector_dot_product(axis, axis); float intersection_length_squared = (delta * delta) / axis_length_squared; // this amount is less that our current intersection candidate. // that will be our new intersection candidate. if(!params.m_intersect_valid || (intersection_length_squared < params.m_intersect_depth_squared)) { // update SAT intersection params params.m_intersect_depth_squared = intersection_length_squared; params.m_intersect_valid = true; params.m_intersect_axis = (delta1 > delta2)? vector_opposite(axis) : axis; } } //------------------------------------------------------------ // collision test. //------------------------------------------------------------ if(!params.m_collision_failed) { // velocity projected on axis. float vel = vector_dot_product(axis, params.m_collide_velocity); // velocity perpendicular to axis (or no velocity at all). // objects will potentially collide only // if objects intersect along that axis. if(fabs(vel) < 0.0001f) { // but we are not intersecting along that axis // so we'll miss collisions. if(!intersecting) params.m_collision_failed = true; return; } // collision times when intervals are just touching float t0 = (maxa - minb) / vel; float t1 = (mina - maxb) / vel; // sort times for when intervals start intersecting // and when intervals stop intersecting. float t_enter; float t_exit; Vector n_enter; Vector n_exit; if(t0 < t1) { t_enter = t0; t_exit = t1; n_enter = axis; n_exit = vector_opposite(axis); } else { t_enter = t1; t_exit = t0; n_enter = vector_opposite(axis); n_exit = axis; } // the objects are too far away. if(t_enter > params.m_collide_max_time) { params.m_collision_failed = true; return; } // the objects are behind each other. if(t_exit < 0.0f) { params.m_collision_failed = true; return; } // time of collision greater than our entry time. update. if((!params.m_exit_valid) || (t_exit < params.m_exit_time)) { params.m_exit_valid = true; params.m_exit_time = t_exit; params.m_exit_axis = n_exit; } // time of collision greater than our last entry time. update. if((!params.m_enter_valid) || (t_enter > params.m_enter_time)) { params.m_enter_valid = true; params.m_enter_time = t_enter; params.m_enter_axis = n_enter; } // collision enter and exit time inconsistent. // It means objects missed each other. if( (params.m_enter_valid) && (params.m_exit_valid) && (params.m_enter_time > params.m_exit_time)) { params.m_collision_failed = true; } }}// check if two polygons can collide along a direction.bool CollidePolygonsBoxAlongAxis( const Vector& axis, const Vector* vertices, const int vertices_count, const Vector& box_centre, const Vector& box_halfsize, CollisionParams& params){ // axis is degenerate. ignore. float d2 = vector_dot_product(axis, axis); if(d2 < 0.00001f) return true; // find intervals of the two objects float mina, maxa; float minb, maxb; FindPolygonInterval(axis, vertices, vertices_count, mina, maxa); FindBoxInterval(axis, box_centre, box_halfsize, minb, maxb); // collide intervals. CollideIntervalsAlongAxis(axis, mina, maxa, minb, maxb, params); // no point continuing tests if we already know there is no overlap // and no collisions possible. if(params.m_intersection_failed && params.m_collision_failed) return false; return true;}bool CollidePolygonBox( const Vector& polygon_normal, const Vector* vertices, const int vertices_count, const Vector& polygon_velocity, const Vector& box_centre, const Vector& box_halfsize, const Vector& box_velocity, float max_time, CollisionResult& results){ // reset collision report. results.m_collision_found = false; results.m_intersection_found = false; // reset collision params. CollisionParams params(max_time, vector_subtract(box_velocity, polygon_velocity)); // test polygon normal if(!CollidePolygonsBoxAlongAxis(polygon_normal, vertices, vertices_count, box_centre, box_halfsize, params)) { return false; } // axes of the box (basically, axis aligned. static const Vector box_axes[3] = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } }; for(int i = 0; i < 3; i ++) { // test box axes if(!CollidePolygonsBoxAlongAxis(box_axes, vertices, vertices_count, box_centre, box_halfsize, params)) { return false; } // test cross product of box axes with polygon edges. for(int j = 0, k=(vertices_count-1); j < vertices_count; k=j, j ++) { Vector edge = vector_subtract(vertices[j], vertices[k]); Vector cross_axis = vector_cross_product(box_axes, edge); // test cross-axis if(!CollidePolygonsBoxAlongAxis(cross_axis, vertices, vertices_count, box_centre, box_halfsize, params)) { return false; } } } // intersection is valid. setup intersection data. if(!params.m_intersection_failed && params.m_intersect_valid) { results.m_intersection_found = true; results.m_intersection_depth = sqrt(params.m_intersect_depth_squared); results.m_intersection_direction = vector_direction(params.m_intersect_axis); } // collision is valid. setup collision data. if(!params.m_collision_failed && params.m_exit_valid && params.m_enter_valid) { results.m_collision_found = true; results.m_collision_normal = vector_direction(params.m_enter_axis); results.m_collision_time = params.m_enter_time; } // we found an intersection, or a collision (or both). return (results.m_collision_found || results.m_intersection_found);}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// END OF POLYGON / POLYGON COLLISION////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
