2d Collision Processing
Author
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.
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?
Author
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.
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.
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.
Look for Chris Hecker's articles on physics-based collision response. They're well-written and could be a great help.
Author
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.
I'll check out Chris Hecker's papers. Thanks.
Perhaps I should have posted this on the physics section.
If it's 2-D and you have concave objects, then use
and
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
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).
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 */ do { 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;}and
// Will return true if two line segments p1p2 and p3p4 intersect. If so,// intersection point will be in the memory pointed to by intersectbool 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 *pointfloat 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).
Author
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
