Claudio Bustamante
Jittered grid (stratified points): In IslandsRejilla con jitter (puntos estratificados): En IslandsLow-discrepancy sequences (Halton, Sobol', golden ratio): Web prototypeSecuencias de baja discrepancia (Halton, Sobol', razón áurea): Prototipo webPoisson disk sampling: Web prototypeMuestreo de disco de Poisson: Prototipo webLloyd relaxation: Web prototypeRelajación de Lloyd: Prototipo web

"Web prototype": the code on this page is a JavaScript study; Islands does not have it yet.«Prototipo web»: el código de esta página es un estudio en JavaScript; Islands todavía no lo tiene.

Spreading Points on a Line

Trees in a forest, towns on a map, stars in a sky: procedural worlds keep needing points that look random but not clumpy. Before the plane, the line, where every method fits in one row and the numbers are exact. Change the count, the seed and the relaxation steps, tap a row, and press Add one by one to see which methods keep the points they already placed. How it works.

Árboles en un bosque, pueblos en un mapa, estrellas en el cielo: los mundos procedurales necesitan una y otra vez puntos que parezcan aleatorios pero sin amontonarse. Antes del plano, la recta, donde cada método cabe en una fila y los números son exactos. Cambia la cantidad, la semilla y los pasos de relajación, toca una fila y pulsa Añadir uno a uno para ver qué métodos conservan los puntos que ya colocaron. Cómo funciona.

Selected row: share of points left of x minus x. Green band: the best any set of n points can do. Dashed: its worst deviation, the star discrepancy.Fila elegida: fracción de puntos a la izquierda de x menos x. Banda verde: lo mejor que puede hacer cualquier conjunto de n puntos. Discontinua: su peor desviación, la discrepancia estrella.

The idea in plain words

Scattering points "at random" gives clumps and holes, and lining them up gives a pattern the eye spots at once. Every method on this page is a different compromise between those two failures, and the four numbers in the table say exactly where each one lands.

Think of people sitting down on a long bench. If each picks a spot blindly, some end up shoulder to shoulder while a stretch stays empty: that is the top row. If each one keeps an arm's length from whoever is already seated, you get the Poisson disk row. The analogy has limits. People can see the whole bench and shuffle along, which is closer to Lloyd's relaxation, and real people do not draw their next spot from a hash.

Look at the orange stretch in each row: the largest gap. In the top row it is several grid steps long; in the others it shrinks towards one. Then press Add one by one. In the uniform, van der Corput and golden-ratio rows the old points stay where they were, while the grid, the jittered grid, Poisson disk and Lloyd rearrange everything as n grows.

Why it matters

A world generator places trees, rocks, towns and resource nodes, and it also picks the points that Voronoi noise grows its cells around. Clumps look wrong and holes waste space; a regular grid looks artificial. What you want is usually "random, but never too close", which graphics calls blue noise. Cook (1986) argued for it in image sampling, pointing to Yellott's (1983) finding that the photoreceptors of the rhesus monkey retina are spread this way, and Mitchell (1987) gave a fast way to approximate it.

The catch is that "evenly spread" means two different things, and no method wins both. Local evenness is about neighbours: the closest pair and the largest gap. Global evenness is about counts: does every stretch of the line hold its fair share of points? That is what discrepancy measures. Poisson disk is excellent locally and mediocre globally; van der Corput is the reverse. And for a world built in chunks, a third property matters: can a point be computed from its seed and position alone, without knowing the others? Only the hash-based rows can. The design note at the end of the walkthrough comes back to this.

Is there a theorem?

Several, and on a line they settle most questions. For sorted points, the star discrepancy has an exact formula (Niederreiter 1992, Theorem 2.6), given below. It shows at once that no set of n points does better than 1/(2n), and that the centred grid reaches it. It also proves a property of the jittered grid: each point stays inside its own cell, so its discrepancy never exceeds 1/n, whatever the seed. The table confirms it: the D* column for that row never passes 1.00.

Sequences, where points keep being added, are harder. Schmidt (1972) proved that no infinite sequence can keep n·D* bounded: it must reach about log n again and again. Van der Corput's sequence (1935) grows only that fast, which is as good as it gets. For the golden-ratio sequence, the three-gap theorem (Steinhaus's conjecture, proved by Sós and by Świerczkowski in the late 1950s; see Marklof and Strömbergsson 2017) says that n points i·α mod 1 on a circle leave gaps of at most three different lengths.

For uniform random points, the largest gap is about (ln n + γ)/n on average, where γ ≈ 0.577; Pyke (1965) reviews this and finer results. For Lloyd's relaxation in 1D, the only centroidal arrangement, where every point sits at the centre of its cell, is the centred grid, so that is where it ends up (Du, Faber and Gunzburger 1999). How long that takes is another matter, measured below.

The equations

