#![warn(missing_docs)]
use std::iter::{
self,
Extend,
};
use std::f64;
use rand::{
Rng,
SeedableRng,
distributions::{
Standard,
}
};
use rand_xorshift::{
XorShiftRng,
};
use concurrent_hashmap::{
Options as HashMapOptions,
ConcHashMap,
};
use fnv::FnvBuildHasher;
#[cfg(not(feature = "web"))]
use rayon::prelude::*;
#[cfg(not(feature = "web"))]
pub struct WorleyNoise {
permutation_table: Vec<u128>,
permutation_mask: usize,
density: f64,
point_count_table: Vec<u32>,
cache: ConcHashMap<(i32, i32, i32), Vec<(f64, f64, f64)>, FnvBuildHasher>,
distance_function: Box<dyn Fn(f64, f64, f64) -> f64 + Sync>,
value_function: Box<dyn Fn(Vec<f64>) -> f64 + Sync>,
radius: (u16, u16, u16),
}
#[cfg(feature = "web")]
pub struct WorleyNoise {
permutation_table: Vec<u128>,
permutation_mask: usize,
density: f64,
point_count_table: Vec<u32>,
cache: ConcHashMap<(i32, i32, i32), Vec<(f64, f64, f64)>, FnvBuildHasher>,
distance_function: Box<dyn Fn(f64, f64, f64) -> f64>,
value_function: Box<dyn Fn(Vec<f64>) -> f64>,
radius: (u16, u16, u16),
}
impl WorleyNoise {
const MIN_POINTS: u32 = 1;
const MAX_POINTS: u32 = 9;
const POINT_COUNT_TABLE_LEN: usize = 150;
const CONCURRENCY: u16 = 64;
pub const DEFAULT_RADIUS: u16 = 1;
pub const DEFAULT_PERMUTATION_BITS: usize = 10;
pub const DEFAULT_DENSITY: f64 = 3.0;
pub const DEFAULT_CACHE_CAPACITY: usize = 10000;
pub fn new() -> Self {
Self::with_cache_capacity(Self::DEFAULT_CACHE_CAPACITY)
}
pub fn with_cache_capacity(capacity: usize) -> Self {
let default_distance_function = |x, y, z| x * x + y * y + z * z;
let default_value_function = |distances: Vec<f64>| distances.iter()
.cloned()
.fold(f64::MAX, f64::min);
let cache_options = HashMapOptions {
capacity: capacity,
hasher_factory: FnvBuildHasher::default(),
concurrency: Self::CONCURRENCY
};
let mut noise = Self {
permutation_table: Vec::new(),
permutation_mask: 0,
density: 0.0,
point_count_table: Vec::new(),
cache: ConcHashMap::with_options(cache_options),
distance_function: Box::new(default_distance_function),
value_function: Box::new(default_value_function),
radius: (Self::DEFAULT_RADIUS, Self::DEFAULT_RADIUS, Self::DEFAULT_RADIUS),
};
noise.set_density(Self::DEFAULT_DENSITY);
noise.permutate(Self::DEFAULT_PERMUTATION_BITS);
noise
}
fn feature_point_count(&self, probability: f64) -> u32 {
let index = (self.point_count_table.len() as f64 * probability).floor() as usize;
self.point_count_table[index]
}
fn hash(&self, x: i32, y: i32, z: i32) -> [u8; 16] {
let mut hash = self.permutation_table[x as usize & self.permutation_mask];
hash = self.permutation_table[(hash as usize ^ y as usize) & self.permutation_mask];
hash = self.permutation_table[(hash as usize ^ z as usize) & self.permutation_mask];
hash.to_be_bytes()
}
fn feature_points_with_cache(&self, cube_x: i32, cube_y: i32, cube_z: i32, collector: &mut Vec<(f64, f64, f64)>) {
if let Some(cached) = self.cache.find(&(cube_x, cube_y, cube_z)) {
collector.extend_from_slice(cached.get());
return;
}
let seed = self.hash(cube_x, cube_y, cube_z);
let mut rng = XorShiftRng::from_seed(seed);
let count = self.feature_point_count(rng.gen());
let mut points = Vec::with_capacity(count as usize);
for _ in 0 .. count {
let x = rng.gen::<f64>() + cube_x as f64;
let y = rng.gen::<f64>() + cube_y as f64;
let z = rng.gen::<f64>() + cube_z as f64;
points.push((x, y, z));
}
collector.extend_from_slice(&points);
self.cache.insert((cube_x, cube_y, cube_z), points);
}
fn feature_points(&self, cube_x: i32, cube_y: i32, cube_z: i32, collector: &mut Vec<(f64, f64, f64)>) {
let seed = self.hash(cube_x, cube_y, cube_z);
let mut rng = XorShiftRng::from_seed(seed);
let count = self.feature_point_count(rng.gen());
for _ in 0 .. count {
let x = rng.gen::<f64>() + cube_x as f64;
let y = rng.gen::<f64>() + cube_y as f64;
let z = rng.gen::<f64>() + cube_z as f64;
collector.push((x, y, z));
}
}
fn feature_points_from_cube_list(&self, cubes: &Vec<(i32, i32, i32)>) -> Vec<Vec<(f64, f64, f64)>> {
let points_per_cube = (self.density + 1.0).ceil() as usize;
let mut feature_points = Vec::with_capacity(cubes.len());
#[cfg(not(feature = "web"))]
let cube_iter = cubes.par_iter();
#[cfg(feature = "web")]
let cube_iter = cubes.iter();
let cube_iter = cube_iter.map(|&(x, y, z)| {
let mut points = Vec::with_capacity(points_per_cube);
self.feature_points(x, y, z, &mut points);
points
});
#[cfg(not(feature = "web"))]
cube_iter.collect_into_vec(&mut feature_points);
#[cfg(feature = "web")]
feature_points.extend(cube_iter);
feature_points
}
fn adjacent_feature_points(&self, cube_x: i32, cube_y: i32, cube_z: i32) -> Vec<(f64, f64, f64)> {
let radius_x = self.radius.0 as i32;
let radius_y = self.radius.1 as i32;
let radius_z = self.radius.2 as i32;
let cubes_per_sample = (1 + radius_x * 2) * (1 + radius_y * 2) * (1 + radius_z * 2);
let points_per_sample = ((self.density + 1.0) * cubes_per_sample as f64).ceil() as usize;
let mut points = Vec::with_capacity(points_per_sample);
let start_x = cube_x - radius_x;
let start_y = cube_y - radius_y;
let start_z = cube_z - radius_z;
let end_x = cube_x + radius_x;
let end_y = cube_y + radius_y;
let end_z = cube_z + radius_z;
for x in start_x ..= end_x {
for y in start_y ..= end_y {
for z in start_z ..= end_z {
self.feature_points_with_cache(x, y, z, &mut points);
}
}
}
points
}
fn sample_points_from_point_lists(&self, feature_points: &Vec<Vec<(f64, f64, f64)>>, sample_points: &Vec<(f64, f64, f64)>, (cube_range_x, cube_range_y): (i32, i32)) -> Vec<f64> {
let (radius_x, radius_y, radius_z) = (
self.radius.0 as i32,
self.radius.1 as i32,
self.radius.2 as i32
);
let cubes_per_sample = (1 + radius_x * 2) * (1 + radius_y * 2) * (1 + radius_z * 2);
let points_per_sample = ((self.density + 1.0) * cubes_per_sample as f64).ceil() as usize;
let mut values = Vec::with_capacity(sample_points.len());
#[cfg(not(feature = "web"))]
let sample_point_iter = sample_points.par_iter();
#[cfg(feature = "web")]
let sample_point_iter = sample_points.iter();
let sample_point_iter = sample_point_iter.map(|&(sample_point_x, sample_point_y, sample_point_z)| {
let mut adjacent_points = Vec::with_capacity(points_per_sample);
let cube_x = sample_point_x.floor() as i32;
let cube_y = sample_point_y.floor() as i32;
let cube_z = sample_point_z.floor() as i32;
let start_x = cube_x - radius_x;
let start_y = cube_y - radius_y;
let start_z = cube_z - radius_z;
let end_x = cube_x + radius_x;
let end_y = cube_y + radius_y;
let end_z = cube_z + radius_z;
for x in start_x ..= end_x {
for y in start_y ..= end_y {
for z in start_z ..= end_z {
let idx = (
(x + radius_x)
+ (y + radius_y) * cube_range_x
+ (z + radius_z) * cube_range_x * cube_range_y
) as usize;
let points = &feature_points[idx];
adjacent_points.extend_from_slice(&points);
}
}
}
let mut distances = Vec::with_capacity(points_per_sample);
let distances_iter = adjacent_points.iter()
.map(|&(x, y, z)| (x - sample_point_x, y - sample_point_y, z - sample_point_z))
.map(|(x, y, z)| (self.distance_function)(x, y, z));
distances.extend(distances_iter);
(self.value_function)(distances)
});
#[cfg(not(feature = "web"))]
sample_point_iter.collect_into_vec(&mut values);
#[cfg(feature = "web")]
values.extend(sample_point_iter);
values
}
pub fn permutate(&mut self, permutation_table_bit_length: usize) {
self.permutate_seeded(permutation_table_bit_length, rand::random());
}
pub fn permutate_seeded(&mut self, permutation_table_bit_length: usize, seed: u128) {
let seed = seed.to_be_bytes();
let rng = XorShiftRng::from_seed(seed);
let length = 1 << permutation_table_bit_length;
self.permutation_table.clear();
self.permutation_table.reserve(length);
self.permutation_table.extend(rng.sample_iter::<u128, Standard>(Standard).take(length));
self.permutation_mask = length - 1;
}
pub fn set_density(&mut self, density: f64) {
self.point_count_table.clear();
self.point_count_table.reserve(Self::POINT_COUNT_TABLE_LEN);
for i in Self::MIN_POINTS ..= Self::MAX_POINTS {
let poisson = density.powi(i as i32) * f64::consts::E.powf(-density) / factorial(i as u16) as f64;
let count = (poisson * Self::POINT_COUNT_TABLE_LEN as f64).round() as usize;
self.point_count_table.extend(iter::repeat(i).take(count));
}
self.density = density;
}
#[cfg(not(feature = "web"))]
pub fn set_distance_function<F>(&mut self, function: F) where F: Fn(f64, f64, f64) -> f64 + Sync + 'static {
self.distance_function = Box::new(function);
}
#[cfg(feature = "web")]
pub fn set_distance_function<F>(&mut self, function: F) where F: Fn(f64, f64, f64) -> f64 + 'static {
self.distance_function = Box::new(function);
}
#[cfg(not(feature = "web"))]
pub fn set_value_function<F>(&mut self, function: F) where F: Fn(Vec<f64>) -> f64 + Sync + 'static {
self.value_function = Box::new(function);
}
#[cfg(feature = "web")]
pub fn set_value_function<F>(&mut self, function: F) where F: Fn(Vec<f64>) -> f64 + 'static {
self.value_function = Box::new(function);
}
pub fn set_radius(&mut self, radius: u16) {
self.radius = (radius, radius, radius);
}
pub fn set_radius_x(&mut self, radius: u16) {
self.radius.0 = radius;
}
pub fn set_radius_y(&mut self, radius: u16) {
self.radius.1 = radius;
}
pub fn set_radius_z(&mut self, radius: u16) {
self.radius.2 = radius;
}
pub fn value_3d(&self, x: f64, y: f64, z: f64) -> f64 {
let points = self.adjacent_feature_points(x.floor() as i32, y.floor() as i32, z.floor() as i32);
let distances = points.iter()
.map(|&(px, py, pz)| (px - x, py - y, pz - z))
.map(|(x, y, z)| (self.distance_function)(x, y, z))
.collect();
(self.value_function)(distances)
}
pub fn value_2d(&self, x: f64, y: f64) -> f64 {
self.value_3d(x, y, 0.0)
}
pub fn values_3d(&self, points: &Vec<(f64, f64, f64)>) -> Vec<f64> {
let mut values = Vec::with_capacity(points.len());
#[cfg(not(feature = "web"))]
{
points.par_iter()
.map(|&(x, y, z)| self.value_3d(x, y, z))
.collect_into_vec(&mut values);
}
#[cfg(feature = "web")]
{
points.iter()
.map(|&(x, y, z)| self.value_3d(x, y, z))
.for_each(|val| values.push(val));
}
values
}
pub fn values_2d(&self, points: &Vec<(f64, f64)>) -> Vec<f64> {
let points_3d = points.iter()
.map(|(x, y)| (*x, *y, 0.0))
.collect();
self.values_3d(&points_3d)
}
pub fn values_3d_range(&self, start: (f64, f64, f64), end: (f64, f64, f64), sample_cnt: (u32, u32, u32)) -> Vec<f64> {
let (start_x, start_y, start_z) = start;
let (end_x, end_y, end_z) = end;
if end_x < start_x || end_y < start_y || end_z < start_z {
panic!("End coordinates can't be smaller than start coordinates");
}
let (sample_cnt_x, sample_cnt_y, sample_cnt_z) = sample_cnt;
let (sample_range_x, sample_range_y, sample_range_z) = (
(end_x - start_x),
(end_y - start_y),
(end_z - start_z)
);
let (radius_x, radius_y, radius_z) = (
self.radius.0 as i32,
self.radius.1 as i32,
self.radius.2 as i32
);
let (cube_start_x, cube_start_y, cube_start_z) = (
start_x.floor() as i32 - radius_x,
start_y.floor() as i32 - radius_y,
start_z.floor() as i32 - radius_z
);
let (cube_end_x, cube_end_y, cube_end_z) = (
end_x.floor() as i32 + radius_x,
end_y.floor() as i32 + radius_y,
end_z.floor() as i32 + radius_z
);
let (cube_range_x, cube_range_y) = (
cube_end_x - cube_start_x + 1,
cube_end_y - cube_start_y + 1
);
let cube_cnt = ((1 + cube_end_x - cube_start_x) * (1 + cube_end_y - cube_start_y) * (1 + cube_end_z - cube_start_z)) as usize;
let sample_cnt = (sample_cnt_x * sample_cnt_y * sample_cnt_z) as usize;
let mut cubes = Vec::with_capacity(cube_cnt);
let mut sample_points = Vec::with_capacity(sample_cnt);
for z in cube_start_z ..= cube_end_z {
for y in cube_start_y ..= cube_end_y {
for x in cube_start_x ..= cube_end_x {
cubes.push((x, y, z));
}
}
}
let feature_points = self.feature_points_from_cube_list(&cubes);
for z in 0 .. sample_cnt_z {
let sample_point_z = start_z + z as f64 * sample_range_z / sample_cnt_z as f64;
for y in 0 .. sample_cnt_y {
let sample_point_y = start_y + y as f64 * sample_range_y / sample_cnt_y as f64;
for x in 0 .. sample_cnt_x {
let sample_point_x = start_x + x as f64 * sample_range_x / sample_cnt_x as f64;
sample_points.push((sample_point_x, sample_point_y, sample_point_z));
}
}
}
self.sample_points_from_point_lists(&feature_points, &sample_points, (cube_range_x, cube_range_y))
}
pub fn values_2d_range(&self, start: (f64, f64), end: (f64, f64), sample_cnt: (u32, u32)) -> Vec<f64> {
let (start_x, start_y) = start;
let (end_x, end_y) = end;
let (sample_cnt_x, sample_cnt_y) = sample_cnt;
self.values_3d_range((start_x, start_y, 0.0), (end_x, end_y, 0.0), (sample_cnt_x, sample_cnt_y, 1))
}
pub fn clear_cache(&mut self) {
self.cache.clear();
}
}
fn factorial(x: u16) -> u32 {
let mut val = 1;
for i in 2 .. x as u32 + 1 {
val *= i;
}
val
}