Skip to content

Instantly share code, notes, and snippets.

@tombsar

tombsar/gradient.hh

Created January 8, 2015 15:06
Show Gist options
  • Save tombsar/7d7efebb93a003812998 to your computer and use it in GitHub Desktop.
Save tombsar/7d7efebb93a003812998 to your computer and use it in GitHub Desktop.
Download ZIP
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
Raw
gradient.hh
/*
* 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
Raw
seed.hh
/*
* 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
Raw
simplectic.hh
/*
* 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