KiCad PCB EDA Suite
PerlinNoise.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2016 Mario Luzeiro <mrluzeiro@ua.pt>
5  * Copyright (C) 1992-2016 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
42 #include "PerlinNoise.h"
43 #include <cmath>
44 #include <iostream>
45 #include <cmath>
46 #include <random>
47 #include <algorithm>
48 #include <numeric>
49 
50 // THIS IS A DIRECT TRANSLATION TO C++11 FROM THE REFERENCE
51 // JAVA IMPLEMENTATION OF THE IMPROVED PERLIN FUNCTION (see http://mrl.nyu.edu/~perlin/noise/)
52 // THE ORIGINAL JAVA IMPLEMENTATION IS COPYRIGHT 2002 KEN PERLIN
53 
54 // I ADDED AN EXTRA METHOD THAT GENERATES A NEW PERMUTATION VECTOR
55 // (THIS IS NOT PRESENT IN THE ORIGINAL IMPLEMENTATION)
56 
57 // Initialize with the reference values for the permutation vector
59 {
60 
61  // Initialize the permutation vector with the reference values
62  p = {
63  151,160,137,91,90,15,131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,
64  8,99,37,240,21,10,23,190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,
65  35,11,32,57,177,33,88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,
66  134,139,48,27,166,77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,
67  55,46,245,40,244,102,143,54, 65,25,63,161,1,216,80,73,209,76,132,187,208, 89,
68  18,169,200,196,135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,
69  250,124,123,5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,
70  189,28,42,223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167,
71  43,172,9,129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,
72  97,228,251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,
73  107,49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
74  138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180 };
75 
76  // Duplicate the permutation vector
77  p.insert(p.end(), p.begin(), p.end());
78 }
79 
80 // Generate a new permutation vector based on the value of seed
81 PerlinNoise::PerlinNoise( unsigned int seed )
82 {
83  p.resize( 256 );
84 
85  // Fill p with values from 0 to 255
86  std::iota( p.begin(), p.end(), 0 );
87 
88  // Initialize a random engine with seed
89  std::default_random_engine engine( seed );
90 
91  // Suffle using the above random engine
92  std::shuffle( p.begin(), p.end(), engine );
93 
94  // Duplicate the permutation vector
95  p.insert( p.end(), p.begin(), p.end() );
96 }
97 
98 float PerlinNoise::noise( float x, float y, float z ) const
99 {
100  // Find the unit cube that contains the point
101  int X = static_cast<int>( std::floor( x ) ) & 255;
102  int Y = static_cast<int>( std::floor( y ) ) & 255;
103  int Z = static_cast<int>( std::floor( z ) ) & 255;
104 
105  // Find relative x, y,z of point in cube
106  x -= std::floor( x );
107  y -= std::floor( y );
108  z -= std::floor( z );
109 
110  // Compute fade curves for each of x, y, z
111  const float u = fade( x );
112  const float v = fade( y );
113  const float w = fade( z );
114 
115  // Hash coordinates of the 8 cube corners
116  const int A = p[X] + Y;
117  const int AA = p[A] + Z;
118  const int AB = p[A + 1] + Z;
119  const int B = p[X + 1] + Y;
120  const int BA = p[B] + Z;
121  const int BB = p[B + 1] + Z;
122 
123  // Add blended results from 8 corners of cube
124  const float res = lerp( w,
125  lerp( v,
126  lerp( u,
127  grad( p[AA], x , y, z),
128  grad( p[BA], x - 1, y, z) ),
129  lerp( u,
130  grad( p[AB], x , y - 1, z ),
131  grad( p[BB], x - 1, y - 1, z) ) ),
132  lerp( v,
133  lerp( u,
134  grad( p[AA + 1], x , y, z - 1 ),
135  grad( p[BA + 1], x - 1, y, z - 1) ),
136  lerp( u,
137  grad( p[AB + 1], x , y - 1, z - 1 ),
138  grad( p[BB + 1], x - 1, y - 1, z - 1 ) ) ) );
139 
140  return (res + 1.0f) / 2.0f;
141 }
142 
143 
144 float PerlinNoise::noise( float x, float y ) const
145 {
146  // Find the unit cube that contains the point
147  int X = static_cast<int>( std::floor( x ) ) & 255;
148  int Y = static_cast<int>( std::floor( y ) ) & 255;
149 
150  // Find relative x, y,z of point in cube
151  x -= std::floor( x );
152  y -= std::floor( y );
153 
154  // Compute fade curves for each of x, y
155  const float u = fade( x );
156  const float v = fade( y );
157 
158  // Hash coordinates of the 8 cube corners
159  const int A = p[X] + Y;
160  const int AA = p[A] + 0;
161  const int AB = p[A + 1] + 0;
162  const int B = p[X + 1] + Y;
163  const int BA = p[B] + 0;
164  const int BB = p[B + 1] + 0;
165 
166  // Add blended results from 8 corners of cube
167  const float res = lerp( v,
168  lerp( u,
169  grad( p[AA], x , y ),
170  grad( p[BA], x - 1, y ) ),
171  lerp( u,
172  grad( p[AB], x , y - 1 ),
173  grad( p[BB], x - 1, y - 1 ) ) );
174 
175  return (res + 1.0f) / 2.0f;
176 }
177 
178 
179 float PerlinNoise::fade( float t ) const
180 {
181  return t * t * t * (t * (t * 6.0f - 15.0f) + 10.0f);
182 }
183 
184 
185 float PerlinNoise::lerp( float t, float a, float b ) const
186 {
187  return a + t * (b - a);
188 }
189 
190 
191 float PerlinNoise::grad( int hash, float x, float y, float z ) const
192 {
193  const int h = hash & 15;
194 
195  // Convert lower 4 bits of hash inot 12 gradient directions
196  const float u = h < 8 ? x : y;
197  const float v = h < 4 ? y : h == 12 || h == 14 ? x : z;
198 
199  return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
200 }
201 
202 
203 float PerlinNoise::grad( int hash, float x, float y ) const
204 {
205  const int h = hash & 15;
206 
207  // Convert lower 4 bits of hash inot 12 gradient directions
208  const float u = h < 8 ? x : y;
209  const float v = h < 4 ? y : h == 12 || h == 14 ? x : 0.0f;
210 
211  return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
212 }
This source code comes from the project: https://github.com/sol-prog/Perlin_Noise.
std::vector< int > p
Definition: PerlinNoise.h:58
float lerp(float t, float a, float b) const
float fade(float t) const
float grad(int hash, float x, float y, float z) const
float noise(float x, float y, float z) const
Definition: PerlinNoise.cpp:98