基於快速傅立葉轉換的水波生成(1)

作為目前電影業界廣泛採用的海洋波浪生成方案，基於快速傅立葉轉換(Fast Fourier Transform, 之後簡稱 FFT)的水波生成方式其優點是高真實度和豐富的細節。

對於一個發現自己走錯行的遊戲工程師，決定把自己對FFT水水波生成的理解當作不務正業開始墮落的第一篇網誌。

在討論實際做法之前，必須先了解什麼是傅立葉轉換。
先從數學上來說，這個方程式就是傅立葉轉換

... 看得懂有鬼！

但是不要急，將這段方程式用中文來解釋就是：

....聽得懂有鬼！

看不懂也聽不懂怎麼辦？只剩下賣雞排或異世界轉生這兩條路了...

別急！讓我用一個簡單的範例來做說明。
這是一個看起來有點複雜的訊號波形 f(t)



但實際上，卻是可以用簡單的Sin波相加合成


簡單分析Sin波可以得到


因此，範例中的3個Sin波可以分析成



為了方便理解，將波形資料圖形化，取Sin波的振幅為縱軸，角周波數為橫軸，可以得到



到了這裡，回頭看看一開始說明的傅立葉轉換，先不管那複雜的時間積分之類的描述，
我們將範例波形由時間函數f(t)轉換成角周波函數F(w)來表示，而這就是傅立葉轉換在做的事情。

歸納一下上述總結，可以用下圖來解釋



但現實上，不是所有訊號都能像上述範例那麼簡單。
範例是用到3個週期波形所組合，所以可以簡單地被分解。
那什麼是週期波形？顧名思義，就是訊號的形狀呈現週期性(一段時間後，形狀重複)


非週期函數在計算上有其困難性。
因此，在水波生成計算上，會假設訊號都是由週期波形所組合



這叫做傅立葉級數展開。
然後整理一下傅立葉級數展開，可以得到


賽已、摳賽、甲賽  ...
看到那麼多個賽，都想跑廁所了...
還好 Eular 大老師幫我們建立了一個公式



然後，利用這個公式，連立求解得到



代入到傅立葉級數可以得到



將同類項合併



從結果可以觀察到



接下來，可以把整個方程式做個整理




比照之前的角周波函數F(w)



所以，只要求得所有的係數，就完成了傅立葉轉換！

... 回到了最根本的問題 ，係數怎麼求？


在談到如何計算係數之前，要先介紹三角函數的一個特性，正交
不同角周波數的三角函數彼此正交，證明如下



那正交有什麼好處，答案是求係數很方便

舉一個2維向量作範例

(2,5) = a*(1,0) + b*(0,1)， 求 a,b 值

看到題目可以直接知道 a =2. b = 5。
但是我們用數學的方式來求，就使用到內積

a = dot((2,5),(1,0)) = 2*1 + 5*0 = 2
b = dot((2,5),(0,1)) = 2*0 + 5*1 = 5

現在我們回去看看最後求得的時間函數 f(t)


由於複數內積要取共軛，所以可得




在水波生成的實作上，之前提到會假設波形是由週期函數所組合
因此，



這就是離散傅立葉轉換。



寫了那麼多，簡單的介紹傅立葉轉換，
下一篇會開始進入正題介紹如何用傅立葉轉換做水波生成。


註1. 本文對於angular frequency一詞翻譯成角周波，在國內常用角頻或角頻率來說明，但因為想強調其周期性和本身哈日(日文也是使用角周波一詞)，所以就直接使用角周波。
之後的文章也會繼續使用角周波來代替angular frequency