Archived

This topic is now archived and is closed to further replies.

EEPROM

Contact Determination of 3D Objects

Recommended Posts

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

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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)?

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 1


project [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.

Share this post


Link to post
Share on other sites
I also worked on the same problem and solved it in the following simple way:

I never let my objects collide, whatever happens.
If your objects don''t collide, it is very easy to find the smallest distance separating 2 object pairs. That distance is either vertex-surface, either edge-edge.
Given a threshold e, I check if the distance separating two objects is smaller than e. If yes, I take the middle of the smallest distance segment as the collision point. The nice thing if your do like this is that you can easily find all collision points between two objects. Just take all features which are closer than e.
With these collision points you can then compute the collision response.

Oliii: I compute the intersection between two objects like you described. However I don''t use this for collision response. Like you said, I don''t think it can be very useful for collision response.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
quote:
Original post by oliii
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?


By applying proper collision response, you can ensure that all objects are always disjoint. Should some objects intersect you have to rewind to the previous state and choose a smaller time step.
Another nice thing by doing so is that you are not limited to convex or closed objects for collision response (since no penetration depth has to be calculated). However multiple distance calculation between non-convex objects is not extremely fast...

I need the intersection segment for functionalities not related to collision response (visualization, section extraction)

Share this post


Link to post
Share on other sites