Datové struktury počítačové grafiky bližší informace o studiu na katedře

Detaily předmětu
Vyučující | Vlastimil Havran |
---|---|
Rozsah výuky | 2 + 2 |
Kredity | 6 |
Semestr | Z |
Zakončení | Z + Zk |
Web | http://cw.fel.cvut.cz/wiki/courses/a4m39dpg |
Rozvrh | B4M39DPG |
Anotace
Obsahem předmětu je seznámení se s datovými strukturami používanými v grafických algoritmech. Důraz je kladen na základní a hierarchické datové struktury nad bodovými a objektovými daty, z hlediska aplikací datove struktury pro vyhledávání nejbližšího souseda, metodu sledování paprsku, z-buffer a detekci kolizí. Na cvičení studenti řeší samostatný projekt.
Přednášky
- 1.
Přehled přednášek, zopakování řazení a vyhledávání nad čísly, základní přehled algoritmů probíraných v předmětu, pravidla hry. Úvod do hierarchických a pravidelných datových struktur.
- 2.
Incidenční operace mezi entitami používané v poč. grafice.
- 3.
Bodové datové struktury a reprezentace.
- 4.
Objektové a obrazkové reprezentace ve 2D a 3D.
- 5.
Algoritmy pro vyhledávání nejbližších elementů.
- 6.
Přibližné vyhledávací algoritmy pro vyhledávaní. Aplikace algoritmů vyhledávání.
- 7.
Algoritmy vyhledávání ve vysokodimenzionálních prostorech.
- 8.
Datové struktury pro algoritmy sledování a vrhání paprsku a jejich aplikace I.
- 9.
Datové struktury pro algoritmy sledování a vrhání paprsku a jejich aplikace II.
- 10.
Datové struktury a algoritmy pro výpočet viditelnosti
- 11.
Algoritmy pro detekci kolizí mezi objekty pro animace.
- 12.
Pokročilé algoritmy pro detekci kolizí.
- 13.
Rezerva.
Cvičení
- 1.
Úvod ke cvičení, popis domácích úloh.
- 2.
Výběr domácích ůloh studenty, konzultace k domácím úlohám.
- 3.
Příklady na incidenční operace.
- 4.
Konzultace k domácím úlohám.
- 5.
Výkladová prezentace domácích úloh (4 studenti)
- 6.
Výkladová prezentace domácích úloh (4 studenti)
- 7.
Výkladová prezentace domácích úloh (4 studenti)
- 8.
Konzultace k domácím úlohám.
- 9.
Písemný test na 60 minut.
- 10.
Výkladová prezentace domácích úloh (4 studenti).
- 11.
Výkladová prezentace domácích úloh (4 studenti).
- 12.
Demonstrační prezentace domácích úloh. (10 studentů)
- 13.
Demonstrační prezentace domácích úloh. (10 studentů)
Literatura & zdroje
- 1.
Samet, H: The Design and Analysis of Spatial Data Structures, Addison Wesley 1994.
- 2.
Samet, H: Applications of Spatial Data Structures, Addison Wesley, 1990.
- 3.
Laurini, R. and Thompson D.: Fundamentals of Spatial Information Systems, Academic Press 1992.
- 4.
Samet, H: Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann Publishers, 2006.
- 5.
E. Langetepe and G. Zachmann: Geometric Data Structures for Computer Graphics, 2006.
- 6.
C. Ericson: Real Time Collision Detection, Morgan Kauffman Publishers, 2005.
- 7.
G. van den Bergen: Collision Detection in Interactive 3D Environments, Elsevier, 2004.
- 8.
D. P. Mehta and S. Sahni: Handbook of Data Structures and Applications, Chapman and Hall/CRC, 2004.