From 58467bf9440571c0f7f43ba43bde9589e36d719e Mon Sep 17 00:00:00 2001 From: =?utf8?q?Alexis=20Laferri=C3=A8re?= Date: Thu, 5 Mar 2015 14:14:37 -0500 Subject: [PATCH] lib: intro 2 noise generators MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Alexis Laferrière --- lib/noise.nit | 333 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 333 insertions(+) create mode 100644 lib/noise.nit diff --git a/lib/noise.nit b/lib/noise.nit new file mode 100644 index 0000000..9c77d5c --- /dev/null +++ b/lib/noise.nit @@ -0,0 +1,333 @@ +# This file is part of NIT ( http://www.nitlanguage.org ). +# +# 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. + +# Provides the noise generators `PerlinNoise` and `InterpolatedNoise` +module noise + +# 2D noise generator +abstract class Noise + + # Get the noise value at `x`, `y` + # + # The coordinates `x`, `y` can be floats of any size. + # + # Returns a value between or equal to `min` and `max`. + fun [](x, y: Float): Float is abstract + + # Lowest possible value returned by `[]` + # + # Default at `0.0`. + # + # Require: `min < max` + var min = 0.0 is writable + + # Highest possible value returned by `[]` + # + # Default at `1.0`. + # + # Require: `min < max` + var max = 1.0 is writable + + # Distance between reference points of the noise + # + # Higher values will result in smoother noise and + # lower values will result in steeper curves. + # + # Default at `1.0`. + var period = 1.0 is writable + + # Amplitude of the values returned by `[]` + fun amplitude: Float do return max - min + + # Set the desired amplitude of the values returned by `[]` + # + # Will only modify `max`, `min` stays the same. + fun amplitude=(value: Float) do max = min + value + + # Frequency of this noise + fun frequency: Float do return 1.0/period + + # Set the frequency if this noise + fun frequency=(value: Float) do period = 1.0/value + + # Seed to the random number generator `gradient_vector` + # + # By default, `seed` has a random value created with `Int::rand`. + var seed: Int = 19559.rand is lazy, writable +end + +# 2D Perlin noise generator using layered `InterpolatedNoise` +# +# Get values at any coordinates with `[]`. +# The behavior of this generator can be customized using its attributes `min`, +# `max`, `period` and `seed`. +# +# This noise is more realistic and less smooth than the `InterpolatedNoise`. +# +# Due to implementation logic, the full amplitude cannot be reached. +# In practice, only `amplitude * (1.0 - 1.0 / n_levels)` is covered. +# +# This implementation uses a custom deterministic pseudo random number +# generator to set `InterpolatedNoise::seed` of the `layers`. +# It is seeded with the local `seed` and can be further customized by +# redefining `pseudo_random`. +# This process do not require any state, so this class only holds the +# attributes of the generator and does not keep any generated data. +# +# ## Usage example +# +# ~~~ +# var map = new PerlinNoise +# map.min = 0.0 +# map.max = 16.0 +# map.period = 20.0 +# map.seed = 0 +# +# var max = 0.0 +# var min = 100.0 +# for y in 30.times do +# for x in 70.times do +# # Get a value at x, y +# var val = map[x.to_f, y.to_f] +# printn val.to_i.to_hex +# +# max = max.max(val) +# min = min.min(val) +# end +# print "" +# end +# assert max <= map.max +# assert min >= map.min +# ~~~ +# +# ## Result at seed == 0 +# +# ~~~raw +# 7778887888899999888777666666666666666667777877776666666677777777788888 +# 7788877788899999998877776666666666666667777777766666666667777777778888 +# 77877777888999aa999888777777776666666667777777666666666666667777778888 +# 7777777888899aaaa99988877777776666666667777777666666666666667777778888 +# 7777777888899aaaa99998877777776666666667777777666666666666666777778888 +# 7777778888999aaaa99999887777777666666666777667666666666656667777788888 +# 7777778888899aaaa99999888877776666666666666666666666666555666777888888 +# 7777778888999aaaa99999888887777666666666666666666666666555666778888888 +# 6677778888999aaaa99999888887777666666677766666666666666555667778888888 +# 6677788889999aaa999998888877777766666677766667666666666656667788888888 +# 777788889999999a999998888777777766666677777777766666666666667788888888 +# 6677888899999999999988888777667776677777777777766666666666666788888888 +# 6677888999999999999988888776667777777777777777766666665566666788888888 +# 6777788999999999998888887766667777777777777777666666665566666788888889 +# 6777788999999999998888877766677777777777777777667666655566666788988999 +# 7777888999988999988888877766677777777777877777777665555666667788999999 +# 6778888899888889988888877766666777777777777776666665555666667888999999 +# 7788888899888888888888877666666777777777777766666665556666677888898999 +# 7788888899888888888888776666666777777777777666666666566666677888899999 +# 7788889998888888888877766666666777777777777666666666666666777888899999 +# 7888999988888888888777666666666777777777776666666666666667777788899988 +# 7888999988888887777776666666666777777777776666766666666677788888899988 +# 7788999998888877777776666666666777777777776667776666667778888888899988 +# 7788999988888777777776666666666777776677766777776677777788888889999988 +# 6788999988888777777766666666666677676677667777766677777888999999999998 +# 7788888888888777777776666666666666676677777776666777778889999999999998 +# 6778888888888777777766666566666666667777666776667777888999999999999999 +# 6778888888888777777766666566666666667776666776667778889999999999999999 +# 6778888888777777777666666566666666667776666777677788899999999999888999 +# 6777787777777777776666666666666666677777677777777888999999999998888899 +# ~~~ +class PerlinNoise + super Noise + + # Desired number of `layers` + # + # This attribute must be assigned before any call to `layers` or `[]`. + # + # By default, it is the highest integer under the logarithm base 2 + # of `amplitude`, or 4, whichever is the highest. + var n_layers: Int = 4.max(amplitude.abs.log_base(2.0).to_i) is lazy, writable + + # Layers of `InterpolatedNoise` composing `self` + var layers: Array[InterpolatedNoise] is lazy do + var layers = new Array[InterpolatedNoise] + + var max = max + var min = min + var period = period + var seed = seed + for l in n_layers.times do + min = min / 2.0 + max = max / 2.0 + seed = pseudo_random(seed) + + var layer = new InterpolatedNoise + layer.min = min + layer.max = max + layer.period = period + layer.seed = seed + layers.add layer + + period = period / 2.0 + end + return layers + end + + redef fun [](x, y) + do + var val = 0.0 + for layer in layers do + val += layer[x, y] + end + return val + end + + # Deterministic pseudo random number generator + # + # Used to get seeds for layers from the previous layers or `seed`. + protected fun pseudo_random(value: Int): Int + do + return value + 2935391 % 954847 + end +end + +# Simple interpolated noise +# +# Generates smoother noise than `PerlinNoise`. +# +# Each coordinates at a multiple of `period` defines a random vector and +# values in between are interpolated from these vectors. +# +# This implementation uses a custom deterministic pseudo random number +# generator seeded with `seed`. +# It can be further customized by redefining `gradient_vector`. +# This process do not require any state, so this class only holds the +# attributes of the generator and does not keep any generated data. +# +# ## Usage example +# +# ~~~ +# var map = new InterpolatedNoise +# map.min = 0.0 +# map.max = 16.0 +# map.period = 20.0 +# map.seed = 0 +# +# var max = 0.0 +# var min = 100.0 +# for y in 30.times do +# for x in 70.times do +# # Get a value at x, y +# var val = map[x.to_f, y.to_f] +# printn val.to_i.to_hex +# +# max = max.max(val) +# min = min.min(val) +# end +# print "" +# end +# assert max <= map.max +# assert min >= map.min +# ~~~ +# +# ## Result at seed == 0 +# +# ~~~raw +# 8777766666666666777787777666666666667777888999aaaaaaaaa999888777766666 +# 88877776666666667777777766666666666667777889999aaaaaaa9999887777666666 +# 98887777776666667777777666666666666666777889999aaaaaaa9999887776666666 +# 998888777777766777777776666666666666667778889999aaaaa99998887776666666 +# a998888777777777777777666666666666666667778899999aaa999998877766666666 +# aa99888877777777777777666666655566666667778899999999999998877766666665 +# aa99988877777777777777666666555556666667778889999999999988877766666655 +# aaa9988887777777777777666665555555666667778889999999999988877766666555 +# baa9998887777777777776666665555555666666778889999999999988877666666555 +# baa9998887777777777776666665555555666666778889999999999988877666666555 +# baa9998887777777777776666655555555566666778889999999999988877666665555 +# baa9998887777777777776666665555555666666778889999999999988877666666555 +# baa9998887777777777776666665555555666666778889999999999988877666666555 +# aaa9988887777777777777666665555555666667778889999999999988877766666555 +# aa99988877777777777777666666555556666667778889999999999988877766666655 +# aa99888877777777777777666666655566666667778899999999999998877766666665 +# a998888777777777777777666666666666666667778899999aaa999998877766666666 +# 998888777777766777777776666666666666667778889999aaaaa99998887776666666 +# 98887777776666667777777666666666666666777889999aaaaaaa9999887776666666 +# 88877776666666667777777766666666666667777889999aaaaaaa9999887777666666 +# 8777766666666666777787777666666666667777888999aaaaaaaaa999888777766666 +# 777766666666666667777777777666677777778889999aaaaaaaaaa999887777666666 +# 7776666666666666667777777777777777778888999aaaaaaaaaaa9999887776666666 +# 777666666666666666777777777777777888889999aaaaaaaaaaaa9998887776666666 +# 7766666666666666666777777777778888889999aaaaaaaaaaaaa99998877766666666 +# 776666666555666666677777777888888899999aaaaaaaaaaaaaa99998877766666665 +# 7766666655555666666777777788888899999aaaaaaaaaaaaaaa999988877766666655 +# 776666655555556666677777788888999999aaaaaaaaaaaaaaaa999988877766666555 +# 7666666555555566666677778888899999aaaaaabbbbaaaaaaa9999888777666666555 +# 766666655555556666667778888899999aaaaaabbbbaaaaaaa99999888777666666555 +# ~~~ +class InterpolatedNoise + super Noise + + redef fun [](x, y) + do + x = x/period + y = y/period + + # Get grid coordinates + var x0 = if x > 0.0 then x.to_i else x.to_i - 1 + var x1 = x0 + 1 + var y0 = if y > 0.0 then y.to_i else y.to_i - 1 + var y1 = y0 + 1 + + # Position in grid + var sx = x - x0.to_f + var sy = y - y0.to_f + + # Interpolate + var n0 = gradient_dot_product(x0, y0, x, y) + var n1 = gradient_dot_product(x1, y0, x, y) + var ix0 = sx.lerp(n0, n1) + n0 = gradient_dot_product(x0, y1, x, y) + n1 = gradient_dot_product(x1, y1, x, y) + var ix1 = sx.lerp(n0, n1) + var val = sy.lerp(ix0, ix1) + + # Return value in [min...max] from val in [-0.5...0.5] + val += 0.5 + return val.lerp(min, max) + end + + # Get the gradient vector at `x`, `y` on the axis `w` + # + # Returns a value between 0.0 and 1.0. + # + # Require: `w == 0 or w == 1` + protected fun gradient_vector(x, y, w: Int): Float + do + assert w == 0 or w == 1 + + # Use our own deterministic pseudo random number generator + # + # These magic prime numbers were determined good enough by + # non-emperical experimentation. They may need to be changed/improved. + var i = 17957*seed + 45127*x + 22613*y + 36919*w + var mod = 19031 + + return (i%mod).to_f/mod.to_f + end + + private fun gradient_dot_product(ix, iy: Int, x, y: Float): Float + do + var dx = x - ix.to_f + var dy = y - iy.to_f + + return dx*gradient_vector(ix, iy, 0) + dy*gradient_vector(ix, iy, 1) + end +end -- 1.7.9.5