Points x₁ ≤ x₂ ≤ … ≤ xn in [0, 1), sorted. A "grid step" is 1/n; the table multiplies every distance by n.

  • Star discrepancy: D*n = supx | #{xi < x}/n − x | = 1/(2n) + maxi | xi − (2i − 1)/(2n) |
  • Jittered grid: xi = (i + ui)/n, ui uniform in [0, 1)
  • Van der Corput: if i = Σ bk 2k, then xi = Σ bk 2−k−1
  • Golden ratio: xi = frac(x₀ + i·α), α = (√5 − 1)/2 ≈ 0.618
  • Poisson disk: |xi − xj| ≥ r for every pair
  • Lloyd step: xi ← (mi−1 + mi)/2, with mi = (xi + xi+1)/2, m₀ = 0, mn = 1

Read the first equation as a contest between two shares. Pick any point x on the line. The share of the line to its left is x; the share of the points to its left is a count divided by n. Discrepancy is the worst mismatch over every x. The lower canvas draws that mismatch for the selected row, and the dashed lines mark its worst value. Readers who know statistics will recognise it: it is the Kolmogorov–Smirnov statistic against the uniform distribution.

What the numbers say

Measured with this page's code, 20 seeds each, for 50, 100 and 200 points:

  • Uniform random: the closest pair falls to 0.03, then 0.01, then 0.00 steps: two points almost on top of each other. D*·n grows from 5.9 to 8.8 to 13, roughly as √n. The largest gap, 4.4 to 5.7 steps, follows ln n + γ (4.5, 5.2, 5.9).
  • Jittered grid: D*·n between 0.94 and 1.00, as the theorem says. The largest gap is always under 2 steps (two neighbours at the far ends of their cells), but the closest pair is only 0.11 to 0.17 steps on average.
  • Van der Corput: at a power of two it is a shifted grid, with every gap exactly one step. In between, the closest pair is 0.78 and the largest gap 1.56. Its worst D*·n for any n up to 256 is 3.45, and it keeps growing, slowly, like log n.
  • Golden ratio: three gap lengths, as promised; the closest pair stays between 0.50 and 0.66, and D*·n stays under 2 for every n up to 256.
  • Poisson disk with r = 2/(3n): 47 to 54 points when 50 are asked for, so the count drifts. The closest pair is 0.67 by construction and the largest gap about 1.33. But D*·n grows, from 1.5 to 2.2 to 2.7: the gaps are random, and their errors add up along the line.
  • Lloyd: after 100 steps the mean spacing is 0.99 and the closest pair 0.72, yet D*·n is still 6.5 for 100 points, barely better than the random start. Reaching D*·n below 0.6 took about 250 steps for 16 points, 1,100 for 32 and 4,700 for 64: four times the work every time n doubles.

What the picture does and does not say

  • On a line, ordering points is trivial, so all the measures are exact. In the plane they are not: the exact discrepancy becomes expensive, and the next page will have to estimate it.
  • D* only tests stretches that start at 0. A set can score well on it and still have a clump in the middle of the line; the gap and closest-pair columns are there for that.
  • Poisson disk here is nearly, not exactly, maximal. With Bridson's 30 tries per point, some gaps reach 1.42 steps, a little above the 2r = 1.33 a maximal set would allow.
  • Islands' jittered grid reads one byte of the hash, so a point can sit at one of 256 positions in its cell, both edges included. Two points in neighbouring cells can therefore coincide exactly, about once in 65,536 neighbouring pairs. This page uses all 32 bits.
  • Only the jittered grid exists in Islands. Every other row is a JavaScript prototype for this page.

How it works

This part walks through the code of the scene, step by step. It covers:

  • Getting repeatable random numbers from a hash.
  • Three simple ways to place points: chance, grid and jittered grid.
  • Measuring a point set with four numbers.
  • Two low-discrepancy sequences: van der Corput and the golden ratio.
  • Bridson's Poisson disk sampling, in one dimension.
  • Lloyd's relaxation, and why it is slow.
  • Drawing the discrepancy.

Plain JavaScript and the Canvas 2D API, no libraries. The point methods and the measures are about 130 lines; the scene about 230.

1. Random numbers from a hash

Math.random() cannot be seeded, and it hands out numbers in order: point 50 depends on the 49 before it. The hash from part 1 has neither problem. Feed it the seed, the point's index and a "salt" per method, so the methods do not share their random numbers, and divide by 232. 

// A uniform number in [0, 1) from (seed, index, salt). Full 32 bits, not one byte.
export function u01(s, i, salt) {
  return avalanche(eat(eat(seed(s), i), salt)) / 4294967296;
}

2. Chance, grid and jittered grid

The first three methods are one line each. The grid puts point i in the middle of cell i; the jittered grid puts it anywhere inside that cell. That is the method Islands uses for Voronoi noise, one point per lattice cell. 

export function uniform(n, s) {
  return Array.from({ length: n }, (_, i) => u01(s, i, 0));
}

export function grid(n) {
  return Array.from({ length: n }, (_, i) => (i + 0.5) / n);
}

// One point per cell, anywhere inside it (stratified sampling).
export function jittered(n, s) {
  return Array.from({ length: n }, (_, i) => (i + u01(s, i, 1)) / n);
}

