01
2021
07

使用GPU实现快速傅里叶变换

光经过一个物体(可以是小孔,也可以是任意),成的像是物的傅里叶变换。

所以想要显示夫琅禾费衍射的效果,就是求物的傅里叶变换。

二维傅里叶变换的复杂度是n*n*n*n

一个256*256的图像,傅里叶变换需要计算256*256*256*256=4294967296次,4亿次。

计算机CPU计算需要“秒”的量级。

有人发明了快速傅里叶变换,只需要2*n*n*log(n)次计算。

256*256*2*8 = 1048576次。

减少到了100万次。

但是如果是白光的话,至少需要6个颜色叠加,也就是600万次,如果是菲涅尔衍射,还需要做反变换,需要乘以2,也就是1200万次。

假设一次需要10次加减法,计算白光的菲涅尔衍射,就需要1亿2000万次计算。

计算机1秒大概能算3亿次加减法。

所以一秒也就算几次。

会很卡。

达不到一秒60帧。

所以有人提出了,用GPU做快速傅里叶变换。

我试了试,果然很快。

做了好几个星期了,总算初步成功了。

参考:

一小时学会快速傅里叶变换(Fast Fourier Transform) - 知乎 (zhihu.com)

详尽的快速傅里叶变换推导与Unity中的实现 - 知乎 (zhihu.com)

我还是用的先交换数据的顺序,再进行蝶形变换的方式。(时间上没有真的交换,而是第一轮变换的时候按照特定的顺序取值)

有两个难点:

1、蝶形变换

2、第一轮变换取值的顺序。


源码打包下载(原理)

源码打包下载(pixi-demo)

« 上一篇

相关文章:

FFT输入序列的倒序数算法设计  (2017-11-25 17:13:38)

AS3傅里叶变换  (2015-7-30 13:29:23)

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。