Circle-Packing-Mosaik: Wie wir eine kantenerhaltende Percolator-Engine gebaut haben

Eine von Percolator inspirierte Mosaik-Engine in Canvas 2D: Kanten-Dilatation, Spatial Hash Grid, konzentrische Farbringe und Key-Plate-Überdruck.

> Kurz gesagt

Klassisches Circle Packing zerstört Fotos, weil große Kreise über kontrastreiche Konturen hinweglaufen und Silhouetten verwischen. Um die fühlbare Ästhetik von Tinrockets Percolator in Canvas 2D nachzubauen, braucht es vier gekoppelte Schritte: (1) eine Kantenkarte mit separierbarer Dilatation, die große Kreise auf ruhige Flächen begrenzt und feine Perlen an Konturen legt; (2) ein Spatial Hash Grid, das Kollisionsprüfungen auf lokale Nachbarzellen reduziert; (3) mehrstufige konzentrische Farbringe und radiale Facettenkeile; und (4) einen doppelten Key-Plate-Überdruck, der Strukturkontrast und Lichter zurückholt. In Yan läuft das komplett auf der CPU im Browser ohne externe Abhängigkeiten.

Warum Percolator bis heute fasziniert

2010 brachte Tinrocket Percolator für iOS heraus. Während alle Welt auf Filmkorn und Polaroid-Rahmen setzte, ging Percolator einen konsequent grafischen Weg: Fotos wurden in organische Konstellationen aus bunten Kreisen, konzentrischen Ringen und Prismen-Facetten zerlegt.

Statt Punkte auf ein starres Schachbrett zu pressen (wie klassische Halbtonraster) oder Kreise blind über Kanten wachsen zu lassen, entstand ein fühlbares Druck-Mosaik zwischen digitaler Präzision und Handarbeit.

Als wir die Bibliothek im Textur-Studio erweitert haben, wollten wir eine kantenerhaltende Mosaik-Engine in genau diesem Geist bauen – rein in Canvas 2D, ohne GPU-Shader und ohne externe Bibliotheken.

Hier sind alle vier Stufen der Pipeline:

Percolator-Circle-Packing-Pipeline-Diagramm
Abbildung 1: Die vierstufige Mosaik-Pipeline in Yan – von Kanten-Dilatation über Spatial-Hash-Packing und konzentrische Ringe bis zum Key-Plate-Überdruck.


Warum naives Circle Packing Fotos ruiniert

Klassisches Circle Packing folgt drei simplen Schritten:

  1. Wähle einen Kandidaten (x, y).
  2. Berechne den maximal möglichen Radius bis zu bestehenden Kreisen und Rändern: r_fit = min_i(||p - c_i|| - r_i) - gap.
  3. Ist r_fit >= minR, zeichne einen Kreis mit r = min(maxR, r_fit) in der Farbe des Bildpunkts.

Auf einem Foto mit klaren Motiven zerfällt das Ergebnis sofort:

Circle-Packing-Vergleich: Original vs. Naiv vs. Yan Engine
Abbildung 2: Vergleich auf einem kontrastreichen Ausschnitt – (01) Original; (02) naives Circle Packing, bei dem zu große Kreise Hüte und Mäntel überschreiten; (03) Yans kantenerhaltende Engine mit großen Kreisen im Himmel und feinen Perlen entlang der Silhouetten.

In Panel // 02: NAIVE PACKING (CRUSHED) sieht man die drei Probleme deutlich:

  • Figuren und Hüte verlieren ihre Kontur: Weil die Wiese ringsum ruhig ist, entstehen große Kreise direkt neben den Figuren und wachsen quer über die Hutkrempen hinweg.
  • Ausgestanzte Übergänge: Überschreitet ein einfarbiger Kreis eine Kante, repräsentiert er weder Vorder- noch Hintergrund sauber.
  • Tote Fugen: Reines Schwarz zwischen den Kreisen unterbricht die Wahrnehmung zusammenhängender Linien.

Die Lösung verlangt vier aufeinander abgestimmte Grafik-Durchläufe:


Stufe 1: Kantenkarte & mehrskalige Dilatation

In einem guten Mosaik verhalten sich Kreise wie Flüssigkeitstropfen: Auf freien Flächen fließen sie zu großen Blasen zusammen, an jeder Kontur verdichten sie sich zu feinen Perlen.

1. Helligkeits-Gradient mit Kontrastempfindlichkeit

Zuerst berechnen wir Helligkeit und Manhattan-Gradient auf einem halb so großen Puffer (2x Downsampling) und unterdrücken feines Flächenrauschen per Soft-Coring:

// Downsampled luminance buffer (2x downsample for high speed)
const dw = Math.max(2, Math.floor(w / 2))
const dh = Math.max(2, Math.floor(h / 2))
const lumaGrid = new Float32Array(dw * dh)
for (let dy = 0; dy < dh; dy++) {
  for (let dx = 0; dx < dw; dx++) {
    const idx = ((dy * 2) * w + (dx * 2)) * 4
    lumaGrid[dy * dw + dx] =
      0.2126 * (data[idx] ?? 0) + 0.7152 * (data[idx + 1] ?? 0) + 0.0722 * (data[idx + 2] ?? 0)
  }
}

// Contrast slider (0..100) dynamically tunes edge sensitivity threshold
const edgeSens = Math.max(22, 68 - (contrast / 100) * 32)
const edgeGrid = new Float32Array(dw * dh)
for (let dy = 1; dy < dh - 1; dy++) {
  for (let dx = 1; dx < dw - 1; dx++) {
    const gx = Math.abs((lumaGrid[dy * dw + (dx + 1)] ?? 0) - (lumaGrid[dy * dw + (dx - 1)] ?? 0))
    const gy = Math.abs((lumaGrid[(dy + 1) * dw + dx] ?? 0) - (lumaGrid[(dy - 1) * dw + dx] ?? 0))
    const raw = (gx + gy) / edgeSens
    // Soft edge coring: ignore micro-texture noise below 0.18 so smooth slopes & open fields can bloom large bubbles
    edgeGrid[dy * dw + dx] = raw > 0.18 ? Math.min(1.0, Math.pow((raw - 0.18) / 0.82, 1.25)) : 0
  }
}

2. Separierbare Kanten-Dilatation (Schutzpuffer)

Ein Kreis in (x, y) mit Radius R_max kann im Zentrum null Gradient haben – und trotzdem 30 Pixel weiter eine harte Kante überrollen.

Deshalb prüft ein separierbarer 2-Pass-Maximum-Filter (erst horizontal, dann vertikal) mit Radius rad = round(maxR * 0.42 / 2), ob in der Umgebung eine Kante liegt. Das drosselt den Zielradius frühzeitig in Richtung minR:

const dilated = new Float32Array(dw * dh)
const rad = Math.max(2, Math.round((maxR * 0.42) / 2)) // ~42% of maxR standoff in 2x-downsampled units
const temp = new Float32Array(dw * dh)

// Horizontal max-filter pass
for (let y = 0; y < dh; y++) {
  for (let x = 0; x < dw; x++) {
    let maxV = 0
    const startX = Math.max(0, x - rad), endX = Math.min(dw - 1, x + rad)
    for (let k = startX; k <= endX; k += 1) {
      const v = edgeGrid[y * dw + k] ?? 0
      if (v > maxV) maxV = v
    }
    temp[y * dw + x] = maxV
  }
}

// Vertical max-filter pass
for (let x = 0; x < dw; x++) {
  for (let y = 0; y < dh; y++) {
    let maxV = 0
    const startY = Math.max(0, y - rad), endY = Math.min(dh - 1, y + rad)
    for (let k = startY; k <= endY; k += 1) {
      const v = temp[k * dw + x] ?? 0
      if (v > maxV) maxV = v
    }
    dilated[y * dw + x] = maxV
  }
}

Die Zielradius-Funktion setzt diesen Schutzabstand direkt durch:

