Question regarding Octree Texture & LOD

Hey

I’ve been reading up on Octree textures for use on the GPU, with this GPU Gems article the main source (the relevant info is under section named “Accessing the Structure: Tree Lookup”).

I’m currently working on it at the moment(bit of a head wrecker in parts :P), but I was thinking about how LOD would work with it.

With the method above, the alpha value indicates if the value stored in the RGB component of the current pixel in the 3D texture is empty (alpha = 0), points to another value (alpha = 0.5f) or contains actual data (alpha = 1f).

So, for example, the texture stores an octree of depth 5. What if I only want to draw as far as depth 4. Would this require another texture? Or would you have to calculate the colour of each node at level 4 by averaging the child nodes (this would seem rather costly to perform in real time).

You mean the texture lod, like mipmaps ?
It seems covered in “Mipmapping” section. My cursory read did not allow me to really understand it, I need to spend more time on the whole page

I feel so stupid! I don’t know how I missed that, must have been staring at the monitor for too long yesterday. Thanks

Ok, so I’ve been trying to implement the octree to texture part of the article. I’m having a bit or trouble, so if any of you kind people could help me out, that would be great!

I have written it out on paper, and checked that the values in the array are what they should be. I do have a question in regard to this. The cell in the indirection grid can store the index of the another indirection grid. So for example, it would store an index such as (1, 0, 0) to indicate the second the grid in the 3DTexture. Do I need to do anything with this? Like ensure the indexes are between [0, 1] for each dimension?

I have implemented their lookup code, and I am incorporating it into a gpu raycaster. This is where I get lost (wish I could add a breakpoint to the shader and step through it :D). I want to pass the position of the current ray into the tree_lookup function, however the comments from NVidia say that the function accepts lookup coordinates. How to I convert the position to coordinates?

Currently, nothing is displayed when I pass in the current ray position to the lookup function.

Any help or advice would be great, thanks!

I thought it would be best to post the code for storing the octree to a texture.

The octree CPU is is made up of a rootNode, which is subdivided into 8 nodes, which are subdivided into 8 nodes etc. Each node has an array of pointers to child nodes. These pointers are initally set to 0, to indicate that the node is not pointing to anything. Each node also has a stored value, which represents the average scalar value of all the scalars within the node (I’m using the octree to subdivide volume data).

It’s a lot of code, but I’m pretty sure it is correct, and the problem is in the shader side and not the texture creation.

void Octree::InitOctreeTexture(GLubyte **octreeData)
{
    // Get the number of nodes in the octree
    int numNodes = pow(8.0, (double)currentSubDivision) + 1;

    // Number of girds stored in u v w
    Su = ceil(cube_root(numNodes));
    Sv = Su;
    Sw = Su;

    // The number of indirection grids stored in the pool
    S = Vector3<float>(Su, Sv, Sw);

    // Number of cells in a grid per dimension
    N = 2;

    // Index of the current maximum indirection gird
    maxI = Vector3<int>(0, 0, 0);
    
    // Size of the array based on S & N
    const int arraySize = ( (S.x * N) * (S.y * N) * (S.z * N));// * 4;

    // create array and set all values to 0
    octreeData = new GLubyte*[arraySize];
    for (int i = 0; i < arraySize; i++)
    {
        octreeData[i] = new GLubyte[4];
		
        for (int j = 0; j < 4; j++)
        {
            octreeData[i][j] = 0;
        }
    }
    
    // Start loading the data to the array
    FillNode(octreeData, rootNode, Vector3<int>(0, 0, 0));

}

void Octree::FillNode(GLubyte **data, Node *node, Vector3<int> I)
{
    Vector3<int> *offsets = new Vector3<int>(0, 0, 0);

    int arrayIndex = 0;
    
if (node->subDivided)
{
    for (int i = 0; i < 8; i++)
    {
	switch(i)
	{
   	    case TOP_LEFT_FRONT:

		offsets = new Vector3<int>(0, 0, 0);
		arrayIndex = GetArrayIndex(I, offsets);
		break;

	    case TOP_LEFT_BACK:

	        offsets = new Vector3<int>(0, 0, 1);
		arrayIndex = GetArrayIndex(I, offsets);
		break;

	    case TOP_RIGHT_BACK:

		offsets = new Vector3<int>(1, 0, 1);
		arrayIndex = GetArrayIndex(I, offsets);
		break;

	    case TOP_RIGHT_FRONT:

		offsets = new Vector3<int>(1, 0, 0);
		arrayIndex = GetArrayIndex(I, offsets);
		break;

	    case BOTTOM_LEFT_FRONT:

		offsets = new Vector3<int>(0, 1, 0);
		arrayIndex = GetArrayIndex(I, offsets);
		break;

	    case BOTTOM_LEFT_BACK:

		offsets = new Vector3<int>(0, 1, 1);
		arrayIndex = GetArrayIndex(I, offsets);
		break;

	    case BOTTOM_RIGHT_BACK:

		offsets = new Vector3<int>(1, 1, 1);
		arrayIndex = GetArrayIndex(I, offsets);
		break;

	    case BOTTOM_RIGHT_FRONT:

		offsets = new Vector3<int>(1, 1, 0);
		arrayIndex = GetArrayIndex(I, offsets);
		break;
	}
        // This child is empty, so set the current cell to be empty
	if (node->children[i] == 0)
	{
	    data[arrayIndex][0] = (GLubyte)OCTREE_EMPTY_ALPHA;
	    data[arrayIndex][1] = (GLubyte)OCTREE_EMPTY_ALPHA;
	    data[arrayIndex][2] = (GLubyte)OCTREE_EMPTY_ALPHA;
	    data[arrayIndex][3] = (GLubyte)OCTREE_EMPTY_ALPHA;
	}
        // Else if child is subdivided, add another indirection grid
	else if (node->children[i]->subDivided)
	{
	    Vector3<int> newI = Vector3<int>(maxI.x + 1, maxI.y, maxI.z);

	    if (newI.x > (Su - 1))
	    {
		newI.x = 0;
		newI.y++;

		if (newI.y > (Sv - 1))
		{
	    	    newI.y = 0;
		    newI.z++;

		}
	    }

	    maxI = newI;

	    data[arrayIndex][0] = (GLubyte)newI.x;
	    data[arrayIndex][1] = (GLubyte)newI.y;
	    data[arrayIndex][2] = (GLubyte)newI.z;
	    data[arrayIndex][3] = (GLubyte)OCTREE_NODE_ALPHA;

	    FillNode(data, node->children[i], newI);
	}
        // Else this child is a leaf node, add scalar value to array
        else
	{
	    data[arrayIndex][0] = (GLubyte)node->children[i]->totalScalarValue;
	    data[arrayIndex][1] = (GLubyte)OCTREE_EMPTY_ALPHA;
	    data[arrayIndex][2] = (GLubyte)OCTREE_EMPTY_ALPHA;
	    data[arrayIndex][3] = (GLubyte)OCTREE_LEAF_ALPHA;
	}
    }
}

    delete offsets;
}

int Octree::GetArrayIndex(Vector3<int> I, Vector3<int> *offsets)
{
    int x, y, z;

    x = ( I.x * (N) ) + (offsets->x);
    y = ( I.y * ( (Su * (N) ) * N) ) + (offsets->y * ( Su * (N) ) );
    z = ( I.z * ( ( (Su * (N) ) * N) * Sv) ) + (offsets->z * (Su * (N)) * (Sv * N));

    return x + y + z;
}