4 people like it.
Like the snippet!
Perlin/Gradient Noise
I came looking for a fast implementation of Perlin Noise, but the only code snippet showed value noise, which has discontinuity in its 2nd derivative. This version of Perlin Noise has 3 improvements over the default.
1. 1024 gradient vectors
2. Higher order smoothing polynomial
3. A better hash function
This implementation has a slight change for performance reasons, and that is the removal of clamping the smoothing polynomial from 0.0 to 1.0, and no clamp on the final value, which would be from -1.0 to 1.0. I have not experienced any issues as in my code I have offset the values by scaling them into the range of 0.0 -> 1.0.
I have tested this and profiled this code for many hours in order get the absolute best performance I could. This code runs much faster in release mode than it does under debug mode. I have profiled in both debug and release modes, and against Heikki Törmälä's SimplexNoise, and in release mode my gradient noise implementation is a lot faster and since it uses doubles the numerical limit is far greater, as the Simplex Noise function fails once the 32bit floats overflow.
Keep in mind, this is 2D gradient noise, and I have not tested a 3D version.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
|
namespace TheGame
module Fractal =
let fractalBrownianMotion octaves lacunarity hz0 gain gain0 (fn : float -> float -> float) =
let rec fbm hz amp octaves x y =
if octaves = 0 then (fn (x*hz) (y*hz))*amp
else (fn (x*hz) (y*hz))*amp + fbm (hz*lacunarity) (amp*gain) (octaves-1) x y
fbm hz0 gain0 octaves
module GradientNoise =
let shuffle (rand : int -> int -> int) (data : List<int>) =
let swap (a: _[]) x y =
let tmp = a.[x]
a.[x] <- a.[y]
a.[y] <- tmp
let shuffle a =
Array.iteri (fun i _ -> swap a i (rand i (Array.length a))) a
a
shuffle (List.toArray data)
let dot (u : float*float) (v : float*float) =
let (x, y) = u
let (s, t) = v
x*s + y*t
let mag (u : float*float) = sqrt (dot u u)
let normalise u =
let (x, y) = u
let m = mag u
x/m, y/m
let makeGradNoise (seed : int) gridSize roughness =
// MathNet library; replace with System.Random for poor performance and quality
let rand = System.Random() //new MathNet.Numerics.Random.MersenneTwister(seed)
let maxPerms = 1023
let guass () = rand.NextDouble() - rand.NextDouble()
let grads = [| for i in 0 .. maxPerms -> normalise (guass(), guass()) |]
let gradsx, gradsy = [| for (x, y) in grads -> x |], [| for (x, y) in grads -> y |]
let xs = shuffle (fun x y -> rand.Next(x, y)) [0 .. maxPerms]
let ys = shuffle (fun x y -> rand.Next(x, y)) [0 .. maxPerms]
let rGridSize = 1.0 / gridSize
let gradNoise (x : float) (y : float) =
let gx = x*rGridSize
let gy = y*rGridSize
let igx0 = int gx
let igy0 = int gy
let igx1 = igx0 + 1
let igy1 = igy0 + 1
let fgx0 = System.Math.Floor gx
let fgy0 = System.Math.Floor gy
let fgx1 = System.Math.Ceiling gx
let fgy1 = System.Math.Ceiling gy
let ydx0 = ys.[igy0 &&& maxPerms]
let ydx1 = ys.[igy0 &&& maxPerms]
let ydx2 = ys.[igy1 &&& maxPerms]
let ydx3 = ys.[igy1 &&& maxPerms]
let xdx0 = xs.[igx0 &&& maxPerms]
let xdx1 = xs.[igx1 &&& maxPerms]
let xdx2 = xs.[igx0 &&& maxPerms]
let xdx3 = xs.[igx1 &&& maxPerms]
let idx0 = xdx0 ^^^ ydx0
let idx1 = xdx1 ^^^ ydx1
let idx2 = xdx2 ^^^ ydx2
let idx3 = xdx3 ^^^ ydx3
let g0x = gradsx.[idx0]
let g0y = gradsy.[idx0]
let g1x = gradsx.[idx1]
let g1y = gradsy.[idx1]
let g2x = gradsx.[idx2]
let g2y = gradsy.[idx2]
let g3x = gradsx.[idx3]
let g3y = gradsy.[idx3]
let d0 = (gx - fgx0)*g0x + (gy - fgy0)*g0y
let d1 = (gx - fgx1)*g1x + (gy - fgy0)*g1y
let d2 = (gx - fgx0)*g2x + (gy - fgy1)*g2y
let d3 = (gx - fgx1)*g3x + (gy - fgy1)*g3y
let remX = gx-fgx0
let remY = gy-fgy0
let rx = remX*remX*remX*(remX*(remX*6.0-15.0)+10.0)
let ry = remY*remY*remY*(remY*(remY*6.0-15.0)+10.0)
let xx = (1.0-rx)*d0 + rx*d1
let yy = (1.0-rx)*d2 + rx*d3
(1.0-ry)*xx + ry*yy
Fractal.fractalBrownianMotion roughness 2.0 (1.0/gridSize) 0.65 0.65 gradNoise
|
val fractalBrownianMotion : octaves:int -> lacunarity:float -> hz0:float -> gain:float -> gain0:float -> fn:(float -> float -> float) -> (float -> float -> float)
Full name: TheGame.Fractal.fractalBrownianMotion
val octaves : int
val lacunarity : float
val hz0 : float
val gain : float
val gain0 : float
val fn : (float -> float -> float)
Multiple items
val float : value:'T -> float (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.float
--------------------
type float = System.Double
Full name: Microsoft.FSharp.Core.float
--------------------
type float<'Measure> = float
Full name: Microsoft.FSharp.Core.float<_>
val fbm : (float -> float -> int -> float -> float -> float)
val hz : float
val amp : float
val x : float
val y : float
module GradientNoise
from TheGame
val shuffle : rand:(int -> int -> int) -> data:List<int> -> int []
Full name: TheGame.GradientNoise.shuffle
val rand : (int -> int -> int)
Multiple items
val int : value:'T -> int (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int
--------------------
type int = int32
Full name: Microsoft.FSharp.Core.int
--------------------
type int<'Measure> = int
Full name: Microsoft.FSharp.Core.int<_>
val data : List<int>
Multiple items
module List
from Microsoft.FSharp.Collections
--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member Head : 'T
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list
Full name: Microsoft.FSharp.Collections.List<_>
val swap : ('a [] -> int -> int -> unit)
val a : 'a []
val x : int
val y : int
val tmp : 'a
val shuffle : ('a [] -> 'a [])
module Array
from Microsoft.FSharp.Collections
val iteri : action:(int -> 'T -> unit) -> array:'T [] -> unit
Full name: Microsoft.FSharp.Collections.Array.iteri
val i : int
val length : array:'T [] -> int
Full name: Microsoft.FSharp.Collections.Array.length
val toArray : list:'T list -> 'T []
Full name: Microsoft.FSharp.Collections.List.toArray
val dot : float * float -> float * float -> float
Full name: TheGame.GradientNoise.dot
val u : float * float
val v : float * float
val s : float
val t : float
val mag : float * float -> float
Full name: TheGame.GradientNoise.mag
val sqrt : value:'T -> 'U (requires member Sqrt)
Full name: Microsoft.FSharp.Core.Operators.sqrt
val normalise : float * float -> float * float
Full name: TheGame.GradientNoise.normalise
val m : float
val makeGradNoise : seed:int -> gridSize:float -> roughness:int -> (float -> float -> float)
Full name: TheGame.GradientNoise.makeGradNoise
val seed : int
val gridSize : float
val roughness : int
val rand : System.Random
namespace System
Multiple items
type Random =
new : unit -> Random + 1 overload
member Next : unit -> int + 2 overloads
member NextBytes : buffer:byte[] -> unit
member NextDouble : unit -> float
Full name: System.Random
--------------------
System.Random() : unit
System.Random(Seed: int) : unit
val maxPerms : int
val guass : (unit -> float)
System.Random.NextDouble() : float
val grads : (float * float) []
val gradsx : float []
val gradsy : float []
val xs : int []
System.Random.Next() : int
System.Random.Next(maxValue: int) : int
System.Random.Next(minValue: int, maxValue: int) : int
val ys : int []
val rGridSize : float
val gradNoise : (float -> float -> float)
val gx : float
val gy : float
val igx0 : int
val igy0 : int
val igx1 : int
val igy1 : int
val fgx0 : float
type Math =
static val PI : float
static val E : float
static member Abs : value:sbyte -> sbyte + 6 overloads
static member Acos : d:float -> float
static member Asin : d:float -> float
static member Atan : d:float -> float
static member Atan2 : y:float * x:float -> float
static member BigMul : a:int * b:int -> int64
static member Ceiling : d:decimal -> decimal + 1 overload
static member Cos : d:float -> float
...
Full name: System.Math
System.Math.Floor(d: float) : float
System.Math.Floor(d: decimal) : decimal
val fgy0 : float
val fgx1 : float
System.Math.Ceiling(a: float) : float
System.Math.Ceiling(d: decimal) : decimal
val fgy1 : float
val ydx0 : int
val ydx1 : int
val ydx2 : int
val ydx3 : int
val xdx0 : int
val xdx1 : int
val xdx2 : int
val xdx3 : int
val idx0 : int
val idx1 : int
val idx2 : int
val idx3 : int
val g0x : float
val g0y : float
val g1x : float
val g1y : float
val g2x : float
val g2y : float
val g3x : float
val g3y : float
val d0 : float
val d1 : float
val d2 : float
val d3 : float
val remX : float
val remY : float
val rx : float
val ry : float
val xx : float
val yy : float
module Fractal
from TheGame
More information