Разделение ограничивающей рамки в построении KD-дерева из «физически обоснованного рендеринга»

Я пытаюсь реализовать трассировщик лучей и использую метод построения 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 ,...); 
}

очевидно, сферы могут перекрывать друг друга.

и нет хорошей позиции разделения, которая позволила бы двум подблокам покрыть все объекты. объект, который пересекает позицию разделения, не будет находиться ни в одном подблоке. я добавил новое условие, что только когда количество объектов ниже позиции разделения плюс число выше равно количеству всех объектов в ограничивающей рамке, тогда позиция будет записана.

//update best split if this is lowest cost so far
    if( cost < bestCost && (nBelow + nAbove == nObjects ) ){
        bestCost = cost;
        bestAxis = axis;
        bestOffset = i;
    }

( nBelow + nAbove == nObjects ) всегда "false". если

если мы создадим здесь листовой узел, то 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. Надеюсь, мой плохой английский ясно объяснил вопрос...


algorithm graphics raytracing
person Clones1201    schedule 27.05.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

KD-дерево требует хранения всех объектов, пересекающих плоскость разделения, в обоих поддеревьях. Ваше предположение о том, что объект хранится только в одном из поддеревьев, просто неверно. Правильное утверждение:

( nBelow + nShared + nAbove == nObjects )

Это одна из причин, почему BVH часто превосходит KD-Tree (т. е. BVH хранит объекты только в одном из поддеревьев, поскольку ограничивающие рамки поддеревьев могут перекрываться).

Разделенная плоскость со многими пересекающимися объектами будет иметь более высокую стоимость SAH (поскольку пересекающиеся объекты учитываются 2 раза), поэтому код разделения KD-дерева по-прежнему будет пытаться минимизировать количество общих объектов (но часто будет некоторое дублирование).

person Dade916    schedule 28.05.2013