Compare the first three rows. The jittered grid has no large holes, since every cell holds a point, but two neighbours can still land almost together at a cell border: look for the blue pair.

3. Four numbers

Everything is measured on the sorted points. The closest pair and the mean distance to the nearest neighbour describe local spacing. The largest gap counts the ends of the line too, because a world has edges. The discrepancy uses the exact formula: walking the sorted points once is enough. 

export function measure(points) {
  const x = [...points].sort((a, b) => a - b);
  const n = x.length;
  let minNN = Infinity, sumNN = 0, maxGap = x[0], gapAt = 0, dstar = 0, dAt = 0;
  for (let i = 0; i < n; i++) {
    const l = i > 0 ? x[i] - x[i - 1] : Infinity;
    const r = i + 1 < n ? x[i + 1] - x[i] : Infinity;
    const nn = Math.min(l, r);
    if (n > 1) { minNN = Math.min(minNN, nn); sumNN += nn; }
    const gap = i + 1 < n ? r : 1 - x[i];
    if (gap > maxGap) { maxGap = gap; gapAt = i + 1; }
    // Exact star discrepancy in 1D: 1/(2n) + max |x(i) − (2i − 1)/(2n)| (i from 1).
    const dev = Math.abs(x[i] - (2 * i + 1) / (2 * n));
    if (dev > dstar) { dstar = dev; dAt = i; }
  }
  return {
    …
    dstar: (1 / (2 * n) + dstar) * n,
    maxGap: maxGap * n,
    …
  };
}
Why multiply everything by n?

So that sets of different sizes can be compared. Times n, a perfect grid scores 1 on spacing and 0.5 on discrepancy whatever its size, and a number that grows with n, like the random gap, shows a method that gets relatively worse as it gets bigger.

4. Van der Corput: mirror the digits

Write the index in binary, mirror its digits about the point, and read the result as a fraction. Index 1 gives 0.5, 2 gives 0.25, 3 gives 0.75: each new point falls into the largest hole left so far. In one dimension this is also the Halton sequence in base 2 and the first dimension of Sobol's, which is why one row stands for all three. 

// Base-2 radical inverse: mirror the binary digits of i about the point.
// 1 → 0.1₂ = 0.5, 2 → 0.01₂ = 0.25, 3 → 0.11₂ = 0.75…
export function radicalInverse2(i) {
  let r = 0, f = 0.5;
  for (; i > 0; i >>>= 1, f *= 0.5) if (i & 1) r += f;
  return r;
}

// Van der Corput (Halton and Sobol' in 1D). The seed shifts the whole set round the
// circle (a Cranley–Patterson rotation), which keeps its spacing.
export function vanDerCorput(n, s) {
  const shift = s ? u01(s, 0, 2) : 0;
  return Array.from({ length: n }, (_, i) => frac(radicalInverse2(i) + shift));
}

The sequence has no randomness, so the seed shifts the whole set round the line as if it were a circle (Cranley and Patterson 1976). Set the seed to 0 to see the plain sequence, then drag Points across 32, 64 or 128: exactly at a power of two, the row becomes a perfect grid.

5. The golden ratio

The simplest low-discrepancy sequence keeps adding the same irrational step and wraps around. The golden ratio is the "most irrational" number, the hardest to approximate by fractions, so the points take longest to line up into a pattern. 

// Additive recurrence with the golden ratio (Weyl; Roberts' R1).
export const GOLDEN = (Math.sqrt(5) - 1) / 2;
export function golden(n, s) {
  const start = s ? u01(s, 0, 3) : 0.5;
  return Array.from({ length: n }, (_, i) => frac(start + i * GOLDEN));
}

6. Poisson disk, Bridson's way

The naive method, dart throwing, draws random points and rejects any that land too close to an earlier one; it slows down badly as the line fills up. Bridson (2007) grows the set outwards instead. An "active" list holds points that may still have room next to them. Pick one, try up to k candidates between r and 2r away, and keep the first that fits; if none fits, retire the point. A background grid with cells of size r holds at most one point per cell, so checking a candidate only needs the three nearest cells. 

export function poissonDisk(r, s, k = 30) {
  const cells = Math.ceil(1 / r);
  const grid = new Array(cells).fill(-1);
  const points = [], active = [];
  let draw = 0;
  const rnd = () => u01(s, draw++, 4);

  const fits = (x) => {
    const c = Math.floor(x / r);
    for (let j = Math.max(0, c - 1); j <= Math.min(cells - 1, c + 1); j++) {
      if (grid[j] >= 0 && Math.abs(points[grid[j]] - x) < r) return false;
    }
    return true;
  };
  …
  add(rnd());
  while (active.length) {
    const a = Math.floor(rnd() * active.length);
    const p = points[active[a]];
    let placed = false;
    for (let t = 0; t < k && !placed; t++) {
      // A candidate between r and 2r away, on either side.
      const d = r * (1 + rnd()) * (rnd() < 0.5 ? -1 : 1);
      const x = p + d;
      if (x >= 0 && x < 1 && fits(x)) { add(x); placed = true; }
    }
    if (!placed) active.splice(a, 1);   // no room left around p
  }
  return points;
}

