forked from boskee/Minecraft
/
perlin.py
398 lines (339 loc) · 14.4 KB
/
perlin.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
# Copyright (c) 2008, Casey Duncan (casey dot duncan at gmail dot com)
# Under MIT License
# From https://pypi.python.org/pypi/noise/
"""Perlin noise -- pure python implementation"""
__version__ = '$Id: perlin.py 521 2008-12-15 03:03:52Z casey.duncan $'
from math import floor, fmod, sqrt
from random import randint
__all__ = (
'BaseNoise', 'SimplexNoise', 'TileableNoise',
)
# 3D Gradient vectors
_GRAD3 = (
(1, 1, 0), (-1, 1, 0), (1, -1, 0), (-1, -1, 0),
(1, 0, 1), (-1, 0, 1), (1, 0, -1), (-1, 0, -1),
(0, 1, 1), (0, -1, 1), (0, 1, -1), (0, -1, -1),
(1, 1, 0), (0, -1, 1), (-1, 1, 0), (0, -1, -1),
)
# 4D Gradient vectors
_GRAD4 = (
(0, 1, 1, 1), (0, 1, 1, -1), (0, 1, -1, 1), (0, 1, -1, -1),
(0, -1, 1, 1), (0, -1, 1, -1), (0, -1, -1, 1), (0, -1, -1, -1),
(1, 0, 1, 1), (1, 0, 1, -1), (1, 0, -1, 1), (1, 0, -1, -1),
(-1, 0, 1, 1), (-1, 0, 1, -1), (-1, 0, -1, 1), (-1, 0, -1, -1),
(1, 1, 0, 1), (1, 1, 0, -1), (1, -1, 0, 1), (1, -1, 0, -1),
(-1, 1, 0, 1), (-1, 1, 0, -1), (-1, -1, 0, 1), (-1, -1, 0, -1),
(1, 1, 1, 0), (1, 1, -1, 0), (1, -1, 1, 0), (1, -1, -1, 0),
(-1, 1, 1, 0), (-1, 1, -1, 0), (-1, -1, 1, 0), (-1, -1, -1, 0)
)
# A lookup table to traverse the simplex around a given point in 4D.
# Details can be found where this table is used, in the 4D noise method.
_SIMPLEX = (
(0, 1, 2, 3), (0, 1, 3, 2), (0, 0, 0, 0), (0, 2, 3, 1), (0, 0, 0, 0),
(0, 0, 0, 0), (0, 0, 0, 0), (1, 2, 3, 0),
(0, 2, 1, 3), (0, 0, 0, 0), (0, 3, 1, 2), (0, 3, 2, 1), (0, 0, 0, 0),
(0, 0, 0, 0), (0, 0, 0, 0), (1, 3, 2, 0),
(0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0),
(0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0),
(1, 2, 0, 3), (0, 0, 0, 0), (1, 3, 0, 2), (0, 0, 0, 0), (0, 0, 0, 0),
(0, 0, 0, 0), (2, 3, 0, 1), (2, 3, 1, 0),
(1, 0, 2, 3), (1, 0, 3, 2), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0),
(2, 0, 3, 1), (0, 0, 0, 0), (2, 1, 3, 0),
(0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0),
(0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0),
(2, 0, 1, 3), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (3, 0, 1, 2),
(3, 0, 2, 1), (0, 0, 0, 0), (3, 1, 2, 0),
(2, 1, 0, 3), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (3, 1, 0, 2),
(0, 0, 0, 0), (3, 2, 0, 1), (3, 2, 1, 0)
)
# Simplex skew constants
_F2 = 0.5 * (sqrt(3.0) - 1.0)
_G2 = (3.0 - sqrt(3.0)) / 6.0
_F3 = 1.0 / 3.0
_G3 = 1.0 / 6.0
class BaseNoise(object):
"""Noise abstract base class"""
def __init__(self, period=None, permutation_table=None):
"""Initialize the noise generator. With no arguments, the default
period and permutation table are used (256). The default permutation
table generates the exact same noise pattern each time.
An integer period can be specified, to generate a random permutation
table with period elements. The period determines the (integer)
interval that the noise repeats, which is useful for creating tiled
textures. period should be a power-of-two, though this is not
enforced. Note that the speed of the noise algorithm is independent of
the period size, though larger periods mean a larger table, which
consume more memory.
A permutation table consisting of an iterable sequence of whole
numbers can be specified directly. This should have a power-of-two
length. Typical permutation tables are a sequence of unique integers in
the range [0,period) in random order, though other arrangements could
prove useful, they will not be "pure" simplex noise. The largest
element in the sequence must be no larger than period-1.
period and permutation_table may not be specified together.
"""
self.permutation = (
151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7,
225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6,
148, 247, 120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35,
11, 32, 57, 177, 33, 88, 237, 149, 56, 87, 174, 20, 125, 136, 171,
168, 68, 175, 74, 165, 71, 134, 139, 48, 27, 166, 77, 146, 158,
231, 83, 111, 229, 122, 60, 211, 133, 230, 220, 105, 92, 41, 55,
46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80, 73,
209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188,
159, 86, 164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250,
124, 123, 5, 202, 38, 147, 118, 126, 255, 82, 85, 212, 207, 206,
59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 223, 183, 170, 213, 119,
248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 172, 9,
129, 22, 39, 253, 9, 98, 108, 110, 79, 113, 224, 232, 178, 185,
112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12,
191, 179, 162, 241, 81, 51, 145, 235, 249, 14, 239, 107, 49, 192,
214, 31, 181, 199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45,
127, 4, 150, 254, 138, 236, 205, 93, 222, 114, 67, 29, 24, 72, 243,
141, 128, 195, 78, 66, 215, 61, 156, 180
)
self.period = len(self.permutation)
# Double permutation array so we don't need to wrap
self.permutation *= 2
if period is not None and permutation_table is not None:
raise ValueError(
'Can specify either period or permutation_table, not both')
if period is not None:
self.randomize(period)
elif permutation_table is not None:
self.permutation = tuple(permutation_table) * 2
self.period = len(permutation_table)
def randomize(self, period=None):
"""Randomize the permutation table used by the noise functions. This
makes them generate a different noise pattern for the same inputs.
"""
if period is not None:
self.period = period
perm = range(self.period)
perm_right = self.period - 1
for i in list(perm):
j = randint(0, perm_right)
perm[i], perm[j] = perm[j], perm[i]
self.permutation = tuple(perm) * 2
class SimplexNoise(BaseNoise):
"""Perlin simplex noise generator
Adapted from Stefan Gustavson's Java implementation described here:
http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf
To summarize:
"In 2001, Ken Perlin presented 'simplex noise', a replacement for his
classic
noise algorithm. Classic 'Perlin noise' won him an academy award and has
become an ubiquitous procedural primitive for computer graphics over the
years, but in hindsight it has quite a few limitations. Ken Perlin himself
designed simplex noise specifically to overcome those limitations, and he
spent a lot of good thinking on it. Therefore, it is a better idea than his
original algorithm. A few of the more prominent advantages are:
* Simplex noise has a lower computational complexity and requires fewer
multiplications.
* Simplex noise scales to higher dimensions (4D, 5D and up) with much less
computational cost, the complexity is O(N) for N dimensions instead of
the O(2^N) of classic Noise.
* Simplex noise has no noticeable directional artifacts. Simplex noise has
a well-defined and continuous gradient everywhere that can be computed
quite cheaply.
* Simplex noise is easy to implement in hardware."
"""
def noise2(self, x, y):
"""2D Perlin simplex noise.
Return a floating point value from -1 to 1 for the given x,
y coordinate.
The same value is always returned for a given x, y pair unless the
permutation table changes (see randomize above).
"""
# Skew input space to determine which simplex (triangle) we are in
s = (x + y) * _F2
i = floor(x + s)
j = floor(y + s)
t = (i + j) * _G2
x0 = x - (i - t) # "Unskewed" distances from cell origin
y0 = y - (j - t)
if x0 > y0:
i1 = 1
j1 = 0 # Lower triangle, XY order: (0,0)->(1,0)->(1,1)
else:
i1 = 0
j1 = 1 # Upper triangle, YX order: (0,0)->(0,1)->(1,1)
x1 = x0 - i1 + _G2 # Offsets for middle corner in (x, y) unskewed coords
y1 = y0 - j1 + _G2
x2 = x0 + _G2 * 2.0 - 1.0 # Offsets for last corner in (x, y) unskewed coords
y2 = y0 + _G2 * 2.0 - 1.0
# Determine hashed gradient indices of the three simplex corners
perm = self.permutation
ii = int(i) % self.period
jj = int(j) % self.period
gi0 = perm[ii + perm[jj]] % 12
gi1 = perm[ii + i1 + perm[jj + j1]] % 12
gi2 = perm[ii + 1 + perm[jj + 1]] % 12
# Calculate the contribution from the three corners
tt = 0.5 - x0 ** 2 - y0 ** 2
if tt > 0:
g = _GRAD3[gi0]
noise = tt ** 4 * (g[0] * x0 + g[1] * y0)
else:
noise = 0.0
tt = 0.5 - x1 ** 2 - y1 ** 2
if tt > 0:
g = _GRAD3[gi1]
noise += tt ** 4 * (g[0] * x1 + g[1] * y1)
tt = 0.5 - x2 ** 2 - y2 ** 2
if tt > 0:
g = _GRAD3[gi2]
noise += tt ** 4 * (g[0] * x2 + g[1] * y2)
return noise * 70.0 # scale noise to [-1, 1]
def noise3(self, x, y, z):
"""3D Perlin simplex noise.
Return a floating point value from -1 to 1 for the given x, y,
z coordinate.
The same value is always returned for a given x, y, z pair unless the
permutation table changes (see randomize above).
"""
# Skew the input space to determine which simplex cell we're in
s = (x + y + z) * _F3
i = floor(x + s)
j = floor(y + s)
k = floor(z + s)
t = (i + j + k) * _G3
x0 = x - (i - t) # "Unskewed" distances from cell origin
y0 = y - (j - t)
z0 = z - (k - t)
# For the 3D case, the simplex shape is a slightly irregular tetrahedron.
# Determine which simplex we are in.
if x0 >= y0:
if y0 >= z0:
i1 = 1
j1 = 0
k1 = 0
i2 = 1
j2 = 1
k2 = 0
elif x0 >= z0:
i1 = 1
j1 = 0
k1 = 0
i2 = 1
j2 = 0
k2 = 1
else:
i1 = 0
j1 = 0
k1 = 1
i2 = 1
j2 = 0
k2 = 1
else: # x0 < y0
if y0 < z0:
i1 = 0
j1 = 0
k1 = 1
i2 = 0
j2 = 1
k2 = 1
elif x0 < z0:
i1 = 0
j1 = 1
k1 = 0
i2 = 0
j2 = 1
k2 = 1
else:
i1 = 0
j1 = 1
k1 = 0
i2 = 1
j2 = 1
k2 = 0
# Offsets for remaining corners
x1 = x0 - i1 + _G3
y1 = y0 - j1 + _G3
z1 = z0 - k1 + _G3
x2 = x0 - i2 + 2.0 * _G3
y2 = y0 - j2 + 2.0 * _G3
z2 = z0 - k2 + 2.0 * _G3
x3 = x0 - 1.0 + 3.0 * _G3
y3 = y0 - 1.0 + 3.0 * _G3
z3 = z0 - 1.0 + 3.0 * _G3
# Calculate the hashed gradient indices of the four simplex corners
perm = self.permutation
ii = int(i) % self.period
jj = int(j) % self.period
kk = int(k) % self.period
gi0 = perm[ii + perm[jj + perm[kk]]] % 12
gi1 = perm[ii + i1 + perm[jj + j1 + perm[kk + k1]]] % 12
gi2 = perm[ii + i2 + perm[jj + j2 + perm[kk + k2]]] % 12
gi3 = perm[ii + 1 + perm[jj + 1 + perm[kk + 1]]] % 12
# Calculate the contribution from the four corners
tt = 0.6 - x0 ** 2 - y0 ** 2 - z0 ** 2
if tt > 0:
g = _GRAD3[gi0]
noise = tt ** 4 * (g[0] * x0 + g[1] * y0 + g[2] * z0)
else:
noise = 0.0
tt = 0.6 - x1 ** 2 - y1 ** 2 - z1 ** 2
if tt > 0:
g = _GRAD3[gi1]
noise += tt ** 4 * (g[0] * x1 + g[1] * y1 + g[2] * z1)
tt = 0.6 - x2 ** 2 - y2 ** 2 - z2 ** 2
if tt > 0:
g = _GRAD3[gi2]
noise += tt ** 4 * (g[0] * x2 + g[1] * y2 + g[2] * z2)
tt = 0.6 - x3 ** 2 - y3 ** 2 - z3 ** 2
if tt > 0:
g = _GRAD3[gi3]
noise += tt ** 4 * (g[0] * x3 + g[1] * y3 + g[2] * z3)
return noise * 32.0
def lerp(t, a, b):
return a + t * (b - a)
def grad3(hash, x, y, z):
g = _GRAD3[hash % 16]
return x * g[0] + y * g[1] + z * g[2]
class TileableNoise(BaseNoise):
"""Tileable implemention of Perlin "improved" noise. This
is based on the reference implementation published here:
http://mrl.nyu.edu/~perlin/noise/
"""
def noise3(self, x, y, z, repeat, base=0.0):
"""Tileable 3D noise.
repeat specifies the integer interval in each dimension
when the noise pattern repeats.
base allows a different texture to be generated for
the same repeat interval.
"""
i = int(fmod(floor(x), repeat))
j = int(fmod(floor(y), repeat))
k = int(fmod(floor(z), repeat))
ii = (i + 1) % repeat
jj = (j + 1) % repeat
kk = (k + 1) % repeat
if base:
i += base
j += base
k += base
ii += base
jj += base
kk += base
x -= floor(x)
y -= floor(y)
z -= floor(z)
fx = x ** 3 * (x * (x * 6 - 15) + 10)
fy = y ** 3 * (y * (y * 6 - 15) + 10)
fz = z ** 3 * (z * (z * 6 - 15) + 10)
perm = self.permutation
A = perm[i]
AA = perm[A + j]
AB = perm[A + jj]
B = perm[ii]
BA = perm[B + j]
BB = perm[B + jj]
return lerp(fz, lerp(fy, lerp(fx, grad3(perm[AA + k], x, y, z),
grad3(perm[BA + k], x - 1, y, z)),
lerp(fx, grad3(perm[AB + k], x, y - 1, z),
grad3(perm[BB + k], x - 1, y - 1, z))),
lerp(fy, lerp(fx, grad3(perm[AA + kk], x, y, z - 1),
grad3(perm[BA + kk], x - 1, y, z - 1)),
lerp(fx, grad3(perm[AB + kk], x, y - 1, z - 1),
grad3(perm[BB + kk], x - 1, y - 1, z - 1))))