「点群表示機能を自作してみる」のその４です。
今回は10億点を表示するための方策を検討します。
コードの変更はありませんが、ここからが本番です。

検討

1度に描画することができない規模の点群を描画するためには、点数を減らすことが必要になります。その手段を検討していきます。

案１見えない点の描画を省略する（点数削減方法その１）

上図は透視投影の模式図です。(A～Cは点群ないし物体と思ってください。)この図において、Bの描画をしないことを案１とします。直観的で分かりやすいかと思います。この方法は次に述べる点の間引きと違い描画結果を変えません。

見えない点というと A の陰にあるCも同様に見えない点と言うこともできます。(見えないと思ってください。）ですが、ここでは省略の対象としません。この判定をCPUで高速に行うのが容易ではなく、GPUで処理することが合理的と思うためです。一方Bが視野外か否かを判定するのは、Bounding volume を用いると容易に判定できます。

視野外の点の描画を省略することは実現できるとして、それだけでは点数の削減が十分でない場合があります。具体的には上図のAやCが高密度点群がある場合「見える点群」が大規模になるでしょう。そのため、次の「点の間引き」が必要になります。

案２点を間引く（点数削減方法その２）

次に考えるのは点の間引きでしょう。これも分かりやすいのですが、間引いた点群の描画結果は当然ながら元の点群の描画結果とは一致するとは限りません。「間引いても問題ない」という前提が成り立つことを仮定することになります。この前提は成り立つ場合もありますが、特定の狭い領域のみ表示する場合は多く成り立たないでしょう。

この前提が成り立つケースとして、正確な描画が必要ない場合があります。典型的なケースとしてビューを動かしている時にはFPSを重視して描画データを軽くすることがあります。

このアイデアをおし進めるとプログレッシブ表示というアイデアになります。描画に使える時間が短い場合は疎なデータを、時間が長い場合はより多いデータを表示するという方法です。粗密の2段階ではLOD (Level of detail)表示と呼ばれるかもしれません。多段にするとプログレッシブ表示と呼ばれる機能になります。点群の場合は時間と共に追加の点群を描画していくことで、自然にプログレッシブ表示を実現できます。
プログレッシブ表示の可否は描画の目的によるかもしれません。今回はマシンスペックを補う方法として可とします。

案３高速に描画する

点を削減するのとは逆に高速により多くの点を描画する方向の工夫も考えられます。これは描画データ(バーテックスバッファ)の事前構築と、その使いまわし一択と考えます。案とか言ってますが GPU を用いて描画する場合の普通の実装でしょう。
但しハードウェアの過信は禁物で、この方法だけでは描画時間が十分に早くならないことも考えられます。実際今回のハードウェアでは100万点を超えてくると必要なFPSが得られないというのが前回の結果です。何点まで効果があるかはハードウェアに依存するでしょう。 (さすがに NVIDIA のGPUなどで100万点までしか扱えないことはないはず。)

バーテックスバッファにデータを入れるとGPUのメモリを圧迫します。GPU に乗る量の点群にしかこの方法は使えないということです。ハードウェアによってはRAMをGPUメモリのように扱える場合もあるかもしれませんが、いずれにしてもメモリ使用量が扱える点数の上限となります。

案４メモリに乗りきらない点群を扱えるようにする

それでは逆にメモリに乗らない規模の点数を扱うにはどうしたらよいか。これも一択で、一言で言えば Out of core 実装を採用するということになります。ここでは描画データをそのイメージのままファイルに保存しておき、ファイルから読んだイメージをそのままバーテックスバッファにコピーして描画することを指します。
実装方法はいくつかあるかもしれませんが、Windows の場合メモリマップドファイルを使うのがよいと考えます。ページファイルのIOと同様の機能であり、最大のパフォーマンスが得られるはずと考えるためです。

ファイルに情報を保存することから、ディスクIOのパフォーマンスが重要になります。そのためHDDではなくSSDを要求することになる可能性が高くなります。(SSDの使用もメジャーになってきたとはいえ、この点はもう少し工夫したい。)

物理メモリ量が多いPCにおいては使用していないメモリは最近の Windows ではファイルキャッシュとして利用されます。そのため Out of core を採用する場合、ファイルの内容がキャッシュされることで実際上メモリに乗っているデータにアクセスするだけになる場合も考えられます。この場合、2回目以降のアクセスでは HDD/SSD を問わず十分速い速度で点を描画できるでしょう。（大規模な点群ファイルのうち実際に描画される一部だけがメモリに乗るイメージです。）

試作方針まとめ

以上を踏まえ、以下の方針で試作することにします。

プログレッシブ表示を行う。（案２）
- 点群に対し前処理で LOD のデータ構造の構築を行う。
- この中で Out of core 実装も採用する。（案４）
点群データを位置で分割する。（案１）
- 見える、見えないの判定の他、遠くの点は詳細を表示しない、といった処理も加えます。（上記のLOD構造のうち、粗い部分だけを描く。）
- 分割数が多くなる場合は、分割したサブ点群は木構造で管理し、O(log) で描画すべきデータを絞る。

今回はチープなハードウェアを前提にするため、案３のハードウェアを活用するバーテックスバッファを事前構築する手段は実装保留します。