Three.js - morphing geometries and refining triangular meshes

Question

I am attempting to use Three.js to morph one geometry into another. Here's what I've done so far (see http://stemkoski.github.io/Three.js/Morph-Geometries.html for a live example).

I am attempting to morph from a small polyhedron to a larger cube (both triangulated and centered at the origin). The animating is done via shaders. Each vertex on the smaller polyhedron has two associated attributes, its final position and its final UV coordinate. To calculate the final position of each vertex, I raycasted from the origin through each vertex of the smaller polyhedron and found the point of intersection with the larger cube. To calculate the final UV value, I used barycentric coordinates and the UV values at the vertices of the intersected face of the larger cube.

That led to a not awful but not great first attempt. Since (usually) none of the vertices of the larger cube were the final position of any of the vertices of the smaller polyhedron, big chunks of the surface of the cube were missing. So next I refined the smaller polyhedron by adding more vertices as follows: for each vertex of the larger cube, I raycasted toward the origin, and where each ray intersected a face of the smaller polyhedron, I removed that triangular face and added the point of intersection and three smaller faces to replace it. Now the morph is better (this is the live example linked to above), but the morph still does not fill out the entire volume of the cube.

My best guess is that in addition to projecting the vertices of the larger cube onto the smaller polyhedron, I also need to project the edges -- if A and B are vertices connected by an edge on the larger cube, then the projections of these vertices on the smaller polyhedron should also be connected by an edge. But then, of course it is possible that the projected edge will cross over multiple pre-existing triangles in the mesh of the smaller polyhedron, requiring multiple new vertices be added, retriangularization, etc. It seems that what I actually need is an algorithm to calculate a common refinement of two triangular meshes. Does anyone know of such an algorithm and/or examples (with code) of morphing (between two meshes with different triangularizations) as described above?

Answer 1

As it turns out, this is an intricate question. In the technical literature, the algorithm I am interested in is sometimes called the "map overlay algorithm"; the mesh I am constructing is sometimes called the "supermesh".

Some useful works I have been reading about this problem include:

• Morphing of Meshes: The State of the Art and Concept.
  PhD. Thesis by Jindrich Parus
  http://herakles.zcu.cz/~skala/MSc/Diploma_Data/REP_2005_Parus_Jindrich.pdf
  (chapter 4 especially helpful)

• Computational Geometry: Algorithms and Applications (book)
  Mark de Berg et al
  (chapter 2 especially helpful)

• Shape Transformation for Polyhedral Objects (article)
  Computer Graphics, 26, 2, July 1992
  by James R. Kent et al
  http://www.cs.uoi.gr/~fudos/morphing/structural-morphing.pdf

I have started writing a series of demos to build up the machinery needed to implement the algorithms discussed in the literature referenced above to solve my original question. So far, these include:

• Spherical projection of a mesh @ http://stemkoski.github.io/Three.js/Sphere-Project.html
• Topological data structure of a THREE.Geometry @ http://stemkoski.github.io/Three.js/Topology-Data.html

There is still more work to be done; I will update this answer periodically as I make additional progress, and still hope that others have information to contribute!