Latest revision as of 11:52, 14 November 2014

Project 4: Scene Graph

In this project you will need to implement a scene graph data structure and a view frustum culling algorithm for it. You should start out with your code for project 2 -- we will no longer do the rasterization ourselves from this point on.

This project is due on Friday, November 14th at 3:30pm and will be discussed in CSB 001 on Monday, November 10th at 5pm.

1. Class Hierarchy (30 points)

Implement scene graph classes with the following hierarchy:

The classes should have at least the following functionality (5 points for each class):

• 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.
• Cube should have a draw function which draws a cube. You can use glutSolidCube for that.

2. Walking Robot (30 Points)

Demonstrate your scene graph functionality by constructing a walking robot.

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). (20 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. (10 points)

3. Object-Level Culling (40 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 can use an approach similar to the one in homework assignment 2:

• 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.

• Distribute the robots on a 2D grid (i.e., place them on a plane with uniform spacing). (5 points)

• Choose the camera parameters so that many of the robots are located outside of the view frustum (off-screen), so that object-level culling matters. (5 points)

• Use your rotation and scale routines to allow the user to rotate the grid of 3D objects and zoom in or out. (5 points)

• 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. (5 points)

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.
• 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. Extra Credit: Robot with Flashlight (10 points)

Implement a scene graph node class for a light source (Light), which implements an OpenGL spot light (flashlight). Attach the Light node to your robot's hand via the scene graph. In this exercise you should only have one robot walking around (not the entire army). (5 points)

Create a rectangular room with three walls (open on the side facing the viewer) and a floor for your robot to walk around in a circle, with the flashlight's light cone moving along walls and floor. In order for the light spot on the walls to render as a nice oval, your walls need to be built out of thousands of triangles or quads. For this purpose, create a new node type derived from Geode, which takes in a tessellation parameter to control the number of primitives. (5 points)