Sign in to follow this  
ak-73

Collision Handling

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
hey!


////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
//
//
// 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 direction
float 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[i]);

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[i], 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[i], 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[i]);

if( project > support)
{
vertex = v[i];
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[i] = 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[i] = 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[i].x, v[i].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[i] += (Vector2(x, y) - a0);
}

if(drag == &b0)
{
for(int i = 0; i < b_count; i++)
b[i] += (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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 direction
void 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[i]);

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[i], 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[i], 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
//
//
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////


Share this post


Link to post
Share on other sites
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 direction
void 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[i]);

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[i],
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[i], 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
//
//
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////



Share this post


Link to post
Share on other sites
Quote:
Original post by oliii


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.


Follow-up question:
Möller/Haines claims their interval overlap method is faster than SAT for detecting tri-tri intersections. Can anyone confirm that? (Because SAT seems to be much better documented than their method.)

Alex

Share this post


Link to post
Share on other sites
Could be, but the SAT is simple and already very efficient. I doubt it's a lot faster than the SAT, when fully optimised for triangle / triangle. I'd just run with it.

It also depends what sort of information you are able to extract from it. The SAT can return you the MTD vector.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
Could be, but the SAT is simple and already very efficient. I doubt it's a lot faster than the SAT, when fully optimised for triangle / triangle. I'd just run with it.


Their method involves calculating the line of intersection between the planes of both triangles and then projecting the tris onto that axis only.

Quote:

It also depends what sort of information you are able to extract from it. The SAT can return you the MTD vector.


I have been looking at the PolygonPolygon code and some questions remain:
1. The time of collision is calculated by measuring the deepest penetration of any axises, is that correct? Is that an *approximation* of collision time?
2. The normal of the collision is also derived from that? The axis of deepest penetration?
3. Why does t_exit < 0 mean objects behind each other? I'm not sure I get this quite right.

Thanks,
Alex

Share this post


Link to post
Share on other sites
Quote:

1. The time of collision is calculated by measuring the deepest penetration of any axises, is that correct? Is that an *approximation* of collision time?


Not really. I consider intersections, and collisions forward in time. Both are unrelated (in a way). But knowing if an intersection happens and what way the intersection is can be useful in itself.

Quote:

2. The normal of the collision is also derived from that? The axis of deepest penetration?


It depends what sort of normal of collision you want. Usually, if there is an intersection, I use the intersection info as my normal of collision.

if there is no intersection, I use the collision info as my collision parameters.

However, in case of an intersection and a collision both registered, the time of collision will be negative, and the collision normal could be used instead of the intersection direction.

In case of an intersection, what is useful is the mtd, or minimum translation distance. The mtd vector is along the axis of least intersection. You can use that as a normal of collision in the case of the two object actually intersecting.

The second part of the algo computes the collision time. t_enter and t_exit represent the time the objects just begin to collide, then there is a phase where the two objects are intersecting when moving along the sweep direction, and then finally, a time where the objects finish intersecting along the sweep direction.

Basically, with the mtd vector, and the collision times (as well as the normal of the surfaces when both objects begin colliding) is pretty much all the info you can get out of the SAT for collision response.


Quote:

3. Why does t_exit < 0 mean objects behind each other? I'm not sure I get this quite right.


this picture probably worth a 1000 words


/*

missed intersection.
--------------------
intervals [tymin, tymax] and [txmin, txmax] do not overlap (here, txmin > tymax)


| |
| |
*P0 | |
\ | |
\tymin | |
--------*-----+-----+-----------------
\ | |
\ | |
-----------*--+-----+-----------------
tymax \ | |
\| |
*txmin|
|\ |
| \ |
| \ |
| \ |
| \|
| *txmax
| |\
| | \
| | *P1


we have intersection.
----------------------
intervals [tymin, tymax] and [txmin, txmax] overlap (tymin < txmax and tymax > txmin)

*P0 | |
\ | |
\ | |
\|txmin |
* |
|\ tymin
--------------+-*----+-----------------
| \ |
| \ tymax
--------------+----*-+-----------------
| \|
| *txmax
| |\
| | \
| | *P1
| |

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this