Jump to content
  • Advertisement
Sign in to follow this  

Calculating contact points

This topic is 5194 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

Hi. I'm having troubles calculating contact points in 2d. I have been searching the internet and this forum (..when is that search function gonna be fixed?) for some information about this but most of the time i find only information about what to do after the contact points have been found. My problem is how do i find those contact points in the first place ? Are there some papers about this ? ps:sorry for my bad English

Share this post

Link to post
Share on other sites
1. use Google, search "site:gamedev.net contact points"

2. here's your answer: http://uk.geocities.com/olivier_rebellion/
actually this is your answer http://uk.geocities.com/olivier_rebellion/box.zip
this file also contains doc's + source for contact points: http://uk.geocities.com/olivier_rebellion/Polycolly.zip (I like this file the most, cause it contains a lot of useful information about collision detection)

[Edited by - nife on July 29, 2005 8:33:46 AM]

Share this post

Link to post
Share on other sites
Yes i found Olli's documents, but i dont understand his procedure
completly. When i try to apply this in my own sources i get very
weird results. My rigid bodies spin into the wrong direction and
collision detection isn't detected very accuratly.
So i think there's someting wrong in my conctact points calculation.

But anyway i tried to take a look at Olli's sources and tried to understand

I made a picture to explain the things i've tried.

When there is an intersection between to objects A and B, Olli
projects all vertices on the collision normal. The lowest
projects point on this normal is a contact point(1) of object A.
To find the contact point on the other object B, you have to find the point on object B
the closest to the contact point on A.(2)

Ok when i get this far i have one pair of contacts (1) (2)

So now my question is what did i do everything correct so far ?
and what i is the next step ?

Share this post

Link to post
Share on other sites
OK, I'd better step in...

YOu have the collision normal.

You find the points on A that projects the lowest along that vector (point (1)).

You find the points on B that projects the *HIGHEST* along that vector (the two vertices at the top of ).

so, you end up with one point on [A], and two points on .

These are called the support points.

Now, you need to find the contact points from that.

in 2D, the case study down there is a vertex vs an edge (one support vertex on [A], two support vertices on ).

to solve that case, you have to find on the supporting edge, the point closest to (1).

that will give you point (2).

these two contact opints, on both objects, plus the normal, and the distance between the contact points, is what you need to go to the next step, that is the collision response. The minimal data you need from an intersection, for collision response, is actually just the two contact points. YOu can extract the collision normal and depth from those contact points.

that data, forms a collision packet, from which an impulse is calculated, that will make the objects bounce on each other.

As for the collision contact calculation, there are basically two cases in 2D.

1) a vertex / edge collision (like above).
2) an edge / edge collision, when the two objects are supported by an edge (two boxes resting on each other, for example).

for case 2) it's a little bit more complicated. YOu need to find the shared portion between the two edges. That forms a contact surface area.

That surface area, in 2D and during an intersection, looks like two segment portion on both objects. To find that portion, from the 4 support points (remember, 2 on each objects), you need to find the two points which are 'in between'. One way to do it, is to project the points along a vector perpendicular to the collision normal, and sort them by projection value. From that, there are several configurations. Let's call A0, A1, the supoprt points on A, and B0 B1 the support points on B.

you project those points along the axis V(-Normal.y, Normal.x). Simple DOT product.

Then you sort those point (ascending or descending, won;t matter).

you may end up with the list [A0, B0, A1, B0], or [A0, B0, B1, A1], or [B0, A1, B1, A0], ... it doesn't matter. The two points in the middle are the points part of the collision surface area.

From that, you need to find the pairing opint on the opposing object, by simply finding te closest point on the supporting segment.

for example, you have the pair[A1, B0] as the surface area. then you need to pair it with [B3, A3], such as

B3 = ClosestPointOnSegment(A1, Segment(B0, B1));
A3 = ClosestPointOnSegment(B0, Segment(A0, A1));

then the pair of point [A1, B3] forms a first contact. [B0, A3] forms the second contact.

in 3D, the proces is the same. YOu find the supporting feature (vertex, edge, or convex face) between the two objects that collide / intersect. then you have several cases.

1) vertex - face.
2) edge - face.
3) edge - edge.

other combination (vertex-vertex, vertex-edge) should not be available, if you use the SAT algorithm to find the collision normal, but you can handle these cases if you want to.

Right, so in 3D, for example, in case of an edge-face suport case, you 'clip' the edge against the face (an extrusion of it, to be more accurate). In case of a face-face, yuo clip one face gainst teh other. Those will return the surface area shared by the two faces.

In 2D, the same can be applied. YOu could 'clip' one of the support edge against the extrusion of the other edge, that will give you the two pair of contact points needed.

Share this post

Link to post
Share on other sites
Ok Oli thanks for your answer (i have to reread that i few times though)

Share this post

Link to post
Share on other sites
pictures would help. I will edit the post and put some pics later on.

It really isn't hard, and the maths aren't too complicated. just difficult to explain without visual feedback.

Share this post

Link to post
Share on other sites
Ok i tried to make some pictures myself it make's Oli's reply
more clear.

case vertex - edge collision: dealt with it in first posts

case edge - edge collision:

You have 2 objects A and B which are colliding,
how do i find the contact points of both objects.

1)Project alle vertices of object A and B on the collision normal.
2)The support contacts for A are the projected vertices with the lowest value, for object B the highest value.
3)You find for object A support vertices with nr 2 and 6 for object B support vertices with nr 1 and 5
4)Project al support vertices of object A and B on a line perpendicular to the collision normal (-normal.y,normal.x)
5)Sort all projected points descending or ascending (doesn't matter)
6)Take the 2 points in middle -> you find vertices with nr 1 and 2
7)Project each vertex on the the supporting edge of the pairing object:
->project vertex 1 on edge 2 - 6
->project vertex 2 on edge 5 - 1
8)You find vertex 3 and 4, so now you have two pairs of contact points [1,4] and [2,3]

If i forgot something please correct me

Haven't started to think about this in 3D yet..

edit: spelling

[Edited by - meo on August 1, 2005 4:20:38 PM]

Share this post

Link to post
Share on other sites
nope that's pretty much it.

3D, as I said, is more to do with 3D polygon clipping. An identical clipping algo can be applied in 2D as well.

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!