Moving Remy in Harmony: Pixar's Use of Harmonic Functions
Posted March 2010.
This article will describe some new mathematical techniques being tested at Pixar for use in upcoming films...
David Austin
Grand Valley State University
austind at gvsu.edu
The rat in the cage
To make an engaging animated film, you need characters, like Remy from Pixar Animation Studio's Ratatouille, that are lovable with loads of personality

© Disney/Pixar 
and the ability to move them in ways that are both believable and interesting.

© Disney/Pixar 
While there are many mathematical issues that show up in computer animation, this article will describe some new mathematical techniques being tested at Pixar for use in upcoming films. In particular, we'll see how harmonic functions give life to animated characters by enabling their movement and expression of emotion.
Animated characters are usually constructed from a grid of points with a means to interpolate between the grid points and produce a natural, smooth appearance. On the character shown below can be seen some of the 8019 points forming the curvilinear rectangular grid on the character's body:

© Disney/Pixar 
When we want to make the character move, we then need to move each of the 8019 points in the grid. This sounds like a daunting task: not only does the location of each point need to be modified, but the motion of nearby points needs to be coordinated to create the illusion of a realistic solid body.
Consequently, animators may place the character inside a "cage," a coarser grid of control points containing the character. For instance, the character above is shown contained in a cage of 112 points.

© Disney/Pixar 
To move the character, we would like to move the relatively small number of control points defining the cage and have the points inside respond in some natural way. For instance, to make the character's arm bend, we could just move the relatively small number of points on the cage as shown below.


© Disney/Pixar 
© Disney/Pixar 
To give a more familiar example, the surface of Remy's body is defined by 9775 points while his cage has 325 control points.

© Disney/Pixar 
In fact, we may give greater expressive control by placing smaller cages of control points around special features, such as Woody's eye:

© Disney/Pixar 
This raises an important question that must be addressed: when one of the control points on the cage moves, how should the interior points move in response? This article will describe two new ways to approach this question.
Barycentric coordinates
Let's first look at a simpler situation.
Here's a character (lovable with loads of personality, right?)


that we place inside a triangular cage defined by control points v_{1}, v_{2} and v_{3}.


How should the character's points respond to the movement of control points? For instance, what should happen to the points on the interior circle when we move v_{i} → v'_{i}?
Barycentric coordinates, which we will now describe, give a pleasing solution to this problem. We define the linear function
β_{1}(x, y) = ax + by + c
by declaring
β_{1}(v_{1}) = 1
β_{1}(v_{2}) = 0
β_{1}(v_{3}) = 0
Since linear functions on the plane are determined by their values at three noncollinear points, this is enough information to determine β_{1} uniquely. The values of the function inside the cage may be represented graphically as a shade of blue as shown below. Pure blue represents 1 while black represents 0.
In the same way, we may define functions β_{2 }and β_{3}.


β_{2} 
β_{3} 
These functions, β_{1}, β_{2}, and β_{3}, are called barycentric coordinates, and satisfy some pleasant properties, the most important of which is this:
If p is a point in the interior of the triangle, then
p = Σ_{i} β_{i}(p) v_{i}.


This may be understood easily enough: since both sides of the expression are linear functions in p and agree at the three vertices of the triangle v_{i}, they must agree everywhere.
The idea is that we may use the functions β_{i} as a set of coordinates to locate points in the triangle, as shown below:
To understand this by analogy, imagine creating a custom color at the paint store by mixing together various shades of red, blue, and yellow. The barycentric coordinates β_{i}(p) specify how much of the three "colors" v_{i} to mix together to obtain the "color" p.
Now when we move the control points of the cage, we move the interior points so that they have the same barycentric coordinates in the new cage:
p = Σ_{i} β_{i}(p) v_{i} → p' = Σ_{i} β_{i}(p) v'_{i}

is moved to


If we now want to move our simple character, we let each interior point respond to the motion of the control points:

is moved to


