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

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?

• I think that the slowdown you'll receive from trying to force a square into a circular hole will outweigh the speedup you gain from being able to do fast matrix math Jul 22, 2018 at 0:30
• But anyways, here developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch06.html Jul 22, 2018 at 0:31

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.

• So this should be doable on Vulkan, but also one layer at the time? Jul 22, 2018 at 7:42
• @Karlovsky120 If you really want to try Vulkan, go ahead, but I would favour compute for this. Don't see why it wouldn't be possible under Vulkan, though. Jul 22, 2018 at 7:46
• Doesn't Vulkan have compute shaders and command queues for this very reson? To unify openGL and openCL capabilities under one framework (among many other things)? Jul 22, 2018 at 15:15
• @Karlovsky120 You're right. Thanks for pointing this out. Seems your road is clear then - good luck! Jul 22, 2018 at 15:16
• Vulkan is heavily inspired from OpenCL in terms of command queues and synchronization (only better), and the compute shaders in vulkan are pretty much the same as OpenGL (later versions). Additionally you CAN do recursion on the gpu with cuda, though it won't prove usefull for OP's use case stackoverflow.com/questions/3644809/does-cuda-support-recursion Aug 28, 2018 at 21:15