Revision as of 13:54, 31 October 2015

Project 5: Robot Army

In this project you will need to implement a scene graph to render an army of robots. The army should consist of two platoons, which need to be independently controllable to behave like the people in this amazing video.

You can start out with your code from project 4. Don't worry if your mouse routines or lights don't work perfectly, neither is required for this homework project. But if your code has grown to an unwieldy size feel free to start from scratch.

This project is due on Friday, November 6th, 2015 at 2:00pm. You need to upload your code to Ted and present your results in the CSE basement labs as usual, grading starts at 2pm.

The homework discussion for this project will be on Monday, Nov 2nd.

The total score for this project is 100 points. Additionally, you can obtain up to 10 points of extra credit.

1. Scene Graph Engine (30 Points)

Implement a scene graph structure for our rendering engine. Use the following hierarchy:

The classes should have at least the following functionality:

• Class Node should be abstract and serve as the common base class. It should implement an abstract draw method: virtual void draw(Matrix4 C) = 0, and also an abstract virtual void update() = 0 method to separate bounding sphere updates from rendering.
• Group should store a list of pointers to child nodes (std::list<Node*>) and provide functionality to add and remove child nodes (addChild(), removeChild()). Its draw method needs to traverse the list of children and call each child node's draw function.
• Geode should be an abstract class. It should set OpenGL's ModelView matrix to the current C matrix, and have an abstract render function to render its geometry.
• MatrixTransform should store a 4x4 transformation matrix M which is multiplied with matrix C, which is passed to the draw method.
• Sphere should have a draw function which draws a sphere. You can use glutSolidSphere for that, or use your own tessellation algorithm.
• Cube should have a draw function which draws a cube. You can use glutSolidCube for that, or use your own implementation of a cube.

2. Walking Robot (20 Points)

First get your rendering engine ready to recursively traverse the scene graph for rendering by creating a root node of type Group and calling its draw() function with the identity matrix as its parameter.

The robot should have a torso, head, arms and legs. This means that the robot has to consist of at least 6 instances of Geode-derivatives. You can use the sphere and cube classes for the body parts, and add more shapes as you like (e.g., using any of GLUT's pre-defined shapes). Each Geode-derivative should have a MatrixTransform before it to position the body part(s) below it in the scene graph. You might want some of your basic shapes, such as spheres and cubes, elongated, rotated, or otherwise deformed, which you should do with separate MatrixTransform nodes for (non-uniform) scales, and/or rotations. Note that it is very common to concatenate multiple MatrixTransform nodes in a scene graph, each of which doing a separate affine transformation (e.g., one for position, one for scale, one to rotate). (15 points)

Animate the robot to make it look like it is walking: move arms and legs back and forth by rotating around hip and shoulder joints. You can do this by re-calculating rotation matrices every frame by increasing or decreasing the respective angle by a small amount, up to a limit point at which you reverse the direction. (5 points)

3. Culling (30 Points)

Add a bounding sphere (Vector3 for its center point, and a radius) to your Node class, and implement code to update the bounding box parameters in all other classes of your scene graph. You also need to add code to your Node class to display each node's bounding sphere as a wireframe sphere with glutWireSphere. Support the 'b' key to toggle these bounding spheres on and off. (10 points)

Note: You do not need to find the smallest possible bounding sphere, but you can approximate it:

• Find minimum and maximum extents of your geometry in x,y and z (bounding box).
• The center of the bounding sphere is the center of the bounding box.
• The radius of the bounding sphere is equal to half the diameter of the bounding box.

Extend the Node class to perform view frustum culling using the bounding spheres of the objects. If the bounding sphere of an object is completely outside of the view frustum, the object should be culled (not rendered). Your culling algorithm should make use of a utility function to test whether a bounding sphere intersects with a given plane, or whether the sphere is entirely on one side of the plane. (10 points)

Test your implementation by constructing a scene which consists of a sufficiently large amount of your robots to speed up rendering when object culling is used. (10 points)

• Create only one instance of your robot class, which you reference every time you render a robot. This saves a great deal of memory.

• Create a scene graph with two platoons of as many robots as it takes to render at around 20 fps. Distribute the robots of each platoon on a regular 2D grid.

• Choose the camera parameters so that many of the robots are located outside of the view frustum (off-screen), so that culling kicks in.

• Use your rotation and scale routines to allow the user to rotate the camera and zoom in and out.

• Compare the frame rates with and without object-level culling by supporting the keyboard key 'c' to toggle culling on and off, and displaying the rendering rate (frames per second) in the console window for every frame (frames_per_second = 1/rendering_time). Tweak the number of robots, their spatial density, and your camera parameters until your frame rate is noticeably higher with culling enabled.

Notes:

• All your robots need to be walking like in part 2. This means that you need to re-calculate the bounding spheres each frame, or use bounding spheres which contain the entire animation.
• For the calculation of the view frustum bounding planes you may want to take a look at the Lighthouse3D web site.

This image illustrates the grid layout of the robots:

4. Animation (20 Points)

Animate the robots and the platoons like in the above mentioned video. Your animation needs to consist of at least 4 turns and changes of direction of the robots. The platoons need to move in different directions at least once (i.e., they can't be walking synchronously all the time). Make the platoons interleave each other like in the video. It is not critical that there is no collision between them, we will deal with that in the extra credit section. The animation needs to be running automatically, so you will need a way to script it.

5. Extra Credit: Collision Detection (10 Points)

Implement a bounding sphere based collision detection algorithm and visually indicate when two or more robots collide. For example, you could draw the colliding robots' bounding spheres in red. Tweak the interleaving part of your animation so that the robots never intersect. Add a manual control mode to control the walking direction of each platoon independently so that you can force collisions. For instance, one platoon could be controlled with the WASD keys, the other with IJKL.