Sign in to follow this  
Berion

collision detection and contact calculation

Recommended Posts

I am researching und planning collision detection for my simple physics simulation, but I am confused and need help. Broad Phase: AABB, OBB, Spheres or something else? which algorithm should I chose? Where can I find good tutorials? (I found too many and don't know which I should use) Narrow Phase: How should I test triangle against triangle? separating axis theorem or something from http://www.realtimerendering.com/int/ I researched the last week and the more I found the more I got confused. For example "sort and sweep", "separating axis theorem", "sweep and prune", Recursive dimensional clustering" ...

Share this post


Link to post
Share on other sites
Broad Phase : Sort & Sweep (or Sweep & Prune, all the same I believe). Recursive Dimensional Clustering.... nah...

Tri-Tri / Box-Tri / Box-Box Intersection Detection : Separation Axis Theorem (or SAT).

if you plan on doing tri-tri, you'll need some kind of tree acceleration (OBB tree).

that should cover the basics.

Share this post


Link to post
Share on other sites
Hopefully, some part of your code will in some way determine that it needs to check a triangle against another triangle, and it will call a function to do so. Use any method you like in that function, get it working, and then consider alternatives when you have a working system to use for comparisons. The same is nearly as true of the spacial partitioning system - hopefully it will be only visible through a small and simple API and you can swap it for another one later if you want to. Go with whatever seems simplest to you. Make it work. Then worry about it.

Chances are you will make such a mess of your first ever physics engine that when it comes time to write a game that uses it, you will start again anyway, and do it better ;)

Share this post


Link to post
Share on other sites
thanks for your help

I have another problem:

I have solved AABB swept collision test to the point where I have the time of the first(t0) and the last(t1) contact of the the two AABBs

now I want to test the triangle mesh of object a against the triangle mesh of object B between t0 and t1 ( a tri - tri swept test?)

then calculate the time of the first real contact

reupdate the stats (position, velocity at the time of the first real contact)

apply impulses to the objects


is this a good way to handle collision detection?
how should I test the triangles?

Share this post


Link to post
Share on other sites
Quote:
how should I test the triangles?
Quoting oliii:
Quote:
Tri-Tri...Separation Axis Theorem (or SAT).

if you plan on doing tri-tri, you'll need some kind of tree acceleration (OBB tree).
However, if this is your first collision detection system and/or physics engine, you might consider skipping arbitrary mesh collision and instead using a simpler convex bounding volume. Just a thought...

Share this post


Link to post
Share on other sites
triangle-triangle is expensive. Like very expensive. Doing a swept test is even more expensive :)

For intersection tests, I'd use the good old separation algorithm. TO build the hierarchy to speed up the process, I'd make either an binary AABB tree, or a binary OBB tree.

For OBB trees and triangle intersections, and intersecting two meshes, the RAPID collision detection library does it all. However, it's quite lazy, in the sense that it does not return any contact information.

That in itself, is another huge problem.

If you can, approximate your meshes with simple convex objects, like boxes and spheres, simpler, and cleaner contacts, however, not as precise.

If you want a fairly good approximation of the two meshes, and in an automated way, I'd try an octree of spheres. That's simple, fast. Better systems are adaptive sphere trees, but the adaptive part is complicated.

Share this post


Link to post
Share on other sites
Colliding triangles are relatively easy and fast.
So , Have you ever see Coldet package? It has the cleanest and cheaper algorithm for colliding triangle meshes.
Please visit http://photoneffect.com/coldet/

But the real problem comes when you need to deal with physics, and there is need to find contact points and normals.
Coldet do something of this stuff, but it isn't enough. At this point, coldet gives the intersection point of two triangles. That's good, but , what about if you'll need to find penetrations? for separate colliding objects?

In my experience, find contact points for a physics simulation is not enough, because objects pass throught each other when there isn't information about how much it should separate these objects.

Is there any colliding package for find interpenetration and contact information?

Share this post


Link to post
Share on other sites
okay I have solved the tri-tri swept test and now have the pairs of colliding tris and the time of collision

Next i want to calculate the contact points and normals, but I cant find good papers about it.

can somebody please posts links to some good papers or a tutorial

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this