Kd-stablo

Kd-stablo (eng. kd-tree) je struktura podataka za podjelu prostora i organiziranje objekata u k-dimenzionalnom prostoru. Kd-stablo je poseban slučaj BSP stabla kod kojeg su ravnine podjele poravnate sa koordinatnim osima. Oktalno stablo je poseban slučaj kd-stabla kod kojeg osi podjele prolaze kroz središte oktanta koji se dijeli. Na slici 10 je prikazano 3-dimenzionalno kd-stablo.

Slika 10: kd-stablo za 3 dimenzije

Generiranje kd-stabla

Kd-stablo se generira tako da se prvo odabere jedna ravnina za podjelu. Ta ravnina se bira ciklički prolazeći kroz osi (npr. korijen će biti podijeljen s ravninom koja je poravnata s x-osi, njegova djeca bi onda bila podijeljena s ravninom koja je poravnata s y-osi, a njihova djeca bi bila podijeljena s ravninom koja je poravnata sa z-osi, ravnina podijele na sljedećoj razini bi bila poravnata s x-osi). Ravnina podjele se bira kao medijan objekata u trenutnom čvoru s obzirom na koordinate na osi koja se koristi za podjelu. Ovo će rezultirati balansiranim kd-stablom kod kojeg je svaki list jednako udaljen od korijena stabla.

Primjene kd-stabla

Budući da je kd-stablo specijalni slučaj BSP stabla, a oktalno stablo specijalni slučaj oktalnog stabla kd-stablo se može koristiti za iste primjene. Te primjene se odnose na podjelu prostora i modela na manje dijelove, a time i smanjenje broja potrebnih proračuna i ubrzavanje algoritama. To znači da je kd-stablo primjenjivo u postupku praćenja zrake, kod uklanjanja geometrije s obzirom na volumen pogleda, detekciju kolizije i u drugim područjima.