source/maths/Noise.cpp

   1 /* Copyright (C) 2009 Wildfire Games.
   2  * This file is part of 0 A.D.
   3  *
   4  * 0 A.D. is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * 0 A.D. is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 /*
  19  * 2D and 3D seamless Perlin noise
  20  */
  21
  22 // Based on http://www.cs.cmu.edu/~mzucker/code/perlin-noise-math-faq.html
  23 // and http://mrl.nyu.edu/~perlin/paper445.pdf.
  24 // Not optimized for speed yet.
  25
  26 #include "precompiled.h"
  27 #include "Noise.h"
  28 #include <cmath>
  29 #include <boost/random/mersenne_twister.hpp>
  30
  31 namespace
  32 {
  33         /// Random number generator (Boost Mersenne Twister)
  34         boost::mt19937 rng;
  35
  36         /// Utility function for random numbers
  37         float randFloat() {
  38                 return ((float)rng()) / 4294967296.0f;
  39         }
  40
  41         /// Utility function used in both noises as an ease curve
  42         float easeCurve(float t)
  43         {
  44                 return t*t*t*(t*(t*6-15)+10);
  45         }
  46 }
  47
  48 Noise2D::Noise2D(int f)
  49 {
  50         freq = f;
  51         grads = new CVector2D*[freq];
  52         for(int i=0; i<freq; i++)
  53         {
  54                 grads[i] = new CVector2D[freq];
  55                 for(int j=0; j<freq; j++)
  56                 {
  57                         float a = randFloat() * 2 * (float)M_PI;
  58                         grads[i][j] = CVector2D(cos(a), sin(a));
  59                 }
  60         }
  61 }
  62
  63 Noise2D::~ Noise2D()
  64 {
  65         for(int i=0; i<freq; i++)
  66         {
  67                 delete[] grads[i];
  68         }
  69         delete[] grads;
  70 }
  71
  72 float Noise2D::operator()(float x, float y)
  73 {
  74         x *= freq;
  75         y *= freq;
  76
  77         int ix = (int)floor(x);
  78         int iy = (int)floor(y);
  79
  80         float fx = x - ix;
  81         float fy = y - iy;
  82
  83         ix %= freq; if(ix<0) ix += freq;
  84         iy %= freq; if(iy<0) iy += freq;
  85
  86         int ix1 = (ix+1) % freq;
  87         int iy1 = (iy+1) % freq;
  88
  89         float s = grads[ix][iy].Dot(CVector2D(fx, fy));
  90         float t = grads[ix1][iy].Dot(CVector2D(fx-1, fy));
  91         float u = grads[ix][iy1].Dot(CVector2D(fx, fy-1));
  92         float v = grads[ix1][iy1].Dot(CVector2D(fx-1, fy-1));
  93
  94         float ex = easeCurve(fx);
  95         float ey = easeCurve(fy);
  96         float a = s + ex*(t-s);
  97         float b = u + ex*(v-u);
  98         return (a + ey*(b-a)) * .5 + .5;
  99 }
 100
 101 Noise3D::Noise3D(int f, int v) : freq(f), vfreq(v)
 102 {
 103         grads = new CVector3D**[freq];
 104         for(int i=0; i<freq; i++)
 105         {
 106                 grads[i] = new CVector3D*[freq];
 107                 for(int j=0; j<freq; j++)
 108                 {
 109                         grads[i][j] = new CVector3D[vfreq];
 110                         for(int k=0; k<vfreq; k++)
 111                         {
 112                                 CVector3D vec;
 113                                 do {
 114                                         vec = CVector3D(2*randFloat()-1, 2*randFloat()-1, 2*randFloat()-1);
 115                                 }
 116                                 while(vec.LengthSquared() > 1 || vec.LengthSquared() < 0.1);
 117                                 vec.Normalize();
 118                                 grads[i][j][k] = CVector3D(vec.X, vec.Y, vec.Z);
 119                         }
 120                 }
 121         }
 122 }
 123
 124 Noise3D::~ Noise3D()
 125 {
 126         for(int i=0; i<freq; i++)
 127         {
 128                 for(int j=0; j<freq; j++)
 129                 {
 130                         delete[] grads[i][j];
 131                 }
 132                 delete[] grads[i];
 133         }
 134         delete[] grads;
 135 }
 136
 137 float Noise3D::operator()(float x, float y, float z)
 138 {
 139         x *= freq;
 140         y *= freq;
 141         z *= vfreq;
 142
 143         int ix = (int)floor(x);
 144         int iy = (int)floor(y);
 145         int iz = (int)floor(z);
 146
 147         float fx = x - ix;
 148         float fy = y - iy;
 149         float fz = z - iz;
 150
 151         ix %= freq; if(ix<0) ix += freq;
 152         iy %= freq; if(iy<0) iy += freq;
 153         iz %= vfreq; if(iz<0) iz += vfreq;
 154
 155         int ix1 = (ix+1) % freq;
 156         int iy1 = (iy+1) % freq;
 157         int iz1 = (iz+1) % vfreq;
 158
 159         float s0 = grads[ix][iy][iz].Dot(CVector3D(fx, fy, fz));
 160         float t0 = grads[ix1][iy][iz].Dot(CVector3D(fx-1, fy, fz));
 161         float u0 = grads[ix][iy1][iz].Dot(CVector3D(fx, fy-1, fz));
 162         float v0 = grads[ix1][iy1][iz].Dot(CVector3D(fx-1, fy-1, fz));
 163
 164         float s1 = grads[ix][iy][iz1].Dot(CVector3D(fx, fy, fz-1));
 165         float t1 = grads[ix1][iy][iz1].Dot(CVector3D(fx-1, fy, fz-1));
 166         float u1 = grads[ix][iy1][iz1].Dot(CVector3D(fx, fy-1, fz-1));
 167         float v1 = grads[ix1][iy1][iz1].Dot(CVector3D(fx-1, fy-1, fz-1));
 168
 169         float ex = easeCurve(fx);
 170         float ey = easeCurve(fy);
 171         float ez = easeCurve(fz);
 172
 173         float a0 = s0 + ex*(t0-s0);
 174         float b0 = u0 + ex*(v0-u0);
 175         float c0 = a0 + ey*(b0-a0);
 176
 177         float a1 = s1 + ex*(t1-s1);
 178         float b1 = u1 + ex*(v1-u1);
 179         float c1 = a1 + ey*(b1-a1);
 180
 181         return (c0 + ez*(c1-c0)) * .5 + .5;
 182 }
 183
 184