A randomly distributed sets of points can be considered as the lowest state of architectural order; the placing of the simplest object, a point, with the least degree of structure, being randomly placed.

Well distributed point sets are important in several areas of computer graphics. These include anti-aliasing, global illumination, non-photorealistic rendering, point based modelling and rendering.

Point based modelling corresponds most closely to the architectural case.

In many applications it is also desirable that the distribution is scalable, that is stays the same at all scales.

The section immediately below follows “Hierarchical Poisson disk sampling distributions” (McCool and Fiume, 1992) and uses their diagrams.

A Poisson or Random Distribution

A Poisson Distribution is one in which  each event is entirely independent and when thought of spatially the effect is of each point being randomly selected. This is the state of least order although determined by a simple rule.

Figure 1. Poisson Distribution

Visually this is lumpy, appears to have clusters and lacks smoothness. Requiring the points to be at least a minimum distance apart improves this and provides an initial level of ordering.

Poisson Disk Distribution

A Poisson Disk Distribution requires that no two points are less than a minimum distance apart.

Figure 2. Dart Throwing Algorithm

This is visually smoother, but in theory to get a  true Poisson Disk Distribution one must continue generating Poisson Distributions until one hits upon one with the requisite separations, an awkward procedure with no guarantee of success.

Dart Throwing Algorithm

With the Dart Throwing Algorithm points are placed sequentially and checked against all the points that have already been added, if a point is too near to any previously placed point it is simply discarded. The process continues until the required number of points have been placed or no other points can be added (after very many attempts).

Importantly the sequential nature of this algorithm means that the points can be indexed and the density of the distribution simply manipulated by including only the necessary number of points to achieve the required density. This is possible because all points have the same status; they have all been randomly selected.

Figure 2. actually shows a distribution arrived at using the Dart Throwing Algorithm. Circles are drawn in the centre tile showing in this case a separation of 0.1 (disk diameter).

Relaxation

In fact there is no requirement that the separation distance remains constant, one can start with a large separation, say 0.3, and at each iteration reduce it by a factor slightly less than 1, as shown in Figure 4. below. Note that the current (smaller) disk size can be used for all distance comparisons as the aim is produce a distribution with a single minimum separation.

Figure 4: Poisson Disk Distribution with Relaxation

Another type of relaxation due to Lloyd generates the Voronoi diagram of the distributed points and then moves each point to the centroid of its Voronoi cell, a process that can be repeated until changes become minimal.

Figure 5: Lloyd Relaxation

The effectiveness and in particular the speed of convergence of this procedure depends upon the distribution of the initial points. Dart Throwing followed by Lloyd relaxation is therefore a good strategy.

Some work has been done on the aesthetics of distribution sets with varying degrees of relaxation (Duessen, 2009).

Blue Noise Point Sets

Blue noise has few low-frequency components that can be interpreted as artefacts. It is thought to be an appropriate model of smooth distribution because it corresponds to the distribution of cones in the retina. It is surmised that this distribution evolved as a efficient method of receiving light in an even manner.

What follows is based on “Recursive Wang tiles for real-time blue noise” (Kopf, Cohen-Or, Deussen et al 2006) which itself makes use of a Relaxed Dart Throwing Algorithm, as described above, at least as a means of generating initial stochastic point distributions, and the ability to easily select point sets of different densities sharing common points. It also makes use of Wang aperiodic tiling using a small set of  tiles to avoid repetition and creates a set of recursive tiles to achieve this at different scales

Figure 6. below contrasts uniform blue noise point sets generated using periodic tiling (top row), aperiodic Penrose tiling (middle row) and aperiodic Wang tiling (bottom row).

The red and blue diagrams to the right show the mean radial power (red) and radial anisotropy plots (blue). The anisotropy spectrum is a measure of the angular regularity of the distribution.

In the top row the repetitions due to the periodic tiling are easily seen. The energy of the spectrum is quite evenly distributed but the anisotropy is strong.

The energy of the Penrose tiling version displays strong spikes resulting in extreme anisotropy values. The spectrum reveals the rotational ten-fold symmetry of the Penrose tiling which can be seen as an artefact in the rendering.

The Wang tiling version displays few repetitions in the rendering or the spectrum. The energy is well distributed in the spectrum and the anisotropy is very low.

Progressive Blue Noise Tiles

The aim is to produce a set of Wang tiles whose edges blend seamlessly together accross their point distributions and that can be calculated just once and then reused.

The Relaxed Dart Throwing Algorithm is used to produce a unique distribution for each tile and each colour of a Wang tile set.

The point distribution of each tile is then recalculated using its own distribution and the distributions of its four edge colours.

The tile distribution is combined in turn with the distributions of each of its four edge colours. This is done by combining the 2 point sets, generating the Voronoi  diagram of the combined set, giving high cost to points which are very close together and then calculating the shortest path between appropriate tile corners. The shortest path is then used to separate the two point sets and the sequencing of the combined points recalculated. As can be seen after all four edge colour distributions have been combined in this way much of the original tile distribution remains, but smooth transitions to adjacent (same colour) edged tiles has been achieved.

Recursive Wang Tiles

In order to make the point distributions scalable a set of recursive Wang tiles is generated by coding the edges as shown below, a process that can carry on endlessly.

In order to ensure smooth frame coherence for real time movement some points are relaxed between scales, the whole process is nicely covered in the following clip.

Bibliography