miyabittiのブログ

プログラミング

JavaScriptでマンデルブロ集合を超高倍率で探索できるサイトを見つけたので紹介します！

JavaScriptでマンデルブロ集合を超高倍率で探索できるサイトを見つけたので紹介します！
41回表示
ちょっと前に、素のJSを使用してマンデルブロ集合を描画するサイトをGitHub上に公開しましたが、そのゴミとは比にならないほどズームがスムーズに行えるサイトを見つけたので紹介します。
以下のサイトになります ↓
https://bertbaron.github.io/mandelbrot/
JavaScriptは通常、倍精度浮動小数点数で計算するので、およそ10^16程度の倍率で計算誤差が許容範囲外になるため、ピクセル化してしまいます(厳密に正確な演算ができるのは10^14程度)。僕が作成したサイトは実際この計算方法で実装しているため、割とすぐにズームの限界に到達します。
しかし、上記のサイトは摂動法という計算方法を利用することで、10^300程度まで正確なズームを可能にしています。更に、WebWorkerによる並列化やGPUアクセラレーションを実装しており、非常に深いズームであっても高速に計算できるようです。
ここから先は、摂動法の計算方法についてや、このサイトの実装概要を初心者の管理人ができる程度に解説していきます。

まずはマンデルブロ集合について

https://zenn.dev/miyabitti256/articles/f1aa12e95b39d9#%E3%83%9E%E3%83%B3%E3%83%87%E3%83%AB%E3%83%96%E3%83%AD%E9%9B%86%E5%90%88%E3%81%A3%E3%81%A6%E4%BD%95%EF%BC%9F
こちらの記事で解説していますが、軽く説明すると、
次の漸化式
{zn+1=zn2+cz0=0{\begin{cases}z_{n+1}=z_{n}^{2}+c\\z_{0}=0\end{cases}}
で、定義された複素数列の n→∞n→∞にしたときに、発散しないという点全体の集合をレンダリングしたものです。この図形は、いくら拡大しても同じような構造が現れるフラクタル図形と言われるものです。

摂動法について

先ほども説明しましたが、通常のJavaScriptでは倍精度浮動小数点数で整数、小数に関わらず数値を扱うのですが、極端にズームをすると、座標の小数点以下の桁数がfloat64の仮数部を超えてしまい、付近では計算誤差が、それより大きいと計算が不可能になります。
しかし、当然ながらそれより大きな値を扱うためのBigIntというものがあり、これはメモリが許す限りの桁数、実質ほぼ無限に大きな(小さな)値を表現することが可能です。が、通常のnumber型で計算するより遥かに遅くなります(数倍~数十倍)。たとえ、通常のnumber型で表せるflaot64の限界値(900京ぐらい)以内であってもです。
つまり、通常の計算方法である1ピクセルごとに独立して計算をする方法では、BigIntで行おうとすると現実的な時間で計算することができません。1枚レンダリングするたびに数十秒から数分、もっと拡大して桁数が増えてくると数時間掛かる可能性があるのです。
そこで使用されるアルゴリズムが摂動法という計算方法です。
以下、wikipediaより引用
数学的に厳密に解くことのできない問題の近似解を求める手法の1つに、摂動論（せつどうろん、 英語: perturbation theory）がある。具体的には、次のような手順で近似解を求める。
  • 考えている問題Aを、厳密に解ける問題Bに小さな変更（摂動）が加えられた問題であるとみなす。
  • 問題Aの近似解は、問題Bの厳密解に、摂動が加わったことによって生じる小さな補正（摂動項）を加えたものであると考える。
  • ここで求めるべき摂動項は、問題Bの厳密解の組み合わせ、すなわち一次結合の形で表現出来ると考え、その係数を与えられた条件から順次求める。
何を言っているかちょっと分かりづらいですが、これをマンデルブロ集合の描画に適用します。
数学的に厳密に解くことの出来ない問題ではありませんが、近似解を求める部分を使用します。
  1. 描画領域の一つの点を代表の点(参照点)としてBigIntを使用して高精度に計算を行う。このとき、計算結果を全て保持しておく。
  2. 他の点は、その参照点からの差分で近似反復計算を行う。このとき、誤差境界を超えてしまう点が現れた場合、新しく参照点として計算を行う。
    このときの参照点との差分が、通常のnumber型での範囲内に収まると期待することで、BigIntの使用を最小限にしつつ、高速で高精度なレンダリングが可能になります。
視覚的に理解したいなら、3Blue1BrownJapan様の以下の動画の4:10ほどの部分から見れるアニメーションを見てみてください。
YouTube で視聴
この軌跡ですが、拡大していくと、隣り合うピクセルの数値の差がとても小さな値になり、遠目にみたらほぼ同じ軌跡を辿るようになります。この軌跡の誤差をnumber型で高速に計算できると考えると分かりやすいかと思います。
そして、この軌跡の差が一定以上になったときは正確な計算のために新しく参照点を作成し、同じ様に全てのピクセルで計算するのです。
しかし、それでも差分がnumber型の範囲内に収まると期待されるのが、せいぜい10^300ぐらいと言われているので、それ以上のズームを行う場合は、指数部をまた別に保持するというような高負荷な計算方法になります。

実装概要

ここからは、実際の実装について軽めに解説していきます。
このサイトの実装で特に注目すべき点は、段階的なアルゴリズム切り替えと効率的な並列処理です。

JavaScript実装の特徴

JavaScriptで実装されているにも関わらず、このサイトが高速に動作する理由は、以下の工夫にあります。
  1. 精度に応じたアルゴリズム切り替え
    ズームレベルに応じて、自動的に最適なアルゴリズムを選択します。
    • 10^13倍まで: 通常のJavaScript数値（float64）を使った基本的なマンデルブロ計算
    • 10^300倍まで: BigIntを使った高精度参照点計算＋float64での摂動法
    • 10^300倍以上: BigInt + 拡張浮動小数点を使った超深度摂動法
  2. Web Workersによる並列処理
    画面を小さなタイル（通常32×32ピクセル）に分割し、CPUの全コア数に合わせて複数のワーカーで並列計算を行います。これにより、メインスレッドが固まることなく、スムーズなユーザー操作を維持できます。
  3. 段階的な描画
    最初は16x16ピクセルの低解像度で素早く全体像を表示し、その後徐々に解像度を上げて詳細を描き込みます。これにより、計算完了を待たずに即座にフィードバックが得られます。

WebGPU実装の威力

実験的な機能として提供されているWebGPU実装ですが、WebWorkerのみの並列化とは比べ物にならないほど高速なレンダリングを実現しています。管理人のデスクトップ環境では、最大で10倍近くの高速化がされている場面もありました。

固定小数点演算の活用

深いズームでは座標の精度が極めて重要になります。このサイトではBigIntを基盤とした固定小数点演算ライブラリを独自実装し、必要な精度を動的に調整しています。
javascript
// 座標変換の例（概念的）
canvas2complex(x, y) {
  // キャンバス座標を高精度な複素数座標に変換
  const scale = this.zoom.multiply(width).divide(4)
  const r = fxp.fromNumber(x).subtract(width/2).divide(scale)
  const i = fxp.fromNumber(y).subtract(height/2).divide(scale)
  return [r.add(center[0]), i.add(center[1])]
}

技術的な工夫の詳細

スムーズ着色（連続着色）技術

通常のマンデルブロ描画では、収束しない点の反復回数によって色を決めるため、同じ色の帯状パターンが現れて美しくありません。このサイトではSmooth Coloringという技術を使用して、滑らかなグラデーションを実現しています。
基本的な考え方は、反復回数を整数ではなく実数として扱うことです。
javascript
// スムーズ着色の計算（簡略版）
if (iter > 3) {
  let log_zn = Math.log(zq) / 2  // |z|の対数
  let nu = Math.log(log_zn / Math.log(2)) / Math.log(2)
  iter = Math.floor(iter + 1 - nu)  // 実数の反復回数
}
これにより、隣接するピクセル間で滑らかに色が変化し、美しいグラデーションが生まれます。

カラーパレットシステム

色彩豊かな表現を可能にするため、複数のカラーパレットを切り替えられる仕組みを実装しています。
  • パレット密度: 色の変化速度を調整
  • パレット回転: 色相を回転させて異なる雰囲気を演出
  • 単調三次補間: 色の境界を滑らかに接続

キャンセル制御とUI応答性

長時間の計算でも操作性を保つため、独特なキャンセル制御システムを実装しています。
  • ジョブトークン方式: 計算開始時に一意のトークン（Blob URL）を生成
  • 非同期キャンセル: メインスレッドがトークンを無効化（revokeObjectURL）
  • ワーカー側検知: 定期的にトークンの有効性をチェックし、無効なら計算停止
javascript
1// ワーカー側でのキャンセル検知（概念）
2function shouldStop(jobToken) {
3  if (!jobToken) return false
4  try {
5    // 同期XHRでトークンの有効性をチェック
6    let xhr = new XMLHttpRequest()
7    xhr.open('GET', jobToken, false)
8    xhr.send(null)
9    return false  // 有効
10  } catch (e) {
11    return true   // 無効 = キャンセル要求
12  }
13}

段階的描画の仕組み

即座のフィードバックを提供するため、複数段階の描画を行います。
  1. 第1パス: 粗い解像度（4×4ピクセルなど）で全体像を素早く表示(最大で16x16ピクセル)
  2. 第2パス: 中間解像度で詳細を追加
  3. 最終パス: フル解像度で完全な画像を完成
各パスは前のパスの結果の上に重ねて描画され、ユーザーは計算の進行状況をリアルタイムで確認できます。

実際に使ってみよう

基本操作

  • ズーム: マウスホイールまたは2本指ピンチ
  • 移動: ドラッグ操作
  • 設定変更: 画面右側のパネルから
  • パラメータ確認: 少し小さいですがinfoと書いているボタンから

面白いポイントを探してみよう

マンデルブロ集合の境界線はフラクタル図形なので、めちゃくちゃ複雑で美しい構造を持っています。また、探索していると、小さなマンデルブロ集合の複製が無数に存在します(厳密には同じ形ではないようですが)。面白い形が見つかったら、カラーパレットを調整したりして更に魅力的な探索を進めてみましょう。
サイトには「I feel lucky」ボタンがあり、6つの興味深いポイントにランダムでジャンプできます。

WebGPU機能を試してみる

対応ブラウザ（Chrome/Edge最新版）では、「GPU (exp.)」をオンにしてWebGPU機能を体験できます。特に深いズームレベル(~10^300)で、CPU実装との速度差を実感できるでしょう。

まとめ

紹介させてもらったこのサイトは、単なるマンデルブロ集合ビューアーを超えて、現代のブラウザ技術を最大限に活用した技術的傑作だと思います。摂動法による計算効率化、Web WorkersとWebGPUによる並列処理、BigIntを使った高精度演算など、多くの先進的な技術が組み合わされています。
特に印象的なのは、理論と実装の絶妙なバランスです。数学的に美しい摂動法のアイデアを、JavaScriptとWebGPUという実用的な技術で巧みに実現し、誰でもブラウザで簡単に体験できるようにしています。
高校数学レベルの知識があれば理論を理解でき、プログラミングの基礎があれば実装の詳細も追跡できる、学習教材としても非常に優秀なプロジェクトだと思います。美しい数学と最新技術の融合を、ぜひ実際に触って体験してみてください。
紹介したサイトのGitHubリポジトリ↓
bertbaron/mandelbrot
GitHubで見る
最初のいいねをしませんか？

コメント (0)

まだコメントがありません

ログインしてコメントを投稿してみませんか？

関連記事

こちらの記事もおすすめです