Výpočetní geometrie

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

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

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

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.

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

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

• Csaba D. Toth, Joseph O'Rourke, Jacob E. Goodman: Handbook of Discrete and Computational Geometry, 3rd Edition, 2017.
• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications, 3rd. ed., Springer-Verlag, 2008.
• 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/geometric-algebra.pdf
• Gaigen, https://github.com/Sciumo/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.

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.

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

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