Podział pola ograniczania w konstrukcji drzewa KD z "fizycznie opartego renderowania" - algorytm, grafika, raytracing

Próbuję zaimplementować raytracer i używam metody konstrukcji kd-tree z książki „Physicall Based Rendering”.

książka używa metody zwanej SAH, aby wybraćpozycja do podziału obwiedni. wybiera pozycję podziału od krawędzi obwiedni obiektów na scenie. krawędzie są sortowane od niskiej do wysokiej wzdłuż osi.

i znaleźć najlepszy podział w ten sposób:

//<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;
}

losowo umieściłem w scenie 100 sfer:

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 ,...);
}

oczywiście kule mogą się pokrywać.

i nie ma dobrej podzielonej pozycji, która mogłabypozwól, aby dwie skrzynki pomocnicze pokryły wszystkie obiekty. obiekt, który przekroczy pozycję podziału, nie będzie w żadnej pod-skrzynce. dodałem nowy warunek, że tylko wtedy, gdy liczba obiektów poniżej pozycji podziału plus liczba powyżej jest równa liczbie wszystkich obiektów w obwiedni, pozycja zostanie zapisana.

//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) jest zawsze „fałszywy”. Jeśli

jeśli utworzymy tutaj węzeł liścia, wówczas drzewo kd jest bez znaczenia, po prostu zdegenerowało się do przejścia sekwencyjnego, ponieważ całe drzewo zawiera tylko jeden węzeł liścia.

więc czy jest jakieś rozwiązanie? dzięki!

oto kilka definicji:

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 mam nadzieję, że mój słaby angielski wyjaśnił pytanie wyraźnie ...

Odpowiedzi:

2 dla odpowiedzi № 1

Drzewo KD wymaga przechowywania wszystkich przechodzących obiektówpłaszczyzna podziału w obu drzewach podrzędnych. Twoje założenie, że obiekt jest przechowywany tylko w jednym drzewie podrzędnym, jest po prostu niepoprawne. Prawidłowe stwierdzenie brzmi:

(nBelow + nShared + nAbove == nObjects)

Jest to jeden z powodów, dla których BVH często przewyższa drzewo KD (tj. BVH przechowuje obiekty tylko w jednym z drzew podrzędnych, ponieważ pola ograniczające pod drzewem mogą się nakładać).

Płaszczyzna podziału z wieloma obiektami skrzyżowanymi będziemają wyższy koszt SAH (ponieważ przecinające się obiekty są liczone 2 razy), więc kod podziału drzewa KD nadal będzie próbował zminimalizować liczbę współużytkowanych obiektów (ale często będzie powielanie).

---