🔒 Locked

Rectangle collision detection.

Started by Abob Apr 26, 2003 at 7:08 PM 3 replies 1.7k views

Original Post

Apr 26, 2003 at 7:08 PM

I need a way to figure out if two rects are moving toward each other. I need this for my collision detection code to prevent objects from colliding mutable times (if in frame x two objects are overlapping the program calls the collision code to modify the objects velocity. If the time step of the next frame is less, or the velocity’s are less, the two objects might still be overlapping the next frame and “Collide” again.) So In the collision test I need to test that the objects overlap, and that they are moving toward each other. I know how to do this with circles, but I do not know how to do it with rectangles. I suspect that a simple test might not be possible with rects. If this is the case, dose any body know any other way I could make rectangle collision detection work? Thanks for any help.

Vich

Apr 29, 2003 at 7:45 AM

Do this:
- find both rectangle''s plane normals
- find the intersection line from both (infinite) planes
- if this intersection line is inside BOTH of the planes, then they have collided. you can check this by performing a ray-triangle collision after converting each rectangle to two triangles.

Greetz,
Vich

oliii

271

oliii

Apr 29, 2003 at 3:14 PM

your best bet would be to find the collision normal of the two rectangles, and check the dot product of the relative velocity time the plane normal.

Rect1(P1, V1)
Rect2(P2, V2)

if you found that Rect1 intersects Rect2, and the collision plane is (P, N), where N points from Rect1 towards Rect2,

if ((V1 - V2) * N > 0.0f)) return NoCollision;

Not sure about the sign of the equation, but if you inverse it, you''ll see straight away which one you should use. It''s either ''>'' or ''<''. you may need to watch out for values close to 0.0f. You might find the objects penetrating slowly. You need to handle a special case where the dot product of the relative velocity * N is very close to 0.0f (say between 0.0f, 0.0001f for example). In this case, push the position of the objects slightly apart, using the normal direction.

This simple test applies to any convex shape detection, like spheres, boxes, cylinders, triangles, ect...

To improve the algorithm, you can use some simple rigid body dynamics. This does not ''inverse'' the velocities, but add energy (forces) to seperate the objects, so you don''t get that sticking/penetration problem, the objects will naturally pull away from each other, even at low velocity. The only problem, if you do not use dynamic constraints, you''ll see the object jittering a bit, but it''s usually acceptable.

Abob

Author

Abob

Apr 30, 2003 at 8:33 PM

quote:
Original post by Vich
Do this:
- find both rectangle''s plane normals
- find the intersection line from both (infinite) planes
- if this intersection line is inside BOTH of the planes, then they have collided. you can check this by performing a ray-triangle collision after converting each rectangle to two triangles.

Greetz,
Vich

I do not understand, could you explain in more detail?

quote:
Original post by oliii
your best bet would be to find the collision normal of the two rectangles, and check the dot product of the relative velocity time the plane normal.

Therein lies my problem, how do I find the collision normal for two rects?

Vich

May 1, 2003 at 12:41 PM

ok, when two triangles hit eachother, they form a line that is made by the intersection of those triangles. To find this line - if there is one - we will see if the planes where the triangles are on have an intersection line. Those planes always have an intersection line unless the triangles are placed parallel to eachother.
So if you have found the intersection line of those planes, you will have to see if that line is part of the first triangle AND the second triangle. If so, than our triangles have an intersection, so we collided.

Here's a function to find the normal of a triangle (you should form a triangle with 3 points of the rectangle

)

    
// vector cross product

CVector3 Cross(const CVector3 Vector1, const CVector3 Vector2)
{
	CVector3 Normal;	
	Normal.x = ((Vector1.y * Vector2.z) - (Vector1.z * Vector2.y));
	Normal.y = ((Vector1.z * Vector2.x) - (Vector1.x * Vector2.z));
	Normal.z = ((Vector1.x * Vector2.y) - (Vector1.y * Vector2.x));
	return Normal;										 
}

// normal calculations for a triangle

CVector3 Normal(CVector3 Polygon[])			
{
	CVector3 Vector1 = Polygon[2] - Polygon[0];
	CVector3 Vector2 = Polygon[1] - Polygon[0];
	CVector3 Normal = Cross(Vector1, Vector2);
	Normal = Normalize(Normal);
	return Normal;
}

[edited by - Vich on May 1, 2003 1:44:08 PM]

[edited by - Vich on May 1, 2003 1:44:27 PM]

Topic Locked

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