Simplex noise

Last updated

Simplex noise is a method for constructing an n-dimensional noise function comparable to Perlin noise ("classic" noise) but with fewer directional artifacts and, in higher dimensions, a lower computational overhead. Ken Perlin designed the algorithm in 2001 [1] to address the limitations of his classic noise function, especially in higher dimensions.

Contents

The advantages of simplex noise over Perlin noise:

Whereas classical noise interpolates between the gradients at the surrounding hypergrid end points (i.e., northeast, northwest, southeast and southwest in 2D[ citation needed ]), simplex noise divides the space into simplices (i.e., -dimensional triangles). This reduces the number of data points. While a hypercube in dimensions has corners, a simplex in dimensions has only corners. The triangles are equilateral in 2D, but in higher dimensions the simplices are only approximately regular. For example, the tiling in the 3D case of the function is an orientation of the tetragonal disphenoid honeycomb.

Simplex noise is useful for computer graphics applications, where noise is usually computed over 2, 3, 4 or possibly 5 dimensions. For higher dimensions, n-spheres around n-simplex corners are not densely enough packed, reducing the support of the function and making it zero in large portions of space.

Algorithm detail

Simplex noise is most commonly implemented as a two-, three-, or four-dimensional function, but can be defined for any number of dimensions. An implementation typically involves four steps: coordinate skewing, simplicial subdivision, gradient selection, and kernel summation.

Coordinate skewing

An input coordinate is transformed using the formula

where

This has the effect of placing the coordinate on an A*
n
lattice, which is essentially the vertex arrangement of a hypercubic honeycomb that has been squashed along its main diagonal until the distance between the points (0, 0, ..., 0) and (1, 1, ..., 1) becomes equal to the distance between the points (0, 0, ..., 0) and (1, 0, ..., 0).

The resulting coordinate (x', y', ...) is then used in order to determine which skewed unit hypercube cell the input point lies in, (xb' = floor(x'), yb' = floor(y'), ...), and its internal coordinates (xi' = x'xb', yi' = y'yb', ...).

Simplicial subdivision

Once the above is determined, the values of the internal coordinate (xi', yi', ...) are sorted in decreasing order, to determine which skewed Schläfli orthoscheme simplex the point lies in. Then the resulting simplex is composed of the vertices corresponding to an ordered edge traversal from (0, 0, ..., 0) to (1, 1, ..., 1), of which there are n! possibilities, each of which correspond to a single permutation of the coordinate. In other words, start with the zero coordinate and successively add ones starting in the value corresponding to the largest internal coordinate's value, ending with the smallest.

For example, the point (0.4, 0.5, 0.3) would lie inside the simplex with vertices (0, 0, 0), (0, 1, 0), (1, 1, 0), (1, 1, 1). The yi' coordinate is the largest, so it is added first. It is then followed by the xi' coordinate, and finally zi'.

Gradient selection

Each simplex vertex is added back to the skewed hypercube's base coordinate, and hashed into a pseudo-random gradient direction. The hash can be implemented in numerous ways, though most often uses a permutation table or a bit manipulation scheme.

Care should be taken in the selection of the set of gradients to include, in order to keep directional artifacts to a minimum.

Kernel summation

The contribution from each of the n + 1 vertices of the simplex is factored in by a summation of radially symmetric kernels centered around each vertex. First, the unskewed coordinate of each of the vertices is determined using the inverse formula

where

This point is subtracted from the input coordinate in order to obtain the unskewed displacement vector. This unskewed displacement vector is used for two purposes:

From there, each vertex's summed kernel contribution is determined using the equation

where r2 is usually set to either 0.5 or 0.6: the value 0.5 ensures no discontinuities, whereas 0.6 may increase visual quality in applications for which the discontinuities are not noticeable; 0.6 was used in Ken Perlin's original reference implementation.

Uses of implementations in 3D and higher for textured image synthesis are covered by U.S. Patent 6,867,776 , if the algorithm is implemented using the specific techniques described in any of the patent claims. The patent is expected to expire on January 8, 2022.

See also

Related Research Articles

Curl (mathematics) Vector operator describing circulation density at a point in a 3D vector field

In vector calculus, the curl is a vector operator that describes the infinitesimal circulation of a vector field in three-dimensional Euclidean space. The curl at a point in the field is represented by a vector whose length and direction denote the magnitude and axis of the maximum circulation. The curl of a field is formally defined as the circulation density at each point of the field.

Cube A geometric 3-dimensional object with 6 square faces

In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex.

In elementary geometry, a polytope is a geometric object with "flat" sides. It is a generalization in any number of dimensions of the three-dimensional polyhedron. Polytopes may exist in any general number of dimensions n as an n-dimensional polytope or n-polytope. Flat sides mean that the sides of a (k+1)-polytope consist of k-polytopes that may have (k−1)-polytopes in common. For example, a two-dimensional polygon is a 2-polytope and a three-dimensional polyhedron is a 3-polytope.

