Course detail

# Computational Geometry

Linear algebra, geometric algebra, affine an projective geometry, principle of duality, homogeneous and parallel coordinates, point in polygon testing, convex hull, intersection problems, range searching, space partitioning methods, 2D/3D triangulation, Delaunay triangulation, proximity problem, Voronoi diagrams, tetrahedral meshing, surface reconstruction, point clouds, volumetric data, mesh smoothing and simplification, linear programming.

Learning outcomes of the course unit

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

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

Prerequisites

• Basic knowledge of linear algebra and geometry.
• Good knowledge of computer graphics principles.
• Good knowledge of basic abstract data types and fundamental algorithms.

Co-requisites

Not applicable.

Recommended optional programme components

Not applicable.

• 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

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

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

• Preparing for lectures (readings): up to 18 points
• Realized and defended project: up to 31 points
• Written final exam: up to 51 points
• Minimum for final written examination is 17 points.
• Minimum to pass the course according to the ECTS assessment - 50 points.

Language of instruction

Czech, English

Work placements

Not applicable.

Course curriculum

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

Syllabus - others, projects and individual work of students:
Team or individually assigned projects.

Aims

To get acquainted with the typical problems of computational geometry and existing solutions. To get deeper knowledge of mathematics in relation to computer graphics and to understand the foundations of geometric algebra. To learn how to apply basic algorithms and methods in this field to problems in computer graphics and machine vision. To practice presentation and defense of results of a small project.

Specification of controlled education, way of implementation and compensation for absences

The evaluation includes mid-term test, individual project, and the final exam.

Classification of course in study plans

• Programme IT-MGR-2 Master's

branch MBI , any year of study, summer semester, 5 credits, elective
branch MPV , any year of study, summer semester, 5 credits, elective
branch MSK , any year of study, summer semester, 5 credits, elective
branch MIS , any year of study, summer semester, 5 credits, elective
branch MBS , any year of study, summer semester, 5 credits, elective
branch MIN , any year of study, summer semester, 5 credits, elective
branch MMM , any year of study, summer semester, 5 credits, elective
branch MGM , 2. year of study, summer semester, 5 credits, compulsory

#### Type of course unit

Lecture

26 hours, optionally

Teacher / Lecturer

Syllabus

1. Introduction to computational geometry: typical problems in computer graphics and machine vision, algorithm complexity and robustness, numerical precision and stability.
2. Overview of linear algebra and geometry, coordinate systems, homogeneous coordinates, affine and projective geometry. An example from 3D vision.
3. Coordinate systems and homogeneous coordinates. Applications in computer graphics.
4. Range searching and space partitioning methods: range tree; quad tree, k-d tree, BSP tree. Applications in machine vision.
5. Point in polygon testing, polygon triangulation, convex hull in 2D/3D and practical applications.
6. Collision detection and the algorithm GJK.
7. Proximity problem: closest pair; nearest neighbor; Voronoi diagrams.
8. Affine and projective geometry. Epipolar geometry. Applications in 3D machine vision.
9. Triangulation in 2D/3D, Delaunay triangulation, tetrahedral meshing.
10. Principle of duality and its applications.
11. Surface reconstruction from point clouds and volumetric data. Surface simplification, mesh smoothing and re-meshing.
12. Basics and of geometric algebra. Quaternions. Applications in computer graphics.
13. More computational geometry problems and modern trends. Linear programming: basic notion and applications; half-plane intersection.

Project

26 hours, compulsory

Teacher / Lecturer

Syllabus

Team or individually assigned projects.