The Algorithm Design Manual Second Edition

8.4

War Story: Evolution of the Lobster

I caught the two graduate students lurking outside my office as I came in to work

that morning. There they were, two future PhDs working in the field of high-

performance computer graphics. They studied new techniques for rendering pretty

computer images, but the picture they painted for me that morning was anything

but pretty.

“You see, we want to build a program to morph one image into another,” they

explained.

“What do you mean by morph?” I asked.

“For special effects in movies, we want to construct the intermediate stages in

transforming one image into another. Suppose we want to turn you into Humphrey

Bogart. For this to look realistic, we must construct a bunch of in-between frames

that start out looking like you and end up looking like him.”

“If you can realistically turn me into Bogart, you have something,” I agreed.

“But our problem is that it isn’t very realistic.” They showed me a dismal

morph between two images. “The trouble is that we must find the right corre-

1

2

2

3

1

4

4

5

5

---

292

8 .

D Y N A M I C P R O G R A M M I N G