Of course I’m a bit biased since I was privileged to write the chapter Collision Detection Using the GJK Algorithm (chapter 11). The chapter is about 35 pages long and covers a 2D implementation and explanation of GJK and related algorithms.
Throughout the chapter I explain the concepts with concrete examples and pseudo code. At the end of the last three sections I talk about the robustness of each, focusing on floating point problems and special cases.
Here’s a breif summary of the topics covered in the GJK chapter:
Introduction to Collision Detection
SAT-GJK (GJK w/o the distance sub algo.)
GJK Distance and Closest Points
Big thanks to the editors of the book for allowing me this great opportunity and an even bigger thanks to my Savior Jesus Christ.
Many have asked “How do I get the contact points from GJK?” or similar on the SAT, GJK, and EPA posts. I’ve finally got around to creating a post on this topic. Contact point generation is a vital piece of many applications and is usually the next step after collision detection. Generating good contact points is crucial to predictable and life-like iteractions between bodies. In this post I plan to cover a clipping method that is used in Box2d and dyn4j. This is not the only method available and I plan to comment about the other methods near the end of the post.
Had a friend of mine send me a link to this video on YouTube from the 1930’s explaining how a differential works. This video does a great job of explaining the concept and possibly the thought process that was used to develop it.
The next equality constraint we will derive is the prismatic constraint. A prismatic constraint is like the line constraint except it does not allow rotation about the anchor point. A prismatic constraint constraints the linear motion of the bodies along a line. An example of a prismatic joint is the slide of a semi-automatic pistol. The slide is moved back to charge the weapon, then released to its original position. The slide cannot rotate about the pistol, nor can it move up/down or left/right only along one axis.
In addition to the full OpenGL API, JOGL also offers OO approaches to common tasks like texturing, shaders, etc. The project owners, after reviving JOGL and JOAL (thank you!!!) have also been working on a binding to OpenCL called JOCL. This seems very promising and hopefully I’ll have some time to actually look into using this to help speed up some bottlenecks in dyn4j.
As a side note, I do have to say that the OpenGL API is really good and pretty well documented. I had a few “scratch my head” moments but for the most part I’m really liking it.
The next equality constraint we will derive is the line constraint. A line constraint is like a prismatic constraint (which will most likely be the next post) except allows rotation about the anchor point. A prismatic constraint constraints the linear motion of the bodies along a line. An example of a prismatic joint might be a roller coaster on the track. The cars cannot translate or rotate except along the track. For simplicity the prismatic constraint we will define is only for straight lines.
The next equality constraint we will derive is the weld constraint. A weld constraint can be used to join two bodies at an anchor point in which the bodies must move and rotate together (all DOF are constrained).
This post will differ slightly from the previous posts. A weld joint is basically a revolute joint + an angle joint. In that case we can use the resulting Jacobians from those posts to skip a bit of the work.
The next equality constraint we will derive is the angle constraint. An angle constraint can be used to join two bodies forcing them to have the same rotation. This particular constraint will be added to other constraints (in later posts) to form more complex constraints.
The next equality constraint we will derive is the pulley constraint. A pulley constraint can be used to join two bodies at a fixed distance. In addition, the constraint can be used to simulate a block-and-tackle.