29

Les Courbes de Bézier #1

août

Un peu de géométrie aujourd’hui !
Je me suis mis à m’intéresser aux courbes de Bezier il y a quelques mois de cela ! Et je dois bien avouer que si leur utilisation est quelques peu consommatrice de ressources, j’ai un peu tendance a en abuser en ce moment, car ces courbes (comment dire) me fascinent !
Je dirai pour faire simple que la courbe de Bezier est au polygone ce que le potentiomètre est à l’interrupteur (c’est beau hein ?).


Je me suis donc mis dans l’idée de les utiliser un peu partout ! Collision, surfaces texturées, mecanique physique, …
Autant dire que c’est une drôle d’idée qui m’est passé par la tête. J’étais loin de me douter jusqu’où cette histoire allait m’entraîner. Si la définition d’une forme (2D) polygonale est assez simple (tout est relatif), gérer une forme courbe demande un peu plus de math, ce qui pour un vieillard comme mois n’a pas été de tout repos !

Introduction

Imaginions que vous ayez un point P qui doive aller d’un point A à un point B en un temps t. La représentation la plus “évidente” que décrit l’ensemble des points P au cours du temps est un segment. C’est-à-dire tous les points se situant entre A et B et sur la droite (A, B).
Maintenant, imaginons que nous souhaitions donner à notre point P une direction de départ et une direction d’arrivée. Un peu comme si on disait: “Notre point doit aller de A à B mais au départ il va dans la direction de C et à l’arrivée il doit aller dans la direction de D !” Le problème semble un peu plus compliqué à résoudre !

Hermite

C’est exactement ce que fait la courbe paramétrique de degré 3 dites de Hermite.

	Soit deux point P1 et P2
	Soit deux tangentes à ces points T1 et T2

	P(t) = a * P1 + b * P2 + c * T1 + d * T2

	avec

	a = (2t^3 - 3t^2 + 1)
	b = (-2t^3 + 3t^2)
	c = (t^3 - 2t^2 + t)
	d = (t^3 -  t^2)

Pour obtenir tous les points de la courbe, il faut faire varier t de 0 (auquel cas on obtient P1) à 1 (auquel cas on obtient P2).

Bézier

Les courbes de Bézier sont également des courbes paramétriques de degré 3.
Il existe une bijection qui permet de transformer une courbe de Hermite en une courbe de Bézier (car c’est finalement quasiment la même chose).
Il n’y a donc aucune raison pour que l’informatique aie retenu la courbe de Bézier plutôt que celle d’Hermite, et pourtant c’est bien Bézier donc on parle partout. Cela n’a aucune importance gardez juste à l’esprit que, si un jour vous tombez sur un article qui parle des courbes d’Hermite, il s’agit en fait d’une représentation alternative des courbes de Bézier.

La courbe de Bézier n’utilise plus de tangente ! On parle de points de contrôles ! Dans la pratique c’est exactement la même chose puisque ces points de contrôles permettent de recréer les tangentes !

	Soit deux points P1, P2
	Soit deux points de contrôle C1, C2

	P(t) = (1 - t)^3 * P1 + t*(1 - t)^2 * C1 + t^2*(1 - t) * C2 + t^3 * P2

Remarque: Même si l’équation de a courbe de Bézier à l’air plus simple en fait les deux équations on la même complexité.

Définition

Il n’existe pas de définition à proprement parlé d’une courbe de Bézier, donc je peux me risquer à fournir la mienne :

"Une courbe de Bézier est une portion de la courbe définie par une équation
paramétrique de degré 3, passant par les points P1 et P2
et dont le tracé est contraint par les points de contrôles C1 et C1".

Voilà!

Courbes de Bézier convexes et courbes de Bézier concaves

Alors attention, car là je m’apprête à inventer un concept qui n’existe pas !

J’ai décidé, (moi tout seul) d’appeler une courbe de Bézier “convexe” toutes les courbes de Bézier dont les points P1, C1, C2 et P2 forme un polygone convexe.
Et par conséquent, les autres seront des courbes de Bézier “concaves”.

Ci-dessous quelques exemples de courbes de Béziers (que j’ai piqué sur le site du CNRS, j’espère qu’ils ne m’en voudront pas trop !)

Dans ces 4 exemples de courbe seul la première est donc convexe !

Quels sont les avantages des courbes de Bézier

