GJK Algorithm for Quadcopter Collision Detection

Post Reply
wyattsmcall1
Posts: 3
Joined: Sat Oct 15, 2016 9:28 pm

GJK Algorithm for Quadcopter Collision Detection

Post by wyattsmcall1 »

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.
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: GJK Algorithm for Quadcopter Collision Detection

Post by drleviathan »

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.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: GJK Algorithm for Quadcopter Collision Detection

Post by Erwin Coumans »

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.
wyattsmcall1
Posts: 3
Joined: Sat Oct 15, 2016 9:28 pm

Re: GJK Algorithm for Quadcopter Collision Detection

Post by wyattsmcall1 »

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.
irlanrobson
Posts: 16
Joined: Sun Feb 08, 2015 3:21 pm
Location: Brazil

Re: GJK Algorithm for Quadcopter Collision Detection

Post by irlanrobson »

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!
Attachments
GJK.zip
(9.5 KiB) Downloaded 653 times
wyattsmcall1
Posts: 3
Joined: Sat Oct 15, 2016 9:28 pm

Re: GJK Algorithm for Quadcopter Collision Detection

Post by wyattsmcall1 »

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.
irlanrobson
Posts: 16
Joined: Sun Feb 08, 2015 3:21 pm
Location: Brazil

Re: GJK Algorithm for Quadcopter Collision Detection

Post by irlanrobson »

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
Post Reply