The number of points is not an input: it comes out of r. On a line the gaps end up between r and 2r, so the scene picks r to land near the requested count, and the row label says how many points it actually got. 

// r = 2 / (3n) gives about n points: in 1D the gaps fall between r and 2r.
{ id: "poisson", …, make: (n, s) => poissonDisk(2 / (3 * n), s) },
Why is Poisson disk hard for a chunked world?

Each point depends on the points accepted before it, so the result depends on the order of the work. Compute two neighbouring chunks separately and their points can end up too close at the seam; compute them together and you no longer have independent chunks. The grid-and-hash methods above have no such problem. Wei (2008) parallelised Poisson disk sampling on the GPU by processing grid cells in phases that cannot conflict; Lagae and Dutré (2008) compare that family of methods with tiling approaches.

7. Lloyd: move to the middle, repeat

Lloyd's algorithm comes from signal quantisation (Lloyd 1982). Give each point the stretch of line closer to it than to any other point, its Voronoi cell, then move the point to the middle of that stretch. Repeat. Every step uses the old positions, so the loop only needs to remember the boundary it has just computed. 

export function lloyd(n, s, iterations) {
  const x = uniform(n, s).sort((a, b) => a - b);
  for (let it = 0; it < iterations; it++) {
    let left = 0;
    for (let i = 0; i < n; i++) {
      const right = i + 1 < n ? (x[i] + x[i + 1]) / 2 : 1;
      x[i] = (left + right) / 2;
      left = right;   // already computed from the old x[i + 1] and the old x[i]
    }
  }
  return x;
}

Drag Lloyd steps up. The blue pair separates within a few steps, while the D* column hardly moves until hundreds of steps. Each step only passes information to neighbours, so a surplus of points at one end of the line spreads like heat, one cell at a time.

8. Drawing the discrepancy

The lower canvas plots the share of points to the left of x minus x itself. Between two points it falls with slope −1; at each point it jumps up by 1/n. The green band is ±1/(2n), what the centred grid achieves. 

// The staircase: falls with slope −1 between points, jumps up 1/n at each point.
dctx.moveTo(px(0), py(0));
for (let i = 0; i < n; i++) {
  const x = sorted[i];
  dctx.lineTo(px(x), py(i / n - x));
  dctx.lineTo(px(x), py((i + 1) / n - x));
}
dctx.lineTo(px(1), py(0));

Select the uniform row and watch the curve wander far from zero. That wandering is a random walk, which is why its size grows as √n.

A note for Islands

Islands generates deterministically, runs its noise in parallel with Burst, and may move to chunks with Phase W. Measured against those three constraints:

  • Jittered grid fits all three: one hash per cell, any cell on its own, no seams. It is already there. Its weak spot is the closest pair.
  • Low-discrepancy sequences are deterministic and computed by index, so they parallelise, but they cover one global domain. Per chunk they need their own shift or scrambling, and nothing keeps points apart across a seam.
  • Poisson disk gives the best local spacing but depends on the order of work. The chunk-friendly variant to try first: one jittered candidate per grid cell with a hashed priority; a candidate survives if no higher-priority candidate lies within r. That decision only looks at nearby cells, so it is deterministic, parallel and the same on both sides of a seam. The result is sparser and less even than Bridson's, which is a trade-off to measure on the 2D page.
  • Lloyd is iterative and global: useful offline to polish a small set, wrong for streaming.

See it in practice in Hillside: an endless landscape built in chunks, where you can switch between these methods and watch the seams.

Going further

  • Go to the plane: Halton in bases 2 and 3, Bridson in 2D and the radial spectrum that gives blue noise its name. That is the next page.
  • Implement the hashed-priority Poisson variant above and compare it with Bridson on the same four numbers.
  • Scramble van der Corput with a hash, digit by digit (Owen 1995), instead of shifting it, and see whether the power-of-two grids survive.

La idea en palabras sencillas

Si se reparten puntos «al azar», salen montones y huecos; si se alinean, sale un patrón que el ojo detecta enseguida. Cada método de esta página es un compromiso distinto entre esos dos fallos, y los cuatro números de la tabla dicen exactamente dónde cae cada uno.

Piensa en gente que se sienta en un banco largo. Si cada uno elige un sitio a ciegas, algunos quedan hombro con hombro mientras un tramo se queda vacío: es la primera fila. Si cada uno guarda un brazo de distancia con quien ya está sentado, sale la fila del disco de Poisson. La analogía tiene límites. La gente ve el banco entero y se va corriendo, que se parece más a la relajación de Lloyd, y nadie saca su próximo sitio de un hash.

Mira el tramo naranja de cada fila: el hueco mayor. En la primera mide varios pasos de rejilla; en las demás se acerca a uno. Luego pulsa Añadir uno a uno. En las filas de azar uniforme, Van der Corput y razón áurea, los puntos viejos se quedan donde estaban, mientras que la rejilla, la rejilla con jitter, el disco de Poisson y Lloyd lo reordenan todo a medida que crece n.

