Rutgers CG Group 14 Blog: October 2015

Monday, October 26, 2015

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.

Friday, October 16, 2015

Assignment B1 Unity: Navigation & Animation

Rutgers Computer Graphics Course Fall 2015 Assignment B1

Unity: Navigation & Animation

PART 1: Navigation

1. We designed a relatively complex environment, our environment include a simple maze field, two rooms, two bridge, two stairs, bottleneck areas, 3 height levels.
2. A navigation mesh and off mesh links for the whole environment was computed.
3. Created capsule collider prefab for the “Agent”, and several agents were used to create a crowd.
4. A mouse script was created to select and specify the destination of agents.
5. “Director” script was setup to keep track of all selected agents and send messages to each agent to move to its selected destination.
6. Two obstacles were created in the environment, they can be selected by mouse and be moved using arrow keys.
7. We manually created two off mesh links for stairs, they were used to connect different planes.
8. For moving carving, it will recalculate the navMesh carving EVERY SINGLE FRAME

- Difference between carving and not carving:

  A NavMeshObstacle is cylindrical in shape and can move around the surface of the NavMesh with a specified velocity.

  When carving is disabled, agents will ignore the obstacle when calculating paths but will sidestep around it while moving along the path. So the obstacle will only affect the agent's avoidance behavior rather than the pathfinding.

  If carving is enabled, the obstacle will create a temporary "hole" in the NavMesh. The hole will be recognized by the pathfinding, so calculated paths will avoid obstacles.

  - When and why use carving or not carving:
  For automatically moving NavMeshObstacles, navMesh will change every single frame, as the result, agents will calculate paths every single frame. It will cause great overhead. So it's not recommended to active carving for automatically moving NavMeshObstacles.

  But for stationary NavMeshObstacle for obstacles controlled by input, navMesh will not change very frequently, the overhead is relatively much smaller. So we can active carving for these NavMeshObstacles.

  - Problems for carving and not carving:
  a. if we make all obstacle carving, moving carving may cause stuck of some agents because of recalculating path every single frame.
  b. if we make all obstacle not carving, agents may not effectively avoid obstacles.

9. In order to avoid obstacles, we can use collision detecting to predict if gents will colloid with obstacles or not. Using if the distance between an agent and obstacles < triggerDistance ( collision of agent and obstacles) to detect collision. When detecting collision, we could set the triggerDistance a little bigger so that agents could predict if it will colloid with obstacles earlier.

10. Extra credit attempt: When we active carving for the automatically moving obstacles, agents could avoid then automatically, but some agents will get stuck, especially when the calculated path going through the locus of these obstacles. The reason for this problem is that, when carving activated, pathfinding module will have to recalculate the path every frame because the navMesh is changing every fame, which is very expensive overhead. In the worst situation, agents may not get the path bacause pathfinding module is always calculating but doesn’t return path to agents, which will make the agents stay on original position.

11. Extra credit attempt: We add both NavMeshAgent and NavMeshObstacle component on the Nazgul agent. To let other "human" agents avoid the Nagzul by a rather far distance, we set the size of NavMeshAgent and NavMeshObstacle much bigger than it appears. The tricky part is that, when NavMeshAgent and NavMeshObstacle component are on the same agent, it will colloid with itself, and appears randomly on the scene. To solve the problem, we modified the height of the NavMeshAgent and NavMeshObstacle and let them have different position on y axis, so that they will not colloid with each other.

The Nazgul is the read capsule located in the center of the plane, click to slick it. Move the Nazgul like normal capsule agent.

Play Instructions:

Use mouse left click to select agent or obstacles, you can hold left Ctrl key to select multiple agents.

Use mouse right click to deselect.

For agents, after selecting, use mouse left click to select destination.

For movable obstacles, after selecting, use "←" "→" "↑" "↓" to control obstacle movement.

Part1 Web playable demo

(Unity Web Player maybe not supported by Chrome, recommend using another browser, such as Internet Explorer, Firefox or Opera )

PART 2: Animation

1. An animated human character model and animation clips were download to Unity.

2. An animator controller was created; it has several states, including idle, walk, run, jump fall and dance.

3. The animated human character prefab was created.

4. The camera view was set to follow the character; this can be seen in the playable demo.

Play Instructions:

Use "W" "A" "S" "D" or "←" "→" "↑" "↓" to control character's movement.

When walking, press and hold left "Shift"key to run.

When walking or running, press "Space" to jump.

When idling, press "G" for a dance.

When the character will fall down when he reach the cliff.

Part2 Web playable demo

(Unity Web Player maybe not supported by Chrome, recommend using another browser, such as Internet Explorer, Firefox or Opera )

PART 3: Combine Animation & Navigation

1. The prefab in part 2 was integrated into our crowd simulator, a crowd of direct able animated characters were created.
2. When navigating the same level off mesh links, characters jump. When character navigating the drop fall off mesh links, the character will fall and roll to the ground
3. Speed is adjustable, keep press Z will let the agent run.

4. Extra credit, we Integrate the 3 scenes, and create a menu that user can select which part want to play and press ESC back to main menu.

Play Instructions:

Same with Part 1

Part3 Web playable demo

(Unity Web Player maybe not supported by Chrome, recommend using another browser, such as Internet Explorer, Firefox or Opera )