Název:

Výpočetní geometrie

Zkratka:VGE
Ak.rok:2011/2012 (není otevřen)
Semestr:letní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MBI-volitelný
IT-MGR-2MBS-volitelný
IT-MGR-2MGM-volitelný
IT-MGR-2MGM.-volitelný
IT-MGR-2MIN-volitelný
IT-MGR-2MIN.-volitelný
IT-MGR-2MIS-volitelný
IT-MGR-2MIS.-volitelný
IT-MGR-2MMI-volitelný
IT-MGR-2MMM-volitelný
IT-MGR-2MPS-volitelný
IT-MGR-2MPV-volitelný
IT-MGR-2MSK-volitelný
Vyučovací jazyk:čeština
Kredity:5 kreditů
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:2600026
 zkouškatestycvičenílaboratořeostatní
Body:51140035
Garant:Kršek Přemysl, doc. Ing., Ph.D., UPGM
Přednášející:Herout Adam, doc. Ing., Ph.D., UPGM
Kršek Přemysl, doc. Ing., Ph.D., UPGM
Španěl Michal, Ing., Ph.D., UPGM
Zemčík Pavel, prof. Dr. Ing., UPGM
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav počítačové grafiky a multimédií FIT VUT v Brně
 
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. Prohloubit znalosti matematiky aplikované v počítačové grafice a seznámit se s geometrickou algebrou. Zaměřit studenta na praktické využití výpočetní geometrie a geometrické algebry v grafice a počítačovém vidění. Procvičit tvorbu projektové dokumentace a obhajobu projektu.
Anotace:
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í.
Požadované prerekvizitní znalosti a dovednosti:
  • Znalost základů lineární algebry a geometrie (v rozsahu bakalářského studia FIT).
  • Znalost základních algoritmů a datových struktur (v rozsahu bakalářského studia FIT).
  • Znalost základů počítačové grafiky (v rozsahu bakalářského studia FIT).
  • Znalost jazyka C++ a objektově orientovaného návrhu aplikací.
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 problémy.
  • Student získá přehled o existujících algoritmech a jejich aplikacích v grafice a poč. vidění.
  • 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ů.
Osnova přednášek:
  1. Úvod do výpočetní geometrie: příklady řešených problému, 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.
  3. Obecný princip duality, dualita v geometrických úlohách a aplikace.
  4. Základy a použití geometrické algebry.
  5. Geometrická algebra a konformní geometrie. Geometrické transformace geom. elementů v E2 a E3 s geometrickou algebrou.
  6. Praktické využití geometrické algebry a konformní geometrie v počítačové grafice.
  7. Testování polohy bodu v polygonu, triangulace polygonu, konvexní obálka ve 2D a 3D, praktické aplikace.
  8. Efektivní alg. výpočtu průsečíků (line-triangle intersection, apod.).
  9. Hledání intervalů a metody dělení prostoru: range searching a range tree; quad tree, k-d tree, BSP tree.
  10. Problém nejbližších (proximity): closest pair; nearest neighbour; Voroniovy diagramy.
  11. Triangulace ve 2D a 3D, Delaunay triangulace, tetrahedral meshing.
  12. Rekonstrukce povrchu z mračna bodů a z volumetrických dat. Algoritmy pro surface simplification, smoothing a surface remeshing.
  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.
Literatura referenční:
  1. Leo Dorst, Daniel Fontijne, Stephen Mann: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, rev. ed., Morgan Kaufmann, 2007.
  2. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.
Literatura studijní:
  1. Leo Dorst, Daniel Fontijne, Stephen Mann: Geometric Algebra for Computer Science: An Object-Oriented Approach to Geometry, rev. ed., Morgan Kaufmann, 2007.
  2. Geometric Algebra (based on Clifford Algebra), http://staff.science.uva.nl/~leo/clifford/
  3. Suter, J.: Geometric Algebra Primer, 2003, http://www.jaapsuter.com/data/2003-3-12-geometric-algebra/geometric-algebra.pdf
  4. Gaigen, http://www.science.uva.nl/ga/gaigen/
  5. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.
  6. Computational Geometry on the Web, http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
Kontrolovaná výuka:
Kontrolovaná výuka zahrnuje půlsemestrální test, individuální projekt a písemnou zkoušku.
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ů