Předmět Výpočetní geometrie (FIT-VGE)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu FIT-VGE - Výpočetní geometrie, Fakulta informačních technologií, Vysoké učení technické v Brně (VUT).

Materiál	Typ	Datum	Počet stažení

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.

Osnova

Osnova přednášek:Ú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í. Obecný princip duality, dualita v geometrických úlohách a aplikace. Testování polohy bodu v polygonu, triangulace polygonu, konvexní obálka ve 2D a 3D, praktické aplikace. Efektivní alg. výpočtu průsečíků (line-triangle intersection, apod.). Příklad použití v raytracingu. Základy a použití geometrické algebry. Geometrická algebra a konformní geometrie. Geometrické transformace geom. elementů v E2 a E3 s geometrickou algebrou. Praktické využití geometrické algebry a konformní geometrie v počítačové grafice. 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í. Problém nejbližších (proximity): closest pair; nearest neighbour; Voroniovy diagramy. Triangulace ve 2D a 3D, Delaunay triangulace, tetrahedral meshing. 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í. 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

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

Požadavky

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

Garant

Ing. Michal Španěl, Ph.D.

Vyučující

Ing. Michal Španěl, Ph.D.