BSP (počítače)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

BSP (binary space partitioning, binární rozdělování prostoru) je způsob rozdělení prostoru pomoci binárního stromu. Výsledný strom ve svém kořenu obsahuje rovinu, která všechny objekty v prostoru dělí na 2 skupiny (ležící před a za rovinou). Potomci kořene pak reprezentují vzniklé skupiny, jež jsou opět rekurzivně děleny nově zvolenou rovinou na 2 části. Listy stromů pak obsahují vhodné skupiny objektů (nejčastěji se jedná o množinu polygonů, které tvoří konvexní celek, tj. žádná rovina určena polygonem neprotne jiný polygon ze skupiny).

Dvourozměrný případ BSP - pouze pro levé větve stromu.
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 v interaktivních počítačových hrách.