Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Datové struktury počítačové grafiky

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B4M39DPG Z,ZK 6 2P+2S česky
Vztahy:
Předmět B4M39DPG nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BE4M39DPG (vztah je symetrický)
Předmět B4M39DPG může být splněn v zastoupení předmětem BE4M39DPG
Předmět B4M39DPG nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BE4M39DPG (vztah je symetrický)
Garant předmětu:
Vlastimil Havran
Přednášející:
Vlastimil Havran
Cvičící:
Vlastimil Havran
Předmět zajišťuje:
katedra počítačové grafiky a interakce
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.

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, příměřená znalost jazyka C++. Znalost jazyka C++ bude krátce ověřena na prvním cvičení předmětu.

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

Osnova 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

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.

Studijní materiály:

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

Poznámka:

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

Další informace:
https://cw.fel.cvut.cz/wiki/courses/B4M39DPG
Rozvrh na zimní semestr 2024/2025:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost KN:E-127
Havran V.
11:00–12:30
(přednášková par. 1)
Karlovo nám.
Kotkova cvičebna K4
místnost KN:E-127
Havran V.
14:30–16:00
(přednášková par. 1
paralelka 101)

Karlovo nám.
Kotkova cvičebna K4
Út
místnost KN:E-127

16:15–17:45
(přednášková par. 1
paralelka 102)

Karlovo nám.
Kotkova cvičebna K4
St
Čt

Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 4. 10. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet4697906.html