KD-Tree in GLSL

Question

Hi everybody,

after one day of trying to figure out how to implement a kd-tree in OpenGL/GLSL i am pretty frustrated ...

I declare my KD-Nodes like this in GLSL:

layout(std140) uniform node{
  ivec4 splitPoint;
  int dataPtr;
} nodes[1024];

SplitPoint holds the kd-tree splitpoint, the fourth element of the vector holds the splitDirection forming a plane in 3d space. DataPtr currently only holds random values in the leafs of the tree.

The whole array forms a Ahnentafel List.

In C++ the structure looks like this:

struct Node{
  glm::ivec4 splitPoint;
  GLint dataPtr;
  GLint padding[3];
};

I believe that to be correct and i upload the constructed tree in the buffer. As a check i map the buffer into main memory and inspect the values:

0x08AB6890     +0  +256    +0    +1    -1  -858993460  -858993460  -858993460
0x08AB68B0   +256    +0    +0    +0    -1  -858993460  -858993460  -858993460
0x08AB68D0   +256  +256    +0    +0    -1  -858993460  -858993460  -858993460
[...]
0x08AB7070     +0    +0    +0    +0 +2362  -858993460  -858993460  -858993460

Looking good sofar (it actually says that the volume is split at (0,256,0) in y direction in node 0, -1 is the sign for no data).

Now for the tree traversal i tried this:

float distanceFromSplitPlane;
while(nodes[n].dataPtr == -1){

  // get split direction
  vec3 splitDir = vec3(0,0,0);
  if(nodes[n].splitDir == 0)
    splitDir.x = 1;
  else if(nodes[n].splitDir == 1)
    splitDir.y = 1;
  else 
    splitDir.z = 1;


  // calculate distance of ray starting point to the split plane
  distanceFromSplitPlane = dot(startP.xyz-(nodes[n].splitPoint.xyz/511.0), splitDir);

  // depending on the side advance in the tree
  if(distanceFromSplitPlane >= 0)
    n = 2 * n + 1;
  else
    n = 2 * n + 2;
}

// we should new be located in a leaf node and therefor have a value in dataPtr
gl_FragColor = vec4(dataPtr/6000.0, 0,1,1);

At this point there should be a pattern of random colors onscreen. But in most cases there is nothing to be seen.

I tried to get values from nodes directly and get correct results ... so i believe there is something wrong with the dynamic indexing of the uniform block data.

I hope someone can help me here ... cause i am running out of ideas :/

Florian

Answer 1

Sweet : glm AND layouts :) ( Do you happen to know Groovounet ? )

I believe I see some weird things here

• Your criterion for deciding on which side of the tree to recurse is strange. What do you expect it to do ? Definitely not a kd-tree walk. Do you have access to a recent ShaderX ? I believe the #5 gives actual code for this

• Your data is weird too (maybe : are you 100% sure of the splitting points ?)

Maybe you should check that std140 is really taken into account. But you C++ Node seems ok though.