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

• 前言

前兩篇文章簡單敘述如何用離散傅立葉轉換做水波生成，但是存在著效能問題。

在我的桌上型主機上，長、寬各取64個取樣點時，勉強還能運行；

但當取樣點來到128個時候，Unity就沒有反應，只能出動檔案管理員來關閉執行

就算做出來，也無法實際運用在遊戲內。

因此，需要使用快速傅立葉轉換來改善效能。

在實際實作之前，本篇文章會講述快速傅立葉的原理，以方便加深對實作程式碼的理解。

• 快速傅立葉轉換

先回到傅立葉轉換的公式

為了方便說明，我假設所有的訊號的是週期波，範圍在 0 ~ 2PI 內。

然後將公式離散化得到

然後展開數學式，根據 n 的值，分成奇數項(n = 1,3,5,...)的和與偶數項(n = 2,4,6,...)的和



接著，移動相位前進半個取樣點(這個點我稱之為反轉相位，因為彼此相位差距PI)，
然後同樣展開成基數項與偶數項的和，比較兩者差異

 

從這裡，可以觀察到兩者的差異只是在奇數項和的正負值。

因此，可以得知當求得某個相位的傅立葉係數，那我可以立刻得知反轉相位的傅立葉係數

大幅減少計算總量，這就是快速傅立葉的原理。


那麼，在實作快速傅立葉轉換需要注意幾個點：

1.離散取樣數必須是2的冪次

只有這樣才能讓每個取樣點，他的反轉相位也是取樣點

2.為了加速找到每個取樣點的反轉相位，會建立一個索引表幫助搜尋

 這個索引表用圖來表示的話會看起來如下圖所示



因為形狀看起來就像蝴蝶，所以又被叫做 Butterfly Lookup Table

• 總結

本篇只是稍微介紹快速傅立葉轉換的原理，沒有打算去實作快速傅立葉轉換。

因此在最後實作快速傅立葉轉換的水渲染時會引用其他高手所公開的程式碼。

因為原理只是將奇數項偶數項分開計算，

所以不管提供的資料內容是什麼，都可以不用修改直接引用。