Courbe de Bézier

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 vidéo [un peu plus d'une heure en anglais].

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.

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.

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.

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.

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}$$

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)$.

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.

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.

# 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)

Vous pouvez lire les documentations : les méthodes de Point nous permettent de faire facilement les calculs utiles.

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 :

coords = [ (10,50), (40,20), (160,20), (200,50),
                    (210, 100), (200,110), (100,200),
                    (0,290), (10,350), (120,400)]

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]

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.

# 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

On se propose d'expérimenter le module précédent avec un tracer dans matplotlib.

# 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()