Detail předmětu

Výpočetní geometrie

VGE Ak. rok 2017/2018 letní semestr 5 kreditů

Aktuální akademický rok

Lineární algebra, geometrická algebra, afinní a projektivní geometrie, princip duality, homogenní a paralelní souřadnice, testování polohy bodu, konvexní obálka, alg. výpočtu průsečíků, hledání intervalů, metody dělení prostoru, 2D/3D triangulace, Delaunay triangulace, problém nejbližších, Voroniovy diagramy, meshing, rekonstrukce povrchu, mračno bodů, volumetrická data, vyhlazování a decimace polygonálních modelů, lineární programování.

Garant předmětu

Španěl Michal, Ing., Ph.D. (UPGM)

Jazyk výuky

česky, anglicky

Zakončení

zkouška (písemná)

Rozsah

Bodové hodnocení

  • 51 bodů závěrečná zkouška
  • 49 bodů projekty

Zajišťuje ústav

Ústav počítačové grafiky a multimédií (UPGM)

Získané dovednosti, znalosti a kompetence z předmětu

  • Student se seznámí s problematikou výpočetní geometrie a jejími typickými úlohami.
  • Student získá přehled o některých tradičních problémech počítačového vidění a počítačové grafiky a možnostech jejich řešení s využitím znalostí výpočetní geometrie.
  • Student prohloubí své znalosti matematiky a seznámí se užitečnými vlastnostmi geometrické algebry včetně reálných aplikací.
  • Student se zaměří na zvolenou oblast výpočetní geometrie a v rámci projektu vytvoří praktickou aplikaci, projektovou dokumentaci a projekt obhájí.

  • Student se naučí odborné terminologii v anglickém jazyce.
  • Student se naučí vyhledávat informace v angličtině.
  • Student se naučí vytvářet projekty v malém týmu a prezentovat i obhájit výsledky projektu.
  • Studenti se zdokonalí v praktickém užívání programátorských nástrojů.

Cíle předmětu

Seznámit se s typickými problémy výpočetní geometrie, získat přehled o existujících řešeních a algoritmech. Zaměřit studenta na praktické využití výpočetní geometrie v moderní počítačové grafice a počítačovém vidění. Prohloubit znalosti matematiky aplikované v grafice a poč. vidění, seznámit se s geometrickou algebrou. Procvičit tvorbu projektové dokumentace a obhajobu projektu.

Požadované prerekvizitní znalosti a dovednosti

  • Znalost základů lineární algebry a geometrie (v rozsahu bakalářského studia FIT).
  • Znalost základů počítačové grafiky (v rozsahu bakalářského studia FIT).
  • Znalost základních algoritmů a datových struktur (v rozsahu bakalářského studia FIT).
  • Základní znalost jazyka C/C++ a objektově orientovaného návrhu aplikací.

Literatura studijní

  • Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman: Handbook of Discrete and Computational Geometry, 3rd Edition, 2017.
  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.
  • Leo Dorst, Daniel Fontijne, Stephen Mann: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, rev. ed., Morgan Kaufmann, 2007.

Literatura referenční

  • Leo Dorst, Daniel Fontijne, Stephen Mann: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, rev. ed., Morgan Kaufmann, 2007.
  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.

Osnova seminářů

Osnova přednášek:
  1. Úvod do výpočetní geometrie: příklady řešených problémů v počítačové grafice a počítačovém vidění, typické metody, složitost a robustnost algoritmů, numerická přesnost a stabilita.
  2. Přehled pojmů z lineární algebry a geometrie, souřadné systémy, homog. souřadnice, afinní a projektivní geometrie. Proč je nutnost tohle znát? Příklad využití ve 3D vidění. 
  3. Obecný princip duality, dualita v geometrických úlohách a aplikace. 
  4. Testování polohy bodu v polygonu, triangulace polygonu, konvexní obálka ve 2D a 3D, praktické aplikace. 
  5. Efektivní alg. výpočtu průsečíků (line-triangle intersection, apod.). Příklad použití v raytracingu. 
  6. Základy a použití geometrické algebry. 
  7. Geometrická algebra a konformní geometrie. Geometrické transformace geom. elementů v E2 a E3 s geometrickou algebrou. 
  8. Praktické využití geometrické algebry a konformní geometrie v počítačové grafice. 
  9. Hledání intervalů a metody dělení prostoru: range searching a range tree; quad tree, k-d tree, BSP tree. Aplikace v počítačovém vidění. 
  10. Problém nejbližších (proximity): closest pair; nearest neighbour; Voroniovy diagramy. 
  11. Triangulace ve 2D a 3D, Delaunay triangulace, tetrahedral meshing. 
  12. Rekonstrukce 3D povrchu z mračna bodů a z volumetrických dat. Algoritmy pro surface simplification, smoothing a surface remeshing. Ukázka tvorby 3D modelu z několika fotografií. 
  13. Další příklady typických úloh výpočetní geometrie a aktuální trendy. Využití lineárního programování: definice a aplikace; half-plane intersection.

Osnova ostatní - projekty, práce:
Skupinové nebo individuální projekty s tvorbou dokumentace a obhajobou.

Průběžná kontrola studia

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Kontrolovaná výuka

Kontrolovaná výuka zahrnuje půlsemestrální test, individuální projekt a písemnou zkoušku.

Zařazení předmětu ve studijních plánech

Nahoru