function getTargetRadius(x: number, y: number): number {
  const gx = Math.min(dw - 1, Math.max(0, Math.floor(x / 2)))
  const gy = Math.min(dh - 1, Math.max(0, Math.floor(y / 2)))
  const localEdge = edgeGrid[gy * dw + gx] ?? 0
  const neighborhoodEdge = dilated[gy * dw + gx] ?? 0
  
  // High sensitivity to nearby contours pulls radius down toward minR
  const edgeFactor = Math.pow(Math.max(localEdge, neighborhoodEdge * 0.85), 0.68)
  return Math.max(minR, maxR - (maxR - minR) * edgeFactor)
}

Stufe 2: Spatial Hash Grid für lokale Kollisionsabfragen

Brute-Force-Packing vergleicht jeden Kandidaten mit allen bisherigen Kreisen (O(N^2)). Bei Tausenden Kreisen friert das den Browser sofort ein.

Mit einem Spatial Hash Grid, dessen Zellgröße genau maxR entspricht, muss jeder Kandidat nur noch seine unmittelbaren Nachbarzellen (meist ein 3×3-Feld) prüfen:

// Excerpt: spatial grid collision lookup
const cellSize = maxR
const cols = Math.ceil(w / cellSize)
const rows = Math.ceil(h / cellSize)
const grid: number[][] = new Array(cols * rows).fill(null).map(() => [])
const circles: { x: number; y: number; r: number }[] = []

function maxRadiusAt(cx: number, cy: number, maxAllowed: number): number {
  let maxFit = Math.min(maxAllowed, cx - 1, w - cx - 1, cy - 1, h - cy - 1)
  if (maxFit < minR) return 0

  const minCellX = Math.max(0, Math.floor((cx - maxFit) / cellSize))
  const maxCellX = Math.min(cols - 1, Math.floor((cx + maxFit) / cellSize))
  const minCellY = Math.max(0, Math.floor((cy - maxFit) / cellSize))
  const maxCellY = Math.min(rows - 1, Math.floor((cy + maxFit) / cellSize))

  for (let gy = minCellY; gy <= maxCellY; gy++) {
    for (let gx = minCellX; gx <= maxCellX; gx++) {
      const bucket = grid[gy * cols + gx]
      if (!bucket) continue
      for (let i = 0; i < bucket.length; i++) {
        const c = circles[bucket[i] ?? 0]
        if (!c) continue
        const dx = cx - c.x
        const dy = cy - c.y
        const dist = Math.sqrt(dx * dx + dy * dy) - c.r
        if (dist < minR) return 0
        if (dist < maxFit) maxFit = dist
      }
    }
  }
  return maxFit
}

Vier abgestufte Packing-Durchläufe

Statt Punkte rein zufällig zu streuen, arbeitet die Engine in vier absteigenden Runden:

  1. Runde 1 (Grobes Jitter-Raster): Setzt die größten Kreise ausschließlich in freien, kantenfernen Flächen (targetRadius >= 0.45 * maxR, r >= 0.40 * maxR).
  2. Runde 2 (Mittlere Füllung): Verteilt mittelgroße Kreise (r >= 2.4 * minR) in Übergangszonen.
  3. Runde 3 (Feine Übergangsperlen): Rasterscan bis minR * 2.8, nimmt Kreise ab 1.5 * minR; nahe Konturen zieht das Dilatationsfeld die Größe weiter bis auf minR.
  4. Runde 4 (Mikro-Fugen): Füllt verbleibende Zwischenräume mit feinsten Punkten (minR).

Auf Apple Silicon (Chrome 130) dauert das gesamte Packing unter 10 ms; die Gesamtrechenzeit liegt bei ~15 ms für die Vorschau (0,2 MP) und ~100 ms für den 1400×1400-Export.


Stufe 3: Konzentrische Ringe & prismatische Facetten

Die Kreise sind keine flachen Punkte, sondern besitzen eigene Binnenstrukturen:

StilVorbildVisuelle Mechanik
Percolator (circle-mosaic)Konzentrische Druckringe (Treble-Stil)Bis zu 4 konzentrische Ringe mit mehrfacher Farbprobe und feinem Schatten
Facet Mosaic (facet-mosaic)Kaleidoskop-Prismen (Ray-Ray-Stil)4 bis 10 radiale Keile mit wechselnder Lichtmodulation

