26

Les Courbes de Bezier #2 : collision

sept

Voici la suite de mes essais sur les courbes de Bézier ! Aujourd’hui on parle collisions !
Alors aucun doute possible, l’utilisation des Courbes de Bézier dans le cadre d’une application temps réelle (comme un jeu) doit se faire à dose homéopathique tellement les calculs qu’ils faut mettre en oeuvre sont complexes !

Introduction

Dans mon super clone de Mario, j’ai décidé d’utiliser des surfaces délimitées par des segments et des courbes de Bézier pour gérer les collisions ! L’intérêt est assez mince car il est probable que l’échantillonnage des courbes de Bézier en une série de segments eu été plus efficace en terme de performance brutes !
Le système de collision que j’utilise est composé d’un semble de points (appelés points de contrôles) situés autour du personnage. Chaque point vérifie s’il entre en collision avec le décors, puis en fonction du moment de la collision et du type de point de contrôle, j’applique une correction à la position du personnage !

Collision avec un segment

Prenons le cas du personnage en train de retomber (suite à un saut), et intéressons-nous au point de contrôle qui se trouve au niveau de pieds et qui permet au personnage de ne pas s’enfoncer dans le décor !

A l’image i le point de contrôle se trouve à la position P(i) = A
A l’image suivante (i + 1) il se trouve à la position P(i + 1) = B

On se rend compte qu’il va entrer en collision avec le segment [C,D].
Il faut donc calculer s’il y a intersection entre les segments [A,B] et [C,D] et, si oui, corriger la position du personnage (pour l’empêcher d’entrer dans le décors).

Si l’obtention du point de collision est le but ultime de la routine dans un premier temps nous allons nous intéresser au moment de la collision. C’est à dire à l’instant t ou la collision à lieu.
Si le personnage se trouve en A à l’instant t0 et en B à l’instant t1, alors à quel instant entre t-il en collision avec le segment [C,D].

Calculer l’instant de collision est très utile, car supposons qu’il existe plusieurs points de collisions (plusieurs points de contrôles peuvent entrer en collision à des moments différents). Choisir parmi les points de collisions lequel doit être pris en compte n’est pas simple! Il est plus judicieux de calculer quel est l’instant t où une collision à eu lieu et de ne conserver que l’instant t le plus proche de t0 !

On présente donc notre segment [A,B] sous sa forme paramétrique

	I = B - A
	P(t) = A + t * I

Tous les points du segment sont représenté par 0 < = t <= 1.

Nous représentons également [C,D] sous sa forme paramétrique

	J = D - C
	P(t) = C + q * J

Il y a intersection entre les segments si :

  • A + t * I = C + q * J
  • et 0 < = t <= 1
  • et 0 < = q <= 1
	Ax + t * Ix = Cx + q * Jx
	Ay + t * Iy = Cy + q * Jy

	donnent 

	det = (Ix * Jy - Iy * Jx);
	t = ((Cx - Ax) * Jy + (Ay - Cy) * Jx) / det;
	q = ((Cx - Ax) * Iy + (Ay - Cy) * Ix) / det;

Si det est nul alors les droites portant les segments sont parallèles. Il ne peut donc y avoir d’intersection !

le code complet de l’intersection de 2 segment [A,B] et [C,D] est donc :

	Ix = Bx - Ax;
	Iy = By - Ay;
	Jx = Dx - Cx;
	Jy = Dy - Cy;

	det = (Ix * Jy - Iy * Jx);
	float min_t = 2.0f;
	if (det != 0)
	{
		fidet = 1.0f / (float)det;
		t = ((float)((Cx - Ax) * Jy + (Ay - Cy) * Jx)) * fidet;
		q = ((float)((Cx - Ax) * Iy + (Ay - Cy) * Ix)) * fidet;

		if ((t >= 0.0f) && (t < = 1.0f) && (q >= 0.0f) && (q < = 1.0f))
		{
			min_t = t;
			Px = (int)(t * (float)Ix);
			Py = (int)(t * (float)Iy);
		}
	}

	// min_t est l'instant de collision
	// Px et Py contiennent le point de collision

On remarquera qu'il est possible de faire une grosse partie des calculs en entier !
min_t représente ici l'instant auquel la collision se produit !

Collision avec une courbe de Bézier

Bon c'est là que ça va un peu se compliquer !
Cette fois-ci (C,D) n'est plus un segment mais deux points limitant une courbe de Bézier ! les points U et V sont les points de contrôles de la courbe.

Comme pour l'intersection de segment, ce qui nous intéresse c'est de trouver la valeur de t pour laquelle

	I = B - A
	P(t) = A + t * I
	et
	P(t) = C * (1-q)^3 + 3 * U * q(1-q)^2 + 3 * V * q^2(1-q) + D * q^3

