я пытаюсь реализовать рэйтрейсер и я использую KD-дерево методы строительства из книги „Physicall Based Rendering“.Split ограничивающего параллелепипеда в конструкции KD-дереве из «Физически рендеринга»
книга использует метод SAH для выбора позиции для разделения ограничивающей рамки. выбирает положение разделения по краям ограничивающих окон объектов на сцене. Края сортируются от низкого до высокого вдоль оси.
и его найти лучший раскол следующим образом:
//<Compute cost of all splits for axis to find best>
int nBelow = 0, nAbove = nObjects;
for(int i = 0; i < 2 * nObjects ; ++i){
if(edges[axis][i].type == END) -- nAbove;
float edget = edges[axis][i].t;
if(edget > nodeBounds.pMin[axis] &&
edget < nodeBounds.pMax[axis]){
//<Compute cost for split at ith edges>
}
if(edges[axis][i].type == START) ++ nBelow;
}
я поставил 100 сфер в сцене случайно, как это:
for(int i = 1 ; i < 100 ; ++ i){
float x,y,z,r;
x = 800 * float(rand())/float(RAND_MAX) - 200 ;
y = 800 * float(rand())/float(RAND_MAX) - 200 ;
z = 400 * float(rand())/float(RAND_MAX) - 100 ;
r = 50 * float(rand())/float(RAND_MAX) + 25;
initSphere(..., Point3D(x,y,z) , r ,...);
}
очевидно, сферы могут накладываться друг на друга.
и нет хорошего положения разделения, которое могло бы позволить двум суб-коробкам покрывать все объекты. объект, который пересекает разделенную позицию, не будет в каком-либо субблоке. Я добавил новое условие, что только когда количество объектов под разделенным положением плюс число выше, равное количеству всех объектов в ограничивающей рамке, тогда будет записана позиция.
(nBelow + nAbove == nObjects) всегда является «ложным». если
Если мы создаем листовой узел здесь, то kd-дерево не имеет смысла, оно просто вырождается в последовательный обход, потому что все дерево будет содержать только один листовой узел.
так, есть ли решение? благодаря!
здесь несколько определений:
struct Point3D{
float x,y,z;
}
struct BBox{
float pMax[3],pMin[3];
}
struct BoundEdge{
float t;
int type; // START or END
}
BoundEdge *edges[3];
ps.i надеюсь, что мой бедный английский объяснил вопрос ясно ...