KD-дерево в GLSL - PullRequest
Новая
       33

KD-дерево в GLSL

5 голосов
/ 29 июля 2010

после одного дня попыток выяснить, как реализовать kd-дерево в OpenGL / GLSL, я очень разочарован ...

Я объявляю мои KD-узлы в GLSL следующим образом: 

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

SplitPoint содержит точку разделения дерева kd, четвертый элемент вектора содержит направление splitDirection, образующее плоскость в трехмерном пространстве. DataPtr в настоящее время содержит только случайные значения в листьях дерева.

Весь массив образует Список Аннентафель .

В 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,256,0) в направлении y в узле 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

1 Ответ

4 голосов
/ 30 июля 2010

Sweet: glm и макеты :) (Вы случайно не знаете Groovounet?)

Мне кажется, я вижу здесь какие-то странные вещи

  • Ваш критерий выбора стороны дерева для рекурсии странный. Что вы ожидаете от этого? Определенно не прогулка по дереву. У вас есть доступ к последнему ShaderX? Я считаю, что # 5 дает фактический код для этого

  • Ваши данные тоже странные (может быть: вы на 100% уверены в точках расщепления?)

Может быть, вам следует проверить, что std140 действительно учитывается. Но ваш C ++ Node кажется нормальным.

...