Drzewo BSP

Z Wikipedii

Drzewo BSP (BSP - Binary Space Partition; Drzewo podziału binarnego przestrzeni) - struktura danych stosowana w grafice komputerowej służąca do:

• opisywania wielokątów, nawet wielokątów "z dziurami" - umożliwia szybsze stwierdzenie czy punkt leży wewnątrz/na zewnątrz figury, co jest wykorzystywane m.in. w zadaniach interakcji z użytkownikiem w programach graficznych;
• opisywania brył zbudowanych z siatek wielokątów - jednym z zastosowań jest wykonywanie na bryłach geometrycznych operacji boolowskich: suma, część wspólna, różnica (patrz: CSG);
• opisywania całych scen trójwymiarowych - łatwiejsza detekcja kolizji (istotne w grach komputerowych), łatwiejsze śledzenie promieni oraz usuwanie niewidocznych powierzchni.

Drzewo BSP to drzewo binarne, które powstaje poprzez rekurencyjny podział przestrzeni za pomocą hiperpłaszczyzn (proste w przestrzeni 2D, płaszczyzny w 3D, itd.), tak że w węźle drzewa znajduje się obiekt który leży na hiperpłaszczyźnie, natomiast w obu poddrzewach zapisane są wszystkie obiekty, które w całości leżą po danej stronie hiperpłaszczyzny. Jeśli obiektu nie da się zakwalifikować, musi zostać podzielony, tak aby stało się to możliwe. Na głębokość drzewa BSP oraz jego zrównoważenie ma wypływ wybór hiperpłaszczyzn dzielących.

Wadą drzew BSP jest powolny proces tworzenie takiej struktury. Dlatego nie nadają się do opisu np. dynamicznych scen trójwymiarowych, gdzie obiekty przemieszają się, są dodawane lub usuwane. Często jednak są stosowane rozwiązania hybrydowe - jeśli statyczna część sceny jest duża, wówczas jest ona opisywana za pomocą drzewa BSP, natomiast części ruchome (np. drzwi budynków), ściany które mogą zostać usunięte przechowywane są w jakiś inny sposób.

Na rysunku powyżej pokazano, w jaki sposób tworzone jest drzewo BSP opisujące wielokąt wklęsły. Widać, że dwie krawędzie musiały zostać podzielone (e-d, f-g). W tym przykładzie proste dzielące pokrywają się z krawędziami figury (tak jest najczęściej). Czarne kwadraciki oznaczają puste poddrzewo.

[edytuj] Zobacz też

Inne struktury podziału przestrzennego:

• drzewa kd - przestrzeń jest dzielona przez płaszczyzny równoległe do głównych płaszczyzn układu współrzędnych (XY, YZ, XZ)
• drzewa ósemkowe - przestrzeń jest dzielona na jednakowe sześciany (prostopadłościany)