Datové struktury počítačové grafiky

• Stránky předmětu: http://service.felk.cvut.cz/courses/X36DPG/
• 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á?

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