みなさんこんにちは！ 今日は、コンピューターゲーム、アニメーション映画、工業デザインシステムに関連しないレンダリングについてお話したいと思います。 プロジェクトMAPS.MEのマップをリアルタイムでレンダリングするためのエンジンについてです。 この投稿では、エンジンの一般的な原則と、私たちが踏み込んだいくつかのレーキ（および正常に回避されたレーキ）について説明します。 大量のデータ、特にカートグラフィックのデータをレンダリングする場合、私たちの経験があなたのプロジェクトに役立つか、少なくとも興味があることを願っています。 猫に興味がある人は誰でも聞いてください。

MAPS.MEとレンダリングについて

MAPS.MEは、ユーザーが検索、ナビゲーション、さまざまな機能を備えた完全なオフラインマップをデバイス上で取得できるモバイルアプリケーションです。 OpenStreetMapから地図データを取得、処理、パッケージ化し、アプリケーションを通じてユーザーに提供します。 今日、OpenStreetMapはかなり高い詳細度で全世界をカバーしています。デバイス上で地図をレンダリングする必要があり、表示される地図データの量は非常に重要です。 マップデータを効率的に表示するために、MAPS.MEではDrapeと呼ばれるエンジンを開発しました。 このエンジンはリリースの準備が整いました。多くの点で現在のグラフィックライブラリよりも優れているため、今日（少し前に）Drapeについて説明します。



既存のプロジェクトに新しいグラフィックエンジンを作成するという決定がゼロから生じるのではないことは明らかです。以前のレンダリングメカニズムでは、プロジェクトを目的の方向に開発できませんでした。 多くの（特にgamedevの人たち）は、「エンジンライター」に対して安定した（まったく明確な）態度を持っています。 残念ながら、この分野ではサードパーティ開発の選択肢が非常に乏しく、レンダリングカードの要件はゲームのレンダリングの要件とは大きく異なります。 ゲーム開発におけるグラフィック開発者の主な活動は、ゲームのスタイルに従って仮想世界を表示することです。 常に救助に参加できるゲームデザイナー、アーティスト、モデラーは、伝統的にゲームグラフィックプログラマーの隣に立ちます：アーティファクトが遅くなったり目立たないように、ポリゴンモデルを減らしたり、テクスチャを再描画したり、ゲームレベルを再構築したりします。 さらに、オープンコミュニティの人々によってマッピングされた現実の世界を描きます。 マッピングの文化がかなり高いにもかかわらず、OpenStreetMapには多くのベクターデータが含まれており、元の形式では表示にはあまり適していません。 データの前処理アルゴリズムに携わっている人たちのおかげで、地図を描くことができます。 したがって、私たちのビジネスでは、レンダリングとデータ前処理アルゴリズムを最適化する能力のみに頼ることができます。 私たちの主なタスクは、多くのオブジェクトで構成されるマップを、できるだけ速く、美しく、盲目的に信頼できないデータに従って描画することです。 私たちのドレープエンジンが解決するのはこの問題であり、私たちの原則は順調に進んでいます。

ドレープエンジンの性質について

Webで慣れているカードについて話すと、ほとんどのアプリケーションはタイル表示モデルを使用しています。 タイルは、特定の詳細レベルのマップの一部を含む画像です。 マップを使用したさまざまな操作（スケール、パン、ブート）の間に、サーバーから必要なタイルを取得し、ブラウザーに表示します。 これらはすべて、ユーザー側でタイルをキャッシュする場合、オンラインでもわずかにオフラインでも正常に機能します。 しかし、完全なオフラインマップについて考え始めるとすぐに、このアプローチは受け入れられません。 現時点では、ユーザーのモバイルデバイスに十分なディスク領域があるように、事前に準備されたラスターデータを圧縮することは非常に困難です。 したがって、Drapeではベクターデータを操作してリアルタイムで地図をレンダリングします。 Drapeエンジンは、C ++で記述されたクロスプラットフォームのマルチスレッドシステムです。 エンジン自体は、3つのメインスレッドで動作します。

1. UIストリーム。 このスレッドでは、ユーザーアクションが記録され、特定のプラットフォーム（iOS、Android）に固有のコードが実行されます。 このスレッドは、アプリケーションが実行されているオペレーティングシステムによって生成されます。
2. FRストリーム（フロントエンドレンダラーの略）。 このストリームの主なタスクは、準備された頂点バッファーとインデックスバッファーを画面にレンダリングすることです。 このストリームは、エンジン自体によって生成されます。
3. BRストリーム（バックエンドレンダラーの略）。 このストリームでは、FRでのレンダリング用に頂点バッファーとインデックスバッファーおよびその他のデータが形成されます。 このストリームもエンジンによって生成されます。

スレッド間の相互作用は、メッセージングによって標準化されています。 FRおよびBRストリームにはメッセージキューが含まれており、制限なしで相互にデータを交換できます。 また、UIスレッドでコードの実行を要求する機能もあります。 UIスレッドは、残りのスレッドのいずれかにメッセージを送信し、必要に応じて、メッセージが処理されるまで自身をブロックできます。 エンジンの概略図を以下に示します。







