【しばらく編集不可モードで運営します】 編集(管理者用) | 差分 | 新規作成 | 一覧 | RSS | FrontPage | 検索 | 更新履歴

HowGoogleEarthReallyWorks - Google Earth の <ほんとの> 仕組み

目次

Google Earth の <ほんとの> 仕組み

この文書について

Google Earth の <ほんとの> 仕組み

有名サイト HowStuffWorks.com の記事 "How Google Earth Works" を読んだら, freelance writer jobs この記事が "それがどれだけスゴいか" や "その使い方" を書くだけで "それが(ほんとは)どんな仕組みで動いているのか" を説明していないことがわかった.

そこで考えた. 興味のある人はいるらしい. だから知財の懸念はあるけれど, Google Earth の最低限の仕組みを説明する記事の "第一話" を書いてみた.

知財の懸念が本物である点には気をつけてほしい. Keyhole (現在の Google Earth) は他人のどうでもいい(←個人的見解)技術をぱくった旨で 訴えられたことがある. 裁判所は完全にその主張を完全に 退けた が, 辛い年月が続いた. この例から, ただ話をするだけで困ることがあるのだと痛感させられる. 何かを口にするだけで, "我々と <同じようなこと> をしている" と主張する 特許ゴロの連中をおびきよせてしまう. Skyline 対 Google の訴訟からわかるのは, <同じようなこと> というだけで権利侵害の証明にはならないということだ. でもいつもそんな判決が下るわけじゃない.

とにかく. "Google Earth の <ほんとの> 仕組み" を話すための打開策はある. 既に公開されている様々な情報, 特に Google 自身の特許を頼りに話をすればいい. 特許は比較的すくない. 世界のために特許はすくない方がいい. でも今回に限っては, 特許は多いほど勝手に話せる技術も多くなる. それがまあ, 特許のもともとの目的なわけだし. 限られた独占権と引き換えに公共の利益をもたらすという...気には入らないけれど.

技術的な興味から特許そのものを読もうとする人がいるかもしれない. 警告する. 法律家や技術者は時に言語的マヨネーズをこねくりだす. 命を削るその文書は "Patent English", あるいは "Painglish" として知られている. もし君に勇気があれば, またはマゾなら, どうぞお好きに.

遠からず関係のある Google 特許がもういくつかある. これらの特許が躍起なのはよくわからないが, 各分野では重要な話題なんだろう. 将来の記事で詳しく掘り下げられればと思う.

もう少し役に立ちそうな記事が SGI によって書かれている. これはハードウェア "clipmap" について解説しており, 私達も後で参照する. ところで著者の Michael Jones は Google Earth の立役者の一人. 今でも CTO として技術を推し進めている.

ここからは公開情報か広く知られた技術の知識に基いて話を進める. なるべく多くの人に理解できるよう説明したいと思う. それが今回の目標. わからないことがあったら指摘してほしい.

懸念事項: Google Earth のコードベースは私が Keyhole にいた頃から, また特許が申請されてからも何度か書き直されていると思う.  そのため最新の実装は大幅に違うものとなっているかもしれない. また私の解説はおおまか(かつ古いかもしれない)ため, 知的関心や理解以外の目的でこの文書を頼るべきではない.

もう一つ: この記事は逆順で進む. 違和感があるかもしれないけれど, まず簡単な 3D の地球を画面に書くところから始まり, それからデータが配信される方に戻っていく. こう説明する方がわかりやすいし, 他の説明ではうまくいかないと思っている.

パート1 終幕: 3D の仮想地球を描画する

仕組みを理解する上で, Google Maps と Earth には大きな違いが二つある. 一つ目は固定ビュー(大抵は見下ろす方向)の 2D に対する自由視点の 3D 描画という違い. 二つ目はグラフィクスがリアルタイム描画かプリ描画かの違い. この二つの違いは各製品が守備範囲を広げるよう強化されるにつれ曖昧になりつつあるけれど, 今日でもまだ際立った差がある.

双方に共通するのは, 古き良きデジタル写真 ... しかも大量の ... で 一つの巨大かつ高解像度(または複数解像度)な地球の絵を作り上げているところだ. 違いはそのデータをどう描画するか.

考えてみて欲しい: 地球の腰回りはおよそ 40,000 km. 小さな世界が可愛いなんて言ったやつは誰だよまったく. 仮に 1 平方キロメートル範囲の色を (メルカトル投影とかで平面に落としてから)わずか 1 ピクセルに保存するとして, これは 40,000 ピクセルの幅を持つ. 高さはだいたい半分. 今日のグラフィクス・ハードウェアが扱えるサイズよりだいぶでかい. なにしろこの画像は最低でも 800 メガピクセル, 2.4 ギガバイトもあるんだから. 大半の PC は今でも メインメモリに 2GB も載せていない. 描画に使うビデオメモリについては, 典型的な PC だと 128MB, 上位のゲーム用マシンでもせいぜい 512 MB だ.

忘れちゃいけないのは, これはピクセルあたり 1 平方キロの並画像についての話だということ. これだと最小の分解能は 2 キロメートル幅で, (ナイキスト氏に感謝を.) ビル, 川, 道, 人などはさっぱり見えない. でもアメリカの主要都市に限れば, Google Earth の分解能は 1 メートルの半分かそれより細かいくらい. 少くとも 4000 倍は密だ. つまり上の例に対し 千六百万倍 のストレージが必要になる.

こんな画像を扱うには文字通り何テラバイトもの大きさが必要だ(し, 現にそのくらいある). このサイズを現行の PC で描画する方法はない. ましてリアルタイムでは無理だ.

でも Google Earth はそれを起動するたびにやってのける.

考えてみて欲しい: 真の 3D 仮想地球では, 視点を動かしたり傾けたりするのは自由だ. どこだって見える. (地底は除く...データがあればできるかもしれない.) どの 3D 地球でも, なにかしらの元データはある. 典型的には地球表面全体の超高解像度画像か, 少なくともその会社が買った範囲の画像がある. 元データはユーザの画面に届き, 仮想地球, 理想的には小さな 3D の面(三角形とか)に マッピングされ, 本物の陸, 山, 川などに見せかける必要がある.

もしソフトウェア設計者が移動や回転を制限しようと決めたなら, おめでとう. 工学上の問題は単純化され, 時間も節約できるだろう. でもそれは Google Earth じゃない.

現在, この特大テクスチャの一部分を "動きまわる" ための方法はいくつか知られている. 他の地図アプリケーションはそれぞれ独自の方法で問題を解決している. そして大半は見た目に無視できない欠点がある. 大半のものは巨大な地球を小さな正則タイルに分割し, それをおそらく四分木に保存する. それからある瞬間に必要な分だけのタイルを画面に描画する. (Google Maps のように) 2D で書いてもいいし, Microsoft の Virtual Earth はこの方法で 3D を描いているように見える.

しかし Google Earth が使う方法は本当に革新的だ. これは特許に値する. (ふだんの私はソフトウェア特許に反対しているけれど.) 説明のために, これからいくつかのコンセプトを組み立てていく. 離散信号理論やコンピュータグラフィクスの背景知識は役に立つ. けれどそれなしでも理解できるくらい易しい話にできればと思う.

ここで 3D レンダリング の仕組みを説明するつもりはない. 他をあたってほしい. ただ テクスチャマッピング と特に テクスチャフィルタリング には 焦点をあてて話す. これが原理の肝だからだ. 基本的なコンセプトから高度なテクスチャフィルタリングの話に進むことで, これがなぜ動くのか, この技術がどれだけ驚くべきものかを理解する助けになるだろう. 辛くなってきた人のために, まずは駆け足でテクスチャフィルタリングを勉強しよう.

基本

2D 画像の拡大, 回転, 引き伸ばしの問題は遠い昔に解決された. もっとも一般的な解は バイリニアフィルタリング と呼ばれる. これは要するにこういうものだ. 新しい(回転, 拡大後の)ピクセルを計算するとき, まず 4 つの "最良" ピクセルを元画像から持ってくる. 次にそれらをブレンドする. "バイリニア" というのは, まず(同じ軸にある)二つのピクセルをブレンドし, それから(軸の異なる)二つの結果をブレンドして最終的な答えを出すからだ.

("リニアなブレンド" という言葉がわからない人に補足しておく. 簡単な話. A の色を 40%, B の色を 60% もってきて, それを足すだけだ. 40/60 の分割が変数になり, これが各色の "重要度" をあらわす. ただし合計は 100% になる.)

この機能は 3D グラフィクスのハードウェアに組込まれている. だから計算機は文字通り毎秒数十億回もこの計算ができる. お気に入りのペイントプログラムがなぜ遅いかは知らない.

解決すべき問題は簡単に可視化できる...だから私はコンピュータグラフィクスが好きなんだ. 元ピクセルを他の(回転, 拡大, 移動後の)出力ピクセルにマップする時に問題が起こる. 見た目の情報が失われてしまう.

この問題は "エイリアシング" と呼ばれている. これは元の画像をデジタルでサンプルしたために起こる. サンプルは一方向で, ある周波数(解像度)を持つ. だからこれらのデジタルデータを再サンプルしても噛み合わないことがある.

さて, 出力ピクセルの行き先について話すとき, その行き先がペイントプログラムのビットマップなのか Google Earth のような 3D アプリケーションのウィンドウなのかはあまり関係がない. エイリアシングは出力ピクセルが元画像のサンプリング幅(周波数, 解像度)と揃っていないと起こる. そしてエイリアシングの見た目はよくない. エイリアシングにどう対処するかがテクスチャマッピングの仕事の半分だと言える. もう半分はメモリ管理. この制約はどちらも Google Earth の仕組みを浮き彫りにしてくれる.

そしてやるべき仕事は, 冴えたやりかたと良い設計で エイリアシングを最小化することだ. 出力ピクセルと入力ピクセルの比率をできるだけ 1:1 に近づけられれば一番良い. またはピクセルを余分に生成し, それを無難に出力へダウンサンプルしても エイリアシングは最小化できる. ("アンチエイリアシング" としても知られる.) 同時に両方使うことは多い.

考えてみて欲しい: 画像のサイズを変えると事態は悪化する ... 出力画像の各ピクセルは元画像の数百ピクセルに対応するかもしれない. 逆もありうる. バイリニア補間最良の 4 ピクセルしか使わず, 他は無視してしまう. だから重要なピクセルを飛ばしてしまうこともありうる. エッジ, 影, ハイライトなどだ. もしそのピクセルがあるフレームではブレンドされたのに続くフレームでスキップされたら, これは鬱陶しい "ピクセル・ポッピング" やチラつきを招く. ビデオゲームで目にしたこともあると思う. これで仕組みはわかったよね.

画像上の視点移動(や 3D 変換ならなんでも)は更に問題が多い. 拡大や回転がある上に, 描画する面のピクセル密度に大きな幅がでてしまうからだ. たとえば画面の "手前(near)" では, 高解像度のナイスな地形画像も滲んでしまう. 一方で "奥(far)" では 2x2 のバイリニア補間が詳細をスキップするせいでチラつく.

より良いフィルタリングを持ち込む

大半の庶民向け 3D ハードウェアは既に "トライリニア" フィルタと 呼ばれるものをサポートしている. トライリニアと, 関連した 'ミップマップ' と呼ばれる技術では, ハードウェアが入力画像やテクスチャの低解像度版一式を計算して保持する. 各ミップマップは自動的で 1/2 のダウンサプルを行う. ダウンサンプルは 1x1 のサイズになるまで再帰的に続く. 1x1 ピクセル画像の全入力画像全体の平均色になる.

例えばハードウェアに 512x512 の入力画像を渡したとしよう. ハードウェアは 8 つのミップレベルを計算して保存する. (それぞれ 256, 128, 64, 32, 16, 8, 4, 2, 1 ピクセル四方.) この "ミップスタック" を可視化するのは簡単だ. これを縦に積み上げればいい. 各ミップレベル(の断面)は一つ上のレベルと比べて 1/2 の幅になる.

3D 描画の際, ミップマップとトライリニアフィルタはそれぞれ出力ピクセルを受け取り, 最適なミップレベルを二つ選ぶ. 二つのミップレベルそれぞれでバイリニアフィルタをして, その結果を再度(線形)補間する. これでようやくトライリニアの結果が出る.

例をあげよう. あるピクセルを描くとき, もし入力画像が 47.5 ピクセル平方の解像度を持っていればエイリアシングが起きないとする. システムは 2 の乗数 (16, 32, 64, ...) でミップマップを保持している. 賢いハードウェア君は 47.5 に近い 64x64 と 32x32 のバージョンを選びだし, それぞれにバイリニア(4 サンプル)を計算, 結果をブレンドする.

これがトライリニアとミップマップの基本だ. 多くの標準的な 3D 変換のエイリアシングを最小化する上で, この技術は大きな役割を果たしている.

思いだしてほしい: ここまでは 512x512 といった小さな画像について話してきた. 例の全地球画像は数百万ピクセルの幅がある. この地球画像にははミップマップが必要そうだと思うかもしれない. 1 メートル解像度で考えてみよう. 本当に問題ない? すぐに気付くのは, このミップマップは 26 レベルの深さが必要で, 高解像度バージョンは 6600 万ピクセル幅になるということ. これじゃ出回っている 3D ビデオカードで使えない. 少なくともあと 10 年は無理だろう.

Microsoft の Virtual Earth はこの制限を回避するために 巨大な地球テクスチャを小さな, たとえば 256 ピクセル平方のタイルに分割している かんじがする. ミップマップは個々のテクスチャが持っている. このアプローチはある程度うまくいくだろう. でも速度は遅くなるし見た目の問題もある. 既に見たような滲みや, 平方の範囲を越えてズームイン/アウトした時のポッピングがそうだ.

ミップマップについて理解しておくべき最後のポイントを抑えてから 本題に入ろう. ここで一旦, 先に説明したミップマップの各レベルを色で表現した状態を考えてみてほしい. レイヤ全体が 赤, 黄, ... と色分けされているわけ. このミップマップを(Google Earth の "plane" のように)斜めから描くと, ミップマップのピラミッドを気になる角度から "薄切りにして" 見たようになる. この視点ではピラミッドの該当部分だけが使われている.

ミップマップの持つこの特徴が Google Earth を成り立たせている.

左の図は Google Earth で普通に描いた 3D シーン. 右が 3D ハードウェアがミップスタックのどこを最良の入力画像として選ぶかを図示したもの. 各レイヤが色付けされているとする.

手前の領域は最高解像度のミップレベル(赤)で塗り潰す. 視点が遠くへ離れるにつれて解像度は下がっていく. こうして先に説明したチラつきその他のエイリアシング問題を回避している. ピクセル単位でなるべく 1:1 に近い入力/出力比を保ち, エイリアシングは最小化される.

もっと良い方法もある. 3D グラフィクスハードウェアのトライリニアフィルタは 異方性フィルタリング と呼ばれる方法で改良できる. (Google Earth の設定でも簡単に選べる.) 基本的なアイデアは先に説明した通りだけれど, フィルタの際に基本だった 2x2 の正方形以外を使う. これは見た目の品質に大きく寄与する. たとえ優れもののミップマップを使っても, テクスチャつきポリゴンを大きく傾けて見ると厳しい. チラつきを避けたいハードウェアは低い解像度のミップレベルを選択し, 結果としてポリゴン全体がその低すぎる解像度のサンプルを使ってしまう. 低解像度が必要なのは片側だけなのに. もしハードウェアが異方性フィルタリングをサポートしているなら, それを有効にすると良い結果が得られる. これは割に合う.

さあ本題に入ろう

さて, 解決すべき問題が残っている. 各方向数百万ピクセルもあるテクスチャをどうミップマップするか. ユニバーサルテクスチャ (Google Earth の特許) は, 高品質のテクスチャフィルタリングを実現しながら問題を解決している. この方法は数テラバイトの巨大な地球全体の仮想テクスチャを 極めて冴えたやりかたで構築する. こんなことが言えるのは, 私がこれを発明したわけではないから. Chris Tanner がこの方法を編み出し, それまでは専用の回路を持つ高価なグラフィクス・スーパーコンピュータでしか できなかったことを PC 上で実現した. スーパーコンピュータの専用回路は クリップマッピングという. (Chris, Michael らによるオリジナルのハードウェア実装に関する詳細は SGI の PDF 記事 を参照.) まさにこの技術が Google Earth を可能にしている. そしてそのプロジェクトで, 私の初仕事はこれをインターネット接続の上で動かすことだった. その話は後述.

さて, これはどんな仕組みなんだろうか.

もちろん巨大な全地球テクスチャを一度にロードして描画することはない... 現行のハードウェアではできない. 数百万のタイルに分割することもない. フィルタリング品質や効率が落ちてしまう. 思い出してほしい. ある瞬間にユーザが使うのはミップマップの限られた一部のスライス、 ミップマップピラミッド全体の一部の列だけだった. ピラミッド内の列, 角度, 高さはその時の 3D の視野から決まる. 急に変わることはないし, 利用パターンは素直だ. 賢いアルゴリズムなら, 今自分がどこにいて何を描こうとしているのかを求めたり推理したりすることができる.

その賢いアルゴリズムは, ある瞬間に巨大な仮想テクスチャのうちどのセクションが必要かを導きだす. そして必要な分だけをシステムメモリからビデオカードのテクスチャメモリに読み込む. テクスチャメモリに置けば描画は効率的で, リアルタイムに動く.

ミップマップとの概念上の主な違いは, それが単なるピラミッドではないこと. もっとずっと細長く, クリップしたテクスチャのスタックになっている. 変な名前だけれど "クリップスタック" という. これは 16-30 レベル以上の高さを持つ. 概念的には 16-30 レベルの深さと数万数億ピクセルの幅を持つ 巨大なミップマップピラミッドがあるのと同じ. ただし端は クリップ されている. 今はまだその部分が必要ないからだ.

ワシントンの記念碑を天地逆さまにした状態を思いうかべるといい. ピサみたいに傾いた塔でもいい. 近づいてみる. 塔は傾いていて, その塔の中にあるピクセルが今まさに描画しようとしているもの. 他は無視する.

各クリップレベルも一段下と比べて倍の解像度を持っている. ミップマップと同じだ. フィルタリングも同様に使える. ただしクリップスタックの大きさは固定されており, たとえば 512x512 になる. (これも Google Earth の設定にある.) 各クリップレベルは一段前に対して倍の有効解像度と半分の対象範囲を持つ. (訳注: ミップマップはサイズが倍で範囲は同じ.) これはまさに求めていたものだ. 限られた視野の範囲に限って巨大なミップマップの恩恵を受ける.

もう一つのポイントとして, Google Earth は視野の中心(先の図で赤かった部分)から うまくプログレッシブに高解像度の情報をロードしていく. 中心から離れると解像度は二の乗数で下がる. 移動して飛び回り, 地面から地平線の方を見るごとに, ユニバーサルテクスチャ は いちばん使いたい詳細度のテクスチャを最適な形で送信し, ハードウェアに送り届ける. 必要の無いものには触れることすらない... おかげで超効率的に動く.

この方法はメモリ効率も良い. この地球大のテクスチャサイズの合計は今や (ベースのミップマップが幅 512 ピクセル, クリップレベルが 20 だとして) たったの 17 メガバイト だ. 恐怖の数十数百テラバイトではない. これなら現実的だし, メモリが 32MB もない 1999 年の 3D ハードウェアでも動く. 3D カードが大きくなるにつれ, 他の技術も徐々に使えるようになってきた.

実際には, わずか 20 のクリップレベル(と基底ピラミッドの 9 のミップレベル)だけで 2^29 もの仮想テクスチャを作ることができる. これは各次元について最大 5 億 3,600 万ピクセルを持つことができる. 面積にすると 数百テラピクセル, 0.15 メートルの細かさまで表現できる. これが本当の上限というわけではない. 適当な数字として 20 にしただけ. 数メガピクセルを越えたデジカメの競争は厳しいと思っただろう. それに百万を掛ければ地球丸ごとが入ってしまうわけ.

幸い, 今のところ Google が実際に保存する必要があるのは 数十 テラピクセルの 画像だけでいい. このシステムの優れたところは, 最高解像度の画像を全ての場所で用意する必要が無い点にある. 解像度に制限のある場所, 境目, データ紛失など...では, 持っている分で描けばいい. 高解像度のデータがあるなら, それも取得して描く. なければ, データのうちひとつ低い解像度のバージョン(上述のミップマップ)を使う. 空白にはしない. 綺麗ではっきりした絵の領域がある一方で, 一部地域でズームをすると巨大なボケ画像になってしまうのはこんな理由. データの有無が全てであり, 3D 描画の限界というわけではない. データさえあれば, 大洋の真ん中でセンチメートルの解像度を持つことだってできる.

これら全てがうまくいくのは, ユーザが 3D 地球の周りを動くごとに システムが新しいテクスチャを効率的に ローカルのディスクキャッシュや主記憶からページングできるからだ. (データがどうやってディスクキャッシュに届くかは次回.) このテクスチャアップロードは気付かない間に目にしているはずだ. これら全てがスムーズに動くという激務には心打たれる. 地球をストローで吸ってるかんじ.

そろそろ最後だけれど, 話を進める前にまだいくつか見所がある. 特許では非同期の挙動を強調している. これはテクスチャ断片を 3D ハードウェアへ連続的にアップロードするのに, 少しとはいえ全体では結構な時間がかかるため. そこで時間をかけると, 3D 画像の描画をスムーズにカクつかないよう描画したり, ユーザの入力をすみやかに処理することができなくなる. 言うまでもなくハードウェアが一杯一杯になってしまうわけ.

大半のハードウェアで安定した毎秒 60 フレームを出すために, テクスチャのアップロードは小さな細かい断片に分割される. そうすればグラフィクス用ビデオメモリを素早く かつ必要とされる直前に視野内の素材データで更新できる. でも本当に冴えているのは, システムが必要最小限のテクスチャしかアップロードせず, 何も待たせることがない点だろう. おかげで描画はスムーズになり, ユーザーインターフェイスもなめらかだ. この非同期の仕組みがなかったら, 東海岸から西海岸まで綺麗な放物線を描いて移動することは諦めなければいけない.

さて, 他の仮想地球でも地球全体のテクスチャは仮想化できる. たぶんタイルに分割し, 2 の乗数で複数解像度を持たせればいい. Google Earth がそうしているように. でもこの ユニバーサルテクスチャ のコンポーネントか より優れた仕組みがなければ, いまいちな結果しか得られないだろう. 描画を 2D の見下ろし視点に限定するとか, 3D 描画でも滲みやチラつきがあったり, キャッシュからテクスチャメモリへのストリーミングも性能がでないみたいな.

というわけで, 地球全体をどうやって毎フレーム画面に描くのか, きみの知りたい以上の話だったと思う.

今回はここまで. 次回は Google Earth がデータを計算機へ届けるストリーミングについて, 二番目の特許の話をしたい.