Datové struktury počítačové grafiky

• Stránky předmětu: https://edux.feld.cvut.cz/courses/A4M39DPG/start
• Přednášející: Vlastimil Havran (web)
• Cvičící: Vlastimil Havran

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):

• 21/4 Konzultace k implementaci
• 28/4 Konzultace k implementaci
• 5/5 Pisemny test na 60 minut
• 10/5 Prednaska - ODPADA (podle Havranova mailu je Bittner nemocny)
• 12/5 Odpada (rektorsky den)
• 17/5 pondeli do 12:45, tedy 45 minut po poledni, termin pro nahrani dat semestralni prace na service.felk.cvut.cz, na dalsi data dodana pozdeji nebude bran zretel.

• 17/5 a 18/5 v dobe 12:30 az 16:30 konzultacni hodiny

• 19/5 streda v terminu 16:00 az 19:00: Predvadeni funkcnosti jiz implementovanych semestralnich praci na 10 minut.

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ř.

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.

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á?

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)

Real Time Collision Detection

* 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