CS 370: Lab 16: Scene Graphs

Now that we have completed our study of geometry and lighting, both which utilize the vertex processor, we will explore a nice way to organize the objects into our scene, particularly those that have a direct relationship to each other. For example, the position of your hand is related to the position of your arm which is related to the position of your body. Thus rather than having to continually recompute the absolute position of each part, we would like to create a mechanism for simply keeping track of the relative positioning of each part with respect to the other parts. Therefore, when one part moves, e.g. your body, those parts connected to it will automatically move with it. We could do this using glPushMatrix( ) and glPopMatrix( ) calls, but a more systematic way is by constructing a tree structure known as a scene graph. In the scene graph, every object will become a node which will contain the local transformations for that particular object as well as the necessary rendering routine. The tree then provides a convenient mechanism for preserving the transformations from level to level, hence objects that are related will have the same transformations applied to them automatically. Once the tree has been constructed, rendering the scene is simply a matter of traversing the tree using a depth first approach (actually any part of the tree can likewise be rendered by starting at the desired node). Also note that in this lab we will employ multiple shaders such that some objects can be illuminated by lighting while others can simply use set colors.

0. Getting Started

Download CS370_Lab16.zip, saving it into the labs directory.

Double-click on CS370_Lab16.zip and extract the contents of the archive into a subdirectory called CS370_Lab16

Navigate into the CS370_Lab16 directory and double-click on CS370_Lab16.sln (the file with the little Visual Studio icon with the 12 on it).

If the source file is not already open in the main window, open the source file by expanding the Source Files item in the Solution Explorer window and double-clicking treeRobot.cpp.

1. Scene Graph Nodes

For the tree structure we will be using, each node will contain fields as shown below:

struct treenode {
	MaterialType material;
	GLfloat color[4];
	GLuint texture;
	void (*f)();
	GLfloat m[16];
	treenode *sibling;
	treenode *child;
	GLuint shaderProg;
};

where material is the material structure (if the object uses lighting), color (if the object uses direct color), texture is the texture map index (if the object uses textures), f is a pointer to a function for rendering the object, m[ ] is a local transformation matrix array, sibling is a pointer to a single sibling node of the tree, child is a pointer to a single child node of the tree, and shaderProg is the shader program to use to render the object. Thus children will be objects connected to the current one while siblings are ones connected to the same parent as the current object. For efficient rendering, we will pre-compute the entire local transformation and store it into the m[ ] matrix within the node structure. Additional fields can be added to the structure to further expand the capabilities of the scene graph.

For this lab we will be constructing a simple robot with a circular base, a single lower arm, and two upper arms.

image

The scene graph is given pictorially as

image

Note: Whenever a node does not have a child or sibling, its corresponding field should be set to NULL. A more general technique would be to dynamically allocate nodes as needed, i.e. similar to maintaining a linked-list, when the number of objects in the scene is variable (e.g. projectiles). This paradigm also fits nicely within an object oriented framework and is fundamental for graphic API’s such as Java3D.

So for example the base node (assuming it is called base with draw function draw_base( ) and the lower arm node named lower_arm) would be created as follows (note the pointer to a function is simply the function’s name and we use the update_base( ) function to set the m field)

base.material = brass;          	// Set material
base.f = draw_base;         		// Set drawing function
base.sibling = NULL;            	// Set sibling node
base.child = &lower_arm;        	// Set child node
base.shaderProg = lightShaderProg;  // Set shader program (for lighting)
update_base();              		// Set initial transformation matrix

Tasks

NOTE: Notice that in the draw functions for each piece, the transformations are only to create the shape of the object and locate the center of it appropriately with respect to the world origin, i.e. the lower arm is drawn so its base is on the x-z plane, etc. The actual absolute position will be determined by the transformations in the scene graph nodes. Hence objects that have the same shape and color, e.g. the left and right upper arms, can be drawn with the same rendering routine.

2. Local Transformation Update Functions

Once we have created the tree structure by setting the various node fields, we need to compute the local transformation matrices for each piece to locate it relative to its parent. Fortunately we can use OpenGL to do this computation by applying the individual translation, rotation, and scalings as we have done before, but now we will retrieve and store the net matrix into the m[] array within the node. We can retrieve the current modelview matrix using the command

glGetFloatv(GL_MODELVIEW_MATRIX, m);

where m is the pointer to the array we wish to store the matrix values into. Hence typically we will issue a glLoadIdentity() first, then apply our desired local transformations, and then get the resulting transformation matrix using glGetFloatv( ).

NOTE: DO NOT forget to call the update function whenever the local transformation matrices change, e.g. during animation.

Tasks

3. Rendering the Scene Graph

Finally we can render the scene by simply traversing the tree in a depth-first fashion starting at a root node. One traversal routine traverse( ) is given by

void traverse(treenode *node)
{
	// Stop when at bottom of branch
	if (node == NULL) 
	{
		return;
	}

	// Apply local transformation and render
	glPushMatrix();
	glMultMatrixf(node->m);
	glUseProgram(node->shaderProg);
	node->f();

	// Recurse vertically if possible (depth-first)
	if (node->child != NULL)
	{
		traverse(node->child);
	}

	// Remove local transformation and recurse horizontal
	glPopMatrix();
	if (node->sibling != NULL)
	{
		traverse(node->sibling);
	}
}

Note that we take advantage of the matrix stack via glPushMatrix( ) and glPopMatrix( ) throughout the traversal to augment as we proceed down the tree and resetting it when we move across the tree. We also activate the appropriate shader program prior to rendering each node (which also means that in the drawing function we will need to set any necessary shader variables).

Tasks

Compiling and running the program

Once you have completed typing in the code, you can build and run the program in one of two ways:

(On Linux/OSX: In a terminal window, navigate to the directory containing the source file and simply type make. To run the program type ./treeRobot.exe)

The output should look similar to below

image

To quit the program simply close the window.

Scene graphs provide a convenient framework for organizing the geometry of our scenes. However, to further enhance the visual effect we need to move to the fragment (or pixel) shader in order to manipulate the final colors. In this stage of the pipeline, we can create transparency effects through alpha blending and apply images to our scenes through billboarding and texture mapping.

Copyright (c) 2007-2016 | Unless indicated otherwise, content is freely-redistributable | Creative Commons License