Algorithm to morph one shape into another.

Question

I'm trying to work on an algorithm that will morph one "shape" into another "shape". Both shapes are arbitrary, and may even have smaller, disjointed shapes too.

The basic idea I have so far is as follows: locate the edges of the shape, place points all along those edges, then do the same with the target image, then move the points to their targets.

Here's an illustration:

I just don't know where to start. The image above is a simplification, actual use case has more complex shapes/outlines. My main problem is: How do I handle disjoint shapes? The best I can come up with is to figure out the closest point between the two pieces, and join them together as part of the path. But how would I implement this?

I don't have any code yet, I'm still at the planning phase for this. I guess what I'm asking for is if anyone can link me to any resources that may help, or give any pointers. Searching Google has yielded some interesting morph algorithms, but they all deal with full images and involve breaking the image into pieces to reshape them, which is not what I'm looking for.

Note that this will be used in JavaScript, but could be precomputed in PHP instead if it's easier.

Answer 1

It's best to break the problem into multiple smaller problems which can be solved independently. That way you also own independent functionalities after solving this problem, which can be added to some global module collection.

First we need to figure out which pixel in the from_shape goes to which pixel in the to_shape.
We can figure that out with the following method:

1. Place to_shape over from_shape.
   

2. For every pixel in from_shape, find its closest to_shape pixel.
   Every pixel in a shape must have a unique id, that id can be for instance, its xy location.

3. Now you can record each unique pixel in from_shape, and which unique pixel it goes to in to_shape.

4. Delete the overlapped shapes and go back to the original ones,
   just now each pixel in from_shape knows its destination in to_shape.

We also need to know which 'siblings' each pixel has.
A sibling is a pixel that lies right next to another pixel.
To find it, go to a given pixel, collect all pixels in radius one from it, all of them which are black.. are the from-pixel's siblings. This information is necessary to keep the shape as a single unit when the pixels travel to their destination. Skipping the siblings would substantially speed up and simplify the morph, but without them the shape might become fragmented during morph. Might wanna begin with a siblingless version, see how that goes.

And finally we implement the morph:

1. There is morph_time_duration.
   For each pixel in from_shape, find the distance to it's destination in to_shape.
   That distance, divided by morph_time_duration, is the speed of the pixel during the morph.
   Also, the angle towards destination is the angle to travel in.
   So now you have speed and angle.

2. So at each frame in the morphing procedure, a given from_pixel now knows which direction to travel in, speed, and it also knows its siblings. So in each frame just draw the pixel in its new location, after having traveled at its speed in its direction. And then draw a line to all of that pixels siblings.

And that will display your morph.