6.

837 Computer Graphics

Hierarchical Modeling
Wojciech Matusik, MIT EECS
Some slides from BarbCutler &
Jaakko Lehtinen

Image courtesy of BrokenSphere on Wikimedia Commons. License: CC-BY-SA. This content is excluded
from our Creative Commons license. For more information, see [Link]

1
1
Recap
• Vectors can be expressed in a basis
• Keep track of basis with left notation
• Change basis
• Points can be expressed in a frame
(origin+basis)
• Keep track of frame with left notation
• adds a dummy 4th coordinate always 1

2
Frames & transformations
• Transformation S wrt car frame f

• how is the world frame a affected by this?

• we have
• which gives

• i.e. the transformation in a is A-1SA

• i.e., from right to left, A takes us from a to f, then
we apply S, then we go back to a with A-1
3
Homogeneous Visualization
• Divide by w to normalize (project)
• w = 0?

(0,0,0)

(0, 0, 1) = (0, 0, 2) = … w=1

(7, 1, 1) = (14, 2, 2) = …
(4, 5, 1) = (8, 10, 2) = … w=2

4
Different objects
• Points
• represent locations
• Vectors
• represent movement, force, displacement from A to B
• Normals
• represent orientation, unit length
• Coordinates
• numerical representation of the above objects
in a given coordinate system

5
Normal
• Surface Normal: unit vector that is locally
perpendicular to the surface

6
Why is the Normal important?
• It's used for shading — makes things look 3D!

object color only Diffuse Shading

7
Visualization of Surface Normal

± x = Red
± y = Green
± z = Blue

8
How do we transform normals?

nWS

nOS

Object Space World Space

9
Transform Normal like Object?

• translation?
• rotation?
• isotropic scale?
• scale?
• reflection?
• shear?
• perspective?

10
Transform Normal like Object?
• translation?
• rotation?
• isotropic scale?
• scale?
• reflection?
• shear?
• perspective?

11
Transformation for shear and scale

Incorrect
Normal
Transformation

Correct
Normal
Transformation

12
More Normal Visualizations

Incorrect Normal Transformation Correct Normal Transformation

13
So how do we do it right?
• Think about transforming the tangent plane
to the normal, not the normal vector
nOS nWS

vOS vWS
Original Incorrect Correct

Pick any vector vOS in the tangent plane,

how is it transformed by matrix M?
vWS = M v OS

14
Transform tangent vector v
v is perpendicular to normal n:
Dot product n ᵀv = 0 OSʿ OS
nOS
n ᵀ (M ̄ ¹ M) v = 0
OS OS

(n ᵀ M ̄ ¹) (M v ) = 0
OS OS
vOS
(n ᵀ M ̄ ¹) v = 0
OS WS

v is perpendicular to normal n :
WS WS

nWS n ᵀ = n ᵀ (M ̄ ¹)
WS OS

n = (M ̄ ¹)ᵀ n
WS OS

vWS n ᵀv = 0
WS WS

15
Digression
n = (M¯¹)ᵀ n
WS OS

• The previous proof is not quite rigorous; first

you’d need to prove that tangents indeed
transform with M.
- Turns out they do, but we’ll take it on faith here.
- If you believe that, then the above formula follows.

16
Comment
• So the correct way to transform normals is:
n = (M¯¹)ᵀ n
WS OS Sometimes denoted M¯ᵀ

• But why did n = M n work for similitudes?

WS OS

• Because for similitude / similarity transforms,

(M¯¹)ᵀ =λ M
• e.g. for orthonormal basis:

M¯¹ = M ᵀ i.e. (M¯¹)ᵀ = M

17
Connections
• Not part of class, but cool
• “Covariant”: transformed by the matrix
• e.g., tangent
• “Contravariant”: transformed by the inverse transpose
• e.g., the normal
• a normal is a “co-vector”

• Google “differential geometry” to find out more

18
• Further Reading
–Buss, Chapter 2

• Other Cool Stuff

–Algebraic Groups
–[Link]
–[Link]
–Free-form deformation of solid objects
–Harmonic coordinates for character articulation

19
Question?

20
Hierarchical Modeling
• Triangles, parametric curves and surfaces
are the building blocks from which more
complex real-world objects are modeled.