Por qué importa

Un generador de mundos coloca árboles, rocas, pueblos y recursos, y además elige los puntos alrededor de los que el ruido de Voronoi hace crecer sus celdas. Los montones quedan mal y los huecos desperdician espacio; una rejilla regular parece artificial. Lo que se busca suele ser «al azar, pero nunca demasiado cerca», lo que en gráficos se llama ruido azul. Cook (1986) lo defendió para el muestreo de imágenes, apoyándose en el hallazgo de Yellott (1983) de que los fotorreceptores de la retina del macaco rhesus se reparten así, y Mitchell (1987) dio una forma rápida de aproximarlo.

La trampa es que «bien repartido» quiere decir dos cosas distintas, y ningún método gana en las dos. La regularidad local trata de los vecinos: el par más cercano y el hueco mayor. La regularidad global trata de cuentas: ¿cada tramo de la recta tiene su parte justa de puntos? Eso es lo que mide la discrepancia. El disco de Poisson es excelente en lo local y mediocre en lo global; Van der Corput, al revés. Y para un mundo hecho por chunks importa una tercera propiedad: ¿se puede calcular un punto solo con su semilla y su posición, sin conocer los demás? Solo las filas basadas en el hash pueden. La nota de diseño al final del recorrido por el código vuelve sobre esto.

¿Hay un teorema?

Varios, y en una recta resuelven casi todas las preguntas. Para puntos ordenados, la discrepancia estrella tiene una fórmula exacta (Niederreiter 1992, teorema 2.6), que aparece abajo. Muestra de inmediato que ningún conjunto de n puntos baja de 1/(2n), y que la rejilla centrada lo alcanza. También demuestra una propiedad de la rejilla con jitter: cada punto se queda dentro de su celda, así que su discrepancia nunca pasa de 1/n, sea cual sea la semilla. La tabla lo confirma: la columna D* de esa fila nunca supera 1,00.

Las secuencias, donde se siguen añadiendo puntos, son más difíciles. Schmidt (1972) demostró que ninguna secuencia infinita puede mantener acotado n·D*: tiene que llegar a algo del orden de log n una y otra vez. La secuencia de Van der Corput (1935) crece solo así de rápido, que es lo mejor posible. Para la secuencia de la razón áurea, el teorema de los tres huecos (conjetura de Steinhaus, demostrada por Sós y por Świerczkowski a finales de los años cincuenta; véase Marklof y Strömbergsson 2017) dice que n puntos i·α mód 1 sobre una circunferencia dejan huecos de como mucho tres longitudes distintas.

Para puntos uniformes al azar, el hueco mayor es en promedio de unos (ln n + γ)/n, con γ ≈ 0,577; Pyke (1965) revisa este y otros resultados más finos. Para la relajación de Lloyd en 1D, la única disposición centroidal, en la que cada punto está en el centro de su celda, es la rejilla centrada, así que ahí termina (Du, Faber y Gunzburger 1999). Cuánto tarda es otra cuestión, medida abajo.

Las ecuaciones

Puntos x₁ ≤ x₂ ≤ … ≤ xn en [0, 1), ordenados. Un «paso de rejilla» es 1/n; la tabla multiplica cada distancia por n.

  • Discrepancia estrella: D*n = supx | #{xi < x}/n − x | = 1/(2n) + máxi | xi − (2i − 1)/(2n) |
  • Rejilla con jitter: xi = (i + ui)/n, ui uniforme en [0, 1)
  • Van der Corput: si i = Σ bk 2k, entonces xi = Σ bk 2−k−1
  • Razón áurea: xi = frac(x₀ + i·α), α = (√5 − 1)/2 ≈ 0,618
  • Disco de Poisson: |xi − xj| ≥ r para todo par
  • Paso de Lloyd: xi ← (mi−1 + mi)/2, con mi = (xi + xi+1)/2, m₀ = 0, mn = 1

Lee la primera ecuación como una competición entre dos fracciones. Elige cualquier punto x de la recta. La fracción de la recta a su izquierda es x; la fracción de los puntos a su izquierda es una cuenta dividida entre n. La discrepancia es el peor desajuste sobre todos los x. El lienzo de abajo dibuja ese desajuste para la fila elegida, y las líneas discontinuas marcan su peor valor. Quien sepa estadística lo reconocerá: es el estadístico de Kolmogórov-Smirnov frente a la distribución uniforme.

Qué dicen los números

