FFT镜头效果已经完成，并集成入KlayGE开发版中，命名为FFTLensEffectPostProcess。除此之外，还写了一个命令行工具，用于产生镜头效果的纹理。虽然FFT的方法能在一个pass内产生各种复杂的镜头效果，但目前性能低于默认的多重gaussian blur。其中最主要的开销来自于FFT本身，下面就着重就讨论一下GPU FFT的进展和未来。
前不久我在用Pixel Shader实现FFT的时候，提到了用Compute Shader来实现FFT效率可以更高。之前Ocean的例子里就有用于实现波浪模拟的CS4 FFT（从NV的例子改进而成），它的输入和输出是1D Buffer的形式。为了更通用，在进入KlayGE核心的时候改成了2D Texture的形式。可惜的是，CS4不能写入纹理，就需要增加一个把Buffer转成纹理的PS。CS5的实现基本类似于CS4，但改为直接读写纹理。现在CS4和CS5的FFT都已经实现完毕，终于可以比较一下性能。
算法的差异
由于输出的限制，pixel shader的FFT只能实现最简单的radix-2算法，每次输入2个复数、生成2个复数。而compute shader支持任意写入，所以可以实现更复杂的radix-4、radix-8甚至multi-radix。在这里我实现的是radix-8，每次处理8个复数。所以512×512只需要6个pass，比PS的18个pass少得多。
另一个区别在于，因为CS4的限制，CS4 FFT的数据都以float2的Buffer来保存（实部和虚部），只有3通道，每个pixel的RGB是排列成R0/R1/R2…Rn G0/G1/G2…Gn B0/B1/B2…Bn的形式。而在PS和CS5的实现中，仍然保留R0G0B0A0/R1G1B1A1/R2G2B2A2…RnGnBnAn的排列，并且是4通道的。所以单从计算来说，CS4少一个通道，标量的计算量和带宽耗用量都会小于PS和CS5。
性能比较
这里的输入是512×512，分别在高端、中端、低端显卡上同时比较了正向FFT和逆向IFFT。
| NV GTX580 FFT/IFFT (ms) | AMD HD6670 FFT/IFFT (ms) | NV 9800GT FFT/IFFT (ms) | NV NVS4200M FFT/IFFT (ms) | |
|---|---|---|---|---|
| PS | 2.12/2.28 | 7.09/7.22 | 7.99/8.16 | 33.30/33.30 |
| CS4 | 0.70/0.70 | 2.44/2.47 | 3.33/3.45 | 10.36/9.80 |
| CS5 | 0.76/0.76 | 2.40/2.39 | 不支持 | 8.86/8.81 |
从结果可以看出，CS4的实现能比PS快2倍左右，一方面来自于radix-8带来的计算量减小，另一个方面来自于pass数减少。有趣的是，除了高端的GTX580，其他卡上CS5都比CS4略快。在NV的卡上，以64-bit为单位的IO效率高于其他格式，这一点也给CS4带来了一定的优势。
反过来，这个结果也说明了CS5还有优化的空间。CS5多做了1/3的计算，IO效率也不不是最高的，却能于CS4相似甚至更快。
未来
这个版本里的FFT镜头效果暂时告一段落，除了继续优化之外，以后还有很多算法级别的改进值得尝试。
数据格式
现在所有的中间格式都是ABGR32F。如果用ABGR16F的话，在暗处将会出现一些artifact。如果这样的artifact在可以接受的范围内，或者用其他补偿方法来改进16F的精度，速度就能大大提高。输入和输出格式则不受限制。输入格式可以用ABGR16F、或者更少的B10G11R11F，输出格式可以用ABGR16F。
纯实数FFT
因为输入数据是张只有实数部分的图像，对纯实数做FFT的结果是头尾对称的，可以利用这一点做算法上的改进。FFTW里面，这个变换称为r2c。对n长度的输入它只需要输出n/2+1个复数，而不用n个，IO和计算量都可以减小。另一个尝试的方向是DCT。作为FFT的特例，经过特殊寻址安排的DCT也符合卷积定理。所以用输入输出都是纯实数的DCT也能减少IO。
sFFT
今年一月，MIT的一个团队提出了Spare Fast Fourier Transform（sFFT）的算法。在输入信号稀疏的情况下，sFFT能比传统FFT快之百倍。由于用于镜头效果的输入仅仅是亮度大于某个阈值的pixel，稀疏程度非常高，所以也可能可以利用sFFT来进行加速。
Comments