基于Unity的3d力导向图排布算法(ComputeShader)

之前需要做拓扑排布与流量展示，我研究了两种算法，其中一种是力导向图排布算法。我简单说说力导向图的思路以及为什么要使用 ComputeShader。

原理展示

我使用立方体代表节点，下面是两种算法的排布预览，本文只讨论后者。

1. 基于领域的排布图（本文不讨论）

2. 3D力导向排布图（排布中，暂未达到最优位置）

如果计算时忽略 Y 轴，就是普通的 2D 力导向图。

力导向图的原理

我采用的算法很简单，两句话就够了：

• 每个单元是一个带正电的粒子，它们每两个之间会有库仑力，力与距离的平方成反比。
• 相连单元间有弹簧，定长 L，物体距离超过 L，互相吸引，反之排斥。

根据最终受力结果，计算其位移（或者刚体施加力），即可进行排序。经过一段时间的排序，力的作用逐渐达到平衡，各粒子的状态趋于稳定。

如何计算

根据库仑力公式计算力 F1，根据弹簧形变公式计算力 F2，F合 = F1 + F2。

• 计算库仑力时，需要遍历范围内所有的粒子(a,b,c,d…)，F1 = Fa + Fb + …。
• 计算弹力时，需要根据图内边的关系寻找父子物体。

最终，根据合力计算位移即可。

为什么要使用 ComputeShader

CPU 并不适合简单且大量重复的运算，CPU 并行运算能力很差，且在大量重复运算上，其分支预测单元、寄存单元等根本无用武之地。反观 GPU，动辄就成百上千个流处理器，同时执行大量重复且简单的任务不在话下。

以 1000 个点为例，未优化情况下，每次计算库仑力时需要进行 1000 * 1000 次运算，而每次运算又至少包括三维向量求距离、除法等两个基础运算。如果把这些放在 Unity 主线程中计算，你会发现光三维向量Vector3的计算就占用了大部分 CPU 时间，而帧率也会惨不忍睹。

对于毫不相关且数量巨大的计算来说，我们完全可以把它丢到 GPU 上计算， CPU 只需赋值后等待取值即可。由于 GPU 并行任务处理极快，因此运行速度近乎于实时运行。

上文中的“毫不相关”指的是一个线程的计算不依赖于另一个线程的计算结果。我们每次计算时，所有节点位置是固定的，因此计算过程不依赖其他线程的计算结果。

当计算足够快

在使用 CPU 计算时，为了减少 CPU 代码执行量，我做了一些优化工作，例如计算 A、B 间的库仑力 F(ab)后，不再重复计算 B、A 间的库仑力，而是直接使用 -F(ab)。但即使是这样，在 700 个点以上的场景中，CPU 计算也会直接 GG。

换用 ComputeShader 后，我发现根本没必要使用上文中的优化，因为其不但增加了线程代码的复杂性，还带不来多少收益。两种方式我测试过，计算速度没啥区别，单次计算都是秒出。

结语

迁移到 GPU 上计算后，对于 5000 个点以上的情况，每帧计算 1 次基本不卡。对于 5000 点以下的情况，每帧可酌情增加计算次数。

点数增加后，CPU 与 GPU 间的数据传输量也会相应增加，为了保持效率，可以使 Shader 与 ComputeShader 共享 Buffer，使用Graphics.DrawProceduralIndirectNow直接通知 GPU 画图。直接画图的方法在绘制 1 百万个 CUBE 时，能保持帧率在 1000 以上。

直接 GPU 画图方法不适用于我的场景，因为这些点需要点击、悬浮、拖动等交互逻辑。