Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Algorithme (Nurbs)

6 réponses
Avatar
ibiiztera
Salut,

Je ne m'en sors pas avec l'implantation des Nurbs dans mon logiciel malgr=
=E9 l'aide de nombreux livres et documents.

https://github.com/mdahmen/emptycanvas

/**
* *
**
*/
package info.emptycanvas.library.nurbs;
import info.emptycanvas.library.object.Point3D;
/**
*
* @author
*/
public class NurbsSurface extends ParametrizedSurface {
/**
* *
*
* degree:
*
* Degr=E9 de la fonction de base
*
* params[]:
*
* Tableau de noeuds weights[]: * Tableau de pond=E9rations pour des courbes
* NURBS rationnelles ; sinon NULL ou 1.0 pour une b-spline polynomiale.
* c_pnts[][3]:
*
* Tableau de points de contr=F4le D=E9finition : k =3D degree of basis func=
tion N
* =3D number of knots, degree -2 wi =3D weights Ci =3D control points (x, y=
, z) *
* wi Bi,k =3D basis functions Par cette =E9quation, le nombre de points de
* contr=F4le est =E9gal =E0 N+1.
*/
private int degreeU;
private int degreeV;
@Override
public Point3D coordPoint3D(int x, int y) {
return calculerNurbs(1.0 * x / getMaxX(), 1.0 * y / getMaxY());
}
@Override
public Point3D calculerPoint3D(double u, double v) {
return calculerNurbs(u, v);
}
/**
* *
* "Knots"
*/
class Intervalle {
private final double[][] Data;
private final int m, n;
private Intervalle(double[][] T) {
this.Data =3D T;
m =3D T.length;
n =3D T[0].length;
}
public double get(int i, int j) {
try {
return this.Data[i][j];
} catch (java.lang.ArrayIndexOutOfBoundsException ex) {
return 0;
}
}
public void set(int i, int j, double v) {
this.Data[i][j] =3D v;
}
}
/**
* *
* Point3D Weight associated
*/
class Point3DPoids {
private final Point3D[][] points;
private final double[][] poids;
final int m, n;
public Point3DPoids(Point3D [][] poins, double [][] poids) {
this.points =3D poins;
this.poids =3D poids;
m =3D points.length;
n =3D points[0].length;
}
private double getPoids(int i, int j) {
return poids[i][j];
}
public Point3D getPoint3D(int i, int j) {
return points[i][j];
}
public void set(int i, int j, Point3D p, double w) {
if (i >=3D 0 && i < m && j >=3D 0 && j < n) {
points[i][j] =3D p;
poids[i][j] =3D w;
}
}
}
public NurbsSurface() {
}
@Override
public Point3D calculerVitesse3D(double u, double v) {
throw new UnsupportedOperationException("Not supported yet."); //To change =
body of generated methods, choose Tools | Templates.
}
public void creerNurbs() {
if (points !=3D null && T !=3D null && poids !=3D null) {
intervalle =3D new Intervalle(T);
forme =3D new Point3DPoids(points, poids);
for (int i =3D 0; i < forme.m; i++) {
for (int j =3D 0; j < forme.n; j++) {
forme.set(i, j, points[i][j], poids[i][j]);
}
}
}
}
public double f0sur0egal0(double t1, double t2) {
if (t2 =3D=3D 0 && t1 =3D=3D 0) {
return 0;
} else {
return t1 / t2;
}
}
public int coefficients(int type_coord, double t) {
if(t<=3Dintervalle.get(type_coord, 0))
return 0;
for (int i =3D 0; i < intervalle.m; i++) {
if ((t >=3D intervalle.get(type_coord, i)) && (t <intervalle.get(type_coord=
, i + 1) )) {
return i;
}
}
return 1;
}
public void setMaillage(Point3D[][] points, double[][] poids) {
this.points =3D points;
this.poids =3D poids;
}
public void setReseauFonction(double[][] T) {
this.T =3D T;
}
public double N(int type_coord, int i, int deg, double t) {
if (i >=3D intervalle.m || i<0) {
return 0;
}
if (deg <=3D0) {
if(coefficients(type_coord, t)=3D=3Di)
{
return 1;
}
else
return 0;
}
return N(type_coord, i, deg - 1, t)
* f0sur0egal0(t-intervalle.get(type_coord, i) , intervalle.get(type_coord, =
i+deg-1) - intervalle.get(type_coord, i))
+ N(type_coord, i + 1, deg - 1, t)
* f0sur0egal0(intervalle.get(type_coord, i + deg) - t, intervalle.get(type_=
coord, i+deg) - intervalle.get(type_coord, i + 1));
}
public long C(int i, int n) {
return factorielle(n) / factorielle(i) / factorielle(n - i);
}
protected long factorielle(int n) {
long sum =3D 1;
for (int i =3D 1; i <=3D n; i++) {
sum *=3D i;
}
return sum;
}
public void setDegreU(int deg) {
this.degreeU =3D deg;
}
public void setDegreV(int deg) {
this.degreeV =3D deg;
}
public Point3D calculerNurbs(double u, double v) {
double sum =3D 0;
Point3D ret =3D Point3D.O0;
for (int i =3D 0; i < forme.m; i++) {
for (int j =3D 0; j < forme.n; j++) {
double sumP =3D (double) (C(i, forme.m) * C(j, forme.n)) * N(type_coordU, i=
, degreeU, u) * N(type_coordV, j, degreeV, v);
ret =3D ret.plus(forme.getPoint3D(j,i).mult(sumP));
sum +=3D sumP;
}
}
return ret.mult(1 / sum);
}
@Override
public String toString() {
String s =3D "nurbs ( \n";
for (int i =3D 0; i < intervalle.m; i++) {
for (int j =3D 0; j < intervalle.n; j++) {
s +=3D "knot (" + i + "," + j + ")=3D" + intervalle.get(i, j) + "\n\t";
}
}
for (int i =3D 0; i < forme.m; i++) {
for (int j =3D 0; j < forme.n; j++) {
s +=3D "point (" + i + "," + j + ")=3D" + forme.getPoint3D(i, j) + " Poids =
: (" + i + "," + j + ")" + forme.getPoids(i, j) + "\n\t";
}
}
return s + "\n\n)";
}
public static final int type_coordU =3D 0;
public static final int type_coordV =3D 1;
private Point3D[][] points;
private double[][] poids;
private double[][] T;
private Intervalle intervalle;
private Point3DPoids forme;
}

