Pixar mathematics

Pixar's use of harmonic functions (by David Austin) describes mathematical techniques used by Pixar. Incidentally, apparently there exists something called Pixar University, which I learned when I went to the excellent Pixar exhibit at the Oakland Museum of California. As far as I can tell they are not hiring, they're really an internal training program, and anyway I don't know anything about animation. (The exhibit's next stop is in Hong Kong.

The problem that the article addresses is basically this: 3-D animated characters have many "control points" on their surface. Animators would not like to have to specify how all of these move individually, so they don't; they only specify the motion of a subset of these called the "cage". How do we interpolate? When there are just three control points this is obvious -- use barycentric coordinates in both triangles. This is basically exploiting the fact that there's a unique linear transformation taking a generic triangle to another. generic triangle

But what if there are more than three control points? One generalization is "mean value coordinates", which are a linear transformation, but which are problematic when the cage is not convex. Since the cage is often, say, the outline of a human being, this is a real problem! Apparently the newer technique is "harmonic coordinates" -- define the coordinates of the n boundary points of a cage to be (1,0,...,0), (0,1,...,0), ..., (0,0,...,1). Then for any point p in 3-space, let h_i(p) be linear on the edges of the cage, and harmonic (having zero Laplacian) elsewhere. Then the non-cage control point p has harmonic coordinates h₁(p), ..., h_n(p); if you move the cage points then these points keep the same harmonic coordinates but change their coordinates in 3-space. Unfortunately inverting the h-function is a bit harder but it seems worth the trouble.

There's a video explaining this, with lots of images!

Random Walk: The visualization of randomness

Random Walk: The visualization of randomness, Daniel Becker's diploma thesis, shows fascinating pictures that illustrate various stochastic phenomena: dart-throwing and the Poisson distribution, Benford's law, Monte Carlo methods, some hidden high-order correlations in pseudo-random number generators, and so on.

Newton's method fractals

Simon Tatham has produced fractals derived from Newton-Raphson iteration which are quite interesting to look at.

The main idea here is that if you want to find a root of some function f, then you start from a guess a₀; then compute a₁ = a₀ - f(a₀)/f'(a₀); geometrically this corresponds to replacing the graph of the function with its tangent line at (a₀, f(a)₀) and finding the root of the tangent line. Then starting from a₁ we find a₂ and so on. If you're already close to a root you'll get closer. But if you're far away from a root unexpected things can happen; the set of all starting points a₀ for which the sequence (a₀, a₁, a_@, a₃, ...) converges to a given root of f is fractal.

(I've mentioned this before, and so has John Armstrong, but Tatham's pictures are better.)

compressed calendars and the Doomsday algorithm

Infodesign challenge -- how to fit a calendar for a year onto a business card.

There are many solutions; basically it seems that in order to do this well one has to exploit the fact that our calendar has some sort of structure. In short, all months look the same if you just rename the days of the week.

#2, for example, takes this into account: in a non-leap year January and October "look the same", as do February, March and November; September and December; April and July.

Incidentally, this is not a problem I particularly worry about, because I know the Doomsday algorithm. In short:

• It is relatively easy to determine what day of the week the last day of February falls on in a given year. (Because of leap years, a lot of calendar algorithms focus on this day. There are some cases where for the purposes of formulas it is convenient to think of January and February as the 13th and 14th months of the previous year.) This day of the week is called "Doomsday". Doomsdays run in a 400-year cycle, as does the entire Gregorian calendar. Doomsday in 1900 was a Wednesday, and in 2000 it was a Tuesday. For every twelve years after a multiple of 100 Doomsday moves forward one day; this is because twelve years include three leap years, so Doomsday actually moves forward 15 days. (So Doomsday in 2012 is a Wednesday, in 2024 a Thursday, and so on.) So take the last two digits of the year and divide by 12; call the quotient q and the remainder r. Move Doomsday forward from its day in the last century year by q+r days (each dozen years moves Doomsday forward fifteen (= one) days, then each year after that moves it forward one more day) plus r/4 days rounded down (for leap years). So, for example, Doomsday in 2000 was Tuesday; 7 divided by 12 is 0, with remainder 7. So Doomsday in 2007 is Tuesday, plus zero days, plus seven days, plus one day (7/4 rounded down is 1); that's Wednesday. Indeed, February 28 was a Wednesday this year.


