Title:

Computational Geometry

Code:VGE
Ac.Year:2019/2020
Sem:Summer
Curriculums:
ProgrammeField/
Specialization
YearDuty
IT-MSC-2MBI-Elective
IT-MSC-2MBS-Elective
IT-MSC-2MGM-Elective
IT-MSC-2MGM2ndCompulsory
IT-MSC-2MIN-Elective
IT-MSC-2MIS-Elective
IT-MSC-2MMM-Elective
IT-MSC-2MPV-Elective
IT-MSC-2MSK-Elective
MITAINADE-Elective
MITAINBIO-Elective
MITAINCPS-Elective
MITAINEMB-Elective
MITAINGRI-Compulsory
MITAINHPC-Elective
MITAINIDE-Elective
MITAINISD-Elective
MITAINISY-Elective
MITAINMAL-Elective
MITAINMAT-Elective
MITAINNET-Elective
MITAINSEC-Elective
MITAINSEN-Elective
MITAINSPE-Elective
MITAINVER-Elective
MITAINVIZ-Compulsory
Language of Instruction:Czech
Credits:5
Completion:examination (written)
Type of
instruction:
Hour/semLecturesSeminar
Exercises
Laboratory
Exercises
Computer
Exercises
Other
Hours:2600026
 ExamsTestsExercisesLaboratoriesOther
Points:5100049
Guarantor:©paněl Michal, Ing., Ph.D. (DCGM)
Deputy guarantor:Bařina David, Ing., Ph.D. (DCGM)
Lecturer:Bařina David, Ing., Ph.D. (DCGM)
Beran Vítězslav, Ing., Ph.D. (DCGM)
Herout Adam, prof. Ing., Ph.D. (DCGM)
©paněl Michal, Ing., Ph.D. (DCGM)
Zemčík Pavel, prof. Dr. Ing. (DCGM)
Faculty:Faculty of Information Technology BUT
Department:Department of Computer Graphics and Multimedia FIT BUT
Schedule:
DayLessonWeekRoomStartEndLect.Gr.Groups
WedlecturelecturesD0207 09:0010:501MIT 2MIT MGM xx
 
Learning objectives:
  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.
Description:
  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.
Knowledge and skills required for the course:
  
  • Basic knowledge of linear algebra and geometry.
  • Good knowledge of computer graphics principles.
  • Good knowledge of basic abstract data types and fundamental algorithms.
Subject specific learning outcomes and competencies:
  
  • 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 competencies:
  
  • 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.
Why is the course taught:
  This course focuses on topics and classical problems which, in small variations, students meet in other courses (e.g. computer vision or computer graphics). These topics are rather marginal with respect to the content of these courses, so there is typically not enough time to discuss them in more detail. However, their knowledge is needed in practice.
The lectures present some of the classical problems of computational geometry (nearest neighbour search, range searching, space partitioning methods, 2D/3D triangulation, Voroni diagrams, etc.) and further deepen your theoretical background in the field of affine and projective geometry, homogeneous coordinates, quaternions, etc.
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. 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. 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.
Syllabus - others, projects and individual work of students:
 Team or individually assigned projects.
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.
Study literature:
 
  • 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/data/2003-3-12-geometric-algebra/geometric-algebra.pdf
  • Gaigen, http://www.science.uva.nl/ga/gaigen/
  • Computational Geometry on the Web, http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
Controlled instruction:
  The evaluation includes mid-term test, individual project, and the final exam.
Progress assessment:
  
  • 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.
 

Your IPv4 address: 54.211.135.32