円パッキング・モザイク：輪郭を守るPercolator風タイリングエンジンの実装

Percolatorが放つ色褪せない魅力

2010年、TinrocketはiOS向けに写真アプリ『Percolator』をリリースしました。当時のモバイル写真アプリ界隈が人工的なフィルム粒子やポラロイド風フレームの模倣に終始していたなか、Percolatorは極めてモダンなアプローチを打ち出しました。写真を色鮮やかな円、同心円リング、そして万華鏡のような多面体ファセットの有機的な星団へと解体・再構成したのです。

規則的な直交グリッドに点を並べる一般的なハーフトーン処理や、輪郭を無視した単純な円パッキングとは異なり、それは機械的な幾何学性と手仕事の温もりが共存する、印刷版画のような触感を備えていました。

質感工坊（Texture Studio）のプロシージャル・フィルタ群を28種から30種へと拡張するにあたり、私たちはこの名作の美学にインスパイアされ、GPUシェーダーや外部ライブラリに一切頼らない、純粋なCanvas 2Dによる輪郭保護型モザイクエンジンの自社実装に挑みました。

以下が、その完全な4段階アーキテクチャ・パイプラインです。

図1：Yanのモザイク・パイプライン全4段階 — 輝度勾配のエッジ膨張から空間ハッシュ配置、多重同心円描画、そしてキープレート重ね刷りまで。

---

なぜ単純な円パッキングは写真を破壊してしまうのか

このエフェクトの実装が難しい理由を理解するために、古典的な円パッキングの手順を振り返ってみましょう：

1. 候補座標 (x, y) を選ぶ。
2. 既存の配置済み円群およびキャンバス外枠との最短距離を計算する：r_fit = min_i(||p - c_i|| - r_i) - gap。
3. r_fit >= minR であれば、r = min(maxR, r_fit) の円をスタンプし、下地画像のピクセル色をサンプリングする。

輪郭が明確な写真に対してこのナイーブな手法をそのまま適用すると、結果は無残なものになります：

図2：高コントラスト画像での比較 — (01) 原画、(02) ナイーブなパッキング（笠や衣服の境界線を大円が踏み越えて輪郭崩壊）、(03) Yanの輪郭保護エンジン（空には大径バブルが咲き、人物の輪郭には極小ビーズが吸着）。

上図のパネル // 02: NAIVE PACKING (CRUSHED) を注意深く観察してください：

• 人物と三度笠の輪郭喪失：旅人の周囲の草地は比較的均一なため、人物のすぐ真横に大きな円の中心が生成されます。その半径が笠のつばを越えて大きく膨張し、笠の中に緑色の草地の色をサンプリングしてしまうため、明瞭だった人物のシルエットが無差別な緑の球の散らばりに崩壊します。
• クッキー型のような境界破綻：高周波な境界線を跨いだ大きな円は、前景でも背景でもない不自然な中間色を呈し、視覚的なノイズとなります。
• 死んだ黒い目地：円と円の隙間を単色のベタ黒で塗り潰してしまうと、人間の脳が空間のゲシュタルト輪郭を補完して読み取る能力を阻害します。

これらを解決するために、形状を保持するモザイクエンジンには4つの独立したグラフィックス処理段階が不可欠です。

---

第1段階：エッジ感度と分離可能近傍膨張（チェビシェフ緩衝帯）

優れたモザイクにおいて、円は物理的なリトグラフにおける液体小滴のように振る舞わなければなりません。開けた平坦な空間では大きな泡へと合流し、境界線（輪郭）に近づくにつれて微細なビーズへと凝縮していく必要があります。

1. コントラスト感度を考慮した輝度マンハッタン勾配

まず、メモリスループットを極小化するため、2倍ダウンサンプリングしたバッファ上で輝度と勾配強度を計算します。演算コストを抑えるため、中心差分のマンハッタン勾配 |L(x+1) - L(x-1)| + |L(y+1) - L(y-1)|（除算 /2 は省略）を用い、微小ノイズを抑制するコーリング処理を施します：

// 高速化のため2倍ダウンサンプリングした輝度グリッド
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)
  }
}

