Původní BSP-strom se využíval v 3D počítačové grafice. Používal ho Fuchs k vytvoření skrytého povrchu obrázku statické 3D scény. Po fázi předzpracovaní je možné vytvořit obraz z jakéhokoliv směru pohledu v O(n) čase, kde n je počet polygonů v BSP-stromu. [1]

Obrázek 7. Vytvoření BSP-stromu. [1]

BSP-strom může být používán pro strukturované uchovávání geometrických dat. Jedná se o datovou strukturu, která není založena na obdélníkovém rozdělování prostoru. Využívá liniových úseků polylinií a okrajů polygonů k rozdělení prostoru rekurzivním způsobem. BSP-strom odráží toto rekurzivní dělení prostoru. Prostor (případně podprostor) je pokaždé rozdělen do dvou podprostorů takzvaným rozdělovacím primitivem (splitting primitive) a odpovídající uzel je přidán do stromu. BSP-strom reprezentuje organizaci prostoru souborem konvexních podprostorů v binárním stromu. Strom je užitečný během prostorového vyhledávání a ostatních prostorových operací. Obrázek 7a zobrazuje 2D prostor s některými usměrněnými liniovými úseky. (2D prostor je zde použit pro snazší ilustraci, ale princip u 3D prostoru zůstává stejný.) Levá strana liniového úseku je označena šipkou. Z této scény je vybrán liniový úsek a. 2D prostor je rozdělen do dvou částí a podporuje linii a, která je znázorněna čárkovanou linií na obrázku 7b. Tento proces se opakuje pro každý ze dvou podprostorů i s ostatními liniovými úseky. Rozdělování prostoru pokračuje, dokud liniové úseky jsou přítomné. Poznamenejme, že rozdělování prostoru občas naznačuje, že liniový úsek (který ještě nebyl použit pro rozdělování jako takový), je již na dvě části rozdělen. Linie d je například je rozdělena do d1 a d2. Obrázek 7b ukazuje výslednou organizaci prostoru, jako soubor (pravděpodobně otevřených) konvexních podprostorů. Odpovídající BSP-strom je nakreslen na obrázku 7c. Ve 3D případě se používají podpůrné roviny plochých polygonů k rozdělení prostoru místo linií.

Vytváření stromu je velice ovlivněno volbou liniového úseku pro rozdělení prostoru. Preferované je mít vyvážený BSP-strom s co nejméně uzly, jak jen je možné. A to je velmi obtížně splnitelný požadavek, protože vyvažování stromu potřebuje, aby k rozdělení prostoru byly používány liniové úseky ze středu souboru dat. Tyto liniové úseky pravděpodobně rozdělí další liniové úseky. Každé rozdělení liniového úseku vytváří navíc uzel v BSP-stromu. Diskuse ohledně vyvažování tohoto stromu viz [1]. Následuje ukázka programu, který tvoří BSP-strom. Kód je syntakticky podobný Pascalu.

Program BuildTree;
type BSP = ^node; 
     node = record segm: Line; 
                   l, r: BSP 
            end; 
var root: BSP; 
    newsegm: Line; 

function AddLine(tree:BSP; segm:Line): BSP; 
var Lsegm, Rsegm: Line; 
begin 
   if (tree = nil) then tree := CreateNode(tree, segm) 
   else case LinePosition(tree,segm) of 
        LEFT: tree^.l := AddLine(tree^.l, segm); 
        RIGHT: tree^.r := AddLine(tree^.r, segm); 
        SPLIT: SplitLine(tree, segm, Lsegm, Rsegm); 
               tree^.l := AddLine(tree^.l, Lsegm); 
               tree^.r := AddLine(tree^.r, Rsegm); 
   AddLine:=tree; 
end; 
begin 
   root := nil; 
   while GetLine(newsegm) do root := AddLine(root, newsegm); 
end.

Program BuildTree je variací tradiční (neinkrementující) metody pro stavbu BSP-stromu. Procedura SplitLine, funkce LinePosition, CreateNode a GetLine nejsou zahrnuty, protože jejich implementace je zřejmá. Uzel v BSP-stromu je reprezentován záznamem (record) typu uzel (node), který obsahuje liniový úsek a ukazatele na levého a pravého potomka. Zpočátku je strom prázdný. A to trvá dokud GetLine nepřivolá nový liniový úsek, který se přidá do BSP-stromu zavoláním funkce AddLine. AddLine kontroluje, jestli byla v BSP-stromu nalezena správná pozice. Výsledek je true, pokud ukazatel na strom v BSP-stromu ukazuje na nil. V tom případě se vytvoří nový uzel a přidá do stromu. Jinak LinePosition určí, ve kterém podstromu bude liniový úsek uložen. Uložení liniového úseku je implementováno rekurzivním voláním AddLine. Je možné, že liniový úsek musí být nejprve rozdělen.

Rozdělování liniových úseků má vážný nedostatek. Pokud máme na scéně n liniových úseků, pak je možné, že dosáhneme složitosti O(n2) uzlů ve stromu. Tato složitost, jak již bylo řečeno, je v GIS aplikacích nepřijatelná. V GIS aplikacích se totiž běžně setkáváme s 10 000 a více liniovými úseky. Skutečný počet uzlů nebude tak veliký, protože uvažujeme nejhorší případ. BSP-strom je myšlený pro interaktivní aplikace, ve kterých jsou vyžadovány rychlé odezvy. Minimalizace využívání paměti je pokládána za méně důležitou, proto se jí zde příliš věnovat nebudeme. Typické využití paměti je kolem 3 až 4 krát velikosti originálních mapových dat. Pro to existují 3 důvody: místo v paměti vyžadované pro ukazatele, pro rozdělování liniových úseků a pro replikaci bodů. Konec jednoho liniového úseku je často začátek dalšího.

