Vertex Queue Area Generation for Gradient Noise

Proof of concept. Generates gradient noise over a specified area (using a vertex queue and not a "range"), with the goal of increasing performance.

The first idea I thought of was to simply iterate over skewed lattice coordinates. That wouldn't have been very good for generating slices of higher dimensional noise, though, at least outside of certain grid rotations. There is also a company that wants to reserve it for themselves. I want to make sure everybody has access to speed-optimized gradient noise for whole-area generation, so I spent some time and came up with this instead.

Algorithm

1. Define your image/buffer/array with a shape and size.
2. Use the frequency scaling (+ any other transforms) to pre-generate the contribution falloff.
3. Define the offset for the noise generation (e.g. if generating large tiles of an even larger world).
4. Start at one point on the image. I chose to start on the lowest corner. Skew the point into noise lattice coordinate space (including transforms such as frequency scaling).
5. Pick a nearby point/vertex on the skewed noise lattice. Add it to the queue and the "seen" set. The chosen point should either contribute directly to the image, or have at least one neighbor that does.
6. While the queue is not empty, loop:
   1. Pop off one point to process.
   2. Loop over and add its contribution anywhere necessary, to the image/array/buffer.
   3. For all of its defined "neighbors" (e.g. in 2D this could be the hexagon surrounding the point)
      1. If that neighbor is within contribution distance of the image/array/buffer, and is also not in the "seen" set, add it to the queue and set.

Usage

Demo

1. javac NoiseDemo.java
2. java NoiseDemo

Your own project

1. Add OpenSimplex2F or OpenSimplex2S to your project.
2. Initialize it with a seed, and call OpenSimplex2X.GenerateContext#D (e.g. OpenSimplex2S.GenerateContext3D) with a lattice orientation (domain rotation), a frequency scaling, and an amplitude.
3. Define a multidimensional array of the form double[][] for 2D or double[][][] for 3D with a constant dimensions.
4. Call generate2(...) or generate3(...) providing your array, context, and X/Y offsets.
   • The X/Y offsets are in image coordinate space. Generating an offset of (512, 0) while filling a 512x512 buffer will generate the tile adjacent to the one generated by (0, 0).

Notes:

• The array is not cleared when generate#D(...) is called. This means you will need to either clear it yourself or initialize a new one. Otherwise, the generator will add its results to the existing values (which could be useful sometimes!).
• The output can sometimes slightly exceed -1 and 1. While it is based off of a traditional evaluator that was properly normalized, the grid-snapping of the pre-generated falloffs introduces some slight variation in the results. Accounting for this dynamically depending on frequency would have been more difficult than pre-computing a normalization constant, though it is still an interesting problem.

Results

Noise

Subtle differences compared to point evaluation.

The biggest performance improvement came from pre-generating the falloff function. The side effect is that it becomes snapped into alignment with the image pixel grid. In practice, the differences are not visible. But they can be visualized with direct comparisons to traditional point-evaluated noise.

Performance

Seems great for large areas (1024x1024 - 8192x8192) and low relative frequencies. Seems fine for moderately size areas (64x64) with high relative frequencies. Seems not very good for very small areas (16x16) and any frequency.

Perhaps pre-generating the falloff function for noise that otherwise uses traditional point evaluation would be an interesting experiment.

Versus FastNoise (not FastNoiseSIMD/FastNoise2/FastNoiseLite)

Possible extensions and related ideas

• Accept an amplitude scaling constant to better faciliate octave summation. The GenerateContext2D can bake this into the pre-generated falloff. Implemented
• Support domain rotation and independent axis scaling (arbitrary linear transforms). This example only includes a single frequency scaling for both axes. Implemented
• If using octaves, associate each point from the higher frequencies with one (nearest?) point from the lowest frequency, and process them all together.
• Write a 3D version (BCC or OpenSimplex) Implemented
• Try it with the torus trick in 4D. This technique should work better for that than iterating over skewed lattice coordinates. Will probably require re-parameterizing the falloff function.
• The above, but with various map projections such as geodesic dome tiles, cylindrical maps, etc. One could also define noise directly on a sphere, by determining a polyhedron (e.g. geodesic dome) whose vertices are assigned falloffs not unlike the familiar ones, with gradients defined along whichever geometry is most practical. Though, vertex intransitivity may create visible artifacts.
• Support differently-shaped and differently-laid-out destination images/arrays/buffers. Hex grids, triangular sections of images, etc.
• This might not lend well to domain warping in general. However, if the amount of displacement is limited, then increasing the checked contribution radius by the maximum displacement should suffice.
• Should work just fine on a regular hypercube grid (Perlin) if necessary -- use a domain-rotated grid for best visual results!
• Could probably experiment with only checking some of the neighbors, or checking more than just the direct neighbors, for some lattices. I imagine this decision is similiar to choosing between 4-point and 8-point flood-fill from an efficiency standpoint.
• Evaluate to multiple images/arrays/buffers simultaneously, but with different seeds or other parameters.
• Group up points in hexes like this. Each hex is processed as one unit. Should work in higher dimensions too -- just consider the vectors between centers of hexes and try to generalize those. Might improve efficiency by reducing queue and set invocations, and enable group contribution addition in a single loop.
• Perhaps pregenerate another sparse lattice (cubic, simplex, simplectic, or other) where each cell (plane-bounded, or voronoi, etc.) accumulates a list of contributing points for the region it covers. Then apply all of those points over that region.
• Try a pregenerated falloff of sufficient resolution on standard point-evaluation noise. I didn't see the speed improvements in this one until I pregenerated the falloff.
• Apply it to value-noise of some sort.
• Jitter the points
• Perform on points produced by Poisson disc sampling or other blue noise distributions.

Philosophy

This software is released under an open source license. With this license, you can use it for just about anything: independent projects, commercial projects, education, redistributable libraries, etc. Use this to make cool things!

The original reason I created this repository was to provide an immediate alternative to a scope-hungry software patent that was in the application process. That application has since been withdrawn, but software patents present an ongoing threat to the software development community.

• http://endsoftpatents.org/
• http://en.swpat.org/wiki/Why_abolish_software_patents
• https://www.eff.org/deeplinks/2012/06/want-abolish-software-patents-tell-us
• https://www.wired.com/2015/02/eff-eliminate-software-patents/