Project demo

Tutorial mode

After the intermediate project presentation we changed paths a little bit, although this hasn't really been clear until now. Our original plan was to make a 3D GJK for convex objects and to use it to make a kubb game. However, we were adviced to instead create an interactive GJK tutorial. That is why we have limited our GJK to 2D and instead focused on the concave implementation. 

The first thing we did for our tutorial mode was to show the Minkowski difference.

The Minkowski difference between the shapes S1 and S2 is the set of all points that can be expressed as a point in S1 minus a point in S2. In somewhat mathematical notation, Mdiff = {p1 - p2 : p1 in S1, p2 in S2}. If S1 and S2 are overlapping, there exists a point p that is in both S1 and S2. There fore the point p - p = 0, is in the Minkowski difference. This is the main idea of the GJK algorithm. If the Minkowski difference contains the origin, the shapes are overlapping. 

Of course, we didn't calculate the Minkowski difference by looking at all points in both shapes. We looked at just the Minkowski difference of the set of vertices of each shape, and used Jarvis' gift wrapping algorithm to find the convex hull of the corners found.

😎 😎 😎 😎 😎

The GJK algorithm doesn't look at the entire Minkowski difference to find whether it contains the origin. Instead, it starts with just a line and then adds points to create a subset of the Minkowski difference until it can conclude that it does or cannot contain the origin. Our tutorial mode adds functionality so that the user can step through and visualize each of these steps. 

As can be seen in the above example, if the shape we have right now doesn't contain the origin, we extend the shape in the direction that we think the origin is. We then repeat this until the shape contains the origin, as it will since the shapes are overlapping. In the final step we found that they are indeed overlapping.

When the shapes are not even close to overlapping, the algorithm sometimes only needs one or very few steps to come to this conclusion. This is because we do a check. If we find that we have been searching in the right direction but we are at the end of the Minkowski difference and still haven't found the origin, we can conclude that the Minkowski difference cannot possibly contain the origin.

In the above example, the algorithm terminates after just one iteration.

😎 😎 😎 😎 😎

Now, some of you might have noticed that I wrote that we are using the convex hull to find the Minkowski difference. If we have concave shapes, this won't work correctly. In those cases, we are actually performing GJK multiple times, once for each combination of convex part of the concave shapes. 

In the above example, the left shape has been divided into two convex parts, so there are two Minkowski differences. The idea is the Minkowski difference that we are iterating over right now will be red and the others white, but this isn't really working right now. 

I will now post about a million screenshots to show how GJK works on a concave shape.

The algorithm first looks at the left part of the concave shape (the white Minkowski difference) and correctly concludes that it is not overlapping with rectangle. We then look at the right part.

This Minkowski difference does contain the origin, so we have found that the shapes are overlapping. 

😎 😎 😎 😎 😎

The above examples have been simple enough. Before I finish this extremely long blog post, let's have a look at what happens with a complex concave object that gets divided into many parts.

Clearly, the Minkowski differences are overlapping a lot so there must be a more optimized method than GJK:ing over each one. However, we will not be looking into that for this project. For now, we are viewing this as an educational tool and will simply recommend that the user focuses on simple shapes when in tutorial mode.

Concave shapes integrated

Today we adapted our main algorithm to work with concave shapes. In the previous blog post we divided our concave shapes into convex parts. However, then we GJK'd each of those parts. Now we work on a group of convex pieces as a single unit.

We also made the line work again. We did this by finding the closest distance between all pieces and choosing the shortest one. 

By taking these pictures we also accidentally summoned the devil.

As a bonus, here is one of Rodrigo's artworks: