]> git.lizzy.rs Git - minetest.git/blob - src/noise.cpp
refactor main.cpp
[minetest.git] / src / noise.cpp
1 /*
2  * Minetest
3  * Copyright (C) 2010-2014 celeron55, Perttu Ahola <celeron55@gmail.com>
4  * Copyright (C) 2010-2014 kwolekr, Ryan Kwolek <kwolekr@minetest.net>
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without modification, are
8  * permitted provided that the following conditions are met:
9  *  1. Redistributions of source code must retain the above copyright notice, this list of
10  *     conditions and the following disclaimer.
11  *  2. Redistributions in binary form must reproduce the above copyright notice, this list
12  *     of conditions and the following disclaimer in the documentation and/or other materials
13  *     provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED
16  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
17  * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
20  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
21  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
22  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
23  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include <math.h>
27 #include "noise.h"
28 #include <iostream>
29 #include <string.h> // memset
30 #include "debug.h"
31 #include "util/numeric.h"
32
33 #define NOISE_MAGIC_X    1619
34 #define NOISE_MAGIC_Y    31337
35 #define NOISE_MAGIC_Z    52591
36 #define NOISE_MAGIC_SEED 1013
37
38 typedef float (*Interp3dFxn)(
39                 float v000, float v100, float v010, float v110,
40                 float v001, float v101, float v011, float v111,
41                 float x, float y, float z);
42
43 float cos_lookup[16] = {
44         1.0,  0.9238,  0.7071,  0.3826, 0, -0.3826, -0.7071, -0.9238,
45         1.0, -0.9238, -0.7071, -0.3826, 0,  0.3826,  0.7071,  0.9238
46 };
47
48
49 ///////////////////////////////////////////////////////////////////////////////
50
51
52 //noise poly:  p(n) = 60493n^3 + 19990303n + 137612589
53 float noise2d(int x, int y, int seed)
54 {
55         int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y
56                         + NOISE_MAGIC_SEED * seed) & 0x7fffffff;
57         n = (n >> 13) ^ n;
58         n = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff;
59         return 1.f - (float)n / 0x40000000;
60 }
61
62
63 float noise3d(int x, int y, int z, int seed)
64 {
65         int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y + NOISE_MAGIC_Z * z
66                         + NOISE_MAGIC_SEED * seed) & 0x7fffffff;
67         n = (n >> 13) ^ n;
68         n = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff;
69         return 1.f - (float)n / 0x40000000;
70 }
71
72
73 float dotProduct(float vx, float vy, float wx, float wy)
74 {
75         return vx * wx + vy * wy;
76 }
77
78
79 inline float linearInterpolation(float v0, float v1, float t)
80 {
81     return v0 + (v1 - v0) * t;
82 }
83
84
85 float biLinearInterpolation(
86                 float v00, float v10,
87                 float v01, float v11,
88                 float x, float y)
89 {
90     float tx = easeCurve(x);
91     float ty = easeCurve(y);
92     float u = linearInterpolation(v00, v10, tx);
93     float v = linearInterpolation(v01, v11, tx);
94     return linearInterpolation(u, v, ty);
95 }
96
97
98 float biLinearInterpolationNoEase(
99                 float x0y0, float x1y0,
100                 float x0y1, float x1y1,
101                 float x, float y)
102 {
103     float u = linearInterpolation(x0y0, x1y0, x);
104     float v = linearInterpolation(x0y1, x1y1, x);
105     return linearInterpolation(u, v, y);
106 }
107
108 /*
109 float triLinearInterpolation(
110                 float v000, float v100, float v010, float v110,
111                 float v001, float v101, float v011, float v111,
112                 float x, float y, float z)
113 {
114         float u = biLinearInterpolation(v000, v100, v010, v110, x, y);
115         float v = biLinearInterpolation(v001, v101, v011, v111, x, y);
116         return linearInterpolation(u, v, z);
117 }
118
119
120 float triLinearInterpolationNoEase(
121                 float v000, float v100, float v010, float v110,
122                 float v001, float v101, float v011, float v111,
123                 float x, float y, float z)
124 {
125         float u = biLinearInterpolationNoEase(v000, v100, v010, v110, x, y);
126         float v = biLinearInterpolationNoEase(v001, v101, v011, v111, x, y);
127         return linearInterpolation(u, v, z);
128 }
129 */
130
131
132 float triLinearInterpolation(
133                 float v000, float v100, float v010, float v110,
134                 float v001, float v101, float v011, float v111,
135                 float x, float y, float z)
136 {
137         float tx = easeCurve(x);
138         float ty = easeCurve(y);
139         float tz = easeCurve(z);
140
141         return (
142                 v000 * (1 - tx) * (1 - ty) * (1 - tz) +
143                 v100 * tx * (1 - ty) * (1 - tz) +
144                 v010 * (1 - tx) * ty * (1 - tz) +
145                 v110 * tx * ty * (1 - tz) +
146                 v001 * (1 - tx) * (1 - ty) * tz +
147                 v101 * tx * (1 - ty) * tz +
148                 v011 * (1 - tx) * ty * tz +
149                 v111 * tx * ty * tz
150         );
151 }
152
153 float triLinearInterpolationNoEase(
154                 float v000, float v100, float v010, float v110,
155                 float v001, float v101, float v011, float v111,
156                 float x, float y, float z)
157 {
158         float tx = x;
159         float ty = y;
160         float tz = z;
161         return (
162                 v000 * (1 - tx) * (1 - ty) * (1 - tz) +
163                 v100 * tx * (1 - ty) * (1 - tz) +
164                 v010 * (1 - tx) * ty * (1 - tz) +
165                 v110 * tx * ty * (1 - tz) +
166                 v001 * (1 - tx) * (1 - ty) * tz +
167                 v101 * tx * (1 - ty) * tz +
168                 v011 * (1 - tx) * ty * tz +
169                 v111 * tx * ty * tz
170         );
171 }
172
173
174 #if 0
175 float noise2d_gradient(float x, float y, int seed)
176 {
177         // Calculate the integer coordinates
178         int x0 = (x > 0.0 ? (int)x : (int)x - 1);
179         int y0 = (y > 0.0 ? (int)y : (int)y - 1);
180         // Calculate the remaining part of the coordinates
181         float xl = x - (float)x0;
182         float yl = y - (float)y0;
183         // Calculate random cosine lookup table indices for the integer corners.
184         // They are looked up as unit vector gradients from the lookup table.
185         int n00 = (int)((noise2d(x0, y0, seed)+1)*8);
186         int n10 = (int)((noise2d(x0+1, y0, seed)+1)*8);
187         int n01 = (int)((noise2d(x0, y0+1, seed)+1)*8);
188         int n11 = (int)((noise2d(x0+1, y0+1, seed)+1)*8);
189         // Make a dot product for the gradients and the positions, to get the values
190         float s = dotProduct(cos_lookup[n00], cos_lookup[(n00+12)%16], xl, yl);
191         float u = dotProduct(-cos_lookup[n10], cos_lookup[(n10+12)%16], 1.-xl, yl);
192         float v = dotProduct(cos_lookup[n01], -cos_lookup[(n01+12)%16], xl, 1.-yl);
193         float w = dotProduct(-cos_lookup[n11], -cos_lookup[(n11+12)%16], 1.-xl, 1.-yl);
194         // Interpolate between the values
195         return biLinearInterpolation(s,u,v,w,xl,yl);
196 }
197 #endif
198
199
200 float noise2d_gradient(float x, float y, int seed)
201 {
202         // Calculate the integer coordinates
203         int x0 = myfloor(x);
204         int y0 = myfloor(y);
205         // Calculate the remaining part of the coordinates
206         float xl = x - (float)x0;
207         float yl = y - (float)y0;
208         // Get values for corners of square
209         float v00 = noise2d(x0, y0, seed);
210         float v10 = noise2d(x0+1, y0, seed);
211         float v01 = noise2d(x0, y0+1, seed);
212         float v11 = noise2d(x0+1, y0+1, seed);
213         // Interpolate
214         return biLinearInterpolation(v00, v10, v01, v11, xl, yl);
215 }
216
217
218 float noise3d_gradient(float x, float y, float z, int seed, bool eased)
219 {
220         // Calculate the integer coordinates
221         int x0 = myfloor(x);
222         int y0 = myfloor(y);
223         int z0 = myfloor(z);
224         // Calculate the remaining part of the coordinates
225         float xl = x - (float)x0;
226         float yl = y - (float)y0;
227         float zl = z - (float)z0;
228         // Get values for corners of cube
229         float v000 = noise3d(x0,     y0,     z0,     seed);
230         float v100 = noise3d(x0 + 1, y0,     z0,     seed);
231         float v010 = noise3d(x0,     y0 + 1, z0,     seed);
232         float v110 = noise3d(x0 + 1, y0 + 1, z0,     seed);
233         float v001 = noise3d(x0,     y0,     z0 + 1, seed);
234         float v101 = noise3d(x0 + 1, y0,     z0 + 1, seed);
235         float v011 = noise3d(x0,     y0 + 1, z0 + 1, seed);
236         float v111 = noise3d(x0 + 1, y0 + 1, z0 + 1, seed);
237         // Interpolate
238         if (eased) {
239                 return triLinearInterpolation(
240                         v000, v100, v010, v110,
241                         v001, v101, v011, v111,
242                         xl, yl, zl);
243         } else {
244                 return triLinearInterpolationNoEase(
245                         v000, v100, v010, v110,
246                         v001, v101, v011, v111,
247                         xl, yl, zl);
248         }
249 }
250
251
252 float noise2d_perlin(float x, float y, int seed,
253                 int octaves, float persistence)
254 {
255         float a = 0;
256         float f = 1.0;
257         float g = 1.0;
258         for (int i = 0; i < octaves; i++)
259         {
260                 a += g * noise2d_gradient(x * f, y * f, seed + i);
261                 f *= 2.0;
262                 g *= persistence;
263         }
264         return a;
265 }
266
267
268 float noise2d_perlin_abs(float x, float y, int seed,
269                 int octaves, float persistence)
270 {
271         float a = 0;
272         float f = 1.0;
273         float g = 1.0;
274         for (int i = 0; i < octaves; i++)
275         {
276                 a += g * fabs(noise2d_gradient(x * f, y * f, seed + i));
277                 f *= 2.0;
278                 g *= persistence;
279         }
280         return a;
281 }
282
283
284 float noise3d_perlin(float x, float y, float z, int seed,
285                 int octaves, float persistence, bool eased)
286 {
287         float a = 0;
288         float f = 1.0;
289         float g = 1.0;
290         for (int i = 0; i < octaves; i++)
291         {
292                 a += g * noise3d_gradient(x * f, y * f, z * f, seed + i, eased);
293                 f *= 2.0;
294                 g *= persistence;
295         }
296         return a;
297 }
298
299
300 float noise3d_perlin_abs(float x, float y, float z, int seed,
301                 int octaves, float persistence, bool eased)
302 {
303         float a = 0;
304         float f = 1.0;
305         float g = 1.0;
306         for (int i = 0; i < octaves; i++)
307         {
308                 a += g * fabs(noise3d_gradient(x * f, y * f, z * f, seed + i, eased));
309                 f *= 2.0;
310                 g *= persistence;
311         }
312         return a;
313 }
314
315
316 float contour(float v)
317 {
318         v = fabs(v);
319         if(v >= 1.0)
320                 return 0.0;
321         return (1.0 - v);
322 }
323
324
325 ///////////////////////// [ New perlin stuff ] ////////////////////////////
326
327
328 Noise::Noise(NoiseParams *np, int seed, int sx, int sy, int sz)
329 {
330         this->np   = np;
331         this->seed = seed;
332         this->sx   = sx;
333         this->sy   = sy;
334         this->sz   = sz;
335
336         this->noisebuf = NULL;
337         resizeNoiseBuf(sz > 1);
338
339         this->buf    = new float[sx * sy * sz];
340         this->result = new float[sx * sy * sz];
341 }
342
343
344 Noise::~Noise()
345 {
346         delete[] buf;
347         delete[] result;
348         delete[] noisebuf;
349 }
350
351
352 void Noise::setSize(int sx, int sy, int sz)
353 {
354         this->sx = sx;
355         this->sy = sy;
356         this->sz = sz;
357
358         this->noisebuf = NULL;
359         resizeNoiseBuf(sz > 1);
360
361         delete[] buf;
362         delete[] result;
363         this->buf    = new float[sx * sy * sz];
364         this->result = new float[sx * sy * sz];
365 }
366
367
368 void Noise::setSpreadFactor(v3f spread)
369 {
370         this->np->spread = spread;
371
372         resizeNoiseBuf(sz > 1);
373 }
374
375
376 void Noise::setOctaves(int octaves)
377 {
378         this->np->octaves = octaves;
379
380         resizeNoiseBuf(sz > 1);
381 }
382
383
384 void Noise::resizeNoiseBuf(bool is3d)
385 {
386         int nlx, nly, nlz;
387         float ofactor;
388
389         //maximum possible spread value factor
390         ofactor = (float)(1 << (np->octaves - 1));
391
392         //noise lattice point count
393         //(int)(sz * spread * ofactor) is # of lattice points crossed due to length
394         // + 2 for the two initial endpoints
395         // + 1 for potentially crossing a boundary due to offset
396         nlx = (int)(sx * ofactor / np->spread.X) + 3;
397         nly = (int)(sy * ofactor / np->spread.Y) + 3;
398         nlz = is3d ? (int)(sz * ofactor / np->spread.Z) + 3 : 1;
399
400         if (noisebuf)
401                 delete[] noisebuf;
402         noisebuf = new float[nlx * nly * nlz];
403 }
404
405
406 /*
407  * NB:  This algorithm is not optimal in terms of space complexity.  The entire
408  * integer lattice of noise points could be done as 2 lines instead, and for 3D,
409  * 2 lines + 2 planes.
410  * However, this would require the noise calls to be interposed with the
411  * interpolation loops, which may trash the icache, leading to lower overall
412  * performance.
413  * Another optimization that could save half as many noise calls is to carry over
414  * values from the previous noise lattice as midpoints in the new lattice for the
415  * next octave.
416  */
417 #define idx(x, y) ((y) * nlx + (x))
418 void Noise::gradientMap2D(
419                 float x, float y,
420                 float step_x, float step_y,
421                 int seed)
422 {
423         float v00, v01, v10, v11, u, v, orig_u;
424         int index, i, j, x0, y0, noisex, noisey;
425         int nlx, nly;
426
427         x0 = floor(x);
428         y0 = floor(y);
429         u = x - (float)x0;
430         v = y - (float)y0;
431         orig_u = u;
432
433         //calculate noise point lattice
434         nlx = (int)(u + sx * step_x) + 2;
435         nly = (int)(v + sy * step_y) + 2;
436         index = 0;
437         for (j = 0; j != nly; j++)
438                 for (i = 0; i != nlx; i++)
439                         noisebuf[index++] = noise2d(x0 + i, y0 + j, seed);
440
441         //calculate interpolations
442         index  = 0;
443         noisey = 0;
444         for (j = 0; j != sy; j++) {
445                 v00 = noisebuf[idx(0, noisey)];
446                 v10 = noisebuf[idx(1, noisey)];
447                 v01 = noisebuf[idx(0, noisey + 1)];
448                 v11 = noisebuf[idx(1, noisey + 1)];
449
450                 u = orig_u;
451                 noisex = 0;
452                 for (i = 0; i != sx; i++) {
453                         buf[index++] = biLinearInterpolation(v00, v10, v01, v11, u, v);
454                         u += step_x;
455                         if (u >= 1.0) {
456                                 u -= 1.0;
457                                 noisex++;
458                                 v00 = v10;
459                                 v01 = v11;
460                                 v10 = noisebuf[idx(noisex + 1, noisey)];
461                                 v11 = noisebuf[idx(noisex + 1, noisey + 1)];
462                         }
463                 }
464
465                 v += step_y;
466                 if (v >= 1.0) {
467                         v -= 1.0;
468                         noisey++;
469                 }
470         }
471 }
472 #undef idx
473
474
475 #define idx(x, y, z) ((z) * nly * nlx + (y) * nlx + (x))
476 void Noise::gradientMap3D(
477                 float x, float y, float z,
478                 float step_x, float step_y, float step_z,
479                 int seed, bool eased)
480 {
481         float v000, v010, v100, v110;
482         float v001, v011, v101, v111;
483         float u, v, w, orig_u, orig_v;
484         int index, i, j, k, x0, y0, z0, noisex, noisey, noisez;
485         int nlx, nly, nlz;
486
487         Interp3dFxn interpolate = eased ?
488                 triLinearInterpolation : triLinearInterpolationNoEase;
489
490         x0 = floor(x);
491         y0 = floor(y);
492         z0 = floor(z);
493         u = x - (float)x0;
494         v = y - (float)y0;
495         w = z - (float)z0;
496         orig_u = u;
497         orig_v = v;
498
499         //calculate noise point lattice
500         nlx = (int)(u + sx * step_x) + 2;
501         nly = (int)(v + sy * step_y) + 2;
502         nlz = (int)(w + sz * step_z) + 2;
503         index = 0;
504         for (k = 0; k != nlz; k++)
505                 for (j = 0; j != nly; j++)
506                         for (i = 0; i != nlx; i++)
507                                 noisebuf[index++] = noise3d(x0 + i, y0 + j, z0 + k, seed);
508
509         //calculate interpolations
510         index  = 0;
511         noisey = 0;
512         noisez = 0;
513         for (k = 0; k != sz; k++) {
514                 v = orig_v;
515                 noisey = 0;
516                 for (j = 0; j != sy; j++) {
517                         v000 = noisebuf[idx(0, noisey,     noisez)];
518                         v100 = noisebuf[idx(1, noisey,     noisez)];
519                         v010 = noisebuf[idx(0, noisey + 1, noisez)];
520                         v110 = noisebuf[idx(1, noisey + 1, noisez)];
521                         v001 = noisebuf[idx(0, noisey,     noisez + 1)];
522                         v101 = noisebuf[idx(1, noisey,     noisez + 1)];
523                         v011 = noisebuf[idx(0, noisey + 1, noisez + 1)];
524                         v111 = noisebuf[idx(1, noisey + 1, noisez + 1)];
525
526                         u = orig_u;
527                         noisex = 0;
528                         for (i = 0; i != sx; i++) {
529                                 buf[index++] = interpolate(
530                                                                         v000, v100, v010, v110,
531                                                                         v001, v101, v011, v111,
532                                                                         u, v, w);
533
534                                 u += step_x;
535                                 if (u >= 1.0) {
536                                         u -= 1.0;
537                                         noisex++;
538                                         v000 = v100;
539                                         v010 = v110;
540                                         v100 = noisebuf[idx(noisex + 1, noisey,     noisez)];
541                                         v110 = noisebuf[idx(noisex + 1, noisey + 1, noisez)];
542                                         v001 = v101;
543                                         v011 = v111;
544                                         v101 = noisebuf[idx(noisex + 1, noisey,     noisez + 1)];
545                                         v111 = noisebuf[idx(noisex + 1, noisey + 1, noisez + 1)];
546                                 }
547                         }
548
549                         v += step_y;
550                         if (v >= 1.0) {
551                                 v -= 1.0;
552                                 noisey++;
553                         }
554                 }
555
556                 w += step_z;
557                 if (w >= 1.0) {
558                         w -= 1.0;
559                         noisez++;
560                 }
561         }
562 }
563 #undef idx
564
565
566 float *Noise::perlinMap2D(float x, float y)
567 {
568         float f = 1.0, g = 1.0;
569         size_t bufsize = sx * sy;
570
571         x /= np->spread.X;
572         y /= np->spread.Y;
573
574         memset(result, 0, sizeof(float) * bufsize);
575
576         for (int oct = 0; oct < np->octaves; oct++) {
577                 gradientMap2D(x * f, y * f,
578                         f / np->spread.X, f / np->spread.Y,
579                         seed + np->seed + oct);
580
581                 for (size_t i = 0; i != bufsize; i++)
582                         result[i] += g * buf[i];
583
584                 f *= 2.0;
585                 g *= np->persist;
586         }
587
588         return result;
589 }
590
591
592 float *Noise::perlinMap2DModulated(float x, float y, float *persist_map)
593 {
594         float f = 1.0;
595         size_t bufsize = sx * sy;
596
597         x /= np->spread.X;
598         y /= np->spread.Y;
599
600         memset(result, 0, sizeof(float) * bufsize);
601
602         float *g = new float[bufsize];
603         for (size_t i = 0; i != bufsize; i++)
604                 g[i] = 1.0;
605
606         for (int oct = 0; oct < np->octaves; oct++) {
607                 gradientMap2D(x * f, y * f,
608                         f / np->spread.X, f / np->spread.Y,
609                         seed + np->seed + oct);
610
611                 for (size_t i = 0; i != bufsize; i++) {
612                         result[i] += g[i] * buf[i];
613                         g[i] *= persist_map[i];
614                 }
615
616                 f *= 2.0;
617         }
618         
619         delete[] g;
620         return result;
621 }
622
623
624 float *Noise::perlinMap3D(float x, float y, float z, bool eased)
625 {
626         float f = 1.0, g = 1.0;
627         size_t bufsize = sx * sy * sz;
628
629         x /= np->spread.X;
630         y /= np->spread.Y;
631         z /= np->spread.Z;
632
633         memset(result, 0, sizeof(float) * bufsize);
634
635         for (int oct = 0; oct < np->octaves; oct++) {
636                 gradientMap3D(x * f, y * f, z * f,
637                         f / np->spread.X, f / np->spread.Y, f / np->spread.Z,
638                         seed + np->seed + oct, eased);
639
640                 for (size_t i = 0; i != bufsize; i++)
641                         result[i] += g * buf[i];
642
643                 f *= 2.0;
644                 g *= np->persist;
645         }
646
647         return result;
648 }
649
650
651 void Noise::transformNoiseMap()
652 {
653         size_t i = 0;
654
655         for (int z = 0; z != sz; z++)
656         for (int y = 0; y != sy; y++)
657         for (int x = 0; x != sx; x++) {
658                 result[i] = result[i] * np->scale + np->offset;
659                 i++;
660         }
661 }
662