INFO4216 : Géométrie Computationnelle et Images Digitales
Computational geometry and digital images
- Responsable(s) :
-
- Daniel Hirschkoff
- Enseignant(s) :
-
- Vincent Nivoliers
Niveau
M1+M2
Discipline
Informatique
Public externe (ouverts aux auditeurs de cours)
Informations générales sur le cours : INFO4216
This course will focus on algorithms and data structures for geometric objects (segments, polygons, surfaces, volumes, …) and digital images. We will focus on various ways such
data can be generated, processed and used. After introducing the classical data structures to store 2D and 3D shapes, we will cover how these data structures are used depending on
the way the data is generated or processed. Typical algorithms include nearest neighbor search or ray tracing queries, surface reconstruction from point sets, parameterization for
texture mapping, rasterization and image synthesis.
Detailed Notions
Image processing
- Colors
- Histograms
- Fourrier analysis
- Shannon theorem
- Local descriptor
3D Geometry basics
- Vectors, Matrices, Perspective transformations
- Triangles meshes
- Normals
- Parameterization
- Splines
Rendering
- Camera
- Visibility
- Rasterization
- Ray tracing
- Depth
- Lighting
- Shadows
Geometry processing
- Differential operators on meshes
- Curvature
- Mesh quality
- Compression
Computational geometry
- Convex hulls
- Delaunay /Voronoi
- Spatial acceleration structures
- Predicates and robustness
This course will require basic knownlege in geometry and linear algebra : points, vectors, matrices, basic linear transformations (translation, rotation, scaling, projection), dot
and cross product, elementary area computation for polygons, trigonometry, barycenters and barycentric coordinates.
In terms of practicals and programming, although many state of the art existing libraries related to the field use the C++ programming language, we decided to go for a notebook
approach using python, numpy and various bindings in an attempt for user-friendliness. As non python specialists ourselves, we will not make use of language specific features and
focus on basic algorithm logic.