Course detail

Computational Geometry

FIT-VGEAcad. year: 2024/2025

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.

Language of instruction

Czech

Number of ECTS credits

5

Mode of study

Not applicable.

Guarantor

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

Department

Department of Computer Graphics and Multimedia (UPGM)

Entry knowledge

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

Rules for evaluation and completion of the course

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

The evaluation includes reading scientific articles, individual project, and the final exam.

Aims

  • 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 in relation to computer graphics.
  • 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.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

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

Recommended literature

Geometric Algebra (based on Clifford Algebra), http://staff.science.uva.nl/~leo/clifford/
Gaigen, https://github.com/Sciumo/gaigen
Computational Geometry on the Web, http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
Suter, J.: Geometric Algebra Primer, 2003, http://www.jaapsuter.com/geometric-algebra.pdf
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.

Classification of course in study plans

  • Programme MITAI Master's

    specialization NGRI , 0 year of study, summer semester, compulsory
    specialization NADE , 0 year of study, summer semester, elective
    specialization NISD , 0 year of study, summer semester, elective
    specialization NMAT , 0 year of study, summer semester, elective
    specialization NSEC , 0 year of study, summer semester, elective
    specialization NISY up to 2020/21 , 0 year of study, summer semester, elective
    specialization NNET , 0 year of study, summer semester, elective
    specialization NMAL , 0 year of study, summer semester, elective
    specialization NCPS , 0 year of study, summer semester, elective
    specialization NHPC , 0 year of study, summer semester, elective
    specialization NVER , 0 year of study, summer semester, elective
    specialization NIDE , 0 year of study, summer semester, elective
    specialization NISY , 0 year of study, summer semester, elective
    specialization NEMB , 0 year of study, summer semester, elective
    specialization NSPE , 0 year of study, summer semester, elective
    specialization NEMB , 0 year of study, summer semester, elective
    specialization NBIO , 0 year of study, summer semester, elective
    specialization NSEN , 0 year of study, summer semester, elective
    specialization NVIZ , 0 year of study, summer semester, compulsory

Type of course unit

 

Lecture

26 hod., optionally

Teacher / Lecturer

prof. Dr. Ing. Pavel Zemčík, dr. h. c.
prof. Ing. Adam Herout, Ph.D.
Ing. David Bařina, Ph.D.
doc. Ing. Vítězslav Beran, Ph.D.
Ing. Michal Španěl, Ph.D.

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. Why is it necessary to know this?
  3. Range searching and space partitioning methods: range tree; quad tree, k-d tree, BSP tree. Applications in machine vision.
  4. Coordinate systems and homogeneous coordinates. Applications in computer graphics.
  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.
  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 hod., compulsory

Teacher / Lecturer

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

Syllabus

Team or individually assigned projects.