src/noise.cpp

   1 /*
   2 Minetest-m13
   3 Copyright (C) 2010-2011 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include <math.h>
  21 #include "noise.h"
  22 #include <iostream>
  23 #include "debug.h"
  24
  25 #define NOISE_MAGIC_X 1619
  26 #define NOISE_MAGIC_Y 31337
  27 #define NOISE_MAGIC_Z 52591
  28 #define NOISE_MAGIC_SEED 1013
  29
  30 double cos_lookup[16] = {
  31         1.0,0.9238,0.7071,0.3826,0,-0.3826,-0.7071,-0.9238,
  32         1.0,-0.9238,-0.7071,-0.3826,0,0.3826,0.7071,0.9238
  33 };
  34
  35 double dotProduct(double vx, double vy, double wx, double wy){
  36     return vx*wx+vy*wy;
  37 }
  38
  39 double easeCurve(double t){
  40     return 6*pow(t,5)-15*pow(t,4)+10*pow(t,3);
  41 }
  42
  43 double linearInterpolation(double x0, double x1, double t){
  44     return x0+(x1-x0)*t;
  45 }
  46
  47 double biLinearInterpolation(double x0y0, double x1y0, double x0y1, double x1y1, double x, double y){
  48     double tx = easeCurve(x);
  49     double ty = easeCurve(y);
  50         /*double tx = x;
  51         double ty = y;*/
  52     double u = linearInterpolation(x0y0,x1y0,tx);
  53     double v = linearInterpolation(x0y1,x1y1,tx);
  54     return linearInterpolation(u,v,ty);
  55 }
  56
  57 double triLinearInterpolation(
  58                 double v000, double v100, double v010, double v110,
  59                 double v001, double v101, double v011, double v111,
  60                 double x, double y, double z)
  61 {
  62     /*double tx = easeCurve(x);
  63     double ty = easeCurve(y);
  64     double tz = easeCurve(z);*/
  65     double tx = x;
  66     double ty = y;
  67     double tz = z;
  68         return(
  69                 v000*(1-tx)*(1-ty)*(1-tz) +
  70                 v100*tx*(1-ty)*(1-tz) +
  71                 v010*(1-tx)*ty*(1-tz) +
  72                 v110*tx*ty*(1-tz) +
  73                 v001*(1-tx)*(1-ty)*tz +
  74                 v101*tx*(1-ty)*tz +
  75                 v011*(1-tx)*ty*tz +
  76                 v111*tx*ty*tz
  77         );
  78 }
  79
  80 double noise2d(int x, int y, int seed)
  81 {
  82         int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y
  83                         + NOISE_MAGIC_SEED * seed) & 0x7fffffff;
  84         n = (n>>13)^n;
  85         n = (n * (n*n*60493+19990303) + 1376312589) & 0x7fffffff;
  86         return 1.0 - (double)n/1073741824;
  87 }
  88
  89 double noise3d(int x, int y, int z, int seed)
  90 {
  91         int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y + NOISE_MAGIC_Z * z
  92                         + NOISE_MAGIC_SEED * seed) & 0x7fffffff;
  93         n = (n>>13)^n;
  94         n = (n * (n*n*60493+19990303) + 1376312589) & 0x7fffffff;
  95         return 1.0 - (double)n/1073741824;
  96 }
  97
  98 #if 0
  99 double noise2d_gradient(double x, double y, int seed)
 100 {
 101         // Calculate the integer coordinates
 102         int x0 = (x > 0.0 ? (int)x : (int)x - 1);
 103         int y0 = (y > 0.0 ? (int)y : (int)y - 1);
 104         // Calculate the remaining part of the coordinates
 105         double xl = x - (double)x0;
 106         double yl = y - (double)y0;
 107         // Calculate random cosine lookup table indices for the integer corners.
 108         // They are looked up as unit vector gradients from the lookup table.
 109         int n00 = (int)((noise2d(x0, y0, seed)+1)*8);
 110         int n10 = (int)((noise2d(x0+1, y0, seed)+1)*8);
 111         int n01 = (int)((noise2d(x0, y0+1, seed)+1)*8);
 112         int n11 = (int)((noise2d(x0+1, y0+1, seed)+1)*8);
 113         // Make a dot product for the gradients and the positions, to get the values
 114         double s = dotProduct(cos_lookup[n00], cos_lookup[(n00+12)%16], xl, yl);
 115         double u = dotProduct(-cos_lookup[n10], cos_lookup[(n10+12)%16], 1.-xl, yl);
 116         double v = dotProduct(cos_lookup[n01], -cos_lookup[(n01+12)%16], xl, 1.-yl);
 117         double w = dotProduct(-cos_lookup[n11], -cos_lookup[(n11+12)%16], 1.-xl, 1.-yl);
 118         // Interpolate between the values
 119         return biLinearInterpolation(s,u,v,w,xl,yl);
 120 }
 121 #endif
 122
 123 #if 1
 124 double noise2d_gradient(double x, double y, int seed)
 125 {
 126         // Calculate the integer coordinates
 127         int x0 = (x > 0.0 ? (int)x : (int)x - 1);
 128         int y0 = (y > 0.0 ? (int)y : (int)y - 1);
 129         // Calculate the remaining part of the coordinates
 130         double xl = x - (double)x0;
 131         double yl = y - (double)y0;
 132         // Get values for corners of cube
 133         double v00 = noise2d(x0, y0, seed);
 134         double v10 = noise2d(x0+1, y0, seed);
 135         double v01 = noise2d(x0, y0+1, seed);
 136         double v11 = noise2d(x0+1, y0+1, seed);
 137         // Interpolate
 138         return biLinearInterpolation(v00,v10,v01,v11,xl,yl);
 139 }
 140 #endif
 141
 142 double noise3d_gradient(double x, double y, double z, int seed)
 143 {
 144         // Calculate the integer coordinates
 145         int x0 = (x > 0.0 ? (int)x : (int)x - 1);
 146         int y0 = (y > 0.0 ? (int)y : (int)y - 1);
 147         int z0 = (z > 0.0 ? (int)z : (int)z - 1);
 148         // Calculate the remaining part of the coordinates
 149         double xl = x - (double)x0;
 150         double yl = y - (double)y0;
 151         double zl = z - (double)z0;
 152         // Get values for corners of cube
 153         double v000 = noise3d(x0, y0, z0, seed);
 154         double v100 = noise3d(x0+1, y0, z0, seed);
 155         double v010 = noise3d(x0, y0+1, z0, seed);
 156         double v110 = noise3d(x0+1, y0+1, z0, seed);
 157         double v001 = noise3d(x0, y0, z0+1, seed);
 158         double v101 = noise3d(x0+1, y0, z0+1, seed);
 159         double v011 = noise3d(x0, y0+1, z0+1, seed);
 160         double v111 = noise3d(x0+1, y0+1, z0+1, seed);
 161         // Interpolate
 162         return triLinearInterpolation(v000,v100,v010,v110,v001,v101,v011,v111,xl,yl,zl);
 163 }
 164
 165 double noise2d_perlin(double x, double y, int seed,
 166                 int octaves, double persistence)
 167 {
 168         double a = 0;
 169         double f = 1.0;
 170         double g = 1.0;
 171         for(int i=0; i<octaves; i++)
 172         {
 173                 a += g * noise2d_gradient(x*f, y*f, seed+i);
 174                 f *= 2.0;
 175                 g *= persistence;
 176         }
 177         return a;
 178 }
 179
 180 double noise2d_perlin_abs(double x, double y, int seed,
 181                 int octaves, double persistence)
 182 {
 183         double a = 0;
 184         double f = 1.0;
 185         double g = 1.0;
 186         for(int i=0; i<octaves; i++)
 187         {
 188                 a += g * fabs(noise2d_gradient(x*f, y*f, seed+i));
 189                 f *= 2.0;
 190                 g *= persistence;
 191         }
 192         return a;
 193 }
 194
 195 double noise3d_perlin(double x, double y, double z, int seed,
 196                 int octaves, double persistence)
 197 {
 198         double a = 0;
 199         double f = 1.0;
 200         double g = 1.0;
 201         for(int i=0; i<octaves; i++)
 202         {
 203                 a += g * noise3d_gradient(x*f, y*f, z*f, seed+i);
 204                 f *= 2.0;
 205                 g *= persistence;
 206         }
 207         return a;
 208 }
 209
 210 double noise3d_perlin_abs(double x, double y, double z, int seed,
 211                 int octaves, double persistence)
 212 {
 213         double a = 0;
 214         double f = 1.0;
 215         double g = 1.0;
 216         for(int i=0; i<octaves; i++)
 217         {
 218                 a += g * fabs(noise3d_gradient(x*f, y*f, z*f, seed+i));
 219                 f *= 2.0;
 220                 g *= persistence;
 221         }
 222         return a;
 223 }
 224
 225 // -1->0, 0->1, 1->0
 226 double contour(double v)
 227 {
 228         v = fabs(v);
 229         if(v >= 1.0)
 230                 return 0.0;
 231         return (1.0-v);
 232 }
 233
 234 double noise3d_param(const NoiseParams &param, double x, double y, double z)
 235 {
 236         double s = param.pos_scale;
 237         x /= s;
 238         y /= s;
 239         z /= s;
 240
 241         if(param.type == NOISE_CONSTANT_ONE)
 242         {
 243                 return 1.0;
 244         }
 245         else if(param.type == NOISE_PERLIN)
 246         {
 247                 return param.noise_scale*noise3d_perlin(x,y,z, param.seed,
 248                                 param.octaves,
 249                                 param.persistence);
 250         }
 251         else if(param.type == NOISE_PERLIN_ABS)
 252         {
 253                 return param.noise_scale*noise3d_perlin_abs(x,y,z, param.seed,
 254                                 param.octaves,
 255                                 param.persistence);
 256         }
 257         else if(param.type == NOISE_PERLIN_CONTOUR)
 258         {
 259                 return contour(param.noise_scale*noise3d_perlin(x,y,z,
 260                                 param.seed, param.octaves,
 261                                 param.persistence));
 262         }
 263         else if(param.type == NOISE_PERLIN_CONTOUR_FLIP_YZ)
 264         {
 265                 return contour(param.noise_scale*noise3d_perlin(x,z,y,
 266                                 param.seed, param.octaves,
 267                                 param.persistence));
 268         }
 269         else assert(0);
 270 }
 271
 272 /*
 273         NoiseBuffer
 274 */
 275
 276 NoiseBuffer::NoiseBuffer():
 277         m_data(NULL)
 278 {
 279 }
 280
 281 NoiseBuffer::~NoiseBuffer()
 282 {
 283         clear();
 284 }
 285
 286 void NoiseBuffer::clear()
 287 {
 288         if(m_data)
 289                 delete[] m_data;
 290         m_data = NULL;
 291         m_size_x = 0;
 292         m_size_y = 0;
 293         m_size_z = 0;
 294 }
 295
 296 void NoiseBuffer::create(const NoiseParams &param,
 297                 double first_x, double first_y, double first_z,
 298                 double last_x, double last_y, double last_z,
 299                 double samplelength_x, double samplelength_y, double samplelength_z)
 300 {
 301         clear();
 302
 303         m_start_x = first_x - samplelength_x;
 304         m_start_y = first_y - samplelength_y;
 305         m_start_z = first_z - samplelength_z;
 306         m_samplelength_x = samplelength_x;
 307         m_samplelength_y = samplelength_y;
 308         m_samplelength_z = samplelength_z;
 309
 310         m_size_x = (last_x - m_start_x)/samplelength_x + 2;
 311         m_size_y = (last_y - m_start_y)/samplelength_y + 2;
 312         m_size_z = (last_z - m_start_z)/samplelength_z + 2;
 313
 314         m_data = new double[m_size_x*m_size_y*m_size_z];
 315
 316         for(int x=0; x<m_size_x; x++)
 317         for(int y=0; y<m_size_y; y++)
 318         for(int z=0; z<m_size_z; z++)
 319         {
 320                 double xd = (m_start_x + (double)x*m_samplelength_x);
 321                 double yd = (m_start_y + (double)y*m_samplelength_y);
 322                 double zd = (m_start_z + (double)z*m_samplelength_z);
 323                 double a = noise3d_param(param, xd,yd,zd);
 324                 intSet(x,y,z, a);
 325         }
 326 }
 327
 328 void NoiseBuffer::multiply(const NoiseParams &param)
 329 {
 330         assert(m_data != NULL);
 331
 332         for(int x=0; x<m_size_x; x++)
 333         for(int y=0; y<m_size_y; y++)
 334         for(int z=0; z<m_size_z; z++)
 335         {
 336                 double xd = (m_start_x + (double)x*m_samplelength_x);
 337                 double yd = (m_start_y + (double)y*m_samplelength_y);
 338                 double zd = (m_start_z + (double)z*m_samplelength_z);
 339                 double a = noise3d_param(param, xd,yd,zd);
 340                 intMultiply(x,y,z, a);
 341         }
 342 }
 343
 344 // Deprecated
 345 void NoiseBuffer::create(int seed, int octaves, double persistence,
 346                 bool abs,
 347                 double first_x, double first_y, double first_z,
 348                 double last_x, double last_y, double last_z,
 349                 double samplelength_x, double samplelength_y, double samplelength_z)
 350 {
 351         NoiseParams param;
 352         param.type = abs ? NOISE_PERLIN_ABS : NOISE_PERLIN;
 353         param.seed = seed;
 354         param.octaves = octaves;
 355         param.persistence = persistence;
 356
 357         create(param, first_x, first_y, first_z,
 358                         last_x, last_y, last_z,
 359                         samplelength_x, samplelength_y, samplelength_z);
 360 }
 361
 362 void NoiseBuffer::intSet(int x, int y, int z, double d)
 363 {
 364         int i = m_size_x*m_size_y*z + m_size_x*y + x;
 365         assert(i >= 0);
 366         assert(i < m_size_x*m_size_y*m_size_z);
 367         m_data[i] = d;
 368 }
 369
 370 void NoiseBuffer::intMultiply(int x, int y, int z, double d)
 371 {
 372         int i = m_size_x*m_size_y*z + m_size_x*y + x;
 373         assert(i >= 0);
 374         assert(i < m_size_x*m_size_y*m_size_z);
 375         m_data[i] = m_data[i] * d;
 376 }
 377
 378 double NoiseBuffer::intGet(int x, int y, int z)
 379 {
 380         int i = m_size_x*m_size_y*z + m_size_x*y + x;
 381         assert(i >= 0);
 382         assert(i < m_size_x*m_size_y*m_size_z);
 383         return m_data[i];
 384 }
 385
 386 double NoiseBuffer::get(double x, double y, double z)
 387 {
 388         x -= m_start_x;
 389         y -= m_start_y;
 390         z -= m_start_z;
 391         x /= m_samplelength_x;
 392         y /= m_samplelength_y;
 393         z /= m_samplelength_z;
 394         // Calculate the integer coordinates
 395         int x0 = (x > 0.0 ? (int)x : (int)x - 1);
 396         int y0 = (y > 0.0 ? (int)y : (int)y - 1);
 397         int z0 = (z > 0.0 ? (int)z : (int)z - 1);
 398         // Calculate the remaining part of the coordinates
 399         double xl = x - (double)x0;
 400         double yl = y - (double)y0;
 401         double zl = z - (double)z0;
 402         // Get values for corners of cube
 403         double v000 = intGet(x0,   y0,   z0);
 404         double v100 = intGet(x0+1, y0,   z0);
 405         double v010 = intGet(x0,   y0+1, z0);
 406         double v110 = intGet(x0+1, y0+1, z0);
 407         double v001 = intGet(x0,   y0,   z0+1);
 408         double v101 = intGet(x0+1, y0,   z0+1);
 409         double v011 = intGet(x0,   y0+1, z0+1);
 410         double v111 = intGet(x0+1, y0+1, z0+1);
 411         // Interpolate
 412         return triLinearInterpolation(v000,v100,v010,v110,v001,v101,v011,v111,xl,yl,zl);
 413 }
 414
 415 /*bool NoiseBuffer::contains(double x, double y, double z)
 416 {
 417         x -= m_start_x;
 418         y -= m_start_y;
 419         z -= m_start_z;
 420         x /= m_samplelength_x;
 421         y /= m_samplelength_y;
 422         z /= m_samplelength_z;
 423         if(x <= 0.0 || x >= m_size_x)
 424 }*/
 425