Medido con el código de esta página, 20 semillas cada vez, para 50, 100 y 200 puntos:

  • Azar uniforme: el par más cercano cae a 0,03, luego 0,01 y luego 0,00 pasos: dos puntos casi encima. D*·n crece de 5,9 a 8,8 y a 13, más o menos como √n. El hueco mayor, de 4,4 a 5,7 pasos, sigue a ln n + γ (4,5; 5,2; 5,9).
  • Rejilla con jitter: D*·n entre 0,94 y 1,00, como dice el teorema. El hueco mayor siempre queda por debajo de 2 pasos (dos vecinos en los extremos opuestos de sus celdas), pero el par más cercano es en promedio de solo 0,11 a 0,17 pasos.
  • Van der Corput: en una potencia de dos es una rejilla desplazada, con todos los huecos de un paso exacto. Entre medias, el par más cercano es 0,78 y el hueco mayor 1,56. Su peor D*·n para cualquier n hasta 256 es 3,45, y sigue creciendo, despacio, como log n.
  • Razón áurea: tres longitudes de hueco, como se prometía; el par más cercano se queda entre 0,50 y 0,66, y D*·n por debajo de 2 para todo n hasta 256.
  • Disco de Poisson con r = 2/(3n): de 47 a 54 puntos cuando se piden 50, así que la cuenta varía. El par más cercano es 0,67 por construcción y el hueco mayor, unos 1,33. Pero D*·n crece, de 1,5 a 2,2 y a 2,7: los huecos son aleatorios y sus errores se acumulan a lo largo de la recta.
  • Lloyd: tras 100 pasos, la distancia media es 0,99 y el par más cercano 0,72, pero D*·n sigue en 6,5 para 100 puntos, apenas mejor que el punto de partida al azar. Bajar D*·n de 0,6 costó unos 250 pasos con 16 puntos, 1100 con 32 y 4700 con 64: cuatro veces más trabajo cada vez que n se duplica.

Qué dice y qué no dice la imagen

  • En una recta, ordenar los puntos es trivial, así que todas las medidas son exactas. En el plano no: la discrepancia exacta se vuelve cara, y la página siguiente tendrá que estimarla.
  • D* solo prueba tramos que empiezan en 0. Un conjunto puede puntuar bien y aun así tener un montón en mitad de la recta; para eso están las columnas del hueco y del par más cercano.
  • Aquí el disco de Poisson es casi maximal, no del todo. Con los 30 intentos por punto de Bridson, algunos huecos llegan a 1,42 pasos, algo por encima de los 2r = 1,33 que permitiría un conjunto maximal.
  • La rejilla con jitter de Islands lee un byte del hash, así que un punto puede caer en una de 256 posiciones de su celda, bordes incluidos. Por eso dos puntos de celdas vecinas pueden coincidir exactamente, más o menos una vez cada 65 536 pares vecinos. Esta página usa los 32 bits.
  • En Islands solo existe la rejilla con jitter. Todas las demás filas son prototipos en JavaScript hechos para esta página.

Cómo funciona

Esta parte recorre el código de la escena, paso a paso. Cubre:

  • Sacar números aleatorios repetibles de un hash.
  • Tres formas sencillas de colocar puntos: azar, rejilla y rejilla con jitter.
  • Medir un conjunto de puntos con cuatro números.
  • Dos secuencias de baja discrepancia: Van der Corput y la razón áurea.
  • El muestreo de disco de Poisson de Bridson, en una dimensión.
  • La relajación de Lloyd, y por qué es lenta.
  • Dibujar la discrepancia.

JavaScript sin más y la API Canvas 2D, sin librerías. Los métodos y las medidas ocupan unas 130 líneas; la escena, unas 230. Los comentarios del código están en inglés.

1. Números aleatorios a partir de un hash

Math.random() no admite semilla y reparte los números en orden: el punto 50 depende de los 49 anteriores. El hash de la parte 1 no tiene ninguno de esos problemas. Se le da la semilla, el índice del punto y una «sal» por método, para que los métodos no compartan sus números aleatorios, y se divide entre 232. 

// A uniform number in [0, 1) from (seed, index, salt). Full 32 bits, not one byte.
export function u01(s, i, salt) {
  return avalanche(eat(eat(seed(s), i), salt)) / 4294967296;
}

2. Azar, rejilla y rejilla con jitter

Los tres primeros métodos ocupan una línea cada uno. La rejilla pone el punto i en el centro de la celda i; la rejilla con jitter lo pone en cualquier sitio de esa celda. Es el método que usa Islands para el ruido de Voronoi, un punto por celda de la red. 

export function uniform(n, s) {
  return Array.from({ length: n }, (_, i) => u01(s, i, 0));
}

export function grid(n) {
  return Array.from({ length: n }, (_, i) => (i + 0.5) / n);
}

// One point per cell, anywhere inside it (stratified sampling).
export function jittered(n, s) {
  return Array.from({ length: n }, (_, i) => (i + u01(s, i, 1)) / n);
}

Compara las tres primeras filas. La rejilla con jitter no tiene huecos grandes, porque todas las celdas tienen un punto, pero dos vecinos aún pueden caer casi juntos en el borde entre celdas: busca el par azul.

3. Cuatro números

Todo se mide sobre los puntos ordenados. El par más cercano y la distancia media al vecino más próximo describen el espaciado local. El hueco mayor cuenta también los extremos de la recta, porque un mundo tiene bordes. La discrepancia usa la fórmula exacta: basta con recorrer una vez los puntos ordenados. 

