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).
náhled|střed|460px|Dvourozměrný případ BSP – pouze pro levé větve stromu.1. A je kořenem stromu, reprezentuje všechny hrany2. A je rozdělen na B a C3. 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.
Kategorie:Stromy (datové struktury)