Revision as of 00:08, 1 November 2013

Project 5: Scene Graph

In this project you will need to implement a scene graph data structure and a view frustum culling algorithm.

This project is due on Friday, November 8th at 1:30pm and will be discussed in Center Hall 105 on Monday, November 4th at 3pm.

1. Scene Graph (60 points)

In this part of the project you will need to modify your renderer to use a scene graph data structure instead of a linear list of objects.

1a. Class Hierarchy (15 points)

Implement an abstract base class Node for nodes in the scene graph, and abstract subclasses Group and Geode as shown in the figure below. The Group class should store a list of pointers to child nodes and provide functionality to add and remove child nodes. Implement a subclass MatrixTransform of Group, and a geometry sub-class Sphere of Geode. MatrixTransform should store a transformation matrix that is applied to the subtree below the node, and Sphere should consist of a draw function which uses OpenGL code to create a sphere (or use glutSolidSphere).

Here is a picture of the scene graph class hierarchy you should implement:

1b. Rendering (15 points)

Modify the GLUT draw callback in your application to recursively traverse the scene graph for rendering. Each subclass of Node, e.g., Group, MatrixTransform and Geode, will need to have its own implementation of a draw method that is called recursively during scene graph traversal. See the lecture slides for more details on the recursive function for rendering the scene graph.

1c. Testing (30 points)

Demonstrate your scene graph functionality by constructing a walking robot. The robot should have a torso, a head, and arms and legs that consist of at least two parts each, for instance upper and lower arms or arm and hand. This means that the robot has to consist of at least 10 instances of Geode-derivatives. You can use simple shapes for the body parts, like boxes, spheres or cylinders. It may be helpful to sketch the scene graph on a piece of paper before you implement it. The root node should be a MatrixTransform for the position of the torso. It will have several children: a Geode node to represent the torso geometry, and several MatrixTransform nodes with attached Geode nodes to represent arms, legs and head. The arm and leg nodes each should have at least two Geode children of their own, representing for instance upper and lower arm. (20 points)

Animate the robot with at least 5 animation steps to make it look like it is walking: move the arms and legs back and forth by rotating around hip, shoulder, elbow and knee joints, and also move the head with respect to the torso. You can accomplish rotation by applying a rotation matrix to the transformation matrices of the MatrixTransform nodes in your scene graph. (10 points, one for each moving body part/limb)

Note: You can use GLUT's shape functions to make parts for the robot, such as glutSolidSphere, glutSolidCube, glutSolidCone, glutSolidTorus, or glutSolidTetrahedron.

2. Object-Level Culling with Bounding Spheres (40 points)

Add a method to your Geode class which computes and stores a bounding sphere for your robot. The bounding sphere should consist of a center point and a radius. (5 points)

Note: You do not need to find the minimal 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 Geode 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 slow down rendering when object culling is not 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 mouse control routines to allow the user to rotate the grid of 3D objects (5 points). Compare the frame rates with and without object-level culling by supporting the keyboard keys 'c' for culling and 'n' for no culling, and displaying the rendering rate (frames per second) in the console window once every second (5 points). Tweak the number of robots, their spatial density, and your camera parameters until your frame rate is noticeably higher with culling enabled. (5 points)

Note: In this exercise the robots do not need to be walking. If you want them to walk, you need to calculate bounding spheres which contain the geometry of all steps of the animation.

This image illustrates the grid layout of the robots:

3. 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). Demonstrate this functionality by attaching the flashlight to your robot's hand, pointing forward (4 points). Create a rectangular room with three walls (open on the side facing the viewer) and a floor (2 points) for your robot to walk around in, with the flashlight's light cone moving along walls and floor (2 points). The robot can walk up and down the room along a wall, or walk around in a circle, or any other path of your choice (2 points).

Note: In order to get the light spot on the walls to render correctly as a sphere or oval, your walls need to be built out of thousands of triangles or quads, unless you want to create a pixel shader for Phong shading.