Collision Detection using GJK and EPA algorithm

For collision detection we implemented the GJK(Gilbert-Jhonson-Keerthi) algorithm. The Algorithm makes use of the concept of Minkowski-difference of two convex objects, i.e if two convex objects intersect, then the Convex Hull of the Minkowski difference encompasses the origin. 


We used SteeeLite API (​https://github.com/SteerSuite/SteerLite.git) and implemented the GJK algorithm in the collision AI module. For finding the collision depth for intersecting polygons, we implemented the EPA algorithm.

Here are some screen-shots of our implementation and results.

For the situation described in figure 1, the GJK algorithm gives us the collision results as expected.

                                                       Fig 2

For the situation described in Figure 2, the GJK reports a collision b/w the polygons, whereas in reality there is no collision. This is due the fact that the polygons are concave. To solve the problem, we decompose the concave polygon to the left into two convex polygons(two triangles) and then run the GJK.

After convex decomposition we get the result of no collision.

Navigation Meshes and Crowd Simulation

As a part of our course project, we were asked to  design a relatively complex environment using different obstacle configurations for crowd simualtion.

Our environment consists of a scene with two levels,  navigation static containers(on top of which agents can move/jump), multiple bottleneck areas.

We created an "Agent" prefab with NavMeshAgent component to allow agents to navigate in
the environment while using the navigation mesh and then created a script to select agents and specify which destination to navigate towards. For this we capitalized on the concept of Ray Casting.


The next part of the project, was to get a good grip about Unity's Mecanim Animation System and
create an animated human character using Mecanim.
This was done by taking a humanoid character, importing  its animation data onto the humanoid and then create an animation state machine to have him walk, run, jump. A controller script was created where a player can control the character using arrow keys,run modifiers (shift key) and SPACE to jump.
A “third person” camera is implemented and attached to the character to give an RPG feel.


In the last part, we integrated our prefab into our crowd simulator to create a crowd of directable animated characters. Double right clicking the destination will make the agent sprint towards it.

Please click the following link for the web deployed version of our Game,
https://dl.dropboxusercontent.com/s/dedu824xex8kdsw/builds.html

P.S Please use Mozilla Firefox for best results.