Clever Geek Handbook

MAPS.MEでナビゲーションデータをレンダリングするフードの下





みなさんこんにちは！ MAPS.MEアプリケーションのナビゲーションは、私たちが注力している主な機能の1つです。 最近歩行者のナビゲーションについて話しました。 今日は、MAPS.MEでナビゲーションデータを表示する方法について説明します。 ナビゲーションデータとは、ルートライン、操作を表示するための矢印、およびルート上のユーザーの位置を意味します。 この投稿は、OSMデータに従ってルートを構築するためのアルゴリズムや、操作を割り当てるためのアルゴリズムではなく、レンダリング専用です。 猫の下で興味を持ってください。



上記のナビゲーションデータを表示するための要件を定義することから議論を始めます。

  1. ルートラインは、マップの縮尺に応じて可変の太さを持つ必要があります。 明らかに、小規模では、この線は重要な地図上のランドマークと重ならないように十分に細く、しかも区別できるほど十分に太くする必要があります。 大規模な場合、ルートラインの幅は道路の幅を超えないことが理想的です。
  2. ルートの合格部分は非表示にする必要があります。
  3. 経路上に操縦を表示する必要があります。 現時点では、操縦は旋回に制限されており、回転の方向を示す矢印の形で表示する必要があります。
  4. ルートラインには任意の色（半透明を含む）を使用できます。 これで、ルート全体で色が均一になりました。
  5. ユーザーの位置は、進行方向の矢印として表示されます。
  6. ルートの終点にも特別なアイコンが付いています。


次に、これらすべてを表示するために使用できるものを見てみましょう。 ルート構築システムから得られるもの：



さらに、次のものがあります。



ポリライン上のポイントは論理的です。 このポリラインの一部ではなく、ラインの先頭からの距離として定義されます。 たとえば、0.0はポリラインの最初のポイントを示し、ポリラインの長さに等しい値は最後のポイントを示します。



すべての入力条件を決定したので、レンダリングプロセスの分析を開始します。



ルートラインジオメトリの形成



ルートラインのジオメトリを三角形のリストとして形成します。 要件に可変幅があり、各フレームのジオメトリを再形成する余裕がないため、線幅は均一な変数にレンダリングされます。 初期状態では、すべてのポイントは中心軸に沿ってグループ化されています。 各頂点について、頂点シェーダーでこの頂点をシフトする方向にベクトルを保存します（このベクトルを法線と呼びます）。 その結果、次の図のような結果が得られます。







この図は、ポイント3で2組の法線が共存することを示しています。 図で同じ色で示されている法線は互いに平行で多方向であり、そのうちの1つがわかっている場合、2番目はベクトルの逆数によって計算されます。



1つのポイントに2つの双方向の非平行法線を含めるには、ポイントを複製する必要があります。これは、ポリゴンの形成中に自然に発生します。 また、骨折部位では、形成されたポリゴンが一方の側で重なり、他方でギャップを形成することもわかります。 一見、ポリゴンの重なりは問題ないようです。 これは、ルートのラインが完全に不透明になるまで続きます。 半透明の線の場合、多角形の交点はより暗くなるため、それらを破棄する必要があります。 ギャップを埋めるのははるかに簡単で、その場所に多角形のインサートが形成されます。



重複するポリゴンを排除するため、法線を変更して、形成されたポリゴンが重複しないようにします。 これを行うには、2つの隣接する法線の平均を計算し、新しいベクトルに沿って両方の点をシフトします。







このアプローチでは、1つの微妙さが現れます。 法線は正規化されなくなりました。鋭角で頂点を大幅にシフトする必要がある場合があるためです。 既に述べたように、ポリゴンインサートを使用してルートラインのギャップを排除します。 これらのインサートを形成する3つの方法をサポートしています。







最初のケースでは、多角形の挿入は、ルートラインのセグメントの関節に内接する円の一部を三角形分割することによって形成されます。 2番目のケースでは鋭角が形成され、3番目のケースでは正確に1つの三角形が挿入されます。 ジオメトリ生成アルゴリズムは、ギャップのサイズ、法線の発散の程度を推定し、ポリゴンインサートを形成する方法の1つを選択します。 さらに、ルートラインの端にラウンドが追加されます。 それらは、第1タイプのインサートと同じ方法で形成されます。 その結果、ルートラインの複雑なジオメトリを取得しました。これは、半透明を含む任意の色で描画できます。







ルートの移動部分の表示



ルートの覆われた部分を切り取るための最も明白な解決策は、ルートが通過するときにジオメトリを再生成することです。 明らかに、この方法はパフォーマンスの点でコストが高くなります。ここでのポイントは、ジオメトリ生成アルゴリズムの複雑さではなく、新しい頂点バッファーとインデックスバッファーをGPUに送信するコストです。 GPS座標の更新ごとにジオメトリを再生成しないために、次のアプローチを思いつきました。 生成されたジオメトリの各頂点で、ルートラインの先頭からルートラインへのこの頂点の投影までの長さに等しい値を追加します。







各フラグメントの頂点間の値の補間により、ルートラインの先頭からこのフラグメントまでのルートラインに沿った距離（DISTANCE_FROM_START）に等しい値になります。 そして、次のシンプルなシェーダー擬似コードでは、ルートラインの一部が切り取られます。 



vec4 mainFragment() { vec4 color = ROUTE_LINE_COLOR; if (DISTANCE_FROM_START < CURRENT_CLIP_DISTANCE) color.a = 0.0; return color; }


ここで、 ROUTE_LINE_COLORはルートラインの色、 CURRENT_CLIP_DISTANCEはルートに沿った現在の距離です。 このアプローチには小さな欠点が1つあります。ポリゴンインサートのすべての頂点が1点で投影されます。







与えられた例では、タイプ2ポリゴンインサートに含まれるポイント1、2、および3は、値7.4でルートラインの中心軸に投影されます。 実際には、これは2つのセグメントの境界での不均一なラインの形成で表現されます。 しかし、実際、この動作は問題ではありません。ほとんどの場合、スライス（偶数または不均一）はユーザーの位置を示すアイコンの下にあるからです。



表示操作



すでに述べたように、操縦は今やターンサインのある矢印に限定されています。 ここでの主な問題は、異なるレベルのスケールで、いくつかの矢印が小さくなりすぎて読めないように1つにマージする必要があることです。







今回は、各フレームのジオメトリを再生成せずにしたかったのは明らかです。 次のアルゴリズムを実装しました。

  1. 事前キャッシュ手順。 この段階では、CPUのほとんどがロードされています。 ルート構築システムからのラインは、セグメントに分割されます。 当初、私たちは1つの分割不可能なラインで運用していましたが、その過程で長いルートを構築するときに1つの重大な問題に遭遇しました。 残念ながら、長い距離で長さを補間するとき、浮動小数点数の精度に到達しました。 アプリケーションでは、メルカトルの座標を使用します。これにより、小数点の後にかなり多くの有効数字が発生し、OpenGL ESのシェーダーでは、浮動小数点数の精度はCPUのコードの浮動小数点数の精度よりも低くなります（highpで2 -16対2 -24 ）。 その結果、シェーダーでのマテリアル演算の過程で、精度が失われ、グラフィカルなアーティファクトが出現しました。 必要な精度を達成するためのすべての試みは、第一に、フラグメントシェーダーを非常に複雑にし、第二に、機能しないルートラインの長さが常に存在していました。 そのため、メルカトル座標系で特定の距離を超えないように、ルートラインをこのようなセグメントに分割することにしました。 これで、各セグメントごとに値が相互に独立して補間されたため、精度の問題を回避できました。 セグメントの接合部に隙間がないように、カットの場所は特別な方法で選択されました。 目的の場所に最も近い破線のセグメントをカットし、同時に、操作矢印がカットポイントに到達できないように十分に長くしました。 この段階の結果として、ルートラインの三角形分割されたジオメトリを持つ頂点バッファーとインデックスバッファーのセットを取得します。
  2. 幾何データを更新する段階。 このステップに関連するコードは、レンダリングの直前にフレームごとに実行されます。 この段階の最初のタスクは、ルートラインのどのセグメントが画面に表示されるかを調べることです。 次に、可視セグメントごとに、操縦の矢印がその上に投影されます。 実際、矢印を描画する場合、ルートライン自体を描画する場合と同じジオメトリを使用し、矢印の始点と終点の座標の配列をシェーダーに渡す必要があります。 この配列を計算するには、次の手順を実行します。

    1. ルートラインのセグメントに矢印をそのまま投影します（元の配列はルート構築システムから取得されます）。
    2. 交差する矢印を1つにマージします（矢印は、メルカトルの座標とピクセルの両方で、長さに一定の制限があり、したがって交差できます）。
    3. ルートの平らな部分に完全に収まるように矢印の頭を移動します（これは、テクスチャからサンプリングするときに歪みを避けるために必要です）。


    この段階の結果として、現在のフレームに描画するジオメトリを決定し、操作の矢印の始点と終点の座標で配列を計算します。
  3. レンダリング段階。 もちろん、ここではGPUをロードしています。 レンダリングにはルートラインジオメトリを使用します（前の手順で頂点バッファーとインデックスバッファーを決定しました）。 フラグメントシェーダーでは、境界線の配列と、矢印の画像を持つテクスチャーを渡します。 境界配列の各要素には、矢印の始点と終点の1次元座標が含まれます。この座標は、ルートラインの現在のセグメントの始点からの距離です。 これらの座標に基づいて、ルートラインジオメトリ上のテクスチャマッピングのフラグメントシェーダでテクスチャ座標が計算され、指定された領域に形成された矢印が表示されます。 矢印がルートラインを超えて突出できるように、特別なライン幅が設定されます（均一な変数として設定することを忘れないでください）。 さらに、矢印のテクスチャは、尾、頭、中央の3つの部分に分かれています。 中央部分は歪みなく経路に沿って伸びることができ、尾部と頭の部分は常にその比率を維持します。 下の矢印を描画するためのフラグメントシェーダー擬似コード。 



     struct Arrow { float start; float end; }; Arrow arrows[MAX_ARROWS_COUNT]; sampler2D arrowTexture; vec4 mainFragment(float distanceFromStart, float v) { for (int i = 0; i < MAX_ARROWS_COUNT; i++) { if (distanceFromStart <= arrows[i].start && distanceFromStart < arrows[i].end) { float u = (distanceFromStart - arrows[i].start) / (arrows[i].end - arrows[i].start); return texture(arrowTexture, vec2(u, v)); } } return vec4(0, 0, 0, 0); }


おわりに



本日、MAPS.MEでナビゲーションデータをレンダリングするプロセスを確認しました。 私たちのソリューションが普遍的であると主張しているわけではありませんが、ここであなた自身とあなたのプロジェクトに役立つ何かを見つけていただければ幸いです。 MAPS.MEでのレンダリングについてはまだ説明がありませんが、読者にとって最も興味深いものを理解したいと思います。 あなたが読みたいと思うものをコメントに書いてください、そしておそらく次の投稿はあなたによって提案されたトピックに関するでしょう。


More articles:


All Articles