# Intersection points?

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

## Recommended Posts

Hi, I try to make a physics system like the one Thomas Jakobsen discribes in his article (and the used in Hitman: codename 47). I have a part of the system working, but now I need collision respons. And to do that I need a collision detection system wich detects if two objects collide and if they collide where the points of collision (intersection points) on both the objects are. I can detect the collision using the method of seperation axis, but I don't know how to get the points of intersection on both the objects. Can someone explain me how to find the points of intersection on both the obects? Thanks.

##### Share on other sites
I'll just point you to this for 3D, or this for 2D

##### Share on other sites
I already downloaded his code (and doc), but I don't realy understand how he finds the intersection points. Can someone maybe explain it to me?

Thanks

##### Share on other sites
well, I wrote the code. What don't you understand? 2D or 3D? I can always clear it up in the docs.

##### Share on other sites
I have the collision detection working (without intersection points), but I haven't followed you docs so my code is defferent from yours. When I look at your intersection point doc (code) I can;t realy follow what you're doing. Can you globaly discribe to me, how you calculate the intersection points?

Thanks.

##### Share on other sites
Ok i'll try to explain two methods:

1. using time sub-division - binary-search of collision time. Sub-divide time and integrate until you find that there are no inter-penetrations, only collisions. For a better explanation look at Chris Hecker's physics tutorials.

2. project objects outside of each other. With oliii's code, you can determine the MTD (minimum translation distance) which will separate the two polygons. Find which point is penetrating and translate the objects accordingly, and this point will become the collision point.

##### Share on other sites
you still haven;t specified if it is 2D or 3D. It's quite different for both cases (when going into details anyway). but here are the steps for 3D...

1) find the plane of collision using the Separation axis (either, the MTD vector in case of intersection, of the time when the two polygon touch, which will give you a plane normal and time of collision).

2) Using that normal of collision, find the two sets of features supporting the objects along that normal. Imagine a dice resting on a table. The normal of collision will be pointing upwards, and the two sets would be the top quad for the table, and the face at the bottom of the dice.

for any convex polyhedron object in collision, the supporting features along an arbitrary direction are either.
a - a face
b - an edge
c - a vertex

3) using the two colliding features, find the points of intersection, which will be the points that will be the closest to each supporting features.

for example,

- a vertex hitting a face gives the vertex itself, and the projection of the vertex on the face.
- an edge edge contact will give the two points on the edges the closest to each other.
- a face against a face will give the clipped region shared by both faces.
- an edge versus a face will give the portion of the edge clipped by the face, and the projection of that segment on the face.

these are the principle intersection events you can get.

so now you have pairs of points (that you can reduce to only on set of points, if the collision is not in intersection), and the normal of collision, you should be able to apply collision impulses, and in the case of an intersection, separate the objects appropriately.

##### Share on other sites
Kee Yip Chan
Bouncer

Both came up with alternate solutions to the one presented in the paper. Check them out if you're having trouble with the interestion points.

[Edited by - skittleo on September 10, 2005 11:49:37 PM]

##### Share on other sites
I'm working in 2d (I forgot to mention it).:-D

##### Share on other sites
ok. then the process is the same, but simpler

2) Using that normal of collision, find the two sets of features supporting the objects along that normal. Imagine a rectangular box resting on a table. The normal of collision will be pointing upwards, and the two sets would be the top edge for the table, and the edge at the bottom of the box.

for any convex polygon object in collision, the feature supporting the objects is either
a- a vertex
b- an edge

to find those supports (edge or vertex), it's not very dificult. YOu just need to find the vertices that, when projected along the normal, gives the minimum value.

3) using the two colliding features, find the points of intersection, which will be the points that will be the closest to each supporting features.

for example,

- a vertex hitting an edge gives the vertex itself, and the projection of the vertex on the edge.
- an edge against an edge will give the clipped region shared by both edges.

these are the principle intersection events you can get. Vertex-vertex should not happen, but the contact points are easy enough.

For an edge versus an edge, it means that the edges are parallel. What you want is the bit in the middle, shared by both edges.

to get is, imagine these situations

   |     |A        |                |B   |     +---------|----------------+   +-----|---------+                |   |C    |         |D               |         |A   |               |     |B         +----|---------------|-----+         |    +---------------+         |    |C              |D         |A                    |    |B         |         +--------------------------+          |         |                     +----|----------+         |                     |C   |          |D

example 1, the contact surface shared by the two segments is the area defined by points A and D. Pairs of points of contact will be [A, A'] , [D', D], where A' is the projection of A on the infinite line (CD), and D' is the projection of A on the infinite line (AB).

similarly, for example 2, the contact patches is the bit in the middle, [C', C], [D', D].

for example 3, it's [C', C] and [B, B'].

now, to get those, if you sort the points along the edge direction (simply dot product the edge direction and the vertex, and compare the results), then you ned to take the points number 2 and 3 in the sorting order.

Another solution is to take each segment, and take the points
Max(Seg0.Min, Seg1.Min)
Min(Seg0.Max, Seg1.Max)
and their respective projection as the points of contact.

again, you need to compare the projection of the points along that edge direction.