export function measure(points) {
  const x = [...points].sort((a, b) => a - b);
  const n = x.length;
  let minNN = Infinity, sumNN = 0, maxGap = x[0], gapAt = 0, dstar = 0, dAt = 0;
  for (let i = 0; i < n; i++) {
    const l = i > 0 ? x[i] - x[i - 1] : Infinity;
    const r = i + 1 < n ? x[i + 1] - x[i] : Infinity;
    const nn = Math.min(l, r);
    if (n > 1) { minNN = Math.min(minNN, nn); sumNN += nn; }
    const gap = i + 1 < n ? r : 1 - x[i];
    if (gap > maxGap) { maxGap = gap; gapAt = i + 1; }
    // Exact star discrepancy in 1D: 1/(2n) + max |x(i) − (2i − 1)/(2n)| (i from 1).
    const dev = Math.abs(x[i] - (2 * i + 1) / (2 * n));
    if (dev > dstar) { dstar = dev; dAt = i; }
  }
  return {
    …
    dstar: (1 / (2 * n) + dstar) * n,
    maxGap: maxGap * n,
    …
  };
}
¿Por qué multiplicarlo todo por n?

Para poder comparar conjuntos de distinto tamaño. Multiplicada por n, una rejilla perfecta puntúa 1 en espaciado y 0,5 en discrepancia sea cual sea su tamaño, y un número que crece con n, como el hueco del azar, delata un método que empeora en términos relativos al crecer.

4. Van der Corput: dar la vuelta a las cifras

Escribe el índice en binario, refleja sus cifras respecto a la coma y lee el resultado como una fracción. El índice 1 da 0,5; el 2, 0,25; el 3, 0,75: cada punto nuevo cae en el mayor hueco que queda. En una dimensión es también la secuencia de Halton en base 2 y la primera dimensión de la de Sobol', por eso una sola fila representa a las tres. 

// Base-2 radical inverse: mirror the binary digits of i about the point.
// 1 → 0.1₂ = 0.5, 2 → 0.01₂ = 0.25, 3 → 0.11₂ = 0.75…
export function radicalInverse2(i) {
  let r = 0, f = 0.5;
  for (; i > 0; i >>>= 1, f *= 0.5) if (i & 1) r += f;
  return r;
}

// Van der Corput (Halton and Sobol' in 1D). The seed shifts the whole set round the
// circle (a Cranley–Patterson rotation), which keeps its spacing.
export function vanDerCorput(n, s) {
  const shift = s ? u01(s, 0, 2) : 0;
  return Array.from({ length: n }, (_, i) => frac(radicalInverse2(i) + shift));
}

La secuencia no tiene azar, así que la semilla desplaza todo el conjunto a lo largo de la recta, como si fuera una circunferencia (Cranley y Patterson 1976). Pon la semilla en 0 para ver la secuencia tal cual y arrastra Puntos por 32, 64 o 128: justo en una potencia de dos, la fila se convierte en una rejilla perfecta.

5. La razón áurea

La secuencia de baja discrepancia más sencilla suma una y otra vez el mismo paso irracional y da la vuelta al llegar al final. La razón áurea es el número «más irracional», el más difícil de aproximar con fracciones, así que los puntos son los que más tardan en alinearse en un patrón. 

// Additive recurrence with the golden ratio (Weyl; Roberts' R1).
export const GOLDEN = (Math.sqrt(5) - 1) / 2;
export function golden(n, s) {
  const start = s ? u01(s, 0, 3) : 0.5;
  return Array.from({ length: n }, (_, i) => frac(start + i * GOLDEN));
}

6. El disco de Poisson, a la manera de Bridson

El método ingenuo, lanzar dardos, saca puntos al azar y descarta los que caen demasiado cerca de uno anterior; se vuelve muy lento a medida que la recta se llena. Bridson (2007) hace crecer el conjunto hacia fuera. Una lista de «activos» guarda los puntos que aún pueden tener sitio al lado. Se elige uno, se prueban hasta k candidatos a entre r y 2r de distancia y se queda el primero que cabe; si no cabe ninguno, el punto se retira. Una rejilla de fondo con celdas de tamaño r guarda como mucho un punto por celda, así que comprobar un candidato solo exige mirar las tres celdas más cercanas. 

export function poissonDisk(r, s, k = 30) {
  const cells = Math.ceil(1 / r);
  const grid = new Array(cells).fill(-1);
  const points = [], active = [];
  let draw = 0;
  const rnd = () => u01(s, draw++, 4);

  const fits = (x) => {
    const c = Math.floor(x / r);
    for (let j = Math.max(0, c - 1); j <= Math.min(cells - 1, c + 1); j++) {
      if (grid[j] >= 0 && Math.abs(points[grid[j]] - x) < r) return false;
    }
    return true;
  };
  …
  add(rnd());
  while (active.length) {
    const a = Math.floor(rnd() * active.length);
    const p = points[active[a]];
    let placed = false;
    for (let t = 0; t < k && !placed; t++) {
      // A candidate between r and 2r away, on either side.
      const d = r * (1 + rnd()) * (rnd() < 0.5 ? -1 : 1);
      const x = p + d;
      if (x >= 0 && x < 1 && fits(x)) { add(x); placed = true; }
    }
    if (!placed) active.splice(a, 1);   // no room left around p
  }
  return points;
}

