collision detection and contact calculation
Author
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" ...
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.
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.
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 ;)
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 ;)
Author
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?
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?
Quote:how should I test the triangles?Quoting oliii:
Quote:Tri-Tri...Separation Axis Theorem (or SAT).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...
if you plan on doing tri-tri, you'll need some kind of tree acceleration (OBB tree).
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.
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.
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?
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?
Author
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
