BSP (počítače)

Z Wikipedie, otevřené encyklopedie
Jump to navigation Jump to search

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.