6 réponses

Avatar
Yliur
Le Thu, 8 Jan 2015 03:38:51 -0800 (PST)
ibiiztera a écrit :

Je ne m'en sors pas avec l'implantation des Nurbs dans mon logiciel
malgré l'aide de nombreux livres et documents.

https://github.com/mdahmen/emptycanvas

[...]



Si tu as de la chance quelqu'un passera ici et connaîtra ce problème,
mais ce n'est pas sûr.

Si tu as des difficultés à comprendre l'algorithme, tu auras peut-être
plus de chance sur un groupe qui parle de mathématiques, non ?

Si tu comprends bien l'algorithme, en as-tu une représentation formelle
simplifiée ? Sans toutes les équations, mais au moins les étapes du
calcul.

Et aussi un exemple de calcul, avec les résultats intermédiaires ? Soit
trouvé quelque part dans une explication, soit calculé à la main ou
avec un autre logiciel.
Avatar
ibiiztera
Le jeudi 8 janvier 2015 13:16:53 UTC+1, Yliur a écrit :
Le Thu, 8 Jan 2015 03:38:51 -0800 (PST)
ibiiztera a écrit :

> Je ne m'en sors pas avec l'implantation des Nurbs dans mon logiciel
> malgré l'aide de nombreux livres et documents.
>
> https://github.com/mdahmen/emptycanvas
>
> [...]

Si tu as de la chance quelqu'un passera ici et connaîtra ce problème,
mais ce n'est pas sûr.

Si tu as des difficultés à comprendre l'algorithme, tu auras peut-ê tre
plus de chance sur un groupe qui parle de mathématiques, non ?



Le groupe de math j'en viens ... Si personne n'a la réponse c'est bon je sors et vais m'acheter un bouquin à 200 EURO qui traite le sujet de mani ère approfondie. Ce dont je ne pense pas avoir besoin.

Si tu comprends bien l'algorithme, en as-tu une représentation formelle
simplifiée ? Sans toutes les équations, mais au moins les étapes du
calcul.


Les équations présentées ci-dessus Sont les étapes du calcul. Mais il semble y avoir une erreur ??? Où est l'erreur?


Et aussi un exemple de calcul, avec les résultats intermédiaires ? So it
trouvé quelque part dans une explication, soit calculé à la main ou
avec un autre logiciel.
Avatar
Samuel DEVULDER
Le 08/01/2015 13:19, Yliur a écrit :

Si tu as des difficultés à comprendre l'algorithme, tu auras peut-être
plus de chance sur un groupe qui parle de mathématiques, non ?



Il/elle en vient (fr.sci.maths)

