Stručný úvod do BSP stromů

Malíř

Základní metodou, která by tento problém mohla řešit a která asi napadne každého jako první, je tzv. malířův algoritmus . Všechny polygony prostě setřídíme podle vzdálenosti od kamery a vykreslíme odzadu dopředu. Nejen že je to metoda pomalá, ale ani moc nefunguje. A to nejen když se polygony protínají. Jeden jednoduchý případ, se kterým si libovolné pořadí kreslení polygonů neporadí, je na obrázku 1. Obrázek vedle ukazuje, co by mohl provést malíř. Navíc ani není jasné, jak takové polygony třídít. Drtivá většina jeho implementací selhává i v situacích, kdy správně pořadí existuje (Tomb Raider).

Obr.1

Obr.2

BSP stromy

BSP strom je [úplný?] binární strom (každý uzel má právě dva syny). Uzel obsahuje informaci o dělící nadrovině a jeden syn odpovídá zápornému, druhý kladnému poloprostoru.

Jedná se tedy o hierarchické rekurzivní dělení n-dimenzionálního (většinou 3D) prostoru na konvexní podprostory (tzv. buňky - listy BSP stromu). Jaké další podmínky musí list BSP stromu splňovat se různí podle použití. Pro účely vykreslování scény musí např. platit, že polygony ležící v takovém podprostoru už nějak vykreslit umíme. Nejjednodušší je, pokud lze takové polygony kreslit v libovolném pořadí.

Obr.3

Obr.4

Obr.5

Jeden z možných BSP stromů je zobrazen na následujících obrázcích. Jak se ale takový strom vyrobí? Nejdříve je vhodné zadefinovat si základní struktury:

// Nadrovina (s metodami distance, ...)
class Plane;

// Polygon
struct Polygon;

// Seznam polygonů (s metodami get, add, ...)
class PolyList;

struct BSPNode;

// Potomek uzlu
struct BSPChild
   {
   BOOL is_node;             // Je potomek uzel?
   union
      {
      BSPNode *node;         // (is_node == TRUE)
      PolyList *polygons;    // (is_node == FALSE)
      };
   };

// Uzel BSP stromu
struct BSPNode
   {
   Plane plane;              // Dělící nadrovina
   BSPChild positive;        // Kladný poloprostor
   BSPChild negative;        // Záporný poloprostor
   };

Stavění BSP stromu

void build_bsp (BSPNode *tree, PolyList *polygons)
{
Plane *plane;
Polygon *poly;
PolyList *front, *back;

// Vyber sekací rovinu
plane = polygons->partition_plane();

// Vyrob nové dva seznamy
front = new PolyList;
back = new PolyList;

while ((poly = polygons->get()) != NULL)
   {
   // Pro každý polygon zjisti, kde se nachází vzhledem k rovině
   switch (plane->classify_polygon (poly))
      {
   case IN_FRONT_OF:
      front->add (poly);
      break;
      
   case IN_BACK_OF:
      back->add (poly);
      break;
      
   case SPANNING:
      // Musíme sekat
      Polygon *p1, *p2;
      
      poly->split (&p1, &p2, plane);
      delete poly;
      
      front->add (p1);
      back->add (p2);
      break;
      }
   }
   
delete polygons;

if (front->can_draw())
   {
   // Umíme nakreslit polygony - bude to list
   node->positive.is_node = FALSE;
   node->positive.polygons = front;
   }
else
   {
   // Musíme dál dělit
   node->positive.is_node = TRUE;
   node->positive.node = new BSPNode;
   build_bsp (node->positive.node, front);
   }

if (back->can_draw())
   {
   // Umíme nakreslit polygony - bude to list
   node->negative.is_node = FALSE;
   node->negative.polygons = back;
   }
else
   {
   // Musíme dál dělit
   node->negative.is_node = TRUE;
   node->negative.node = new BSPNode;
   build_bsp (node->negative.node, back);
   }
}

Mezi další (spíše prakticé) problémy patří:

• Co dělat s polygonem, který leží na dělící rovině (jeden to určitě bude)? V závislosti na chápání can_draw() takovýto polygon vždy "patří" do jednoho z poloprostorů. V některých implementacích obsahuje seznam polygonů i uzel - jsou to právě ty, které leží na dělící rovině.
• Jak implementovat rozseknutí (DCV)
• Jak implementovat can_draw() (DCV)
• Jak se vypořádat s nepřesností floatů.

Obr.6

Obr.7

Třídění polygonů pomocí BSP stromu

Obr.8

Obr.9

Základní optimalizace vykreslování

Co se rychlosti týče - je vidět, že uvedený algoritmus třídění vždy prochází celý strom, takže proto je důležité minimum rozsekávání a ne vyváženost. Teoreticky by mohla velikost BSP stromu dosáhnout řádově N^2 polygonů, ale např. náš BSPátor při plných optimalizacích dosahuje zhruba 4*N při mapách o mnoho větších a o trochu složitějších něž má Quake.

Víme-li, jakým způsobem se polygony budou kreslit (druh projekce, směr pohledu, FOV), můžeme provést pár jednoduchých optimalizací - ignorovat celé podstromy, které určitě nebudou vidět. Jsou to ty, které se kompletně nacházejí mimo zorné pole kamery. Jednoduše (i když nepřesně) to lze testovat pomocí nějakých primitivních objektů (koulí či kvádrů), které "obalují" podstromy - stačí přidat krátkou informaci do každého uzlu.

