Zaczniemy od przypadku najłatwiejszego do narysowania, a zatem najbardziej odpowiedniego do przedstawienia zasady. Przyjmiemy, że d=2, a zatem kostka jest kwadratem (albo, ogólniej, prostokątem). Cała kostka jest reprezentowana przez korzeń drzewa. Kostkę i każdy boks dzielimy na cztery przystające kwadraty (lub prostokąty). Każdy wierzchołek drzewa, który nie jest liściem, ma cztery poddrzewa.

Drzewa czwórkowe można zastosować w naturalny sposób do rozwiązywania różnych zadań dwuwymiarowych, takich jak

• Przeszukiwanie obszarów, na przykład w geograficznej bazie danych,

• Konstrukcyjna geometria figur płaskich,

• Algorytmy widoczności,

• Transmisja obrazów,

• Wykrywanie kolizji w ruchu płaskim, np. w animacji.

Omówimy reprezentację płaskiej figury F, mieszczącej się w prostokącie. Z każdym wierzchołkiem drzewa zwiążemy atrybut, zwany umownie kolorem. Wierzchołek jest

• czarny, jeśli wnętrze boksu reprezentowanego przez ten wierzchołek jest zawarte w figurze F,

• biały, jeśli wnętrze boksu jest rozłączne z figurą F,

• szary, jeśli przecięcie wnętrza boksu i brzegu figury F jest niepuste.

Nie ma powodu, aby dzielić wierzchołki czarne i białe, zatem są one zwykle liśćmi drzewa, a wszystkie wierzchołki wewnętrzne są szare. Istnieją też na ogół szare liście, co wynika z ograniczenia wysokości drzewa, które określa osiągalną dokładność reprezentowania figur. Można jednak umieścić w szarych liściach dodatkową informację, która pozwala na przykład zbadać, czy dany punkt, należący do boksu reprezentowanego przez szary liść, należy do F, czy nie. Informacja taka może być prostsza niż reprezentacja całej figury F.

Przykład: Niech figura F będzie wielokątem krzywoliniowym, którego brzeg składa się z kilku krzywych sklejanych. Podział boksów wykonujemy do chwili, gdy w każdym boksie, który zawiera fragment brzegu, fragment taki składa się z co najwyżej dwóch połączonych łuków wielomianowych. Sprawdzenie, czy dany punkt p należy do F polega na odnalezieniu w drzewie liścia, który zawiera ten punkt, i jeśli ten liść jest szary, to zbadanie, po której stronie brzegu leży punkt p, jest dosyć łatwe.

Drzewa ósemkowe spełniają w zastosowaniu do figur przestrzennych te same role, co drzewa czwórkowe dla figur płaskich. Korzeń drzewa ósemkowego reprezentuje kostkę trójwymiarową (prostopadłościan lub w szczególności sześcian), a jego wierzchołki reprezentują boksy, będące prostopadłościanami podobnymi do całej kostki. Drzewo ósemkowe może być podstawową reprezentacją figury przestrzennej, a także pomocniczą strukturą danych, która ma na celu przyspieszenie pewnych obliczeń.

Przykład: Opisana wcześniej konstrukcyjna geometria brył wielościennych wymaga wyznaczenia wszystkich krawędzi przecięcia ścian danych brył. Jeśli liczby ścian brył oznaczymy symbolami n1 i n2, to ,,bezpośrednia” procedura

ma koszt rzędu n1⁢n2, nawet jeśli liczba znalezionych krawędzi jest znacznie mniejsza. Można jednak dla każdej ściany pierwszej bryły znaleźć kostkę, w której ta ściana jest zawarta, a następnie zbudować drzewo ósemkowe, którego każdy wierzchołek zawiera listę ścian pierwszej bryły, mających niepuste przecięcie z odpowiednim boksem. Następnie, dla każdej ściany drugiej bryły wyszukujemy boksy, z którymi ta ściana przecina się i sprawdzamy, czy istnieją wspólne krawędzie ze ścianami pierwszej bryły znajdującymi się w odpowiednich listach. Ta metoda jest opłacalna zwłaszcza wtedy, gdy brzegi brył składają się z dużej liczby małych ścian.

Kolejne przykłady zastosowania takich drzew, to wykrywanie kolizji obiektów poruszających się w scenie, która nie zmienia się w czasie oraz wyznaczanie przecięć promieni z obiektami w metodzie śledzenia promieni. W obu tych przypadkach oszczędności czasowe mogą być bardzo duże.

Wadą drzew czwórkowych i ósemkowych może być bardzo duża liczba poddrzew każdego wierzchołka; jeśli liście mają taką samą reprezentację jak wierzchołki wewnętrzne, to mają cztery lub osiem pustych wskaźników.

