Jak zrobiłem kd-tree

Uwaga! Informacje na tej stronie mają ponad 5 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

# Jak zrobiłem kd-tree

Sat
07
Jun 2008

Do testowania kolizji promienia od kamery do świateł napisałem sobie drzewo kd, w którym przechowałem odniesienia do trójkątów mapy. Właściwie to jest swobodne drzewo kd, analogicznie do swobodnych drzew ósemkowych.

Interesujący jest sposób, w jaki go zapisałem. Wcześniej zawsze węzeł drzewa był u mnie prawdziwym, alokowanym dynamicznie obiektem przechowującym własny wektor trójkątów. Tym razem wszystko mieści się w zwykłych tablicach:

struct NODE
{
  BOX Bounds; // AABB węzła
  unsigned FirstTriangle;
  unsigned TriangleCount;
  unsigned SubnodeIndex[2];
};

// To jest kd-tree
std::vector<NODE> Nodes;
std::vector<unsigned> Triangles;
// To jest siatka mapy
std::vector<unsigned> Indices;
std::vector<VERTEX> Vertices;

Pierwszy element tablicy węzłów to korzeń. Każdy węzeł przechowuje indeksy swoich dwóch podwęzłów SubnodeIndex odnoszące się do tablicy Nodes. Każdy węzeł wyznacza też zakres trójkątów, które do niego należą - FirstTriangle i TriangleCount odnoszące się do tablicy Triangles. Każdy element Triangles to z kolei numer pierwszego z indeksów wierzchołków należących do danego trójkąta, odnoszący się do tablicy Indices. Natomiast Indices to już zwykły bufor indeksów siatki, odnoszący się do tablicy Vertices.

Jak takie drzewo powstaje? Funkcja rekurencyjna dla danego węzła z Nodes tworzy dwa podwęzły, a zakres trójkątów należących do tego węzła rozdziela na trzy podzakresy: te które trafiają do pierwszego podwęzła, które trafiają do drugiego podwęzła i które zostają w tym węźle. W tym celu wykonuje dwukrotnie algorytm podziału zakresu na dwa podzakresy - tego samego którego używa QuickSort. On ma złożoność liniową i jest do dyspozycji w STL jako algorytm std::partition.

Podsumowując, takie podejście do tworzenia i przechowywania drzewa podziału przestrzeni ma liczne zalety: drzewo zajmuje mniej pamięci, szybciej się wylicza, łatwiej się zapisuje i odczytuje z pliku. Ma też jedną wadę - wymaga używania zamotanych odwołań takich jak to:

x = Vertices[Indices[Triangles[Nodes[
  NodeIndex].FirstTriangle+ti]+vi]].Pos.x;

Profesjonaliści pewnie mnie wyśmieją że dopiero teraz na to wpadłem, a początkujący i tak tego nie zrozumieją, ale co mi zależy... Piszę to na co mam ochotę :)

Comments | #algorithms Share

Comments

STAT NO AD
[Stat] [STAT NO AD] [Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2019