Assignment A2 Collision Detection

Part1 Output ploygons1:

 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

 Collision detected between polygon No.0 and No.4 with a penetration depth of 0.707107 and penetration vector of (-0.707107,0,0.707107)

 Collision detected between polygon No.0 and No.5 with a penetration depth of 2 and penetration vector of (-0,0,1)

 NO collision detected between polygon No.1 and No.2

 NO collision detected between polygon No.1 and No.3

 NO collision detected between polygon No.1 and No.4

 NO collision detected between polygon No.1 and No.5

 NO collision detected between polygon No.2 and No.3

 NO collision detected between polygon No.2 and No.4

 NO collision detected between polygon No.2 and No.5

 Collision detected between polygon No.3 and No.4 with a penetration depth of 1 and penetration vector of (1,0,-0)

 NO collision detected between polygon No.3 and No.5

 Collision detected between polygon No.4 and No.5 with a penetration depth of 1.34164 and penetration vector of (0.894427,0,0.447214)

Part B Output ploygons2:

loaded module collisionAI

loaded module testCasePlayer

Initializing...

Preprocessing...

 NO collision detected between polygon No.0 and No.1

Simulation is running...

Postprocessing...

Simulated 14 frames.

Cleaning up...

Done.

Part C Output ploygons2 new:

In the testcase polygons1, all the polygons are convex, so that the GJK and EPA works nice. However in the testcase polygons2, the two polygons are not convex polygon, the GJK cannot determine the collision about concave polygon.  So we fix the testcase, change the two concave polygons to convex polygons. We ignore the point (3,0,0) of the first polygons and (5,0,-3) of the second polygons. And changed the order of the vertex in testcase. After we changed the testcase, there is a collision between two polygons.

loaded module collisionAI

loaded module testCasePlayer

Initializing...

Preprocessing...

 Collision detected between polygon No.0 and No.1 with a penetration depth of 1.00024 and penetration vector of (0.800072,0,-0.599904)

Simulation is running...

Postprocessing...

Simulated 13 frames.

Cleaning up...

Done.

EXTRA CREDIT ­­ PART D

We attempted the part D

The standard GJK algorithm cannot detect collision between concave polygons, if we just run the standard GJK for the testcase3, the output shows that there is a collision between to polygons. But actually there is no collision

The idea to fix the code is keep the GJK and EPA algorithm, and add a process which is polygonal decomposition. We separate the polygons to triangles. And detect collision between triangles of each polygons.

We have a function call separatepolygon. In this function, we find the left most point in the polygon A, and find the two adjacent vertices B and C , check this triangle that there is other polygon point P inside the triangle ABC or not. If there is not vertex in the triangle, remove the point A and do the algorithm recursively.  If there is a vertex of polygon P in the triangle, we connect the A and P. the one polygon become to 2 polygons, and call separatepolygon for those two new polygon.

After did this the output of polygon3 is correct.

Output ploygons3:

loaded module collisionAI

loaded module testCasePlayer

Initializing...

Preprocessing...

 NO collision detected between polygon No.0 and No.1

Simulation is running...

Postprocessing...

Simulated 96 frames.

Cleaning up...

Done.

And we edit polygon3 to polygon4 that move the up-right polygon to negative x direction 2 to make two polygon collision, the shapes likes look below. And our algorithm detect the collision correctly

Output ploygons4:

ploygons4:

loaded module collisionAI

loaded module testCasePlayer

Initializing...

Preprocessing...

 Collision detected between polygon No.0 and No.1 with a penetration depth of 2.00048 and penetration vector of (0.800072,0,-0.599904)

Simulation is running...

Postprocessing...

Simulated 215 frames.

Cleaning up...

Done.

We also make a new testcase which is more complex concave polygon to check our separate function is correct or not. The lower polygon separate to five triangle which are

the new triangle is (2,0,1)(0,0,0)(1,0,0)

the new triangle is (2,0,1)(1,0,0)(4,0,1)

the new triangle is (3,0,3)(2,0,1)(4,0,1)

the new triangle is (2,0,-1)(0,0,0)(1,0,0)

the new triangle is (2,0,-1)(1,0,0)(4,0,-1)

Actually, we did some research and found there are many ways to do the polygon decomposition, the way we used is the simplest way to do that. But I think if the polygon is complex enough like it contain so many vertices, our method is not that efficiency. 

After did this, we found a problem that the EPA sometimes does not work correctly to compute the penetration depth and vector when we separated the polygon to triangles. When we detect collision by using two triangles from each polygons, and compute the EPA, the penetration depth and vector is not the depth and vector of polygons. Maybe moving the triangle to a vector with depth can avoid collision with other triangle, but the polygons may also collision in other parts.  We tried to find a way to deal this problem, but unfortunately, we did not find a way to do that.