Concave shapes

One big problem with the GJK algorithm is that it only works for convex shapes. If something is inside the cavity of a concave shape, it will detect an intersection because it is inside the convex hull of the shape.

 

It will also show the closest distance between the shapes as the closest distance to the convex hull.

Since many interesting shapes in applications of collision detection are concave, this is quite limiting. Thankfully, Felix has developed an algorithm which splits a concave shape into convex parts. 

Don't worry about the fact that the lines and the overlapping is a bit chaotic right now. Adapting our GJK algorithm for our new group of convex shapes will be our next step.

Multiple arbitrary shapes

Today we made our application a bit more fun to use. None of us could be bothered to make more test polygons in Blender. Instead, we can now click on arbitrary points in the scene to create a shape that works just like any other polygon.

As you can see, we also added functionality so that lines between all shapes are drawn, and the color changes if a shape intersects with any other.

One problem we have with arbitrary shapes is that our algorithm doesn't work for concave shapes. While Rodrigo and I have been working on the contents of this blog post, Felix has been working on some exciting stuff to fix this but I think that deserves its own blog post because he is a 

😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎😎

Distance between 2D objects

Today we extended our 2D GJK into a version that finds the points on two objects that minimizes the distance between them, as well as calculates that distance. We decided to visualize this new information with a line between the two closest points.

The algorithm works even when the shapes are rotated. When there are several candidates that all give the same distance, only two points are chosen, as can be seen in the first image. When the objects are intersecting, no line is drawn.

We still haven't drawn polygons other than squares to test our algorithm with. However, we tried it with Unity's built in pill shape and we accidentally found out that our algorithm works even for rounded shapes. 

GJK 4 life

First implementation of GJK

Today we implemented a first version of GJK in 2D. For now it only shows us whether or not our 2D shapes are touching. We are planning to extend this version into one which also tells us how far apart they are. We would also like to implement a GJK for 3D.

In our current version, the squares are red when they are touching and green when they are not. The algorithm also works when we rotate the squares.

Although we haven't hard coded the algorithm for squares only, we have only tested it with squares. This is simply because it is the only polygon that is readily available in Unity. Before we move on to our 3D implementation, we will test our algorithm with other polygons.

Setting up the scene

Before we can start implementing GJK we needed to set up the Unity environment we will be working in.

We added a few cubes to a scene and attached a Polygon script which finds all vertices of the shape. Finding the vertices of a shape turned out to be more difficult than expected. There is a built in method called Mesh.vertices which finds all vertices of the mesh. However, it creates duplicates since each corner lies on several different planes. On our cube, for example, each of the six sides has four vertices. Each corner has three vertices with the same position but different normal vectors. Hence, Mesh.vertices gives us a list of 24 vertices. Since we only care about the position, we wanted to remove duplicates. We also had to transform the vectors from coordinates local to the mesh into world coordinates.

In these images you can see that as we move our square, the coordinates (in the bottom right corner of the image) change as well. Our first implementation of GJK will handle 2D objects, so here we have used squares. However, our Polygon script also works on 3D objects, as can be seen below.

The last thing we did today was to create the shell for our GJK script. For now it only finds all Polygons in the scene and adds them to a list. 

Since none of us has much experience working with Unity, this first session was a bit slow and frustrating. Hopefully today's work will enable us to focus on implementing the algorithm.