# How to evaluate a binary expression tree in HLSL without recursion or a stack?

I'm currently working on a dual contouring implementation for which I want to create procedural terrain based on layers of noise. Both, the terrain generation and the mesh creation via dual contouring run on the GPU in compute shaders.

For configurating the terrain generation I previously changed the specific compute shader's source code itself to generate different layers of FBM noise and combine them with various CSG operations (e.g. union, intersection, difference) to arrive at the final terrain. But this offers very little flexibility, e.g. I cannot change the terrain generation at runtime.

So in order to get more flexibility for configuring the terrain generation, I've started implementing a graph tool (similiar to ShaderLab) using XNode: Red (leaf) nodes are operands, grey (internal) nodes are operators (either binary or unary) and the green (root) node is simple the output node. On the GPU side each operator (internal node) equals a function, e.g. a function that creates the output of the noise node.

The idea is that I can visually create a binary expression tree (with additional unary operators), upload it to the GPU using a StructuredBuffer<NoiseGraphNode> where NoiseGraphNode is

struct NoiseGraphNode
{
uint leftNodeIndex;
uint rightNodeIndex;
uint nodeType;
uint dataIndex;         // Index used in conjunction with nodeType
// to access a node's data located in a
// nodeType-specific StructuredBuffer, e.g.
// the noise parameters in case of a noise node.
};


and have that graph evaluated by the GPU's compute shader for generating the noise that represents the final terrain. Normally such a graph would be evaluated using a recursive approach, something like:

evaluate(node) {
if(node has children){
left_val = evaluate(node->left);
right_val = evaluate(node->right);

// find operation symbol for node and use it as
// val = left_val operation right_val

return val;
}
else {
return node_value;
}
}


Pseudo-code taken from https://stackoverflow.com/questions/10769174/evaluating-expression-trees.

HLSL doesn't support recursion though! Another way would be to emulate the recursive implementation using a stack and a while loop (after all recursion is leveraging the call stack). But creating a stack structure in HLSL like so

struct NoiseGraphStack
{
uint buffer;
uint count;

void Push(uint number)
{
buffer[count++] = number;   // Doesn't work because an array reference
// cannot be used as an l-value.
}

float Pop()
{
return buffer[--count];
}

static NoiseGraphStack Create()
{
NoiseGraphStack stack;
stack.count = 0;

return stack;
}
};


doesn't work either because it requires the while loop to be unrolled which isn't possible.

Note: The exact error message referred to in the code above is "array reference cannot be used as an l-value; not natively addressable, forcing loop to unroll."

So is it possible to evaluate a binary expression tree without recursion or a stack? Can I perhaps somehow preprocess the necessary steps for evaluating such a tree on the CPU (where I can use recursion just fine) first and linearize them before I send them to the GPU?

• How often do you need to change terrain generation algorithms (not just parameters, but the whole logical tree of operations) between one frame and the next? It seems like it would be much more efficient to just compile your nodegraph to shader code in the background when you need a new algorithm (say you're approaching a new biome), then swap to the newly compiled shader when appropriate. Jun 6, 2021 at 14:30
• @DMGregory, I do not intend to change the expression tree frequently. I merely would like to have the option to change it at runtime in the first place (as of now). I was considering just generating the appropriate source code for a given expression tree and recompiling the compute shader which would probably be possible inside the Unity editor. But would that also be possible when I build the game and run it as a standalone application? Jun 6, 2021 at 14:45
• @DMGregory, actually just being able to do it in the Unity editor would be fine if it is possible to create a compute shader asset through a script. E.g. I would like to have a button inside the node editor that triggers the code generation for the current expression tree and creates the compute shader asset containing that code. At runtime I could simply link the appropriate compute shader as necessary. For Shaders there's "ShaderUtil.CreateShaderAsset(...)" to do something along those lines. But I couldn't find anything similar for compute shaders. Jun 6, 2021 at 15:23

Alright, I didn't manage to evaluate the binary expression tree without a stack entirely. I do need a stack but the stack capacity only has to be 2 elements in order to evaluate any binary expression tree (regardless how large). At least I think that's true, I didn't formally proof it...

I basically do two things:

1. Before I upload the tree to the GPU, I traverse it in preorder on the CPU using recursion.
2. I then upload the tree to the GPU in the traversed order. Now the GPU can simply iterate over each node in the uploaded node buffer and (using the stack mentioned initially) compute the final output.

Here's an example tree with some annotations and the GPU side algorithm for clarity: The data for each node, e.g. the noise parameters of a noise node, are uploaded in separate buffers. My HLSL node struct looks like this:

struct NoiseGraphNode
{
uint nodeType;
uint dataIndex;
};


The nodeType of each node is used in conjunction with the dataIndex to choose the correct buffer and index into it.

Finally, my HLSL stack struct looks like this:

struct NoiseGraphStack
{
float4 buffer;
uint count;

{
[branch]
switch(count++)
{
case 0:
break;

default:
break;
}
}

void Push(float3 position)
{
Push(float4(position, 0.0f));
}

float4 Pop()
{
return buffer[--count];
}

static NoiseGraphStack Create()
{
NoiseGraphStack stack;
stack.count = 0;

return stack;
}
};


Note: I'm using a switch case for pushing because that avoids the l-value issue mentioned in the original question.

One thing I noticed (through trial and error) is that I needed to tag certain branches in my code with the [branch] attribute in order for my code to compile. Without that attribute Unity threw the following error during compilation of the compute shader: Plaintext for people googling the error message: Shader error in 'VoxelVolume': Compilation failed for kernel 'GenerateVoxelVolume' [0x80004005 - unknown error] 'internal error: no storage type for block output

Note: I'm still using a lot of branching to compute the output of the graph on the GPU but, as far as I understand, that shouldn't be a problem because the branching is based on data that is identical to all threads in a warp, meaning no branch divergence will occur.

When implementing something similar, only with post order traversal (evaluation of mathematical structures for ray marching), i encountered the same error with "array reference cannot be used as an l-value; not natively addressable".
Since for postorder traversal you need a stack with size about equal to the height of the tree, i could not use your solution of using a switch case for accessing, but i noticed that using not a global array as the stack but declaring the stack in a function does the trick and will not force the loop to unroll.