Hi, I''m working on a physic engine wich is supposed to simulate Rigid Body Dynamics. It''s the first time I''m working on something related to collision and now I''m really in need of help. The engine already loads 3D objects from files and builds Octree based Sphere-Trees for each object to speed up collision detecion, and finding the area of a possible collision is no trouble. The real problem is how to calculate the exact point where contact did happen. I did some readings about it in some papers, but wasn''t able to extract any practical information out of them. The only thing I became to know is that it is unlike to have a "Point" of contact, but a "Penetration Region". All the scientific explanations about Contact Determination are so complex that I''m frustrated by now. I''m completly lost and don''t know wich direction to go. I would really appreciate any information from more experienced people who could give me some directions of where to go, what to do, or even better, how to do it. Thanks

Gee, man, I'm working on the exact same problem (and engine). Although I've already got to the point where I determine if spheres collide and octree sub-children, I haven't got to the part (yet) where I find out which of triangles in the bottom nodes collide.
If you want, we can try to do it together, although its not hard for me to determine collision triangles and the collision point.
Thanks.

Are you having a problem finding where two triangles intersect? (at which exact point?)

I got an idea for you.
Wanna hear it?
Reply here again

" Do we need us? "

Ionware Productions - Games and Game Tools Development

[edited by - HellRiZZer on October 7, 2003 8:22:29 PM]

Cool! Nice to see someone else working on the same kind of engine.

Yes, actually I am having trouble finding the exact point where two triangles intersect. I imagine wich kind of "point" will this be, since triangle collision is a surface overlaping problem, and when two surfaces overlap there is more than one single dot wich can represent a collision point. There will more likely be a "line" of intersection, right?

Anyway, how do I get that intersection point (line)?

jesus christ on a bike,

You guys want to do per-triangle collisions? That's a bit excessive

anyhow, a list of collision detection and physics links, out of my favorites. They are sort of ordered. the first link is the one you are directly interested in.

http://www.realtimerendering.com/int/
http://www.cs.unc.edu/~ehmann/RigidTutorial/
http://www.ams.sunysb.edu/~jklosow/quickcd/QCD_resources.html
http://www.realtimerendering.com/#colldet
http://www-rocq.inria.fr/~redon/research.htm
http://www.magic-software.com
http://opende.sourceforge.net/
http://www.tokamakphysics.com/
http://www.gamasutra.com/resource_guide/20030121/kennedy_01.shtml
http://www.gamasutra.com/resource_guide/20030121/jacobson_01.shtml
http://www-2.cs.cmu.edu/People/rapidproto/mechanisms/chpt4.html

http://www-2.cs.cmu.edu/~baraff/
http://citeseer.nj.nec.com/cs?q=david+baraff&cs=1

basically, anything by david baraff
citeseer, is the definitive resource for academic papers. it's got them all.
Also David Eberly will publish a book soon, about game physics. See the magic software site.

[edited by - oliii on October 8, 2003 5:00:03 AM]

Well, I just thought of an idea of determining tri/tri intersection point/line:
You got 3 points for triangle, right?
So, why don''t you test ray/triangle intersection by taking pairs of one triangle vertices?

E.g Triangle1 consists of A1, B1, C1;
Triangle2 is A2, B2, and C2;
So, what you do is you test ray/triangle intersection point for lines A1-B1, A1-C1, B1-C1. Of course, of two triangles DO collide, you need only test 1 triangle rays against the other.
Although I''m not sure that ray/tri gives a point of collision, but what else they would need it for in raytracing?
Anyway, that'' just an idea.

Good luck.

" Do we need us? "

Ionware Productions - Games and Game Tools Development

You may want to do that test once a less costly reject test has failed (i.e. a separation axis test that returns that the triangles have intersected).

Come to think of it, here is an algorithm.

Compute the intersection point of each intersecting segment (the ones that span across the plane) with the opposite plane. This should give you two unique points (or a segment) per triangle.

then sort the two segements for the two triangle along the axis (triangle1.normal x triangle2.normal). If the two segment-span overlap, then the triangles intersected, and the two points of intersection are the span overlap. It would be better if I did a little drawing.

  triangle 1------------                      .                  / \         P0 /   \ P1     ______/_____\________plane of triangle 2          /       \         /         \        ''-----------''   triangle 2-----------              .                        / \         \   /   \         \ /     \      Q0  \       \         / \       \        ''---\-------''              \Q1              \               \                \ plane of triangle 1project [P0, P1] and [Q0, Q1] on line (Tri1.Normal.Cross(Tri2.Normal))----------------------------------------------------------------------    Q0     P1  Q1            P0____|______|___|____________|__________ Axis = T1.N x T2.N     ----------           -----------------[Q0, Q1] and [P0, P1] overlap, so the triangle intersect at [P1, Q1]. 

Just something I came up with, but I''m sure someone already used that algorithm somewhere. Although I''m not sure is computing the intersection of two triangle is actually of any use in terms of collision response.

Another algorithm that I did use, is based on the separation axis theorem.

You compute the separation planes as usual, and the projections of each triangles on the separation axis, also as usual. Save all of them into a list. If all separation axes fail, you have a collision. Now, search through all the separation axes and their associated triangle spans, and select the one with the minimum overlap (you need to normalise the axes directions first). This "minimum overlap" axis will tell you what features really collided (point-plane of edge-edge), from the "minimum overlap" axis index and what features were used to build them (cross product of edges, or one of the triangle normal).

I use the same principle on OBB-OBB collisions, and it gives me good results.

HellRiZZer: Very interesting approach I think I''ll give it a try.

oliii: Thanks for these links, they are very usefull :D

I''ve got a few questions Mr Freeze. I''ll be quick, gottagotowork.

Can you always ensure that your objects are always disjoint?

If you find your objects intersect, what do you do? Do you do a binary search between the time they were disjointand the time they intersected, until the distance is below a threshold?

Why do you need the intersection segment if you only need to know if the objects intersect or not?