地図描画を支えるシェーダー技術
🎄この記事はNAVITIME JAPAN Advent Calendar 2023の18日目の記事です。
こんにちは、三代目ゆうです。
ナビタイムジャパンで地図フレームワークエンジニアを担当しています。
本日はナビタイムジャパンの地図描画を支える技術の一つ、シェーダーについてご紹介したいと思います。
ナビタイムジャパンの地図とシェーダー
現代の3DCGプログラミングにおいてはシェーダーと呼ばれるプログラムが利用されます。シェーダーとはGPUで処理されるプログラムで、高速で柔軟性の高い描画を実現するために必要になります。
ナビタイムジャパンの各種アプリ、Webサービスにおいて地図を表示するために各環境に合わせたグラフィックAPIを使用しています。
具体的には、AndroidアプリではOpneGLES3.0、iOSアプリではMetal、WebではWebGLを利用してリアルタイムの地図描画を行っています。それぞれ実装は異なりますが、描画処理にシェーダーを用いる必要があるという点では同一です。
実はナビタイムジャパンの地図でシェーダーを活用できるようになったのは最近のことで、一昔前まではAndroid/iOSアプリではOpenGLES1.1、WebではDOMを用いた地図描画を行っており、プログラマブルシェーダーを利用できる環境ではありませんでした。
しかし、近年では更にリッチな描画表現が求められるようになり、より柔軟な実装を可能にするべくシェーダーを利用できるグラフィックAPIを利用する形へリプレースしました。
シェーダーを活用した地図表現についてはぜひ過去の当社note記事も合わせてご覧ください！
シェーダープログラミングとは
この節ではシェーダープログラミングについて簡単に説明します。
3DCG描画を大まかに表すと、任意の3次元頂点郡で構成されるオブジェクト（いわゆる3Dモデル）に対して、様々な処理を施して2次元画面上のどのピクセルにどの色を出力するのかを決める事だと言えます。
この様々な処理のことを総じて専門用語ではレンダリングパイプラインと呼んだりします。このレンダリングパイプラインのうち、プログラマーによって自由に実装可能な箇所をプログラマブルシェーダー、一般的にシェーダーと呼ばれる部分となります。
このシェーダーも大まかに分けると2種類あり、頂点シェーダーとフラグメントシェーダーと呼ばれるものがあります。
頂点シェーダーは文字通り頂点に対して作用するシェーダーで、元の3Dオブジェクトの各頂点の座標を最終的な画面座標に変換する役目を持ちます。この頂点シェーダーが変換した出力はそのままフラグメントシェーダーの入力として渡されます。
次にフラグメントシェーダーは画面座標となった各頂点を結んだ三角形内の各ピクセルに対して作用するシェーダーで、最終的にそのピクセルが出力すべき色を算出する役目を持ちます。ここまで処理されることによって、最終的に画面にグラフィックを描画するということが行われております。
さて、ここでシェーダーとはGPUで処理されるプログラムとお話しましたが、CPUとGPUの違いについても簡単に触れたいと思います。
CPUとGPUはそれぞれ作られた目的も異なるため、得意とする領域が異なります。CPU（Central Proccessing Unit）は汎用的な処理を行うために作られたもので、計算精度に優れ複雑な計算を行うことを得意とします。
GPU（Graphic Proccessing Unit）は高速に画像の処理を行うために作られたもので、単純な計算を並列で高速に行うことを得意とします。これらのスペック上の一番大きな違いは実際に演算を行うユニット数となります。
例えば、一般的なPC向けのCPUでは最新のハイスペックなもので多くて24ユニット程度となる一方、GPUは数百から一万以上のユニット数を持つものもあります。演算ユニット数が多いということはつまり、それだけ物理的に同時に演算が出来るということなため、すなわち並列処理が得意という事になります。
シェーダーは頂点シェーダーであれば処理が全頂点の数ぶん、例えば全3Dオブジェクトが合計10万頂点あれば10万回実行されます。フラグメントシェーダーに至っては例えば4K解像度のディスプレイで全画面の描画を行っていれば、ピクセル数にして3840x2160で約830万回実行されるプログラムとなります。そしてこれらは画面が更新されるたびに実行されるため、60fpsで描画しようと思えば1秒間に60回も前述のプログラムが走る計算となります。
一方で、各シェーダープログラムはその実行を全て並列で行うことが出来ます。つまり、各頂点や各ピクセルの計算は他の点による計算結果に依存しない独立した実行であると言えます。そのため非常に並列計算と相性がいい、と言うより並列計算しないとまともな計算時間で処理しきれないという事になります。よって、描画処理はどれだけシェーダーで実装出来るか、言い換えればGPUに処理を任せられるかが高速化において重要な要素となってきます。
ここで、簡単な計測にはなりますが、150,000点の頂点郡に対する単純な行列計算をCPUで行う場合とGPU（シェーダー）で行う場合を比較してみました。前者はおよそ81ms、後者はおよそ16msと約5倍程度高速に実行されることが確認できました。（OpenGLES3.0環境のAndroid用デモアプリを使用し、Pixel6の実機にて計測）
シェーダーで地図を扱うことの難しさ
ここまで、描画においてシェーダーを活用することのメリットはイメージしていただけたかと思います。しかし地図描画でシェーダーを利用するにあたっては計算精度を考慮すべきことにも触れなくてはなりません。
地図を描画するためのデータというのは大雑把に言えば緯度経度の形状点列になります。
緯度経度の表し方には様々なフォーマットがありますが、最も一般的な度数表記による小数として扱うシチュエーションについて考えます。度数表記は地球一周を360度とするため、雑に計算すると地球の円周の長さを約4万kmとすると1度あたり約111kmとなります。
ここで、緯度経度の小数を表すのにどれだけの精度が求められるかを考えます。32bitの単精度浮動小数点数（いわゆるfloat）では、10進数にして有効桁数はおよそ7桁と言われています。日本の緯度経度をそのまま扱うと、整数部で緯度は2〜3桁使うため小数点以下に使える桁は4〜5桁となります。1度あたり約111kmとすると0.00001度で1〜2m程度となるため、32bitで緯度経度を扱うとおよそ1〜2mの誤差が含まれる可能性があるということになります。
この誤差をどの程度大きく見るかはもちろん扱う対象次第にはなりますが、地図描画に限って言えば十分縮尺の寄った時には1〜2mの誤差があると画面上で見て数ピクセルレベルの誤差となり、画面上で震えるような見た目となってしまいます。そのため、地図描画を想定した環境においては緯度経度は64bitの倍精度浮動小数点数（いわゆるdouble）で扱うことが一般的となります。
一方で、シェーダーでは基本的に倍精度の値を扱うことが出来ません。シェーダーで扱える数値の精度はGPU自体の実装に依存するため一概には言えませんが、基本的には高精度で32bit、中精度で16bitとなる事が一般的です。そのため、緯度経度の点列をそのままシェーダーに渡し頂点シェーダーで画面座標への変換を行うと、前述の通り精度が足りずに計算誤差が画面上の描画ブレとして顕在化してしまいます（以下図参照）。
そこで、計算精度を補うため緯度経度点列を事前に値を小さい範囲に抑えた相対座標系に加工してシェーダーに渡すようにしてみます。
具体的には、データとして取得した形状点列のうち任意の1点を代表点として、各点をそこからの相対座標系として頂点バッファに格納します。基本的に地図上で描画するデータは事前にある程度のメッシュによって分割されているため、各点列間で1度以上離れていることはありません。
こうすることで、殆どのケースにおいて各頂点の整数部が0になり、有効桁数7桁でも十分な精度（およそ1cm程度の誤差）に収めることが出来るようになりました（以下図参照）。もちろん、日本全国を横断するようなデータの場合この限りでは無いのですが、そのような形状はそもそも地図を引いた状態でしか描画しないためここまでの精度が求められることはありません。
ナビタイムジャパンの地図のこれから
ナビタイムジャパンは御存知の通りナビゲーションサービスを中心に事業を展開しています。そのため、地図に求められるものは長らく「分かりやすい案内を提供するための下地」という立ち位置でした。
しかし、近年では地図サービスの使われ方も多様化し、飲食店などのスポットを探すのにまず地図サービスを利用するという方も多いのではないかと思います。現在、ナビタイムジャパンではさらに一歩踏み込んで、見るだけで移動を喚起出来るような地図を目指しております。そのために、よりリッチで楽しさを感じるような表現を、そしてそれらを追加してなお快適に使えるパフォーマンスを目指して、表現の拡充と高速化の両翼でシェーダーを活用した研究開発を進めております。
今後益々進化するナビタイムジャパンの地図に、ぜひご期待ください！