Jump to content
  • Advertisement
Sign in to follow this  

2d Collision Processing

This topic is 3336 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Once I know if the objects have collide/their bounding boxes overlap what would be a good way of separating them and/or determine other factors, like the strength of the impact, the momentum, the bounce etc. I am already using a physics engine, which might complicate things. This is a special case, which is the reason I am performing my own collision detection and processing. Details: The world is destructible, which means it's always changing. A collision happens when an object's pixels and the world's pixels overlap. I need to keep objects from going inside the world/terrain. C++, Direct3D and Box2D in case it's relevant. Thanks.

Share this post

Link to post
Share on other sites
Have you looked into seeing if theres a way to let box2d do the physics and querying that library for the information you are looking for?

Share this post

Link to post
Share on other sites
Yeah, I've tried to implement algorithms to automatically generate a physical body for the world, but it becomes quite slow with huge worlds. I think it would be a lot more complicated to implement all the necessary measures for it to become as fast as possible. And even then I don't think that it would be succesful, it would require a huge amount of shapes and it would still not be nowhere near as fast as my current solution is.

Share this post

Link to post
Share on other sites
oh ok, thought i'd mention it just in case :P

Have you heard of the seperating axis theorem (SAT)?

its one of the common ways modern physics engines find collisions and gather data for collision response.

Not sure if it helps, hopefully someone with more physics knowledge can step in and help you

Edit: btw you might also check out verlet physics. If you've played the flash game "line rider" or any of the commercial versions of that game, it uses verlet physics which can be a simple way of doing realistic physics.

Share this post

Link to post
Share on other sites
Separating axis theorem can't help me here since the world and some objects are concave.

I'll check out Chris Hecker's papers. Thanks.

Perhaps I should have posted this on the physics section.

Share this post

Link to post
Share on other sites
If it's 2-D and you have concave objects, then use

bool PointInPoly(tVector hitPos, const tPolygon *poly)
short first = 0, next = 0;
tVector pnt1, pnt2;
bool inside = false; //Initial test condition
bool flag1, flag2;

pnt1 = poly->vertex[0];
flag1 = ( hitPos.y >= pnt1.y ); //Is the first vertex over or under the line?

/* Loop through the vertices in a sector */
if(++next == poly->points) next = 0;
pnt2 = poly->vertex[next];
flag2 = ( hitPos.y >= pnt2.y ); // Is it over or under
if (flag1 != flag2) //Make sure the edge actually crosses the test x axis
//Clever trick to calculate whether the edge actually crosses the x test axis
if (((pnt2.y - hitPos.y)*(pnt1.x - pnt2.x) >= (pnt2.x - hitPos.x)*(pnt1.y - pnt2.y)) == flag2)
inside = !inside; // If it crosses toggle the inside flag (odd is in, even out)
flag1 = flag2;
pnt1 = pnt2; //Reset for next step
} while(next);
return inside;


// Will return true if two line segments p1p2 and p3p4 intersect. If so,
// intersection point will be in the memory pointed to by intersect
bool LineSegmentIntersect(const tVector *p1,
const tVector *p2,
const tVector *p3,
const tVector *p4,
tVector *intersect)
float dx1, dx2, dy1, dy2, mx, my, ua, ub, D;
dx1 = p2->x - p1->x;
dx2 = p4->x - p3->x;
dy1 = p2->y - p1->y;
dy2 = p4->y - p3->y;

D = dy2*dx1 - dx2*dy1;
if(D==0) return false;
D = 1.0f/D;

mx = p1->x - p3->x;
my = p1->y - p3->y;

ua = (dx2*my - dy2*mx)*D;
if(ua<0 || ua>1.0f) return false;

ub = (dx1*my - dy1*mx)*D;
if(ub<0 || ub>1.0f) return false;

//Intersection is within both line segments - i.e. line segments intersect
intersect->x = p1->x + ua*dx1;
intersect->y = p1->y + ua*dy1;
return true;

to do a point in polygon test and line segment intersection test. You then just have to test every point of each polygon with every point of the other polygon, and every line with every line of the other polygon, and vice versa (with an early break out if there's a collision of course) in order to find if two polygons are colliding. To find the point of the collision, use

//This will test how close a point P3 is to a line segment P1P2, assuming the minimum possible distance.
//The closest point on the line segment to P3 will be in *point
float PointLineSegmentDistance(const tVector *P1, const tVector *P2, const tVector *P3, tVector *point)
float u, dx, dy, den;

dx = P2->x - P1->x; //Work out differences
dy = P2->y - P1->y;

den = dx*dx + dy*dy; //Denominator is square of line segment length
if(den==0) return HUGE; //Line has no length!

u = ((P3->x-P1->x)*dx + (P3->y-P1->y)*dy)/den;

if(u<0 || u>1.0f) return HUGE; //The point is not 'near' the line segment

point->x = P1->x + u*dx; //Position of closest point on line
point->y = P1->y + u*dy;

dx = point->x - P3->x;
dy = point->y - P3->y;

//You can get the actual distance by returning sqrt(dx*dx + dy*dy)
return dx*dx + dy*dy;

to find which point in either polygon is nearest to which line (after reversing the integration using a binary search, or whatever). Then you can use Chris Hecker's physics articles to work out a realistic response (with rotation and linear momentum).

Share this post

Link to post
Share on other sites
Thanks a lot for the code.

So I'll still need to trace the borders of the world? In that case though I'll just stick with the physics engine since what makes it slow is having to trace the objects.

[Edited by - Antonym on October 27, 2009 12:38:56 PM]

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!