středa 16:15 - 17:45, 18:00 - 19:30 v KN:E-311
v 10.týdnu, tj.21.4.2010, se píše test (60 min)
- v mailu bylo napsáno, že se píše test 5.5.. Na přednášce říkal, že to možná bude o týden dřív. Ale 21.4. podle mě rozhodně ne. — Roman Polášek 2010/04/18 12:30
- Program cvičení od 18:00 (dle mailu):
Čas 90min.
možné otázky (sesbíráno z Exfortu, snad si nebudou nárokovat autorská práva :)):
1.) Je dan hyperobdelnik pomoci 2 rohu A[N], B[N] (uhlopricne) a stred hyperkoule S[N]. Spocitej minimalni polomer koule, tak aby obdelnik lezel cely uvnitr.
2.) SAT, vysvetlit, kolik udela testu.
3.) 3 druhy rozdeleni hiearchickejch struktur.
4.) Nejblizsi priblizny soused, co to je, proc funguje.
5.) Algoritmus pro stavbu hiearchicke struktury, jaky se pouzivaj pomocny struktury.
1) Je dan hyperobdelnik pomoci min a max v kazde ose a bod. Napsat algoritmus pro vypocet vzdalenosti bodu od hyperobdelnika.
2) Cenova fuknce pri dotazu do hierarchicke datove struktury.
3) Jake vlastnosti musi mit vzdalenost, co je to metrika a metricky prostor.
4) Napsat vsechny typy objektovych obalek a pozadavky na ne.
5) Jak funguje algoritmus AESA a jakou ma pametovou slozitost. Jaky algoritmus a jak snizuje jeho pametovou slozitost.
1. Výpočet vzdálenosti bodů od AABB v N rozměrech
2. Průsečík přímky a hypersféry v N rozměrech
3. Rozdíl uniformních a neuniformních struktur
4. Je dán hyperobdélník pomocí 2 rohů A[N], B[N] (úhlopříčně) a střed hypersféry S[N]. Spočítej minimální poloměr koule tak, aby obdélník ležel celý uvnitř. Pak ještě poloměr tak, aby se koule dotýkala typicky jednoho (max. čtyř) bodů, jinak disjunktní (koule vepsaná kvádru).
5. SAT, vysvětlit a napsat pseudokód kód, kolik udělá testů pokud se jedná o OBB a kolik pro AABB?
6. 3 druhy rozdělení hierarchických struktur
7. Rozdělení hierarchických struktur, tedy podle uspořádání dat a podle paměti.
8. Nejbližší přibližný soused, co to je a proč to funguje.
9. Algoritmus pro stavbu hierarchické struktury, jaký a k čemu se používají pomocný struktury.
10. Je dán hyperobdélník pomocí min a mex v každé ose a bod. Napsat algoritmus pro výpočet vzdáleností bodu od hyperobdélníka.
11. Cenová funkce při dotazu do hierarchické datové struktury. K čemu se to používá.
12. Jaké vlastnosti musí mít vzdálenost, co je to metrika a metrický prostor.
13. Napsat všechny typy objektových obálek a požadavky na ně.
14. Jak funguje algoritmus AESA a jakou má paměťouvou složitost. Jaký algoritmus a jak snižuje jeho paměťovou složitost.
15. Co je to odhad hustoty pravděpodobnosti (density estimation) a jaký algoritmus se při něm využívá?
16. hierarchie pamětí, typické parametry
2015
2014
Příklad na trojúhelníky za 11b a 5 teoretických otázek za 9b. Teoretické otázky byly ve stejném stylu, co jsou zde již napsané - 2 způsoby reprezentace těles, metody stavby BVH, regulární vs BVH struktury, nějaký otázka s rovinama u kd-stromů, pak ještě něco ke kd-stromům (způsoby štěpení mám pocit). Ústní za 5b, pro lidi co měli odevzdanou semestrálku ten samý den asi po 4h, ostatní v den prezentace semestrálky (cca týden po zkoušce).
Otázky ze zkouškové písemky 28.1.2008
1. Daná koule se středem C a poloměrem R, dále zadaná přímka z O s jednotkovým směrovým vektorem. Najít nejbližší průsečík a vrátit 1, případně 0 pokud průsečík neexistuje. To celé pro N dimenzí. [10 bodů]
2. Uniformní x hierarchické x BVH struktury… Co kde, proč, složitosti, příklady… [3+2 bodů]
3. Máme AABB box s minimálními souřadnicemi A a maximálními B a dotaz Q. Spočítat vzdálenost Q od boxu a vrátit ji. Pokud je Q uvnitř AABB vrátit nulu. Vše pro N dimenzí. [6 bodů]
4. Algortimy se Z-bufferem, vyjmenovat a jeden si vybrat a vysvětlit. [5 bodů]
5. Co je to prokletí dimenzionality a jak se to projevuje na NN-search. [4 body]
viz http://www.exfort.org/forumbb/viewtopic.php?t=4008
Otázky ze zkouškové písemky 6.2.2009
1. Napsat podrobný pseudokód nebo kód v C/C++ příkladu: Vstupni soubor obsahuje počet trojúhelníků a za ním jsou vypsané všechny vrcholy tvořící dané trojúhelníky (na každém řádku 3 float hodnoty určující jeden vrchol trojúhelníku, tedy vždy 3 řádky určují jeden trojúhelník). Do výstupního souboru zapsat počet unikátních vrcholů a jejich výpis s tím, že vrcholy lišící se jen o nějaké EPSILON jsou shodné (například 1.0 2.0 3.0 je totožné jak 1.01 2.0 3.01), dále vypsat počet trojúhelníků a následně na každém řádku tři indexy ukazující na vrcholy trojúhelníku. Napsat algoritmus se složitostí menší než O(n*n)
příklad:
vstup:
2
1.0 2.0 3.0
2.0 1.0 1.0
2.0 2.0 3.0
1.01 2.0 3.0
1.0 3.0 3.0
2.0 2.0 3.008
výstup:
4
1.0 2.0 3.0
2.0 1.0 1.0
2.0 2.0 3.0
1.0 3.0 3.0
2
1 2 3
1 4 3
[15 bodů]
2. Uniformní, prostorové dělení, BVH struktury. Napsat jejich vlastnosti. Napsat jejich výhody a nevýhody pro bodová a nebodová data. [3 bodů]
3. Pro struktury z předchozí otázky napsat časovou složitost sestavení a paměťovou náročnost. Napsat konkrétní příklady struktur. [2 bodů]
4. Máme AABB box s minimálními souřadnicemi A a maximálními B a dotaz Q. Spočítat vzdálenost Q od boxu a vrátit ji. Pokud je Q uvnitř AABB vrátit nulu. Vše pro N dimenzí. [3 bodů]
5. Co je to prokletí dimenzionality a jak se to projevuje na NN-search. [2 body]
Zkouškový otázky z exfortu, tak se snad nikdo nebude zlobit, že sem to sem hodil
pokud by se někomu třeba hodilo..
Geometric DS for CG (.chm, 20MB, @megaupload) - je tam něco málo o octrees, height fields visualization, kd-trees, bvh…
The Design and Analysis of Spatial Data Structures od H.Sameta - myslim že Havran z toho bere minimálně některý obrázky ;). jinak si tady užijou především ti, co rádi sází stromy - hlavně kd-trees, octrees a quadtrees :) (.pdf, 23MB, @megaupload)
* 28 testovacích scén v obj, s konfiguračním souborem kde je uložena pozice kamery a případných světel: http://temp.keymaster.cz/scenes.zip