Terrain morphing

Written by Paul Bourke
April 2001

Source code that created the examples below.

QuickTime animation of example 3: morph.mov.gz (1.2MB)


Morphing is a popular technique in the computer graphics industry extensively used in Michael Jackson videos but also used in countless movies and television ads. The technique was first used in the early 1980's, one of the first movies that used morphing was "Indiana Jones and the last Crusade". Morphing is a very different technique to fading, in that case the colour of each pixel in an intermediate frame is a linear interpolation between the colour of the corresponding pixel in the start and stop frame.

For example
colourintermediate = colourstart + mu (colourstop - colourstart)

In morphing one tries to capture a sense of the geometric transformations between the start and stop frame. In what follows a standard morphing technique as presented by Thaddeus Beier at the 1992 Siggraph will be applied to create smooth transitions between two terrain datasets. For example the application in mind was the morphing of data from continental drift simulations. The technique and algorithm here applies equally well to the more traditional image morphing. The strict term for this method is "field morphing" because the operator chooses related regions in the start and stop frames, during the morph the relationships between these regions is preserved.

In order to understand the morph transformation, assume we have a start and stop surface. On each of these surfaces we create a single directed line, this pair of lines indicates a transformation relationship between the two surfaces. For example, in the following the intention is that the region around the line P1 to P2 is rotated and shrunk during the morph between the two frames.

Now consider estimating the surface height at a point P on an intermediate surface. A directed line P1->P2 on this intermediate surface is formed by interpolating between the lines in the start and stop image. In order to estimate the value at point P compute u and v, these are the normalised distance along the lines P1->P2 and P1->Perp respectively. Note that there are two possible perpendicular vectors, in what follows it doesn't matter which perpendicular is used as long as a consistent choice is made.

P = P1 + u (P2 - P1) + v (Perp - p1)

These values of u and v are applied the line in the start and stop surface to get the corresponding point in those surfaces. The line on the intermediate image is a linear interpolation between the corresponding lines in the start and stop surface. The surface height in the intermediate surface is a cross fade of these two height samples. If the animation sequence is controlled by a parameter mu that ranges from 0 (start) to 1 (stop) and the two height samples are z1 (start) and z2 (stop) then the intermediate height is as follows.

z = z1 (1 - mu) + z2 mu

Most morphs will require more than a single line to define the related regions in the start and stop surfaces. For every point on the intermediate surface each line gives a point on the start surface, a weighted sum of all these points is used to choose the point to sample on the start surface. The same applies for the stop surface. The cross fade is then applied to the weighted sum estimate of the corresponding points on the start and stop surface.

The weight is predominantly determined by the distance of the point and the line on the control surface. This is intuitively obvious, the influence a line plays on a point is inversely related to the distance of the point to the line. Different forms of the weighting can change the exact details of the field on influence, for the details see the sample code.

Examples

In the examples that follow, fractal landscapes are created within the red outlines. The control lines are shown in green except for example 2 where the control lines are identical to the outline. Samples from an animation between the start and stop surfaces are given for both simple blending and morphing. While the blend is a valid smooth transition between the two surfaces, the sample below should convey the richer transition given by the morph.

Example 1 - Rotation

This first example illustrates rotation, note the single control line in the last frame is at 90 degrees to where it is in the first frame. The blend case doesn't behave too objectionably and may be the desired effect in some application. In the morph case there is a clear rotation of the island features.

Start frame
Stop frame

Blend

Morph

Example 2 - Translation

This is an example of translation, as with the above example there is a stunning difference between the morph case and the straightforward blend of the height fields. In the morph case the island slowly moves across the ocean while in the blend one island drops away while the other appears.

Start frame
Stop frame

Blend

Morph

Example 3 - Separation

This is a more complicated example, the main land mass rotates and a small island splits off. In the blend example the small island appears but in the morph animation the land mass clearly rotates while the island slowly pulls away.

Start frame
Stop frame

Blend

Morph

Example 4 - Lake Creation

This example is only fully appreciated as an animation sequence, the left and right arms are drawn around and closes off the gap. This example does illustrate the difficulty imposed by the requirement of having the same number of control lines in the start and stop surface.

Start frame
Stop frame

Morph

References

Digital Image Processing of Earth Observation Sensor Data
Bernstein, R.
IBM J. Res. Development, 20:40-57, 1976.

Feature-Based Image Metamophosis
Beier, T.
Siggraph 1992

Space Deformation Models Survey
Bechmann, D.
Computers & Graphics, 18(4):571-586, 1994.

Three-Dimensional Distance Field Metamorphosis
Cohen-Or, D., Levin, D., Solomovici, A..
Transactions on Graphics, 1998.

Extended free-form deformations: A sculpturing tool for 3D geometric modeling
Coquillart, S.
Computer Graphics (SIGGRAPH '90 Proceedings), volume 24, pages 187--196, 1990.

Conformal image warping
Frederick, C. and Schwartz, E.L.
IEEE Computer Graphics and Applications, 10(3):54-61, March 1990.

Establishing Correspondence by Topological Merging, A New Approach to 3D Shape Transformation
Kent, J., Parent, R., Carlson, W.

The Morphological Cross-Dissolve
Novins, K., Arvo, J.
Conference Abstracts and Applications, page 257. ACM SIGGRAPH, August 1999.

A Morphable Model for the Synthesis of 3D Faces
Blanz, V., Vetter, T.
Proceedings of SIGGRAPH 99, pages 187-194. ACM SIGGRAPH, August 1999.

Digital Image Warping
Wolberg, G.
IEEE Computer Society Press, 1990