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

C Discussion :

Génération de terrain par l'algorithme de Perlin [Tutoriel]


Sujet :

C

  1. #1
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 369
    Points : 40 164
    Points
    40 164
    Par défaut Génération de terrain par l'algorithme de Perlin


    http://khayyam.developpez.com/articles/algo/perlin/

    Cet article montre le fonctionnement de l'algorithme de Perlin pour générer des terrains aléatoires. Les exemples seront écrits en C. Prérequis : manipulation du C.
    Vous pouvez laisser un message à la suite.


  2. #2
    Nouveau membre du Club Avatar de TheZopo
    Homme Profil pro
    Étudiant
    Inscrit en
    Août 2012
    Messages
    29
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 25
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2012
    Messages : 29
    Points : 34
    Points
    34
    Par défaut
    Bonjour,
    Tout d'abord, merci pour ce tutoriel !

    Est-ce qu'une âme charitable aurait la bontée de transposer le code source en Algo (ou en Java) ? Malgré tout mes effort pour essayer de comprendre ton code source (pour le reproduire) je n'y arrive pas.
    Parce-que entre les déclarations de pointeurs de partout, les struct je suis complétement perdu xD.

    Bref merci d'avance !

  3. #3
    Membre à l'essai
    Homme Profil pro
    Développeur Web
    Inscrit en
    Novembre 2011
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Novembre 2011
    Messages : 10
    Points : 12
    Points
    12
    Par défaut Une petite question sur l'interpolation
    Ma question porte sur cette partie du code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    int interpolate(int y1, int y2, int n, int delta){
                if (n==0)
                  return y1;
                if (n==1)
                  return y2;
     
                float a = (float)delta/n;
     
                float v1 = 3*pow(1-a, 2) - 2*pow(1-a,3);
                float v2 = 3*pow(a, 2)   - 2*pow(a, 3);
     
                return y1*v1   y2*v2;
    }
    Si j'ai bien compris, on cherche a interpoler le point à la distance delta de y1 entre y1 et y2.
    Donc ce que je ne comprend pas c'est les 4 première ligne de la fonction.

    Si y1 et y2 sont 2 points différente, n n'est jamais égal à 0. On cherche ici à traiter le cas où delta == 0 et donc où la point dont on cherche l'interpolation est y1.
    De même n==1 peut être vrai sans pour autant que le point dont on cherche l'interpolation soit confondu avec y2, j'aurai donc plutôt mis delta == n comme condition.

    Pour résumé j'aurai remplacé les première lignes par :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
                if (delta==0)
                  return y1;
                if (delta==n)
                  return y2;
    Voila, c'est ce point la que je n'ai pas trop compris.
    Si je pouvais avoir une explication ça serait super.

    Merci d'avance

  4. #4
    Expert éminent sénior
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 352
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 352
    Points : 20 359
    Points
    20 359
    Par défaut
    super ! Merci pour le tuto

  5. #5
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    Par défaut
    Citation Envoyé par Coubas Voir le message
    Ma question porte sur cette partie du code :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    int interpolate(int y1, int y2, int n, int delta){
                if (n==0)
                  return y1;
                if (n==1)
                  return y2;
     
                float a = (float)delta/n;
     
                float v1 = 3*pow(1-a, 2) - 2*pow(1-a,3);
                float v2 = 3*pow(a, 2)   - 2*pow(a, 3);
     
                return y1*v1   y2*v2;
    }
    <snip>
    Moi, c'est la dernière ligne que je ne comprends pas. Ça compile, ça?

    Edit: En fait, il y a des opérateurs manquants en de nombreux endroits (je suppose qu'il manque des '+') et pas mal de warnings de conversion de float en int sans cast.

    Edit2: Sur la qualité du tuto lui-même, ma note serait négativement affectée par les bouts de code orphelins qui sont postés alors qu'ils dépendent de variables et fonctions déclarées plus tard dans le tuto. Au niveau du style, les boucles for imbriquées sans accolades (surtout qu'en style K&R, les accolades ne bouffent pas beaucoup de place) sont assez dérangeantes également...
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  6. #6
    Expert éminent sénior
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 369
    Points : 41 518
    Points
    41 518
    Par défaut
    Citation Envoyé par TheZopo Voir le message
    Bonjour,
    Tout d'abord, merci pour ce tutoriel !

    Est-ce qu'une âme charitable aurait la bontée de transposer le code source en Algo (ou en Java) ? Malgré tout mes effort pour essayer de comprendre ton code source (pour le reproduire) je n'y arrive pas.
    Parce-que entre les déclarations de pointeurs de partout, les struct je suis complétement perdu xD.

    Bref merci d'avance !
    J'ai traduit le code dans un langage objet où le code actuel n'utilise aucun pointeur.
    Mais comme je suis un gros troll, c'est du C++/CLI... (qui en fait, ne devrait pas être si difficile que ça à traduire en C# ou en Java quand on connait les concepts de base, il n'y a rien de bien méchant ici: Pas de types primitifs passés par référence (une horreur pour Java), etc.)

    Code C++/CLI : 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
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
     
    //
    //----------------------------------------------------------------------------
    //Calque, fonctions de calque.c
    ref class calque {
    public:
    	array<int, 2>^ v;
    	int taille;
    	float persistance;
     
    	System::Random^ rnd;
     
    public:
    	static calque^ init(int t, float p);
    	static void free(calque^ s);
     
    	void generer(int frequence, int octaves, float persistance, int liss);
    private:
    	static int interpolate(int y1, int y2, int n, int delta);
     
    	System::Byte aleatoire(float a);
    	//void enregistrer_bmp(String^ filename);
    	int valeur_interpolee(int i, int j, int frequence);
    };
     
    //
    //----------------------------------------------------------------------------
    //Fonctions de main.c
    ref class Perlin abstract sealed {
    	public:
    		static void enregistrer_bmp(calque^ c, System::String^ filename);
    		static int Main(array<System::String^>^ args);
    };
     
     
    //
    //----------------------------------------------------------------------------
    //Fonctions de calque.c
     
    //#include "Perlin_calque.h"
    //#include "Perlin_main.h"
    using namespace System;
     
    calque^ calque::init(int t, float p) {
    	calque^ s = gcnew calque;
    	//Pour bien faire, je devrais mettre ça dans le constructeur de calque
    	s->v = gcnew array<int, 2>(t, t);
    	s->taille = t;
    	s->persistance = p;
    	s->rnd = gcnew Random();
    	return s;
    }
    void calque::free(calque^ s) {
    	//Rien à faire ici, le garbage collector s'en occupe
    }
     
     
    Byte calque::aleatoire(float a)
    {
    	//Il y aurait probablement plus efficace avec un argument entier et Random::Next(), 
    	//mais vu que je ne sais pas encore comment cette fonction est appelée...
    	return (Byte)(rnd->NextDouble() * a);
    }
     
    //La fonction principale
    void calque::generer(int frequence, int octaves, float persistance, int liss) {
    	calque^ c = this;
    	int taille = c ->taille;
    	float pas = (float)taille / frequence;
     
    	//Calque aléatoire
    	calque^ random;
    	random = init(taille, 1);
     
    	for(int i=0; i<taille ; i++) {
    		for(int j=0; j<taille ; j++) {
    			random->v[i, j] = random->aleatoire(256); //Qu'est-ce que je disais...
    		}
    	}
     
    	Perlin::enregistrer_bmp(random, L"alea.bmp");
     
    	//Calques de travail
    	float persistance_courante = persistance;
    	array<calque^>^ mes_calques = gcnew array<calque^>(octaves);
    	for(int i=0 ; i<octaves ; i++) {
    		mes_calques[i] = calque::init(taille, persistance_courante);
    		persistance_courante *= persistance;
    	}
     
    	//Remplissage des calques
    	int f_courante = frequence;
    	for (int n=0; n<octaves; n++) {
    		for(int i=0; i<taille; i++) {
    			for(int j=0; j<taille; j++) {
    				int a = random->valeur_interpolee(i, j, f_courante);
    				mes_calques[n]->v[i, j] = a;
    			}
    		}
    		f_courante*=frequence;
    	}
     
    	//Ajout de tous les calques (en gros, c'est une moyenne pondérée)
    	/* calcul de la somme de toutes les persistances,
    	pour ramener les valeurs dans un intervalle acceptable */
    	float sum_persistances = 0;
    	for (int i=0; i<octaves; i++)
    		sum_persistances += mes_calques[i]->persistance;
     
    	/* ajout des calques successifs */
    	for (int i=0; i<taille; i++) {
    		for (int j=0; j<taille; j++) {
    			float sum = 0;
    			for (int n=0; n<octaves; n++) {
    				sum += mes_calques[n]->v[i, j] * mes_calques[n]->persistance;
    			}
     
    			/* normalisation */
    			c->v[i, j] = (int)(sum / sum_persistances);
    		}
    	}
     
    	/* lissage */
    	calque ^lissage;
    	lissage = calque::init(taille, 0);
     
    	for (int x=0; x<taille; x++) {
    		for (int y=0; y<taille; y++) {
    			int a=0;
    			int n=0;
    			for (int k=x-liss; k<=x+liss; k++) {
    				for (int l=y-liss; l<=y+liss; l++) {
    					if ((k >= 0) && (k<taille) && (l>=0) && (l<taille)) {
    						n++;
    						a += c->v[k, l];
    					}
    				}
    			}
    			lissage->v[x, y] = (int)( (float)a/n );
    		}
    	}
     
    	Perlin::enregistrer_bmp(lissage, L"lisse.bmp");
    }
     
    int calque::valeur_interpolee(int i, int j, int frequence)
    {
    	//déterminations des bornes
    	int borne1x, borne1y, borne2x, borne2y, q;
    	float pas;
    	pas = (float)this->taille/frequence;
     
    	q = (int)( (float)i/pas );
    	borne1x = (int)( q*pas );
    	borne2x = (int)( (q+1)*pas );
     
    	if(borne2x >= this->taille)
    		borne2x = this->taille-1;
     
    	q = (int)( (float)j/pas );
    	borne1y = (int)( q*pas );
    	borne2y = (int)( (q+1)*pas );
     
    	if(borne2y >= this->taille)
    		borne2y = this->taille-1;
     
    	/* récupérations des valeurs aléatoires aux bornes */
    	int b00,b01,b10,b11;
    	b00 = this->v[borne1x, borne1y];
    	b01 = this->v[borne1x, borne2y];
    	b10 = this->v[borne2x, borne1y];
    	b11 = this->v[borne2x, borne2y];
     
    	int v1  = interpolate(b00, b01, borne2y-borne1y, j-borne1y);
    	int v2  = interpolate(b10, b11, borne2y-borne1y, j-borne1y);
    	int fin = interpolate(v1, v2, borne2x-borne1x , i-borne1x);
     
    	return fin;
    }
     
    int calque::interpolate(int y1, int y2, int n, int delta) {
    	//Interpolation linéaire
    	/*
    	if (n!=0)
    		return y1 delta*(y2-y1)/n;
    	else
    		return y1;
    	*/
    	//Interpolation non linéaire
    	if (n==0)
    		return y1;
    	if (n==1)
    		return y2;
     
    	float a = (float)delta/n;
     
    	double v1 = 3*Math::Pow(1-a, 2) - 2*Math::Pow(1-a,3);
    	double v2 = 3*Math::Pow(a, 2)   - 2*Math::Pow(a, 3);
     
    	return (int)( y1*v1 + y2*v2 );
    }
     
    //
    //----------------------------------------------------------------------------
    //Fonctions de main.c
     
    #using <System.Drawing.dll>
    //#include "Perlin_main.h"
    //#include "Perlin_calque.h"
    using namespace System;
     
    void Perlin::enregistrer_bmp(calque^ c, String^ filename) {
    	System::Drawing::Bitmap^ s = gcnew System::Drawing::Bitmap(c->taille, c->taille, System::Drawing::Imaging::PixelFormat::Format24bppRgb);
     
    	//On boucle sur chaque pixel
    	for(int i=0; i<c->taille ; i++) {
    		for(int j=0; j<c->taille ; j++) {
    			System::Drawing::Color u = System::Drawing::Color::FromArgb(255, c->v[i, j], c->v[i, j], c->v[i, j]);
    			s->SetPixel(i, j, u);
    		}
    	}
    	s->Save(filename, System::Drawing::Imaging::ImageFormat::Bmp);
    	delete s; //This maps into s->Dispose();
    }
     
    int Perlin::Main(cli::array<System::String ^,1> ^args)
    {
    	// valeurs d'entree
    	int octaves = 3;
    	int frequence = 4;
    	float persistence = 0.5;
    	int taille_de_sortie = 200;
    	int lissage = 3;
     
    	calque^ s;
    	s = calque::init(taille_de_sortie, 1);
     
    	s->generer(frequence, octaves, persistence, lissage);
     
    	enregistrer_bmp(s, L"resultat.bmp");
    	return 0;
    }
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

Discussions similaires

  1. Génération de terrain
    Par vincechaff10 dans le forum OpenGL
    Réponses: 5
    Dernier message: 05/08/2006, 01h58
  2. complexité d'un algorithme par un...algorithme??
    Par afrikha dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 02/11/2005, 01h59
  3. Réponses: 6
    Dernier message: 19/10/2005, 13h10

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