Detail předmětu

Výpočetní geometrie

FIT-VGEAk. rok: 2020/2021

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

Jazyk výuky

čeština

Počet kreditů

5

Garant předmětu

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

Zajišťuje ústav

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

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

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

Učební cíle

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 půlsemestrální test, individuální projekt a písemnou zkoušku.

Základní literatura

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.

Doporučená literatura

Computational Geometry on the Web, http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman: Handbook of Discrete and Computational Geometry, 3rd Edition, 2017.
Gaigen, https://github.com/Sciumo/gaigen
Geometric Algebra (based on Clifford Algebra), http://staff.science.uva.nl/~leo/clifford/
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.
Suter, J.: Geometric Algebra Primer, 2003, http://www.jaapsuter.com/geometric-algebra.pdf

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

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

    obor MGM , 2 ročník, letní semestr, povinný
    obor MBI , 0 ročník, letní semestr, volitelný
    obor MBS , 0 ročník, letní semestr, volitelný
    obor MIN , 0 ročník, letní semestr, volitelný
    obor MIS , 0 ročník, letní semestr, volitelný
    obor MMM , 0 ročník, letní semestr, volitelný
    obor MPV , 0 ročník, letní semestr, volitelný
    obor MSK , 0 ročník, letní semestr, volitelný

  • Program MITAI magisterský navazující

    specializace NISY , 0 ročník, letní semestr, volitelný
    specializace NADE , 0 ročník, letní semestr, volitelný
    specializace NBIO , 0 ročník, letní semestr, volitelný
    specializace NCPS , 0 ročník, letní semestr, volitelný
    specializace NEMB , 0 ročník, letní semestr, volitelný
    specializace NHPC , 0 ročník, letní semestr, volitelný
    specializace NGRI , 0 ročník, letní semestr, povinný
    specializace NIDE , 0 ročník, letní semestr, volitelný
    specializace NISD , 0 ročník, letní semestr, volitelný
    specializace NMAL , 0 ročník, letní semestr, volitelný
    specializace NMAT , 0 ročník, letní semestr, volitelný
    specializace NNET , 0 ročník, letní semestr, volitelný
    specializace NSEC , 0 ročník, letní semestr, volitelný
    specializace NSEN , 0 ročník, letní semestr, volitelný
    specializace NSPE , 0 ročník, letní semestr, volitelný
    specializace NVER , 0 ročník, letní semestr, volitelný
    specializace NVIZ , 0 ročník, letní semestr, povinný

Typ (způsob) výuky

 

Přednáška

26 hod., nepovinná

Vyučující / Lektor

Ing. Michal Španěl, Ph.D.
prof. Dr. Ing. Pavel Zemčík, dr. h. c.
prof. Ing. Adam Herout, Ph.D.
Ing. David Bařina, Ph.D.
doc. Ing. Vítězslav Beran, 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. 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í.
  4. Souřadné systémy, homogenní souřadnice. Příklady použití v počítačové grafice.
  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.