Detail předmětu

Výpočetní geometrie (v angličtině)

FIT-VGEeAk. rok: 2019/2020

Lineární algebra, geometrická algebra, afinní a projektivní geometrie, princip duality, homogenní a paralelní souřadnice, testování polohy bodu, konvexní obálka, algoritmy 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

Ing. Michal Španěl, Ph.D.

Zajišťuje ústav

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

Nabízen zahradničním studentům

Všech fakult

Výsledky učení 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ů.

Prerekvizity

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

Doporučená nebo povinná literatura

Geometric Algebra (based on Clifford Algebra), http://staff.science.uva.nl/~leo/clifford/
Suter, J.: Geometric Algebra Primer, 2003, http://www.jaapsuter.com/geometric-algebra/
Gaigen, http://www.science.uva.nl/ga/gaigen/
Computational Geometry on the Web, http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
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.

Způsob a kritéria hodnocení

  • Příprava na přednášky (tzv. čtení): 18 bodů
  • Hodnocený projekt s obhajobou: 31 bodů
  • Závěrečná písemná zkouška: 51 bodů
  • Minimum pro závěrečnou písemku je 17 bodů.
  • Hranice pro úspěšné absolvování předmětu podle pravidel ECTS - 50 bodů.

Jazyk výuky

angličtina

Cíl

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.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Kontrolovaná výuka zahrnuje čtení odborných článků, individuální projekt a písemnou zkoušku.

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

  • Program IT-MGR-1H magisterský navazující

    obor MGH , libovolný ročník, letní semestr, 5 kreditů, doporučený

  • Program IT-MGR-2 magisterský navazující

    obor MGMe , 2. ročník, letní semestr, 5 kreditů, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Ing. Michal Španěl, Ph.D.

Osnova

  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. Souřadné systémy, homogenní souřadnice. Příklady použití v počítačové grafice.
  4. Hledání intervalů a metody dělení prostoru: range searching a range tree; quad tree a k-d tree. Aplikace v počítačovém vidění.
  5. Testování polohy bodu v polygonu, triangulace polygonu, konvexní obálka ve 2D a 3D, praktické aplikace.
  6. Detekce kolizí pomocí algoritmu GJK.
  7. Problém nejbližších (proximity): closest pair; nearest neighbour; Voroniovy diagramy.
  8. Afinní a projektivní geometrie. Epipolární geometrie. Příklad využití ve 3D vidění.
  9. Triangulace ve 2D a 3D, Delaunay triangulace, tetrahedral meshing.
  10. Obecný princip duality, dualita v geometrických úlohách a aplikace. 
  11. Rekonstrukce 3D povrchu z mračna bodů. Algoritmy pro surface simplification, smoothing a surface remeshing.
  12. Základy geometrické algebry. Kvaterniony. Příklady využití v počítačové grafice.
  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.

Projekt

26 hod., povinná

Vyučující / Lektor

Ing. Michal Španěl, Ph.D.

Osnova

Skupinové nebo individuální projekty s tvorbou dokumentace a obhajobou.