Rewrite this function without using recursion?

[Josh]

GLSL does not support recursive function calls. How to structure this function without using 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;
}

 

[Slastraf]

you need to iterate svotnodes 
pseudocode

foreach svotnodes as svotnode :
 level = svotnodes[index].params[2];
 if level == maxlevels -1) : [...]
 for n < 8:
	if (SVOTNodeContainsNode(svotnodes[index].child[n], x, y, z))
        {
             foreach svotnodes as svotnode2 :
             level2 = svotnodes[index].params[2];
             if level2 == maxlevels -1) : [...]
        }
	

if you want to find the "terminal node" you need to iterate over all nodes, however I dont think the index changes so that might be a problem.
Sorry dont have much time to look over this

[Josh]

If the number of levels is fixed, you can do it like this, but I want it to work with an arbitrary number of levels:

for (int n0 = 0; n0 < 8; ++n0)
{
    if (SVOTNodeContainsNode(svotnodes[index].child[n0], x, y, z))
    {
        index = svotnodes[index].child[n0];
        for (int n1 = 0; n1 < 8; ++n1)
        {
            if (SVOTNodeContainsNode(svotnodes[index].child[n1], x, y, z))
            {
                index = svotnodes[index].child[n1];
                for (int n2 = 0; n2 < 8; ++n2)
                {
                    if (SVOTNodeContainsNode(svotnodes[index].child[n2], x, y, z))
                    {
                        diffuse = unpackRGBA(svotnodes[index].position[3]);
                    }
                }
                index = svotnodes[index].parent;
            }
        }
        index = svotnodes[index].parent;
    }
}

 

[Josh]

I feel like using arrays for the n and index values puts us a little bit closer...

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

 

[Josh]

I feel like the answer will be something like this...

bool SVOTGetNodeColor(in uint rootindex, in uint x, in uint y, in uint z, out vec4 diffuse, out vec3 emission)
{
    uint index[8];
    index[0] = rootindex;
    int level = 0;
    int n[8];
    int maxlevels = 8;
    while (true)
    {
        level++;
        for (n[level] = 0; n[level] < 8; ++n[level])
        {
            if (SVOTNodeContainsNode(svotnodes[index[level]].child[n[level]], x, y, z))
            {
                index[level] = svotnodes[index[level-1]].child[n[level-1]];
                if (level == maxlevels - 1)
                {
                    diffuse = unpackRGBA(svotnodes[index[level]].position[3]);
                    return true;
                }
            }
        }
        level--;
    }
    return false;
}

 

[Vida Marcell]

Its strange to see the person who can answer any c++ question ask a question.

[Josh]

I've never had to do this before! XD

Okay, for the simplest function 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;
}

The ray tracing function is more complicated because it involves a branching hierarchy.

[Slastraf]

this is not the prime beginner example for recursion, too