A configuration specifies the position of all points
of a mechanical system in relation to a given coordinate system.
Expressed using a vector in generalized coordinates.
The configuration space is the space of all
possible configuration, noted \(C-space\).
We note \(C-free space\) the \(C-space\) without collisions with
obstacles.
A path is a continuous sequence of
configurations.
It connects an initial configuration \(q_s\) to a configuration \(q_f\)
It does not collide with any obstacles (\(\forall q_i \in C-free\))
A trajectory is a path with parametrisation of the
time.
RQ : thus we can do various kind of planning :
motion, path, trajectory…
(state : pos + velocity at a time, motion : change of state).
Exact approaches
Visibility graph
A visibility graph for a set of polygonal (convex)
obstacles is the set of unblocked lines between the vertices of the
obstacles + \(q_s\) and \(q_f\).
Thus :
\(P\) is connected to \(P'\) iff it is visible from \(P'\)
Solution = shortest path in the visibility graph
Limitations : Difficult for d > 2, object =
points (minkowsky distances to mitigate), Computationally exensive with
lot of vertices (naive : \(O(n^3)\),
efficient (sweep line) \(O(n^2
log(n))\)).
Ref : CGAL (computational geometry library).
Voronoy Diagram
Given a set of points \(P\), we
partitionate the space using the following metric : a point \(p\) in the space is of class \(i\) if its closests neighbough in \(P\) is \(P_i\).
The points on the edges of the voronoy diagram are the furthest from
the obstacles.
\(\rightarrow\) Idea : Construct a
path between \(q_s\) and \(q_f\) following the edges of the voronoi
diagram.
RQ : We can reduce the length of the path by
smoothing.
Limitation :
Hard to compute for non polygonal worlds / high dimensions
Approximate algorithm exist
Not necessarily the best, but guarantees completeness
Sampling approaches
Approximate cell
decomposition
Define a discrete grid of the \(C-space\), and mark any cell of the grid
colliding with an obstacle
Find path through remaining cells using \(A*\)
Subdivide the grid if no solution found, by distinguishing cells
entirely contained and those partially contained
Limitations :
One can use quad/oc tree decomposition, high dimensionality easier
but still hard
No optimality (can use visibility graph to optimise) nor
completeness
Limited assumption on obstacle / object configuration
Efficient in practice (video games…)
Exact cell decomposition
TODO
Limitation : Slow in practice (high
dimensionality)
Potential field
Idea :
Stay away from obstacle : repulsive field
Move closer to the objective : attractive field
But : Potential well (local minima) \(\rightarrow\) very difficult to tune / use
of stochastic algorithm
A shader (in this case, a pixel
shader) is a code executed by the GPU on each pixel of an image
(for instance, the screen texture).
Bases du raytracing : CF TIPE.
Qu’est ce que le rendu ?
À partir de primitives, afficher une image.
Il y a plusieurs types de rendus :
Physically base :
Ray tracing : On lance des rayons pour simuler le trajet de la
lumière.
Radiosity : On divise la scène en facettes, et on calcule la couleur
émise de chaque facette en fonction de celle émise par les autres.
Geometry base : Rasterisation. On triangularise la scène, on les
projette dans un espace image, et on utilise un pixel shader pour les
couleurs.
Ici : on va faire de la rasterisation, et utiliser OpenGL
Étapes du rendu (en italique : partie non programmable) :
Vertex shader : s’occupe de la projection des primitives dans
l’espace.
Tesselation shader : En gros : adapter le niveau de détail, sur le
GPU.
Exemple d’utilisation : Affichage d’une courbe de bézier. On fournit
4 points, et avec la tesselation, on crée les points selon le LOD.
Geometry Shader : Manipulation / Création des primitives.
Rasterisation : à partir des sommets et de leur coordonnées
dans l’espace projectif, on les affiche dans une texture avec un algo
d’affichage de triangle (Bresenham…)
Fragment shader.
On appelle BRDF (Bidirectional Reflectance
and Diffusion Function) une fonction qui définit la manière
dont la lumière est réfléchie sur une surface opaque.