Real-Time Physics Simulation Forum

I am a new MS student at the University of Illinois at Urbana Champaign. I am working under a Ph.D. student who wants my help finding a basic GJK function in the bullet library for our quadcopter collision detection program. We want to make our code more robust by using a professional library for the GJK implementation. We just want to input two sets of points to the function forming convex polygons and have the function return the shortest distance magnitude and the weights of the points in the two shapes for the direction. This library seems more geared towards virtual reality and I have not been able to find a basic GJK function which can be called on two convex polygons, instead of more complex implementations. Does anyone know which function I should use, and where the documentation might be?

Thanks.

If you look for "Gjk" in the codebase filenames you'll find several files that look relevant, however I suspect it would be hard to pull just the GJK algorithm out of Bullet without taking a lot of other stuff for support.

It sounds like maybe you only need a 2D implementation of the GJK algorithm. If so then the good news is that while the GJK algorithm is complicated to understand at first, it is not very hard to implement in 2D. My advice would be to research it more and then decide if you want to implement it yourself or hunt for an existing implementation.

This article does a good job of explaining GJK.

When I search the web I find several GJK implementation tutorials that walk through the process and provide the final source code as well.

I agree with drleviathan that it helps to get better understanding in how GJK and EPA works.

There are a few ways to just use the low-level collision detection between two convex objects using Bullet:
See btCollisionWorld::contactPairTest
https://github.com/bulletphysics/bullet ... rld.h#L457
This will require linking against Bullet LinearMath and BulletCollision

If you want to use GJK and EPA using as few dependencies as possible, check out
https://github.com/erwincoumans/bullet3 ... /collision

In this unit test, GJK and EPA is moved in header files, and you only need a few c++ files:
https://github.com/bulletphysics/bullet ... emake4.lua
https://github.com/bulletphysics/bullet ... eLists.txt

Previously there were many low-level examples/demos to show how to use GJK and other low-level parts of Bullet,
See the old demos here: https://github.com/bulletphysics/bullet ... emos/Demos, in particular ConvexHullDistance and EPAPenDepthDemo
we should re-enable such low-level demos in the Bullet Example Browser.

This library seems more geared towards virtual reality

I find that an odd conclusion. Bullet Physics is an SDK for real-time collision detection and
multi-physics simulation for games, visual effects, robotics and so on, not just for vr.

Thank you for your comments. Our algorithm definitely is for 3D and needs to be as portable as humanly possible. We don't need to use EPA at all, and just need a GJK implementation which returns the shortest distance between two convex hulls and the corresponding vertices weight for each hull mapping the direction of that vector from that hull. We of course already have GJK code, but we are looking to use the bullet library in order to ensure robustness. My problem is that all of the functions and demos I can find in the bullet documentation are much more generalized than what I require and I am wondering if you can point me to a specific function or set of methods. What was mentioned in the previous responses included EPA and collision detection, and we are focused on collision avoidance for trajectory planning so this might be to generalized.

My point was that I have not actually seen documentation of this library being used for portable realtime collision avoidance on physical vehicle systems, only for software and simulations. VR was just one example because I see quaternions everywhere when I look at some of the code.

wyattsmcall1,

I'm not a big fan of throwing my collision modules away but will make an exception here. I attached the GJK submodule that belongs to the collision module of Bounce, a physics engine I've been working on since some months ago. It uses barycentric coordinates and Voronoi regions to find the closest points between two convex polyhedrons. There is also feature extraction and simplex caching (in a separate implementation for the sake of readability). These two algorithms are very usefull if you want to implement CCD.

Hope this solves your problem and good luck with your MS thesis!

Thank you so much drleviathan! I really appreciate the help. I am going over this code with my Ph.D. student advisor now and will make sure to site you if you wish. We will review the code and see if we can create our own adaptation for this project.

If you wish to be cited I will check back here and contact you the manner of your choosing. I will post any research publications here. Currently it is all up in the air of course but we will see.

This is our research page:
http://naira.mechse.illinois.edu

Best of luck.

In my opinion the GJK presentation by Erin Catto and its source code on the Box2D repository are the best resources available for understanding and implementing the GJK algorithm in 2D. If you need GJK in 3D I recommend the source code I posted. It is basically a 3D version of Box2D's.

Here is Erin's talk:

http://box2d.org/files/GDC2010/GDC2010_ ... in_GJK.pdf

Here is Erin's implementation:

https://github.com/erincatto/Box2D/blob ... Distance.h
https://github.com/erincatto/Box2D/blob ... stance.cpp