Fakulta informačních technologií VUT v Brně

Detail předmětu

Výpočetní geometrie

VGE Ak. rok 2012/2013 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

Jazyk výuky

česky

Zakončení

zkouška (písemná)

Rozsah

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

Bodové hodnocení

51 zkouška, 14 půlsemestrální test, 35 projekty

Zajišťuje ústav

Přednášející

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

Dovednosti, znalosti a kompetence obecné

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

  • Leo Dorst, Daniel Fontijne, Stephen Mann: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, rev. ed., Morgan Kaufmann, 2007.
  • Geometric Algebra (based on Clifford Algebra), http://staff.science.uva.nl/~leo/clifford/
  • Suter, J.: Geometric Algebra Primer, 2003, http://www.jaapsuter.com/data/2003-3-12-geometric-algebra/geometric-algebra.pdf
  • Gaigen, http://www.science.uva.nl/ga/gaigen/
  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.
  • Computational Geometry on the Web, http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html

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, 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

  • Půlsemestrální test: 14 bodů
  • Hodnocený projekt s obhajobou: 35 bodů
  • Závěrečná písemná zkouška: 51 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