Geometrically, this is basic triangulation, and so-called shape-from-motion estimators have been around since the early 1980's. But there are two problems to be solved before you can triangulate. The first is to figure out how to select landmarks to use as reference points. Bouguet developed software that gives each new frame a quick once-over, chooses surface details that it thinks it can follow, and tracks them automatically thereafter. The second is that, although you know the spacecraft's motion in relation to the solar system, you dont know how the comet and the spacecraft are moving relative to one another. The comet is probably tumbling in some weird way, so your landmarks (and your landing site) will appear to be gyrating wildly. So he wrote a program to extract the comets motion (also of keen interest to a lander) from the collective paths of the landmarks, and then another program to find the 3-D structure from the computed motion.

But a small, slow-moving object seen close-up looks exactly like an object twice as big and twiceas far away moving twice as fast, so Champollion will have accelerometers and range finders as secondary systems.
And as the image sequence gets longer and the landmarks are replaced by new ones, cumulative errors creep in. Most researchers finesse this by using one set of landmarks visible throughout the sequencean impossible feat for an opaque object rotating through 360 degrees. Bouguet got a dramatic demonstration of this problem early on, when he shot a video while riding a cart pushed at a brisk walk by Gonçalves and Ursella through the basement corridors of the Beckman Institute. The Beckman Institute is a hollow square, with level hallways, but the computer reconstructed a rectangular spiral in which the cart rose some six meters over its hundred-meter journey. Bouguet remained unfazed—"I was using a model with as few constraints as possible, so I was not explicitly forcing the motion to be planar. So in my thesis, I propose that M. C. Escher must have designed the building."

In the consumer marketplace, these algorithms could add a whole new dimension, as it were, to home movies you could plug the vacation video tape you shot in Venice into your computer, and have it reconstruct a 3-Dmodel of the town that your friends could stroll through. Or you could take a scene from your favorite movie, reconstruct it in 3-D, and view it from different angles. Add body-tracking software, and you could even insert yourself into your favorite flick.

Bouguet continued to refine the navigation system, but on March 6, 1997, something else happened. He was the teaching assistant for EE/CNS 148, which that year covered the burgeoning field of 3-D photography. Besides picking landing sites on comets, there are lots of reasons for wanting a 3-D representation of an actual object in your computer. For example, the new Star Wars movie, The Phantom Menace, contains dozens of digitally generated aliens, many if not all of whom started as 3-D scans of people. Now when George Lucas scans someone, its several steps up from pressing your face against the glass of that little flatbed scanner in your office. These scanners cost from fourteen thousand to several hundred thousand dollars, and, in general, use motorized platforms that move very precisely through the beam of a laser striper, while a camera records how the stripe plays over the objects surface. "There are many different types of systems," says Bouguet,"and there are books on the technique of active lighting, as its called." EE/CNS 148 wasn't quite so high-tech: the class used a liquid-crystal display projector—an overhead projector for your computer screen, essentially—to cast a computer-controlled pattern of parallel lines. But projectors cost money, and you can get a shadow for free. In an informal meeting on the afternoon of Bouguet's PhD candidacy exam, Perona "mentioned the idea of waving a pencil to cast a shadow," Bouguet recalls, and I saw immediately the geometry of reconstruction. Basically, everything came as a flash of inspiration.