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?