GLSL中的KD-Tree

Question

经过一天的尝试，我仍然无法在OpenGL/GLSL中实现kd树，感到非常沮丧...

我在GLSL中这样声明我的KD节点：

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

SplitPoint保存kd树的分割点，向量的第四个元素保存着形成3D空间平面的分割方向。DataPtr目前在树叶中仅保存随机值。

整个数组形成了一个Ahnentafel列表。

在C++中，该结构如下：

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

我相信这是正确的，并将构建的树上传到缓冲区。作为检查，我将缓冲区映射到主存储器中并检查其值：

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

到目前为止看起来不错（实际上指的是在节点0中，y方向的音量分割位于(0,256,0)，-1表示没有数据）。

现在对于树遍历，我尝试了以下方法：

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);

此时屏幕上应该有随机颜色的模式。但在大多数情况下，什么也看不到。

我尝试直接从节点中获取值，并得到了正确的结果...所以我相信统一块数据的动态索引存在问题。

希望有人能在这里帮助我...因为我已经没有更多的想法了 :/

Florian

- fho

Answer 1

甜美：glm和布局 :)（你是否知道Groovounet？）

我认为我在这里看到了一些奇怪的东西。

• 您决定递归哪一侧树的标准很奇怪。您希望它做什么？绝对不是kd树遍历。您可以访问最近的ShaderX吗？我相信＃5会提供此代码。

• 您的数据也很奇怪（也许：您是否100％确定分裂点？）

也许您应该检查std140是否真正得到考虑。但是您的C ++节点似乎还可以。

- Calvin1602

---

标准是基于数据...或缺乏相同的依据。-1表示节点中没有数据，因此我必须递归，一旦指针到达叶子节点，就有数据了。数据只是未经过规范化。它在0..511的范围内。决定遍历哪个子节点的标准是基于简单平面点比较（distFromPlane = dot(point-pointOnPlane,normalOfPlane);）当我手动将“n”设置为节点并将distanceFromPlane变量输出为gl_Fragcolor.r时，计算正确。我最好的猜测是问题与动态分支相关。 - fho

而且：不，我不认识groovounet ;) 但至少glm向量在内存中布局完美，您可以直接在UBO中使用它们。 - fho

我的意思是它不是KD树遍历。它最终会选择第一个相交的体积，但它不一定包含任何东西，对吧？ - Calvin1602

啊，抱歉...是的，我之前已经删除了相关代码。 我现在会将其重新加入。为什么它应该选择第一个相交的体积？ 我认为它直接穿过树的“底部”，到达有数据的地方。 - fho

没问题...我认为问题在于这里无法从统一对象进行“动态查找”。 如果我使用纹理缓冲区来存储数据，可能会更好。 - fho