Datové struktury počítačové grafiky

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ý)

Předmět je ekvivalentní s AD4M39DPG,AE4M39DPG,A4M39DPG,E36DPG,XD36DPG,X39DPG .

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:

Předmět má studující seznámit s datovými strukturami používanými v algoritmech použivaných v počítačové grafice, zejména pro vyhledávání. Důraz je kladen na základní a hierarchické datové struktury nad bodovými a objektovými daty ve 2D a 3D pro reprezentaci prostorových dat, vyhledávání nejbližšího souseda, sledování paprsku. Na cvičení studující řeší každý sám individuální projekt realizací algoritmu v C++ a získá vhled a zkušenost do konkrétního problému.

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 a základní 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. Jednoduché geometrické entity a jejich reprezentace

3. Pokročilé geometrické entity a jejich reprezentace

4. Incidenční operace mezi entitami používané v počítačové grafice, cenový model.

5. Hierarchické a regulární datové struktury, cenový model

6. Datové struktury a reprezentace bodových dat.

7. Objektové a obrazkové reprezentace ve 2D a 3D.

8. Algoritmy pro vyhledávání nejbližších sousedů.

9. Aproximativní algoritmy pro vyhledávání nejbližších sousedů, aplikace v počítačové grafice

10. Datové struktury pro algoritmy sledování a vrhání paprsku a jejich aplikace I.

11. Datové struktury pro algoritmy sledování a vrhání paprsku a jejich aplikace II.

12. Datové struktury a algoritmy pro výpočet viditelnosti III.

13. Algoritmy pro vyhledávání ve vysoko-dimenzionálních prostorech.

14. Rezerva.

Osnova cvičení:

1. Úvod ke cvičení, vstupní test.

2. Popis semestrálních úloh v kostce.

3. Výběr domácích úloh studenty, konzultace k domácím úlohám.

4. Seznámení se s programovým prostředím v C++.

5. Příklady na incidenční operace.

6. Příklady na incidenční operace.

7. Výkladová prezentace domácích úloh (10 studenti)

8. Výkladová prezentace domácích úloh (10 studenti)

9. Výkladová prezentace domácích úloh, rezerva, konzultace k semestrálním projektům.

10. Písemný test na 60 minut.

11. Konzultace k semestrálním projektům.

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:

Cílem studia je se seznámit s datovými strukturami používanými v počítačové grafice pro 2D a 3D data, typicky pro problém vyhledávání, získat jak teoretické tak praktické zkušenosti s realizací netriviálního algoritmu typicky realizující hierarchickou datovou strukturu a s realizací projektu zahrnující studium algoritmu, jeho implementaci, realizaci, odladění, testování, prezentaci a dokumentaci.

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/B4M39DPG

Další informace:

https://cw.fel.cvut.cz/wiki/courses/B4M39DPG

Rozvrh na zimní semestr 2025/2026:

	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:A-309 Havran V. 11:00–12:30 (přednášková par. 1) Karlovo nám. Posluchárna KA309místnost KN:A-309 Havran V. 14:30–16:00 (přednášková par. 1 paralelka 101) Karlovo nám. Posluchárna KA309
Út	místnost KN:A-309 16:15–17:45 (přednášková par. 1 paralelka 102) Karlovo nám. Posluchárna KA309
St
Čt
Pá

Rozvrh na letní semestr 2025/2026:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Otevřená informatika - Počítačová grafika 2018 (povinný předmět oboru)
• Otevřená informatika - Počítačová grafika (PS)