Page 5: Hierarchy

CS559 Spring 2021 Sample Solution - Workbook 3

Written by CS559 course staff

You can try out the example solutions here. The interesting code is on page 6 and page 8.

Box 1: Arms and Legs

Here’s a little more complete version of the arm example:

This has so many parameters (one for the “root” position x,y and one for each angle) that the sliders are made with a loop! Try it out and see how each joint is connected to a slider. The code can be found in 03-05-01.html and 03-05-01.js.

The place to focus on is the drawBody function (in 03-05-01.js). It takes the parameters for the rotations and root positions, and draws the hierarchical figure.

In this example, notice how some parts (the body) have multiple parts inside of them. Our hierarchical model is a tree. For the stick figure, the “root” is the body, which has 4 sub parts (the four limbs).

If you look carefully, you will notice that the arms are actually the same code repeated (with a changed coordinate system by scaling the X axis to make it go the other direction). We could have made the two arms the same (they are instances).

Because we can have instances (the same part used by multiple “parent” parts), hierarchical models are usually thought of as directed acyclic graphs (or DAGs). A DAG is the generalization of a display list. We discussed display lists in the previous workbook. A common term for a DAG that represents a hierarchical model is a scene graph.

Most retained mode APIs (including SVG and THREE.js, which we will use later in the class) support representing models as scene graphs. In Canvas, because it is immediate mode, we either need to represent the graph in our own data structures, or represent the graph implicitly in code. The latter is what the drawBody function does: you can see the hierarchy of parts, but we never create any data structures to represent them.

More on Save and Restore

Hopefully, you noticed that we can do many saves and restores. When we restore, we get back to the most recent save. When we restore again, we go back to the save before that.

We usually think about saving and restoring as a stack. Save pushes a copy of the current context onto the stack. Restore pops a context off the top of the stack and makes it the current context.

An alternative way to think about this is that the “current context” (the one that we are using) is the context at the top of the stack. Save makes a copy of the current context and pushes it onto the top of the stack (so we start using that copy), while restore pops the top element off the stack and discards it (so the “current context” is now the element that is newly exposed on top of the stack). This is how many systems actually implement the “context stacks”.

In Canvas, we call these operations save and restore and they act on a context. Many other immediate mode graphics systems have similar operations with a stack of contexts. Often the save operation is called push and the restore operation is called pop (which makes sense given what they do). Because the most important piece of context we save is the current coordinate system (or transformation), the stack of contexts is sometimes called a matrix stack because transformations are represented as matrices.

All that is relevant because (1) you need to understand the concept of the stack; and (2) when you read code (or books) written for something other than Canvas, you will see stack terminology.

Chapter 7 of Hart’s “Big Fun Book of Computer Graphics” Hart07-jan19.pdf (14.5mb) discusses hierarchical modeling - it gives a very similar example. The second example is in 3D, so it may not make as much sense yet. He explains things using a different API - but it should seem familiar since it is similar.

Summary: Hierarchical Models

Hopefully, you have gotten the idea of how we use hierarchical modeling to put complicated objects together. Next week, we’ll learn about how transformations are implemented using linear algebra. But for now, we’ll give you a chance to make some models on your own on the next page.

Next: Quadcopter Exercise

There are no points associated with this page.