之前需要做拓扑排布与流量展示,我研究了两种算法,其中一种是力导向图排布算法。我简单说说力导向图的思路以及为什么要使用 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 画图方法不适用于我的场景,因为这些点需要点击、悬浮、拖动等交互逻辑。

梓喵出没博客(azimiao.com)版权所有,转载请注明链接:https://www.azimiao.com/7662.html
欢迎加入梓喵出没博客交流群:313732000

我来吐槽

*

*