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:

Srát na státnice, jdu pařit starcraft.