Detail předmětu

Výpočetní geometrie

VGE Ak. rok 2023/2024 letní semestr 5 kreditů

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)

Koordinátor předmětu

Bařina David, Ing., Ph.D. (UPGM)

Jazyk výuky

česky, anglicky

Zakončení

zkouška (písemná)

Rozsah

  • 26 hod. přednášky
  • 26 hod. projekty

Bodové hodnocení

  • 51 bodů závěrečná zkouška (24 bodů písemná část, 27 bodů testová část)
  • 31 bodů projekty
  • 18 bodů domácí úkoly

Zajišťuje ústav

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

Přednášející

Bařina David, Ing., Ph.D. (UPGM)
Beran Vítězslav, doc. Ing., Ph.D. (UPGM)
Herout Adam, prof. Ing., Ph.D. (UPGM)
Španěl Michal, Ing., Ph.D. (UPGM)
Zemčík Pavel, prof. Dr. Ing., dr. h. c. (UPGM)

Cvičící

Bařina David, Ing., Ph.D. (UPGM)

Cíle 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ů.

Proč je předmět vyučován

Předmět je vystaven na tématech a typických problémech, se kterými se v drobných obměnách setkává student v jiných předmětech (např. počítačové vidění nebo počítačová grafika), ve kterých typicky není prostor se jimi zabývat detailněji. Z pohledu náplně těchto předmětů se jedná spíše o okrajová témata, jejichž znalost je však v praxi potřebná.
Část přednášek je věnována klasickým problémům výpočetní geometrie (problém nejbližších a hledání intervalů, dělení prostoru, 2D/3D triangulace, Voroniovy diagramy, apod.) a další pak prohloubení vašich znalostí teoretických (afinní a projektivní geometrie, homogenních souřadnice, kvaterniony, atd.).

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

Literatura studijní

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 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. Proč je nutnost tohle znát?
  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, k-d tree, BSP 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ů.
  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.

Osnova ostatní - projekty, práce

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

Průběžná kontrola studia

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

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

Rozvrh

DenTypTýdnyMístn.OdDoKapacitaPSKSkupInfo
Út zkouška 2024-05-21 E104 13:0014:50 2. termín
Út zkouška 2024-05-28 A113 13:0014:50 3. termín
St zkouška 2024-05-15 E104 16:0017:50 1. termín
Pá přednáška 1., 2., 3., 5. výuky E105 12:0013:5070 1MIT 2MIT NGRI NISY NVIZ xx Bařina
Pá přednáška 6., 9., 11. výuky E105 12:0013:5070 1MIT 2MIT NGRI NISY NVIZ xx Španěl
Pá přednáška 10., 12., 13. výuky E105 12:0013:5070 1MIT 2MIT NGRI NISY NVIZ xx Herout
Pá přednáška 2024-03-01 E105 12:0013:5070 1MIT 2MIT NGRI NISY NVIZ xx Zemčík
Pá přednáška 2024-03-22 E105 12:0013:5070 1MIT 2MIT NGRI NISY NVIZ xx Beran
Pá ostatní *) 2024-04-26 E105 14:0016:5070 2MIT NGRI NISY NVIZ Bařina
Na výuku se nelze registrovat ve Studis. (Termíny cvičení mohou být v případě potřeby otevřeny dodatečně, ale nemusí být využity vůbec.)

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

Nahoru