I am trying to use bullet (through JMonkeyEngine 3) to detect intersections between volumes. I don't need any kind of physics simulation; no velocities, forces, mass is irrelevant. On top of it, I need accurate detection (with convex meshes only).
So far I measured the accuracy colliding box-shaped meshes (not btBoxShape, but btConvexShape), and I noticed I can get the accuracy I need by scaling all objects up by a factor of 1000 (the error in face-to-face collisions does not scale with the object size, although the edge-to-face and edge-to-edge do). Generally, this works well, although I am sure this is quite a stretch of a use-case.
Stress-testing my library, however, I found that some collisions will go undetected by bullet. I could reproduce the case on Java/JMonkeyEngine and I am trying to do the same on C++ for plain bullet. Particularly, I have noticed that for two btConvexShapes (which happen to be cubes of side 2000) placed at exactly the same point, for some rotations, bullet wont report any intersection. This is not a practical problem by itself, but raises concerns about other possible cases where the library might be inaccurate.
To summarize, what I am looking for is:
- Accurate intersection between objects (1/1000th of a meter, if we assume 1 unit is a meter)
- No need for force, velocity, acceleration or mass, just code handling intersections.
- Working for general convex meshes, I don't need accuracy for concave shapes, but I can't get away with just btBoxShape.
- No margins.
Is there a sane way of doing this with Bullet?
Thanks in advance!
Using Bullet for plain, accurate, convex intersection detection.
-
drleviathan
- Posts: 849
- Joined: Tue Sep 30, 2014 6:03 pm
- Location: San Francisco
Re: Using Bullet for plain, accurate, convex intersection detection.
More information please:
Do you just need to know whether two shapes overlap or not? Or do you also need to know depth and direction of overlap?
When they do touch do you need to know a useful contact manifold? This would be important for knowing how to transfer collision momentums.
Do your calculations need to be real-time and very efficient? Or can you use a slower algorithm/implementation as long as it is accurate?
Do you just need to know whether two shapes overlap or not? Or do you also need to know depth and direction of overlap?
When they do touch do you need to know a useful contact manifold? This would be important for knowing how to transfer collision momentums.
Do your calculations need to be real-time and very efficient? Or can you use a slower algorithm/implementation as long as it is accurate?
Re: Using Bullet for plain, accurate, convex intersection detection.
No need for other information than which shapes overlap. Performance is not a priority (of course within some reasonable limits). The scenes are never too populated anyway. Accuracy however is a hard constraint.drleviathan wrote: ↑Mon Jun 17, 2019 3:03 pm More information please:
Do you just need to know whether two shapes overlap or not? Or do you also need to know depth and direction of overlap?
When they do touch do you need to know a useful contact manifold? This would be important for knowing how to transfer collision momentums.
Do your calculations need to be real-time and very efficient? Or can you use a slower algorithm/implementation as long as it is accurate?
Thanks for your reply.
-
drleviathan
- Posts: 849
- Joined: Tue Sep 30, 2014 6:03 pm
- Location: San Francisco
Re: Using Bullet for plain, accurate, convex intersection detection.
One way to achieve your goal would be to use the GJK algorithm. Bullet has a GJK implementation but it is just one cog in the machine. You could extract that cog, figure out its API, and bend it to your will. Alternatively you could search for some other GJK implementation or even implement your own.
The GJK algorithm is a fast way to figure out whether two shapes overlap or not. It can be enhanced to also estimate the closest approach and depth of overlap, however it sounds like that tweak is outside the scope of your interest. The short overview is: if the origin lies inside the Minkowski sum of the two convex shapes then they overlap, else they don't. The Minkowski sum, in general, is an infinite hypothetical construct whose full set of points cannot be computed however if you could prove the origin is inside it or not then you would know. So the GJK algorithm boils down to searching for a sub-volume of the Minkowski sum that contains the origin.
It is very likely someone has already written the tool for your job. You just need to find it.
In fact, I have written a GJK implementation in C++ that only computes overlap, not closest approach, for an open-source project (Apache License). You're welcome to try it and modify it to your needs if you like. It uses glm::vec3 for its vectors and has some unit tests, however it hasn't been used in production yet so in that sense it is "untested". It is implemented with 32-bits and according to its unit-test implementation its accuracy for grazing touches is within 1e-6 for shapes and separations on the order of 1e3 or less. Send me a PM if you're interested.
The GJK algorithm is a fast way to figure out whether two shapes overlap or not. It can be enhanced to also estimate the closest approach and depth of overlap, however it sounds like that tweak is outside the scope of your interest. The short overview is: if the origin lies inside the Minkowski sum of the two convex shapes then they overlap, else they don't. The Minkowski sum, in general, is an infinite hypothetical construct whose full set of points cannot be computed however if you could prove the origin is inside it or not then you would know. So the GJK algorithm boils down to searching for a sub-volume of the Minkowski sum that contains the origin.
It is very likely someone has already written the tool for your job. You just need to find it.
In fact, I have written a GJK implementation in C++ that only computes overlap, not closest approach, for an open-source project (Apache License). You're welcome to try it and modify it to your needs if you like. It uses glm::vec3 for its vectors and has some unit tests, however it hasn't been used in production yet so in that sense it is "untested". It is implemented with 32-bits and according to its unit-test implementation its accuracy for grazing touches is within 1e-6 for shapes and separations on the order of 1e3 or less. Send me a PM if you're interested.
Re: Using Bullet for plain, accurate, convex intersection detection.
Isn't GJK being used by-default by bullet? If not, I suspect it would be hard to take GJK out of Bullet without a lot of scaffolding, and I don't think there is anything to gain from using my own implementation instead of a well-tested library, so I'd rather use Bullet's implementation. How would I enable it? Can i fine-tune parameters to sacrifice speed and accuracy?
-
drleviathan
- Posts: 849
- Joined: Tue Sep 30, 2014 6:03 pm
- Location: San Francisco
Re: Using Bullet for plain, accurate, convex intersection detection.
I don't know how to do it exactly but merely mention it as a possibility. You'd have to identify the GJK parts, study its API, and figure out how to make it do what you want. Dunno how or if Bullet's GJK algorithm can be fine-tuned.