Barycentric coordinates have useful properties that we note:
 Linear reproduction: at every point p, we have Σ_{i} β_{i}(p) v_{i} = p. This says, simply enough, that the coordinates β_{i}(p) locate a point in the cage in terms of the control points.
 Interpolation: β_{i}(v_{j}) = 1 if i = j and 0 if not. To continue our paint store analogy, this says that to obtain, say, pure red, we need use only pure red paint.
 Smoothness: the coordinates vary smoothly so that when we move the control points, nearby interior points move in concert.
 Affine invariance: at every point p, we have Σ_{i} β_{i}(p) = 1. It is straightforward to see that this property implies the following: if we apply an affine transformation to the points on the cage, then the interior points are moved by the same affine transformation. This is useful because affine transformations include simple geometric operations such as translations, rotations, reflections, and scalings.
Let's briefly consider the computational aspects of this process. Given the initial cage, the coordinates of each of the interior points need to be computed. This process is called binding, and it requires the most significant computational effort, at least in the methods that will be described shortly. To compute the new location of interior points when the control points are moved is much less work since we simply compute a linear combination of the control points. In other words, once the computation required for binding is completed up front, creating new frames of our movie is relatively straightforward. (This statement, of course, ignores all other computational aspects of creating a new frame, which we are not discussing here.)
Barycentric coordinates work with triangular cages. However, we would like to be able to work with more that just three control points. For instance, we may have the following character inside a cage.

© Disney/Pixar 
How can we generalize barycentric coordinates to cages with a richer geometric structure? We will consider two methods, mean value coordinates and harmonic coordinates, that are currently being tested.
Mean value coordinates
The first type of coordinates we'll consider, mean value coordinates, were first introduced by Floater and then applied to character articulation by Ju, Schaefer, and Warren.
Let's remember our goal: given a cage defined by vertices v_{i}, such as that shown to the right, we would like to define functions λ_{i}(p) such that
p = Σ_{i} λ_{i}(p) v_{i}.
This is the linear reproduction condition we mentioned for barycentric coordinates. For what is to follow, it may be helpful to think of this as a linear relation among p and the control points:
p  Σ_{i} λ_{i}(p) v_{i} = 0.
To define the coordinates λ_{i} at a point p, we begin by writing p as the average of all the points over a circle Γ centered at p
Joining p to the control points v_{i} breaks Γ into a number of arcs Γ_{i} so that we may write the integral as the sum of integrals
We will now focus attention on one of those arcs, as shown in the figure. Notice that the points p' on the arc lie inside the triangle formed by p, v_{i}_{ }and v_{i+1}. This means that we may write p' using barycentric coordinates defined by this triangle:
It is possible to express the integrals of the barycentric coordinates in terms of the oriented angle αi shown in the figure. If we then add over all the arcs, we obtain a linear relationship between p and the control points, as desired. More specifically, we find explicit representations for the coordinates λi(p):
where
It is straightforward to verify that mean value coordinates satisfy the affineinvariance and interpolation properties that we earlier stated as essential.
Shown below is a plot of the function λi corresponding to the control point shaded red. Brighter blue colors indicate more positive values, while brighter green indicates more negative. Notice that the coordinate function is defined everywhere, including outside the cage.
We may now use mean value coordinates to move characters by moving the control points, such as the red point below, of a cage containing the character.
Of course, similar ideas may be applied in three dimensions as demonstrated by Pixar's use of mean value coordinates.


© Disney/Pixar 
© Disney/Pixar 
Mean value coordinates are quite convenient to use since they are computed at a point using only local geometric information. From a computational point of view, this means they may be efficiently computed in the binding process.
However, a significant problem arises when the cage is not convex. Notice how moving the leg on the left causes unrealistic deformations of both legs.


