Bukkit-API  1.7.9-R0.2
The inofficial Bukkit-API
SimplexNoiseGenerator.java
1 package org.bukkit.util.noise;
2 
3 import java.util.Random;
4 import org.bukkit.World;
5 
6 /**
7  * Generates simplex-based noise.
8  * <p>
9  * This is a modified version of the freely published version in the paper by
10  * Stefan Gustavson at
11  * <a href="http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf">
12  * http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf</a>
13  */
15  protected static final double SQRT_3 = Math.sqrt(3);
16  protected static final double SQRT_5 = Math.sqrt(5);
17  protected static final double F2 = 0.5 * (SQRT_3 - 1);
18  protected static final double G2 = (3 - SQRT_3) / 6;
19  protected static final double G22 = G2 * 2.0 - 1;
20  protected static final double F3 = 1.0 / 3.0;
21  protected static final double G3 = 1.0 / 6.0;
22  protected static final double F4 = (SQRT_5 - 1.0) / 4.0;
23  protected static final double G4 = (5.0 - SQRT_5) / 20.0;
24  protected static final double G42 = G4 * 2.0;
25  protected static final double G43 = G4 * 3.0;
26  protected static final double G44 = G4 * 4.0 - 1.0;
27  protected static final int grad4[][] = {{0, 1, 1, 1}, {0, 1, 1, -1}, {0, 1, -1, 1}, {0, 1, -1, -1},
28  {0, -1, 1, 1}, {0, -1, 1, -1}, {0, -1, -1, 1}, {0, -1, -1, -1},
29  {1, 0, 1, 1}, {1, 0, 1, -1}, {1, 0, -1, 1}, {1, 0, -1, -1},
30  {-1, 0, 1, 1}, {-1, 0, 1, -1}, {-1, 0, -1, 1}, {-1, 0, -1, -1},
31  {1, 1, 0, 1}, {1, 1, 0, -1}, {1, -1, 0, 1}, {1, -1, 0, -1},
32  {-1, 1, 0, 1}, {-1, 1, 0, -1}, {-1, -1, 0, 1}, {-1, -1, 0, -1},
33  {1, 1, 1, 0}, {1, 1, -1, 0}, {1, -1, 1, 0}, {1, -1, -1, 0},
34  {-1, 1, 1, 0}, {-1, 1, -1, 0}, {-1, -1, 1, 0}, {-1, -1, -1, 0}};
35  protected static final int simplex[][] = {
36  {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},
37  {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},
38  {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},
39  {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},
40  {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},
41  {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},
42  {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},
43  {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}};
44  protected static double offsetW;
45  private static final SimplexNoiseGenerator instance = new SimplexNoiseGenerator();
46 
47  protected SimplexNoiseGenerator() {
48  super();
49  }
50 
51  /**
52  * Creates a seeded simplex noise generator for the given world
53  *
54  * @param world World to construct this generator for
55  */
56  public SimplexNoiseGenerator(World world) {
57  this(new Random(world.getSeed()));
58  }
59 
60  /**
61  * Creates a seeded simplex noise generator for the given seed
62  *
63  * @param seed Seed to construct this generator for
64  */
65  public SimplexNoiseGenerator(long seed) {
66  this(new Random(seed));
67  }
68 
69  /**
70  * Creates a seeded simplex noise generator with the given Random
71  *
72  * @param rand Random to construct with
73  */
74  public SimplexNoiseGenerator(Random rand) {
75  super(rand);
76  offsetW = rand.nextDouble() * 256;
77  }
78 
79  protected static double dot(int g[], double x, double y) {
80  return g[0] * x + g[1] * y;
81  }
82 
83  protected static double dot(int g[], double x, double y, double z) {
84  return g[0] * x + g[1] * y + g[2] * z;
85  }
86 
87  protected static double dot(int g[], double x, double y, double z, double w) {
88  return g[0] * x + g[1] * y + g[2] * z + g[3] * w;
89  }
90 
91  /**
92  * Computes and returns the 1D unseeded simplex noise for the given
93  * coordinates in 1D space
94  *
95  * @param xin X coordinate
96  * @return Noise at given location, from range -1 to 1
97  */
98  public static double getNoise(double xin) {
99  return instance.noise(xin);
100  }
101 
102  /**
103  * Computes and returns the 2D unseeded simplex noise for the given
104  * coordinates in 2D space
105  *
106  * @param xin X coordinate
107  * @param yin Y coordinate
108  * @return Noise at given location, from range -1 to 1
109  */
110  public static double getNoise(double xin, double yin) {
111  return instance.noise(xin, yin);
112  }
113 
114  /**
115  * Computes and returns the 3D unseeded simplex noise for the given
116  * coordinates in 3D space
117  *
118  * @param xin X coordinate
119  * @param yin Y coordinate
120  * @param zin Z coordinate
121  * @return Noise at given location, from range -1 to 1
122  */
123  public static double getNoise(double xin, double yin, double zin) {
124  return instance.noise(xin, yin, zin);
125  }
126 
127  /**
128  * Computes and returns the 4D simplex noise for the given coordinates in
129  * 4D space
130  *
131  * @param x X coordinate
132  * @param y Y coordinate
133  * @param z Z coordinate
134  * @param w W coordinate
135  * @return Noise at given location, from range -1 to 1
136  */
137  public static double getNoise(double x, double y, double z, double w) {
138  return instance.noise(x, y, z, w);
139  }
140 
141  @Override
142  public double noise(double xin, double yin, double zin) {
143  xin += offsetX;
144  yin += offsetY;
145  zin += offsetZ;
146 
147  double n0, n1, n2, n3; // Noise contributions from the four corners
148 
149  // Skew the input space to determine which simplex cell we're in
150  double s = (xin + yin + zin) * F3; // Very nice and simple skew factor for 3D
151  int i = floor(xin + s);
152  int j = floor(yin + s);
153  int k = floor(zin + s);
154  double t = (i + j + k) * G3;
155  double X0 = i - t; // Unskew the cell origin back to (x,y,z) space
156  double Y0 = j - t;
157  double Z0 = k - t;
158  double x0 = xin - X0; // The x,y,z distances from the cell origin
159  double y0 = yin - Y0;
160  double z0 = zin - Z0;
161 
162  // For the 3D case, the simplex shape is a slightly irregular tetrahedron.
163 
164  // Determine which simplex we are in.
165  int i1, j1, k1; // Offsets for second corner of simplex in (i,j,k) coords
166  int i2, j2, k2; // Offsets for third corner of simplex in (i,j,k) coords
167  if (x0 >= y0) {
168  if (y0 >= z0) {
169  i1 = 1;
170  j1 = 0;
171  k1 = 0;
172  i2 = 1;
173  j2 = 1;
174  k2 = 0;
175  } // X Y Z order
176  else if (x0 >= z0) {
177  i1 = 1;
178  j1 = 0;
179  k1 = 0;
180  i2 = 1;
181  j2 = 0;
182  k2 = 1;
183  } // X Z Y order
184  else {
185  i1 = 0;
186  j1 = 0;
187  k1 = 1;
188  i2 = 1;
189  j2 = 0;
190  k2 = 1;
191  } // Z X Y order
192  } else { // x0<y0
193  if (y0 < z0) {
194  i1 = 0;
195  j1 = 0;
196  k1 = 1;
197  i2 = 0;
198  j2 = 1;
199  k2 = 1;
200  } // Z Y X order
201  else if (x0 < z0) {
202  i1 = 0;
203  j1 = 1;
204  k1 = 0;
205  i2 = 0;
206  j2 = 1;
207  k2 = 1;
208  } // Y Z X order
209  else {
210  i1 = 0;
211  j1 = 1;
212  k1 = 0;
213  i2 = 1;
214  j2 = 1;
215  k2 = 0;
216  } // Y X Z order
217  }
218 
219  // A step of (1,0,0) in (i,j,k) means a step of (1-c,-c,-c) in (x,y,z),
220  // a step of (0,1,0) in (i,j,k) means a step of (-c,1-c,-c) in (x,y,z), and
221  // a step of (0,0,1) in (i,j,k) means a step of (-c,-c,1-c) in (x,y,z), where
222  // c = 1/6.
223  double x1 = x0 - i1 + G3; // Offsets for second corner in (x,y,z) coords
224  double y1 = y0 - j1 + G3;
225  double z1 = z0 - k1 + G3;
226  double x2 = x0 - i2 + 2.0 * G3; // Offsets for third corner in (x,y,z) coords
227  double y2 = y0 - j2 + 2.0 * G3;
228  double z2 = z0 - k2 + 2.0 * G3;
229  double x3 = x0 - 1.0 + 3.0 * G3; // Offsets for last corner in (x,y,z) coords
230  double y3 = y0 - 1.0 + 3.0 * G3;
231  double z3 = z0 - 1.0 + 3.0 * G3;
232 
233  // Work out the hashed gradient indices of the four simplex corners
234  int ii = i & 255;
235  int jj = j & 255;
236  int kk = k & 255;
237  int gi0 = perm[ii + perm[jj + perm[kk]]] % 12;
238  int gi1 = perm[ii + i1 + perm[jj + j1 + perm[kk + k1]]] % 12;
239  int gi2 = perm[ii + i2 + perm[jj + j2 + perm[kk + k2]]] % 12;
240  int gi3 = perm[ii + 1 + perm[jj + 1 + perm[kk + 1]]] % 12;
241 
242  // Calculate the contribution from the four corners
243  double t0 = 0.6 - x0 * x0 - y0 * y0 - z0 * z0;
244  if (t0 < 0) {
245  n0 = 0.0;
246  } else {
247  t0 *= t0;
248  n0 = t0 * t0 * dot(grad3[gi0], x0, y0, z0);
249  }
250 
251  double t1 = 0.6 - x1 * x1 - y1 * y1 - z1 * z1;
252  if (t1 < 0) {
253  n1 = 0.0;
254  } else {
255  t1 *= t1;
256  n1 = t1 * t1 * dot(grad3[gi1], x1, y1, z1);
257  }
258 
259  double t2 = 0.6 - x2 * x2 - y2 * y2 - z2 * z2;
260  if (t2 < 0) {
261  n2 = 0.0;
262  } else {
263  t2 *= t2;
264  n2 = t2 * t2 * dot(grad3[gi2], x2, y2, z2);
265  }
266 
267  double t3 = 0.6 - x3 * x3 - y3 * y3 - z3 * z3;
268  if (t3 < 0) {
269  n3 = 0.0;
270  } else {
271  t3 *= t3;
272  n3 = t3 * t3 * dot(grad3[gi3], x3, y3, z3);
273  }
274 
275  // Add contributions from each corner to get the final noise value.
276  // The result is scaled to stay just inside [-1,1]
277  return 32.0 * (n0 + n1 + n2 + n3);
278  }
279 
280  @Override
281  public double noise(double xin, double yin) {
282  xin += offsetX;
283  yin += offsetY;
284 
285  double n0, n1, n2; // Noise contributions from the three corners
286 
287  // Skew the input space to determine which simplex cell we're in
288  double s = (xin + yin) * F2; // Hairy factor for 2D
289  int i = floor(xin + s);
290  int j = floor(yin + s);
291  double t = (i + j) * G2;
292  double X0 = i - t; // Unskew the cell origin back to (x,y) space
293  double Y0 = j - t;
294  double x0 = xin - X0; // The x,y distances from the cell origin
295  double y0 = yin - Y0;
296 
297  // For the 2D case, the simplex shape is an equilateral triangle.
298 
299  // Determine which simplex we are in.
300  int i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords
301  if (x0 > y0) {
302  i1 = 1;
303  j1 = 0;
304  } // lower triangle, XY order: (0,0)->(1,0)->(1,1)
305  else {
306  i1 = 0;
307  j1 = 1;
308  } // upper triangle, YX order: (0,0)->(0,1)->(1,1)
309 
310  // A step of (1,0) in (i,j) means a step of (1-c,-c) in (x,y), and
311  // a step of (0,1) in (i,j) means a step of (-c,1-c) in (x,y), where
312  // c = (3-sqrt(3))/6
313 
314  double x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed coords
315  double y1 = y0 - j1 + G2;
316  double x2 = x0 + G22; // Offsets for last corner in (x,y) unskewed coords
317  double y2 = y0 + G22;
318 
319  // Work out the hashed gradient indices of the three simplex corners
320  int ii = i & 255;
321  int jj = j & 255;
322  int gi0 = perm[ii + perm[jj]] % 12;
323  int gi1 = perm[ii + i1 + perm[jj + j1]] % 12;
324  int gi2 = perm[ii + 1 + perm[jj + 1]] % 12;
325 
326  // Calculate the contribution from the three corners
327  double t0 = 0.5 - x0 * x0 - y0 * y0;
328  if (t0 < 0) {
329  n0 = 0.0;
330  } else {
331  t0 *= t0;
332  n0 = t0 * t0 * dot(grad3[gi0], x0, y0); // (x,y) of grad3 used for 2D gradient
333  }
334 
335  double t1 = 0.5 - x1 * x1 - y1 * y1;
336  if (t1 < 0) {
337  n1 = 0.0;
338  } else {
339  t1 *= t1;
340  n1 = t1 * t1 * dot(grad3[gi1], x1, y1);
341  }
342 
343  double t2 = 0.5 - x2 * x2 - y2 * y2;
344  if (t2 < 0) {
345  n2 = 0.0;
346  } else {
347  t2 *= t2;
348  n2 = t2 * t2 * dot(grad3[gi2], x2, y2);
349  }
350 
351  // Add contributions from each corner to get the final noise value.
352  // The result is scaled to return values in the interval [-1,1].
353  return 70.0 * (n0 + n1 + n2);
354  }
355 
356  /**
357  * Computes and returns the 4D simplex noise for the given coordinates in
358  * 4D space
359  *
360  * @param x X coordinate
361  * @param y Y coordinate
362  * @param z Z coordinate
363  * @param w W coordinate
364  * @return Noise at given location, from range -1 to 1
365  */
366  public double noise(double x, double y, double z, double w) {
367  x += offsetX;
368  y += offsetY;
369  z += offsetZ;
370  w += offsetW;
371 
372  double n0, n1, n2, n3, n4; // Noise contributions from the five corners
373 
374  // Skew the (x,y,z,w) space to determine which cell of 24 simplices we're in
375  double s = (x + y + z + w) * F4; // Factor for 4D skewing
376  int i = floor(x + s);
377  int j = floor(y + s);
378  int k = floor(z + s);
379  int l = floor(w + s);
380 
381  double t = (i + j + k + l) * G4; // Factor for 4D unskewing
382  double X0 = i - t; // Unskew the cell origin back to (x,y,z,w) space
383  double Y0 = j - t;
384  double Z0 = k - t;
385  double W0 = l - t;
386  double x0 = x - X0; // The x,y,z,w distances from the cell origin
387  double y0 = y - Y0;
388  double z0 = z - Z0;
389  double w0 = w - W0;
390 
391  // For the 4D case, the simplex is a 4D shape I won't even try to describe.
392  // To find out which of the 24 possible simplices we're in, we need to
393  // determine the magnitude ordering of x0, y0, z0 and w0.
394  // The method below is a good way of finding the ordering of x,y,z,w and
395  // then find the correct traversal order for the simplex we’re in.
396  // First, six pair-wise comparisons are performed between each possible pair
397  // of the four coordinates, and the results are used to add up binary bits
398  // for an integer index.
399  int c1 = (x0 > y0) ? 32 : 0;
400  int c2 = (x0 > z0) ? 16 : 0;
401  int c3 = (y0 > z0) ? 8 : 0;
402  int c4 = (x0 > w0) ? 4 : 0;
403  int c5 = (y0 > w0) ? 2 : 0;
404  int c6 = (z0 > w0) ? 1 : 0;
405  int c = c1 + c2 + c3 + c4 + c5 + c6;
406  int i1, j1, k1, l1; // The integer offsets for the second simplex corner
407  int i2, j2, k2, l2; // The integer offsets for the third simplex corner
408  int i3, j3, k3, l3; // The integer offsets for the fourth simplex corner
409 
410  // simplex[c] is a 4-vector with the numbers 0, 1, 2 and 3 in some order.
411  // Many values of c will never occur, since e.g. x>y>z>w makes x<z, y<w and x<w
412  // impossible. Only the 24 indices which have non-zero entries make any sense.
413  // We use a thresholding to set the coordinates in turn from the largest magnitude.
414 
415  // The number 3 in the "simplex" array is at the position of the largest coordinate.
416  i1 = simplex[c][0] >= 3 ? 1 : 0;
417  j1 = simplex[c][1] >= 3 ? 1 : 0;
418  k1 = simplex[c][2] >= 3 ? 1 : 0;
419  l1 = simplex[c][3] >= 3 ? 1 : 0;
420 
421  // The number 2 in the "simplex" array is at the second largest coordinate.
422  i2 = simplex[c][0] >= 2 ? 1 : 0;
423  j2 = simplex[c][1] >= 2 ? 1 : 0;
424  k2 = simplex[c][2] >= 2 ? 1 : 0;
425  l2 = simplex[c][3] >= 2 ? 1 : 0;
426 
427  // The number 1 in the "simplex" array is at the second smallest coordinate.
428  i3 = simplex[c][0] >= 1 ? 1 : 0;
429  j3 = simplex[c][1] >= 1 ? 1 : 0;
430  k3 = simplex[c][2] >= 1 ? 1 : 0;
431  l3 = simplex[c][3] >= 1 ? 1 : 0;
432 
433  // The fifth corner has all coordinate offsets = 1, so no need to look that up.
434 
435  double x1 = x0 - i1 + G4; // Offsets for second corner in (x,y,z,w) coords
436  double y1 = y0 - j1 + G4;
437  double z1 = z0 - k1 + G4;
438  double w1 = w0 - l1 + G4;
439 
440  double x2 = x0 - i2 + G42; // Offsets for third corner in (x,y,z,w) coords
441  double y2 = y0 - j2 + G42;
442  double z2 = z0 - k2 + G42;
443  double w2 = w0 - l2 + G42;
444 
445  double x3 = x0 - i3 + G43; // Offsets for fourth corner in (x,y,z,w) coords
446  double y3 = y0 - j3 + G43;
447  double z3 = z0 - k3 + G43;
448  double w3 = w0 - l3 + G43;
449 
450  double x4 = x0 + G44; // Offsets for last corner in (x,y,z,w) coords
451  double y4 = y0 + G44;
452  double z4 = z0 + G44;
453  double w4 = w0 + G44;
454 
455  // Work out the hashed gradient indices of the five simplex corners
456  int ii = i & 255;
457  int jj = j & 255;
458  int kk = k & 255;
459  int ll = l & 255;
460 
461  int gi0 = perm[ii + perm[jj + perm[kk + perm[ll]]]] % 32;
462  int gi1 = perm[ii + i1 + perm[jj + j1 + perm[kk + k1 + perm[ll + l1]]]] % 32;
463  int gi2 = perm[ii + i2 + perm[jj + j2 + perm[kk + k2 + perm[ll + l2]]]] % 32;
464  int gi3 = perm[ii + i3 + perm[jj + j3 + perm[kk + k3 + perm[ll + l3]]]] % 32;
465  int gi4 = perm[ii + 1 + perm[jj + 1 + perm[kk + 1 + perm[ll + 1]]]] % 32;
466 
467  // Calculate the contribution from the five corners
468  double t0 = 0.6 - x0 * x0 - y0 * y0 - z0 * z0 - w0 * w0;
469  if (t0 < 0) {
470  n0 = 0.0;
471  } else {
472  t0 *= t0;
473  n0 = t0 * t0 * dot(grad4[gi0], x0, y0, z0, w0);
474  }
475 
476  double t1 = 0.6 - x1 * x1 - y1 * y1 - z1 * z1 - w1 * w1;
477  if (t1 < 0) {
478  n1 = 0.0;
479  } else {
480  t1 *= t1;
481  n1 = t1 * t1 * dot(grad4[gi1], x1, y1, z1, w1);
482  }
483 
484  double t2 = 0.6 - x2 * x2 - y2 * y2 - z2 * z2 - w2 * w2;
485  if (t2 < 0) {
486  n2 = 0.0;
487  } else {
488  t2 *= t2;
489  n2 = t2 * t2 * dot(grad4[gi2], x2, y2, z2, w2);
490  }
491 
492  double t3 = 0.6 - x3 * x3 - y3 * y3 - z3 * z3 - w3 * w3;
493  if (t3 < 0) {
494  n3 = 0.0;
495  } else {
496  t3 *= t3;
497  n3 = t3 * t3 * dot(grad4[gi3], x3, y3, z3, w3);
498  }
499 
500  double t4 = 0.6 - x4 * x4 - y4 * y4 - z4 * z4 - w4 * w4;
501  if (t4 < 0) {
502  n4 = 0.0;
503  } else {
504  t4 *= t4;
505  n4 = t4 * t4 * dot(grad4[gi4], x4, y4, z4, w4);
506  }
507 
508  // Sum up and scale the result to cover the range [-1,1]
509  return 27.0 * (n0 + n1 + n2 + n3 + n4);
510  }
511 
512  /**
513  * Gets the singleton unseeded instance of this generator
514  *
515  * @return Singleton
516  */
518  return instance;
519  }
520 }
static double getNoise(double x, double y, double z, double w)
static double getNoise(double xin, double yin)
static double getNoise(double xin, double yin, double zin)
double noise(double x, double y, double z, double w)