Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
In order to have such a parametrized path $S_t$ you must know in advance that the two surfaces $S_0$ and $S_1$ are isotopic in $\R^3$. This is a non-obvious condition to verify: if $S_0$ and $S_1$ have the same genus and bound a handlebody on \emph{both} sides, then you can conclude that they are indeed isotopic by Waldhausen theorem. The canonical meshing you are looking for therefore should use the fact that both $S_0$ and $S_1$ bound 3-dimensional blocks homeomorphic to handlebodies (on both sides). –  Bruno Martelli Oct 8 '10 at 12:54
    
By the way, I just noticed that your logo is the same $S_0$ octahedral skeleton polyhedron. :) Very nice. Is there a particular reason for your affinity for this particular platonic solid? –  sleepless in beantown Oct 8 '10 at 22:01
    
@sleepless: I constructed this polyhedron (with a student Melody Donoso) as an example of a polyhedron all of whose faces are rectangles, but whose dihedral angles are not multiples of $\pi/2$. It answered a question in the air at the time, and ever since I have been very fond of it. :-) –  Joseph O'Rourke Oct 8 '10 at 22:43
    
@Joseph: Did you finally succeed and manage to make the movie? I'd very much appreciate to see it, because I find it really hard to "see" genus 7 of your logo? –  Hans Stricker Feb 15 '13 at 15:40
    
@Hans: Never did, nope. I still don't really know how to do it. :-/ –  Joseph O'Rourke Feb 15 '13 at 19:59

2 Answers 2

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.

share|improve this answer
    
"I don't think that the transformation ... can be done by the type of technique which you're asking for": Alas, you may be right. But I can still dream! –  Joseph O'Rourke Oct 8 '10 at 22:54
1  
You also have a Hamiltonian path on the dual, the cube, so that when you effectively have the planar octohedral graph, you can "pluck off" each connected summand in succession (maybe this is obvious and/or not what you want) –  AndrewLMarshall Oct 9 '10 at 3:35

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.

share|improve this answer
    
I guess the problem with this is that your motivation is a visual demonstration of the equivalent genus of two objects. I don't know how Turk and O'Brian's method could be modified to guarantee that the genus is preserved in all intermediate shapes/slices. –  Ramsay Oct 8 '10 at 14:59
    
Thanks, I should have known about this paper! From my superficial scan, it appears that the topology is not maintained throughout the morph (one of the features of their method). But definitely this is closer to what I have in mind than the references I provided, and I will study their paper. Thanks for the pointer! –  Joseph O'Rourke Oct 8 '10 at 15:05
    
I've now had a chance to look over that paper, and they specifically do not want to maintain the topology during the morph. It is very nice work, and it uses the same embedding-into-$R^4$ idea, but otherwise doesn't satisfy either my (a) or (b). –  Joseph O'Rourke Oct 8 '10 at 18:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.