BSP (počítače)

BSP (binary space partitioning, binární rozdělování prostoru) je způsob rozdělení prostoru pomocí binárního stromu. Výsledný strom ve svém kořeni obsahuje nadrovinu, která všechny objekty v prostoru dělí na dvě podmnožiny (ležící před a za dělící nadrovinou). Potomci kořene pak reprezentují vzniklé podmnožiny, jež jsou opět rekurzivně děleny nově zvolenou nadrovinou na dvě nové podmnožiny. Listy stromů pak obsahují vhodné množiny objektů (např. v 3D prostoru se může jednat o množinu polygonů, které tvoří konvexní celek, tj. žádná rovina určena polygonem neprotne jiný polygon z množiny).

+more 1. _A_je_kořen_(graf)|kořenem_Strom_(datová_struktura)|stromu,_reprezentuje_všechny_Hrana_(graf)|hrany 2. _A_je_rozdělen_na_B_a_C 3. _B_je_rozdělen_na_D_a_E. 4. _D_je_rozdělen_na_F_a_G,_které_jsou_Konvexní_množina|konvexní,_tedy_tvoří_List_(graf)|listy_Strom_(datová_struktura)'>stromu. .

Využití

Určení viditelných objektů ve scéně. * Optimalizace detekce kolizí. +more * Spolu s PVS (potentially visible set - seznam viditelných listů u každého listu BSP stromu) optimalizace rychlosti vykreslování scény. Technika je často používána ve videohrách.

Kategorie:Stromy (datové struktury)