Discussion :

[supergrey]

Bonjour, voila le probleme, j'ai 2 points "tournés" dans une direction et par lesquels j'aimerais faire passer une courbe, voici un petit dessin pour comprendre:


J'avais eu l'idée de créer 2 segments dans la "direction des points" et d'avoir un coefficient qui aille de 0 à 1 du genre k*seg1+(1-k)*seg2 mais ca ne marche qu'à moitié à moins que j'ai fait une erreur...
Bref, si quelqu'un à compris ce que je dis et à une idée, je serait ravis de l'entendre.
Merci

[FR119492]

Salut!
Ton dessin est une superbe illustration de ce qu'est une courbe de Bézier. Il te suffit de chercher sous ce nom.
Jean-Marc Blanc

[pseudocode]

Salut!
Ton dessin est une superbe illustration de ce qu'est une courbe de Bézier. Il te suffit de chercher sous ce nom.
Jean-Marc Blanc

"Spline cubique de Hermite" pour être exact. Mais bon, je chipote.

[supergrey]

Ok, merci, d'apres ce que je comprend il faut couper chaque segment en deux et recommancer jusqu'au lissage voulu, mais ça fait beaucoup de calculs pour un lissage correct, est-ce qu'il y aurait un algo simple (pour un non matheux) qui permettrait d'alléger les calculs ? Et si possible qui permette de partir d'un point pour aller jusqu'à l'autre plutot que de devoir tout calculer avant de pouvoir utiliser les points obtenus...

Sinon, avec ma méthode le problème est qu'il va de 0 à 1 de manière linéaire, j'ai essayé d'utiliser un sinus:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

k=0.5f-cosf(k*pi)/2;

Ce qui donne un meilleur résultat mais pas suffisant, comment augmenter la courbe du sinus ?

[souviron34]

courbe de spline (dont le petit nom est "approximation du dessinateur") est ce que tu recherches.

[pseudocode]

Ok, merci, d'apres ce que je comprend il faut couper chaque segment en deux et recommancer jusqu'au lissage voulu, mais ça fait beaucoup de calculs pour un lissage correct, est-ce qu'il y aurait un algo simple (pour un non matheux) qui permettrait d'alléger les calculs ? Et si possible qui permette de partir d'un point pour aller jusqu'à l'autre plutot que de devoir tout calculer avant de pouvoir utiliser les points obtenus...

Le plus simple c'est d'utiliser l'équation paramétrique de la Spline:



P0,P1 sont les points de départ et d'arrivé.
M0 et M1 sont les tangentes aux points P0 et P1

en faisant varier le paramètre "t" entre 0 et 1, tu obtiens les coordonnées des points intermédiaires.

[ToTo13]

Ok, merci, d'apres ce que je comprend il faut couper chaque segment en deux et recommancer jusqu'au lissage voulu, mais ça fait beaucoup de calculs pour un lissage correct, est-ce qu'il y aurait un algo simple (pour un non matheux) qui permettrait d'alléger les calculs ? Et si possible qui permette de partir d'un point pour aller jusqu'à l'autre plutot que de devoir tout calculer avant de pouvoir utiliser les points obtenus...

Bonjour,

l'algorithme en question est celui de De Casteljau. Il est itératif, géométrique et on pourrait presque dire "non mathématique"
En plus il est très rapide.

[supergrey]

La formule fonctionne impeccablement, merci à vous !

Salut, je reviens vers vous car (toujours pas très fort en math) je cherche à calculer la position de l'intersection entre de courbe utilisant cette merveilleuse formule. Avec des courbe utilisant x et y j'arrive à m'en sortir mais la je ne sais pas trop comment faire, j'ai bien essayé de m'occuper que de x et de cherche t mais c'est trop compliqué.

[TNT89]

Tu veux calculer l'intersection entre deux courbes paramétrées (de Spline)?
Ok la resolution directe est assez bourrine (cf à la fin...) pourquoi, au lieu de ça, ne pas interpréter tes courbes comme des suites de segments...

