Jump to content
  • Advertisement
Sign in to follow this  
KDSBest

TriMesh-TriMesh Collision

This topic is 4640 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

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

Share this post


Link to post
Share on other sites
Advertisement
Currently, ODE supports Box-Trimesh, Sphere-Trimesh and Capsule-Trimesh.
But it doesn't support polyhedron-trimesh or trimesh-trimesh. Download it from SourceForge.net.
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Kwizatz
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).

That's a lot easier to say than done.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
That'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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by leoptimus
Ok 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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!