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

Question

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[20];
    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?

Answer 1

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[2];
    uint count;

    void Push(float4 value_gradient)
    {
        [branch]
        switch(count++)
        {
            case 0:
                buffer[0] = value_gradient;
                break;

            default:
                buffer[1] = value_gradient;
                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.

Answer 2

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.