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.