• Hierarchical modeling creates complex real-

world objects by combining simple primitive
shapes into more complex aggregate
objects.

Image courtesy of Nostalgic dave on Wikimedia Commons. License: CC-BY-SA. This content is excluded
from our Creative Commons license. For more information, see [Link]
21
Hierarchical models

Image courtesy of David Bařina, Kamil Dudka, Jakub Filák, Lukáš Hefka on Wikimedia Commons. License: CC-BY-SA. This
content is excluded from our Creative Commons license. For more information, see [Link] 22
Hierarchical models

Image courtesy of David Bařina, Kamil Dudka, Jakub Filák, Lukáš Hefka on Wikimedia Commons. License: CC-BY-SA. This
23
content is excluded from our Creative Commons license. For more information, see [Link]
Hierarchical models

Image courtesy of David Bařina, Kamil Dudka, Jakub Filák, Lukáš Hefka on Wikimedia Commons. License: CC-BY-SA. This
content is excluded from our Creative Commons license. For more information, see [Link] 24
Hierarchical models

Image courtesy of David Bařina, Kamil Dudka, Jakub Filák, Lukáš Hefka on Wikimedia Commons. License: CC-BY-SA. This
content is excluded from our Creative Commons license. For more information, see [Link] 25
Hierarchical models

Image courtesy of David Bařina, Kamil Dudka, Jakub Filák, Lukáš Hefka on Wikimedia Commons. License: CC-BY-SA. This
content is excluded from our Creative Commons license. For more information, see [Link] 26
Hierarchical models

Image courtesy of David Bařina, Kamil Dudka, Jakub Filák, Lukáš Hefka on Wikimedia Commons. License: CC-BY-SA. This
content is excluded from our Creative Commons license. For more information, see [Link]
27
Hierarchical Grouping of Objects
• The “scene graph” represents
the logical organization of scene
scene

chair table ground

table fruits

6.837 - Durand 28
Scene Graph
• Convenient Data structure
for scene representation
• Geometry (meshes, etc.)
• Transformations
• Materials, color
• Multiple instances Image courtesy of David Bařina, Kamil Dudka, Jakub Filák, Lukáš Hefkaon Wikimedia Commons.
License: CC-BY-SA. Thiscontent is excluded from our Creative Commons license.
For more information, see [Link]

• Basic idea: Hierarchical Tree

• Useful for manipulation/animation
• Also for articulated figures
• Useful for rendering, too
• Ray tracing acceleration,
occlusion culling
• But note that two things that are close to This image is in the public domain.

each other in the tree are NOT necessarily Source: Wikimedia Commons.

spatially near each other 29

Scene Graph Representation
• Basic idea: Tree
• Comprised of several node types
• Shape: 3D geometric objects
• Transform: Affect current transformation
• Property: Color, texture
• Group: Collection of subgraphs

• C++ implementation
• base class Object
• children, parent
• derived classes for each
node type (group, transform)

30
 Scene Graph Representation
• In fact, generalization of a tree: Directed Acyclic Graph (DAG)
• Means a node can have multiple parents, but cycles are not allowed
• Why? Allows multiple instantiations
• Reuse complex hierarchies many times in the scene using different
transformations (example: a tree)
• Of course, if you only want to reuse meshes, just load the mesh once and make
several geometry nodes point to the same data

Group

Trsfrm Trsfrm Trsfrm Trsfrm

Group

31
 Simple Example with Groups
Group {
numObjects 3
Group {
numObjects 3
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
numObjects 2
Group {
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
Box { <BOX PARAMS> }
Sphere { <SPHERE PARAMS> }
Sphere { <SPHERE PARAMS> } } }
Plane { <PLANE PARAMS> } }

Text format is fictitious, better to use XML in real applications

6.837 - Durand 32
 Simple Example with Groups
Group {
numObjects 3
Group {
numObjects 3
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
numObjects 2
Group {
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
Box { <BOX PARAMS> }
Sphere { <SPHERE PARAMS> }
Sphere { <SPHERE PARAMS> } } }
Plane { <PLANE PARAMS> } }

Text format is fictitious, better to use XML in real applications

6.837 - Durand 33
 Simple Example with Groups