In geometry, a polygon is a plane figure that is described by a finite number of straight line segments connected to form a closed polygonal chain. The bounded plane region, the bounding circuit, or the two together, may be called a polygon.

Tetrahedron Polyhedron with 4 faces

In geometry, a tetrahedron, also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the ordinary convex polyhedra and the only one that has fewer than 5 faces.

Tesseract Four-dimensional analogue of the cube

In geometry, the tesseract is the four-dimensional analogue of the cube; the tesseract is to the cube as the cube is to the square. Just as the surface of the cube consists of six square faces, the hypersurface of the tesseract consists of eight cubical cells. The tesseract is one of the six convex regular 4-polytopes.

Simplex Multi-dimensional generalization of triangle

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given space.

Hypercube Convex polytope, the n-dimensional analogue of a square and a cube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube. It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length. A unit hypercube's longest diagonal in n dimensions is equal to .

Perlin noise Type of gradient noise in computer graphics

Perlin noise is a type of gradient noise developed by Ken Perlin.

Linear separability

In Euclidean geometry, linear separability is a property of two sets of points. This is most easily visualized in two dimensions by thinking of one set of points as being colored blue and the other set of points as being colored red. These two sets are linearly separable if there exists at least one line in the plane with all of the blue points on one side of the line and all the red points on the other side. This idea immediately generalizes to higher-dimensional Euclidean spaces if the line is replaced by a hyperplane.

Barycentric coordinate system Coordinate system that is defined by points instead of vectors

In geometry, a barycentric coordinate system is a coordinate system in which the location of a point is specified by reference to a simplex. The barycentric coordinates of a point can be interpreted as masses placed at the vertices of the simplex, such that the point is the center of mass of these masses. These masses can be zero or negative; they are all positive if and only if the point is inside the simplex.

Real coordinate space Space formed by the n-tuples of real numbers

In mathematics, a real coordinate space of dimension n, written Rn or , is a coordinate space over the real numbers. This means that it is the set of the n-tuples of real numbers. With component-wise addition and scalar multiplication, it is a real vector space.

Duoprism

In geometry of 4 dimensions or higher, a duoprism is a polytope resulting from the Cartesian product of two polytopes, each of two dimensions or higher. The Cartesian product of an n-polytope and an m-polytope is an (n+m)-polytope, where n and m are 2 (polygon) or higher.

Three-dimensional space Geometric model of the physical space

Three-dimensional space is a geometric setting in which three values are required to determine the position of an element. This is the informal meaning of the term dimension.

Regular grid

A regular grid is a tessellation of n-dimensional Euclidean space by congruent parallelotopes. Grids of this type appear on graph paper and may be used in finite element analysis, finite volume methods, finite difference methods, and in general for discretization of parameter spaces. Since the derivatives of field variables can be conveniently expressed as finite differences, structured grids mainly appear in finite difference methods. Unstructured grids offer more flexibility than structured grids and hence are very useful in finite element and finite volume methods.

Demihypercube Polytope constructed from alternation of an hypercube

In geometry, demihypercubes are a class of n-polytopes constructed from alternation of an n-hypercube, labeled as n for being half of the hypercube family, γn. Half of the vertices are deleted and new facets are formed. The 2n facets become 2n(n-1)-demicubes, and 2n(n-1)-simplex facets are formed in place of the deleted vertices.

Simplicial continuation, or piecewise linear continuation, is a one-parameter continuation method which is well suited to small to medium embedding spaces. The algorithm has been generalized to compute higher-dimensional manifolds by and.

In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels. Such a labeling is called a Hamming labeling; it represents an isometric embedding of the partial cube into a hypercube.

Simplectic honeycomb

In geometry, the simplectic honeycomb is a dimensional infinite series of honeycombs, based on the affine Coxeter group symmetry. It is given a Schläfli symbol {3[n+1]}, and is represented by a Coxeter-Dynkin diagram as a cyclic graph of n+1 nodes with one node ringed. It is composed of n-simplex facets, along with all rectified n-simplices. It can be thought of as an n-dimensional hypercubic honeycomb that has been subdivided along all hyperplanes , then stretched along its main diagonal until the simplices on the ends of the hypercubes become regular. The vertex figure of an n-simplex honeycomb is an expanded n-simplex.

OpenSimplex noise N-dimensional gradient noise function

OpenSimplex noise is an n-dimensional gradient noise function that was developed in order to overcome the patent-related issues surrounding simplex noise, while likewise avoiding the visually-significant directional artifacts characteristic of Perlin noise.

References

  1. Ken Perlin, Noise hardware. In Real-Time Shading SIGGRAPH Course Notes (2001), Olano M., (Ed.). (pdf)
  2. Ken Perlin, Making noise. Based on a talk presented at GDCHardcore (Dec 9, 1999). (url)
  3. "image processing - Why does increasing simplex noise dimension wash it out?". Computer Graphics Stack Exchange. Retrieved 2021-03-10.