1. Konzentrische Farbringe

Je nach Kreisradius werden vier versetzte Punkte im Originalfoto abgetastet:

  • Kernfarbe: Zentrum (c.x, c.y)
  • Außenring: (c.x + 0.65r, c.y + 0.65r)
  • Mittelring 1: (c.x - 0.45r, c.y - 0.45r)
  • Mittelring 2: (c.x + 0.35r, c.y - 0.35r)

Die Zahl der Ringe skaliert mit dem Radius:

  • r >= 3.5 * minR: 4 Ringe (1.0r -> 0.74r -> 0.48r -> 0.25r)
  • r >= 2.2 * minR: 3 Ringe (1.0r -> 0.65r -> 0.34r)
  • r >= 1.4 * minR: 2 Ringe (1.0r -> 0.52r)
  • r < 1.4 * minR: voller Mikropunkt

2. Prismatische Facetten

In facet-mosaic wird jeder Kreis wie ein geschliffener Edelstein in radiale Sektoren zerteilt:

const sectors =
  c.r > minR * 4 ? 10 : c.r > minR * 2.5 ? 8 : c.r > minR * 1.6 ? 6 : 4
const angleStep = (Math.PI * 2) / sectors

for (let s = 0; s < sectors; s++) {
  const a1 = s * angleStep
  const a2 = a1 + angleStep
  const midA = (a1 + a2) / 2
  
  const sampleX = c.x + Math.cos(midA) * c.r * 0.62
  const sampleY = c.y + Math.sin(midA) * c.r * 0.62
  const rgb = contrastRgb(samplePixel(data, w, h, sampleX, sampleY), contrast)

  // Alternating directional facet lighting
  const facetLight = 0.86 + (s % 2 === 0 ? 0.24 : 0.0) + Math.cos(midA) * 0.12
  const crgb: [number, number, number] = [
    clamp(Math.round(rgb[0] * facetLight)),
    clamp(Math.round(rgb[1] * facetLight)),
    clamp(Math.round(rgb[2] * facetLight)),
  ]

  ctx.beginPath()
  ctx.moveTo(c.x, c.y)
  ctx.arc(c.x, c.y, Math.max(0.1, c.r - 0.4), a1, a2)
  ctx.closePath()
  ctx.fillStyle = rgbaStyle(crgb, 0.94 * intensity)
  ctx.fill()
}

Stufe 4: Key-Plate-Überdruck (Formwiederherstellung)

Selbst mit Kantenpuffer kann ein reines Kreismosaik leicht vom Originalmotiv abreißen. Die Drucktechnik löst das seit jeher über die Key Plate (die schwarze Zeichnungsplatte im Vierfarbdruck).

Wir bilden das in zwei Mischstufen nach:

1. Abgedunkelter Untergrund

Vor dem ersten Kreis bekommt der Canvas eine dezente dunkle Lasur (rgba(10, 8, 14, 0.45 * intensity)). Dadurch zeigen die Fugen zwischen den Kreisen echte Tiefenzeichnung statt toter schwarzer Lücken.

2. Doppelter Überdruck

Nachdem alle Kreise gezeichnet sind, wird das Originalfoto zweimal sanft überlagert:

if (source && intensity > 0.05) {
  // 1. Multiply blend restores edge density, garment folds, and shadow grooves
  ctx.globalCompositeOperation = 'multiply'
  ctx.globalAlpha = 0.26 * intensity
  ctx.drawImage(source, 0, 0, w, h)

  // 2. Overlay blend restores specular highlights and sunlit rims
  ctx.globalCompositeOperation = 'overlay'
  ctx.globalAlpha = 0.15 * intensity
  ctx.drawImage(source, 0, 0, w, h)
}

In Panel // 03: YAN ENGINE (EDGE-PRESERVED) von Abbildung 2 behalten die Hüte ihre klare Silhouette, die Figuren bleiben sofort lesbar, und trotzdem wirkt das gesamte Bild wie ein organisches Pop-Art-Mosaik.


