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

and the ability to move them in ways that are both believable and interesting.

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:

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.

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.

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

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₁, v₂ and v₃.

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

β₁(x, y) = ax + by + c

by declaring

β₁(v₁) = 1
β₁(v₂) = 0
β₁(v₃) = 0

Since linear functions on the plane are determined by their values at three non-collinear points, this is enough information to determine β₁ 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 β₂and β₃.


β₂	β₃

These functions, β₁, β₂, and β₃, 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.

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_iand 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 affine-invariance 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 non-convex 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 α₃ is negative which could cause λ₃ to be negative as well.

Here is the function λ_i corresponding to the red control point point v_i in a highly non-convex 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 non-convex 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 steady-state 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 steady-state 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 non-convex regions led to negative coordinates. To remedy this situation, we will introduce a new set of coordinates, called harmonic coordinates, that are always non-negative. 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 non-convex 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 one-dimensional 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 one-dimensional 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 non-convex 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_iover 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 two-dimensional 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.

Using the method of relaxation with a three-dimensional 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:

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 well-told.

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 long-held 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), 19-27.
Tao Ju, Scott Schaefer, Joe Warren, Mean Value Coordinates for Closed Triangular Meshes, ACM Transactions on Graphics 24 (2005), 561-566.
Tony DeRose, Mark Meyer, Harmonic Coordinates, Pixar Technical Memo 06-02, 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, Springer-Verlag, New York, 2001.

David Austin
Grand Valley State University
austind at gvsu.edu