Datové struktury počítačové grafiky bližší informace o studiu na katedře

Datové struktury počítačové grafiky

Detaily předmětu

Vyučující Vlastimil Havran
Rozsah výuky 2 + 2
Kredity 6
Semestr L
Zakončení Z + Zk
Web http://cw.fel.cvut.cz/wiki/courses/a4m39dpg
Rozvrhy a4m39dpg, 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.

Přednášky

  • 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č. grafice.

  • 3.

    Bodové datové struktury a reprezentace.

  • 4.

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

  • 5.

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

  • 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

  • 11.

    Algoritmy pro detekci kolizí mezi objekty pro animace.

  • 12.

    Pokročilé algoritmy pro detekci kolizí.

  • 13.

    Rezerva.

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

Literatura & zdroje

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