2D Point Sequences

Way back in 2007, Robert Bridson came up with an elegant way of generating a well-distributed set of points (D3 animations here and here). This algorithm is awesome for a number of reasons, one of which being that it can create points with arbitrary dimensionality. However it should be noted that it does not create progressive sequences. In a progressive sequence, points are ordered such that any subset consisting of the first N points is Poisson disk distributed over the entire range.

The Recursive Wang Tiles method for generating blue noise (Kopf 2006) can quickly generate a progressive sequence by consuming a small set of pre-generated tiles. On the downside, these tiles are complex to construct.

Here’s a single-file C library that implements the real-time portion of the Recursive Wang Tiles algorithm (as opposed to tile construction).

To show off the library, I used emscripten to create the two demos on this page. Below are links to the density textures used in these demos.

Demo #1: Continuous Generation

First let’s try executing the sequence generator on every frame of camera movement. Try dragging and scrolling inside the canvas, similar to Google Maps. If you get lost, refresh the page.

Loading...


The above demo is continuously re-generating a subset of a truly infinite point sequence (well, until you run into floating-point precision issues). If you have a decent machine, this is basically real-time.

Demo #2: Static Vertex Buffer

For a much faster frame rate, you can generate a bunch of samples ahead of time, and bake them out to a static vertex buffer. By simply changing the draw range within the vertex buffer during camera movement, you can achieve a similar effect with very little CPU overhead.

The following demo uses a vertex buffer with about 1.4 million points, but you can only see a small number of them at a time. Try zooming on the coastline. Again, if you get lost, refresh the page.

Loading...


References

Philip Rideout
October 2015