commit 0a7ea95bd8c25187b82517c8db5dedef6275f04b
parent 3e1ad07f6e5ce8423127f26052fef82b990daaa9
Author: Georges Dupéron <jahvascriptmaniac+github@free.fr>
Date: Sun, 2 Oct 2011 02:33:51 +0200
Utilisation d'une meilleure fonction de hachage.
Diffstat:
6 files changed, 38 insertions(+), 32 deletions(-)
diff --git a/bugs/closed/2011-10-02-0237-hash.txt b/bugs/closed/2011-10-02-0237-hash.txt
@@ -0,0 +1,4 @@
+TODO : trouver une fonction unsigned int hash(uint x, uint y) telle que
+hash(x,y) renvoie toujours la même chose pour les mêmes x et y, et sans
+artefact visuel.
+
diff --git a/bugs/new/2011-10-02-0237-interpolation.txt b/bugs/new/2011-10-02-0237-interpolation.txt
@@ -0,0 +1 @@
+TODO : faire une interpolation autre que linéaire.
diff --git a/bugs/new/2011-10-02-0237-shadeTriangles.txt b/bugs/new/2011-10-02-0237-shadeTriangles.txt
@@ -0,0 +1 @@
+TODO : Remplir et shade les triangles pour que ça soit plus lisible.
diff --git a/display.c b/display.c
@@ -102,10 +102,16 @@ int main() {
// Pour afficher le terrain :
/* int x; */
/* int y; */
- /* printf("P5 %d %d 255\n", 256, 256); */
- /* for (y = 0; y < 256; y++) { */
- /* for (x = 0; x < 256; x++) { */
- /* printf("%c", get_z(x, y));//interpolation(256+x, 256+y, 256, 256, 512, 512, 0, 255, 255, 255)); */
+ /* #define SIZE 256 */
+ /* printf("P5 %d %d 255\n", SIZE, SIZE); */
+ /* for (y = 0; y < SIZE; y++) { */
+ /* for (x = 0; x < SIZE; x++) { */
+ /* //int bit = y / (SIZE/32); */
+ /* //int h = hash2(t,hash2(x, y)); */
+ /* //if (y % (SIZE/32) == 0) h = 0; */
+ /* //printf("%c", ((h >> (31-bit)) & 1) * 255); */
+ /* //printf("%c", interpolation(256+x, 256+y, 256, 256, 512, 512, 0, 255, 255, 255)); */
+ /* printf("%c", get_z(x,y)); */
/* } */
/* } */
return 0;
diff --git a/roam.c b/roam.c
@@ -48,27 +48,21 @@ unsigned int getValueForSeed(unsigned int seed) {
return ((seed * primeA) ^ ((seed+1) * primeB)) + seed; // + seed pour éviter d'avoir uniquement des nombres impairs.
}
-// Donne des mauvais résultats (en faisant & 0xff…, on obtient des valeurs répétitives).
-/* unsigned int hash2(unsigned int a, unsigned int b) { */
-/* unsigned int primeA = 65521; // Plus grand premier < 2^16 */
-/* unsigned int primeB = 4294967291U; // Plus grand premier < 2^32 */
-/* return ((a * primeA) + (b * primeB) + a + 43) ^ ((a * primeB) + (b * primeA) + b + 57); */
-/* } */
-
-int hash2(int a, int b) {
+// Ce hash donne des bons résultats sur tous les bits de l'entier
+// généré (pas d'artefacts, répartition homogène des 0 et des 1).
+unsigned int hash2(unsigned int a, unsigned int b) {
+ unsigned int h = 1;
int i;
- for (i = 0; i < 5; i++) { // repeat five times
- b += a; // b = a + b
- a *= b; // a = a * (a + b)
- b ^= a; // b = (a + b) ^ (a * (a + b))
- a += 211; // a = (a * (a + b)) + 5
- b /= 2; // b = ((a + b) ^ (a * (a + b))) / 2
+ for (i = 0; i < 32; i+=8) {
+ a *= h;
+ b *= h;
+ h = h * 65599 + ((a >> i) & 0xff);
+ h = h * 65599 + ((b >> i) & 0xff);
}
- return (a >> 3); // high bits are never set…
+ return h;
}
-// Un hachage certes un peu primaire mais bon…
-unsigned int hash(unsigned int seed, int x, int y) {
+unsigned int hash3(unsigned int seed, int x, int y) {
return hash2(seed,hash2(x, y));
}
@@ -114,28 +108,27 @@ short** PerlinNoise(Triangle* t) {
// renvoie un z entre 0 et 255
int get_z(int x, int y) {
- unsigned int seed = 45;
x = x; /* Unused */
y = y; /* Unused */
int z = 0;
int level;
- int maxlevel = 7;
- for (level = maxlevel; level > 0; level--) {
+ int maxlevel = 6;
+ for (level = maxlevel; level >= 0; level--) {
int step = (1 << level);
int mask = step - 1;
- int zmax = mask;
+ int zmax = 2*step - 1;
int x1 = x & ~mask;
int y1 = y & ~mask;
int x2 = x1 + step;
int y2 = y1 + step;
- z += interpolation(x, y, x1, y1, x2, y2, hash(seed, x2, y1) & zmax, hash(seed, x2, y2) & zmax, hash(seed, x1, y2) & zmax, hash(seed, x1, y1) & zmax);
+ z += interpolation(x, y, x1, y1, x2, y2, hash3(level, x2, y1) & zmax, hash3(level, x2, y2) & zmax, hash3(level, x1, y2) & zmax, hash3(level, x1, y1) & zmax);
}
- // ici le résultat est entre 0 (inclues) et 2^(1+maxlevel) (non inclus)
- // On normalise sur [0,256[ sachant que 256 == 2^8
- if (maxlevel > 7)
- z = z >> (-7+maxlevel);
- else if (maxlevel != 7)
- z = z << (7-maxlevel);
+ // ici le résultat est entre 0 (inclus) et 2^(2+maxlevel) (non inclus)
+ // On normalise sur [0,256[ sachant que 256 == 2^8.
+ if (maxlevel > 6)
+ z = z >> (-6+maxlevel);
+ else if (maxlevel != 6)
+ z = z << (6-maxlevel);
return z;
}
diff --git a/roam.h b/roam.h
@@ -23,4 +23,5 @@ typedef struct Triangle {
Triangle* initDefaultExample();
int interpolation(int x, int y, int x1, int y1, int x2, int y2, int ne, int se, int so, int no);
+unsigned int hash2(unsigned int a, unsigned int b);
int get_z(int x, int y);
