BSP (počítače)
způsob dělení prostoru prostřednictvím rekurzivního rozdělování jej pomocí nadrovin do dvou podmnožin
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).
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
- 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.
