Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/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.
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, příměřená znalost jazyka C++. Znalost jazyka C++ bude krátce ověřena na prvním cvičení předmětu.
Poznámka:
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ů:
| Stránka vytvořena 16.1.2025 17:50:42, semestry: Z,L/2024-5, Z/2025-6, 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) |