IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Interpolation de couleurs/valeurs sur un polygone quelconque


Sujet :

Algorithmes et structures de données

  1. #21
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    essaye en prenant la norme du produit vectoriel

    n.x = a.y*b.z-a.z*b.y
    n.y = a.z*b.x-a.x*b.z
    n.z = a.x*b.y-a.y*b.x

    A = racine( n.x² + n.y² + n.z² )


    NB: je ne sais pas d'où sort le facteur "2" qu'ils ont collé dans la formule de la tangente a la page 8.

  2. #22
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    merci
    alors avec la norme du produit vectoriel, j'obtiens ça :



    je me suis fait aidé par un pote matheux, il m'a pondu ça :

    (a.x*b.y - b.x*a.y) + (a.y*b.z - a.z*b.y) + (a.x*b.z - a.z*b.x) + (a.y*b.z - a.z*b.y)

    et je retombe sur mon 1er résultat:


    voici la différence amplifiée :


    donc à l'intérieur c'est presque identique, mais à l'extérieur ça n'a rien à voir...

    reste à tester lequel convient le mieux dans mon cas...

    EDIT : et pour ce qui est de l'utilisation en outil de dessin, je me demande comment gérer plusieurs polygones à la fois

  3. #23
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Citation Envoyé par Earthwormjim Voir le message
    donc à l'intérieur c'est presque identique, mais à l'extérieur ça n'a rien à voir...

    reste à tester lequel convient le mieux dans mon cas...
    C'est surement la formule de ton copain qu'il faut utiliser.

    La mienne ne fonctionne que si le determinant est positif (la norme est toujours positive) et donc seulement a l'interieur de la surface, comme tu t'en est rendu compte.

  4. #24
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    C'est surement la formule de ton copain qu'il faut utiliser.

    La mienne ne fonctionne que si le determinant est positif (la norme est toujours positive) et donc seulement a l'interieur de la surface, comme tu t'en est rendu compte.
    ouep, quoiqu'il en soit merci beaucoup pour votre aide

    par contre, je suis toujours coincé avec la prise en compte de plusieurs polygones distincts (comme montré avec le A et le Z dans le pdf)... une idée ?

  5. #25
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Citation Envoyé par Earthwormjim Voir le message
    par contre, je suis toujours coincé avec la prise en compte de plusieurs polygones distincts (comme montré avec le A et le Z dans le pdf)... une idée ?
    Bon, j'ai lu le pdf en entier cette fois.

    Donc Ai représente l'aire du triangle, c'est donc bien "det(Vi,Vi+1)/2" = la moitié de l'aire du parallelogramme. A priori, ma formule devrait donc marcher.

    D'après le pdf (page 8), il n'y a rien de spécial a faire dans le cas de plusieurs polygones. Ils appliquent leur formule en prenant en compte tous les sommets de tous les polygones.

    Mais a mon avis leur formule ne marche que dans le cas 2D, car elle se sert de la formule de Coxeter (page 5) pour le calcul des coordonnées barycentriques

  6. #26
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    D'après le pdf (page 8), il n'y a rien de spécial a faire dans le cas de plusieurs polygones. Ils appliquent leur formule en prenant en compte tous les sommets de tous les polygones.
    mais le problème c'est que tous les sommets s'enchainent comme étant considérés comme un seul polygone, du coup comment faire une coupure pour passer d'un polygone à l'autre ? c'est ça que je capte pas :/

    par exemple comment faire pour qu'il n'y ait pas de edge de liaison entre le contour du A et le trou en son centre ?

  7. #27
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Citation Envoyé par Earthwormjim Voir le message
    mais le problème c'est que tous les sommets s'enchainent comme étant considérés comme un seul polygone, du coup comment faire une coupure pour passer d'un polygone à l'autre ?
    bah, il n'y a pas de "coupure" vu que le but c'est de faire de l'interpolation. non ?

  8. #28
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    bah, il n'y a pas de "coupure" vu que le but c'est de faire de l'interpolation. non ?
    en fait si, exemple, j'ai deux polygones rectangulaires

    dont les points sont ABCD et EFGH, les deux ayants les points tournant dans le sens des aiguilles d'une montre, la liste de points envoyés à la fonction est donc ABCDEFGH, ça donne ça :

    ABCD a les couleurs rouge, vert, bleu, cyan
    EFGH est blanc aux 4 coins

    Si je veux que ça fonctionne, je dois dupliquer le point A, copie que je nomme 'a', et inverser le sens des points du 2eme polygone, ce qui donne ceci :

    ici j'envoie donc la liste de points ABCDaEHGF

    ça marche mieux, mais comme les points ('a' et E) et (E et A) forment les segments 5 et 10, on voit un bord de trop, c'est de cette coupure dont je parle, comment faire pour ne pas avoir à créer les segments 5 et 10 pour que l'interpolation reste correcte.

    Donc là, pour que ça marche, il faut considérer l'ensemble des polygones comme un seul tracé continu, en doublant certains points pour permettre de créer des segments entre les polygones, et aussi inverser l'ordre des points dans le cas d'un polygone à l'intérieur d'un autre... c'est un poil compliqué si on veut une fonction "générique"

  9. #29
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    hum, il y a (heureusement) l'isolation de l'interpolation le long des segments dans le code, c'est le test :

    if A[i]=0 and D[i]<0 then

    si je fais

    if A[i]=0 and D[i]<0 and i<>5 and i<>10 then

    le bord superflu disparait (nb : dans le langage que j'utilise, les tableaux commencent à 1 et non à 0)

    de plus pour que l'interpolation soit bonne dans tous les cas, j'ai dû en fait tripler le point A en a', ce qui donne au final la liste de points :
    ABCDaEHGFa'



    donc il faudrait que j'envoie dans la fonction plusieurs tableaux de points, un pour chaque poly, et qu'ensuite j'ajoute les points supplémentaires, ça devrait pas être trop dur, sauf si les liaisons entre les polygones coupent leurs bords, là je pense que ça va bousiller l'interpolation (ça serait bien que non, mais j'en doute)
    et plus dur : inverser les points des polygones qui se trouvent inclus dans d'autres, là ça va être plus chaud, surtout si j'ai plusieurs polygones imbriqués les uns dans les autres... m'enfin ça doit pas être infaisable

  10. #30
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    Citation Envoyé par Earthwormjim Voir le message
    sauf si les liaisons entre les polygones coupent leurs bords, là je pense que ça va bousiller l'interpolation (ça serait bien que non, mais j'en doute)
    ah bah en fait si, ça marche :
    l'interpolation reste correct même si les segments 'virtuels' coupent les polygones, tant mieux, un soucis de moins

    il ne me reste plus qu'à trouver comment détecter efficacement si un polygone est inclut dans un autre, pour inverser l'ordre de ses points

    EDIT : et bien non, ça ne marche pas à tous les coups, fausse joie...
    si je fais mon test avec 3 polygones, ça repart en sucette grave

  11. #31
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Citation Envoyé par Earthwormjim Voir le message
    et bien non, ça ne marche pas à tous les coups, fausse joie...
    si je fais mon test avec 3 polygones, ça repart en sucette grave
    Tout cela est marqué dans le PDF, page 4, au début du chapitre 3:
    Let Ψ be an arbitrary polygon or a set of arbitrary polygons in the plane with n ≥ 3 distinct vertices, non-intersecting (open) edges, see Figure 1 for some examples.
    If Ψ is a set of (possibly nested) polygons, we require the orientations of the polygons to alternate as shown in Figure 14 (a) in Appendix B
    désolé.

  12. #32
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    en fait oui, pour l'inversion de rotation, ça c'est ok, je pense pouvoir m'en sortir

    ce qui délire, c'est l'enchainement des polygones, voici un lien vers une appli interactive en shockwave (donc faudra le plugin)
    http://earthwormjim.free.fr/stock/ba...rpolation.html

    ou bien une version exe si vous n'avez pas le courage d'installer le plug :
    http://earthwormjim.free.fr/stock/ba...erpolation.zip

    on peut déplacer chaque point à la souris, et activer ou non le rendu de chaque polygone avec les cases à cocher en bas.
    à chaque déplacement, le rendu de l'image est mis à jour avec un pas de 10x10 pixels
    les boutons render1 et render2 refont le rendu avec respectivement un pas de 1 et 2 pixels

    les polygones ABCD et IJKL tournent dans le sens des aiguilles d'une montre
    EFGH lui est inversé

    si on a que ABCD et EFGH ou ABCD et IJKL, tout va bien
    mais si on a les trois ensemble, rien ne va plus.

    j'ai essayé de retourner les polygones dans tous les sens, ça change rien, donc mon problème ici est plutot lié à la forme de mon tableau de points passé dans la fonction, ou un truc du genre

    pour le moment lorsque j'envoie les 3 polygones dans la fonction, je fusionne tout en une seule liste de points, en dupliquant à chaque fois le 1er point de chaque polygone à la fin de la liste de points de ce poly, ce qui donne au final ABCDaEFGHeIJKLi
    a, e et i étant des copies conformes de A,E et I aussi bien pour la position que pour la couleur utilisée

    donc j'ai mal compris un truc dans le pdf, là il semblerait qu'ils expliquent la partie inversion du sens des polygones, mais pas comment les différencier dans la liste de points... je nage...

  13. #33
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    Pour la postérité, l'algo du PDF "Barycentric Coordinates for Arbitrary Polygons in the Plane" implémenté en Java:

    La classe qui modélise une couleur RGB:
    Code java : 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
    public class RGB {
    	private double r=0,g=0,b=0;
     
    	public RGB() {}
     
    	public RGB(double r,double g,double b) {
    		this.r=r; this.g=g; this.b=b;
    	}
    	public RGB scale(double s) {
    		return new RGB(s*r,s*g,s*b);
    	}
    	public RGB add(RGB c) {
    		return new RGB(r+c.r,g+c.g,b+c.b);
    	}
    	public int asrgb32() {
    		int ir = (int) Math.max(0,Math.min(255,r));
    		int ig = (int) Math.max(0,Math.min(255,g));
    		int ib = (int) Math.max(0,Math.min(255,b));
    		return (0xFF<<24)+(ir<<16)+(ig<<8)+ib;
    	}
    }

    La classe qui modélise un point (2D) avec une couleur:
    Code java : 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
    public class MyPoint {
    	public int x=0, y=0;
    	public RGB f=null;
     
    	public MyPoint() {}
     
    	public MyPoint(int x,int y,RGB rgb) {
    		this.x=x; this.y=y; this.f=rgb;
    	}
     
    	// operations
    	public static void substract(MyPoint result, MyPoint a, MyPoint b) {
    		result.x=a.x-b.x;
    		result.y=a.y-b.y;
    	}
    	public static double norm(MyPoint a) {
    		return Math.sqrt(a.x*a.x+a.y*a.y);
    	}
    	public static double det(MyPoint a, MyPoint b) {
    		return a.x*b.y - a.y*b.x;
    	}
    	public static double dot(MyPoint a, MyPoint b) {
    		return a.x*b.x + a.y*b.y;
    	}
    }

    La classe qui réalise l'interpolation suivant l'algo de la page 9. Valable pour un seul polygone, en attendant mieux.
    Code java : 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
    public class Interpolater {
    	private MyPoint[] vi;
     
    	private int n;
    	private MyPoint[] s;
    	private double[] r,A,D;
     
    	public Interpolater(MyPoint... vi) {
    		this.vi=vi;
     
    		this.n = vi.length;
    		this.s = new MyPoint[n];
    		for(int i=0;i<n;i++)
    			this.s[i] = new MyPoint();
    		this.r = new double[n];
    		this.A = new double[n];
    		this.D = new double[n];
    	}
     
    	// traduction mot à mot de l'algorithme (figure 6, page 9)
    	public RGB F(MyPoint v) {
     
    		for(int i=0;i<n;i++)
    			MyPoint.substract(s[i],vi[i],v);
     
    		for(int i=0;i<n;i++) {
    			int inext=(i+1)%n;
     
    			r[i]=MyPoint.norm(s[i]);
    			A[i]=MyPoint.det(s[i],s[inext])/2;
    			D[i]=MyPoint.dot(s[i],s[inext]);
    			if (r[i]==0) 
    				return vi[i].f;
    			if (A[i]==0 && D[i]<0) {
    				r[inext]=MyPoint.norm(s[inext]);
    				return vi[i].f.scale(r[inext])
    					.add( vi[inext].f.scale(r[i]) )
    					.scale( 1.0/(r[i]+r[inext]) );
    			}
    		}
     
    		RGB f = new RGB();
    		double W=0;
    		for(int i=0;i<n;i++) {
    			int iprev=(n+i-1)%n;
    			int inext=(i+1)%n;
     
    			double w=0;
    			if (A[iprev]!=0) 
    				w = w + (r[iprev]-D[iprev]/r[i])/A[iprev];
    			if (A[i]!=0)     
    				w = w + (r[inext]-D[i]/r[i])/A[i];
    			f = f.add( vi[i].f.scale(w) );
    			W = W + w;
    		}
    		return f.scale(1.0/W);
    	}
    }

    et pour l'utiliser:
    Code java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     
    int w=512,h=512;
    BufferedImage img = new BufferedImage(w,h,BufferedImage.TYPE_INT_RGB);
     
    MyPoint[] vi = new MyPoint[] { /* déclarez ici les sommets du polygone */ };
     
    Interpolater interpolater = new Interpolater(vi);
     
    MyPoint v = new MyPoint();
    for(v.y=0;v.y<h;v.y++) {
    	for(v.x=0;v.x<w;v.x++) {
    		RGB f = interpolater.F(v);
    		img.setRGB(v.x, v.y, f.asrgb32());
    	}
    }

  14. #34
    Membre à l'essai
    Profil pro
    Inscrit en
    Août 2006
    Messages
    37
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Août 2006
    Messages : 37
    Points : 16
    Points
    16
    Par défaut
    Cool, merci pour ça ^^
    en attendant, moi je continue de chercher la solution pour plusieurs polygones

Discussions similaires

  1. [StringGrid] Aligner des valeurs sur le '.' ?
    Par MiJack dans le forum Langage
    Réponses: 3
    Dernier message: 06/02/2006, 17h55
  2. récupérer valeur sur 4 chiffres
    Par Gary dans le forum MS SQL Server
    Réponses: 2
    Dernier message: 01/02/2006, 12h10
  3. Réponses: 2
    Dernier message: 23/01/2006, 12h55
  4. Couleurs fantaisistes sur un graphe
    Par decour dans le forum Access
    Réponses: 2
    Dernier message: 14/10/2005, 12h51
  5. Savoir si un point est inclus dans un polygone quelconque
    Par SuperBIBI dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 02/08/2005, 20h02

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo