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 <iostream>
44 #include <cmath>
45 #include <random>
46 #include <algorithm>
47 #include <numeric>
48 
49 // THIS IS A DIRECT TRANSLATION TO C++11 FROM THE REFERENCE
50 // JAVA IMPLEMENTATION OF THE IMPROVED PERLIN FUNCTION (see http://mrl.nyu.edu/~perlin/noise/)
51 // THE ORIGINAL JAVA IMPLEMENTATION IS COPYRIGHT 2002 KEN PERLIN
52 
53 // I ADDED AN EXTRA METHOD THAT GENERATES A NEW PERMUTATION VECTOR
54 // (THIS IS NOT PRESENT IN THE ORIGINAL IMPLEMENTATION)
55 
56 // Initialize with the reference values for the permutation vector
58 {
59 
60  // Initialize the permutation vector with the reference values
61  p = {
62  151,160,137,91,90,15,131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,
63  8,99,37,240,21,10,23,190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,
64  35,11,32,57,177,33,88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,
65  134,139,48,27,166,77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,
66  55,46,245,40,244,102,143,54, 65,25,63,161,1,216,80,73,209,76,132,187,208, 89,
67  18,169,200,196,135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,
68  250,124,123,5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,
69  189,28,42,223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167,
70  43,172,9,129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,
71  97,228,251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,
72  107,49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
73  138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180 };
74 
75  // Duplicate the permutation vector
76  p.insert(p.end(), p.begin(), p.end());
77 }
78 
79 // Generate a new permutation vector based on the value of seed
80 PerlinNoise::PerlinNoise( unsigned int seed )
81 {
82  p.resize( 256 );
83 
84  // Fill p with values from 0 to 255
85  std::iota( p.begin(), p.end(), 0 );
86 
87  // Initialize a random engine with seed
88  std::default_random_engine engine( seed );
89 
90  // Suffle using the above random engine
91  std::shuffle( p.begin(), p.end(), engine );
92 
93  // Duplicate the permutation vector
94  p.insert( p.end(), p.begin(), p.end() );
95 }
96 
97 float PerlinNoise::noise( float x, float y, float z ) const
98 {
99  // Find the unit cube that contains the point
100  int X = (int) ((float)floor( x )) & 255;
101  int Y = (int) ((float)floor( y )) & 255;
102  int Z = (int) ((float)floor( z )) & 255;
103 
104  // Find relative x, y,z of point in cube
105  x -= (float)floor( x );
106  y -= (float)floor( y );
107  z -= (float)floor( z );
108 
109  // Compute fade curves for each of x, y, z
110  const float u = fade( x );
111  const float v = fade( y );
112  const float w = fade( z );
113 
114  // Hash coordinates of the 8 cube corners
115  const int A = p[X] + Y;
116  const int AA = p[A] + Z;
117  const int AB = p[A + 1] + Z;
118  const int B = p[X + 1] + Y;
119  const int BA = p[B] + Z;
120  const int BB = p[B + 1] + Z;
121 
122  // Add blended results from 8 corners of cube
123  const float res = lerp( w,
124  lerp( v,
125  lerp( u,
126  grad( p[AA], x , y, z),
127  grad( p[BA], x - 1, y, z) ),
128  lerp( u,
129  grad( p[AB], x , y - 1, z ),
130  grad( p[BB], x - 1, y - 1, z) ) ),
131  lerp( v,
132  lerp( u,
133  grad( p[AA + 1], x , y, z - 1 ),
134  grad( p[BA + 1], x - 1, y, z - 1) ),
135  lerp( u,
136  grad( p[AB + 1], x , y - 1, z - 1 ),
137  grad( p[BB + 1], x - 1, y - 1, z - 1 ) ) ) );
138 
139  return (res + 1.0f) / 2.0f;
140 }
141 
142 
143 float PerlinNoise::noise( float x, float y ) const
144 {
145  // Find the unit cube that contains the point
146  int X = (int) ((float)floor( x )) & 255;
147  int Y = (int) ((float)floor( y )) & 255;
148 
149  // Find relative x, y,z of point in cube
150  x -= (float)floor( x );
151  y -= (float)floor( y );
152 
153  // Compute fade curves for each of x, y
154  const float u = fade( x );
155  const float v = fade( y );
156 
157  // Hash coordinates of the 8 cube corners
158  const int A = p[X] + Y;
159  const int AA = p[A] + 0;
160  const int AB = p[A + 1] + 0;
161  const int B = p[X + 1] + Y;
162  const int BA = p[B] + 0;
163  const int BB = p[B + 1] + 0;
164 
165  // Add blended results from 8 corners of cube
166  const float res = lerp( v,
167  lerp( u,
168  grad( p[AA], x , y ),
169  grad( p[BA], x - 1, y ) ),
170  lerp( u,
171  grad( p[AB], x , y - 1 ),
172  grad( p[BB], x - 1, y - 1 ) ) );
173 
174  return (res + 1.0f) / 2.0f;
175 }
176 
177 
178 float PerlinNoise::fade( float t ) const
179 {
180  return t * t * t * (t * (t * 6.0f - 15.0f) + 10.0f);
181 }
182 
183 
184 float PerlinNoise::lerp( float t, float a, float b ) const
185 {
186  return a + t * (b - a);
187 }
188 
189 
190 float PerlinNoise::grad( int hash, float x, float y, float z ) const
191 {
192  const int h = hash & 15;
193 
194  // Convert lower 4 bits of hash inot 12 gradient directions
195  const float u = h < 8 ? x : y;
196  const float v = h < 4 ? y : h == 12 || h == 14 ? x : z;
197 
198  return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
199 }
200 
201 
202 float PerlinNoise::grad( int hash, float x, float y ) const
203 {
204  const int h = hash & 15;
205 
206  // Convert lower 4 bits of hash inot 12 gradient directions
207  const float u = h < 8 ? x : y;
208  const float v = h < 4 ? y : h == 12 || h == 14 ? x : 0.0f;
209 
210  return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
211 }
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:97