El número de puntos no es un dato de entrada: sale de r. En una recta los huecos acaban entre r y 2r, así que la escena elige r para acercarse a la cantidad pedida, y la etiqueta de la fila dice cuántos puntos salieron de verdad. 

// r = 2 / (3n) gives about n points: in 1D the gaps fall between r and 2r.
{ id: "poisson", …, make: (n, s) => poissonDisk(2 / (3 * n), s) },
¿Por qué el disco de Poisson es difícil en un mundo por chunks?

Cada punto depende de los aceptados antes, así que el resultado depende del orden del trabajo. Si se calculan por separado dos chunks vecinos, sus puntos pueden quedar demasiado cerca en la costura; si se calculan juntos, los chunks dejan de ser independientes. Los métodos de rejilla y hash de arriba no tienen ese problema. Wei (2008) paralelizó el muestreo de disco de Poisson en la GPU procesando las celdas de la rejilla por fases que no pueden entrar en conflicto; Lagae y Dutré (2008) comparan esa familia de métodos con los enfoques de teselas.

7. Lloyd: ir al centro y repetir

El algoritmo de Lloyd viene de la cuantización de señales (Lloyd 1982). A cada punto se le da el tramo de recta que está más cerca de él que de cualquier otro, su celda de Voronoi, y se lleva el punto al centro de ese tramo. Se repite. Cada paso usa las posiciones viejas, así que el bucle solo necesita recordar el borde que acaba de calcular. 

export function lloyd(n, s, iterations) {
  const x = uniform(n, s).sort((a, b) => a - b);
  for (let it = 0; it < iterations; it++) {
    let left = 0;
    for (let i = 0; i < n; i++) {
      const right = i + 1 < n ? (x[i] + x[i + 1]) / 2 : 1;
      x[i] = (left + right) / 2;
      left = right;   // already computed from the old x[i + 1] and the old x[i]
    }
  }
  return x;
}

Sube Pasos de Lloyd. El par azul se separa en pocos pasos, mientras que la columna D* apenas se mueve hasta los cientos de pasos. Cada paso solo pasa información a los vecinos, así que un exceso de puntos en un extremo de la recta se reparte como el calor, celda a celda.

8. Dibujar la discrepancia

El lienzo de abajo dibuja la fracción de puntos a la izquierda de x menos el propio x. Entre dos puntos baja con pendiente −1; en cada punto sube 1/n. La banda verde es ±1/(2n), lo que consigue la rejilla centrada. 

// The staircase: falls with slope −1 between points, jumps up 1/n at each point.
dctx.moveTo(px(0), py(0));
for (let i = 0; i < n; i++) {
  const x = sorted[i];
  dctx.lineTo(px(x), py(i / n - x));
  dctx.lineTo(px(x), py((i + 1) / n - x));
}
dctx.lineTo(px(1), py(0));

Elige la fila del azar uniforme y mira cómo la curva se aleja de cero. Ese vagabundeo es un paseo aleatorio, y por eso su tamaño crece como √n.

Una nota para Islands

Islands genera de forma determinista, ejecuta su ruido en paralelo con Burst y puede pasar a chunks con la fase W. Frente a esas tres condiciones:

  • La rejilla con jitter cumple las tres: un hash por celda, cualquier celda por separado, sin costuras. Ya está en Islands. Su punto débil es el par más cercano.
  • Las secuencias de baja discrepancia son deterministas y se calculan por índice, así que se paralelizan, pero cubren un único dominio global. Por chunk necesitan su propio desplazamiento o mezcla, y nada separa los puntos a ambos lados de una costura.
  • El disco de Poisson da el mejor espaciado local, pero depende del orden del trabajo. La variante para chunks que conviene probar primero: un candidato con jitter por celda de la rejilla y una prioridad sacada del hash; el candidato sobrevive si no hay otro de mayor prioridad a menos de r. Esa decisión solo mira las celdas cercanas, así que es determinista, paralela e igual a ambos lados de una costura. El resultado es más escaso y menos regular que el de Bridson, un compromiso que habrá que medir en la página 2D.
  • Lloyd es iterativo y global: útil para pulir offline un conjunto pequeño, inadecuado para el streaming.

Puedes verlo en la práctica en Hillside: un paisaje infinito construido por chunks, donde se puede cambiar entre estos métodos y mirar las costuras.

Para ir más allá

  • Pasar al plano: Halton en bases 2 y 3, Bridson en 2D y el espectro radial que da nombre al ruido azul. Es la página siguiente.
  • Implementar la variante de Poisson con prioridad por hash de arriba y compararla con Bridson con los mismos cuatro números.
  • Mezclar Van der Corput con un hash, cifra a cifra (Owen 1995), en vez de desplazarla, y ver si sobreviven las rejillas de las potencias de dos.

SourcesFuentes

Part of Islands Lab. Randomness from the SmallXXHash port of part 1.Parte de Islands Lab. El azar sale del port de SmallXXHash de la parte 1.