Vergleich der Mosaik-Verfahren

MerkmalStandard-HalbtonVoronoi-MosaikNaives Circle PackingYans Percolator-Engine
RaumaufteilungStarres RasterUnregelmäßiges PolygonnetzZufällige AbstandspackungKantengesteuerte Hierarchie
Max. KreisgrößeDurch Raster fixVariabel je PolygonUnbegrenzt (zerstört Konturen)Dynamisch (~1/8 bis 1/7,6 der langen Kante)
KantenschutzIndirekt über PunktgrößeExplizit per RelaxationKeinerChebyshev-Dilatation & Key Plate
BinnenstrukturEinfarbige/CMYK-PunkteFlache FacettenEinfarbige ScheibenBis zu 4 Ringe oder Prismenkeile
KompromissStarre RasterwinkelHarte PolygoneckenStarker SilhouettenverlustKey Plate mildert reine Geometrie leicht ab
RechenmodellEin-Pass-RasterTriangulationO(N^2) AbstandstestsMehrstufiges Spatial Hash Grid

Gemessen in Google Chrome 130 auf Apple Silicon (1400×1400 Canvas, Standardwerte).


Direkt ausprobieren

Sowohl Percolator (circle-mosaic) als auch Facet Mosaic (facet-mosaic) findest du im Textur-Studio:

  • Mit Detail steuerst du zwischen großen Pop-Art-Blasen und feinen Pointillismus-Perlen.
  • Mit Kontrast schärfst du die Kanten-Dilatation rund um feine Details.
  • Mit Stärke regelst du Deckkraft der Kreise und Key-Plate-Anteil.

Im Browser rechnet alles zu 100 % lokal auf deiner CPU ohne Upload und ohne Wasserzeichen. In der Yan-App für iOS und Android laufen dieselben Prinzipien hardwarebeschleunigt direkt im Live-Sucher.

> Häufige Fragen

Was ist der Percolator-Fotoeffekt?
Der Percolator-Effekt – berühmt geworden durch Tinrockets iOS-App von 2010 – verwandelt Fotos in Mosaike aus dicht gepackten Kreisen, konzentrischen Ringen und kaleidoskopischen Facetten. Statt Punkte auf ein starres Raster zu zwingen, nutzt er adaptives organisches Circle Packing im Geist von Pointillismus und Mid-Century-Druckgrafik.
Warum zerstört naives Circle Packing Foto-Silhouetten?
Naives Circle Packing berechnet den Radius nur aus dem Abstand zu Nachbarkreisen und Bildrändern. Landet ein Kreismittelpunkt auf einer ruhigen Fläche direkt neben einer Kante, wächst der Kreis quer über die Kontur, mischt Vorder- und Hintergrundfarben und radiert feine Umrisse aus.
Wie schützt Kanten-Dilatation die Konturen im Kreismosaik?
Ein separierbarer Maximum-Filter erweitert die Gradientenkarte um einen Schutzpuffer von rund 42 % des maximalen Kreisradius. Dadurch schrumpfen Kreise bereits in der Nähe kontrastreicher Kanten auf kleine Radien zusammen, während große Kreise konsequent ruhigen Flächen vorbehalten bleiben.
Wie schnell ist Circle Packing mit Spatial Hash Grid in JavaScript?
Weil der Canvas in Zellen von der Größe des Maximalradius unterteilt wird, prüft jeder neue Kreis nur seine unmittelbaren Nachbarzellen statt aller bisherigen Kreise. Auf Apple Silicon (Chrome) dauert die Kollisionsprüfung unter 10 ms; ein Vorschau-Frame (~0,2 MP) braucht ca. 15 ms, ein 1400×1400-Export rund 100 ms.
Kann ich das Circle-Packing-Mosaik kostenlos online testen?
Ja. Sowohl Percolator als auch Facet Mosaic laufen direkt in Yans Textur-Studio unter yan.yichenlab.com/de/textures/ – 100 % lokal im Browser, ohne Konto, ohne Upload und mit PNG-Export ohne Wasserzeichen bis 1400 px.