• certain days will always fall on the same day of the week as that day; the easiest set to remember is 4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, 11/7 [note that for the set named so far! it doesn't matter whether you put the month first or the day first!], 3/7, 2/(28 or 29), 1/(3 or 4). (A few others that stick in my head are 2/14 (Valentine's Day) in ordinary years, 7/4 (Independence Day), 10/31 (Halloween) and 12/26 (the day after Christmas).) All of these days were Wednesdays this year as well.


• once you have a set that includes at least one day in each month, it's not hard to work within each month, probably because we have a decent amount of practice doing so. November 7 was a Wednesday; thus November 21 (fourteen days later) was also a Wednesday; thus November 25 is a Sunday. And my television agrees with me; it is showing that execrable show that only survives because of its cushy post-Simpsons time slot, King of the Hill.

A real challenge would be to figure out rules that let someone calculate the day of the week of a given date in the Hebrew calendar in their head. I suspect it's not possible.

The spinning woman, part two

Remember the spinning woman that I wrote aboutI wrote about last week?

Supposedly, people who saw her spinning clockwise are more "right-brained" (in the pop-science sense of creative, able to see the big picture, and so on) and people who saw her spinning counterclockwise are more "left-brained".

According to the good folks at Freakonomics, if you use college major as a proxy for pop-culture brain-sidedness, it actually works the other way -- "left-brained" people are more likely to see her spinning clockwise. (Of course, this isn't scientific -- it's just Freakonomics readers, and the sample sizes are small.)

Steven Levitt writes:

I often joke about how the information provided by someone who is incredibly terrible at predicting the future (i.e., they always get things wrong) is just as valuable as what you get from someone who is good at predicting the future. I used this strategy with some success by betting the opposite of my father whenever he’d bet a large sum of money on a football team that was sure to cover the spread.

That's definitely true. I've heard that another such "anti-predictor" is Punxsutawney Phil, the "official" groundhog of Groundhog Day. He gets yanked out of hibernation on February 2, and if he sees his shadow we're supposed to have "six more weeks of winter". (This is part of the utterly bizarre American tradition of Groundhog Day.) I read once that he's wrong something like 80% of the time, although I don't have a source for this. The Wikipedia article says that the actual error rate is something like 60% to 70%. Still, it seems like the groundhog is more often wrong than right.

The spinning woman