この仕組みを想像しやすくするために、例を挙げて説明します。 角度の座標（この場合はメルカトル図法の投影図）で定義されたマップの長方形の断片を、指定された解像度で画面上に描画する必要があるとします。 エンジンは次の方法でこの問題を解決します。

1. UIスレッドでは、ユーザーアクション（この場合は非アクション）、およびビューポートの計算に必要なすべてが収集され、パッケージ化されてFRに送信されます。
2. 入力データに応じたFRは、ビューポート（世界のマトリックス、ビュー、投影）を形成し、地図データの詳細レベルを決定します。 計算されたデータは、いわゆるタイルツリーに投影されます。 このツリーは、グラフィックエンジンでシーンレンダリングを最適化するために広く使用されている悪名高いクワッドツリーにやや似ています。 クワッドツリーの場合と同様に、タイルツリーではネストスペースの概念がサポートされています。 たとえば、第7レベルの詳細の4タイルは、第6レベルの1タイルになります。 従来のクワッドツリーとは異なり、ツリーは現在表示されているタイルのセットに応じて構造を再構築します。 つまり 現時点で第6レベルの詳細のみのタイルが表示されている場合、ツリーはリストに縮退しています。 また、ユーザーが突然マップの第7レベルの詳細にズームインすると、第7レベルのタイルは対応する第6レベルのタイルの子ノードになります。 7番目のレベルの4つのタイルがレンダリングのために準備されると、6番目のレベルの対応するタイルがタイルツリーから強制的に削除されます。 ここで、タイルとは事前に準備された画像を意味するものではないことを明確にする必要があります。 ツリーは、空間の領域とこれらの領域に関連付けられたグラフィックデータ（頂点およびインデックスバッファー、テクスチャ、シェーダーなど）でのみ動作します。
   
   タイルツリーの性質について簡単に説明した後、FRに戻りましょう。 新しいビューポートを自由に使用できるようになると、FRは、表示されなくなったタイルツリーのノードをマークし、新しいビューポートを完全にカバーするためにツリーに表示するタイルも決定します。 このデータはすべてメッセージにまとめられ、BRストリームに送信されます。 この時点でのFRストリームは、新しいマトリックスを考慮に入れて、現在の内容を引き続き表示します。
3. BRはメッセージを受信し、新しいタイルのジオメトリ（およびその他の関連するグラフィックデータ）の生成を開始します。 複数の補助スレッドを使用して生成を並列化します。 タイルのグラフィックデータが形成されるとすぐに、すぐにFRストリームにメッセージで送信されます。 この時点で他のタイルはまだ生成中です。
4. FRは、タイルのグラフィックデータを受信し、タイルツリー内の場所を検索し、現在の状況に応じてツリーの構造を再編成します。 次のフレームに新しいデータをすでに描画できます。 時間の経過とともに、FRはすべてのタイルのデータを受信し、UIストリームから新しいビューポートが到着するまでシステムは停止します。

もちろん、エンジンの主な原理に関する上記の説明は高度なものです。 これらすべてをC ++コードで具体化すると、膨大な数のニュアンスがあふれますが、そのいくつかを次に検討します。

ニュアンスについて

スレッドの同期とパフォーマンス

気配りのある読者は、ユーザーがカードを動かした状況でスレッドが互いに積極的にメッセージを交換すると推測できます。 デバイスの画面上の指の動きは通常スムーズです。つまり、FRストリームに大量のメッセージが送信され、それぞれがFRからBRに多数のメッセージを生成します。これには、重いジオメトリ生成操作が伴います。 あなたが理解するように、見込み客は不快です。 この問題を克服するために、私たち自身の歌の喉を踏んで、ビューポートを設定するためにメッセージを使用することを拒否しました。 これは、UIストリームからのデータがキューをバイパスしてFRストリームに直接プッシュされる場合のみです。 また、ビューポートはフレームごとに1回更新されます。



一般に、スレッドセーフキューがある場合、常識的に、メッセージトラフィックは可能な限り低くする必要があります。 メッセージが少ないほど、書き込み/読み取り時にブロックされるキューが少なくなります。 生成プロセスの最後に、BRからFRにグラフィックデータが送信された多数のメッセージがあります。 この問題を克服するために、データの集約を開始し、さまざまなジオメトリを共通のバッファーに収集しました（これは、描画呼び出しを最小限に抑えるためにレンダリングする場合にも便利です）。 その結果、バッファのサイズが16ビットインデックスでアドレス指定する際に許可されている最大値に近づいていることになりました。

OpenGL ESからの燃えるような挨拶

OpenGL ESとマルチスレッドは非常にホットな組み合わせです。 特にAndroid OSでは、モバイルグラフィックチップのドライバーによって状況が悪化しています。 問題は、開発の全過程で実際に発生し、現在発生しています。残念ながら、発生しなくなるという事実の前提条件はありません。

1. OpenGLコンテキストはオペレーティングシステムによって作成され、FRおよびBRストリームに独自のものです。 OpenGL仕様では、作成されたストリームの外部のコンテキストへのアクセスが禁止されています。 ただし、グラフィックリソース（少なくとも一部）はスレッド間で共有できます。 これだけで、リソースの非同期プロビジョニングが可能になります。 OpenGLコンテキストで動作する2つのスレッドがあり、これらのコンテキストの有効期間を制御するオペレーティングシステムスレッドがあることがわかります。 たとえば、Android OSでは、アプリケーションがバックグラウンドに移行すると、OpenGLコンテキストが平和的に消滅する可能性があります。 そしてこの時点で、コンテキストを使用する両方のスレッドは、すべてのリソースを解放し、OpenGLコマンドの実行を停止するはずです。 これにより、システムスレッドが完了する前にFRスレッドとBRスレッドの寿命を制御するために、これらのスレッドが完了するように余分な努力をする必要があります。
2. フォントのグリフもBRストリームに用意されています。 これらは、最初にFreeTypeライブラリを使用してロードされ、SDF（ 符号付き距離フィールド ）アルゴリズムによって処理され、次にglTexSubImage2D関数を使用してテクスチャに移動されます。 一方のストリーム（BR）はテクスチャに書き込み、他方（FR）はレンダリング時にこのテクスチャから読み取ります。 残念ながら、すべてのドライバーがこのタスクに対応したわけではなく、 glTexSubImage2Dへの呼び出しをレンダリングストリームに転送する必要がありました。 BRストリームだけでレンダリング用のデータが準備されるわけではないことがわかりました。
3. シェーダーをリンクした直後にglDetachShaderを呼び出し 、シェーダーで0を掛けると予測できない結果が生じる場合、 glGetActiveUniformが動作しないTegra 3チップに特に満足しています。

幾何学的な更新

レンダリングプロセス中にジオメトリを更新する必要がある場合に、状況が発生することがあります。 以下は頂点アニメーションについても当てはまりますが、頂点アニメーションについても話していません。 私たちの場合、主な例は、マップの縮尺に応じて頂点データを更新することです。 たとえば、河川の流れの方向を示す矢印の場合のように、スケールに関係なくテクスチャパターンのサイズを保持する場合は、頂点データを更新する必要があります。 場合によっては、頂点バッファーの長さに等しい均一変数の配列が必要になるため、均一変数を使用するソリューションは必ずしも適切ではありません。 この問題を解決するために、次のトリックを使用しました。 頂点バッファーの不変部分を標準的な方法でパックします。たとえば、次のとおりです。



{ [ 1, 1] [ 2, 2] … [ N, N] }









頂点の変数コンポーネントについては、個別のバッファーを形成します。



{ [ 1] [ 2] … [ N] }









テクスチャ座標を更新する必要がある場合、頂点バッファを1つだけ書き換えます。これにより、GPUに送信されるデータ量が大幅に削減されます。

オブジェクトの交差点

カードには、大量のテキストと記号表記があります。 ズームアウトすると、これらのシンボルが重なり始め、マップが読みにくくなります。 1つの建物には、独自の名前とアイコンが付いた多くの施設があり、大規模であっても重複します。 したがって、このグラフィック情報に優先順位を付け、重複して表示されるのを防ぐメカニズムが必要でした。 このメカニズムはオーバーレイツリーと呼ばれます。 このメカニズムの本質は非常に単純です。レンダリング時、すべてのテキストと文字データは、画面上の位置に従ってkdツリーを形成します。 ツリーから、現時点で表示する必要があるオブジェクトを決定し、これらのオブジェクトの優先順位が作用します。 その結果、表示される最も優先度の高い非重複表記のセットを取得します。 しかし、ここで1つの不快な問題に直面しています。 アニメーション中、特にマップの回転中、ツリーがフレームごとに再構築されるため、テキストとアイコンが強く点滅し始めました。 これを回避するために、ツリーを再構築するメカニズムに慣性を導入することを余儀なくされました。

未来について

この投稿では、マップをレンダリングするためのエンジンを作成するために使用したすべてのテクノロジーを取り上げているわけではありません。 SDFアルゴリズムを使用したテキストのレンダリング、道路とルートのジオメトリを生成するアルゴリズム、アンチエイリアス、さらに別の投稿に値するはるかに価値のあるものは、点灯しませんでした。 私たちが何をしているのか、少なくとも興味を持っていただければ幸いです。 もしそうなら、将来、私たちのレンダリングと、もちろん、ドレープエンジンのリリースに関する新しい投稿を見つけるでしょう。



PS紳士、グラフィック開発者、この投稿を読んでいるときに、好みと遊女を使って自分のカードを作成したいという着実な欲求があった場合、私たちはあなたに代替があることを急いで知らせます-私たちのチームに参加する！ 質問がある場合は、PMに安全に書き込むことができます。