Sign in to follow this  

Perfect Collision Detection

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Thanks in advance. I have gotten my collision detection down to perfect testing. It is accurate but slow. I test triangle by triangle. First, I have a function that tests if a line segment is touching a plane. Then I test if the point of collision is inside the polygon with the 360 degree angles test, then for testing a triangle, I use the edges as lines in order test like the above. It works perfectly, but slowly. I checked the articles on this site and none of them really get what I want. The above works, but when I apply it to whole models with 600 and 700 polygons, it is way too slow, like five seconds just to check two models. In a game, I would check with a quick sphere test to see if the models are even near each other, but I don't want to take five seconds to test when they are near. Does anyone have any links to a faster method. I have looked at boxes and spheres, but I would lose the accuracy. I know perfect collision detection is possible at real time speeds because Freespace 2 uses it, but I don't know assembly in order to see the method that it uses. I want the accuracy and the speed. Are there any articles or tuts online with this type of collision. Please help.

Share this post


Link to post
Share on other sites
The first thing I ask is whether you need perfect collision detection. Why do you need to test a 600-700 triangle mesh against another 600-700 triangle mesh? Why does your situation preclude the use of proxy geometry that may be 10 times fewer triangles?

So, if you have a good reason to do triangle/triangle collision detection between meshes with lots of triangles, you can do some things to speed up processing.

First, make sure that you do test for collision of simple bounding volumes before you perform a triangle/triangle test between the meshes.

Second, expanding on the first, create a bounding volume tree, such as an OBB tree. Each leaf of the tree refers to a subset of the triangles of the mesh. Before going triangle/triangle, do collision amongst the leaf nodes of the tree, then only do triangle/triangle for triangles contained in colliding leaves of the OBB trees. This is a quite common approach. (Note for characters you could have one OBB per limb of the character, or a separate OBB tree for each limb if the limbs have large #'s of triangles.)

Third, you can exploit temporal coherence, considering only triangles that previously were close enough together to possibly collide. The OBB tree can help, e.g., keep track of the temporal coherence of the OBB tree leaves instead of individual triangles.

Fourth, once you narrow the problem down to a minimal subset of triangles to test, partition your triangles so that you do not test every possible pair. For example, sort triangles in X, and then do a plane sweep, only testing triangles whose projected X extents overlap. You can really sort in each axis in sequence, X, Y, Z, at each step eliminating triangle tests for triangles that don't overlap in the current axis. That plane sweep process exploits the spatial coherence of the model.

I guess my main point is that even if you don't want to use proxy geometry or bounding volumes to obtain your final result, you are going to have to exploit them to perform your triangle/triangle test in a smart way, to make it fast.

Share this post


Link to post
Share on other sites
Of course Graham basically covered it, but I'd also like to add that there are faster and more robust tri/tri tests than the one you're using. So if in fact you really do need to test tris against tris, I would do some research in that area.

Christer Ericson's new book on collision detection has some good information on the subject (as well as all the stuff Graham mentioned). In any case, I wouldn't recommend the '360 degrees' method for segment/tri intersection (one good alternative is tetrahedral volumes).

Share this post


Link to post
Share on other sites
To complete the previous posts, with a more general pov, as usual :

Complexity = k * func(m, n)

1) optimization : algorithmic improvement (Graham suggested).
To reduce the m*n (rectangle) complexity of the naive algo, obviously any space partition (SP) will help to get a nearly constant (k) processing time. In theory binary (or equivalent) partitions (octree, sphere tree, bsp, etc...) will give you : k*nContacts*(log2(m)+log2(n)). In practice regular 3D grids might be enough. Graham also mentionned caching frame to frame (space time coherency), still in most algos, it's usually efficient for conservative quick rejections, not first contact determination, and this works best when convexity comes into play at one level or another.

2) optimization : code implementation.
The tri/tri primitive routines have been studied extensively. One could mention potential SIMD speed ups at the lowest level. Anyway if your SP is wise, you only need a few calls to this primitive per output, that is per contact. So 1) is definitely the most important. Also think that you can fnd algorithm that avoid redundant tests on the shared vertices and edges by considering the meshes globally or convex sub meshes.

So Google again. Start to use the pointers you found here. Then you should end-up with 1,000,000 times more speedy mesh/mesh routines. 5 seconds is simply horrible ;)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
My tri/tri system works roughly as following.

1. Calculate bounding volumes (BV) for all objects.
2. If two BVs intersect, calculate the intersecting BV.
3. Test all triangles for both objects against that BV.
4. If triangles exist from both objects add those triangles to a checklist.
5. Run all triangles trough an octree and detect potential intersections.
6. Determinate the intersections.

It can easily be extended to use temporal coherence.

There are alot of tri-tri-intersection code availible on the net. My tests indicates that there are cases where all of the fast ones fail!

/__fold

Share this post


Link to post
Share on other sites
1. Calculate bounding volumes (BV) for all objects.
Not real time thus fine. Well if you do it in local coords of course.

2. If two BVs intersect, calculate the intersecting BV.
A (world )space partition will immensely speed up your step 2). Are you using an octree here ? Or swept spheres for dyn objects.

3. Test all triangles for both objects against that BV.
It's a pseudo optimisation (quick rejection) in some worst cases. For instance highly complicated objects embracing.

As pointed in another recent thread. Splitting meshes into convex parts can also speed-up a lot. This applies from here to 5. Most real life meshes can often be split into a few convex parts.

4. If triangles exist from both objects add those triangles to a checklist
So you may well have nearly every triangle (both objects) in that list cf worst case in for 3.

5. Run all triangles trough an octree and detect potential intersections.
I suspect this will be very slow, specially if your octree implementation (for instance no pool allocator) is poor. Transfos into a common 'world space', creating AABoxes, inserting into the octree. This looks like a real pain to me, and specially of an untamed complexity in some cases surely. A good algo should not have potential peaks in perf drops.

If you want something generic use two sphere trees. It's efficient and very easy to understand. Spheres are very practical for many reasons. Their invariance in rotations being the most obvious one. If your tesselations are not too weird (no long sharp triangles), spheres bound triangles quite well, and thus will probably reduce your calls to tri/tri to 1 or not much more. You can refine by a quick sphere/tri, possibly. I don't know if it pays the candle.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Charles B: The pseudo code is for for true real time CD. Maybe I should have pointed that out. The thing is that the implementation must be able to be used on any kind of objects that can be deformed in any way, even splitted, at any time. That's why it was chosen in the first place for my project. The only thing it can't handle (that I know of) is self-intersection. It's true that the octree may run into problems for some cases.

"Most real life meshes can often be split into a few convex parts." If you can do it offline, yes, but for real time CD it can be difficult.

The collision determination code was not the main thing in the project I used it for so I chosed an approach that I knew would work and was fairly easy to implement.

My whole project will be open source when it's finished so you can all kill me later. :)

/__fold

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

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