convolution based algorithm for animated water waves

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.3057&rep=rep1&type=pdf

---

主要说的是使用卷积的方法来做水受到impulse情况下的波动效果。

卷积的公式：

卷积在graphics programming里最普遍的应用是高斯blur，高斯blur就是对row做一个convolutin，然后column一个convolution。

通常说的convolutino kernel也就是公式里的g（当然说是f也是可以的，两者对等的么），在高斯blur里面就是dx sample里面那个数组里的值。

对这篇文章的感性理解可以从高斯blur着手，如果说做类似一种沙子的impulse simulation，那么用高斯blur的convolution kernel就够了，在沙面上的一个点升高，然后不停的blur，可以看到小沙柱在变小变宽，最后消失，这和black render target上加一点白色，然后不停的高斯blur，知道全屏幕是一个颜色（接近全黑）一个道理。

那么由此稍微推广，如果高斯blur的kernel换成有正有负的情况，那么小沙柱的散开方式就变成一高一低的方式，也就是我们要的水面上波纹散开的方式。

这种方式只是帮助理解，不能用来指导编程，编程的话还是需要对背后的数学原理有足够的理解。

---

使用convolution来计算interaction的公式是：

其中convolution kernel的公式是：

里面符号太怪了，没法写出来，假设最终结果就是h（里面类似q的那个符号），convolution kernel是ck（叉子状的符号）

这里结合之前blog里面的water simulation那个dft函数，可以发现其实这个convolution kernel也是一个dft（discrete fourier transform)。

ck的公式里面把exp(w(k)*delta_time)提到1/4*pi*pi部分去，就是和水的wave simulation那个一模一样了。

它是一个随时间周期性变化的函数。

而且它是一个复数。

相应的h也是一个复数，最后render的时候把h的实部拿出来当高度就可以了，但是计算中不能把虚部省略。

整个卷积过程是一个一堆复数的操作。

但是这个convolution算法仍旧需要几个地方要修正：

• 一个是convolution kernel在边缘的时候要有一个绝对值衰减，这样波纹才会以波动衰减的方式散出去
• 一个是如果不想让波动触到边界时候反弹，还要有一定处理，但是游戏里面波纹会反弹多牛逼啊。

衰减部分的公式太tmd烦了，也没啥好说的，直接用就好。

---

实现：

实现的时候有几个选择，自己看心情来做就好。

1，每帧生成conv kernel

每一帧的delta t是不一样的，所以根据delta t来生成一个conv kernel，然后和当前的height map（复数）来做convolution。

2，offline convolution kernel generation

可以offline弄一个convolution kernel，比如使用的delta t是0.066s的，那么在fps为30的游戏里面就可以2帧来做一次convolution。

不用生成convolution kernel。

当然效果可能没有第一种好，但是效率绝对高很多。

3，overlap save or overlap add

insomniac他们用的方法。

原理是2个函数在时域里的卷积在频域里是其傅立叶变换参数的乘法，这个算法在快速傅立叶变换发明出来之后开始变成快速计算convolution的方法。

conv(x,y) = ifft(fft(x)*fft(y));

由于convolution kernel本身就是discrete fourier transform的表示方法，所以两者一结合最后其实只是剩下了一个ifft的计算消耗。

但是这个做法是有很大限制的，insomniac他们的sim框架是一个impulse生成一个tile来模拟，没问题。

如果在一个巨大的heightmap做这个事情，就会遇到dft的一个假设就是信号的周期性，会出现一个波右边散出去，左边传进来（就像小时候玩水管兄弟那样）。

这个是理论上的局限性，谁都没辙，所以这个算法几乎一定要和tile based simulation绑定。

性能：

convolution的性能开销还是比较大的，比如在x*x的grid上做y*y kernel的convolution。

那么计算量是x*x*y*y次，每一次是好几个乘法和加法。