X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fnoise.cpp;h=255d3faee001c5770f0c864434fb738bc5998720;hb=2b3490db1f0e99a427e34135770f8e5afcf275ce;hp=6362f5b2cf3863c8a670c200a8fc3456d3d52f48;hpb=7cfb71385d00d1cbbbfd9c76f6c01adafa9e648a;p=dragonfireclient.git diff --git a/src/noise.cpp b/src/noise.cpp index 6362f5b2c..255d3faee 100644 --- a/src/noise.cpp +++ b/src/noise.cpp @@ -1,328 +1,806 @@ /* -Minetest-c55 -Copyright (C) 2010-2011 celeron55, Perttu Ahola + * Minetest + * Copyright (C) 2010-2014 celeron55, Perttu Ahola + * Copyright (C) 2010-2014 kwolekr, Ryan Kwolek + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without modification, are + * permitted provided that the following conditions are met: + * 1. Redistributions of source code must retain the above copyright notice, this list of + * conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright notice, this list + * of conditions and the following disclaimer in the documentation and/or other materials + * provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR IMPLIED + * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND + * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON + * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ -This program is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. - -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License along -with this program; if not, write to the Free Software Foundation, Inc., -51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. -*/ - -#include +#include #include "noise.h" #include +#include // memset #include "debug.h" +#include "util/numeric.h" +#include "util/string.h" +#include "exceptions.h" -#define NOISE_MAGIC_X 1619 -#define NOISE_MAGIC_Y 31337 -#define NOISE_MAGIC_Z 52591 +#define NOISE_MAGIC_X 1619 +#define NOISE_MAGIC_Y 31337 +#define NOISE_MAGIC_Z 52591 #define NOISE_MAGIC_SEED 1013 -double cos_lookup[16] = { - 1.0,0.9238,0.7071,0.3826,0,-0.3826,-0.7071,-0.9238, - 1.0,-0.9238,-0.7071,-0.3826,0,0.3826,0.7071,0.9238 +typedef float (*Interp2dFxn)( + float v00, float v10, float v01, float v11, + float x, float y); + +typedef float (*Interp3dFxn)( + float v000, float v100, float v010, float v110, + float v001, float v101, float v011, float v111, + float x, float y, float z); + +float cos_lookup[16] = { + 1.0f, 0.9238f, 0.7071f, 0.3826f, .0f, -0.3826f, -0.7071f, -0.9238f, + 1.0f, -0.9238f, -0.7071f, -0.3826f, .0f, 0.3826f, 0.7071f, 0.9238f +}; + +FlagDesc flagdesc_noiseparams[] = { + {"defaults", NOISE_FLAG_DEFAULTS}, + {"eased", NOISE_FLAG_EASED}, + {"absvalue", NOISE_FLAG_ABSVALUE}, + {"pointbuffer", NOISE_FLAG_POINTBUFFER}, + {"simplex", NOISE_FLAG_SIMPLEX}, + {NULL, 0} }; -double dotProduct(double vx, double vy, double wx, double wy){ - return vx*wx+vy*wy; -} - -double easeCurve(double t){ - return 6*pow(t,5)-15*pow(t,4)+10*pow(t,3); -} - -double linearInterpolation(double x0, double x1, double t){ - return x0+(x1-x0)*t; -} - -double biLinearInterpolation(double x0y0, double x1y0, double x0y1, double x1y1, double x, double y){ - double tx = easeCurve(x); - double ty = easeCurve(y); - /*double tx = x; - double ty = y;*/ - double u = linearInterpolation(x0y0,x1y0,tx); - double v = linearInterpolation(x0y1,x1y1,tx); - return linearInterpolation(u,v,ty); -} - -double triLinearInterpolation( - double v000, double v100, double v010, double v110, - double v001, double v101, double v011, double v111, - double x, double y, double z) -{ - /*double tx = easeCurve(x); - double ty = easeCurve(y); - double tz = easeCurve(z);*/ - double tx = x; - double ty = y; - double tz = z; - return( - v000*(1-tx)*(1-ty)*(1-tz) + - v100*tx*(1-ty)*(1-tz) + - v010*(1-tx)*ty*(1-tz) + - v110*tx*ty*(1-tz) + - v001*(1-tx)*(1-ty)*tz + - v101*tx*(1-ty)*tz + - v011*(1-tx)*ty*tz + - v111*tx*ty*tz - ); -} - -double noise2d(int x, int y, int seed) -{ - int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y +/////////////////////////////////////////////////////////////////////////////// + +PcgRandom::PcgRandom(u64 state, u64 seq) +{ + seed(state, seq); +} + +void PcgRandom::seed(u64 state, u64 seq) +{ + m_state = 0U; + m_inc = (seq << 1u) | 1u; + next(); + m_state += state; + next(); +} + + +u32 PcgRandom::next() +{ + u64 oldstate = m_state; + m_state = oldstate * 6364136223846793005ULL + m_inc; + + u32 xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u; + u32 rot = oldstate >> 59u; + return (xorshifted >> rot) | (xorshifted << ((-rot) & 31)); +} + + +u32 PcgRandom::range(u32 bound) +{ + // If the bound is 0, we cover the whole RNG's range + if (bound == 0) + return next(); + + /* + This is an optimization of the expression: + 0x100000000ull % bound + since 64-bit modulo operations typically much slower than 32. + */ + u32 threshold = -bound % bound; + u32 r; + + /* + If the bound is not a multiple of the RNG's range, it may cause bias, + e.g. a RNG has a range from 0 to 3 and we take want a number 0 to 2. + Using rand() % 3, the number 0 would be twice as likely to appear. + With a very large RNG range, the effect becomes less prevalent but + still present. + + This can be solved by modifying the range of the RNG to become a + multiple of bound by dropping values above the a threshold. + + In our example, threshold == 4 % 3 == 1, so reject values < 1 + (that is, 0), thus making the range == 3 with no bias. + + This loop may look dangerous, but will always terminate due to the + RNG's property of uniformity. + */ + while ((r = next()) < threshold) + ; + + return r % bound; +} + + +s32 PcgRandom::range(s32 min, s32 max) +{ + if (max < min) + throw PrngException("Invalid range (max < min)"); + + // We have to cast to s64 because otherwise this could overflow, + // and signed overflow is undefined behavior. + u32 bound = (s64)max - (s64)min + 1; + return range(bound) + min; +} + + +void PcgRandom::bytes(void *out, size_t len) +{ + u8 *outb = (u8 *)out; + int bytes_left = 0; + u32 r; + + while (len--) { + if (bytes_left == 0) { + bytes_left = sizeof(u32); + r = next(); + } + + *outb = r & 0xFF; + outb++; + bytes_left--; + r >>= CHAR_BIT; + } +} + + +s32 PcgRandom::randNormalDist(s32 min, s32 max, int num_trials) +{ + s32 accum = 0; + for (int i = 0; i != num_trials; i++) + accum += range(min, max); + return myround((float)accum / num_trials); +} + +/////////////////////////////////////////////////////////////////////////////// + +float noise2d(int x, int y, s32 seed) +{ + unsigned int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y + NOISE_MAGIC_SEED * seed) & 0x7fffffff; - n = (n>>13)^n; - n = (n * (n*n*60493+19990303) + 1376312589) & 0x7fffffff; - return 1.0 - (double)n/1073741824; + n = (n >> 13) ^ n; + n = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff; + return 1.f - (float)(int)n / 0x40000000; } -double noise3d(int x, int y, int z, int seed) + +float noise3d(int x, int y, int z, s32 seed) { - int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y + NOISE_MAGIC_Z * z + unsigned int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y + NOISE_MAGIC_Z * z + NOISE_MAGIC_SEED * seed) & 0x7fffffff; - n = (n>>13)^n; - n = (n * (n*n*60493+19990303) + 1376312589) & 0x7fffffff; - return 1.0 - (double)n/1073741824; + n = (n >> 13) ^ n; + n = (n * (n * n * 60493 + 19990303) + 1376312589) & 0x7fffffff; + return 1.f - (float)(int)n / 0x40000000; } -#if 0 -double noise2d_gradient(double x, double y, int seed) + +inline float dotProduct(float vx, float vy, float wx, float wy) { - // Calculate the integer coordinates - int x0 = (x > 0.0 ? (int)x : (int)x - 1); - int y0 = (y > 0.0 ? (int)y : (int)y - 1); - // Calculate the remaining part of the coordinates - double xl = x - (double)x0; - double yl = y - (double)y0; - // Calculate random cosine lookup table indices for the integer corners. - // They are looked up as unit vector gradients from the lookup table. - int n00 = (int)((noise2d(x0, y0, seed)+1)*8); - int n10 = (int)((noise2d(x0+1, y0, seed)+1)*8); - int n01 = (int)((noise2d(x0, y0+1, seed)+1)*8); - int n11 = (int)((noise2d(x0+1, y0+1, seed)+1)*8); - // Make a dot product for the gradients and the positions, to get the values - double s = dotProduct(cos_lookup[n00], cos_lookup[(n00+12)%16], xl, yl); - double u = dotProduct(-cos_lookup[n10], cos_lookup[(n10+12)%16], 1.-xl, yl); - double v = dotProduct(cos_lookup[n01], -cos_lookup[(n01+12)%16], xl, 1.-yl); - double w = dotProduct(-cos_lookup[n11], -cos_lookup[(n11+12)%16], 1.-xl, 1.-yl); - // Interpolate between the values - return biLinearInterpolation(s,u,v,w,xl,yl); -} -#endif - -#if 1 -double noise2d_gradient(double x, double y, int seed) + return vx * wx + vy * wy; +} + + +inline float linearInterpolation(float v0, float v1, float t) +{ + return v0 + (v1 - v0) * t; +} + + +inline float biLinearInterpolation( + float v00, float v10, + float v01, float v11, + float x, float y) +{ + float tx = easeCurve(x); + float ty = easeCurve(y); + float u = linearInterpolation(v00, v10, tx); + float v = linearInterpolation(v01, v11, tx); + return linearInterpolation(u, v, ty); +} + + +inline float biLinearInterpolationNoEase( + float v00, float v10, + float v01, float v11, + float x, float y) +{ + float u = linearInterpolation(v00, v10, x); + float v = linearInterpolation(v01, v11, x); + return linearInterpolation(u, v, y); +} + + +float triLinearInterpolation( + float v000, float v100, float v010, float v110, + float v001, float v101, float v011, float v111, + float x, float y, float z) +{ + float tx = easeCurve(x); + float ty = easeCurve(y); + float tz = easeCurve(z); + float u = biLinearInterpolationNoEase(v000, v100, v010, v110, tx, ty); + float v = biLinearInterpolationNoEase(v001, v101, v011, v111, tx, ty); + return linearInterpolation(u, v, tz); +} + +float triLinearInterpolationNoEase( + float v000, float v100, float v010, float v110, + float v001, float v101, float v011, float v111, + float x, float y, float z) +{ + float u = biLinearInterpolationNoEase(v000, v100, v010, v110, x, y); + float v = biLinearInterpolationNoEase(v001, v101, v011, v111, x, y); + return linearInterpolation(u, v, z); +} + +float noise2d_gradient(float x, float y, s32 seed, bool eased) { // Calculate the integer coordinates - int x0 = (x > 0.0 ? (int)x : (int)x - 1); - int y0 = (y > 0.0 ? (int)y : (int)y - 1); + int x0 = myfloor(x); + int y0 = myfloor(y); // Calculate the remaining part of the coordinates - double xl = x - (double)x0; - double yl = y - (double)y0; - // Get values for corners of cube - double v00 = noise2d(x0, y0, seed); - double v10 = noise2d(x0+1, y0, seed); - double v01 = noise2d(x0, y0+1, seed); - double v11 = noise2d(x0+1, y0+1, seed); + float xl = x - (float)x0; + float yl = y - (float)y0; + // Get values for corners of square + float v00 = noise2d(x0, y0, seed); + float v10 = noise2d(x0+1, y0, seed); + float v01 = noise2d(x0, y0+1, seed); + float v11 = noise2d(x0+1, y0+1, seed); // Interpolate - return biLinearInterpolation(v00,v10,v01,v11,xl,yl); + if (eased) + return biLinearInterpolation(v00, v10, v01, v11, xl, yl); + + return biLinearInterpolationNoEase(v00, v10, v01, v11, xl, yl); } -#endif -double noise3d_gradient(double x, double y, double z, int seed) + +float noise3d_gradient(float x, float y, float z, s32 seed, bool eased) { // Calculate the integer coordinates - int x0 = (x > 0.0 ? (int)x : (int)x - 1); - int y0 = (y > 0.0 ? (int)y : (int)y - 1); - int z0 = (z > 0.0 ? (int)z : (int)z - 1); + int x0 = myfloor(x); + int y0 = myfloor(y); + int z0 = myfloor(z); // Calculate the remaining part of the coordinates - double xl = x - (double)x0; - double yl = y - (double)y0; - double zl = z - (double)z0; + float xl = x - (float)x0; + float yl = y - (float)y0; + float zl = z - (float)z0; // Get values for corners of cube - double v000 = noise3d(x0, y0, z0, seed); - double v100 = noise3d(x0+1, y0, z0, seed); - double v010 = noise3d(x0, y0+1, z0, seed); - double v110 = noise3d(x0+1, y0+1, z0, seed); - double v001 = noise3d(x0, y0, z0+1, seed); - double v101 = noise3d(x0+1, y0, z0+1, seed); - double v011 = noise3d(x0, y0+1, z0+1, seed); - double v111 = noise3d(x0+1, y0+1, z0+1, seed); + float v000 = noise3d(x0, y0, z0, seed); + float v100 = noise3d(x0 + 1, y0, z0, seed); + float v010 = noise3d(x0, y0 + 1, z0, seed); + float v110 = noise3d(x0 + 1, y0 + 1, z0, seed); + float v001 = noise3d(x0, y0, z0 + 1, seed); + float v101 = noise3d(x0 + 1, y0, z0 + 1, seed); + float v011 = noise3d(x0, y0 + 1, z0 + 1, seed); + float v111 = noise3d(x0 + 1, y0 + 1, z0 + 1, seed); // Interpolate - return triLinearInterpolation(v000,v100,v010,v110,v001,v101,v011,v111,xl,yl,zl); + if (eased) { + return triLinearInterpolation( + v000, v100, v010, v110, + v001, v101, v011, v111, + xl, yl, zl); + } + + return triLinearInterpolationNoEase( + v000, v100, v010, v110, + v001, v101, v011, v111, + xl, yl, zl); } -double noise2d_perlin(double x, double y, int seed, - int octaves, double persistence) + +float noise2d_perlin(float x, float y, s32 seed, + int octaves, float persistence, bool eased) { - double a = 0; - double f = 1.0; - double g = 1.0; - for(int i=0; i= 1.0) + return 0.0; + return (1.0 - v); } -NoiseBuffer::~NoiseBuffer() + +///////////////////////// [ New noise ] //////////////////////////// + + +float NoisePerlin2D(NoiseParams *np, float x, float y, s32 seed) { - clear(); + float a = 0; + float f = 1.0; + float g = 1.0; + + x /= np->spread.X; + y /= np->spread.Y; + seed += np->seed; + + for (size_t i = 0; i < np->octaves; i++) { + float noiseval = noise2d_gradient(x * f, y * f, seed + i, + np->flags & (NOISE_FLAG_DEFAULTS | NOISE_FLAG_EASED)); + + if (np->flags & NOISE_FLAG_ABSVALUE) + noiseval = std::fabs(noiseval); + + a += g * noiseval; + f *= np->lacunarity; + g *= np->persist; + } + + return np->offset + a * np->scale; } -void NoiseBuffer::clear() + +float NoisePerlin3D(NoiseParams *np, float x, float y, float z, s32 seed) { - if(m_data) - delete[] m_data; - m_data = NULL; - m_size_x = 0; - m_size_y = 0; - m_size_z = 0; + float a = 0; + float f = 1.0; + float g = 1.0; + + x /= np->spread.X; + y /= np->spread.Y; + z /= np->spread.Z; + seed += np->seed; + + for (size_t i = 0; i < np->octaves; i++) { + float noiseval = noise3d_gradient(x * f, y * f, z * f, seed + i, + np->flags & NOISE_FLAG_EASED); + + if (np->flags & NOISE_FLAG_ABSVALUE) + noiseval = std::fabs(noiseval); + + a += g * noiseval; + f *= np->lacunarity; + g *= np->persist; + } + + return np->offset + a * np->scale; } -void NoiseBuffer::create(int seed, int octaves, double persistence, - double pos_scale, - double first_x, double first_y, double first_z, - double last_x, double last_y, double last_z, - double samplelength_x, double samplelength_y, double samplelength_z) + +Noise::Noise(NoiseParams *np_, s32 seed, u32 sx, u32 sy, u32 sz) { - clear(); - - m_start_x = first_x - samplelength_x; - m_start_y = first_y - samplelength_y; - m_start_z = first_z - samplelength_z; - m_samplelength_x = samplelength_x; - m_samplelength_y = samplelength_y; - m_samplelength_z = samplelength_z; + memcpy(&np, np_, sizeof(np)); + this->seed = seed; + this->sx = sx; + this->sy = sy; + this->sz = sz; - m_size_x = (last_x - m_start_x)/samplelength_x + 2; - m_size_y = (last_y - m_start_y)/samplelength_y + 2; - m_size_z = (last_z - m_start_z)/samplelength_z + 2; + allocBuffers(); +} - /*dstream<<"m_size_x="<