将一个形状变换为另一个形状的算法

Question

我正在尝试将一个"形状"转换为另一个"形状"的算法.两种形状都是任意的,甚至可能具有较小的,不连续的形状.

我到目前为止的基本思想如下:找到形状的边缘,沿着这些边缘放置点,然后对目标图像做同样的事情,然后将点移动到它们的目标.

这是一个例子:

我只是不知道从哪里开始.上面的图像是一个简化,实际用例有更复杂的形状/轮廓.我的主要问题是:如何处理不相交的形状？我能想到的最好的方法是找出两个部分之间的最近点,并将它们作为路径的一部分连接在一起.但是我该如何实现呢？

我还没有任何代码,我还处于规划阶段.我想我要求的是,是否有人可以将我链接到任何可能有用的资源,或者给出任何指示.搜索谷歌已经产生了一些有趣的变形算法,但它们都处理完整的图像并涉及将图像分解成碎片以重塑它们,这不是我正在寻找的.

请注意,这将在JavaScript中使用,但如果更容易,可以在PHP中预先计算.

Answer 1

我在JavaScript中发现了一个演示(使用Raphael.js)的轮廓变形和补间动画,展示了Raphael.js如何用于将一条曲线变换为另一条曲线.

此外,这个相关的问题(关于JavaScript中的补间形状)可能包含一些与此问题相关的答案.

该MorpherJS库也可能是适用于这一目的.可以在此处找到使用MorpherJS进行轮廓变形的一些演示.

Answer 2

最好将问题分解为多个可以独立解决的小问题.这样,您在解决此问题后也可以拥有独立的功能,可以将其添加到某些全局模块集合中.

首先,我们需要弄清楚from_shape中的哪个像素转到to_shape中的哪个像素.
我们可以用以下方法解决这个问题:

1. 将to_shape放在from_shape上.
   

2. 对于from_shape中的每个像素,找到其最接近的to_shape像素.
   形状中的每个像素必须具有唯一的id,该id可以是例如其xy位置.

3. 现在,您可以记录from_shape中的每个唯一像素,以及它在to_shape中的唯一像素.

4. 删除重叠的形状并返回到原始形状,
   刚才from_shape中的每个像素都知道to_shape中的目标.

我们还需要知道每个像素的兄弟姐妹.
兄弟是一个紧挨着另一个像素的像素.
要找到它,转到给定像素,从中收集半径为1的所有像素,所有这些像素都是黑色..是像素的兄弟姐妹.当像素行进到目的地时,该信息对于将形状保持为单个单元是必要的.跳过兄弟姐妹会大大加快并简化变形,但没有它们,变形过程中形状可能会变得碎片化.可能想从一个没有兄弟的版本开始,看看它是怎么回事.

最后我们实现变形:

1. 有morph_time_duration.
   对于from_shape中的每个像素,在to_shape中找到它到达目的地的距离.
   该距离除以morph_time_duration,是变形期间像素的速度.
   此外,朝向目的地的角度是要进入的角度.
   所以现在你有速度和角度.

2. 因此,在变形过程的每一帧中,给定的from_pixel现在知道要进入哪个方向,速度,并且它也知道它的兄弟姐妹.因此,在每个帧中,只需在其方向上以其速度行进之后在其新位置绘制像素.然后画一条线给所有像素的兄弟姐妹.

这将显示你的变形.