Cette fois-ci cela ne va pas être tout à fait aussi simple, car ce système d’équations en insoluble sous sa forme actuelle !
Nous allons présenter la droite portant le segment [A,B] sous la forme d’une équation du type

	dA * Px(t) + dB * Py(t) + dC = 0
	où
	dA = By - Ay
	dB = Ax - Bx
	dC = Ay * (Bx - Ax) + Ax * (Ay - By)

Comme par ailleurs notre Courbe de Bézier est représentée par

	Px(t) = Cx * (1-q)^3 + 3 * Ux * q(1-q)^2 + 3 * Vx * q^2(1-q) + Dx * q^3
	Py(t) = Cy * (1-q)^3 + 3 * Uy * q(1-q)^2 + 3 * Vy * q^2(1-q) + Dy * q^3

Nous remplaçons dans l’équation de droite Px(t) et Py(t) par leur valeur dans l’équation de Bézier.
Il nous reste juste à trouver les valeurs de q pour lesquels :

	dA * (Cx * (1-q)^3 + 3 * Ux * q(1-q)^2 + 3 * Vx * q^2(1-q) + Dx * q^3) +
	dB * (Cy * (1-q)^3 + 3 * Uy * q(1-q)^2 + 3 * Vy * q^2(1-q) + Dy * q^3) +
	dC = 0

Alors tout d’abors on réduit un peu cette expression.
Pour faire cela (si on ne veut pas le faire à la main), on utilise un outil

On doit alors obtenir un truc du style

	cA * q^3 + cB * q^2 + cC * q + cD = 0
	avec
	cA = 3 * dA * Ux - 3 * dA * Vx + dA * Dx - dB * Cy + 3 * dB * Uy - 3 * dB * Vy + dB * Dy - dA * Cx;
	cB = -6 * dA * Ux + 3 * dA * Vx + 3 * dB * Cy - 6 * dB * Uy + 3 * dB * Vy + 3 * dA * Cx;
	cC = 3 * dA * Ux - 3 * dB * Cy + 3 * dB * Uy - 3 * dA * Cx;
	cD = dA * Cx + dB * Cy + dC;

Il convient “simplement” donc de résoudre une équation de degré 3.
cA * q^3 + cB * q^2 + cC * q + cD = 0

Pour résoudre cette équation on utilise la méthode de cardan.
Si vous avez cliqué sur le lien précédent, une vent de panique à du souffler près de chez vous! Car, en effet pour un humain normal, c’est incompréhensible !
Il existe donc sur Internet plusieurs implémentation de Cardan.

Voici la mienne qui est légèrement customisée pour les besoins de mon algorithme !!!

int IntersectionDegre3(float a, float b, float c, float d, float *tResult)
{
	const float ATAN1 = atan(1.0);
	const float ATAN3 = 8 * ATAN1 / 3.0;
	const float MININF = -0.00001;
	const float MINSUP = 1.00001;

	float p, q, r, s, t;

	b = b / (a * 3.0);
	p = b * b - c / (a * 3.0);
	q = (b * c - d) / (a * 2.0) - b * b * b;
	r = q * q;
	s = p * p * p;

	float tmp, tmp1, tmp2, tmp3;
	int nr = 0;

	tmp = r - s;
	if (r > s)
	{
		r = sqrt(r - s);
		p = (((q + r) > 0)?pow((q + r), 1.0f / 3.0f):-pow(-(q + r), 1.0f / 3.0f));
		q = (((q - r) > 0)?pow((q - r), 1.0f / 3.0f):-pow(-(q - r), 1.0f / 3.0f));

		tmp1 = q + p - b;
		if ((tmp1 >= MININF) && (tmp1 < = MINSUP)) tResult[nr++] = tmp1;

		if (r < 0.00001)
		{
			tmp2 = -(q + p) / 2.0 - b;
			tmp3 = (q + p) / 2.0 - b;
			if ((tmp2 >= MININF) && (tmp2 < = MINSUP)) tResult[nr++] = tmp2;
			if ((tmp3 >= MININF) && (tmp3 < = MINSUP)) tResult[nr++] = tmp3;
		}
	}
	if (r <= s)
	{
		r = (atan(-q / sqrt(s - r)) + 2 * ATAN1) / 3.0;
		tmp1 = 2.0 * sqrt(p) * cos(r + ATAN3) - b;
		tmp2 = 2.0 * sqrt(p) * cos(r - ATAN3) - b;
		tmp3 = 2.0 * sqrt(p) * cos(r) - b;
		if ((tmp1 >= MININF) && (tmp1 < = MINSUP)) tResult[nr++] = tmp1;
		if ((tmp2 >= MININF) && (tmp2 < = MINSUP)) tResult[nr++] = tmp2;
		if ((tmp3 >= MININF) && (tmp3 < = MINSUP)) tResult[nr++] = tmp3;
	}
	return nr;
}