// コントラストスライダー（0..100）に応じてエッジ感度閾値を動的に調整
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
    // ソフトエッジ・コーリング：0.18以下の微小テクスチャノイズを除去し、平坦部で大円が育つ余地を確保
    edgeGrid[dy * dw + dx] = raw > 0.18 ? Math.min(1.0, Math.pow((raw - 0.18) / 0.82, 1.25)) : 0
  }
}

2. 最も重要なステップ：分離可能近傍エッジ膨張（チェビシェフ緩衝帯）

中心座標 (x, y)、半径 maxR の円は、その中心点自体の勾配がゼロであっても、円周が30〜40ピクセル先のエッジを容赦なく横切ってしまう可能性があります。

したがって、候補地点は局所的な中心勾配を見るだけでは不十分です。自らの勢力範囲（近傍）にエッジが存在するかどうかを先回りで検知しなければなりません。

私たちは、エッジグリッドに対して半径 rad = round(maxR * 0.42 / 2) の分離可能2パス最大値フィルタ（Horizontal / Vertical）を適用します。分離可能1D最大値フィルタは完全な円形ではなくチェビシェフ（正方形）近傍を形成し、さらに neighborhoodEdge * 0.85 の 0.68 乗という非線形減衰を掛けることで、エッジ付近の目標半径を強力に縮小させる実用的なヒューリスティック緩衝帯として機能します：

const dilated = new Float32Array(dw * dh)
const rad = Math.max(2, Math.round((maxR * 0.42) / 2)) // 2倍ダウンサンプル単位でmaxRの約42%
const temp = new Float32Array(dw * dh)

// 水平方向最大値フィルタパス
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
  }
}

// 垂直方向最大値フィルタパス
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
  }
}

これにより、目標半径関数は輪郭線からの非線形な退避距離を自律的に算出します：

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
  
  // 近傍に輪郭が存在するとエッジ係数が急増し、目標半径をminRへと強く引き戻す
  const edgeFactor = Math.pow(Math.max(localEdge, neighborhoodEdge * 0.85), 0.68)
  return Math.max(minR, maxR - (maxR - minR) * edgeFactor)
}

---

第2段階：空間ハッシュ格子による局所衝突判定

愚直な総当たり円パッキングでは、配置候補ごとに既存の全円との距離判定を行うため、最悪計算量は O(N^2) に達します。数千個の円を試行する際、ブラウザのメインスレッドを固まらせる原因になります。

そこで、セルサイズを最大円半径と同一（cellSize = maxR）にした空間ハッシュ格子（Spatial Hash Grid）を構築することで、候補点の衝突判定を局所的な隣接バケット（通常は3×3グリッド領域）のみに限定します：

// 抜粋：空間ハッシュ格子による近傍衝突判定
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
}

階層的マルチパス・パッキング

均一なランダム座標を散布するのではなく、4段階の降順パスで階層的にパッキングを行います：

1. Pass 1（ジッター粗格子パス）：エッジ膨張値の低い平坦領域に、最大級の大円のみを植え付ける（targetRadius >= 0.45 * maxR かつ 確定 r >= 0.40 * maxR を要求）。
2. Pass 2（中径補間パス）：平坦部と輪郭部の中間遷移ゾーンへ中径円（r >= 2.4 * minR）を配置。
3. Pass 3（ジッター微細ビーズパス）：全体を上限 minR * 2.8 の微細スキャンで埋め、r >= 1.5 * minR を受容。輪郭部ではエッジ膨張によって minR へと強く抑え込まれる。
4. Pass 4（マイクロ目地充填パス）：残された微小な隙間を最小半径（minR）のピンポイントで稠密に充填。

Apple Silicon（Mシリーズ、Chrome 130）での実測において、この4段階パスは数千個の円候補を10ms未満で判定し、プレビュー時約15ms、1400×1400エクスポート時でも約100msで完了します。

---

第3段階：同心円リングとプリズム・ファセット

Percolatorにおいて、円は単なる単色の塗りつぶし円盤ではありません。木版画の多色刷りや光学レンズを想起させる内部構造を持っています：

1. 同心円カラーリング（Trebleスタイル）

円のサイズに応じて、4箇所の空間座標から色をサンプリングします：

• 核（Core）の色：中心点 (c.x, c.y) でサンプリング
• 外環（Outer ring）：(c.x + 0.65r, c.y + 0.65r) でサンプリング
• 中環1（Middle ring 1）：(c.x - 0.45r, c.y - 0.45r) でサンプリング
• 中環2（Middle ring 2）：(c.x + 0.35r, c.y - 0.35r) でサンプリング

同心円リングの層数はバブルの半径に応じて自動スケーリングされます：

• r >= 3.5 * minR：4層リング（1.0r -> 0.74r -> 0.48r -> 0.25r）
• r >= 2.2 * minR：3層リング（1.0r -> 0.65r -> 0.34r）
• r >= 1.4 * minR：2層リング（1.0r -> 0.52r）
• r < 1.4 * minR：単色の極小ディスク

2. プリズム・ファセット（Ray Rayスタイル）

facet-mosaic では、円盤が光学万華鏡のように放射状のパイ状ウェッジへと分割されます：

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)

  // 偶数・奇数セクターで交互に方向光の明暗を付ける
  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()
}

---

第4段階：キープレート重ね刷り（輪郭と陰影の復元）

エッジ膨張によって大円の跨ぎを防いだとしても、純粋なベクター円の集合だけでは、写真本来の骨格や陰影のニュアンスが浮き上がってしまうことがあります。伝統的な版画印刷では、これをキープレート（Key Plate：墨版・主線版）によって解決してきました。

私たちは、原画を2つの描画合成モードで再統合するデュアルパス・コンポジットによってこれを再現しています：

1. 暗調の下敷き目地（Grout）

円を描き始める前に、キャンバス全体に薄い写真トーンのウォッシュ（rgba(10, 8, 14, 0.45 * intensity)）を敷いておきます。円が寄り集まるにつれて生じる隙間の目地（Grout）から、無機質な黒ベタではなく本物の写真の暗部アンダートーンが透けて現れ、画面に奥行きが生まれます。

2. キープレート多重ブレンド重ね刷り

すべての円、ドロップシャドウ、同心円リングを描き終えた後、元画像を2つの異なるブレンドモードで画面全体に薄く重ね刷りします：

if (source && intensity > 0.05) {
  // 1. Multiply（乗算）合成：衣服の皺、影の溝、境界輪郭の濃度を強烈に引き締める
  ctx.globalCompositeOperation = 'multiply'
  ctx.globalAlpha = 0.26 * intensity
  ctx.drawImage(source, 0, 0, w, h)

  // 2. Overlay（オーバーレイ）合成：ハイライト部の光沢感と縁取りの照り返しを復元する
  ctx.globalCompositeOperation = 'overlay'
  ctx.globalAlpha = 0.15 * intensity
  ctx.drawImage(source, 0, 0, w, h)
}

図2のパネル // 03: YAN ENGINE (EDGE-PRESERVED) を再度ご覧ください：
三度笠の外形線が明瞭に保たれ、旅人のシルエットは力強い輪郭線を保ち、周囲の緩やかな草地は有機的なポップアート・モザイクへと昇華されています。

---

モザイクレンダリング技術の比較マトリクス

性能測定環境：Google Chrome 130 on Apple Silicon Mシリーズ（1400×1400pxキャンバス、デフォルト設定）。

---

オンラインで今すぐ試す

Percolator（circle-mosaic）および Facet Mosaic（facet-mosaic）は、Web上の質感工坊（Texture Studio）で今すぐ体験できます。

ポートレートやストリート写真、建築写真を読み込んで、スライダーを試してみてください：

• Detail：大粒のポップアート・バブルから、新印象派の超微細な点描ビーズまでをシームレスに切り替えます。
• Contrast：エッジ検出感度を調整し、髪の毛のディテールや輪郭部からどれだけ鋭角にバブルを退避させるかを制御します。
• Intensity：バブルの不透明度と、キープレート重ね刷りの輪郭の濃さを微調整します。

ブラウザ版はCanvas 2Dを用い、端末のCPU上で100%ローカルに完結します。画像データがサーバーへ送られることはなく、プライベートで安全です。なお、iPhoneやAndroidの実機で60fpsのリアルタイムカメラ取景やネイティブ解像度での高画質エクスポートを楽しみたい場合は、モバイル版 Yan App でも同系統のアルゴリズムを着色シェーダーとして提供しています。