Solving a recursive problem in the geometry (or any other) shader

Question

I would like to calculate an effect of an external force on a binary tree (wind on a tree).

It's a recursive function - take a (parent) node and calculate the angle to rotate all of the nodes "younger" than the parent around the parent for the same angle according to the force applied. Then do it for the child nodes and repeat until you reach the leaves. If I'm calculating it right this is a problem of O(k * 2^n) complexity, where n is the depth of the tree and k number of nodes.

Since we rotate a lot of stuff (which is a nice matrix multiplication), it would be really nice to do it on the GPU. The problem is that this code needs to run as many times as the depth of the tree, and not all of it can run in parallel.

For each node (vertex) I have to modify all the nodes (vertices) downstream that vertex. This, however, ruins the parallelism of the GPU, since child nodes cannot be calculated before their parents, but the effect should lessen further up the tree I traverse. How do I make the GPU do this efficiently, if you consider the fact that I'll be having multiple trees in the scene?

Basically, on one hand, I have the same code that needs to execute for every vertex in the same way, but on the other, it needs to be executed in order, only vertices on the same level can run concurrently.

Any idea on how to solve this problem and what to do?

If I were to use Vulkan instead, would that broaden my options?

Answer 1

The problem is that this code needs to run as many times as the depth of the tree, and not all of it can run in parallel.

...which is the prime indicator NOT to process this as such on the GPU. GPU architecture suits problems where the individually-processed elements are independent of one another.

If I were to use Vulkan instead, would that broaden my options?

No. Using a different API doesn't change the underlying GPU architecture, which doesn't suit this kind of problem as such. In any case, you may be better off using compute (OpenCL, CUDA) here.

Any idea on how to solve this problem and what to do?

Break down the problem to enable the sort of massively parallel processing where the GPU excels. At any given pass (phase), there can be no data dependencies, which is your current problem.

Run through multiple kernel passes, where each pass represents a depth in the tree; this would take in parent transforms from currentDepth-1 and output the child transforms for currentDepth.

Queueing work on the GPU

In OpenCL we submit commands via the command queue; in CUDA we submit streams. These will then run on the GPU in the same order as you have specified them in your CPU-side code.

These terms should help you to find the resources you need to code up a solution.