Další možnou optimalizací vykreslování jsou tzv. PVS - potentially visibile sets. Vlastní datová struktura a její použití je velmi triviální - pro každou buňku máme nějak kódovanou množinu potencionálně viditelných buňek (např. maticí bitů velikosti počet buňek na druhou, vetšinou zakompresovanou obdobou RLE). Získání této informace je ale velmi obtížné (viz. diplomka Ondřeje Kárného někdy z minulého roku). Pro zmenšení velikosti dat a urychlení jejich výpočtu lze informace o viditelnosti ukládat pro podstromy (jak velké a které je už jiný problém).

Další možná využití BSP stromů v Quake-like enginech

Při konverzi map do her typu Quake se BSP stromy uplatní ještě mnohokrát, např.

• CSG operace (u Quake pouze sjednocování)
• Zahazování "neviditelných" polygonů. Mapy se většinou staví z konvexních mnohostěnů, naše mapa by tedy měla 7 kvádrů (4 stěny, strop, podlaha, sloup), tedy 7*6=42 stěn a ještě víc polygonů. Tím, že BSPátor při její konverzi správně pochopil, co je to "uvnitř" (tedy kde se smí hráč pohybovat) a co je to "venku", má výsledná mapa 10 stěn a 20 polygonů. (stěna = polygon před stavěním BSP stromu)
• Osvětlování mapy (viz. možná písemný referát)

Obr.10

Obr.11

Volume BSP

Základním algoritmem nad takovýmto stromem je lokalizace bodu (v jakém je listu). To je opravdu trivální - domácí cvičení.

Dalším algoritmem je ray casting (vrhnání paprsku). Úkolem je zjistit, kde paprsek vysílaný z daného bodu daným směrem narazí do "zdi". To lze použít pro detekci kolize bodu pohybujícího se po přímce (nebo třeba ve vykreslování scény raytracingem pro objekty definované CSG operacemi mezi konvexními mnohostěny).

Následující algoritmus se (možná) někdy nazývá rekurzivní dělení paprsku. Pro jednoduchost máme paprsek-úsečku (z obou stran omezený). Ten se rekurzivně seká dělící nadrovinou. Pokud rekurzivní volání na poloprostor s počátkem paprsku určí, že někde narazil, končíme. Jinak algoritmus aplikujeme i na opačný poloprostor. Pokud je syn listem, místo rekurze se podíváme, je-li tento list pro paprsek průchozí.

// Tímto materiálem ještě paprsek projde, "větším" už ne
Material penetrable_material;

// Informace o bodu nárazu platné, pokud cast_ray() vrátí TRUE
HitInfo cast_result;

BOOL cast_ray (BSPNode *node, const Vector &origin, const Vector &direction, float min_dist, float max_dist)
{
BSPChild *first_child, *second_child;
Vector cross_point, normal;
float dist, dot;

// Zjisti, na které straně dělící roviny jsme
dist = node->plane->distance (origin);
if (dist <= 0.0)
   {
   // Za rovinou
   first_child = &node->negative;
   second_child = &node->positive;
   normal = node->plane->reversed_normal();
   dist = -dist;
   }
else
   {
   // Před rovinou
   first_child = &node->positive;
   second_child = &node->negative;
   normal = node->plane->normal();
   }

// Zjisti, kolik paprsek urazí než narazí
dot = -(normal * direction);
if (dot > 0)
   {
   dist /= dot;
   if (dist > max_dist)
      dist = max_dist;
   }
else
   {
   // Nenarazí nikdy
   dist = max_dist;
   }

// Došli jsme do listu, kde leží origin?
if (!first_child->is_node)
   {
   if (first_child->material > penetrable_material)
      {
      // Buňka není průchozí - origin je bod kolize, min_dist vzdálenost od původního počátku
      //(vyplň globální informace o kolizi)
      return TRUE;
      }
   }
else
   {
   // Rekurzivně aplikuj na tu část, ve které leží origin
   if (cast_ray (first_child, origin, direction, min_dist, dist))
      {
      // Narazili jsme - hotovo
      return TRUE;
      }
   }

if (dist >= max_dist)
   {
   // Už dál nemůžeme
   return FALSE;
   }

// Spočítej bod nárazu   
cross_point = origin + dist * direction;
min_dist += dist;
max_dist -= dist;

// Je na druhé straně list?
if (!second_child->is_node)
   {
   if (second_child->material > penetrable_material)
      {
      // Buňka není průchozí - cross_point je bod kolize
      //(vyplň globální informace o kolizi)
      return TRUE;
      }
   return FALSE;
   }
   
// Zavolej se na to, co je za dělící rovinou
return cast_ray (second_child, cross_point, direction, min_dist, max_dist);
}

Počítání kolizí složitějších objektů správně je skoro nemožné. I pro kvádry je to velmi obtížný úkol (znamená to vrhání "tlustého" paprsku). Quake 1 proto dělá takový špinavý trik. I pro hráče nebo příšery používá obyčejný ray cast, ale má speciálně modifikovný BSP strom - všechny objemy zdí jsou jakoby nafouklé směrem dovnitř. Ale ani udělat takové nafouknutí správně není nejjednodušší. Nafukují-li se totiž všechny stěny původních konvexní mnohostěnů, vznikají někdy na jejich hranicích podivné anomálie. Můžete si o tom doma popřemýšlet.

Jeden materiál

Už pěkně dlouho ho neupdatovali. Je to ale výborný zdroj dalších linků, proto nemá smysl, abych je sem opisoval.

A ještě comp.graphics.algorithms , tam vám jistě rádi poradí.