navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
statnice:gi:11 [2011/06/02 00:47] keymaster vytvořeno |
— (aktuální) | ||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== Speciální datové struktury pro pokročilé grafické techniky (vrhání paprsku) ====== | ||
| - | |||
| - | * Motivace: V metodě sledování paprsku potřebujeme najít průsečík mnoha paprsků (n ~ 10^6 - 10^9) se scénou, která obsahuje mnoho objektů (m ~ 10^5 - 10^7). Naivní metoda otestuje pro každý paprsek všechny objekty a vrátí nejbližší průsečík se složitostí O(n×m). To je v praxi nepoužitelné, proto chceme speciální struktury které výpočet urychlí na O(n×log m). | ||
| - | * Struktury pro range a similarity search na bodových datech (otázka 10) nefungují přímo, musí se modifikovat | ||
| - | * Běžně používané struktury: | ||
| - | * Grid | ||
| - | * Octree | ||
| - | * BVH | ||
| - | * kd-tree | ||
| - | |||
| - | ===== Grid ===== | ||
| - | * Srát na státnice, jdu pařit starcraft. | ||
