I'm moving my sparse voxel octree code over to the GPU and have encountered something I've never had to deal with before. GLSL does not support recursive function calls. I know I can do this with a loop somehow, but my brain is not working very well today. How to structure this code to work without recursion?:

bool SVOTGetNodeColor(in uint index, in uint x, in uint y, in uint z, out vec4 diffuse, out vec3 emission)
{
//If we have hit a terminal node return the color
uint level = svotnodes[index].params[2];
if (level == maxlevels - 1)
{
diffuse = unpackRGBA(svotnodes[index].position[3]);
emission = vec3(0.0f);
return true;
}
//Check children
for (int n = 0; n < 8; ++n)
{
if (SVOTNodeContainsNode(svotnodes[index].child[n], x, y, z))
{
if (SVOTGetNodeColor(index, x, y, z, diffuse, emission)) return true;
}
}
return false;
}

With a fixed number of recursion levels you can do it like this, but I want an arbitrary depth:

bool SVOTGetNodeColor(in uint index, in uint x, in uint y, in uint z, out vec4 diffuse, out vec3 emission)
{
int n0, n1, n2;
for (n0 = 0; n0 < 8; ++n0)
{
if (SVOTNodeContainsNode(svotnodes[index].child[n0], x, y, z))
{
index = svotnodes[index].child[n0];
for (n1 = 0; n1 < 8; ++n1)
{
if (SVOTNodeContainsNode(svotnodes[index].child[n1], x, y, z))
{
index = svotnodes[index].child[n1];
for (n2 = 0; n2 < 8; ++n2)
{
if (SVOTNodeContainsNode(svotnodes[index].child[n2], x, y, z))
{
diffuse = unpackRGBA(svotnodes[index].position[3]);
return true;
}
}
index = svotnodes[index].params[1];
break;
}
}
index = svotnodes[index].params[1];
break;
}
}
return false;
}

Okay, I think this is correct:

bool SVOTGetNodeColor(in uint index, in uint x, in uint y, in uint z, out vec4 diffuse, out vec3 emission)

{

int maxlevels = 10;

int level = 0;

uint size = svotnodes[index].params[3];

uint hsize = size / 2;

uint px,py,pz,childindex;

while (true)

{

if (level == maxlevels - 1)

{

diffuse = unpackRGBA(svotnodes[index].position[3]);

return true;

}

px = uint(x - svotnodes[index].position[0] >= size);

py = uint(y - svotnodes[index].position[1] >= size);

pz = uint(z - svotnodes[index].position[2] >= size);

childindex = svotnodes[index].child[pz*hsize*hsize + py * hsize + px];

if (childindex == 0) return false;

level++;

}

return false;

}

I think there's a mistake in your original post - the recursive call uses the same parameters.

But that't not important - I get the idea. You can transform any recursive function into a loop structure by manually maintaining the data that would otherwise be stored on the stack. Sometimes this needs to be an array with max size as big as max recursion depth, other times you may be able to collapse it into a smaller single var (for instance if you're combining the results from the recursive calls in a simple way, e.g. maintaining a running total).

I ran into one problem when I was using an index within and index like this:

child[n[level]]

The same exact code worked fine in C++ but was not giving the correct results in GLSL until I turned n[level] into a variable. Then it worked fine:

uint childindex = n[level];
child[childindex]

But yeah, the basic idea works. Kind of a weird concept I have never encountered before.

Josh Klint said:
But yeah, the basic idea works. Kind of a weird concept I have never encountered before.

After some time it became second nature to me. Actually i avoid recursion even on CPU code. At first it was harder to understand, but seems mostly a matter of habits. At current day recursive functions often end up more confusing to me.

Josh Klint said:
uint childindex = n[level]; child[childindex]

Clearly a compiler bug? Seems quite frequent in GPU land. But they fix it if you report.