OpenToonz 内置的 KISS FFT基于混合基数算法的高效轻量 FFT 库使用指南【免费下载链接】opentoonzOpenToonz - An open-source full-featured 2D animation creation software项目地址: https://gitcode.com/GitHub_Trending/op/opentoonz导读本文围绕 OpenToonz 仓库第三方面组件 KISS FFT完整源码位于 thirdparty/kiss_fft展开系统讲解这一以Keep It Simple, Stupid为设计哲学的快速傅里叶变换库从 1D 复数 FFT 的十分钟快速接入、Make/CMake 双构建系统的全部配置项到混合基数算法、定点数缩放、SIMD 扩展等底层原理。读完本文你将掌握如何把 KISS FFT 以 float / double / int16_t / int32_t 任意数据类型嵌入自己的 C 程序并能理解 OpenToonz 的景深虚化Bokeh与眩光Glare特效为何以及如何调用该库完成频域卷积。一、KISS FFT 是什么为够用且简单而生的 FFT 库KISS FFT项目首页文档是一个基于**混合基数mixed-radix**原理的快速傅里叶变换实现。它的自我定位非常克制There are many great fft libraries already around. Kiss FFT is not trying to be better than any of them. It only attempts to be a reasonably efficient, moderately useful FFT that can use fixed or floating data types and can be incorporated into someones C program in a few minutes with trivial licensing.即市面上优秀的 FFT 库很多KISS FFT 并不试图超越它们它只追求三件事——合理的效率、够用的功能、以及数分钟之内即可嵌入任意 C 程序的极简集成体验并附带宽松的 BSD 许可证。从仓库目录结构看核心实现极其精简文件作用kiss_fft.h公共 API 声明与kiss_fft_scalar类型宏kiss_fft.c1D 复数 FFT 核心实现kiss_fftnd.c多维 FFTkiss_fftr.c实数优化 FFT只输出正半频谱kiss_fftndr.c多维实数 FFTkfc.cFFT 对象缓存工具kissfft.hhC 模板封装作者 Mark Borgerding 在 BACKGROUND 一节解释了创作动机当时找不到不用汇编语言的定点 FFT于是他先用浮点把理论走通最终得到一段能通过重编译轻松切换short、float、double三种数据类型的精简代码。这与 kiss_fft.h 中的宏设计一一对应——通过FIXED_POINT和kiss_fft_scalar即可在编译期切换数据类型。二、快速上手1D 复数 FFT 的十分钟接入KISS FFT 的 1D 复数 FFT 用法被刻意设计得极其直接。原文档给出的最小可运行流程如下#include kiss_fft.h kiss_fft_cfg cfg kiss_fft_alloc( nfft ,is_inverse_fft ,0,0 ); while ... ... // put kth sample in cx_in[k].r and cx_in[k].i kiss_fft( cfg , cx_in , cx_out ); ... // transformed. DC is in cx_out[0].r and cx_out[0].i kiss_fft_free(cfg);核心调用只有三个函数kiss_fft_alloc(nfft, inverse_fft, mem, lenmem)—— 创建并初始化 FFT/IFFT 的配置缓冲区plan。nfft是变换长度inverse_fft传0表示正变换、非0表示逆变换后两个参数用于内存复用见下文。kiss_fft(cfg, fin, fout)—— 执行变换。输入输出均为复数数组kiss_fft_cpx每个元素通过.r实部与.i虚部访问。kiss_fft_free(cfg)—— 释放配置缓冲区。频域数据的布局约定原文档特别强调频率域数据的排列顺序从 DC 一路排到 2π。cx_out[0]是 FFT 的DC直流bincx_out[nfft/2]是Nyquist奈奎斯特bin当该 bin 存在时。即输出按DC, 正频率, ..., Nyquist, 负频率的顺序排列正变换时fin应为f[0], f[1], ..., f[nfft-1]输出fout对应F[0], F[1], ..., F[nfft-1]见 kiss_fft.h。alloc 的内存复用机制源码级细节kiss_fft.h 对kiss_fft_alloc的第四个参数mem/lenmem做了完整说明若lenmem为NULL内部用malloc分配 cfg 缓冲区使用完毕后应free以避免内存泄漏若lenmem非NULL且mem非NULL、且*lenmem足够大cfg 会放置到用户提供的缓冲区mem中并把实际占用大小写回*lenmem返回mem若lenmem非NULL但缓冲区不足函数返回NULL并把所需最小缓冲区大小写入*lenmem可用作两次调用的探测模式。此外kiss_fft.h 还提供了两个实用 APIkiss_fft_stride(cfg, fin, fout, fin_stride)—— 每fin_stride个样本取一个输入的通用水印版本kiss_fft_next_fast_size(n)—— 返回大于等于n的最小整数且该整数只含有快速因子2、3、5。这一函数在 OpenToonz 中被大量用于将图像尺寸取整为 FFT 友好尺寸见下文第六节。超越 1D 的扩展功能原文档指出tools/目录thirdparty/kiss_fft/tools提供了一系列很酷的扩展多维 FFTkiss_fftnd/kiss_fftndr实数优化 FFTkiss_fftr只返回正半频谱即(nfft/21)个复数频率 bin快速卷积 FIR 滤波kiss_fastfir.c注意不支持定点数频谱图像生成psdpng.c依赖 libpng命令行 FFT 工具fftutil.c。核心 FFT 与绝大多数 tools 代码都能以 float、double、Q15 short 或 Q31 样本编译运行默认数据类型是 float。三、构建系统与全部配置项详解KISS FFT 同时维护两套功能等价的构建系统thirdparty/kiss_fft/CMakeLists.txt 与 thirdparty/kiss_fft/MakefileMake面向 Unix/Linux 的传统 MakefileCMake 3.6Kitware 出品的现代构建系统。支持的编译器环境包括 GCC、Clang、GNU Make以及带 CMake 的 MSVC。构建与测试的可选依赖如下依赖用途libpng编译psdpng频谱图工具libfftw3验证 kissfft 结果正确性Python 2/3 Numpy验证 kissfft 结果正确性OpenMPGCC/Clang/MSVC 支持多核 FFT 变换加速原文档同时说明面向 Windows 的 Cygwin、MinGW 环境也很可能可以构建虽然尚未实测。3.1 核心配置参数一览两个构建系统提供同名配置项Make 用KEYvalueCMake 用-DKEYvalue原文档中的完整清单如下配置项Make 写法CMake 写法说明主数据类型KISSFFT_DATATYPEdt-DKISSFFT_DATATYPEdtfloat默认/double/int16_t/int32_t/simd需目标 CPU 支持 SSEOpenMP 加速KISSFFT_OPENMP1-DKISSFFT_OPENMPON默认关闭需要编译器支持静态库KISSFFT_STATIC1-DKISSFFT_STATICON生成.aUnix/Linux或.libWindows默认生成共享库.so/.dll/.dylib关闭测试—-DKISSFFT_TESTOFFMake 下测试由make testall/make testsingle单独触发关闭工具KISSFFT_TOOLS0-DKISSFFT_TOOLSOFF不构建fastconv等命令行工具默认构建使用 allocaKISSFFT_USE_ALLOCA1-DKISSFFT_USE_ALLOCAON用alloca替代malloc/free安装前缀PREFIX/path-DCMAKE_INSTALL_PREFIX/path指定安装目录前缀3.2 配置项的底层实现这些开关并非黑盒均可在源码中直接验证数据类型CMake 在 CMakeLists.txt 中把float/double映射为编译宏kiss_fft_scalartype把int16_t/int32_t映射为FIXED_POINT16/FIXED_POINT32把simd映射为USE_SIMD并自动追加-msseGCC/Clang或/arch:SSEMSVC。这些宏在 kiss_fft.h 中直接决定kiss_fft_scalar的真实类型。非法取值会被 CMake 直接FATAL_ERROR拒绝。静态/共享CMake 在 CMakeLists.txt 中依据KISSFFT_STATIC自动设置BUILD_SHARED_LIBS共享库构建时还会追加KISS_FFT_SHARED编译定义配合 kiss_fft.h 的KISS_FFT_API实现 Windows DLL 的dllexport/dllimport符号导出。OpenMPCMake 在 CMakeLists.txt 中按编译器追加-fopenmpGCC/Clang或/openmpMSVC并将输出库名改为kissfft-datatype-openmp。alloca追加KISS_FFT_USE_ALLOCA编译定义使内部临时缓冲区走栈上分配而非堆分配。3.3 典型构建命令以静态库 int16_t 定点数据类型 OpenMP为例Make 构建make KISSFFT_DATATYPEint16_t KISSFFT_STATIC1 KISSFFT_OPENMP1 all等价 CMake 构建mkdir build cd build cmake -DKISSFFT_DATATYPEint16_t -DKISSFFT_STATICON -DKISSFFT_OPENMPON .. make all指定安装前缀/tmp/1234的安装命令Make 版make PREFIX/tmp/1234 KISSFFT_DATATYPEint16_t KISSFFT_STATIC1 KISSFFT_OPENMP1 installCMake 版mkdir build cd build cmake -DCMAKE_INSTALL_PREFIX/tmp/1234 -DKISSFFT_DATATYPEint16_t -DKISSFFT_STATICON -DKISSFFT_OPENMPON .. make all make install值得补充的是仓库中 Makefile 通过语义化版本变量KFVER_MAJOR 131、KFVER_MINOR 1、KFVER_PATCH 0管理 ABI 版本当前目录名Lz4旁并列的 thirdparty/kiss_fft 对应 KISS FFT 131.1.0 版本CMake 构建系统会在配置时自动从 Makefile 中正则提取这组版本号用于生成共享库的VERSION/SOVERSION。四、测试与验证构建完成后可用以下命令验证Make 单配置验证对应上面 int16_t 示例make KISSFFT_DATATYPEint16_t KISSFFT_STATIC1 KISSFFT_OPENMP1 testsingleCMake 验证make test全配置扩展测试套件sh test/kissfft-testsuite.sh该扩展测试套件覆盖所有可能的构建配置组合耗时约2040 分钟取决于设备性能适合报告 bug 或验证 pull request 时使用。测试基础设施位于 thirdparty/kiss_fft/test其中benchkiss.c性能基准、benchfftw.c对照 FFTW、test_real.c实数 FFT、test_simd.cSIMD 路径、testcpp.ccC 封装以及testkiss.pyNumpy 对照分别负责不同维度的验证twotonetest.c用于两音叠加的数值正确性检查。五、典型接入流程总结综合原文档 USAGE 与 BUILDING 两节把 KISS FFT 接入自有 C 工程的最短路径是将 kiss_fft.h 与 kiss_fft.c 加入工程如需多维/实数/卷积再追加对应源文件按需定义kiss_fft_scalar、FIXED_POINT等预处理宏默认 float 则无需定义调用kiss_fft_alloc→kiss_fft→kiss_fft_free三步完成一次变换注意所有参与编译的源文件必须使用一致的FIXED_POINT与kiss_fft_scalar预处理定义这正是原文档 FAQ 中混编环境错误的根源。六、在 OpenToonz 中的实战Bokeh 与 Glare 特效的频域实现KISS FFT 并非 OpenToonz 的孤立附件而是被正式纳入特效渲染管线的第三方依赖。toonz/sources/stdfx/CMakeLists.txt 将kiss_fft.c与kiss_fftnd.c编译进 stdfx 库并在第 332 行将thirdparty/kiss_fft加入头文件搜索路径。6.1 基于 FFT 的快速卷积方案光学模糊类特效景深虚化、眩光在空间域是逐像素的卷积运算计算量与核尺寸成正比KISS FFT 通过空间域 → FFT 频域相乘 → IFFT的卷积定理将其转化为逐元素乘法复杂度与核尺寸解耦。这一思路在 iwa_bokeh_util.cpp 中体现得十分完整维度取整在 iwa_bokehfx.cpp 中用kiss_fft_next_fast_size()将图像尺寸放大到只含快速因子2、3、5的 FFT 友好尺寸避免混合基数退化到慢速因子。plan 分配在 iwa_bokeh_util.cpp 中分别创建正向与反向两个 2D plankiss_fftnd_alloc(dims, ndims, false, 0, 0)正变换与kiss_fftnd_alloc(dims, ndims, true, 0, 0)逆变换。执行与复用正向kiss_fftnd(...)将图像与光瞳掩模iris变换到频域频域相乘后见multiplyFilter再做逆向kiss_fftnd(...)还原空域plan 用完立即kiss_fft_free释放。资源管理多处用QListkiss_fftnd_cfg登记所有 plan统一在特效结束时循环kiss_fft_free防止泄漏iwa_bokeh_util.cpp。6.2 眩光特效的同类实现iwa_glarefx.cpp 采用完全相同的模式先kiss_fft_next_fast_size取整光瞳尺寸再kiss_fftnd_alloc建立正变换 plan把光瞳iris变换到频域供后续多次复用。RGB 与 Alpha 通道各自维护独立的 fwd/bkwd planiwa_bokeh_util.cpp通过一次 FFT、频域逐元素相乘、一次 IFFT完成整张图像与光瞳核的快速卷积。从源码结构看KISS FFT 之所以被选中正是因为它混合基数、可缩放、无依赖、可直接编译进工程的特性与 OpenToonz 的插件化渲染框架高度契合。七、底层原理UNDER THE HOOD原文档对内部实现给出了精确描述结合源码可梳理出以下要点7.1 算法形态时域抽取的混合基数、异地out-of-placeFFTKISS FFT 使用时域抽取time decimation的混合基数算法且默认异地执行——输入与输出使用不同缓冲区。若传入相同缓冲区内部会自动创建一个临时缓冲区来承接数据。这一设计使调用方无需关心 in-place 与 out-of-place 的差异。7.2 线程安全与无静态数据核心例程不使用任何静态数据因此是线程安全的原文档特别注明 tools 目录下并非全部线程安全。这使其天然适合 OpenToonz 这类多线程渲染环境不同渲染线程可各自持有独立的 plan 与缓冲区并行执行 FFT。7.3 缩放策略浮点不缩放定点双向缩放浮点版本不做任何缩放纯粹为了速度定点版本正反两个方向都做缩放为了防止溢出。这一点也解释了原文档 FAQ 中常见的输出与预期不符问题——请先检查是否存在一个常量倍率差异scaling factor。7.4 优化的蝶形单元对因子2、3、4、5使用专门优化的蝶形butterfly实现这也是kiss_fft_next_fast_size只认可 2、3、5 因子、以及偶数长度才能用实数优化的原因。7.5 实数优化偶数长度专用实数非复数优化只对偶数长度有效它并行执行两个半长度 FFT打包进实部与虚部再通过旋转因子twiddling合并最终输出DC 到 Nyquist 的nfft/21个复数频率 binkiss_fft.h 中kiss_fftr_next_fast_size_real宏强制把尺寸取为偶数正是为此。7.6 快速卷积overlap-scrap 法kiss_fastfir.c的快速卷积滤波采用overlap-scrap重叠丢弃方法并做了轻微改动把 scrap废弃段放在尾部而非头部。八、SIMD 扩展一次并行计算 4 路 FFT仓库中的 README.simd 对KISSFFT_DATATYPEsimd模式给出专门说明。其基本思想是把 4 个 float 打包的__m128当作一个标量元素使用从而一次 FFT 调用同时完成 A、B、C、D 四路独立信号的 FFT在支持 SSE 的 Intel x86 机器上可换取23 倍加速。复数数据交错布局rA0,rB0,rC0,rD0, iA0,iB0,iC0,iD0, rA1,rB1,rC1,rD1, iA1,iB1,iC1,iD1 ...rA0为信号 A 第 0 个样本的实部纯实数数据布局rA0,rB0,rC0,rD0, rA1,rB1,rC1,rD1, ...推荐编译选项-O3 -mpreferred-stack-boundary4 -DUSE_SIMD1 -msse对齐是最大的坑SIMD 需要 16 字节对齐栈上临时变量的地址必须落在 16 字节边界上这是 SIMD 模式最常见的段错误来源。为此 kiss_fft.h 在USE_SIMD下自动将KISS_FFT_MALLOC切换为_mm_malloc(nbytes, 16)、KISS_FFT_FREE切换为_mm_free并在尺寸上做 16 字节向上取整。README.simd 也坦诚地警告该 API 不好用、文档不全并且违背了 KISS 原则Beyond here there be dragons!。它附带的pack128/unpack128示例代码来源为 Divide Concept 的 Robin未经作者实测风险自负演示了如何在 4×N 与 N×4 转置之间格式化 SIMD 数据。九、常见问题FAQ原文档 FAQ 的权威回答如下Q我能在使用 ___ 许可证的项目里用 kissfft 吗A可以见下文的许可证说明。Revised BSD 许可证兼容面极广从 GPL 到闭源商业软件都在其覆盖范围之内。Q为什么我得不到预期的输出A最常见原因有两个缩放你得到的结果与预期之间是否只差一个常量倍率混编环境所有代码必须用相同的FIXED_POINT与kiss_fft_scalar预处理定义编译。Q你能帮我写/调试代码吗A作者表示除非付费否则大概率不会但乐于回答具体而切题的问题。十、性能画像与使用边界原文档给出了一组朴素但直观的性能数据Athlon XP 2100gcc 2.96float 类型完成 10000 次 1024 点复数 FFT 耗时约0.63 秒CPU 时间处理同样数据量md5sum耗时约为其两倍变换 5 分钟 CD 音质音频nfft1024耗时不足 1 秒。对照实验中作者将 KISS FFT 与某个备受尊敬且高度优化的库文中匿称为 FFT_BRANDX对比得到四个关键结论FFT_BRANDX 有超过 10 万行代码而 kiss_fft 的核心1D 复数约500 行作者花了很长时间才让 FFT_BRANDX 跑起来使用 FFT_BRANDX 的简单程序体积 522KB而类似功能的 kiss_fft 程序仅18KB且未做体积优化FFT_BRANDX 在默认模式下大约比 KISS FFT快一倍。因此作者给出的边界十分清醒——DO NOT: 如果需要全世界最快的 FFT 就别用 KISS FFT也别要求添加会让代码膨胀的功能并留下一句耐人寻味的设计哲学Sometimes simpler is better, even if its not better.有时更简单更好即使它并非更好。十一、许可证与后续 TODO许可证Revised BSD License详见 COPYING。概括为可自由使用与修改注明出处即可不提供任何担保。该许可证对 GPL 开源软件与闭源商业软件都兼容。kiss_fft.h 头部的版权声明2003-2010, Mark Borgerding与 SPDX 标识BSD-3-Clause与此一致。TODO 清单原文档记录供贡献者参考为奇数长度 FFT 增加实数优化文档化/重新审视输入输出的缩放策略撰写kiss_fastfir.c中 overlap尾部 scrap快速卷积滤波的说明文档用定点数全面测试tools/下代码已知kiss_fastfir.c不工作其余待测。结语KISS FFT 以约 500 行核心代码同时交付了混合基数 FFT、四类数据类型、线程安全、宽松许可证、分钟级集成的组合是嵌入式与桌面软件中够用就好路线的典型代表。在 OpenToonz 中它被 stdfx 模块用于 Bokeh 景深虚化与 Glare 眩光特效的频域卷积实现了核尺寸无关的高效模糊如果你正在为自己的 C/C 工程寻找一个零依赖、可定点、可快速集成的 FFT 方案thirdparty/kiss_fft 的这套源码与文档就是现成的参考答案。【免费下载链接】opentoonzOpenToonz - An open-source full-featured 2D animation creation software项目地址: https://gitcode.com/GitHub_Trending/op/opentoonz创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OpenToonz 内置的 KISS FFT：基于混合基数算法的高效轻量 FFT 库使用指南
OpenToonz 内置的 KISS FFT基于混合基数算法的高效轻量 FFT 库使用指南【免费下载链接】opentoonzOpenToonz - An open-source full-featured 2D animation creation software项目地址: https://gitcode.com/GitHub_Trending/op/opentoonz导读本文围绕 OpenToonz 仓库第三方面组件 KISS FFT完整源码位于 thirdparty/kiss_fft展开系统讲解这一以Keep It Simple, Stupid为设计哲学的快速傅里叶变换库从 1D 复数 FFT 的十分钟快速接入、Make/CMake 双构建系统的全部配置项到混合基数算法、定点数缩放、SIMD 扩展等底层原理。读完本文你将掌握如何把 KISS FFT 以 float / double / int16_t / int32_t 任意数据类型嵌入自己的 C 程序并能理解 OpenToonz 的景深虚化Bokeh与眩光Glare特效为何以及如何调用该库完成频域卷积。一、KISS FFT 是什么为够用且简单而生的 FFT 库KISS FFT项目首页文档是一个基于**混合基数mixed-radix**原理的快速傅里叶变换实现。它的自我定位非常克制There are many great fft libraries already around. Kiss FFT is not trying to be better than any of them. It only attempts to be a reasonably efficient, moderately useful FFT that can use fixed or floating data types and can be incorporated into someones C program in a few minutes with trivial licensing.即市面上优秀的 FFT 库很多KISS FFT 并不试图超越它们它只追求三件事——合理的效率、够用的功能、以及数分钟之内即可嵌入任意 C 程序的极简集成体验并附带宽松的 BSD 许可证。从仓库目录结构看核心实现极其精简文件作用kiss_fft.h公共 API 声明与kiss_fft_scalar类型宏kiss_fft.c1D 复数 FFT 核心实现kiss_fftnd.c多维 FFTkiss_fftr.c实数优化 FFT只输出正半频谱kiss_fftndr.c多维实数 FFTkfc.cFFT 对象缓存工具kissfft.hhC 模板封装作者 Mark Borgerding 在 BACKGROUND 一节解释了创作动机当时找不到不用汇编语言的定点 FFT于是他先用浮点把理论走通最终得到一段能通过重编译轻松切换short、float、double三种数据类型的精简代码。这与 kiss_fft.h 中的宏设计一一对应——通过FIXED_POINT和kiss_fft_scalar即可在编译期切换数据类型。二、快速上手1D 复数 FFT 的十分钟接入KISS FFT 的 1D 复数 FFT 用法被刻意设计得极其直接。原文档给出的最小可运行流程如下#include kiss_fft.h kiss_fft_cfg cfg kiss_fft_alloc( nfft ,is_inverse_fft ,0,0 ); while ... ... // put kth sample in cx_in[k].r and cx_in[k].i kiss_fft( cfg , cx_in , cx_out ); ... // transformed. DC is in cx_out[0].r and cx_out[0].i kiss_fft_free(cfg);核心调用只有三个函数kiss_fft_alloc(nfft, inverse_fft, mem, lenmem)—— 创建并初始化 FFT/IFFT 的配置缓冲区plan。nfft是变换长度inverse_fft传0表示正变换、非0表示逆变换后两个参数用于内存复用见下文。kiss_fft(cfg, fin, fout)—— 执行变换。输入输出均为复数数组kiss_fft_cpx每个元素通过.r实部与.i虚部访问。kiss_fft_free(cfg)—— 释放配置缓冲区。频域数据的布局约定原文档特别强调频率域数据的排列顺序从 DC 一路排到 2π。cx_out[0]是 FFT 的DC直流bincx_out[nfft/2]是Nyquist奈奎斯特bin当该 bin 存在时。即输出按DC, 正频率, ..., Nyquist, 负频率的顺序排列正变换时fin应为f[0], f[1], ..., f[nfft-1]输出fout对应F[0], F[1], ..., F[nfft-1]见 kiss_fft.h。alloc 的内存复用机制源码级细节kiss_fft.h 对kiss_fft_alloc的第四个参数mem/lenmem做了完整说明若lenmem为NULL内部用malloc分配 cfg 缓冲区使用完毕后应free以避免内存泄漏若lenmem非NULL且mem非NULL、且*lenmem足够大cfg 会放置到用户提供的缓冲区mem中并把实际占用大小写回*lenmem返回mem若lenmem非NULL但缓冲区不足函数返回NULL并把所需最小缓冲区大小写入*lenmem可用作两次调用的探测模式。此外kiss_fft.h 还提供了两个实用 APIkiss_fft_stride(cfg, fin, fout, fin_stride)—— 每fin_stride个样本取一个输入的通用水印版本kiss_fft_next_fast_size(n)—— 返回大于等于n的最小整数且该整数只含有快速因子2、3、5。这一函数在 OpenToonz 中被大量用于将图像尺寸取整为 FFT 友好尺寸见下文第六节。超越 1D 的扩展功能原文档指出tools/目录thirdparty/kiss_fft/tools提供了一系列很酷的扩展多维 FFTkiss_fftnd/kiss_fftndr实数优化 FFTkiss_fftr只返回正半频谱即(nfft/21)个复数频率 bin快速卷积 FIR 滤波kiss_fastfir.c注意不支持定点数频谱图像生成psdpng.c依赖 libpng命令行 FFT 工具fftutil.c。核心 FFT 与绝大多数 tools 代码都能以 float、double、Q15 short 或 Q31 样本编译运行默认数据类型是 float。三、构建系统与全部配置项详解KISS FFT 同时维护两套功能等价的构建系统thirdparty/kiss_fft/CMakeLists.txt 与 thirdparty/kiss_fft/MakefileMake面向 Unix/Linux 的传统 MakefileCMake 3.6Kitware 出品的现代构建系统。支持的编译器环境包括 GCC、Clang、GNU Make以及带 CMake 的 MSVC。构建与测试的可选依赖如下依赖用途libpng编译psdpng频谱图工具libfftw3验证 kissfft 结果正确性Python 2/3 Numpy验证 kissfft 结果正确性OpenMPGCC/Clang/MSVC 支持多核 FFT 变换加速原文档同时说明面向 Windows 的 Cygwin、MinGW 环境也很可能可以构建虽然尚未实测。3.1 核心配置参数一览两个构建系统提供同名配置项Make 用KEYvalueCMake 用-DKEYvalue原文档中的完整清单如下配置项Make 写法CMake 写法说明主数据类型KISSFFT_DATATYPEdt-DKISSFFT_DATATYPEdtfloat默认/double/int16_t/int32_t/simd需目标 CPU 支持 SSEOpenMP 加速KISSFFT_OPENMP1-DKISSFFT_OPENMPON默认关闭需要编译器支持静态库KISSFFT_STATIC1-DKISSFFT_STATICON生成.aUnix/Linux或.libWindows默认生成共享库.so/.dll/.dylib关闭测试—-DKISSFFT_TESTOFFMake 下测试由make testall/make testsingle单独触发关闭工具KISSFFT_TOOLS0-DKISSFFT_TOOLSOFF不构建fastconv等命令行工具默认构建使用 allocaKISSFFT_USE_ALLOCA1-DKISSFFT_USE_ALLOCAON用alloca替代malloc/free安装前缀PREFIX/path-DCMAKE_INSTALL_PREFIX/path指定安装目录前缀3.2 配置项的底层实现这些开关并非黑盒均可在源码中直接验证数据类型CMake 在 CMakeLists.txt 中把float/double映射为编译宏kiss_fft_scalartype把int16_t/int32_t映射为FIXED_POINT16/FIXED_POINT32把simd映射为USE_SIMD并自动追加-msseGCC/Clang或/arch:SSEMSVC。这些宏在 kiss_fft.h 中直接决定kiss_fft_scalar的真实类型。非法取值会被 CMake 直接FATAL_ERROR拒绝。静态/共享CMake 在 CMakeLists.txt 中依据KISSFFT_STATIC自动设置BUILD_SHARED_LIBS共享库构建时还会追加KISS_FFT_SHARED编译定义配合 kiss_fft.h 的KISS_FFT_API实现 Windows DLL 的dllexport/dllimport符号导出。OpenMPCMake 在 CMakeLists.txt 中按编译器追加-fopenmpGCC/Clang或/openmpMSVC并将输出库名改为kissfft-datatype-openmp。alloca追加KISS_FFT_USE_ALLOCA编译定义使内部临时缓冲区走栈上分配而非堆分配。3.3 典型构建命令以静态库 int16_t 定点数据类型 OpenMP为例Make 构建make KISSFFT_DATATYPEint16_t KISSFFT_STATIC1 KISSFFT_OPENMP1 all等价 CMake 构建mkdir build cd build cmake -DKISSFFT_DATATYPEint16_t -DKISSFFT_STATICON -DKISSFFT_OPENMPON .. make all指定安装前缀/tmp/1234的安装命令Make 版make PREFIX/tmp/1234 KISSFFT_DATATYPEint16_t KISSFFT_STATIC1 KISSFFT_OPENMP1 installCMake 版mkdir build cd build cmake -DCMAKE_INSTALL_PREFIX/tmp/1234 -DKISSFFT_DATATYPEint16_t -DKISSFFT_STATICON -DKISSFFT_OPENMPON .. make all make install值得补充的是仓库中 Makefile 通过语义化版本变量KFVER_MAJOR 131、KFVER_MINOR 1、KFVER_PATCH 0管理 ABI 版本当前目录名Lz4旁并列的 thirdparty/kiss_fft 对应 KISS FFT 131.1.0 版本CMake 构建系统会在配置时自动从 Makefile 中正则提取这组版本号用于生成共享库的VERSION/SOVERSION。四、测试与验证构建完成后可用以下命令验证Make 单配置验证对应上面 int16_t 示例make KISSFFT_DATATYPEint16_t KISSFFT_STATIC1 KISSFFT_OPENMP1 testsingleCMake 验证make test全配置扩展测试套件sh test/kissfft-testsuite.sh该扩展测试套件覆盖所有可能的构建配置组合耗时约2040 分钟取决于设备性能适合报告 bug 或验证 pull request 时使用。测试基础设施位于 thirdparty/kiss_fft/test其中benchkiss.c性能基准、benchfftw.c对照 FFTW、test_real.c实数 FFT、test_simd.cSIMD 路径、testcpp.ccC 封装以及testkiss.pyNumpy 对照分别负责不同维度的验证twotonetest.c用于两音叠加的数值正确性检查。五、典型接入流程总结综合原文档 USAGE 与 BUILDING 两节把 KISS FFT 接入自有 C 工程的最短路径是将 kiss_fft.h 与 kiss_fft.c 加入工程如需多维/实数/卷积再追加对应源文件按需定义kiss_fft_scalar、FIXED_POINT等预处理宏默认 float 则无需定义调用kiss_fft_alloc→kiss_fft→kiss_fft_free三步完成一次变换注意所有参与编译的源文件必须使用一致的FIXED_POINT与kiss_fft_scalar预处理定义这正是原文档 FAQ 中混编环境错误的根源。六、在 OpenToonz 中的实战Bokeh 与 Glare 特效的频域实现KISS FFT 并非 OpenToonz 的孤立附件而是被正式纳入特效渲染管线的第三方依赖。toonz/sources/stdfx/CMakeLists.txt 将kiss_fft.c与kiss_fftnd.c编译进 stdfx 库并在第 332 行将thirdparty/kiss_fft加入头文件搜索路径。6.1 基于 FFT 的快速卷积方案光学模糊类特效景深虚化、眩光在空间域是逐像素的卷积运算计算量与核尺寸成正比KISS FFT 通过空间域 → FFT 频域相乘 → IFFT的卷积定理将其转化为逐元素乘法复杂度与核尺寸解耦。这一思路在 iwa_bokeh_util.cpp 中体现得十分完整维度取整在 iwa_bokehfx.cpp 中用kiss_fft_next_fast_size()将图像尺寸放大到只含快速因子2、3、5的 FFT 友好尺寸避免混合基数退化到慢速因子。plan 分配在 iwa_bokeh_util.cpp 中分别创建正向与反向两个 2D plankiss_fftnd_alloc(dims, ndims, false, 0, 0)正变换与kiss_fftnd_alloc(dims, ndims, true, 0, 0)逆变换。执行与复用正向kiss_fftnd(...)将图像与光瞳掩模iris变换到频域频域相乘后见multiplyFilter再做逆向kiss_fftnd(...)还原空域plan 用完立即kiss_fft_free释放。资源管理多处用QListkiss_fftnd_cfg登记所有 plan统一在特效结束时循环kiss_fft_free防止泄漏iwa_bokeh_util.cpp。6.2 眩光特效的同类实现iwa_glarefx.cpp 采用完全相同的模式先kiss_fft_next_fast_size取整光瞳尺寸再kiss_fftnd_alloc建立正变换 plan把光瞳iris变换到频域供后续多次复用。RGB 与 Alpha 通道各自维护独立的 fwd/bkwd planiwa_bokeh_util.cpp通过一次 FFT、频域逐元素相乘、一次 IFFT完成整张图像与光瞳核的快速卷积。从源码结构看KISS FFT 之所以被选中正是因为它混合基数、可缩放、无依赖、可直接编译进工程的特性与 OpenToonz 的插件化渲染框架高度契合。七、底层原理UNDER THE HOOD原文档对内部实现给出了精确描述结合源码可梳理出以下要点7.1 算法形态时域抽取的混合基数、异地out-of-placeFFTKISS FFT 使用时域抽取time decimation的混合基数算法且默认异地执行——输入与输出使用不同缓冲区。若传入相同缓冲区内部会自动创建一个临时缓冲区来承接数据。这一设计使调用方无需关心 in-place 与 out-of-place 的差异。7.2 线程安全与无静态数据核心例程不使用任何静态数据因此是线程安全的原文档特别注明 tools 目录下并非全部线程安全。这使其天然适合 OpenToonz 这类多线程渲染环境不同渲染线程可各自持有独立的 plan 与缓冲区并行执行 FFT。7.3 缩放策略浮点不缩放定点双向缩放浮点版本不做任何缩放纯粹为了速度定点版本正反两个方向都做缩放为了防止溢出。这一点也解释了原文档 FAQ 中常见的输出与预期不符问题——请先检查是否存在一个常量倍率差异scaling factor。7.4 优化的蝶形单元对因子2、3、4、5使用专门优化的蝶形butterfly实现这也是kiss_fft_next_fast_size只认可 2、3、5 因子、以及偶数长度才能用实数优化的原因。7.5 实数优化偶数长度专用实数非复数优化只对偶数长度有效它并行执行两个半长度 FFT打包进实部与虚部再通过旋转因子twiddling合并最终输出DC 到 Nyquist 的nfft/21个复数频率 binkiss_fft.h 中kiss_fftr_next_fast_size_real宏强制把尺寸取为偶数正是为此。7.6 快速卷积overlap-scrap 法kiss_fastfir.c的快速卷积滤波采用overlap-scrap重叠丢弃方法并做了轻微改动把 scrap废弃段放在尾部而非头部。八、SIMD 扩展一次并行计算 4 路 FFT仓库中的 README.simd 对KISSFFT_DATATYPEsimd模式给出专门说明。其基本思想是把 4 个 float 打包的__m128当作一个标量元素使用从而一次 FFT 调用同时完成 A、B、C、D 四路独立信号的 FFT在支持 SSE 的 Intel x86 机器上可换取23 倍加速。复数数据交错布局rA0,rB0,rC0,rD0, iA0,iB0,iC0,iD0, rA1,rB1,rC1,rD1, iA1,iB1,iC1,iD1 ...rA0为信号 A 第 0 个样本的实部纯实数数据布局rA0,rB0,rC0,rD0, rA1,rB1,rC1,rD1, ...推荐编译选项-O3 -mpreferred-stack-boundary4 -DUSE_SIMD1 -msse对齐是最大的坑SIMD 需要 16 字节对齐栈上临时变量的地址必须落在 16 字节边界上这是 SIMD 模式最常见的段错误来源。为此 kiss_fft.h 在USE_SIMD下自动将KISS_FFT_MALLOC切换为_mm_malloc(nbytes, 16)、KISS_FFT_FREE切换为_mm_free并在尺寸上做 16 字节向上取整。README.simd 也坦诚地警告该 API 不好用、文档不全并且违背了 KISS 原则Beyond here there be dragons!。它附带的pack128/unpack128示例代码来源为 Divide Concept 的 Robin未经作者实测风险自负演示了如何在 4×N 与 N×4 转置之间格式化 SIMD 数据。九、常见问题FAQ原文档 FAQ 的权威回答如下Q我能在使用 ___ 许可证的项目里用 kissfft 吗A可以见下文的许可证说明。Revised BSD 许可证兼容面极广从 GPL 到闭源商业软件都在其覆盖范围之内。Q为什么我得不到预期的输出A最常见原因有两个缩放你得到的结果与预期之间是否只差一个常量倍率混编环境所有代码必须用相同的FIXED_POINT与kiss_fft_scalar预处理定义编译。Q你能帮我写/调试代码吗A作者表示除非付费否则大概率不会但乐于回答具体而切题的问题。十、性能画像与使用边界原文档给出了一组朴素但直观的性能数据Athlon XP 2100gcc 2.96float 类型完成 10000 次 1024 点复数 FFT 耗时约0.63 秒CPU 时间处理同样数据量md5sum耗时约为其两倍变换 5 分钟 CD 音质音频nfft1024耗时不足 1 秒。对照实验中作者将 KISS FFT 与某个备受尊敬且高度优化的库文中匿称为 FFT_BRANDX对比得到四个关键结论FFT_BRANDX 有超过 10 万行代码而 kiss_fft 的核心1D 复数约500 行作者花了很长时间才让 FFT_BRANDX 跑起来使用 FFT_BRANDX 的简单程序体积 522KB而类似功能的 kiss_fft 程序仅18KB且未做体积优化FFT_BRANDX 在默认模式下大约比 KISS FFT快一倍。因此作者给出的边界十分清醒——DO NOT: 如果需要全世界最快的 FFT 就别用 KISS FFT也别要求添加会让代码膨胀的功能并留下一句耐人寻味的设计哲学Sometimes simpler is better, even if its not better.有时更简单更好即使它并非更好。十一、许可证与后续 TODO许可证Revised BSD License详见 COPYING。概括为可自由使用与修改注明出处即可不提供任何担保。该许可证对 GPL 开源软件与闭源商业软件都兼容。kiss_fft.h 头部的版权声明2003-2010, Mark Borgerding与 SPDX 标识BSD-3-Clause与此一致。TODO 清单原文档记录供贡献者参考为奇数长度 FFT 增加实数优化文档化/重新审视输入输出的缩放策略撰写kiss_fastfir.c中 overlap尾部 scrap快速卷积滤波的说明文档用定点数全面测试tools/下代码已知kiss_fastfir.c不工作其余待测。结语KISS FFT 以约 500 行核心代码同时交付了混合基数 FFT、四类数据类型、线程安全、宽松许可证、分钟级集成的组合是嵌入式与桌面软件中够用就好路线的典型代表。在 OpenToonz 中它被 stdfx 模块用于 Bokeh 景深虚化与 Glare 眩光特效的频域卷积实现了核尺寸无关的高效模糊如果你正在为自己的 C/C 工程寻找一个零依赖、可定点、可快速集成的 FFT 方案thirdparty/kiss_fft 的这套源码与文档就是现成的参考答案。【免费下载链接】opentoonzOpenToonz - An open-source full-featured 2D animation creation software项目地址: https://gitcode.com/GitHub_Trending/op/opentoonz创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考