This wouldn't be too hard if this wasn't mixing several worlds : the world of algorithmics, the world of C# and the world of compute shaders (in Unity).
EDIT: This is somewhat related. My scenario is worse, as each node not only has one value but a list of values.
===============
Here's what my structure looks like in C# (simplified for explaining) :
class Function {
public int type; // 0 or 1
public int param1;
public int param2;
}
class Node {
public string Id;
public List<Function> Functions;
public List<Node> Children;
}
Once loaded, you can picture it like this, if it was rendered json-style :
{
"id": "node0",
"functions": [
{ "type": 0, "param1": 5, "param2" : 6},
{ "type": 1, "param1": 7, "param2" : 8}
],
"children": [
{
"id": "node00",
"functions": [
{ "type": 0, "param1": 9, "param2" : 10},
{ "type": 1, "param1": 11, "param2" : 12}
],
"children": [
{
"id" : "node000",
"functions": [
{ "type": 0, "param1": 13, "param2" : 14},
{ "type": 1, "param1": 15, "param2" : 16},
],
"children": [] //this one's a leaf
}
]
},
{
"id": "node01",
"functions": [{ "type": 0, "param1": 15, "param2" : 16}],
"children": [] // also a leaf
}
]
}
I want to use compute shaders to compute "the" value of each node (not just the leafs!) each node's value is calculated like this :
For example, node000 would be calculated as follows :
int result0 = computeFunction(type: 0, param1: 13, param2: 14);
int result1 = computeFunction(type: 1, param1: 15, param2: 16);
int node000Sum = result0 + result1 // there can be as many terms as there are functions in the node.
// (not detailed) : repeat with parent, node00
// (not detailed) : repeat with grandparent, node0, which is also root.
int finalResult = node000Sum + node00Sum + node0Sum
We don't just want the leaves' final sum. We will also use node00Sum and node0Sum wherever needed (in other words : each node's computation result is used somewhere).
===================
That was the setup. Now my problem : I can't picture how to organize that data to have it efficiently processed by a compute shader.
I was thinking that the simplest first step is to store all the functions of all the nodes in one big flat array (pseudo-json) :
allFunctions: [
{ "type": 0, "param1": 5, "param2" : 6},
{ "type": 1, "param1": 7, "param2" : 8},
{ "type": 0, "param1": 9, "param2" : 10},
{ "type": 1, "param1": 11, "param2" : 12},
{ "type": 0, "param1": 13, "param2" : 14},
{ "type": 1, "param1": 15, "param2" : 16},
{ "type": 0, "param1": 15, "param2" : 16}
]
...Then have the shader compute each function (and only it).
...then (maybe) have a second shader pass to do the sums... (otherwise do it in C# if it's too complicated). ...then match back those sums to the original node where they belong.
But no matter what I try, the data structure quickly becomes a headache.
Creating the array of all functions and computing them is easy, but doing the sums and matching them back to the nodes is hard. For efficiency I have to work with arrays (shaders don't handle linked lists), but I also need to somehow "remember" the tree structure. As a result I quickly get entangled in some poor-man's linked lists (and overall tree) trying to juggle with the indices of the items in the array.
And even if I manage that, then it's hard to match back the sums to the original nodes.
How would you achieve that? (i.e. what needs changing in the general approach)? Is there a similar problem in literature? (I bet there is, but I'd rather not need a Ph.D. to understand it.)
Not sure I understood the question at all, but here's some advices. Firts of all - it's not good solution to use Node structure in compute shader - as you will copy "references" (basically some id in flat array) to other nodes and functions. You need to represent your tree-like structure in simpler way - from child to parent:
struct Node
{
public int parentNodeId
public int[] functionIds
}
Also you will store id of function (it looks like function's parameters, not the function itself). And the size of array of functionIds must be constant for each Node (there's no way to represent it dynamically, if you don't want to create more indirection).
Now the algorithm is how it should work. You will have a flat array with nodes, and a flat array with functions (data for them?), a flat array with int (the number of nodes for each depth), some kind of array of results. You need to calculate the sum of each node. The nodes in the array should be sorted by depth, parents at the beginning, leaves at the end. You will also have another array that will contain the number of nodes for each depth (sorted from root to leaves, just like the array of nodes themselves). After this, you can launch the computer shader.
We take an element at index zero from the array with the number of nodes for depth (most likely there will be one, the root) - N0, calculate the results for N0 elements from the array with nodes (we write these results into some resulting array), take the element at index 1 (next layer of depth), take N1 elements from the array of nodes starting from N0, calculate their own function values, add the values of the parents (parent index in the node), write the result to our some kind of array, take the element at index 2...
At the end of the execution of each depth/layer, you will need to call the "barrier" function (most likely in Unity there is one, or its analogue; in general, this is used in GLSL), so that execution occurs for all elements of the layer and the function does not start executing for children whose parents have not been calculated.
I apologize that the answer and description were so abstract
P.S. You can calculate functions indepndently, and then just use result in your node calculations
===============
EDIT by @jeancallisti
Despite my final solution being a rework of what @Artromskiy suggested, it was a goos starting point. Therefore, I explain my solution here in his post, to be able to mark it as the accepted answer without stealing the credit from him.
Here is how I did it :
For initialization I still traverse the tree and create one large array containing all the functions of all the nodes. Now the functions are shader-friendly.
I use a compute shader to compute all the functions individually, just in parallel (no summing yet).
Novelty: During traversal in step #1 above, I create a new intermediary data structure called "FunctionsGroup". It represents the bond between a node and its functions as they're stored in the large array :
class FunctionsGroup { public Node node;
// the indices of this node's functions in the large array
public int firstFunctionIndex;
public int lastFunctionIndex;
}
From there on I can do pretty much whatever I want after step #2 :
In step 4 above I didn't detail how to "traverse the tree" but note that having a reference to the Node helps a lot. To make it perfect, In step 3 (as we created the FunctionsGroups) just add a "parent" field so that the FunctionsGroups maintain the same tree structure as the original nodes.
class FunctionsGroup { //... public FunctionsGroup parent; }
Since each FunctionsGroup has a reference to the original node it's easy to traverse the FunctionsGroups one more time to assign the final result to the node.
Finally, the icing on the cake (if needed) make the FunctionsGroups shader-compatible too:
Store all the FunctionsGroups as an array, and replace the "parent" field with an int (the index of the parent in the array).
class FunctionsGroup { //... // public FunctionsGroup parent; public int parent; }
Do the same with the nodes.
8a. Put them in one large array:
Node[] allNodes = new Node[...]; // I'm not detailing!
8b. In each FunctionsGroup, use the index of the node instead of a reference to it :
class FunctionsGroup {
...
//public Node node;
public int node; // success
}
Pass ALMOST EVERYTHING to the shader. Everything's an array and the objects no longer contain references, only int indices:
Just like before, you still need to do a final traversal of the tree in C# to assign the final results to all the nodes. The difference is that now the values are ready-to-use.