# TriMesh-TriMesh Collision

## Recommended Posts

KDSBest    100
Hi, has someone a tutorial or something with a great triMesh-triMesh collision or AABox trimesh collision? Thx

##### Share on other sites
leoptimus    106
Currently, ODE supports Box-Trimesh, Sphere-Trimesh and Capsule-Trimesh.
Watch the examples. ODE exposes its collision detection routines. You can make modifications to it and improve a better collision method for trimeshes.

The basic problem lies on penetration depth. With trimeshes, every triangle behaves like a piece of paper: so objects at high velocity can pass through.

##### Share on other sites
Kwizatz    1392
You'd be wise to avoid trimesh-anything collision altogether, and focus on Convex polyhedrons instead (any trimesh can be broken into multiple convex polyhedrons).

##### Share on other sites
Guest Anonymous Poster
Quote:
 Original post by KwizatzYou'd be wise to avoid trimesh-anything collision altogether, and focus on Convex polyhedrons instead (any trimesh can be broken into multiple convex polyhedrons).

That's a lot easier to say than done.

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by Anonymous PosterThat's a lot easier to say than done.

Manually breaking level geometry into convex shapes (or modeling your levels out of convex shapes from the get-go) goes a lot easier on your psyche than trying to code a working, glitch free continuous collision detection agorithm involving concave shapes, just dont say I didn't warned you.

Beware my friends, as you pass by
As you are now so once was I
As I am now so you must be
Prepare my friends to follow me

Been waitting to use a Megadeth Quote for ages [smile]

##### Share on other sites
leoptimus    106
Ok Kwizatz. So, do you know where we can find a library that collides convex polyhedrons? With penetration depth and contact points and normals?

##### Share on other sites
dgreen02    1428
Newton does it. He's working on adding support for continuous collision detection right now. I'm using it in my game...it's pretty robust.

Newton Homepage

You can retrieve the collision normal, depth, etc. very easily using the collision callback functions the library provides.

Best of all the library is free :-)

- Dan

##### Share on other sites
leoptimus    106
Ok, Ok, Newton, and Tokamap and a couble of engines does polyhedron collisions. But at this time is afforable to find a collision detection engine which comes as OpenSource .( Forget Solid 2.0 It doesn't work!)

##### Share on other sites
Guest Anonymous Poster
Well there are few libraries but as you already found out with Solid these are not what you can call production code.
Each one of these libraries is using and algorithm called GJK or a variance of it.
The problem with the GJK algorithm is that it is mathematically correct but numerical unstable algorithm. Theses instability have a very low probability rate but they do happens. Each one of these library claims they had found a solution to the numerical instability, but in reality all they have done is shifting the problem from one space to another. In the end what you get is that where a library fail a test another pass it but where that one pass it other fail.

To find out how unstable this method are all you have to do take a look at the inner core of the implementation and you will find at least critical tolerances with all kind of configurations setting, some time more than one. Some of them even have abomination backup procedures for when something goes extremely wrong for not reason at all.

In general the best of these libraries will inexplicable fail a collision query in 10,000 to 100,000 tries, which is unacceptable when writing robust and reliable application.
This is why these libraries had been around for so long but there are only used for impressive demos that run in very contrive setup. When used for production code that rate of failure is a showstopper.

I assume physics engines like Havok and Novodex, and maybe the free ones are using the same algorithms, the difference is that some how they have very optimized implementation and they had figured out reliables way to recover from these instabilities innate to GJK.

You can check: Swift (very good), ICollide, VCollide, Vclip, lately Z collide and Bullet
but be ready to experience the same problems you have with Solid in difference scenarios, so if you are ready to fight these problem you can check then out.

Another solution is that you can read the papers and give it a shot at your own implementation.

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by leoptimusOk Kwizatz. So, do you know where we can find a library that collides convex polyhedrons? With penetration depth and contact points and normals?

I am writting the code for ODE to support convex hulls (No GJK, due to the reasons the AP pointed out), so far I got convex-plane and convex-sphere collision covered, still working on convex-convex, ray-convex shouldnt be hard, convex-box is a subcase of convex-convex.

In real life, for a quake2-3ish kind of game all you really need is continuous Convex-Sphere (like I descrived here) for player movement, everything else is not a "need" but a nice to have, at least until you throw vehicles into the mix [smile].

##### Share on other sites
Guest Anonymous Poster
Why making it specific to ODE and not a separate collision library with an ODE friendly interface if you will?
Many people here would love it.

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by Anonymous PosterWhy making it specific to ODE and not a separate collision library with an ODE friendly interface if you will?Many people here would love it.

Well, the selfish answer (though I'll be donating the code to the ODE project) is that because I want to use ODE for my physics simulations, and currently the thing it lacks for it to be a perfect match for my engine is convex collision handling.

The technical answer is that ODE already takes care of the collision detection broad phase and many other things that would be required to be recoded for a complete stand alone collision library (IE: sphere-sphere collision detection is already there), the library would, for all effects, be pretty much useless by itself.

By coding the convex collision detection directly inside ODE, it will do what is required and nothing more, plus, it reuses functionality already present in ODE such as matrix multiplication routines, dot and cross products, etc.

##### Share on other sites
leoptimus    106
Kwizatz!
Have you ever done the code of convex collisions for ODE? Successfully? And works fine? If you've done, would be kind of you to share us a demo executable!

##### Share on other sites
leoptimus    106
Ah! I forgot to tell you.. I've checked Bullet, but it does support Tetrahedrons only. With its GJK algorithm, it only supports basic shapes. But it doesn't support a big polytope with a lot of faces.

##### Share on other sites
Kwizatz    1392
Well, like I said, I am in the process of writting it, here is an early demo, it only supports sphere-convex and plane-convex so far, and well... for now convex objects are just cubes, I'll switch to an octahedron or something fancier once I know the code works 100%.

I saw the Bullet demo, I think it looks pretty good, but I did notice certain inacuracies (a tetrahedron floating slightly above the ground), and like I said I am quite skeptical of GJK behaving nicelly.

##### Share on other sites
leoptimus    106
Works Nice!
If you want a contribution, I give you a suggestion: Use the same code for colliding Convex-Plane for Convex-Convex. Try to find which faces are colliding, and then clip each other with their edges. Then Calc contact points and penetrations with the clipped points.
Can you do it?

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by leoptimusWorks Nice!If you want a contribution, I give you a suggestion: Use the same code for colliding Convex-Plane for Convex-Convex. Try to find which faces are colliding, and then clip each other with their edges. Then Calc contact points and penetrations with the clipped points.Can you do it?

Thanks!

Sadly, it's not so simple, I though I could reuse the code in convex-plane for convex-convex, but it's actually pretty impractical... however in my search for the least memory hungry algorithm for convex-plane detection, (thanks to Christer Ericson <plug>Buy His Book!</plug>) I did some research on The Gauss-Seidel Method for solving a series of equations (the equations of the planes forming the convex hull), which eventually turned up to be really impractical and unstable for convex-plane (oh! the irony [smile]), but seems to be perfect for convex-convex collision detection.

I started writting some SAT code, but in the end I scratched it because I felt it was too computationaly expensive if the 2 shapes are in fact colliding, plus, (I think) it doesn't easily give you penetration info if the 2 shapes collide, thus, more computations are needed.