Popis předmětu - A4M39DPG

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4M39DPG Datové struktury počítačové grafiky Rozsah výuky:2P+2S
Garanti:  Role:PO,V Jazyk výuky:CS
Vyučující:  Zakončení:Z,ZK
Zodpovědná katedra:13139 Kreditů:6 Semestr:L

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.

Výsledek studentské ankety předmětu je zde: A4M39DPG

Cíle studia:

Studenti získají body na základě semestrálního projektu, teoretické prezentace algoritmu, implementace algoritmu, dokumentace zdrojových kódů algoritmu a funkčnosti algoritmu. Písemný test v rámci zkoušky je dán obsahem přednášek.

Osnovy přednášek:

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čítačové grafice.
3. Bodové datové struktury a reprezentace.
4. Objektové a obrazkové reprezentace ve 2D a 3D.
5. Algoritmy pro vyhledávání nejbližších sousedů.
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 I.
11. Datové struktury a algoritmy pro výpočet viditelnosti II.
12. Algoritmy pro detekci kolizí mezi objekty pro animace.
13. Pokročilé algoritmy pro detekci kolizí.
14. Rezerva.

Osnovy 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ů)
14. Rezerva

Literatura:

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

Požadavky:

Časová a paměťová složitost algoritmu, binární stromy a haldy, vyvažování stromů, vyhledávací algoritmy, prioritní fronty, základy architektury von Neumann, znalost jazyka C++.

Poznámka:

Stránky předmětu: http://cw.fel.cvut.cz/wiki/courses/a4m39dpg/start

Webová stránka:

https://cw.fel.cvut.cz/wiki/courses/a4m39dpg/start

Klíčová slova:

třídění, vyhledávání, multidimenzionální datoveé struktury, datové struktury pro metodu paprsku, vyhledávání nejbližšího souseda, výpočty viditelnosti, detekce kolizí.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPIB Před zařazením do oboru V
MPKME1 Bezdrátové komunikace V 2
MPKME5 Komunikační systémy V 2
MPKME4 Sítě elektronických komunikací V 2
MPKME3 Elektronika V 2
MPKME2 Multimediální technika V 2
MPEEM1 Technologické systémy V 2
MPEEM5 Ekonomika a řízení elektrotechniky V 2
MPEEM4 Ekonomika a řízení energetiky V 2
MPEEM3 Elektroenergetika V 2
MPEEM2 Elektrické stroje, přístroje a pohony V 2
MPOI4NEW Počítačová grafika a interakce PO 2
MPOI4 Počítačová grafika a interakce PO 2
MPKYR4 Letecké a kosmické systémy V 2
MPKYR1 Robotika V 2
MPKYR3 Systémy a řízení V 2
MPKYR2 Senzory a přístrojová technika V 2


Stránka vytvořena 14.11.2019 17:50:48, semestry: Z,L/2020-1, L/2018-9, Z,L/2019-20, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.