Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Casteljau
Résumé
L'algorithme de Casteljau est un algorithme récursif trouvé par Paul de Casteljau pour approximer efficacement les polynômes écrits dans la base de Bernstein.
Cet algorithme peut être utilisé pour dessiner des courbes et des surfaces de Bézier. L'idée principale dans ce cas repose sur le fait qu'une restriction d'une courbe de Bézier est aussi une courbe de Bézier. L'algorithme calcule de manière efficace le point de paramètre et les points de contrôle des courbes de la restriction à et à . On applique alors de nouveau l'algorithme sur les deux restrictions jusqu'à réaliser un critère donné (celui-ci peut être, par exemple, que la précision soit inférieure au pixel).
Cet algorithme semble ne plus être le plus efficace car il ne permettrait pas d'utiliser l'antialiasing étant donné qu'il travaille pixel par pixel et ne donne pas d'information sur la tangente.
Historiquement, c'est avec cet algorithme que les travaux de M. de Casteljau commençaient en 1959 chez Citroën. Ils étaient publiés comme des rapports techniques, tenus très au secret par Citroën.
Ces travaux restèrent inconnus jusqu'en 1975 quand W. Böhm en a pris connaissance et les a rendu public. Cet algorithme a été très utile pour l'informatique qui utilise les courbes de Bézier dans de nombreux cas (logiciels de dessin, de modélisation...), et sans lequel le développement de l'utilisation des courbes de Pierre Bézier n'aurait pas pu se faire.
Considérons une courbe de Bézier définie par les points de contrôles , où les sont des points de . Ici on souhaite simplement calculer le point de paramètre .
Comme on peut le voir sur l'image, en calculant les barycentres de paramètres des points de contrôle consécutifs de la courbe, puis les barycentres de même paramètres de ces barycentres et ainsi de suite itérativement, on définit de cette manière une suite de listes de points que l'on va indexer , où est le barycentre de . La dernière liste ne contient en fait qu'un point, qui est le point de la courbe de paramètre .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.