© Disney/Pixar 
© Disney/Pixar 
There is a relatively simple explanation: for nonconvex regions, it may happen that some of the coordinates of a point are negative. For instance, in the situation shown to the right, the oriented angle α_{3} is negative which could cause λ_{3} to be negative as well.
Here is the function λ_{i} corresponding to the red control point point v_{i} in a highly nonconvex cage. Remember that green represents negative values of the function so we see that the values in the "right leg" are generally negative.
Therefore, when the control point v_{i} is moved, say, to the left, a point p with λ_{i}(p) negative will move to the right due to the contribution from λ_{i}(p)v_{i}. For instance, the blue polygon will move to the green polygon shown on the right.
Since nonconvex cages are often desirable, Pixar has been investigating the use of harmonic coordinates, which will be explained after an introduction to harmonic functions.
Harmonic functions
A harmonic function f(x, y) is one whose Laplacian is zero. In two dimensions, this means
Harmonic functions are, well, harmonious: they satisfy several pleasing and useful properties, which will be described momentarily. Linear functions are harmonic; in fact, in one dimension, every harmonic function is linear: for functions f of a single variable, the Laplacian is simply the second derivative of f. If we seek to generalize linear barycentric coordinates, perhaps harmonic functions offer rich possibilities.
Harmonic functions are ubiquitous in the natural world. For instance, the steadystate temperature distribution of some region in space is described by a harmonic function.
Harmonic functions also satisfy an extremely useful property:
Mean Value Property: The value of a harmonic function at any point is equal to the average of its values around any circle centered at that point.

In the figure below, for instance, the value of a harmonic function at p is equal to its values on the circle drawn around p.
This is a familiar property of linear functions in one variable: the value at one point is the average of the values at points equally spaced on either side:
Observe now that the average of a set of numbers may not exceed the largest number in that set. For instance, if everyone in my neighborhood makes less than \$50,000, the average income cannot be larger than \$50,000. This means that the value of a harmonic function at a point cannot exceed the largest value on any circle centered at that point.
Pursuing this line of thought a little further leads to the:
Maximum Principle: The largest value that a harmonic function attains on a region is found on the boundary of that region.

In the same way, the smallest value that a harmonic function attains on a region is found on the boundary as well.
A simple application of the maximum principle gives one final property:
Uniqueness Principle: If we know the values of the function along the boundary of a region, there is only one harmonic function defined in that region with those boundary values.

Remembering that harmonic functions model steadystate temperature distributions, this says that the temperature distribution inside a cooked turkey is uniquely determined by the temperature distribution on the outside of the turkey.
We will now put these properties to work in developing coordinates in the interior of a cage.
Harmonic coordinates
Remember that mean value coordinates provide an effective way to use the control points of a cage to move the interior points, but problems arose when nonconvex regions led to negative coordinates. To remedy this situation, we will introduce a new set of coordinates, called harmonic coordinates, that are always nonnegative. These coordinates were originally introduced by DeRose and Meyer at Pixar. A subsequent paper by Joshi, Meyer, DeRose, Green, and Sanocki gives additional shape to these ideas.
For each control point v_{i}, we will define a harmonic function h_{i}(p) inside the cage by enforcing the interpolation property h_{i}(v_{j}) = 1 if i = j, and 0 if not, and asking that h_{i} be linear on the edges of the cage.
The following properties may now be easily verified:
 Linear reproduction: p = Σ_{i} h_{i}(p) v_{i}. This follows from the uniqueness principle since both sides of this equality are harmonic functions of p and equal on the boundary. They must therefore be equal inside the cage as well.
 Affine invariance: On the boundary, we know that the sum Σ_{i} h_{i} is constantly 1. Since this sum is also harmonic, the maximum/minimum principle tells us that Σ_{i} h_{i} = 1 inside the cage too.
This tells us that the harmonic functions hi satisfy the properties that we desire of coordinate functions. In addition, with these values on the boundary of the cage, the maximum principle guarantees that Therefore, harmonic coordinates will avoid the problem that we see with mean value coordinates for nonconvex cages.
Remember that mean value coordinates may be easily computed using a formula that depends on simple geometric information. How can we compute the harmonic functions inside the cage?
This may be accomplished using the method of relaxation, which we will describe, for illustrative purposes, for onedimensional functions. Suppose we know the values of a harmonic function on the boundary of an interval. We will divide the interval using a finite number of equally spaced grid points.
You will recall that the mean value property says that the value of the harmonic function at some point is the average of the values at equidistant points. We will use this observation and initially set the value of the function to 0 at the interior grid points. Now move across the grid and replace the value of the function at a point by the average of adjacent points.
When we have moved all the way across the grid one time, we find:


Move across the grid a second time.


After 10 times:


After 20 times:


Notice that the values at the grid points eventually converge to the values of the harmonic function, which is linear in this onedimensional case. The same idea works in higher dimensions as well.
Shown below is the function h_{i} found by the method of relaxation on the grid shown. Also, a comparison is given with the corresponding function obtained using mean value coordinates. Notice that the two functions appear to be rather similar inside the cage.
Shown now is a comparison of the results of moving an object using harmonic coordinates, on the left, and mean value coordinates.
If we consider a nonconvex cage, notice that the harmonic function, shown on the left, is everywhere positive inside the cage, as we expected due to the maximum principle. The mean value coordinate is, as we saw earlier, negative in the "right leg."
We may now consider what happens when we move the red control point using both sets of coordinates. The blue figure, the initial one, is moved to the green figure, shown below.
On the right, we see the expected problem with mean value coordinates. Interestingly, the figure does not move significantly when using harmonic coordinates. There is an interesting explanation of this observation.
Mean value coordinates are defined in terms of
whose magnitude is influenced by the straight line distance between p and the control point v_{i}. By contrast, the influence of a control point v_{i }over an interior point p in the harmonic function h_{i} is determined by the distance as measured inside the cage. For instance, consider our cooked turkey: though a leg may be next to the breast, the temperature at a point in the breast will not be significantly influenced by the temperature at a point on the leg. This thinking may be made precise through the formalism of stochastic integrals.
Finally, here is a result of Pixar's use of harmonic coordinates. On the left is seen the original binding configuration. In the middle is the result of moving the cage using harmonic coordinates, and the result of using mean value coordinates is recalled on the right.



© Disney/Pixar 
© Disney/Pixar 
© Disney/Pixar 
Summary
In this article, we've looked at mean value and harmonic coordinates in a twodimensional setting. Ultimately, we need to work in three dimensions, of course, and these ideas may be suitably adapted to work in that environment as well.
The two methods have relative advantages. Mean value coordinates are computed exactly at each of the character's points using geometric information. By contrast, harmonic coordinates are only computed approximately so that some consideration must be paid to the accuracy of the solving algorithm and the resulting error.
Harmonic coordinates require us to compute the value of the coordinate functions at every point on a grid in the interior of the cage. This requires significant computational effort, some of which will necessarily be wasted since we are only interested in the values at the points of our character. To put numbers to this observation, consider Remy's 9775 points in his cage of 325 control points.

© Disney/Pixar 
Using the method of relaxation with a threedimensional grid having 32 grid points on a side takes 57 seconds to compute the harmonic coordinates in the binding process. From that point, however, it requires only 0.111 seconds to create subsequent poses:

© Disney/Pixar 
Of course, the truly remarkable point is that we won't be aware of any of this when we watch the next Pixar film and find ourselves lost in one of our culture's richest experiences: a story welltold.
Thanks
Thanks to Tony DeRose of Pixar Animation Studios for supplying some of the images for this article, answering questions, and reviewing a draft. Any errors are, of course, my own.
Thanks also to the people at Pixar for maintaining their longheld vision that profound creative expression may be found through recent technological innovations.
For V.
References
 Michael Floater, Mean Value Coordinates, Computer Aided Geometric Design 20 (2003), 1927.
 Tao Ju, Scott Schaefer, Joe Warren, Mean Value Coordinates for Closed Triangular Meshes, ACM Transactions on Graphics 24 (2005), 561566.
 Tony DeRose, Mark Meyer, Harmonic Coordinates, Pixar Technical Memo 0602, Pixar Animation Studios, January 2006.
 Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green, Tom Sanocki, Harmonic Coordinates for Character Articulation, ACM Transactions on Graphics 26 (2007),
 Harmonic coordinates explained, a video illustrating many of the ideas in this article.
 David Gilbarg, Neil S. Trudinger, Elliptic partial differential equations of second order, SpringerVerlag, New York, 2001.
David Austin
Grand Valley State University
austind at gvsu.edu