Created
January 8, 2015 15:06
-
-
Save tombsar/7d7efebb93a003812998 to your computer and use it in GitHub Desktop.
C++ port of Michael Powell's Simplectic Noise, originally written in Rust. His algorithm is described in a blog post here: http://www.spiritofiron.com/2015/01/simplectic-noise.html
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * Simplectic Noise in C++ | |
| * by Arthur Tombs | |
| * | |
| * Modified 2015-01-08 | |
| * | |
| * This is a derivative work based on Simplectic Noise in Rust | |
| * by Michael Powell: | |
| * http://www.spiritofiron.com/2015/01/simplectic-noise.html | |
| * | |
| * The files upon which this implementation is based can be found here: | |
| * https://github.com/bjz/noise-rs | |
| * | |
| * The original copyright notice for gradient.rs is included below: | |
| * | |
| * // Copyright 2013 The noise-rs developers. For a full listing of the authors, | |
| * // refer to the AUTHORS file at the top-level directory of this distribution. | |
| * // | |
| * // Licensed under the Apache License, Version 2.0 (the "License"); | |
| * // you may not use this file except in compliance with the License. | |
| * // You may obtain a copy of the License at | |
| * // | |
| * // http://www.apache.org/licenses/LICENSE-2.0 | |
| * // | |
| * // Unless required by applicable law or agreed to in writing, software | |
| * // distributed under the License is distributed on an "AS IS" BASIS, | |
| * // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| * // See the License for the specific language governing permissions and | |
| * // limitations under the License. | |
| */ | |
| #ifndef GRADIENT_HH | |
| #define GRADIENT_HH | |
| #include <cmath> | |
| #include <array> | |
| namespace simplectic { | |
| namespace { | |
| template <typename T, size_t N> | |
| class Gradient; | |
| template <typename T> | |
| class Gradient<T, 2> { | |
| public: | |
| static std::array<T, 2> get (size_t index) { | |
| static const T diag = (T)M_SQRT1_2; | |
| static const T onef = (T)1.0; | |
| static const T zero = (T)0.0; | |
| static const T grad [] = { diag, diag, | |
| diag,-diag, | |
| -diag, diag, | |
| -diag,-diag, | |
| onef, zero, | |
| -onef, zero, | |
| zero, onef, | |
| zero,-onef }; | |
| size_t ind = (index & 0x7) << 1; | |
| return { grad[ind], grad[ind+1] }; | |
| } | |
| }; | |
| template <typename T> | |
| class Gradient<T, 3> { | |
| public: | |
| static std::array<T, 3> get (size_t index) { | |
| static const T diag = (T)M_SQRT1_2; | |
| static const T zero = (T)0.0; | |
| static const T grad [] = { diag, diag, zero, | |
| diag,-diag, zero, | |
| -diag, diag, zero, | |
| -diag,-diag, zero, | |
| diag, zero, diag, | |
| diag, zero,-diag, | |
| -diag, zero, diag, | |
| -diag, zero,-diag, | |
| zero, diag, diag, | |
| zero, diag,-diag, | |
| zero,-diag, diag, | |
| zero,-diag,-diag }; | |
| size_t ind = (index % 12) * 3; | |
| return { grad[ind], grad[ind+1], grad[ind+2] }; | |
| } | |
| }; | |
| template <typename T> | |
| class Gradient<T, 4> { | |
| public: | |
| static std::array<T, 4> get (size_t index) { | |
| static const T diag = (T)(1.0 / std::sqrt(3.0)); | |
| static const T zero = (T)0.0; | |
| static const T grad [] = { diag, diag, diag, zero, | |
| diag,-diag, diag, zero, | |
| -diag, diag, diag, zero, | |
| -diag,-diag, diag, zero, | |
| diag, diag,-diag, zero, | |
| diag,-diag,-diag, zero, | |
| -diag, diag,-diag, zero, | |
| -diag,-diag,-diag, zero, | |
| diag, diag, zero, diag, | |
| diag,-diag, zero, diag, | |
| -diag, diag, zero, diag, | |
| -diag,-diag, zero, diag, | |
| diag, diag, zero,-diag, | |
| diag,-diag, zero,-diag, | |
| -diag, diag, zero,-diag, | |
| -diag,-diag, zero,-diag, | |
| diag, zero, diag, diag, | |
| diag, zero,-diag, diag, | |
| -diag, zero, diag, diag, | |
| -diag, zero,-diag, diag, | |
| diag, zero, diag,-diag, | |
| diag, zero,-diag,-diag, | |
| -diag, zero, diag,-diag, | |
| -diag, zero,-diag,-diag, | |
| zero, diag, diag, diag, | |
| zero, diag,-diag, diag, | |
| zero,-diag, diag, diag, | |
| zero,-diag,-diag, diag, | |
| zero, diag, diag,-diag, | |
| zero, diag,-diag,-diag, | |
| zero,-diag, diag,-diag, | |
| zero,-diag,-diag,-diag }; | |
| size_t ind = (index & 0x1F) << 2; | |
| return { grad[ind], grad[ind+1], grad[ind+2], grad[ind+3] }; | |
| } | |
| }; | |
| } | |
| template <typename T, size_t N> | |
| inline std::array<T, N> getGradient (size_t index) { | |
| return Gradient<T, N>::get(index); | |
| } | |
| } | |
| #endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * Simplectic Noise in C++ | |
| * by Arthur Tombs | |
| * | |
| * Modified 2015-01-08 | |
| * | |
| * This is a derivative work based on Simplectic Noise in Rust | |
| * by Michael Powell: | |
| * http://www.spiritofiron.com/2015/01/simplectic-noise.html | |
| * | |
| * The files upon which this implementation is based can be found here: | |
| * https://github.com/bjz/noise-rs | |
| * | |
| * The original copyright notice for seed.rs is included below: | |
| * | |
| * // Copyright 2013 The noise-rs developers. For a full listing of the authors, | |
| * // refer to the AUTHORS file at the top-level directory of this distribution. | |
| * // | |
| * // Licensed under the Apache License, Version 2.0 (the "License"); | |
| * // you may not use this file except in compliance with the License. | |
| * // You may obtain a copy of the License at | |
| * // | |
| * // http://www.apache.org/licenses/LICENSE-2.0 | |
| * // | |
| * // Unless required by applicable law or agreed to in writing, software | |
| * // distributed under the License is distributed on an "AS IS" BASIS, | |
| * // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| * // See the License for the specific language governing permissions and | |
| * // limitations under the License. | |
| */ | |
| #ifndef SEED_HH | |
| #define SEED_HH | |
| #include <cstdint> | |
| #include <random> | |
| #include <array> | |
| namespace simplectic { | |
| namespace { | |
| template <size_t N> | |
| inline size_t seedGet (const int64_t * pos, const size_t * values) { | |
| return values[(seedGet<N-1>(pos-1, values) + (size_t)(*pos)) & 0xFF]; | |
| } | |
| template <> | |
| inline size_t seedGet<1> (const int64_t * pos, const size_t * values) { | |
| return values[(size_t)((*pos) & 0xFF)]; | |
| } | |
| } | |
| class Seed { | |
| private: | |
| size_t values [256]; | |
| public: | |
| Seed (uint_fast32_t seed) { | |
| // Generate an array of numbers 0->255 in order | |
| size_t seq [256]; | |
| for (size_t i = 0; i < 256; ++i) { seq[i] = i; } | |
| // Initialize the LCG | |
| std::minstd_rand rng(seed); | |
| // Randomly permute the numbers in an unbiased way | |
| for (int i = 255; i >= 0; --i) { | |
| // Generate a random index r in the range 0 <= r <= i | |
| std::uniform_int_distribution<size_t> dst (0, i); | |
| size_t r = dst(rng); | |
| // Swap the rth number with the (i+1)th | |
| values[i] = seq[r]; | |
| seq[r] = seq[i]; | |
| } | |
| } | |
| template <size_t N> | |
| inline size_t operator() (const std::array<int64_t, N> & pos) const { | |
| return seedGet<N>(&(pos[N-1]), &(values[0])); | |
| } | |
| }; | |
| } | |
| #endif |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * Simplectic Noise in C++ | |
| * by Arthur Tombs | |
| * | |
| * Modified 2015-01-08 | |
| * | |
| * This is a derivative work based on Simplectic Noise in Rust | |
| * by Michael Powell: | |
| * http://www.spiritofiron.com/2015/01/simplectic-noise.html | |
| * | |
| * The files upon which this implementation is based can be found here: | |
| * https://github.com/bjz/noise-rs | |
| * | |
| * The original copyright notice for simplectic.rs is included below: | |
| * | |
| * // Copyright 2013 The noise-rs developers. For a full listing of the authors, | |
| * // refer to the AUTHORS file at the top-level directory of this distribution. | |
| * // | |
| * // Licensed under the Apache License, Version 2.0 (the "License"); | |
| * // you may not use this file except in compliance with the License. | |
| * // You may obtain a copy of the License at | |
| * // | |
| * // http://www.apache.org/licenses/LICENSE-2.0 | |
| * // | |
| * // Unless required by applicable law or agreed to in writing, software | |
| * // distributed under the License is distributed on an "AS IS" BASIS, | |
| * // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| * // See the License for the specific language governing permissions and | |
| * // limitations under the License. | |
| */ | |
| #ifndef SIMPLECTIC_HH | |
| #define SIMPLECTIC_HH | |
| #include <cstdint> | |
| #include <type_traits> | |
| #include <array> | |
| #include <cmath> | |
| #include "seed.hh" | |
| #include "gradient.hh" | |
| namespace simplectic { | |
| namespace { | |
| template <typename T, size_t N> | |
| struct SimplecticPoint { | |
| std::array<int64_t, N> cell; | |
| std::array<T, N> offset; | |
| }; | |
| template <typename T> | |
| inline SimplecticPoint<T, 3> to3D (const SimplecticPoint<T, 2> & p, int64_t z_cell, T z_offset) { | |
| return { { p.cell[0], p.cell[1], z_cell }, | |
| { p.offset[0], p.offset[1], z_offset } }; | |
| } | |
| template <typename T> | |
| inline SimplecticPoint<T, 4> to4D (const SimplecticPoint<T, 3> & p, int64_t w_cell, T w_offset) { | |
| return { { p.cell[0], p.cell[1], p.cell[2], w_cell }, | |
| { p.offset[0], p.offset[1], p.offset[2], w_offset } }; | |
| } | |
| // Helper functions to find the dot-product of two arrays | |
| template <typename T, size_t N> | |
| inline T dot (const std::array<T, N> & a, const std::array<T, N> & b) { | |
| T initial = 0.0; | |
| for (size_t i=0; i<N; ++i) initial += a[i]*b[i]; | |
| return initial; | |
| } | |
| // Helper function to find the sum-of-squared-values of an array | |
| template <typename T, size_t N> | |
| inline T sumsq (const std::array<T, N> & a) { | |
| return dot(a, a); | |
| } | |
| #ifdef __FAST_MATH__ | |
| // When compiling with errno disabled, GCC makes std::floor more | |
| // efficient than the version below | |
| #define fastFloorf(x) std::floor(x) | |
| #else | |
| template <typename T> | |
| inline int64_t fastFloori (T x) { | |
| int64_t ip = (int64_t)x; | |
| #ifndef SIMPLECTIC_ALWAYS_POSITIVE | |
| if (x < 0.0) --ip; | |
| #endif | |
| return ip; | |
| } | |
| template <typename T> | |
| inline T fastFloorf (T x) { | |
| return (T)fastFloori(x); | |
| } | |
| #endif | |
| // This function seems to be faster than std::pow(x, 4) in all cases | |
| template <typename T> | |
| inline T pow4 (T x) { | |
| x *= x; | |
| return x*x; | |
| } | |
| template <typename T> inline constexpr T skew_constant (void) { return (T)(std::sqrt(3.0) * 0.5 - 0.5); } | |
| template <typename T> inline constexpr T unskew_constant (void) { return (T)(std::sqrt(3.0) * (-1.0 / 6.0) + 0.5); } | |
| template <typename T> inline constexpr T simplex_size (void) { return (T)M_SQRT1_2; } | |
| template <typename T> inline constexpr T inv_simplex_size (void) { return (T)M_SQRT2; } | |
| template <typename T> inline constexpr T layer_offset_x (void) { return (T)((2.0 / 3.0) - unskew_constant<T>()); } | |
| template <typename T> inline constexpr T layer_offset_y (void) { return (T)((1.0 / 3.0) - unskew_constant<T>()); } | |
| template <typename T> inline constexpr T layer_offset_z (void) { return (T)((1.0 / 3.0) - unskew_constant<T>()); } | |
| template <size_t N> constexpr double norm_constant (void); | |
| template <> inline constexpr double norm_constant<2> (void) { return 8.0; } | |
| template <> inline constexpr double norm_constant<3> (void) { return 9.0; } | |
| template <> inline constexpr double norm_constant<4> (void) { return 10.0; } | |
| template <typename T> | |
| inline std::array<SimplecticPoint<T, 2>, 3> simplectic_points (std::array<T, 2> point) { | |
| // Skew the input coordinates into the grid to figure out which grid cell we are in | |
| T skew_offset = (point[0] + point[1]) * skew_constant<T>(); | |
| T x_cell = fastFloorf(point[0] + skew_offset); | |
| T y_cell = fastFloorf(point[1] + skew_offset); | |
| // Unskew the floored coordinates to find the real coordinates of the cell origin | |
| T unskew_offset = (x_cell + y_cell) * unskew_constant<T>(); | |
| T x_origin = x_cell - unskew_offset; | |
| T y_origin = y_cell - unskew_offset; | |
| // Compute the delta from the first point, which is the cell origin | |
| T dx0 = point[0] - x_origin; | |
| T dy0 = point[1] - y_origin; | |
| // Compute the delta from the second point, which depends on which simplex we are in | |
| T x1_offset = (dx0 > dy0) ? (T)1.0 : (T)0.0; | |
| T y1_offset = (dx0 > dy0) ? (T)0.0 : (T)1.0; | |
| T dx1 = dx0 - x1_offset + unskew_constant<T>(); | |
| T dy1 = dy0 - y1_offset + unskew_constant<T>(); | |
| // Compute the delta from the third point | |
| T dx2 = dx0 + unskew_constant<T>() * (T)2.0 - (T)1.0; | |
| T dy2 = dy0 + unskew_constant<T>() * (T)2.0 - (T)1.0; | |
| return { | |
| SimplecticPoint<T, 2>{ { (int64_t)x_cell, (int64_t)y_cell }, { dx0, dy0 } }, | |
| SimplecticPoint<T, 2>{ { (int64_t)(x_cell + x1_offset), (int64_t)(y_cell + y1_offset) }, { dx1, dy1 } }, | |
| SimplecticPoint<T, 2>{ { (int64_t)x_cell + INT64_C(1), (int64_t)y_cell + INT64_C(1) }, { dx2, dy2 } } | |
| }; | |
| } | |
| template <typename T> | |
| inline std::array<SimplecticPoint<T, 3>, 6> simplectic_points (const std::array<T, 3> & point) { | |
| #ifdef __FAST_MATH__ | |
| T layer = fastFloorf(point[2] * inv_simplex_size<T>()); | |
| int64_t layer_int = (int64_t)layer; | |
| #else | |
| int64_t layer_int = fastFloori(point[2] * inv_simplex_size<T>()); | |
| T layer = (T)layer_int; | |
| #endif | |
| std::array<T, 2> point2 = { point[0], point[1] }; | |
| std::array<T, 2> offset_point2 = { point[0] + layer_offset_x<T>(), | |
| point[1] + layer_offset_y<T>() }; | |
| auto & layer1_point = (layer_int & 0x1) ? offset_point2 : point2; | |
| auto & layer2_point = (layer_int & 0x1) ? point2 : offset_point2; | |
| auto P13 = simplectic_points(layer1_point); | |
| auto P46 = simplectic_points(layer2_point); | |
| T z_offset = point[2] - layer * simplex_size<T>(); | |
| return { | |
| to3D(P13[0], layer_int, z_offset), | |
| to3D(P13[1], layer_int, z_offset), | |
| to3D(P13[2], layer_int, z_offset), | |
| to3D(P46[0], layer_int + INT64_C(1), z_offset - simplex_size<T>()), | |
| to3D(P46[1], layer_int + INT64_C(1), z_offset - simplex_size<T>()), | |
| to3D(P46[2], layer_int + INT64_C(1), z_offset - simplex_size<T>()) | |
| }; | |
| } | |
| template <typename T> | |
| inline std::array<SimplecticPoint<T, 4>, 12> simplectic_points (const std::array<T, 4> & point) { | |
| #ifdef __FAST_MATH__ | |
| T layer = fastFloorf(point[3] * inv_simplex_size<T>()); | |
| int64_t layer_int = (int64_t)layer; | |
| #else | |
| int64_t layer_int = fastFloori(point[3] * inv_simplex_size<T>()); | |
| T layer = (T)layer_int; | |
| #endif | |
| std::array<T, 3> point3 = { point[0], point[1], point[2] }; | |
| std::array<T, 3> offset_point3 = { point[0] + layer_offset_x<T>(), | |
| point[1] + layer_offset_y<T>(), | |
| point[2] + layer_offset_z<T>() }; | |
| std::array<T, 3> & layer1_point = (layer_int & 0x1) ? offset_point3 : point3; | |
| std::array<T, 3> & layer2_point = (layer_int & 0x1) ? point3 : offset_point3; | |
| auto P16 = simplectic_points(layer1_point); | |
| auto P712 = simplectic_points(layer2_point); | |
| T w_offset = point[3] - layer * simplex_size<T>(); | |
| return { | |
| to4D(P16[0], layer_int, w_offset), | |
| to4D(P16[1], layer_int, w_offset), | |
| to4D(P16[2], layer_int, w_offset), | |
| to4D(P16[3], layer_int, w_offset), | |
| to4D(P16[4], layer_int, w_offset), | |
| to4D(P16[5], layer_int, w_offset), | |
| to4D(P712[0], layer_int + INT64_C(1), w_offset - simplex_size<T>()), | |
| to4D(P712[1], layer_int + INT64_C(1), w_offset - simplex_size<T>()), | |
| to4D(P712[2], layer_int + INT64_C(1), w_offset - simplex_size<T>()), | |
| to4D(P712[3], layer_int + INT64_C(1), w_offset - simplex_size<T>()), | |
| to4D(P712[4], layer_int + INT64_C(1), w_offset - simplex_size<T>()), | |
| to4D(P712[5], layer_int + INT64_C(1), w_offset - simplex_size<T>()) | |
| }; | |
| } | |
| template <size_t N, typename T> | |
| inline T gradient (const Seed & seed, const SimplecticPoint<T, N> & p) { | |
| T attn = simplex_size<T>() - sumsq(p.offset); | |
| if (attn > 0.0) { | |
| return pow4(attn) * dot(p.offset, getGradient<T, N>(seed(p.cell))); | |
| } | |
| return 0.0; | |
| } | |
| } | |
| template <size_t N, typename T = double> | |
| T eval (const Seed & seed, const std::array<T, N> & point) { | |
| static_assert(N >= 2 && N <= 4, "This implementation of Simplectic noise only supports 2D, 3D and 4D"); | |
| static_assert(std::is_floating_point<T>::value, "This implementation of Simplectic noise only supports floating point types"); | |
| auto P = simplectic_points(point); | |
| T val = 0.0; | |
| for (auto & p : P) val += gradient(seed, p); | |
| return val * (T)norm_constant<N>(); | |
| } | |
| } | |
| #endif |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment