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).
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í
- 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.
Média použitá na této stránce
Binary space partition.svg
Autor: Jkwchui, Licence: CC BY-SA 3.0
This diagram llustrates the process of partitioning an irregular polygon into a series of convex ones by binary space partitioning. Notice how each step produces polygons with fewer segments until arriving at G and F, which are convex and require no further partitioning. In this particular case, the partitioning line was picked between existing vertices of the polygon and intersected none of its segments.
Autor: Jkwchui, Licence: CC BY-SA 3.0
This diagram llustrates the process of partitioning an irregular polygon into a series of convex ones by binary space partitioning. Notice how each step produces polygons with fewer segments until arriving at G and F, which are convex and require no further partitioning. In this particular case, the partitioning line was picked between existing vertices of the polygon and intersected none of its segments.