如何在基于位置的动力学中并行化碰撞约束

Question

我正在尝试在 OpenCL 中实现 PBD 算法。在 original paper 中，算法表示为

(1) forall vertices i
(2)     initialize x[i]=x0[i], v[i]=v0[i], w[i]=1/m[i]
(3)endfor
(4)loop
(5)    forall vertices i do v[i]←v[i]+∆t*w*i*f_ext(x[i])
(6)    dampVelocities(v1,...,vN)
(7)    forall vertices i do p[i]←x[i]+∆t*v[i]
(8)    forall vertices i do generateCollisionConstraints(xi→pi)
(9)    loop solverIterations times
(10)        projectConstraints(C1,...,CM+Mcoll,p1,...,pN)
(11)   endloop
(12)   forall vertices i
(13)       v[i]←(p[i]−x[i])/∆t(14)x[i]←p[i]
(15)   endfor
(16)   velocityUpdate(v1,...,vN)
(17)endloop

第 8 步是最难有效并行化的。我目前正在做的是使用常规 3D 网格（表示为单个缓冲区），我首先在其中插入所有粒子。接下来我迭代相邻的单元格并检查碰撞。但是当实际检测到碰撞时我该怎么办？我不能保存可变大小的向量，也不能将约束“附加”到缓冲区，因为这需要原子操作，而原子操作不是并行的。在 GPU 上实现 PBD 的一些有效方法是什么？

Answer 1

到目前为止我发现这可能是实现它的最佳方法是

使用atomicAdd模拟堆栈，类似于人脸剔除的方式https://vkguide.dev/docs/gpudriven/compute_culling/
为每个线程预分配一个小堆栈，并让每个线程将约束附加到该私有堆栈。然后，您可以在对数时间内将所有这些堆栈有效地连接到一个大数组中。为了更直观地显示它，考虑 3 个堆栈，每个最大长度为 2

Stack 1: |_|_|  (empty stack)
Stack 2: |A|_|  (stack with one element)
Stack 3: |B|C|  (stack fully filled up to its maximum length)

然后像这样连接这些堆栈

|A|_|_|_|B|C|

现在迭代计算每个元素应该移动多少，这等于它左边的空元素数（含）。创建第二个缓冲区来保存这些空元素的数量。这个缓冲区的初始状态是

|0|1|1|1|0|0|  (each cell is 0 if it is empty or 1 otherwise)

在第二次迭代中，您对位置 i 和 i+1 处的单元格值求和并将结果存储在 i+1.

中

|0|1|2|2|1|0|  (each cell holds number of filled cells up to 2 places to the left, including itself)

在第三次迭代中，您将单元格 i 和 i+2

的值相加

|0|1|2|3|3|2|  (each cell holds number of filled cells up to 4 places to the left, including itself)

在第四次迭代中，您将单元格 i 和 i+4

的值相加

|0|1|2|3|3|3|  (each cell holds number of filled cells up to 8 places to the left, including itself)

现在您知道 A 应该向左移动 0，B 向左移动 3，C 向左移动 3 , 得出最终结果

|A|B|C|_|_|_|

如何在基于位置的动力学中并行化碰撞约束

How to parallelize collision constraints in position based dynamics

gpu

opencl

game-physics

gpgpu

physics-engine