Shortest morphing between shapes embedded in $\mathbb{R}^3$

Question

I am interested in what in computer graphics is called morphing between two topologically equivalent shapes $S_0$ and $S_1$ in 3D. This is a continuous "path" of shapes $S_t$, each embedded and all with the same genus, for $t \in [0,1]$. Let us assume the shapes are closed surfaces; I am particularly interested in polyhedra, but likely could adapt from a method for smooth surfaces. For example, I would like to morph between these two genus-7 polyhedra:
$V{=}30, E{=}84, F{=}42$

It would make a nice movie to show that the first is truly genus 7.

There is an extensive literature on this topic, as it is needed in many graphics contexts. A sample of some work in this area is provided in the references below. As far as I know, all have some ad hoc heuristics to obtain "nice" morphs. What I am seeking to learn here is whether there might be some attractive embedding theorems that could lead to a clean, perhaps more principled morph.

Here is what I have in mind, a simple algorithm for convex shapes. Embed $S_0$ in the 3-flat of $\mathbb{R}^4$ with 4-th coordinate $x_4=0$, and embed $S_1$ in the 3-flat with $x_4=1$. Let $H$ be the convex hull of $S_0 \cup S_1$ in $\mathbb{R}^4$. Now intersect $H$ with $x_4 = t$ to obtain $S_t$. Of course this only works for convex shapes.

Here, finally, is my question:

Is there some mapping that would send $S_0$ and $S_1$ into some space, and a definition of a canonical parametrized path between those shapes as endpoints, so that the intermediate shapes $S_t$ along the path (a) are all embedded in $\mathbb{R}^3$, (b) all have the same genus?

It is likely too much to hope for, but if there were a mapping/space combination that would map genus-$g$ shapes naturally to convex genus-0 shapes, then the above convex algorithm would apply. Or if there were a construct akin to the convex hull that accommodated nonconvexity and holes... I know my question is vague, but I hope its intent is clear. Any ideas, however speculative or tentative, would be appreciated. Thanks!

References.

[GSLML98] Gregory, State, Lin, Manocha, Livingston, "Feature-based surface decomposition for correspondence and morphing between polyhedra," 1998. link

[ACL00] Alexa, Cohen-Or, Levin, "As-rigid-as-possible shape interpolation," 2000. link

[KSK00] Kanai, Suzuki, Kimura, "Metamorphosis of Arbitrary Triangular Meshes," 2000. link

Answer 1

Joseph,

I believe that there is not a simple linear smooth mapping. My short explanation for it is that the morph from $S_0$ to $S_1$ does not really consist of a single continuous deformation, but instead of the concatenation of a sequence of multiple piece-wise linear deformations consisting of more than three separate steps: $S_0 \to S_a \to S_b \to S_c... \to S_1$

Your $S_0$ is the frame of an octahedron.

• I would say that $S_a$ should be the skeleton of your $S_0$, formed by shrinking all of the polygonal faces into a simpler tubular (or line segment) skeleton.

• Then, $S_b$ should be the transformation of the octahedral skeleton in $\mathbb{R}^3$ into the equivalent planar graph in $\mathbb{R}^2$. (this $S_a \to S_b$ step can be done as a linear interpolation morph)

• then, $S_c$ should the the fattening of the skeleton of $S_{b}$ and its transformation into a disk with the seven holes punched in it corresponding to the seven holes in the planar graph representation $S_b$ of the octahedral skeleton $S_a$.

• then, $S_d$ should be the elongation of the disk into an elliptical shape as the seven holes are migrated from their positions in the planar graph $S_b$ into a linear configuration along the long axis of this elliptical elongated disk.

• then, $S_e$ can be the transformation of this disc with seven horizontally space holes into a skeleton graph of your $S_1$

• then, $S_f$ can be the tranformation of the $S_e$ skeleton graph into the polyhedral representation of $S_1$ with polygonal faces as you have drawn.

Note that I have broken up the three steps into a few extra substeps to ease in the understanding of the visualization. Also note that the in toto transformation animation consists of a concatenation of multiple piece-wise linear sub-transformations.

I think that is the best way to visualize or animate it.

Attempting to create a single flowing transformation will falsely blur together the distinction of some of the topological procedures, in my opinion.

A similar problem arises in graphical animation morphing: what is the transform of a square $ABCD$ onto the same square mapping $A \to B, B \to C, C \to D$, and $D \to A$?

• Is it the rotation of the 2-d space around the center of the square? (which preserves the shape and the size of the figure)

• Is it the rotation of the 2-d space around the point "A" followed by translation of the resulting rotated square? (which preserves shape and size, but is "clunky" and may be perceived as the transform requiring two distinct steps) or any other combination of rotations and translations

• Is it the linear "morph" of the coordinate points A to B, B to C, C to D, and D to A, which would result in a square rotated 45 degrees at $t=0.5$ but consisting of half of the area of the square at $t=0.0$ (ABCD) and the square at $t=1.0$ (the square BCDA) --- preserving the shape of the figure, but changing the size/scale of the square over the time of the morph

A morph in graphics is not always just the "tweening" (in between interpolation of the coordinates) of corresponding points between the starting shape $S_0$ and the ending shape $S_1$. Sometimes, some tweaking modifications such as rotation, bending, flowing, etc., are required in order to produce a visually satisfying or acceptable and believable transformation. (Of course, the concept of visually satisfying and acceptable are very subjective, contextual, and in the eye of the beholder, as evidenced by the nonobviousness of some of the examples in the question "Proofs without Words").

In the example you are trying to create, only the $S_a \to S_b$ step can be done as a linear interpolation morph. The rest of the steps require a bit of cleaning up and visual "eye candy" in order to be appreciable and understandable.

I might try playing around with some animation tools to play with this, but I don't think that the transformation of the octahedral skeleton to the overtly obvious genus-7 shape can be done by the type of technique which you're asking for.

Answer 2

There is another solution in the computer graphics literature that you didn't mention:

Greg Turk and James O'Brien, "Shape Transformation Using Variational Implicit Functions," SIGGRAPH 99, August 1999, pp. 335-342.

http://www.cc.gatech.edu/~turk/my_papers/schange.pdf

This uses the same idea that you outline, except instead of taking the convex hull they create a 'best fit' shape in the ambient space using radial basis functions. In this way they don't need the shapes to be isotopic or even homeomorphic.

Maybe people familiar with cobordism would be able to provide insight into what might be desired? Anyway, I like the O'Brien-Turk solution.