Fast Fourier Transform on Ne0's Bloghttps://ne0.io/tags/fast-fourier-transform/Recent content in Fast Fourier Transform on Ne0's BlogHugozh-CNne0.wu@outlook.com (Ne0)ne0.wu@outlook.com (Ne0)Sun, 03 Sep 2023 00:00:00 +0000基于 FFT 的无互锁的装箱算法https://ne0.io/posts/3282821360/Sun, 03 Sep 2023 00:00:00 +0000ne0.wu@outlook.com (Ne0)https://ne0.io/posts/3282821360/3D 打印中, 如何在打印机的工作空间 (通常是一个长方体) 中摆放物体是一个重要的问题. 首先, 装箱问题本身是一个 NP-Hard 的问题; 其次, 求解这一问题需要进行大规模的碰撞检测, 而对于非凸物体的碰撞检测并没有好的算法能实现; 最后, 如何检测摆放好的物体之间是否有互锁 (也就是说打印之后是否能分开) 也是一个重要的问题, 而这一问题目前并没有有效的算法能解决. 本文将介绍 Dense, Interlocking-Free and Scalable Spectral Packing of Generic 3D Objects 这篇文章中提出的基于快速 Fourier 变换的装箱算法. 这篇文章的主要贡献是将 FFT 应用于基于体素的碰撞检测以大大加快检测速度, 并通过这一算法给出了检测物体之间是否能分离的方法.