A spinning dancer, from news.com, via Freakonomics and Marginal Revolution (I'm giving those sources because you might want to look at the comments there.)

There is a woman spinning; the question is, is she spinning clockwise or counterclockwise? Supposedly this has something to do with which side of the brain you use, although I'm not sure I buy it.

But my first thought was "clockwise from whose perspective? From the perspective of someone looking from above, or from below?" (To clarify what I mean by "clockwise", I mean that the dancer is turning to her own right.) I think this does say something about my brain, namely that I demand precise definitions for terms, at least for the sorts of terms that can have them.

Some of the commenters at various places say that you have to look at the shadow, because the shadow doesn't agree with the dancer; as far as I can tell this isn't true, and this is not some sort of optical illusion.

The actual resolution is that you can imagine reflecting the dancer through the plane of your monitor (I almost said "the plane of the board", because usually when I'm thinking about three-dimensional pictures it's when I'm teaching calculus), which will change the direction of rotation but not the picture. So on an intellectual level I understand why both perceptions must be possible. But I can't see her going counterclockwise. Not at all.

A quick thought on Newton's method

John Armstrong talks about fractals in Newton's method. (If you're not familiar with Newton's method, read that post first; what follows is in the nature of a comment to it.) This is something you wouldn't expect; when you're taught Newton's method the impression is that it'll always find the closest root to your initial estimate, or at least that the region which eventually leads to any given root is "nice-looking". That is very far from being true. Basically, if you're trying to find a zero of f(z) using Newton's method, and f'(z) is small, then you can suddenly find yourself making arbitrarily large steps. The self-similar nature of the picture you get if you color the initial values which lead to one zero red, another zero green, another zero blue, and so on isn't too surprising if you think about it this way; the picture has to be its own image under the transformation which takes c to c-(f'(c)/f(c)), which is analytic when f(c) isn't zero. An example of such a picture accompanies the post.

How to build mountains

Mark Chu-Carroll of Good Math, Bad Math writes about how images of simulated mountains are constructed using a fractal process.

I'm kind of surprised to see how simple it is; basically you take a triangle and "pull up" a random point in the interior to get an irregular pyramid, and repeat this procedure on each of the faces.

One of the commenters there, mj, writes: "In a way it's not surprising that complex structure comes out of very simple fractal rules. The structures in reality, the real mountains, are also formed by relatively simple processes. A bit of wind and rain and erosion..." That's a good point. What's interesting is that there's no obvious connection between the rules used to generate the fractal and the real rules, but they generate the same sort of structure on a global scale. On a large enough scale, the low-level structure is simply hidden. Something similar happens with, say, random walks; a cloud of random walkers allowed to dissipate will eventually approach a Gaussian distribution regardless of the underlying lattice. An observer who could only observe on a large scale couldn't tell what the underlying lattice is. There are much deeper ideas of this sort; for example, we don't know whether the universe is actually continuous or discrete.

ways of drawing the Interstate Highway System

Earlier this year, Chris Yates made available online a simplified map of the Interstate highway system, where the interstates are for the most part straight lines. This made its way around the Internet for a while, and it was frequently pointed out that it was wrong -- certain interstates just aren't on it. (The ones I noticed were I-83 (which runs between Harrisburg and Baltimore) and I-88 (Albany to Binghamton); a lot of other people pointed out that it also omits the entire state of Wisconsin.)

It occurred to me that it would be nice to see this map done correctly, and I'm trying to do it myself; unfortunately I don't have a really big piece of paper! It's probably possible to represent all the two-digit Interstates on a single piece of paper, though. But this map from Hedberg Maps looks like what I was thinking of -- it basically assumes that as many of the two-digit Interstates as possible actually form a grid and then fills in the rest, including the three-digit Interstates, accordingly. Too bad it's $40. They explain how the map works here; basically, the map's author, Nat Case, attempted to respect the topology of the system and align the main roads of the system with the grid, so the distance between, say, I-70 and I-80 is the same as the distance between I-80 and I-90. (Case claims inspiration from Yates' map, but seems to be a lot less visible on the Internet, probably because you can't view it online.)

A lot of people compare these to "subway maps", but there's one big difference. On a map of a subway system, the various subway lines are generally denoted by different colors; this makes it obvious when one has to transfer from one line to another. (See, for example, the standard Washington Metro map; there's a recolored version of the map to indicate the different service patterns they run on July 4th.) And this makes sense, because a change of trains has a substantial cost -- you've got to get off the train, often walk up or down some steps, and wait for another train to come. Roads don't work like that -- the cost to go from one highway to another is minimal.

I'd also like to see a similar map of, say, Philadelphia; the street signs indicate that each intersection is a certain distance west or east of one axis (Front Street or Germantown Avenue, depending on location) and north or south of another (Market Street), but the grid breaks down the further you get from the historic city. I actually live along a "seam" in this grid; as you walk down my street the numbers immediately go from the 500s to the 900s. How is the map distorted if you try to place locations not where they are, but where the addressing system implies they are?

edited: Nat Case talks about the map at mapHead; you can see a larger version of the map here. (1080 by 1080, which is large enough to get a very good idea what's going on. It's particularly interesting how some of the shapes of states get distorted here -- Florida is now much longer east-west than north-south, for example, and Arizona and New Mexico end up having roughly the shape of Chile, and Illinois is huge.

Personally, I think it's a little crowded in the northeast, which is something you might not necessarily expect from the description.

And now I don't have to make this map myself to see what it looks like, which is a relief because I'm not particularly good at this sort of thing.