Druga cecha, która może być zaletą lub wadą (zależnie od sytuacji) to brak adaptacji kierunkowej; na wszystkich poziomach rekurencyjnego podziału boksy są podobne do wyjściowej kostki; nie można w związku z tym dostosować się do ,,wydłużonych” obiektów.

Aby to umożliwić, można zamiast drzewa czwórkowego lub ósemkowego zastosować drzewo binarne, w którym boksy dzieli się na dwie części — prostokąty albo prostopadłościany, i można przy tym dowolnie (na przykład kilka razy kolejno tak samo) wybrać kierunek podziału.

Przedstawione na rysunku drzewo binarne powstało z zastosowaniem adaptacyjnego wyboru kierunku podziału boksów. Pokazany płat był dzielony rekurencyjnie na kawałki za pomocą algorytmu de Casteljau. Kierunek podziału był za każdym razem wybierany tak, aby otrzymać kawałki o jak najmniejszej średnicy.

W odróżnieniu od kostki będziemy teraz dzielić całą przestrzeń, czyli zbiór nieograniczony. Idea binarnego podziału przestrzeni (ang. binary space partition, BSP) polega na uzależnieniu go od danych, które wyznaczają pewne hiperpłaszczyzny. Na przykład przestrzeń trójwymiarową będziemy dzielić płaszczyznami, w których leżą dane wielokąty płaskie. Na rysunkach niżej są odcinki, które wyznaczają proste, którymi można podzielić płaszczyznę, bo łatwiej to narysować, a zasada podziału jest identyczna.

Dla każdej ściany znamy jej płaszczyznę, która jest określona przez podanie dowolnego punktu i wektora normalnego. Zwrotu wektora normalego użyjemy do rozróżnienia dwóch półprzestrzeni rozgraniczonych przez ścianę; wektor ten jest zorientowany w stronę półprzestrzeni ,,out”, a druga półprzestrzeń jest oznaczona ,,in”. Dla ścian przetwarzanych w kolejności zgodnej z oznaczeniami na rysunku 8.4 powstanie drzewo przedstawione obok na tym rysunku.

Korzeń drzewa reprezentuje całą przestrzeń. Po wstawieniu pierwszej ściany mamy dwa poddrzewa, które reprezentują półprzestrzenie. Wstawiając każdą następną ścianę przeszukujemy drzewo algorytmem DFS, wybierając za każdym razem to poddrzewo, które zawiera wstawianą ścianę. Jeśli ściana przecina płaszczyznę podziału przestrzeni, to dzielimy ją na dwie części (np. za pomocą algorytmu Sutherlanda-Hodgmana) i wstawiamy je odpowiednio do lewego i prawego poddrzewa. Ściany położone w płaszczyźnie innej ściany, wstawionej wcześniej, możemy dołączyć do odpowiedniego wierzchołka drzewa (którego atrybutem powinna być wtedy lista ścian).

Zauważmy, że

• Koszt budowy drzewa jest nie mniejszy niż o⁢n⁢log⁡n operacji (jeśli drzewo jest idealnie zrównoważone i żadnej ściany nie trzeba dzielić), i nie większy niż O⁢n3 operacji (ten najgorszy przypadek ma miejsce wtedy, gdy każda ściana przecina się z wszystkimi pozostałymi; wtedy wskutek podziału, niezależnie od uporządkowania otrzymamy 12⁢n2+n fragmentów ścian.).

• Jeśli ściany są ścianami wielościanu wypukłego, to drzewo BSP ma wysokość równą liczbie ścian, każdy wierzchołek oprócz ostatniego ma tylko jedno niepuste poddrzewo, a koszt jego utworzenia jest O⁢n2 operacji.

• Ściany płaskie (wielokąty) można reprezentować za pomocą drzew BSP, które opisują podział płaszczyzn ścian przez proste, na których leżą krawędzie ścian. Można więc wprowadzić hierarchię drzew BSP (i czasem tak się robi).

• Budując drzewo BSP warto obniżać jego koszt. Wybierając ścianę, która ma być wstawiona w następnej kolejności, warto wybrać taką ścianę, która

  • spowoduje podzielenie najmniejszej liczby pozostałych (jeszcze nie wstawionych) ścian, a najlepiej żadnych,

  • rozdzieli pozostałe ściany w przybliżeniu na równoliczne podzbiory (co zmniejsza wysokość drzewa). Aby osiągnąć ten cel, czasem wprowadza się dodatkowe płaszczyzny podziału przestrzeni (bez ścian) — to jest jedyna metoda skuteczna dla zbioru ścian bryły wypukłej.

Drzewa BSP mają zastosowanie w algorytmach widoczności i wyznaczania cieni, a także w różnych zadaniach, w których ich celem jest obniżenie kosztu algorytmu, dzięki zmniejszeniu ilości wykonywanych obliczeń.