Tu prends un pas p, assez petit, par exemple p=0.005. Donc il faut 200 pas pour aller à 1 (200*0.005=1)
Avec P0, P1, P2 et P3, des points et M0, M1, M2 et M3, en fait, les vecteurs dirigeants les tangentes à ces points (la direction qu'a la courbe en ce point...).
Tu as les courbes Q1(t) entre P0 et P1 (Q1(0) = P0 et Q1(1) = P1) et Q2(t) entre P2 et P3 (Q2(0) = P2 et Q2(1) = P3) données par les expressions que tu as déjà utilisé.

Tu peux alors découper et représenter tes courbes comme des segments, et ceci de façon itérative :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   Pour i allant de 0 à (200-1)
          Segment( Q1( i*p ), Q1( (i+1)*p ) )
   FinPour

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
   Pour i allant de 0 à (200-1)
          Segment( Q2( i*p ), Q2( (i+1)*p ) )
   FinPour

Maintenant il suffit de voir si deux de ces segments appartenant à deux courbes différentes se coupent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
   Pour i allant de 0 à (200-1)
          Pour j allant de 0 à (200-1)
             Si Intersection( Segment( Q2( i*p ), Q2( (i+1)*p ) ) , Segment( Q2( j*p ), Q2( (j+1)*p ) )
             Alors
                   //faire ce que tu veux, par ex sauvegarder le point d'intersection etc...
           FinPour
   FinPour

Comment savoir si deux segments se croisent?
on prend 2 segments entre les points de coordonnées (x1,y1) et (x2,y2) et
entre les points (x3,y3) et (x4,y4).
et on résout le système... et au final il y a intersection si :
(x3*y1-x4*y1-x3*y2+x4*y2-x1*y3+x2*y3+x1*y4-x2 y4)
et (x3*y1-x4*y1-x3*y2+x4*y2-x1*y3+x2*y3+x1*y4-x2 y4)
sont NON NULS
et
p = -((-x3*y1+x4*y1+x1*y3-x4*y3-x1*y4+x3*y4)/(x3*y1-x4*y1-x3*y2+x4*y2-x1*y3+x2*y3+x1*y4-x2*y4))
q = -((x2*y1-x3*y1-x1*y2+x3*y2+x1*y3-x2*y3)/(x3*y1-x4*y1-x3*y2+x4*y2-x1*y3+x2*y3+x1*y4-x2*y4))
sont COMPRIS ENTRE 0 ET 1

Les formules sont peut-être un peu grosses mais bon ce ne sont que des additions et des multiplications...

On va noter pour t dans [0,1], P1(t) l'équation de ta première courbe et P2(t) l'équation de ta deuxième courbe. Tu as grosso-modo :
P1(t) = (2t^3-3t^2+1)*P0 + (t^3-2t^2+t)*M0 + (-2t^3+3t^2)*P1+(t^3-t^2)*M1
et de même,
P2(t) = (2t^3-3t^2+1)*P2 + (t^3-2t^2+t)*M2 + (-2t^3+3t^2)*P3+(t^3-t^2)*M3
Où P0, P1, P2 et P3 sont des points, M0, M1, M2 et M3 sont, en fait, les vecteurs dirigeants les tangentes à ces points (la direction qu'a la courbe en ce point...).
Il faut chercher tous les couples (t1, t2) dans [0,1]*[0,1] c'est à dire tous les couples de paramètres permettant d'avoir :
P1(t1) = P2(t2)
Car il se peut que les deux courbes ne se coupe pas en même temps. Un peu comme deux voitures, il possible de couper la trajectoire d'une autre voiture, il préférable de ne pas le faire au moment où cette voiture arrive où on se trouve sinon...

On va aussi décomposer les points et les vecteurs en leur coordonnées :
P0 = (P0,1 ; P0,2) M0 = (M0,1 ; M0,2)
P1 = (P1,1 ; P1,2) M1 = (M1,1 ; M1,2)
P2 = (P2,1 ; P2,2) M2 = (M2,1 ; M2,2)
P3 = (P3,1 ; P3,2) M3 = (M3,1 ; M3,2)

Du coup, on obtient deux égalités : une pour les abscisses (où toutes les coordonnées sont en X,1, X prend pour valeur 1, 2, 3, 4) et une selon les ordonnées (où toutes les coordonnées sont en X,2). Pour la première :

(2*t1^3-3*t1^2+1)*P0,1 + (t1^3-2*t1^2+t)*M0,1 + (-2*t1^3+3*t1^2)*P1,1+(t1^3-t1^2)*M1,1
=
(2*t2^3-3*t2^2+1)*P2,1 + (t2^3-2*t2^2+t)*M2,1 + (-2*t2^3+3*t2^2)*P3,1 + (t2^3-t2^2)*M3,1

(pour la seconde il suffit de remplacer les ",1" par ",2"...)

Maintenant, on fixe t1 dans [0,1], c'est à dire que t1 a une valeur particulière entre 0 et 1 mais on ne préoccupe pas de cette valeur. Et donc on peut noter une constante K(t1) telle que :
K(t1) = (2*t1^3-3*t1^2+1)*P0,1 + (t1^3-2*t1^2+t)*M0,1 + (-2*t1^3+3*t1^2)*P1,1 + (t1^3-t1^2)*M1,1
et donc :
K(t1) = (2*t2^3-3*t2^2+1)*P2,1 + (t2^3-2*t2^2+t)*M2,1 + (-2*t2^3+3*t2^2)*P3,1 + (t2^3-t2^2)*M3,1

(On écrit K(t1) et pas K car cette constante dépend du t1 choisit!)
On change un peut l'écriture de l'égalité précédente :
K(t1) = 2*P2,1*t2^3 - 3*P2,1*t2^2 + P2,1 + M2,1*t2^3 - 2*M2,1*t2^2 + t - 2*P3,1*t2^3 + 3*P3,1*t2^2 + M3,1*t2^3 - M3,1*t2^2
(c'est plus très lisible mais développé...)
On factorise selon les termes en t2, t2^2 et t2^3
K(t1) = (2*P2,1 + M2,1 - 2*P3,1 + M3,1)*t2^3 +( -3*P2,1 - 2*M2,1 + 3*P3,1 - M3,1)*t2^2 + t + P2,1

C'est un polynôme en t2 de la forme
a*t2^3 + b*t2^2 + t + c
avec :
a = (2*P2,1 + M2,1 - 2*P3,1 + M3,1)
b = ( -3*P2,1 - 2*M2,1 + 3*P3,1 - M3,1)
c = P2,1

On a l'égalité : K(t1) = a*t2^3 + b*t2^2 + t + c
Ou encore : 0 = a*t2^3 + b*t2^2 + t + c - K(t1)
0 = a*t2^3 + b*t2^2 + t + c'
avec c' = c - K(t1)

[...]

[supergrey]

Merci pour le temps passé à cette réponse...
Je crois que j'arrive à comprendre, mais je bloque (peut etre la fatigue) car j'ai donc un polynome qui est résolu mais qui me donne un konstante variable. Il faut que je fasse la meme chose pour la seconde equation, j'aurai donc un autre polynome et il restera à resoudre l'egalité entre les 2 c'est ça ou je m'égare ?

[TNT89]

Oui c'est ça , mais c'est pour une résolution exacte, lourde (impossible? ?)
la première partie (avec les segments) est beaucoup plus performantes et facile à mettre en place.

(sinon il faudrait peut être utiliser les relations coefficients-racines et vérifier qu'une racine est dans [0,1])

[supergrey]

Bonjour, je rallume le flambeau car j'aurais besoin de savoir s'il existe un formule pour avoir la longueur approximative de la courbe (pas du vol d'oiseau biensur).
Merci

[pseudocode]

Bah, je dirai qu'il faut d'intégrer selon l'abscisse curviligne : http://en.wikipedia.org/wiki/Arc_length#Modern_methods

Je ne suis pas bien sur qu'on puisse trouver une primitive, donc il faudra peut-être passer par une méthode d'intégration numérique.

[TNT89]

Tu peux toujours revenir au fondamentaux en calculant la longueur des segments consécutifs, en découpant la courbe en segments. C'est à la fois une technique de calcul numérique mais aussi la base du calcul de la longueur d'une courbe par l'abscisse curviligne (qui est la limite de la somme des longueurs des lignes polygonales qui forment la courbe : en gros plus tu prends des petits segments plus tu es proche de la courbe, plus il faut de segment pour aller d'un point à t=0 jusqu'à un point à t=1, mais plus tu te rapproches de la "vraie" longueur de la courbe).

[supergrey]

En fait je pensais plus a un formule basé sur le fait que plus les points, sont éloignés ET plus les directions de début et de fin sont différentes, plus la longueur et grande. Donc peut etre une formule qui utilise la différence entre les angle de départ et de fin en utilisant des sinus surement, mais c'est un peu dur à mettre en place sans etre matheux.

[Drannor]

Bonjour,

Je m'excuse de remonter ce post mais j'aimerais un renseignement.
J'ai besoin d'utiliser l'équation paramétrique pour permettre a des particules dans un jeu de rejoindre le score peu importe leur position dans l'écran et ce via une jolie courbe.

Fort heureux de ce post, je bute néanmoins sur une chose surement bête mais étant mauvais en math, est ce que quelqu'un pourrait m'expliquer comment on calcul les tangentes aux points P0 et P1 afin d'obtenir M0 et M1 ?

Merci beaucoup.

[supergrey]

Etant l'initiateur de ce post je me permet une tentative de réponse histoire d'avoir travaillé aussi:
En fait tu mets ces points ou tu veux, c'est eux qui feront que tes particules iront tout droit au score ou plutot en zigzag. Tu peux calculer l'angle du score par rapport a ta particule et ajouter 90 degrés pour M0 en le placant à une certaine distance d de P0 et enlever 90 degrés pour M1 en le placant à d de P1 et tu varies le zigzag en modifiant d.
Enfin c'est une méthode apres ca dépend de l'effet désiré...

[Drannor]

Tout d'abord merci pour ta réponse.

Alors si je comprends bien :

Si ma particule P0 est en X0 = 50 et Y0 = 50 et que mon score P1 est en X1=700 et Y1 =450.

Avec un d = 50
Avec dans ce cas un angle d'environ -Pi/4 entre P0 et P1.

Je calcul M0 en faisant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
pMX0 = (pX0 + cos(-Pi/4 + 2Pi/4) * d); où 2Pi/4 est un angle d'effet
pMY0 = (pY0 + sin( Pi/4 + 2Pi/4) * d); non pas -pi:4 car l'origine de l'écran est inversé

et M1 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
pMX1 = (pX1 + cos(Pi/4 + 2Pi/4) * d); où 2Pi/4 est un angle d'effet
pMY1 = (pY1 + sin(-Pi/4 + 2Pi/4) * d);

?

Et est ce que d doit être identique pour M0 et M1 ?

edit : après essais, cela fonctione mais j'ai toujours un doute sur ma façon de calculer les pM car pour avoir un semblant d'effet mon d doit être assez élevé (supérieur a 500 :s )

Merci beaucoup.

[Saita]

Je fais aussi remonter ce post pour poser une petite question...
Supergrey, Comment tu as fais finalement pour calculer la longueur de ta courbe ?
Merci

[supergrey]

J'ai pu me débrouiller avec une grosse approximation, j'ai fais la somme des distances entre p0 et m0, m0 et m1, et enfin m1 et p1 et je multiplie par 0.8 mais c'est sur qu'il doit y avoir mieux.