连载四:基于GPU模拟高真实度的动态交互水系统

2009-9-14 作者: 金堃 来源: e-works

关键字: GPU 动态交互水系统 傅里叶变换 Philips频谱 

在室外场景的渲染中,水是最富有美感,也是最能增加真实气氛的物体之一。本文介绍了一种完全基于GPU的实时渲染方法,可模拟高真实度的动态交互水系统。

  2.9 快速傅里叶变换(FFT)

  如果按照常规的傅里叶变换式进行计算,其效率是很低的,这是因为它没有考虑到虚指数函数自身的半波奇对称性和周期性。傅里叶变换是一个原信号乘虚指数并累加的过程,因为虚指数自身的性质,我们会进行很多重复运算。

  设原信号(即时轴)离散化为N个元素,频域离散化为M个频率级别,虚指数信号是形如的格式,为了方便起见,我们改写成,它代表频率为u的虚指数函数在时轴x刻度上的值,那么有

  根据三角函数的周期性和半波奇对称性可得:,事实上计算这两个式子时,与结果绝对值相同的 在前面就已经计算出了,如果能利用这一结果,这两步的计算就可以大大简化;类似的还有等等,这些情况都可以用快速傅里叶变换来跳过这些多余的乘虚指数的操作。

  一维傅里叶变换会对所有的离散点进行采样,假设x有N个,那么计算整个傅里叶变换的处理量是(每个x累加N次),而通过FFT的迭代可以将处理量从降低到。当我们把整个乘虚指数、叠加的流程中多余的部分简化,并重新整理时,就变成了一个蝶形运算的流程式(即Butterfly式)。


图8  四元素一维傅里叶变换的蝶形图


图9  八元素一维傅里叶变换的蝶形图




责任编辑:熊东旭