Dosud probíraný BSP-strom sloužil pouze k ukládání kolekcí dat (nesouvisejících) liniových úseků. V modelovacím systému musí být možné reprezentovat uzavřený objekt, ve 2D případě například interiér polygonu. Objektový BSP-strom je rozšířením BSP-stromu s možností reprezentace objektů. Ukládá liniové úseky, které dohromady tvoří hranici polygonu. Objektový BSP-strom má explicitní koncové uzly, které už neobsahují liniové úseky k dalšímu rozdělování podprostorů. Koncové uzly odpovídají konvexnímu podprostoru, který je vytvořený BSP-stromem. Datový typ boolean v koncovém uzlu značí, zdali je konvexní podprostor uvnitř anebo vně objektu.

Objektový BSP-strom je na univerzitě v Leidenu používán k 3D grafickému modelování. [1] Díky jeho prostorové organizaci mohou být skryté povrchy odstraněny při O(n) složitosti, kde n značí počet polygonů ve stromu. Objektový BSP-strom je rovněž vhodný k vykonávání souboru operací jako je union, difference a intersection, tak jako se používají v CSG (Constructive Solid Geometry) systémech. Operce mapového překrytí (map overaly operation) v GIS má silnou návaznost na tento soubor operací.

V GIS, kde obvykle pracujeme s 2D mapami, si přejeme využívat prostorovou organizaci BSP-stromu. Liniové úseky originální databáze jsou používány k rekurzivnímu rozdělení prostoru. Používáním dat spojených s řešením problému organizace prostoru, očekáváme lepší prostorovou organizaci (v porovnání se situací, kde jsou použity fixně rozdělené linie, jako například v čtyřstomu). Mapy vždy obsahují vícenásobné objekty, například země na mapě Evropy. K tomu, abychom se vypořádali s vícenásobnými objekty, musíme pozměnit koncept objektového BSP-stromu. Místo datového typu boolean, koncové uzly budou obsahovat identifikační tag se jménem. Tento identifikační tag nám řekne, kterému objektu bude patřit konvexní podprostor, reprezentovaný koncovým uzlem. Tomuto typu BSP-stromu říkáme multi objektový BPS-strom.

Obrázek 8. Stavba multi objektového BPS stromu. [1]

Obrázek 8a reprezentuje 2D prostor se dvěma objekty, trojúhelníkem T se stranami a, b, c, a obdélníkem R se stranami d, e, f, g. Metoda rozděluje prostor v konvexních podprostorech obrázku 8b. BSP-strom obrázku 8c je rozšířen určitými uzly, kde každý reprezentuje konvexní část prostoru. Pokud konvexní podprostor odpovídá oblasti zvenku, není vykreslena žádná jmenovka (label), viz obrázek 8c. Pokud je dovolen maximálně jeden identifikační tag na list, mohou být uchovány v multi-objektovém BSP stromu pouze vzájemně vylučující se objekty. Jinak by totiž bylo možné setkat se s objekty, které se překrývají. Nevýhodou tohoto BSP stromu je, že reprezentace jednoho objektu je rozptýlena přes několik listů, například obdélník R na obrázku 8. Obrázek 9 ukazuje využití BSP-stromu pro jednoduchou polygonální mapu.

Obrázek 9. BSP-strom pro jednoduchou polygonální mapu. [1]

Jako obvykle, vnitřní uzly obsahují linie úseků a koncové uzly reprezentují konvexní části podprostoru. Nevýhody BSP-stromu jsou zřejmé z obrázku 9. Občas je nutné rozdělit liniové úseky (okraje f) a další nevýhodou je, že polygon může být rozdělen do dvou nebo více koncových uzlů (region II do listů 6, 7 a 9). Následující seznam shrnuje vlastnosti multi objektového BSP stromu:

Uvažujme systém, který zobrazuje mapu na obrazovce. Uživatel vybere bod P = (x, y) vstupním zařízením, například myší, a chce vědět, na který bod zrovna ukázal. K vyřešení tohoto problému nalezneme bod P sestupováním po BSP-stromu, dokud nenarazíme na koncový uzel. Koncový uzel obsahuje identifikační tag objektu. Sestupování stromem je jednoduché: pokud na vnitřním uzlu leží bod P na levé straně liniového úseku, pak následujeme levou větev, jinak pravou. Tato strategie má za důsledek jednu konkrétní cestu od kořene až ke koncovému uzlu. V případě vyvažování stromu s n vnitřními uzly zabere vyhledávání O(log n) času. Tento výsledek je pravděpodobně nejlepším možným.

V mnoha aplikacích uživatel chce vybrat všechny objekty uvnitř nějakého obdélníku R. Vyhledávání pomocí obdélníků je nutné pro zobrazení části mapy na obrazovce. Průchod stromem je v podstatě stejný jako u operace pick. Pokud je překrytí mezi obdélníkem R a levým podprostorem, pak je na vnitřním uzlu následována levá větev; pravá větev je následována, pokud je překrytí mezi pravým podprostorem a obdélníkem R. Pokud je překrytí v obou podprostorech, pak musí být následovány obě větve. Toto zařídí jednoduchá rekurzivní funkce. Operace jsou efektivní, protože části stromu jsou přeskakovány. V nestrukturované kolekci dat bychom museli navštívit každou položku a testovat pokud ji přijmeme na základě jejích geometrických vlastností. Při používání BSP-stromu nemusíme zkoumat data, která neleží v oblasti našeho zájmu.