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ělicí 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).
1. A je kořenem stromu, reprezentuje všechny 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í, tedy tvoří listy stromu
Využití
[editovat | editovat zdroj]- Určení viditelných objektů ve scéně.
- Optimalizace detekce kolizí.
- 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.