Group {
numObjects 3
Group {
numObjects 3
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
numObjects 2
Group {
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
Box { <BOX PARAMS> }
Sphere { <SPHERE PARAMS> }
Sphere { <SPHERE PARAMS> } } }
Plane { <PLANE PARAMS> } }

Here we have only simple shapes, but easy to add a “Mesh”

node whose parameters specify an .OBJ to load (say)
6.837 - Durand 34
 Adding Attributes (Material, etc.)
Group {
numObjects 3
Material { <BLUE> }
Group {
numObjects 3
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
numObjects 2
Material { <BROWN> }
Group {
Box { <BOX PARAMS> }
Box { <BOX PARAMS> }
Box { <BOX PARAMS> } }
Group {
Material { <GREEN> }
Box { <BOX PARAMS> }
Material { <RED> }
Sphere { <SPHERE PARAMS> }
Material { <ORANGE> }
Sphere { <SPHERE PARAMS> } } }
Material { <BLACK> }
Plane { <PLANE PARAMS> } }

35
Adding Transformations

36
Questions?

37
Scene Graph Traversal
• Depth first recursion
• Visit node, then visit subtrees (top to bottom, left to right)
• When visiting a geometry node: Draw it!

• How to handle transformations?

• Remember, transformations are always specified
in coordinate system of the parent

38
Scene Graph Traversal
• How to handle transformations?
• Traversal algorithm keeps a transformation state S (a 4x4 matrix)
• from world coordinates
• Initialized to identity in the beginning
• Geometry nodes always drawn using current S
• When visiting a transformation node T:
multiply current state S with T,
then visit child nodes
• Has the effect that nodes below
will have new transformation
• When all children have been
visited, undo the effect of T!

39
Recall frames
• An object frame has coordinates O in the world
(of course O is also our 4x4 matrix)

• Then we are given coordinates c in the object frame

• Indeed we need to apply matrix O to all objects

40
Frames and hierarchy
• Matrix M1 to go from world to torso
• Matrix M2 to go from torso to arm

• How do you go from arm coordinates to world?

• We can concatenate the matrices

• Matrices for the lower hierarchy nodes go to the right

41
Recap: Scene Graph Traversal
• How to handle transformations?
• Traversal algorithm keeps a transformation state S (a 4x4 matrix)
• from world coordinates
• Initialized to identity in the beginning
• Geometry nodes always drawn using current S
• When visiting a transformation node T:
multiply current state S with T,
then visit child nodes
• Has the effect that nodes below
will have new transformation
• When all children have been
visited, undo the effect of T!

42
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit)

43
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S=I

44
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1

45
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1

46
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1 T2

47
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1 T2

48
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1 T2

49
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1

50
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1 R1

51
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1 R1

52
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1 R1

53
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1

54
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1

55
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S=I

56
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = R2

57
 Traversal Example

Root

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = R2

58
 Traversal Example

Root

Translate T1 Rotate R2

.....
Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = R2

59
 Traversal Example

Root At each node, the current object-to-world transformation is the

matrix product of all transformations found on the way from the
node to the root.

Translate T1 Rotate R2

Group Group
(table, fruits) (chair, legs)

Translate T2 Rotate R1

Group Group
(tabletop, legs) (basket, fruit) S = T1R1

60
Traversal State
• The state is updated during traversal
• Transformations
• But also other properties (color, etc.)
• Apply when entering node, “undo” when leaving

• How to implement?
• Bad idea to undo transformation by inverse matrix (Why?)

61
Traversal State
• The state is updated during traversal
• Transformations
• But also other properties (color, etc.)
• Apply when entering node, “undo” when leaving

• How to implement?
• Bad idea to undo transformation by inverse matrix
• Why I? T*T-1 = I does not necessarily hold in floating point even
when T is an invertible matrix – you accumulate error
• Why II? T might be singular, e.g., could flatten a 3D object onto a
plane – no way to undo, inverse doesn’t exist!

62
Traversal State
• The state is updated during traversal
• Transformations
• But also other properties (color, etc.)
• Apply when entering node, “undo” when leaving

• How to implement?
• Bad idea to undo transformation by inverse matrix
• Why I? T*T-1 = I does not necessarily hold in floating point even
when T is an invertible matrix – you accumulate error
• Why II? T might be singular, e.g., could flatten a 3D object onto a
plane – no way to undo, inverse doesn’t exist!