Ici il y a confusion entre algorithme et implémentation (un algorithme
ne s'ecrit pas en java, mais en pseudo langage avec des mots et des
abstractions et pas des trucs bas niveaux comme hashmap ou tableaux
d'entiers). De ce que j'ai pu comprendre c'est l'implémentation qui soit
n'arrive pas à être faite, soit ne marche pas comme attendu.

Donner le code source ne sert pas à grand-chose. Il faut plus
d'explications sur le principe de l'algo, de la façon dont on a décidé
de l'implémenter, ainsi que le détail de ce qu'on obtient et pourquoi on
devrait obtenir autre chose.

Bref sans plus d'infos c'est mal barré pour avoir une réponse qui aidera
l'O.P. :-/

a+

sam.
Avatar
Yliur
Le Thu, 8 Jan 2015 05:03:50 -0800 (PST)
ibiiztera a écrit :

> Si tu comprends bien l'algorithme, en as-tu une représentation
> formelle simplifiée ? Sans toutes les équations, mais au moins les
> étapes du calcul.

Les équations présentées ci-dessus Sont les étapes du calcul. Mais il
semble y avoir une erreur ??? Où est l'erreur?



Là tu présentes un programme de 200 lignes censé réaliser un calcul
que la plupart des gens ne connaissent pas, ça fait pas mal de boulot
pour eux de se lancer dans l'étude de ce truc et de déterminer où ton
programme contient une erreur.

Je suppose que pour déterminer que ça ne marche pas tu as pris un
exemple de données et tu l'as passé dans ton programme. Donc tu pourrais
sans doute réaliser le calcul à la main étape par étape et tracer ton
programme pour déterminer quelle partie ne fonctionne pas, ça aiderait
déjà à cibler un peu.

Sais-tu faire le calcul à la main ?
Avatar
ibiiztera
Le jeudi 8 janvier 2015 13:16:53 UTC+1, Yliur a écrit :
Le Thu, 8 Jan 2015 03:38:51 -0800 (PST)
ibiiztera a écrit :

> Je ne m'en sors pas avec l'implantation des Nurbs dans mon logiciel
> malgré l'aide de nombreux livres et documents.
>
> https://github.com/mdahmen/emptycanvas
>
> [...]

Si tu as de la chance quelqu'un passera ici et connaîtra ce problème,
mais ce n'est pas sûr.

Si tu as des difficultés à comprendre l'algorithme, tu auras peut-ê tre
plus de chance sur un groupe qui parle de mathématiques, non ?

Si tu comprends bien l'algorithme, en as-tu une représentation formelle
simplifiée ? Sans toutes les équations, mais au moins les étapes du
calcul.

Et aussi un exemple de calcul, avec les résultats intermédiaires ? So it
trouvé quelque part dans une explication, soit calculé à la main ou
avec un autre logiciel.


Voilà ce que j'ai trouvé des sources que j'ai changé en Java (déj à c'était pas évident). Puis j'ai essayé de les intégrer à mon programme emptycanvas
https://gist.github.com/mdahmen/6e64b4c880a6576874e3
Avatar
Samuel DEVULDER
Pour tout ceux qui ne savent pas ce que sont les NURBS, je pense après
avoir survolé

https://www.cs.duke.edu/courses/fall05/cps124/notes/10_curves/opengl_nurbs.pdf

que ce sont juste une généralisation des courbes et surfaces de Bézier
servant dans la génération de surfaces 3D. Il me semble que cette video
sur Pixar (en anglais) parle probablement des NURBs sans mentionner le
terme:

https://www.youtube.com/watch?v=mX0NB9IyYpU

En particulier, on voit la construction récursive de ces objets. C'est
assez instructif.

Le 12/01/2015 19:02, ibiiztera a écrit :

Voilà ce que j'ai trouvé des sources que j'ai changé en Java (déjà c'était pas évident). Puis j'ai essayé de les intégrer à mon programme emptycanvas
https://gist.github.com/mdahmen/6e64b4c880a6576874e3



Oulala c'est quoi cette classe java "Nurbs" avec des méthodes statiques
monstrueusement longues ? Où sont les interfaces, les héritages, le
dispatching? (ok il y en a un peu dans le reste du code). Remarque: le
programme utilise des tableaux mais passe leur taille en paramètres aux
fonctions. Ca n'est pas nécessaire: en java le tableau est un objet qui
connait sa taille (attribut "length").

Misère. Ca ressemble méchamment à du Fortran, du C ou du basic et pas de
la programmation moderne ce code :-/ On ne peut peut-être pas faire
autrement avec ces algo numériques, mais franchement c'est pas du code
très joli. Pour info, j'ai trouvé une API toute faite pour manipuler ces
objets:

http://www.ocnus.com/NURBS/

As tu regardé comment ils font ? (ils utilisent des classes VRML qui
simplifient peut-être le codage en permettant d'écrire et calculer les
barycentres de points etc)

Autres truc que je trouve curieux, l'écriture de la méthode retournant
le coefficient binomial C(n,p) en passant par les factorielles. Avec des
long on peut compter jusqu'à 2^63-1. C'est à dire qu'on ne peut pas
calculer factorielle(21) = 5.1E19 > 2^63-1.

Donc n et p sont condamnés à ne pas dépasser 20. C'est pas beaucoup.
Pour bien faire il faudrait utiliser la classe BigInteger pour avoir un
calcul correct avec n et p>20. Et pour aller plus vite, au lieu de
diviser par les factorielles, il serait bien plus efficace d'utiliser la
formule C(n,p) = (n-p+1)*(n-p+2)*...*n

BigInteger res = BigInteger.ONE;
for(int i=n-p+1; i<=n; ++i) res = res.multiply(BigInteger.valueOf(i));
return res;

Je mentionne cette optimisation, mais il semble que la méthode C(n,p)
bien que présente dans le code ne soit pas utilisée :-/. Je suppose
qu'elle devait servir à calculer les poids optimaux pour avoir une belle
courbe de Bézier.

a+

sam.