Les courbes de Bézier offrent de nombreux avantages :

  • Tout d’abord ce sont des courbes. Il est donc possible de représenter des formes impossibles à obtenir avec un polygone.
  • Toutes les transformations que l’on peut appliquer un un polygone (rotation, translation, mise à l’échelle, inclinaison…) peuvent être appliquées à la courbe. La transformation des 4 points définissant la courbe entraîne la transformation de tous les points de la courbe.
  • Tous les points de la courbe sont contenus dans le plus grand polygone défini par P1, C1, C2 et P2. Dans le cas d’une courbe de Bézier convexe, ce plus grand polygone est (P1, C1, C2, P2).

Tracé d’une courbe de bézier

Bon c’est là qu’on entre dans le vif du sujet car tracer une courbe de Bézier (de façon efficace) n’est déjà pas une chose simple !

Le problème c’est que l’équation de la courbe de Bézier est paramétrique, c’est-à-dire que chaque point de la courbe est obtenu à partir d’une valeur de t variant dans l’espace [0, 1[ !
Toute la question est de savoir quel est la valeur de l’incrément (e) que l’on doit appliquer à t pour obtenir tous les points de la courbe !

  • Si (e) est trop grand, on risque de ne pas tracer tous les points de la courbe.
  • Si (e) est trop petit, on risque de tracer plusieurs fois le même pixel.

Il n’existe pas de valeur (e) idéale et permettant de parcourir tous les points de la courbe sans obtenir 2 fois le même point. En clair, la longueur du segment défini par P(t) et P(t + e) n’est pas constante.
On doit donc se résoudre à choisir une valeur de (e) arbitraire. On ne trace alors des segments reliant P(t) à P(t + e).

Mais quelle valeur choisir pour e ?

Le choix de la valeur de (e) est assez complexe, car il ne sera le même en fonction des transformation que l’on applique à la courbe ! Si vous effectuez un zoom sur votre courbe sans réadapter la valeur de (e), vous allez rapidement vous mettre à voir les segments apparaître ! A l’inverse si vous réduisez la taille de votre forme en conservant la même valeur de (e) alors vous allez vous mettre à tracer de segments de longueur nulle inutilement.

Il est donc judicieux de définir un vecteur associé (vE) à votre courbe dont la norme représentera le nombre de segments que l’on doit tracer.
Les transformations appliquées à la courbe devront également être appliquées au vecteur. Ainsi la transformation de la courbe induira la fluctuation de (e).

Pour définir vE on effectue un précalcul sur le courbe afin de définir sa norme (avant transformation)

	oPoint previousPixel = P0;
	oPoint vE;
	int maxDistance = 0;
	float e = 0.01;
	float nbS = 100;								// nbS = 1 / e

	for (t = 0.0 ; t < 1.0 ; t += e)
	{
		P = computeBezierCurve(t);
		stepDistance = distance(previousPixel, P);
		if (stepDistance > maxDistance)
		{
			maxDistance = stepDistance;
			vE.x = P.x - previousPixel.x;
			vE.y = P.y - previousPixel.y;
		}
		previousPixel = P;
	}

	float maxLongueur = 10;
	float vNorme = (maxDistance * nbS) / maxLongueur;
	vE = normalize(vE, vNorme);
  • On choisit un (e) arbitraire (dans le code ci-dessus j’ai pris 0.01, ce qui veut dire que je souhaite tracer 100 segments pour représenter ma courbe de Bézier).
  • On recherche pour cette valeur de (e), le segment à tracer le plus long
  • Enfin on normalise vE puis on le multiplie par le nombre de segments voulu pour tracer des segments d’une longueur maximum de maxLongueur pixels !

Dans la Pratique :
Supposons qu’a la sortie de la boucle, maxDistance vaillent 1.5. Cela voudra dire que le plus grand segment que l’on a eu à tracer mesurait 1.5 pixels !
On souhaite que le plus grand segment mesure maxLongueur (ici 10) pixels. On a donc tracer trop de Segment.
Le nombre de segments (vNorme) que l’on aurait du tracer est : 1.5 * 100 / 10 = 15 !
(e) aurait du valoir 1 / 15 = 0.066.

Le nombre de segment devient donc la norme du vecteur vE.
C’est exactement ce que fait l’instruction

	vE = normalize(vE, vNorme);

Qui va normer vE puis multiplier chacun de ses composantes par vNorme.

En sortie de cet algorithme, la norme de vE définit le nombre de segments que l’on doit tracer.
Il faudra appliquer sur vE, les mêmes transformations que sur la courbe (attention, vE est un vecteur, pas un point. Il ne faut donc pas lui appliquer les translations !)

Méthode alternative

Une méthode plus simple (celle que j’utilise) est de calculer la longueur (approximative) de la courbe de Bézier avant transformation puis d’appliquer a cette longueur les changement d’échelle !
Pour calculer la longueur de la courbe on échantillonne celle-ci et on ajoute la longueur des segments .

int CHlgShape::GetCurveLength(int x1, int y1, int cx1, int cy1, int cx2, int cy2, int x2, int y2)
{
	int xCoef0, xCoef1, xCoef2, xCoef3;
	int yCoef0, yCoef1, yCoef2, yCoef3;

	yCoef3 = -   y1 + 3*cy1 - 3*cy2 + y2;
	yCoef2 = + 3*y1 - 6*cy1 + 3*cy2;
	yCoef1 = - 3*y1 + 3*cy1;
	yCoef0 = +   y1;

	xCoef3 = -   x1 + 3*cx1 - 3*cx2 + x2;
	xCoef2 = + 3*x1 - 6*cx1 + 3*cx2;
	xCoef1 = - 3*x1 + 3*cx1;
	xCoef0 = +   x1;

	float i, t, xf, yf;
	float length = 0;
	int xi, yi;
	for (i = 0, t = 0.01f ; i < 100 ; i++, t+= 0.01f)
	{
		xf = xCoef3*t*t*t + xCoef2*t*t + xCoef1*t + xCoef0 + 0.5;
		yf = yCoef3*t*t*t + yCoef2*t*t + yCoef1*t + yCoef0 + 0.5;

		xi = (int)xf;
		yi = (int)yf;
		length += sqrt((xi - x1)*(xi - x1) + (yi - y1)*(yi - y1));
		x1 = xi;
		y1 = yi;
	}

	return (int)length;
}
On trace rarement une courbe de Bézier

Le tracé de courbe de Bézier n'a pas grand intérêt !
Les courbes de Bézier sont surtout utiles pour délimiter une surface, laquelle peut ensuite être soit tracée, soit utilisée pour gérer des collisions, ...

Dans ce cas, on n'utilise pas du tout les méthodes décrites précédemment ! On doit se lancer dans des techniques un petit peut plus compliquées !

Mais ça ira pour aujourd'hui !
Il me reste à vous donner un lien vers un petit outil que j'ai développé et qui pourrait (peut être) vous servir un jour - un éditeur de courbes de Bézier.
Je me sers des courbes de Bézier pour les collisions (entre autre) dans mon moteur 2D. Encore fallait-il un moyen simple de créer des formes à base de segments et de courbes de Bézier. N'ayant rien trouvé sur Internet, je me suis donc décidé à coder mon petit outil sans prétention !

Il fonctionne en HTML5 !
Il est libre de tout droit !
Si ie9 est de loin le navigateur le plus rapide pour les la gestion des canvas, je vous conseille (pour une fois) d'utiliser Firefox car celui-ci dispose d'une propriété CSS qui lui permet de zoomer une image sans appliquer de filtre bilinéaire.

L'éditeur se trouve ici

A suivre...

Dans Les courbes de Bézier #2, on va utiliser les courbes pour créer des zones de collisions ultra précises.
Dans Les courbes de Bézier #3, on va s'occuper de tracer une surface délimitée par des segments et des courbes de Bézier.

Et après on verra !

 | Tags:

3 Responses to “Les Courbes de Bézier #1”

  1. William dit :

    L’éditeur de Courbes de Bezier m’intéresse beaucoup. Merci d’avoir mis le code à disposition. Pourrais tu m’expliquer comment je peux l’utiliser pour éditer autre chose que l’image proposé par défaut.

    Merci.

  2. Etienne SOBOLE dit :

    Ouai. Bon ben si ça t’intéresse alors je vais faire un petit post pour détailler :

    - Comment l’utiliser
    - Comment l’implémenter ‘et comment ça marche)
    - Les évolutions éventuelles que j’y apporte.

  3. Antoine dit :

    Merci pour ces explications!! j’ai beaucoup mieux compris le principe!!!!!!!!
    merci beaucoup!

Répondre

Human control : 8 + 5 =