Algorithmic and Architectural Gaming Design: Implementation and Development

Algorithmic and Architectural Gaming Design: Implementation and Development covers a myriad of game development topics. But what sets this book apart, in my opinion, is the focus on actual implementation. 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 Read more about Algorithmic and Architectural Gaming Design: Implementation and Development[…]

Contact Points Using Clipping

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.


EPA (Expanding Polytope Algorithm)

In the last few posts we learned about using GJK for collision detection, distance between shapes, and finding the closest points. It was stated that GJK must be augmented, to find collision information like the penetration depth and vector, with another algorithm. One such algorithm is EPA.

I plan to cover the EPA algorithm and mention an alternative.

GJK (Gilbert–Johnson–Keerthi)

Today I’m going to talk about the other collision detection algorithm packaged with the dyn4j project. You can find a lot of GJK documentation but much of it is really technical mostly because they are research papers. I strongly recommend this video tutorial and to be honest you may not even need to read any further after watching. But if you feel you need more information after watching the video please read on.

SAT (Separating Axis Theorem)

This is a post I have been meaning to do for some time now but just never got around to it. Let me first start off by saying that there are a ton of resources on the web about this particular collision detection algorithm. The problem I had with the available resources is that they are often vague when explaining some of the implementation details (probably for our benefit).

I plan to explain the algorithm and also fill in some of the blanks that I had when implementing this myself.