Three.js - morphing geometry and refinement of triangular grids

Question

I am trying to use Three.js to turn one geometry into another. Here is what I have done so far (see http://stemkoski.imtqy.com/Three.js/Morph-Geometries.html for a live example).

I am trying to turn from a small polyhedron into a larger cube (both triangulated and centered at the origin). Animation is done through shaders. Each vertex on the smaller polyhedron has two associated attributes, its final position and 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 intersection point with the large cube. To calculate the final UV value, I used the barycentric coordinates and UV values ​​at the vertices of the intersected surface of the larger cube.

This led to a not-terrible but not big first attempt. Since (as a rule) none of the vertices of the larger cube was the final position of any of the vertices of the smaller polyhedron, there were no large pieces of the surface of the cube. Then I refined the smaller polyhedron by adding more vertices as follows: for each vertex of the larger cube I raycasted to the origin, and where each ray crossed the face of the smaller polyhedron, I deleted this triangular face and added the intersection point and three smaller faces to replace it. The morph is now better (this is a living example linked to above), but the morph still doesn't fill the entire cube volume.

My best guess is that in addition to projecting the vertices of a larger cube onto a smaller polyhedron, I also need to project edges - if A and B are vertices connected by an edge on a large cube, then the projections of these vertices on the smaller polyhedron must also be connected by an edge. But then, of course, it is possible that the projected edge will intersect several previously existing triangles in the grid of a smaller polyhedron, requiring the addition of several new vertices, re-rendering, etc. It seems that I really need an algorithm to calculate the overall refinement of two triangular grids. Does anyone know about such an algorithm and / or examples (with code) of morphing (between two grids with different triangles), as described above?

Answer 1

As it turns out, this is a difficult question. In the technical literature, the algorithm that interests me is sometimes called the "map overlay algorithm"; the grid that I create is sometimes called the "superblend".

Some helpful works that I read about this issue include:

• Mesh morphing: state of art and concept.
  PhD. Abstract Jindrich Parus
  http://herakles.zcu.cz/~skala/MSc/Diploma_Data/REP_2005_Parus_Jindrich.pdf
  (chapter 4 is especially helpful)

• Computational Geometry: Algorithms and Applications (BOOK)
  Marc de Berg et al. (Chapter 2 is especially recommended)

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

I started writing a series of demos to create the mechanism needed to implement the algorithms discussed in the literature mentioned above to solve my initial question. These include:

• Spherical mesh projection @ http://stemkoski.imtqy.com/Three.js/Sphere-Project.html
• Topological Data Structure THREE.Geometry @ http://stemkoski.imtqy.com/Three.js/Topology-Data.html

Much work remains to be done; I periodically update this answer as I make extra progress, and still hope others have the information to contribute!