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.
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.
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.
No comments:
Post a Comment