Computer
Graphics
Group 40
Documentation
***Note: We built A2 for Windows***
A2: Collision Avoidance
Description:
GJK:
This assignment requires us to implement the
GJK and EPA algorithms for polygon obstacles in two dimensions. We first
tackled the GJK algorithm and then continued on to develop the EPA algorithm.
To start off, we implemented a few “helper” functions, called getFarthestPoint,
getClosestEdge, getSupport, and containsOrigin. The getFarthestPoint function
returns the farthest point in the shape in some specific direction. The
getClosestEdge gets the closest edge of the shape to the origin; sets the
distance variable equal to the distance from the closest edge to the origin;
sets the normal vector to the normalized vector that is perpendicular to the
edge in play; and lastly it sets the index of where to add a new point to the
simplex. The getSupport function used the getFarthestPoint function to return
the farthest point in the Minkowski difference between the two shapes in the
specific direction defined earlier. The containsOrigin function is very
important because it returns true if a simplex contains the origin – meaning
that the two shapes intersect. It is important to note that this function takes
into account the different sizes of the set of simplexes and creates vectors
according to the k-simplex rules. If the origin is not contained in the set of
simplexes, the function will return false and find some new direction vector.
Now, the GJK function ties together all of these functions. It utilizes the
getSupport function for the two inputted shapes and direction vector and pushes
this into our first simplex (a singular point). It continues the process,
discarded “not helpful” simplexes in the process, till the algorithm converges.
EPA:
In order to solve and code the EPA algorithm,
we used the same helper functions that were defined before. Specifically, this
algorithm calculates the penetration depth and the MTV (minimum translation
vector). It does this by finding the
closest edge of the simplex to the origin, using the getClosestEdge function.
Then it uses the getSupport function to find the farthest point in the
Minkowski difference in the direction of the normal vector to the closest edge.
Next, it calculates the distance of the farthest point along the normal vector.
If this distance minus the distance of the closest edge to the origin is less
than .01% (we calculated this number to be an accurate tolerance number), then
the algorithm has converged and we can end. If not, then it continues to add
simplexes and iteratively solve the algorithm.
Intersect:
The intersect function calls both the GJK and
EPA functions; they can almost be thought of as the intersect function’s helper
functions. Intersect uses the GJK function is detect if there is a collision between
two shapes and if they are, it calls the EPA function to get the penetration
depth and the MTV. Otherwise, it will return that the shapes are not colliding.
Polygons2:
What was wrong with this XML file was that
both the shapes were not convex. Since the algorithms we wrote are only for
convex shapes, we changed polygons2.xml so that it included convex shapes. We
did this by rearranging the top right shape points so that they at least
collided. We were not able to rearrange the points in the bottom left shape to
create a convex shape, so instead we split it into two separate convex shapes.
After all this, we were able to create an xml file with convex shapes that
could be used with our algorithms.
Testing:
When we tested our algorithms with the given test files, we saw the following results.
Polygons1:
Output:
NO collision detected between polygon No.0 and No.1
Polygons2:
This was polygons2 before it was fixed. As you can see, these shapes are not convex.
Polygons2:
This is polygons2 after it was fixed. You can see how we split up the one shape into two and how we rearranged the order of points of the third shape to create a convex shape.
Testing:
When we tested our algorithms with the given test files, we saw the following results.
Polygons1:
Output:
NO collision detected between polygon No.0 and No.1
NO collision detected between polygon No.0 and
No.2
NO collision detected between polygon No.0 and
No.3
NO collision detected between polygon No.0 and
No.4
NO collision detected between polygon No.0 and
No.5
Collision detected between polygon No.1 and
No.2 with a penetration depth of 1.
34164
and penetration vector of (-0.894427,0,-0.447214)
NO collision detected between polygon No.1 and
No.3
Collision detected between polygon No.1 and
No.4 with a penetration depth of 1
and
penetration vector of (1,0,0)
Collision detected between polygon No.1 and
No.5 with a penetration depth of 0.
707107
and penetration vector of (-0.707107,0,-0.707107)
NO collision detected between polygon No.2 and
No.3
NO collision detected between polygon No.2 and
No.4
Collision detected between polygon No.2 and
No.5 with a penetration depth of 2
and
penetration vector of (-0,0,1)
NO collision detected between polygon No.3 and
No.4
NO collision detected between polygon No.3 and
No.5
NO collision detected between polygon No.4 and
No.5
Polygons2:
This was polygons2 before it was fixed. As you can see, these shapes are not convex.
Polygons2:
This is polygons2 after it was fixed. You can see how we split up the one shape into two and how we rearranged the order of points of the third shape to create a convex shape.
Output:
NO
collision detected between polygon No.0 and No.1
NO collision detected between polygon No.0 and
No.2
NO collision detected between polygon No.1 and
No.2
