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í.
Garant předmětu
Zajišťuje ústav
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
Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman: Handbook of Discrete and Computational Geometry, 3rd Edition, 2017.
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/
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
čeština, 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 půlsemestrální test, individuální projekt a písemnou zkoušku.
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MBS , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MBI , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MIS , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MIN , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MMM , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MPV , libovolný ročník, letní semestr, 5 kreditů, volitelný
obor MSK , libovolný ročník, letní semestr, 5 kreditů, volitelný - Program MITAI magisterský navazující
specializace NBIO , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NISD , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NISY , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NIDE , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NCPS , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NSEC , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NMAT , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NGRI , libovolný ročník, letní semestr, 5 kreditů, povinný
specializace NNET , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NVIZ , libovolný ročník, letní semestr, 5 kreditů, povinný
specializace NSEN , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NMAL , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NHPC , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NVER , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NEMB , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NADE , libovolný ročník, letní semestr, 5 kreditů, volitelný
specializace NSPE , libovolný ročník, letní semestr, 5 kreditů, volitelný - Program IT-MGR-2 magisterský navazující
obor MGM , 2. ročník, letní semestr, 5 kreditů, povinný
Typ (způsob) výuky
Přednáška
26 hod., nepovinná
Vyučující / Lektor
Osnova
- Ú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. - 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í. - 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í. - Souřadné systémy, homogenní souřadnice. Příklady použití v počítačové grafice.
- Testování polohy bodu v polygonu, triangulace polygonu, konvexní
obálka ve 2D a 3D, praktické aplikace. - Detekce kolizí pomocí algoritmu GJK.
- Problém nejbližších (proximity): closest pair; nearest neighbour;
Voroniovy diagramy. - Afinní a projektivní geometrie. Epipolární geometrie. Příklad využití ve 3D vidění.
- Triangulace ve 2D a 3D, Delaunay triangulace, tetrahedral meshing.
- Obecný princip duality, dualita v geometrických úlohách a aplikace.
- Rekonstrukce 3D povrchu z mračna bodů. Algoritmy pro surface simplification, smoothing a surface remeshing.
- Základy geometrické algebry. Kvaterniony. Příklady využití v počítačové grafice.
- 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
Osnova
Skupinové nebo individuální projekty s tvorbou dokumentace a obhajobou.