Course details

# Computational Geometry

VGE Acad. year 2012/2013 Summer semester 5 credits

Guarantor

Language of instruction

Completion

Time span

Assessment points

Department

Lecturer

Španěl Michal, Ing., Ph.D. (DCGM FIT BUT)

Zemčík Pavel, prof. Dr. Ing. (DCGM FIT BUT)

Subject specific learning outcomes and competences

- Student will get acquaint with the typical problems of computational geometry.
- Student will understand the existing solutions and their applications in computer graphics and machine vision.
- Student will get deeper knowledge of mathematics.
- Student will learn the principles of geometric algebra including its application in graphics and vision related tasks.
- Student will practice programming, problem solving and defence of a small project.

Generic learning outcomes and competences

- Student will learn terminology in English language.
- Student will learn to work in a team and present/defend results of their work.
- Student will also improve his programming skills and his knowledge of development tools.

Learning objectives

Prerequisite kwnowledge and skills

- Basic knowledge of linear algebra and geometry.
- Good knowledge of computer graphics principles.
- Good knowledge of basic abstract data types and fundamental algorithms.
- Basic knowledge of the C/C++ language and object oriented programming.

Study literature

- 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

Fundamental literature

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

Syllabus of lectures

- Introduction to computational geometry: typical problems in computer graphics and machine vision, algorithm complexity and robustness, numerical precision and stability.
- Overview of linear algebra and geometry, coordinate systems, homogeneous coordinates, affine and projective geometry. An example from 3D vision.
- Principle of duality and its applications.
- Point in polygon testing, polygon triangulation, convex hull in 2D/3D and practical applications.
- Intersection problems (fast ray-triangle intersection, etc.). Example of how to speedup a simple raytracer.
- Basics and applications of geometric algebra.
- Geometric algebra and conformal geometry. Geometric transformations of basic elements in E2 and E3 using geometric algebra.
- Practical applications of geometric algebra and conformal geometry in computer graphics.
- Range searching and space partitioning methods: range tree; quad tree, k-d tree, BSP tree. Applications in machine vision.
- Proximity problem: closest pair; nearest neighbour; Voronoi diagrams.
- Triangulation in 2D/3D, Delaunay triangulation, tetrahedral meshing.
- Surface reconstruction from point clouds and volumetric data. Surface simplification, mesh smoothing and re-meshing. Example of 3D model creation from several photos.
- More computational geometry problems and modern trends. Linear programming: basic notion and applications; half-plane intersection.

Syllabus - others, projects and individual work of students

Progress assessment

- Mid-term test: up to 14 points
- Realized and defended project: up to 35 point
- Written final exam: up to 51 points

Controlled instruction

Course inclusion in study plans