# collision detection and contact calculation

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

## 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 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 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 on other sites

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

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 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

1. 1
Rutin
37
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 12
• 14
• 9
• ### Forum Statistics

• Total Topics
633351
• Total Posts
3011476
• ### Who's Online (See full list)

There are no registered users currently online

×