Can you think of a data structure suited for this?

63
Traversal State – Stack
• The state is updated during traversal
• Transformations
• But also other properties (color, etc.)
• Apply when entering node, “undo” when leaving

• How to implement?
• Bad idea to undo transformation by inverse matrix
• Why I? T*T-1 = I does not necessarily hold in floating point even
when T is an invertible matrix – you accumulate error
• Why II? T might be singular, e.g., could flatten a 3D object onto a
plane – no way to undo, inverse doesn’t exist!

• Solution: Keep state variables in a stack

• Push current state when entering node, update current state
• Pop stack when leaving state-changing node
• See what the stack looks like in the previous example! 64
Questions?

65
Plan
• Hierarchical Modeling, Scene Graph
• OpenGL matrix stack
• Hierarchical modeling and animation of characters
• Forward and inverse kinematics

66
Hierarchical Modeling in OpenGL
• The OpenGL Matrix Stack implements what we just did!

• Commands to change current transformation

• glTranslate, glScale, etc.
• Current transformation is part of the OpenGL state, i.e., all
following draw calls will undergo the new transformation
• Remember, a transform affects the whole subtree
• Functions to maintain a matrix stack
• glPushMatrix, glPopMatrix
• Separate stacks for modelview (object-to-view)
and projection matrices

67
When You Encounter a Transform Node
• Push the current transform using glPushMatrix()
• Multiply current transform by node’s transformation
• Use glMultMatrix(), glTranslate(), glRotate(), glScale(), etc.
• Traverse the subtree
• Issue draw calls for geometry nodes
• Use glPopMatrix() when done.

• Simple as that!

68
More Specifically...
• An OpenGL transformation call corresponds to a matrix T
• The call multiplies current modelview matrix C by T from the
right, i.e. C’ = C * T.
• This also works for projection, but you often set it up only once.

• This means that the transformation for the subsequent

vertices will be p’ = C * T * p
• Vertices are column vectors on the right in OpenGL
• This implements hierarchical transformation directly!

69
More Specifically...
• An OpenGL transformation call corresponds to a matrix T
• The call multiplies current modelview matrix C by T from the
right, i.e. C’ = C * T.
• This also works for projection, but you often set it up only once.

• This means that the transformation for the subsequent

vertices will be p’ = C * T * p
• Vertices are column vectors on the right in OpenGL
• This implements hierarchical transformation directly!

• At the beginning of the frame, initialize the current matrix by

the viewing transform that maps from world space to view
space.
• For instance, glLoadIdentity() followed by gluLookAt()
70
Questions?
• Further reading on OpenGL
Matrix Stack and hierarchical model/view transforms
• [Link]

• It can be a little confusing if you don’t think the previous

through, but it’s really quite simple in the end.
• I know very capable people who after 15 years of experience still
resort to brute force (trying all the combinations) for getting their
transformations right, but it’s such a waste :)

71
Plan
• Hierarchical Modeling, Scene Graph
• OpenGL matrix stack
• Hierarchical modeling and animation of characters
• Forward and inverse kinematics

72
Animation
• Hierarchical structure is essential for
animation
• Eyes move with head
• Hands move with arms
• Feet move with legs
• …

• Without such structure the model falls apart.

73
Articulated Models
• Articulated models are rigid parts connected by joints
• each joint has some angular degrees of freedom

• Articulated models can be animated by specifying the joint

angles as functions of time.

74
Joints and bones
• Describes the positions of the
body parts as a function of joint angles.
• Body parts are usually called “bones”

• Each joint is characterized by its degrees of freedom (dof)

• Usually rotation for articulated bodies

1 DOF: knee 2 DOF: wrist 3 DOF: arm

75
 Skeleton Hierarchy
• Each bone position/orientation described
relative to the parent in the hierarchy: For the root, the
parameters
include a position
hips
as well
left-leg
...
r-thigh

Joints are r-calf

y
specified by
angles. vs
x r-foot
z

76
Draw by Traversing a Tree
hips glLoadIdentity();
glPushMatrix();
left-leg
... glTranslatef(…);
r-thigh glRotate(…);
drawHips();
glPushMatrix();
glTranslate(…);
r-calf
glRotate(…);
drawThigh();
glTranslate(…);
r-foot glRotate(…);
drawCalf();
glTranslate(…);
• Assumes drawing procedures glRotate(…);
for thigh, calf, and foot use drawFoot();
glPopMatrix();
joint positions as the origin for left-leg
a drawing coordinate frame

