Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:tds:maths:splines:bezier [2023/01/18 13:19] – supprimée - modification externe (Unknown date) 127.0.0.1
+++ nsi:tds:maths:splines:bezier [2023/01/22 19:25] (Version actuelle) – goupillwiki
@@ Ligne 1: / Ligne 1: @@
+====== Courbe de Bézier ======
+<WRAP box>**Wikipedia** Les courbes de Bézier sont des courbes polynomiales paramétriques développées pour concevoir des pièces de carrosserie d'automobiles. Elles ont été conçues par Paul de Casteljau en 1959 pour Citroën et, indépendamment, par Pierre Bézier en 1962 pour Renault (les travaux de Paul de Casteljau étant confidentiels, c'est le nom de Bézier qui est passé à la postérité). Elles ont de nombreuses applications dans la synthèse d'images et le rendu de polices de caractères. Elles ont donné naissance à de nombreux autres objets mathématiques.
+Il existait avant Bézier des courbes d'ajustement nommées splines, mais dont le défaut était de changer d'aspect lors d'une rotation de repère. Les splines conformes aux principes de Bézier seront par la suite nommées B-splines.
+</WRAP>
+On rencontre des B-splines dans de très nombreux domaines. Les polices de caractères, les jeux vidéos, la modélisation physique... Pour un panorama, je vous recommande cette [[https://www.youtube.com/watch?v=jvPPXbo87ds&t=3954s|vidéo]] [un peu plus d'une heure en anglais].
+===== Qu'est-ce ? =====
+On se donne une série de points. On veut faire passer une courbe par ces points. La solution la plus simple est de tracer des segments entre les points.
+{{ :nsi:tds:maths:splines:bezier-1.png?nolink&400 |}}
+Mais ce n'est pas très satisfaisant. On voudrait une courbe plus souple, plus arrondie. Avec les courbes de Bézier, on ajoute des points de contrôles permettant de préciser les tangentes désirées.
+{{ :nsi:tds:maths:splines:bezier-2.png?nolink&400 |}}
+Les points en bleu sont les points par lesquels la courbe passe. Les points en jaune indiquent les tangentes. Il n'y a rien de plus à ajouter.
+===== Formule =====
+La courbe précédente est formée de 5 points bleus qui délimitent 4 arcs. Chaque arc commence par un point bleu et fini par un point bleu. Chaque arc a également deux points de contrôle.
+Voyons maintenant comment on calcule l'arc entre deux points. Cet arc est défini par les 4 points $P_0P_1P_2
+p_3$. $P_1$ et $P_2$ sont des points de contrôle.
+{{ :nsi:tds:maths:splines:bezier-3.png?nolink&400 |}}
+Pour chaque valeur de $t$ dans $[0 ; 1]$, on calcule un point $M$. Comme $M$ est fonction de $t$, on peut noter $M(t)$.
+On calcule $M(t)$ par étape :
+  * on calcule le barycentre $P_{01}$ de $P_0$ et $P_1$ avec les poids $1-t$ et $t$. Dit plus simplement, avec une notation qui pourrait déplaire à des mathématiciens mais qui est facile à comprendre, on dira que $P_{01} = (1-t)\cdot P_0 + t \cdot P_1$.
+  * de la même façon, $P_{12} = (1-t)\cdot P_1 + t \cdot P_2$ et $P_{23} = (1-t)\cdot P_2 + t \cdot P_3$
+  * de la même façon, $P_{012} = (1-t)\cdot P_{01} + t \cdot P_{12}$ et $P_{123} = (1-t)\cdot P_{12} + t \cdot P_{23}$
+  * enfin $M = (1-t)\cdot P_{012} + t \cdot P_{123}$
+Si on remet tout ensemble :
+$$M(t) = (1-t)^3\cdot P_0 + 3t(1-t)^2\cdot P_1 + 3 (1-t) t^2\cdot P_2 + t^3\cdot P_3$$
+Mais cette forme est sans doute plus efficace :
+$$M(t) = P_0 + t \cdot(-3 P_0 + 3 P_1) + t^2 (3 P_0 - 6 P_1 + 3 P_2)  + t^3 (-P_0 + 3 P_1 -3 P_2 + P_3)$$
+En effet, on peut calculer au préalable : $c_0 = P_0$ ; $c_1 = -3 P_0 + 3 P_1$ ; ... et ensuite on a
+$$M(t) = c_0 + t \cdot c_1 + t^2 \cdot c_2 + t^3 \cdot c_3$$
+Ce qui est très rapide à faire.
+On constate, en remplaçant, que $M(0) = P_0$ et $M(1) = P_3$. La courbe, en général, ne passe ni par $P_1$ ni par $P_2$.
+On peut enfin adopter une écriture **matricielle** (//programme des maths expertes en terminale//)
+$$M(t) = \begin{bmatrix}1 & t & t^2 & t^3\end{bmatrix} \cdot \begin{bmatrix}1 & 0 & 0 & 0\\ -3 & 3 & 0 & 0\\ 3 & -6 & 3 & 3 & 0\\ -1 & 3 & -3 & 1\end{bmatrix} \cdot \begin{bmatrix}P_0 \\ P_1 \\ P_2 \\ P_3 \end{bmatrix}$$
+<WRAP tip>
+Cette dernière écriture a l'avantage de mettre en avant une sorte de signature de la spline de Bézier : il y a d'autres splines qui fonctionnent à peu près de la même façon mais avec quelques choix différents. Elles prendront toutes à peu près la même forme. La seule différence portera sur la matrice centrale. Cela permet d'aller vers quelque chose de plus général.
+</WRAP>
+===== Vecteur tangent =====
+Dans certains cas, il peut être intéressant de connaître le vecteur tangent. Il suffit de dériver par rapport à $t$ :
+$$M'(t) = (-3 P_0 + 3 P_1) + 2t (3 P_0 - 6 P_1 + 3 P_2)  + 3t^2 (-P_0 + 3 P_1 -3 P_2 + P_3)$$
+On constate alors que $M'(0) = 3 (P_1 - P_0) = 3 \overrightarrow{P0P_1}$ et $M'(1) = 3 \overrightarrow{P_2P_3}$.
+La tangente en $P_0$ suit donc bien la ligne $(P_0P_1)$.
+<WRAP tip>
+On pourrait utiliser la courbe dans une animation. La courbe serait la trajectoire, $t$ le temps et $M(t)$ la position de l'élément mobile à l'instant $t$. $M'(t)$ représenterait alors la vitesse de l'élément mobile.
+</WRAP>
+===== Quoi faire ? =====
+Une courbe de Bézier interviendrait dans un projet. Par exemple un jeu Pygame ou un logiciel de dessin.
+Nous allons commencer par concevoir tous les outils pour calculer les coordonnées des points d'une courbe de Bezier puis nous allons l'appliquer dans différents exemples.
+==== Une classe Point ====
+Quand on fait un calcul comme $3P_1 - 3P_0$ il faut comprendre que l'on fait exactement le même calcul sur chaque coordonnée. On calcule donc $x = 3x_1 -3x_0$ et $y = 3y_& - 3y_0$. Doubler tous les calculs peut devenir lourd en termes d'écriture du programme. On choisit donc de représenter le point par un objet ''Point'' ce qui va alléger le code.
+<code python>
+# point.py
+class Point:
+    def __init__(self, x, y):
+        self.x = x
+        self.y = y
+    def __add__(A, B):
+        '''
+        donne un sens au calcul A + B où A et B sont de type Point
+        '''
+        return Point(A.x + B.x, A.y + B.y)
+    def __sub__(A, B):
+        '''
+        donne un sens au calcul A - B où A et B sont de type Point
+        '''
+        return Point(A.x - B.x, A.y - B.y)
+    def kmul(self, k):
+        '''
+        renvoie une copie du point avec les coordonnées multipliées par k
+        ainsi on écrira P.kmul(-3) au lieu d'écrire -3 P
+        '''
+        return Point(self.x*k, self.y*k)
+</code>
+Vous pouvez lire les documentations : les méthodes de ''Point'' nous permettent de faire facilement les calculs utiles.
+<WRAP box>
+Ajoutez la classe ''Point'' à votre projet
+</WRAP>
+==== Les données initiales ====
+On se donne une liste de points. Cette liste contient alternativement des points de la courbe (en bleu sur les exemples plus haut) et les points de contrôle (en jaune) Vous avez pu voir qu'il y a deux points de contrôle entre deux points de la courbe :
+Point, Contrôle, Contrôle, Point, Contrôle, Contrôle, Point, Contrôle, ..., Point
+Exemple :
+<code python>
+coords = [ (10,50), (40,20), (160,20), (200,50),
+                    (210, 100), (200,110), (100,200),
+                    (0,290), (10,350), (120,400)]
+</code>
+Dans cette séquence, nous avons 3 arcs de courbe de Bézier :
+  * le 1er arc constitué des points de coordonnées ''%%coords[0:4]%%''
+  * le 2e arc constitué des points de coordonnées ''%%coords[3:7]%%''
+  * le 3e arc constitué des points de coordonnées ''%%coords[6:10]%%''
+<WRAP tip>Le point d'indice 3 sert comme dernier point du premier arc et comme premier point du 2e. De même le point d'indice 6 sert deux fois.</WRAP>
+<WRAP box>
+  * Soit ''i'' le rang d'un point. Donnez un calcul simple permettant de savoir s'il s'agit d'un point de la courbe ou d'un point de contrôle.
+  * soit 'coords'' une liste de coordonnées. Donnez un calcul simple permettant de savoir si la taille de ''coords'' est acceptable (''coords'' devrait avoir 4, 7, 10, 13, ... éléments)
+  * soit 'coords'' une liste de coordonnées. Donnez un calcul permettant de savoir le nombre d'arcs (4 points: 1 arc ; 7 points: 2arcs ; 10 points: 3arcs...)
+  * Donnez un calcul simple permettant de savoir, pour un arc donné, l'indice du premier des points constituant cet arc (arc 0: commence au point 0 ; arc 1: commence au point 3 ; arc 2: commence au point 6...)
+</WRAP>
+==== Une classe Bezier ====
+Cette classe aura la responsabilité des calculs liés à la courbe de Bézier.
+Ajoutez le module suivant à votre projet et complétez les fonctions.
+<code python>
+# bezier.py
+from point import Point
+class Bezier:
+    def __init__(self, coords):
+        '''
+        coords: liste de paire (x,y) représentant les points
+        '''
+        # vérifier que le nombre de points est valide
+        self.points = [Point(x,y) for x,y in coords]
+    def calc_coeffs(self, i:int):
+        '''
+        i:indice de l'arc considéré
+        la courbe de Bézier est calculée avec les points P0, P1, P2, P3 de l'arc
+        on calcule 4 coefficients :
+        c0 = P0
+        c1 = -3P0 + 3P1
+        c2 = 3P0 - 6P1 + 3P2
+        c3 = -P0 + 3P1 -3P2 + P3
+        La fonction renvoie c0, c1, c2, c3
+        remarque: chaque coefficient est de type Point.
+        '''
+        # vérifie que i est bien une valeur valide
+        # récupérer les 4 points formant l'arc i
+        # calculer les coefficients et les renvoie
+    def M(self, t:float, i:int):
+        '''
+        t: flottant entre 0 et 1, compris
+        i: rang de l'arc considéré
+        renvoie c0 + c1*t + c2*t**2 + c3*t**3 avec c0, c1, c2, c3
+        les coeffs de la fonction précédente.
+        '''
+        # obtenir les valeurs des coefficients
+        # renvoie le résultat du calcul
+    def tangent(self, t:float, i:int):
+        t: flottant entre 0 et 1, compris
+        i: rang de l'arc considéré
+        renvoie c1 + 2*c2*t + 3*c3*t**2 avec c0, c1, c2, c3
+        '''
+        # obtenir les valeurs des coefficients
+        # renvoie le résultat du calcul
+    def plot_points(self, N=100):
+        '''
+        renvoie la liste des points (type Point) constituant la courbe.
+        N représente le nombre de points à calculer pour chaque arc.
+        '''
+        # préparer une liste vide
+        # pour chaque arc i,
+        #    pour chaque t allant de 0/N à (N-1)/N
+        #        calculer M(t, i) et l'ajouter à la liste
+        # compléter la liste avec une copie du dernier point de self.points
+        # renvoyer la liste
+</code>
+<WRAP tip>
+Lors de l'utilisation, pour un arc donné, on calculera ''M(t)'' une bonne centaine de fois. Il serait donc bienvenu de ne pas devoir recalculer les coefficients ''c0'', ''c1'', ''c2'', ''c3'' à chaque fois. Le mieux serait de calculer les coefficients de chaque arc dès le début (''%%__init__%%'') et les placer dans un tableau de façon à ne plus avoir à refaire le calcul ensuite.
+</WRAP>
+==== Utilisation avec matplotlib ====
+On se propose d'expérimenter le module précédent avec un tracer dans matplotlib.
+<code python>
+# demobezier.py
+# démonstration en utilisant matplotlib
+import matplotlib.pyplot as plt
+from bezier import Bezier
+coords = [ (10,50), (40,20), (160,20), (200,50),
+                    (210, 100), (200,110), (100,200),
+                    (0,290), (10,350), (120,400)]
+spline = Bezier(coords)
+# tracé de la courbe
+pts = spline.plot_points()
+# dans matplotlib, il faut placer les x et les y dans deux listes séparées
+x = [pt.x for pt in pts]
+y = [pt.y for pt in pts]
+plt.plot(x, y)
+# tracé des points :
+n = len(coords)
+x = [coords[i][0] for i in range(0,n,3)]
+y = [coords[i][1] for i in range(0,n,3)]
+plt.scatter(x, y, c='b')
+# tracé des contrôles
+x = [coords[i][0] for i in range(n) if i%3 != 0]
+y = [coords[i][1] for i in range(n) if i%3 != 0]
+plt.scatter(x, y, c='y')
+plt.show()
+</code>
+<WRAP todo>
+==== Exemple avec Tkinter ====
+</WRAP>