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...
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.
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.
Let's first look at a simpler situation.
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 vi → 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
β1(v1) = 1
Since linear functions on the plane are determined by their values at three non-collinear 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.
These functions, β1, β2, and β3, are called barycentric coordinates, and satisfy some pleasant properties, the most important of which is this:
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 vi, 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" vi 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) vi → p' = Σi βi(p) v'i
If we now want to move our simple character, we let each interior point respond to the motion of the control points:
Barycentric coordinates have useful properties that we note:
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 vi, such as that shown to the right, we would like to define functions λi(p) such that
p = Σi λi(p) vi.
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) vi = 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 vi 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, vi and vi+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):
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.
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.
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 α3 is negative which could cause λ3 to be negative as well.
Here is the function λi corresponding to the red control point point vi 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 vi 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)vi. 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.
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:
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:
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:
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.
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 vi, we will define a harmonic function hi(p) inside the cage by enforcing the interpolation property hi(vj) = 1 if i = j, and 0 if not, and asking that hi be linear on the edges of the cage.
The following properties may now be easily verified:
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.
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 hi 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 vi. By contrast, the influence of a control point vi over an interior point p in the harmonic function hi 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.
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 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.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance