Discussion :

[MrVylsain]

Bonjour à tous et merci de prendre le temps de m'aider.

Je développe un programme dans lequel je dois déformer un mesh plan en fonction d'une grille de points de contrôle. Je dois donc générer une surface à partir de ces points de contrôle.

Pour un premier test, j'ai utilisé les surfaces de bézier mais ça ne convient pas. En effet, cette méthode d'approximation est globale et déplacer un point de contrôle à une extrémité de la grille entraîne une déformation à l'autre bout de la grille.

Je dois donc trouver une méthode d'approximation locale qui soit la plus automatisée possible ( si on peut éviter la définition manuelle des tangentes...).
Seulement voilà, je n'arrive pas à déterminer une bonne fois pour toute quelle méthode utiliser. Surface bicubique, surface B-spline, etc... les méthodes ne manquent pas.
Les infos que je trouve sur ces différentes méthodes sont contradictoires.

Alors voilà, pour éviter de me lancer dans le dev d'un algo qui me demandera du temps et ne conviendra pas, je préfère vous demander conseil.

Avez-vous des suggestions ?

Merci d'avance.

[pseudocode]

Pour un premier test, j'ai utilisé les surfaces de bézier mais ça ne convient pas. En effet, cette méthode d'approximation est globale et déplacer un point de contrôle à une extrémité de la grille entraîne une déformation à l'autre bout de la grille.

Habituellement on découpe le plan en plusieurs patch 4x4, avec des contraintes sur les points de contrôle pour assurer la continuité entre les patchs. Ca limite les effets d'un point de contrôle à un petit voisinage.

[MrVylsain]

Merci pour votre réponse.

On utilise pas plutôt les surfaces B-Splines qui semblent avoir cette propriété d'approximation locale de manière naturelle ?

[pseudocode]

Merci pour votre réponse.

On utilise pas plutôt les surfaces B-Splines qui semblent avoir cette propriété d'approximation locale de manière naturelle ?

Oui, les NURBS/B-spline ont cette propriété par construction.

Je répondais juste à la problématique pour les surfaces de Bézier.

[MrVylsain]

Ah ok !
Alors effectivement, les B-Splines semblent appropriées avec cette possibilité de localiser l'influence des points de contrôle. Celà dit, je rencontre un problème dans leur mise en oeuvre...

J'ai noté qu'il y a plusieurs version de la formule récursive de De Boor.
En voici une première qui utilise tj et tj-1 : http://www.rqna.net/qna/nyhir-can-co...ple-knots.html
En voici une autre qui utilise les tj et tj+1 : http://en.wikipedia.org/wiki/B-spline
On retrouve les 2 versions assez régulièrement.

Normalement je dois utiliser la seconde car la 1e m'amène à accéder à un élément d'indice -1.
Seulement, ça ne marche pas, je me retrouve avec 2 problèmes :
- des zones de ma courbe où il n'y a aucun point et donc j'ai des portions de la courbe qui sont de simples segments
- une irrégularité de densité de points. Les points ont une densité faible au début de la courbe, se densifient à mi-courbe et s'étalent de nouveau à la fin de la courbe.

Ironiquement, c'est en me plantant dans cette formule et en faisant un mixe accidentel des 2 versions que j'obtiens le meilleur résultat.
En utilisant cette fonction :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
double basisBSpline(int index, int degre, double parameter)  
{
  double value;
 
  if (degre==1)			// base case for the recursion
  {
    if ((vKnots[index]<=parameter) && (parameter<vKnots[index+1]))
      value=1;
    else
      value=0;
  }
  else //mix des 2
  {
    if ((vKnots[index+degre-1]==vKnots[index]) && (vKnots[index+degre]==vKnots[index+1]))
      value = 0;
    else
    if (vKnots[index+degre-1]==vKnots[index])
      value = (vKnots[index+degre] - parameter) / (vKnots[index+degre] - vKnots[index+1]) * basisBSpline(index+1, degre-1, parameter);
    else
    if (vKnots[index+degre]==vKnots[index+1])
      value = (parameter - vKnots[index]) / (vKnots[index+degre-1] - vKnots[index]) * basisBSpline(index, degre-1, parameter);
    else
      value = (parameter - vKnots[index]) / (vKnots[index+degre-1] - vKnots[index]) * basisBSpline(index, degre-1, parameter) +
	      (vKnots[index+degre] - parameter) / (vKnots[index+degre] - vKnots[index+1]) * basisBSpline(index+1, degre-1, parameter);
  }
  return value;
}

Je n'ai alors plus qu'un seul des 2 problèmes : les trous ont disparu mais j'ai toujours une densité de points qui varie...

J'ai du mal à trouver la provenance de ces 2 problèmes et encore plus à savoir pourquoi une erreur dans mon algo résout l'un d'eux.

Voici le code complet et merci pour votre aide.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
struct Point {
  float x;
  float y;
};
 
vector<Point> vCtrlPts;
vector<Point> vCurvePts;
vector<int> vKnots;
int nbPtsCtrl = 9;
int n=nbPtsCtrl-1;          // number of control points = n+1
int degre=3;           // degree of polynomial = t-1
int nbCurvePts = 36;  
 
void computeKnots()  
{
  int j;
 
  for (j=0; j<n+degre+1; j++)
  {
    if (j<degre)
      vKnots[j]=0;
    else
    if ((degre<=j) && (j<=n))
      vKnots[j]=j-degre+1;
    else
    if (j>n)
      vKnots[j]=n-degre+2;
    //cout<<vKnots[j]<<endl;
  }
}
 
void iniVectors()
{
    Point p; p.x=0.0; p.y=0.0;
    vCtrlPts.resize(n+1,p);
    vCtrlPts[0].x=0.1;  vCtrlPts[0].y=0.5;
    vCtrlPts[1].x=0.2;  vCtrlPts[1].y=0.5;
    vCtrlPts[2].x=0.3;  vCtrlPts[2].y=0.5;
    vCtrlPts[3].x=0.4;  vCtrlPts[3].y=0.5;
    vCtrlPts[4].x=0.5;  vCtrlPts[4].y=0.5;
    vCtrlPts[5].x=0.6;  vCtrlPts[5].y=0.5; 
    vCtrlPts[6].x=0.7;  vCtrlPts[6].y=0.5; 
    vCtrlPts[7].x=0.8;  vCtrlPts[7].y=0.5;  
    vCtrlPts[8].x=0.9;  vCtrlPts[8].y=0.5;
 
    vKnots.resize(n+degre+1,0);
    computeKnots();
}
 
double basisBSpline(int index, int degre, double parameter)  
{
  double value;
 
  if (degre==1)			// base case for the recursion
  {
    if ((vKnots[index]<=parameter) && (parameter<vKnots[index+1]))
      value=1;
    else
      value=0;
  }
//  else //mix des 2
//  {
//    if ((vKnots[index+degre-1]==vKnots[index]) && (vKnots[index+degre]==vKnots[index+1]))
//      value = 0;
//    else
//    if (vKnots[index+degre-1]==vKnots[index])
//      value = (vKnots[index+degre] - parameter) / (vKnots[index+degre] - vKnots[index+1]) * basisBSpline(index+1, degre-1, parameter);
//    else
//    if (vKnots[index+degre]==vKnots[index+1])
//      value = (parameter - vKnots[index]) / (vKnots[index+degre-1] - vKnots[index]) * basisBSpline(index, degre-1, parameter);
//    else
//      value = (parameter - vKnots[index]) / (vKnots[index+degre-1] - vKnots[index]) * basisBSpline(index, degre-1, parameter) +
//	      (vKnots[index+degre] - parameter) / (vKnots[index+degre] - vKnots[index+1]) * basisBSpline(index+1, degre-1, parameter);
//  }
 
    else //FORMULE CORRECTE (enfin je crois...)
    {
      if ((vKnots[index+degre]==vKnots[index]) && (vKnots[index+degre+1]==vKnots[index+1]))
        value = 0;
      else
      if (vKnots[index+degre]==vKnots[index])
        value = (vKnots[index+degre+1] - parameter) / (vKnots[index+degre+1] - vKnots[index+1]) * basisBSpline(index+1, degre-1, parameter);
      else
      if (vKnots[index+degre+1]==vKnots[index+1])
        value = (parameter - vKnots[index]) / (vKnots[index+degre] - vKnots[index]) * basisBSpline(index, degre-1, parameter);
      else
        value = (parameter - vKnots[index]) / (vKnots[index+degre] - vKnots[index]) * basisBSpline(index, degre-1, parameter) +
               (vKnots[index+degre+1] - parameter) / (vKnots[index+degre+1] - vKnots[index+1]) * basisBSpline(index+1, degre-1, parameter);
    }
  return value;
}
 
Point computePoint(double parameter)
{
  double coeff;
  Point result;
  result.x=0;
  result.y=0;
 
  for (int i=0; i<n+1; i++)
  {
    coeff = basisBSpline(i,degre,parameter);
    result.x += (vCtrlPts[i]).x * coeff;
    result.y += (vCtrlPts[i]).y * coeff;
  }
  return result; 
}
 
void bspline()
{
  float increment,t=0;
 
  increment=(float)(n-degre+2)/(vCurvePts.size()-1);
 
  for (int i=0; i<vCurvePts.size(); i++)
  {    
    vCurvePts[i] = computePoint(t);
    t+=increment;
  }
}
 
void Reshape(int width, int height) 
{
    glViewport(0, 0, width, height);
}
 
void drawCurve()
{    
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0,1.0,0.0,1.0,0.1,1000);
    gluLookAt(0,0,1000,0,0,0,0,1,0);
 
    glClear(GL_COLOR_BUFFER_BIT |GL_DEPTH_BUFFER_BIT);
    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();
 
    glPointSize(2.0);
    glColor3f(1.0,1.0,1.0);
    glBegin(GL_POINTS);
    for(unsigned int i=0; i<nbCurvePts; i++)
    {
        glVertex2f(vCurvePts[i].x, vCurvePts[i].y);
        cout<<"["<<i<<";"<<i+1<<"] : "<<vCurvePts[i+1].x - vCurvePts[i].x<<endl;
    }
    glEnd();
    glLineWidth(0.1);
    glBegin(GL_LINE_STRIP);
    for(unsigned int i=0; i<nbCurvePts; i++)
    {
        glVertex2f(vCurvePts[i].x, vCurvePts[i].y);
    }
    glEnd();
 
    glPointSize(5.0);
    glColor3f(1.0,0.0,0.0);
    glBegin(GL_POINTS);
    for(int i=0; i<n+1; i++)
    {
        glVertex2f(vCtrlPts[i].x,vCtrlPts[i].y);
    }
    glEnd();
}
 
void Display(void) 
{       
    Point p; p.x=0.0; p.y=0.0;
    vCurvePts.resize(nbCurvePts,p);
 
    bspline();
 
    drawCurve();
 
    glutSwapBuffers();
 
    glutPostRedisplay();
}
 
void Keyboard(unsigned char key, int x, int y)
{
    switch(key){
        case 56:
            vCtrlPts[4].y+=0.01;
            break;
        case 50:
            vCtrlPts[4].y-=0.01;
            break;
        default:
            break;
    }
}
 
int main(int argc, char** argv)
{
    //window init
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH );
    glutInitDisplayMode(GLUT_MULTISAMPLE);
    glutInitWindowSize(1000,1000);
    glutCreateWindow(argv[0]); 
 
    iniVectors();
 
    glutReshapeFunc(Reshape);
    glutDisplayFunc(Display);
    glutKeyboardFunc(Keyboard);
 
    glutMainLoop();
 
    return 0;
}

[pseudocode]

J'ai noté qu'il y a plusieurs version de la formule récursive de De Boor.
En voici une première qui utilise tj et tj-1 : http://www.rqna.net/qna/nyhir-can-co...ple-knots.html
En voici une autre qui utilise les tj et tj+1 : http://en.wikipedia.org/wiki/B-spline
On retrouve les 2 versions assez régulièrement.

Pour moi, les 2 formulations sont identiques. Je n'ai pas du comprendre de quoi tu parlais.

Je me souviens d'avoir déjà discuté de B-Spline par récursion sur ce forum. Peut-être que cette discussion pourra t'aider.

[MrVylsain]

J'ai lu le topic que tu as mis en lien.
Il m'a permis de confirmer que certains de mes calculs sont bons mais ne parle pas du problème auquel je suis confronté.

Je me suis un peu mal exprimé. Je vais faire ça en image, ça sera plus clair.
Ces 2 versions de la formule de récurrence sont semblables, la seule différence est que :
- l'une calcule Ni,k en fonction de i et i+1
- l'autre calcule Ni,k en fonction de i et i-1

Quand j'utilise l'une de ces 2 expressions, le résultat est illustré avec ces 2 images.




Comme tu peux le voir, la répartition des points de la courbe est étrange et on retrouve les 2 problèmes que j'évoquais à savoir :

- des zones de ma courbe où il n'y a aucun point et donc j'ai des portions de la courbe qui sont de simples segments
- une irrégularité de densité de points. Les points ont une densité faible au début de la courbe, se densifient à mi-courbe et s'étalent de nouveau à la fin de la courbe.

Par contre, en me trompant en codant ces forumles, et donc en utilisant une forumule récursive qui n'est pas celle de Cox De Boor, j'obtiens un meilleur résultat.
Regardes bien les indices mis en gras, c'est un mix des 2 formules récursives plus haut :
il manque des -1 et il y a des +1 en trop

Code :

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

1
2
3
4
      value = (parameter - vKnots[index]) / (vKnots[index+degre-1] - vKnots[index]) * basisBSpline(index, degre-1, parameter) +
	      (vKnots[index+degre] - parameter) / (vKnots[index+degre] - vKnots[index+1]) * basisBSpline(index+1, degre-1, parameter);
  }

Avec cette erreur, j'obtiens ça :



Le problème des trous dans la courbe a disparu et ne reste plus que celui de la variation de densité des points entre le centre et les extrémités...

Appliqué aux surface ça se voit encore mieux.

Bonne formule :

Mauvaise formule:
http://hpics.li/ecdaab5

Voilà, j'espère que c'est plus clair. En tout cas je ne comprends pas d'où viennent ces 2 phénomènes.
Je veux utiliser les surfaces B-Splines pour un mesh texturé donc l'irrégularité des points est vraiment problématique.

Merci pour ton aide en tout cas, parce que je bloque vraiment là dessus.

[souviron34]

Je trouve bizarre que tes courbes ne passent pas par tes points dans le pic...

A moins qu'il y ait un truc particulier avec les NURBS, en général les splines sont justement faits pour passer par les points.. (interpooation dite "du dessinateur")

[pseudocode]

Je trouve bizarre que tes courbes ne passent pas par tes points dans le pic...

A moins qu'il y ait un truc particulier avec les NURBS, en général les splines sont justement faits pour passer par les points.. (interpooation dite "du dessinateur")

Les splines ne passent pas par les points de contrôle.

Si on veut qu'une spline passe par des points particuliers, on a deux choix:

• résoudre un système linéaire pour trouver où on doit placer les points de contrôles (spline interpolation)
• forcer la spline a passer par les points de contrôle en jouant sur leur multiplicité (=superposer des points de contrôle).

@MrVylsain: je vais tâcher de voir si j'obtiens la même chose que toi avec les bouts de code Java que j'ai posté.

[MrVylsain]

Merci à toi pseudocode.

Bon, j'ai trouvé la formule que j'utilise dans les pdf de plusieurs universitaires ainsi que sur plusieurs sites.
Je ne comprends pas comment 3 versions différentes de cette même formule peuvent exister...

Enfin bon cela veut dire qu'elle est valable et qu'il ne reste plus que le problème de la variation de densité des points à corriger.
J'espère que ce n'est pas le comportement classique de ce type de courbe car il me faut absolument des points équidistants.

[pseudocode]

Enfin bon cela veut dire qu'elle est valable et qu'il ne reste plus que le problème de la variation de densité des points à corriger.
J'espère que ce n'est pas le comportement classique de ce type de courbe car il me faut absolument des points équidistants.

Tes points devraient normalement être équidistants sur l'axe des X, puisque tu échantillonnes 't' de manière uniforme (incrément constant):

Code C :

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

1
2
3
4
5
for (int i=0; i<vCurvePts.size(); i++)
  {    
    vCurvePts[i] = computePoint(t);
    t+=increment;
  }

Le problème, c'est que tu n'utilises pas "t" comme abscisse pour "vCurvePts[].x". Tu interpoles l'abscisse des points de contrôles, ce qui doit être la cause de ta variation de densité sur les abscisses si tes points de contrôles ne sont pas espacés régulièrement.

Code C :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Point computePoint(double parameter)
{
  double coeff;
  Point result;
  result.x=0;
  result.y=0;

  for (int i=0; i<n+1; i++)
  {
    coeff = basisBSpline(i,degre,parameter);
    result.x += (vCtrlPts[i]).x * coeff;
    result.y += (vCtrlPts[i]).y * coeff;
  }
  return result; 
}

Note que même avec un densité uniforme sur les abscisses, la distance 2D entre les points ne sera pas constante. Mais ca, c'est normal étant donné que l'ordonnée des points varie suivant une courbe cubique.

Pour ma part, voila ce que j'obtiens avec tes valeurs (9 points de controles, 36 échantillons):

[MrVylsain]

Le problème, c'est que tu n'utilises pas "t" comme abscisse pour "vCurvePts[].x". Tu interpoles l'abscisse des points de contrôles, ce qui doit être la cause de ta variation de densité sur les abscisses si tes points de contrôles ne sont pas espacés régulièrement.

Précisément, mes points de contrôle sont espacés régulièrement.
En théorie, c'est bien l'abscisse de mes points de contrôle que je dois interpoler.
En gros la formule dit que pour un point de la courbe, je fais la somme de toutes les coordonnées de mes points de contrôle multipliées par un coefficient qui détermine le poids de ces points de contrôle. C'est bien ce que je fais avec result.x += (vCtrlPts[i]).x * coeff;

Le paramètre t est bien sensé échantilloner mon vecteur de noeuds, non ?
Or t n'est pas du tout lié aux coordonnées de mes points de contrôle.

Par exemple :
- j'ai un vecteur de noeud variant de 0 à 25.
- j'ai des points de contrôle dont l'abscisse varie de 0 à 1
Si j'utilise t comme paramètre en faisant
result.x += t*coeff;
je vais avoir une courbe dont l'abscisse va varier effectivement de façon régulière, mais de de 0 à 25 et non pas de 0 à 1.
Mes noeuds joueraient le rôle de points de contrôle en fait...

Dans le cas de ton appli java :
- est-ce que t parcours ton vecteur de noeuds ?
- est-ce que l'intervalle dans lequel se trouvent tes noeuds est le même que celui dans lequel se trouvent les abscisses de tes points de contrôle ?
- est ce que les multiplicités permettant de faire passer la courbe par les extrémités sont appliquées aux noeuds ou aux points de contrôle ? (dans mon cas c'est aux noeuds)

Bon, de toute façon le problème a bien un lien avec ça. J'échantillone de manière linéaire un vecteur de noeuds qui n'est pas linéaire (du genre [0,0,0,1,2,3,4,5,6,6,6] lorsque j'ai 8 points de contrôle).
Il y a quelque chose qui m'échappe dans cette histoire de noeuds !

[pseudocode]

Bon, de toute façon le problème a bien un lien avec ça. J'échantillone de manière linéaire un vecteur de noeuds qui n'est pas linéaire (du genre [0,0,0,1,2,3,4,5,6,6,6] lorsque j'ai 8 points de contrôle).
Il y a quelque chose qui m'échappe dans cette histoire de noeuds !

Les noeuds sont les endroits où l'on tronçonne la courbe. Dans chaque tronçon on aura une portion de spline = une somme de 4 cubiques pondérées par les valeurs des points de contrôle. Ces cubiques sont jointives entre les troncons, et forment ce qu'on appelles les fonctions de base. Une fonction de base est non-nulle sur 4 tronçons consécutifs.

(image)

Ces noeuds n'ont pas de rapport direct avec les points d'échantillonnage, c'est à dire les points où l'on souhaite connaitre la valeur de la courbe finale.

Dans le cas de ton appli java :
- est-ce que t parcours ton vecteur de noeuds ?

hum, pas vraiment. Il parcourt linéairement les valeur de l'intervalle (entre le premier noeud et le denier noeud).

- est-ce que l'intervalle dans lequel se trouvent tes noeuds est le même que celui dans lequel se trouvent les abscisses de tes points de contrôle ?

Heu... oui, en quelque sorte. Un point de contrôle est "sur" un noeud. (cf image).

- est ce que les multiplicités permettant de faire passer la courbe par les extrémités sont appliquées aux noeuds ou aux points de contrôle ? (dans mon cas c'est aux noeuds)

Les 2 méthodes permettent de faire passer la courbe finale par les points de contrôle. Mais avec la formule de l'algo récursif, c'est plus simple de mettre la multiplicité sur les points de contrôle.

P     = {  5, 5, 5, 0, 0, 0, 9, 9, 9, 0, 0, 0, 3, 3, 3 }
Knots = { -3,-2,-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15 }

-->Courbe évaluée entre t=0 et t=12:

Spline(0,00) = 0,167*P(00) + 0,667*P(01) + 0,167*P(02) +             +             +             +             +             +             +             +             +             +             +             +             = 5,000000
Spline(0,34) = 0,047*P(00) + 0,569*P(01) + 0,377*P(02) + 0,007*P(03) +             +             +             +             +             +             +             +             +             +             +             = 4,966414
Spline(0,69) = 0,005*P(00) + 0,358*P(01) + 0,583*P(02) + 0,054*P(03) +             +             +             +             +             +             +             +             +             +             +             = 4,731312
Spline(1,03) =             + 0,153*P(01) + 0,666*P(02) + 0,181*P(03) + 0,000*P(04) +             +             +             +             +             +             +             +             +             +             = 4,093236
Spline(1,37) =             + 0,041*P(01) + 0,554*P(02) + 0,396*P(03) + 0,009*P(04) +             +             +             +             +             +             +             +             +             +             = 2,978601
Spline(1,71) =             + 0,004*P(01) + 0,339*P(02) + 0,597*P(03) + 0,061*P(04) +             +             +             +             +             +             +             +             +             +             = 1,712828
Spline(2,06) =             +             + 0,140*P(02) + 0,663*P(03) + 0,197*P(04) + 0,000*P(05) +             +             +             +             +             +             +             +             +             = 0,698484
Spline(2,40) =             +             + 0,036*P(02) + 0,539*P(03) + 0,415*P(04) + 0,011*P(05) +             +             +             +             +             +             +             +             +             = 0,180000
Spline(2,74) =             +             + 0,003*P(02) + 0,320*P(03) + 0,609*P(04) + 0,068*P(05) +             +             +             +             +             +             +             +             +             = 0,014169
Spline(3,09) =             +             +             + 0,127*P(03) + 0,660*P(04) + 0,213*P(05) + 0,000*P(06) +             +             +             +             +             +             +             +             = 0,000945
Spline(3,43) =             +             +             + 0,031*P(03) + 0,522*P(04) + 0,433*P(05) + 0,013*P(06) +             +             +             +             +             +             +             +             = 0,118076
Spline(3,77) =             +             +             + 0,002*P(03) + 0,301*P(04) + 0,620*P(05) + 0,077*P(06) +             +             +             +             +             +             +             +             = 0,688618
Spline(4,11) =             +             +             +             + 0,116*P(04) + 0,654*P(05) + 0,230*P(06) + 0,000*P(07) +             +             +             +             +             +             +             = 2,068583
Spline(4,46) =             +             +             +             + 0,027*P(04) + 0,505*P(05) + 0,452*P(06) + 0,016*P(07) +             +             +             +             +             +             +             = 4,210950
Spline(4,80) =             +             +             +             + 0,001*P(04) + 0,283*P(05) + 0,631*P(06) + 0,085*P(07) +             +             +             +             +             +             +             = 6,444000
Spline(5,14) =             +             +             +             +             + 0,105*P(05) + 0,648*P(06) + 0,247*P(07) + 0,000*P(08) +             +             +             +             +             +             = 8,055394
Spline(5,49) =             +             +             +             +             + 0,023*P(05) + 0,488*P(06) + 0,470*P(07) + 0,019*P(08) +             +             +             +             +             +             = 8,795965
Spline(5,83) =             +             +             +             +             + 0,001*P(05) + 0,265*P(06) + 0,640*P(07) + 0,095*P(08) +             +             +             +             +             +             = 8,992443
Spline(6,17) =             +             +             +             +             +             + 0,095*P(06) + 0,640*P(07) + 0,265*P(08) + 0,001*P(09) +             +             +             +             +             = 8,992443
Spline(6,51) =             +             +             +             +             +             + 0,019*P(06) + 0,470*P(07) + 0,488*P(08) + 0,023*P(09) +             +             +             +             +             = 8,795965
Spline(6,86) =             +             +             +             +             +             + 0,000*P(06) + 0,247*P(07) + 0,648*P(08) + 0,105*P(09) +             +             +             +             +             = 8,055394
Spline(7,20) =             +             +             +             +             +             +             + 0,085*P(07) + 0,631*P(08) + 0,283*P(09) + 0,001*P(10) +             +             +             +             = 6,444000
Spline(7,54) =             +             +             +             +             +             +             + 0,016*P(07) + 0,452*P(08) + 0,505*P(09) + 0,027*P(10) +             +             +             +             = 4,210950
Spline(7,89) =             +             +             +             +             +             +             + 0,000*P(07) + 0,230*P(08) + 0,654*P(09) + 0,116*P(10) +             +             +             +             = 2,068583
Spline(8,23) =             +             +             +             +             +             +             +             + 0,077*P(08) + 0,620*P(09) + 0,301*P(10) + 0,002*P(11) +             +             +             = 0,688618
Spline(8,57) =             +             +             +             +             +             +             +             + 0,013*P(08) + 0,433*P(09) + 0,522*P(10) + 0,031*P(11) +             +             +             = 0,118076
Spline(8,91) =             +             +             +             +             +             +             +             + 0,000*P(08) + 0,213*P(09) + 0,660*P(10) + 0,127*P(11) +             +             +             = 0,000945
Spline(9,26) =             +             +             +             +             +             +             +             +             + 0,068*P(09) + 0,609*P(10) + 0,320*P(11) + 0,003*P(12) +             +             = 0,008501
Spline(9,60) =             +             +             +             +             +             +             +             +             + 0,011*P(09) + 0,415*P(10) + 0,539*P(11) + 0,036*P(12) +             +             = 0,108000
Spline(9,94) =             +             +             +             +             +             +             +             +             + 0,000*P(09) + 0,197*P(10) + 0,663*P(11) + 0,140*P(12) +             +             = 0,419090
Spline(10,29)=             +             +             +             +             +             +             +             +             +             + 0,061*P(10) + 0,597*P(11) + 0,339*P(12) + 0,004*P(13) +             = 1,027697
Spline(10,63)=             +             +             +             +             +             +             +             +             +             + 0,009*P(10) + 0,396*P(11) + 0,554*P(12) + 0,041*P(13) +             = 1,787160
Spline(10,97)=             +             +             +             +             +             +             +             +             +             + 0,000*P(10) + 0,181*P(11) + 0,666*P(12) + 0,153*P(13) +             = 2,455942
Spline(11,31)=             +             +             +             +             +             +             +             +             +             +             + 0,054*P(11) + 0,583*P(12) + 0,358*P(13) + 0,005*P(14) = 2,838787
Spline(11,66)=             +             +             +             +             +             +             +             +             +             +             + 0,007*P(11) + 0,377*P(12) + 0,569*P(13) + 0,047*P(14) = 2,979848
Spline(12,00)=             +             +             +             +             +             +             +             +             +             +             +             + 0,167*P(12) + 0,667*P(13) + 0,167*P(14) = 3,000000

[MrVylsain]

Merci pour ces explications.

Dans ton exemple, les points de contrôle sont simplement des valeurs de y à approximer.
Du coup, tu n'interpoles que les y et tu prends t comme abscisse c'est bien ça ?
Dailleurs, pourquoi t échantillonné entre 0 et 12 ?

Dans mon cas, je dois absolument interpoler les abscisses de mes points de contrôle.
Tu as essayé d'utiliser tes algos pour créer une courbe dont les points de contrôle sont dans un plan ? Si tu interpoles aussi tes abscisses, tu devrais retomber sur le même problème de non linéarité que moi, non ?

[pseudocode]

Dans ton exemple, les points de contrôle sont simplement des valeurs de y à approximer.
Du coup, tu n'interpoles que les y et tu prends t comme abscisse c'est bien ça ?

Oui, c'est ça.

Dailleurs, pourquoi t échantillonné entre 0 et 12 ?

Parce que, pour calculer la courbe finale, il faut être dans un intervalle où on à 4 fonctions de bases définies (= non-nulles). On ne peut donc pas calculer la courbe dans les intervalles [-3, 0[ et ]12,15]. (cf image précédente)

Dans mon cas, je dois absolument interpoler les abscisses de mes points de contrôle.
Tu as essayé d'utiliser tes algos pour créer une courbe dont les points de contrôle sont dans un plan ? Si tu interpoles aussi tes abscisses, tu devrais retomber sur le même problème de non linéarité que moi, non ?

Dans un plan ce qui change c'est que les points de contrôles ont 2 coordonnées: P.x et P.y

Spline(0,00).x = 0,???*P(00).x + 0,???*P(01).x + 0,???*P(02).x + ...
Spline(0,00).y = 0,???*P(00).y + 0,???*P(01).y + 0,???*P(02).y + ...

Spline(0,34).x = 0,???*P(00).x + 0,???*P(01).x + 0,???*P(02).x + ...
Spline(0,34).y = 0,???*P(00).y + 0,???*P(01).y + 0,???*P(02).y + ...

...

Une autre solution, plus simple, c'est d'utiliser des formules d'interpolation 1D. D'abord sur l'axe des X, puis sur l'axe des Y. C'est ce qu'on fait pour interpoler les images, mais ca impose d'avoir un maillage régulier au départ.




Est-ce que ce que tu appelles "non linéarité" c'est toujours la même problématique de "points équidistants" ?

[MrVylsain]

Est-ce que ce que tu appelles "non linéarité" c'est toujours la même problématique de "points équidistants" ?

Oui.

Dans un plan ce qui change c'est que les points de contrôles ont 2 coordonnées: P.x et P.y

Spline(0,00).x = 0,???*P(00).x + 0,???*P(01).x + 0,???*P(02).x + ...
Spline(0,00).y = 0,???*P(00).y + 0,???*P(01).y + 0,???*P(02).y + ...

Spline(0,34).x = 0,???*P(00).x + 0,???*P(01).x + 0,???*P(02).x + ...
Spline(0,34).y = 0,???*P(00).y + 0,???*P(01).y + 0,???*P(02).y + ...

...

Oui et de fait on retombe dans mon cas. Les x étant interpolés eux aussi, le problème de variation de densité des points apparait.
Je ne parviens pas à déterminer si c'est un comportement normal ou pas des B-Splines...

On sait que le problème vient du fait que t échantillonne un vecteur de noeuds dont les valeurs ne progressent pas de façon arithmétique mais pour corriger ça...

[pseudocode]

Oui et de fait on retombe dans mon cas. Les x étant interpolés eux aussi, le problème de variation de densité des points apparait.
Je ne parviens pas à déterminer si c'est un comportement normal ou pas des B-Splines...

C'est le comportement normal. Un échantillonnage de la spline avec un pas constant ne donne pas forcément des points équidistants. C'est même peu probable.

On sait que le problème vient du fait que t échantillonne un vecteur de noeuds dont les valeurs ne progressent pas de façon arithmétique mais pour corriger ça...

Un moyen c'est c'est de sur-échantillonner la spline, puis de sélectionner des échantillons qui sont à peu près régulièrement espacés.

Sinon, on peut aussi échantillonner une première fois avec un pas constant pour approximer la longueur totale de la spline. Puis re-échantillonner une seconde fois aux endroits (estimés) qui découpent la spline en morceaux de meme tailles.

[LinuxUser]

Le paramètre t est bien sensé échantilloner mon vecteur de noeuds, non ?
Or t n'est pas du tout lié aux coordonnées de mes points de contrôle.

Mes noeuds joueraient le rôle de points de contrôle en fait...

Non, mais noeuds et points de contrôle sont liés.
Si tu as

Code :

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

1
2
m = nombre de noeuds
k = l'ordre

Tu auras

Code :

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

n = m - k points de contrôle // et donc fonctions

Par contre je ne comprends pas cette histoire de densité de points.

Normalement tu as un polynôme de contrôle puis tu l'interpoles par une courbe.

[pseudocode]

Par contre je ne comprends pas cette histoire de densité de points.

Normalement tu as un polynôme de contrôle puis tu l'interpoles par une courbe.

Je dois dire que je ne comprend pas trop non plus la finalité d'avoir des points de la spline espacés régulièrement.

Si je reprend le Post Original:

Je développe un programme dans lequel je dois déformer un mesh plan en fonction d'une grille de points de contrôle. Je dois donc générer une surface à partir de ces points de contrôle.

je comprends qu'on veut obtenir quelque chose comme cela:



i.e. une interpolation bicubique d'une grille dont seuls les points de 'contrôle' et les points des bords sont connus. Par exemple en utilisant des courbes de Hermite, ou tout autre interpolateur.

Après, je ne vois pas trop comment ca va servir à "déformer un mesh plan". Parce que, pour moi, la surface obtenue (figure b) est déjà la déformation du plan.

[LinuxUser]

Oui je suis d'accord avec toi pseudocode, pour cela je propose d'implémenter les NURBS.
Pour cela je conseil un merveilleux livre: The NURBS Book de Lars Piegl
http://www.amazon.com/NURBS-Book-Mon.../dp/3540615458