4 people like it.

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
Raw view Test code New version

More information

Link:http://fssnip.net/pq
Posted:9 years ago
Author:Krunoslav Saho
Tags: perlin noise , gradient noise , noise

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.