Datové struktury počítačové grafiky

Garant předmětu:

Přednášející:

Cvičící:

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:

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

Další informace:

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

Pro tento předmět se rozvrh nepřipravuje

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