Bon. On remarque tout de suite que c'est que du bonheur : des ArcTangentes (atan), des Cosinus (cos), des Puissances (pow : qui sont en fait des racines cubiques) et des Racines carrées (sqrt) !!!
En plus comme toutes bon algorithme de cardan, il ne fonctionne que si a est non nul. si a est nul alors on se retrouve avec une équation de degré 2 qui peut être résolue avec la fonction suivante :

int IntersectionDegre2(float a, float b, float c, float *result)
{
	const float MININF = -0.00001;
	const float MINSUP = 1.00001;

	float delta = (b * b) - 4 * (a * c);
	float tmp;
	int nr = 0;

	if (delta > 0)
	{
		tmp = (-b + sqrt(delta)) / (2 * a);
		if ((tmp >= MININF) && (tmp < = MINSUP)) result[nr++] = tmp;
		tmp = (-b - sqrt(delta)) / (2*a);
		if ((tmp >= MININF) && (tmp < = MINSUP)) result[nr++] = tmp;
	}
	return nr;
}

Rem : je n'ai pas encore fini le portage des ces fonctions en assembleur. Je ne manquerai pas de faire un petit post pour indiquer le gain de performance obtenu !

On remarque que ces fonctions ne retournent que les valeurs de q (le paramètre de la courbe de Bézier) comprise entre 0 et 1.
Les autres solutions de q donneraient des coordonnées de point en dehors des bornes (C et D) de la courbe de Bézier !

le code de l'intersection d'un segment [A,B] et d'une courbe de Bézier (C,U,V,D) est donc :

	Ix = Bx - Ax;
	Iy = By - Ay;

	dA = By - Ay;
	dB = Ax - Bx;
	dC = Ay * (Bx - Ax) + Ax * (Ay - By);

	cA = 3 * dA * Ux - 3 * dA * Vx + dA * Dx - dB * Cy + 3 * dB * Uy - 3 * dB * Vy + dB * Dy - dA * Cx;
	cB = -6 * dA * Ux + 3 * dA * Vx + 3 * dB * Cy - 6 * dB * Uy + 3 * dB * Vy + 3 * dA * Cx;
	cC = 3 * dA * Ux - 3 * dB * Cy + 3 * dB * Uy - 3 * dA * Cx;
	cD = dA * Cx + dB * Cy + dC;

	if (cA == 0)
		nRes = IntersectionDegre2((float)cB, (float)cC, (float)cD, tRes);
	else
		nRes = IntersectionDegre3((float)cA, (float)cB, (float)cC, (float)cD, tRes);
	if (nRes > 0)
	{
		float min_t = 2.0;
		for (r = 0 ; r < nRes ; r++)
		{
			q = tRes[r];
			Px = Cx*(1-q)*(1-q)*(1-q) + 3*Ux*(1-q)*(1-q)*q + 3*Vx*(1-q)*q*q + Dx * q*q*q;
			Py = Cy*(1-q)*(1-q)*(1-q) + 3*Uy*(1-q)*(1-q)*q + 3*Vy*(1-q)*q*q + Dy * q*q*q;

			if (Ix != 0)
				t = (Px - Ax ) / (float)Ix;
			else
				t = (Py - Ay ) / (float)Iy;

			if ((t >= 0.0f) && (t < = 1.0f) && (t < min_t))
			{
				min_t = t;
		         	Px = (int)(t * (float)Ix);
		         	Py = (int)(t * (float)Iy);
			}
		}
	}

	// min_t est l'instant de collision
	// Px et Py contiennent le point de collision

Conclusion

Le calcul des intersections d'un segment et d'une courbe de Bézier sont près de 100 fois (en C tout du moins) plus lent que le calcul de l'intersection de 2 segments.
Il est donc évidement qu’échantillonner les Courbes de Bézier en une dizaine de segments serait rentable en terme de temps CPU et quasiment imperceptible en terne de qualité de rendu !

Il convient donc d'utiliser les courbe de Bézier avec parsimonie !

Une fois que j'aurai porté tous les calculs en assembleur je ferai un point sur le nombre de cycles que me coûte cette fantaisie ! Éventuellement j'abandonnerai les courbes de Bézier dans leur forme analytique pour opter pour un système échantillonné !

 | Tags:

Répondre

Human control : 3 + 7 =