X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fnoise.cpp;h=e16564b05f4da07ab0f14546d74d103eb5932318;hb=71287894adbf3cbe092ded1cbf02755678305afb;hp=4bfc46f15053fffc0d4a4c2edb0412120c79ef23;hpb=943c6e523e64dd879b7974b7adc35153095fd80e;p=dragonfireclient.git diff --git a/src/noise.cpp b/src/noise.cpp index 4bfc46f15..e16564b05 100644 --- a/src/noise.cpp +++ b/src/noise.cpp @@ -23,10 +23,10 @@ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ -#include +#include #include "noise.h" #include -#include // memset +#include // memset #include "debug.h" #include "util/numeric.h" #include "util/string.h" @@ -46,11 +46,6 @@ typedef float (*Interp3dFxn)( float v001, float v101, float v011, float v111, float x, float y, float z); -float 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 -}; - FlagDesc flagdesc_noiseparams[] = { {"defaults", NOISE_FLAG_DEFAULTS}, {"eased", NOISE_FLAG_EASED}, @@ -90,23 +85,35 @@ u32 PcgRandom::next() u32 PcgRandom::range(u32 bound) { + // If the bound is 0, we cover the whole RNG's range + if (bound == 0) + return next(); + /* - 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 threshhold. - In our example, threshhold == 4 - 3 = 1 % 3 == 1, so reject 0, thus - making the range 3 with no bias. - - This loop looks dangerous, but will always terminate due to the - RNG's property of uniformity. + This is an optimization of the expression: + 0x100000000ull % bound + since 64-bit modulo operations typically much slower than 32. */ - u32 threshhold = -bound % bound; + u32 threshold = -bound % bound; u32 r; - while ((r = next()) < threshhold) + /* + 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; @@ -115,8 +122,12 @@ u32 PcgRandom::range(u32 bound) s32 PcgRandom::range(s32 min, s32 max) { - assert(max >= min); - u32 bound = max - min + 1; + 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; } @@ -136,7 +147,7 @@ void PcgRandom::bytes(void *out, size_t len) *outb = r & 0xFF; outb++; bytes_left--; - r >>= 8; + r >>= CHAR_BIT; } } @@ -146,28 +157,28 @@ 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 ((float)accum / num_trials) + 0.5f; + return myround((float)accum / num_trials); } /////////////////////////////////////////////////////////////////////////////// -float noise2d(int x, int y, int seed) +float noise2d(int x, int y, s32 seed) { - int n = (NOISE_MAGIC_X * x + NOISE_MAGIC_Y * y + 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.f - (float)n / 0x40000000; + return 1.f - (float)(int)n / 0x40000000; } -float 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.f - (float)n / 0x40000000; + return 1.f - (float)(int)n / 0x40000000; } @@ -190,14 +201,6 @@ inline float biLinearInterpolation( { float tx = easeCurve(x); float ty = easeCurve(y); -#if 0 - return ( - v00 * (1 - tx) * (1 - ty) + - v10 * tx * (1 - ty) + - v01 * (1 - tx) * ty + - v11 * tx * ty - ); -#endif float u = linearInterpolation(v00, v10, tx); float v = linearInterpolation(v01, v11, tx); return linearInterpolation(u, v, ty); @@ -223,18 +226,6 @@ float triLinearInterpolation( float tx = easeCurve(x); float ty = easeCurve(y); float tz = easeCurve(z); -#if 0 - 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 - ); -#endif float u = biLinearInterpolationNoEase(v000, v100, v010, v110, tx, ty); float v = biLinearInterpolationNoEase(v001, v101, v011, v111, tx, ty); return linearInterpolation(u, v, tz); @@ -250,34 +241,7 @@ float triLinearInterpolationNoEase( return linearInterpolation(u, v, z); } - -#if 0 -float noise2d_gradient(float x, float y, int seed) -{ - // 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 - float xl = x - (float)x0; - float yl = y - (float)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 - float s = dotProduct(cos_lookup[n00], cos_lookup[(n00+12)%16], xl, yl); - float u = dotProduct(-cos_lookup[n10], cos_lookup[(n10+12)%16], 1.-xl, yl); - float v = dotProduct(cos_lookup[n01], -cos_lookup[(n01+12)%16], xl, 1.-yl); - float 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 - - -float noise2d_gradient(float x, float y, int seed, bool eased) +float noise2d_gradient(float x, float y, s32 seed, bool eased) { // Calculate the integer coordinates int x0 = myfloor(x); @@ -293,12 +257,12 @@ float noise2d_gradient(float x, float y, int seed, bool eased) // Interpolate if (eased) return biLinearInterpolation(v00, v10, v01, v11, xl, yl); - else - return biLinearInterpolationNoEase(v00, v10, v01, v11, xl, yl); + + return biLinearInterpolationNoEase(v00, v10, v01, v11, xl, yl); } -float noise3d_gradient(float x, float y, float z, int seed, bool eased) +float noise3d_gradient(float x, float y, float z, s32 seed, bool eased) { // Calculate the integer coordinates int x0 = myfloor(x); @@ -323,16 +287,16 @@ float noise3d_gradient(float x, float y, float z, int seed, bool eased) v000, v100, v010, v110, v001, v101, v011, v111, xl, yl, zl); - } else { - return triLinearInterpolationNoEase( - v000, v100, v010, v110, - v001, v101, v011, v111, - xl, yl, zl); } + + return triLinearInterpolationNoEase( + v000, v100, v010, v110, + v001, v101, v011, v111, + xl, yl, zl); } -float noise2d_perlin(float x, float y, int seed, +float noise2d_perlin(float x, float y, s32 seed, int octaves, float persistence, bool eased) { float a = 0; @@ -348,14 +312,14 @@ float noise2d_perlin(float x, float y, int seed, } -float noise2d_perlin_abs(float x, float y, int seed, +float noise2d_perlin_abs(float x, float y, s32 seed, int octaves, float persistence, bool eased) { float a = 0; float f = 1.0; float g = 1.0; for (int i = 0; i < octaves; i++) { - a += g * fabs(noise2d_gradient(x * f, y * f, seed + i, eased)); + a += g * std::fabs(noise2d_gradient(x * f, y * f, seed + i, eased)); f *= 2.0; g *= persistence; } @@ -363,7 +327,7 @@ float noise2d_perlin_abs(float x, float y, int seed, } -float noise3d_perlin(float x, float y, float z, int seed, +float noise3d_perlin(float x, float y, float z, s32 seed, int octaves, float persistence, bool eased) { float a = 0; @@ -378,14 +342,14 @@ float noise3d_perlin(float x, float y, float z, int seed, } -float noise3d_perlin_abs(float x, float y, float z, int seed, +float noise3d_perlin_abs(float x, float y, float z, s32 seed, int octaves, float persistence, bool eased) { float a = 0; float f = 1.0; float g = 1.0; for (int i = 0; i < octaves; i++) { - a += g * fabs(noise3d_gradient(x * f, y * f, z * f, seed + i, eased)); + a += g * std::fabs(noise3d_gradient(x * f, y * f, z * f, seed + i, eased)); f *= 2.0; g *= persistence; } @@ -395,7 +359,7 @@ float noise3d_perlin_abs(float x, float y, float z, int seed, float contour(float v) { - v = fabs(v); + v = std::fabs(v); if (v >= 1.0) return 0.0; return (1.0 - v); @@ -405,7 +369,7 @@ float contour(float v) ///////////////////////// [ New noise ] //////////////////////////// -float NoisePerlin2D(NoiseParams *np, float x, float y, int seed) +float NoisePerlin2D(NoiseParams *np, float x, float y, s32 seed) { float a = 0; float f = 1.0; @@ -420,7 +384,7 @@ float NoisePerlin2D(NoiseParams *np, float x, float y, int seed) np->flags & (NOISE_FLAG_DEFAULTS | NOISE_FLAG_EASED)); if (np->flags & NOISE_FLAG_ABSVALUE) - noiseval = fabs(noiseval); + noiseval = std::fabs(noiseval); a += g * noiseval; f *= np->lacunarity; @@ -431,7 +395,7 @@ float NoisePerlin2D(NoiseParams *np, float x, float y, int seed) } -float NoisePerlin3D(NoiseParams *np, float x, float y, float z, int seed) +float NoisePerlin3D(NoiseParams *np, float x, float y, float z, s32 seed) { float a = 0; float f = 1.0; @@ -447,7 +411,7 @@ float NoisePerlin3D(NoiseParams *np, float x, float y, float z, int seed) np->flags & NOISE_FLAG_EASED); if (np->flags & NOISE_FLAG_ABSVALUE) - noiseval = fabs(noiseval); + noiseval = std::fabs(noiseval); a += g * noiseval; f *= np->lacunarity; @@ -458,18 +422,14 @@ float NoisePerlin3D(NoiseParams *np, float x, float y, float z, int seed) } -Noise::Noise(NoiseParams *np_, int seed, int sx, int sy, int sz) +Noise::Noise(NoiseParams *np_, s32 seed, u32 sx, u32 sy, u32 sz) { - memcpy(&np, np_, sizeof(np)); + np = *np_; this->seed = seed; this->sx = sx; this->sy = sy; this->sz = sz; - this->persist_buf = NULL; - this->gradient_buf = NULL; - this->result = NULL; - allocBuffers(); } @@ -510,7 +470,7 @@ void Noise::allocBuffers() } -void Noise::setSize(int sx, int sy, int sz) +void Noise::setSize(u32 sx, u32 sy, u32 sz) { this->sx = sx; this->sy = sy; @@ -538,28 +498,37 @@ void Noise::setOctaves(int octaves) void Noise::resizeNoiseBuf(bool is3d) { - //maximum possible spread value factor + // Maximum possible spread value factor float ofactor = (np.lacunarity > 1.0) ? pow(np.lacunarity, np.octaves - 1) : np.lacunarity; - // noise lattice point count + // Noise lattice point count // (int)(sz * spread * ofactor) is # of lattice points crossed due to length float num_noise_points_x = sx * ofactor / np.spread.X; float num_noise_points_y = sy * ofactor / np.spread.Y; float num_noise_points_z = sz * ofactor / np.spread.Z; - // protect against obviously invalid parameters + // Protect against obviously invalid parameters if (num_noise_points_x > 1000000000.f || - num_noise_points_y > 1000000000.f || - num_noise_points_z > 1000000000.f) + num_noise_points_y > 1000000000.f || + num_noise_points_z > 1000000000.f) throw InvalidNoiseParamsException(); + // Protect against an octave having a spread < 1, causing broken noise values + if (np.spread.X / ofactor < 1.0f || + np.spread.Y / ofactor < 1.0f || + np.spread.Z / ofactor < 1.0f) { + errorstream << "A noise parameter has too many octaves: " + << np.octaves << " octaves" << std::endl; + throw InvalidNoiseParamsException("A noise parameter has too many octaves"); + } + // + 2 for the two initial endpoints // + 1 for potentially crossing a boundary due to offset - size_t nlx = (size_t)ceil(num_noise_points_x) + 3; - size_t nly = (size_t)ceil(num_noise_points_y) + 3; - size_t nlz = is3d ? (size_t)ceil(num_noise_points_z) + 3 : 1; + size_t nlx = (size_t)std::ceil(num_noise_points_x) + 3; + size_t nly = (size_t)std::ceil(num_noise_points_y) + 3; + size_t nlz = is3d ? (size_t)std::ceil(num_noise_points_z) + 3 : 1; delete[] noise_buf; try { @@ -585,25 +554,26 @@ void Noise::resizeNoiseBuf(bool is3d) void Noise::gradientMap2D( float x, float y, float step_x, float step_y, - int seed) + s32 seed) { float v00, v01, v10, v11, u, v, orig_u; - int index, i, j, x0, y0, noisex, noisey; - int nlx, nly; + u32 index, i, j, noisex, noisey; + u32 nlx, nly; + s32 x0, y0; bool eased = np.flags & (NOISE_FLAG_DEFAULTS | NOISE_FLAG_EASED); Interp2dFxn interpolate = eased ? biLinearInterpolation : biLinearInterpolationNoEase; - x0 = floor(x); - y0 = floor(y); + x0 = std::floor(x); + y0 = std::floor(y); u = x - (float)x0; v = y - (float)y0; orig_u = u; //calculate noise point lattice - nlx = (int)(u + sx * step_x) + 2; - nly = (int)(v + sy * step_y) + 2; + nlx = (u32)(u + sx * step_x) + 2; + nly = (u32)(v + sy * step_y) + 2; index = 0; for (j = 0; j != nly; j++) for (i = 0; i != nlx; i++) @@ -648,20 +618,21 @@ void Noise::gradientMap2D( void Noise::gradientMap3D( float x, float y, float z, float step_x, float step_y, float step_z, - int seed) + s32 seed) { float v000, v010, v100, v110; float v001, v011, v101, v111; float u, v, w, orig_u, orig_v; - int index, i, j, k, x0, y0, z0, noisex, noisey, noisez; - int nlx, nly, nlz; + u32 index, i, j, k, noisex, noisey, noisez; + u32 nlx, nly, nlz; + s32 x0, y0, z0; Interp3dFxn interpolate = (np.flags & NOISE_FLAG_EASED) ? triLinearInterpolation : triLinearInterpolationNoEase; - x0 = floor(x); - y0 = floor(y); - z0 = floor(z); + x0 = std::floor(x); + y0 = std::floor(y); + z0 = std::floor(z); u = x - (float)x0; v = y - (float)y0; w = z - (float)z0; @@ -669,9 +640,9 @@ void Noise::gradientMap3D( orig_v = v; //calculate noise point lattice - nlx = (int)(u + sx * step_x) + 2; - nly = (int)(v + sy * step_y) + 2; - nlz = (int)(w + sz * step_z) + 2; + nlx = (u32)(u + sx * step_x) + 2; + nly = (u32)(v + sy * step_y) + 2; + nlz = (u32)(w + sz * step_z) + 2; index = 0; for (k = 0; k != nlz; k++) for (j = 0; j != nly; j++) @@ -763,7 +734,7 @@ float *Noise::perlinMap2D(float x, float y, float *persistence_map) g *= np.persist; } - if (fabs(np.offset - 0.f) > 0.00001 || fabs(np.scale - 1.f) > 0.00001) { + if (std::fabs(np.offset - 0.f) > 0.00001 || std::fabs(np.scale - 1.f) > 0.00001) { for (size_t i = 0; i != bufsize; i++) result[i] = result[i] * np.scale + np.offset; } @@ -801,7 +772,7 @@ float *Noise::perlinMap3D(float x, float y, float z, float *persistence_map) g *= np.persist; } - if (fabs(np.offset - 0.f) > 0.00001 || fabs(np.scale - 1.f) > 0.00001) { + if (std::fabs(np.offset - 0.f) > 0.00001 || std::fabs(np.scale - 1.f) > 0.00001) { for (size_t i = 0; i != bufsize; i++) result[i] = result[i] * np.scale + np.offset; } @@ -811,19 +782,19 @@ float *Noise::perlinMap3D(float x, float y, float z, float *persistence_map) void Noise::updateResults(float g, float *gmap, - float *persistence_map, size_t bufsize) + const float *persistence_map, size_t bufsize) { // This looks very ugly, but it is 50-70% faster than having // conditional statements inside the loop if (np.flags & NOISE_FLAG_ABSVALUE) { if (persistence_map) { for (size_t i = 0; i != bufsize; i++) { - result[i] += gmap[i] * fabs(gradient_buf[i]); + result[i] += gmap[i] * std::fabs(gradient_buf[i]); gmap[i] *= persistence_map[i]; } } else { for (size_t i = 0; i != bufsize; i++) - result[i] += g * fabs(gradient_buf[i]); + result[i] += g * std::fabs(gradient_buf[i]); } } else { if (persistence_map) {