77
Forward Kinematics

vs How to determine the world-space

position for point vs?

78
Forward Kinematics

Transformation matrix S for a point vs is a matrix

composition of all joint transformations between
the point and the root of the hierarchy. S is a
function of all the joint angles between here and
root.

vs

79
Forward Kinematics

Transformation matrix S for a point vs is a matrix

composition of all joint transformations between
the point and the root of the hierarchy. S is a
function of all the joint angles between here and
root.
Note that the angles have a non-linear effect.

vs
This product is S

80
Forward Kinematics

Transformation matrix S for a point vs is a matrix

composition of all joint transformations between
the point and the root of the hierarchy. S is a
function of all the joint angles between here and
root.
Note that the angles have a non-linear effect.

vs
This product is S

parameter vector p
6.837 - Durand 81
Questions?

82
Inverse Kinematics
• Context: an animator wants to “pose” a character
• Specifying every single angle is tedious and not intuitive
• Simpler interface:
directly manipulate position of e.g. hands and feet
• That is, specify vw, infer joint transformations

vs

83
Inverse Kinematics
• Forward Kinematics
• Given the skeleton parameters p (position of the root and the joint
angles) and the position of the point in local coordinates vs, what is
the position of the point in the world coordinates vw?
• Not too hard, just apply transform accumulated from the root.

vs

84
Inverse Kinematics
• Forward Kinematics
• Given the skeleton parameters p (position of the root and the joint
angles) and the position of the point in local coordinates vs, what is
the position of the point in the world coordinates vw?
• Not too hard, just apply transform accumulated from the root.

• Inverse Kinematics
• Given the current position of the point
and the desired new position in
world coordinates, what are the skeleton
parameters p that take the point to the vs
desired position?
ṽw

85
Inverse Kinematics
• Given the position of the point in local coordinates vs and
the desired position in world coordinates, what are the
skeleton parameters p?

ṽw
skeleton parameter vector p

• Requires solving for p, given vs and

• Non-linear and …

86
It’s Underconstrained
• Count degrees of freedom:
• We specify one 3D point (3 equations)
• We usually need more than 3 angles
• p usually has tens of dimensions vs

• Simple geometric example (in 3D):

specify hand position, need elbow & shoulder
• The set of possible elbow location is a circle in 3D

87
How to tackle these problems?
• Deal with non-linearity:
Iterative solution (steepest descent)
• Compute Jacobian matrix of world position w.r.t. angles
• Jacobian: “If the parameters p change by tiny amounts, what is the resulting
change in the world position vWS?”
• Then invert Jacobian.
• This says “if vWS changes by a tiny amount, what is the change in the
parameters p?”
• But wait! The Jacobian is non-invertible (3xN)
• Deal with ill-posedness: Pseudo-inverse
• Solution that displaces things the least
• See [Link]
• Deal with ill-posedness: Prior on “good pose” (more advanced)
• Additional potential issues: bounds on joint angles, etc.
• Do not want elbows to bend past 90 degrees, etc.

88
Example: Style-Based IK
• Video

• Prior on “good pose”

• Link to paper: Grochow, Martin, Hertzmann, Popovic: Style-Based

Inverse Kinematics, ACM SIGGRAPH 2004

89
Mesh-Based Inverse Kinematics
• Video

• Doesn’t even need a hierarchy or skeleton: Figure proper

transformations out based on a few example deformations!

• Link to paper:
Sumner, Zwicker, Gotsman, Popovic: Mesh-Based Inverse Kinematics,
ACM SIGGRAPH 2005

90
That’s All for Today!
Further reading
 OpenGL Matrix Stack and
hierarchical model/view transforms
 [Link]
[Link]

Image courtesy of BrokenSphere on Wikimedia Commons. License: CC-BY-SA. This content is excluded
from our Creative Commons license. For more information, see [Link]
91
MIT OpenCourseWare
[Link]

6.837 Computer Graphics

Fall 2012

For information about citing these materials or our Terms of Use, visit: [Link]