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