はじめに
今週のAKARI Tech Blogは、DX Solution 事業本部 Dev nebulaの西宮が担当します！
今回は、開発している三次元シミュレーションソフトに点群表示を実装する際に行った工夫について紹介します。
建築、都市計画、自動運転など、多くの分野で大規模な点群データを扱う機会が増えています。
しかし、数千万から数十億に及ぶ大規模点群のなかをGoogle Street Viewのように自由に移動しながら表示するには、パフォーマンスの面でいろいろな工夫が必要です。
本記事では、一番簡単でオーソドックスな実装だけではなく、より大規模なシーンをレンダリングするための主要なアプローチをOpenGLでの描画を前提として解説します。
（同じシミュレーションソフトで学習画像を自動生成しSim2Realした例もあります。良ければご覧ください）
tech.akariinc.co.jp
従来の点群描画とGL_POINTSの限界
OpenGLで点群を描画する最も基本的な方法は、古典的な描画プリミティブとしてGL_POINTSを使用することです。（DirectXでいうD3D_PRIMITIVE_TOPOLOGY_POINTLIST、VulkanのVK_PRIMITIVE_TOPOLOGY_POINT_LIST）
// GL_POINTSを使って点群を描画するC++サンプルコード GLuint vertex_array; // VAOを生成 glCreateVertexArrays(1, &vertex_array); // 同様にVBOの生成も実装し、点群情報を格納する.... glPointSize(2.0); // 点群の表示サイズ [px]を指定 glBindVertexArray(vertex_array); // VAO (Vertex Array Object)をバインディングする int num_vertices = 3; glDrawArrays(GL_POINTS, 0, num_vertices); // 頂点バッファの内容を点の集まりとして解釈してフレームバッファに描画
詳細な実装例は以下のような記事を参照
床井研究室 - Point Sprite を使ってみる
この方法はシンプルで直感的ですが、点の数が増えるとパフォーマンスが急激に悪化します。なぜなら、グラフィックスパイプラインが元々「三角形」の描画を想定しているため、各頂点が必ず頂点シェーダーやフラグメントシェーダーといった多くの処理を通過する必要があるからです。
数億もの点群を一つひとつこのパイプラインに乗せると、そのオーバーヘッドは無視できなくなります。
手法1: compute shaderで高速化する
根本的な解決策の１つとして、既存グラフィックスパイプラインを迂回し、Compute Shaderを使って点群を描画するアプローチがあります。
これによりGL_POINTSよりも10～100倍高速にレンダリング可能です(下図)。
以下はCompute shaderを使った点群の描画方法の実装とその論文（READMEにリンクあり）です。
https://www.cg.tuwien.ac.at/research/publications/2021/SCHUETZ-2021-PCC/SCHUETZ-2021-PCC-paper.pdf
この手法の基本的な考え方は、以下の通りです（論文中の「render pass」）。
- 点群の各頂点を、画面上の位置（スクリーン空間）に変換する。
- 各点の深度（奥行き情報）と色情報を、単一の64ビット整数にエンコードする。
- このエンコードされたデータ(色 + 深度情報)を画面上*1の1ピクセルに直接書き込む。
手順2.ではatomicMinというGLSL関数を使うことで、複数の点が同じピクセルに描画される場合でも、一番手前にある点（深度値が小さい点）の色を正しく表示できます。これにより、遠近感の整合性を保ちながら、高速な描画を実現します。
// 点群の各点に対して実行されるcompute shaderのGLSL // それぞれがフレームバッファの1ピクセルを塗り替える uint pixelID = x + y * imageSize.x; vec4 pos = worldViewProj * position; int64_t depth = floatBitsToInt(pos.w); int64_t point = (depth << 24) | rgb; // 一番手前の色とdepthでフレームバッファのpixelID番目の値を上書きする // point変数の上位ビットがdepthになっているため、atomicMinをとると手前の点群で上書きされる atomicMin(framebuffer[pixelID], point);
// 上記GLSLを実行するためのC++コード // Compute Shaderの実行部分のコード. 点群のXYZと色をバッファに格納し、bindしたFramebufferに結果を格納する // https://github.com/m-schuetz/compute_rasterizer/blob/f2cbb658e6bf58407c385c75d21f3f615f11d5c9/include/compute_basic.h#L93-L108 glUseProgram(csTiles->program); glUniformMatrix4dv(0, 1, GL_FALSE, &viewProj[0][0]); glUniform2i(1, fbo->width, fbo->height); glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 1, ssTileMetadata.handle); glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 2, ssTiles.handle); glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 3, ssDepth.handle); glBindImageTexture(0, fbo->colorAttachments[0]->handle, 0, GL_FALSE, 0, GL_READ_WRITE, GL_RGBA8UI); glDispatchCompute(32, 32, 1); GLTimerQueries::timestamp("compute-tiles-end"); glMemoryBarrier(GL_ALL_BARRIER_BITS);
フレームバッファには1ピクセルが64ビットの整数になっており、下位24ビットがRGB値、上位32ビットが深度という内容になっています。
その後、色と深度情報が混ざったフレームバッファを入力として、通常のOpenGLの色とDepthテクスチャに変換されて画面上表示されます（論文中だと「resolve」パス)。
// https://github.com/m-schuetz/compute_rasterizer/blob/f2cbb658e6bf58407c385c75d21f3f615f11d5c9/modules/compute_2021_dedup/compute_2021_dedup.h#L141-L161 glUseProgram(csResolve->program); glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 0, las->ssPoints.handle); glBindBufferBase(GL_SHADER_STORAGE_BUFFER, 1, ssFramebuffer.handle); glBindImageTexture(0, fbo->colorAttachments[0]->handle, 0, GL_FALSE, 0, GL_READ_WRITE, GL_RGBA8UI); int groups_x = fbo->width / 16; int groups_y = fbo->height / 16; glDispatchCompute(groups_x, groups_y, 1); glMemoryBarrier(GL_ALL_BARRIER_BITS);
Shuffled Mortonによりさらに高速化する
この手法ではレンダリングする頂点順序もパフォーマンスに大きく影響します。
論文中でもっとも安定してレンダリングできたのは、Shuffled-Mortonというソート方法です。点群の各頂点に対してmorton order(z階級曲線）でソートした後、128点のバッチに分割し、そのバッチをランダムにシャッフルします。
まず、モートンコードを使用したソートを適用することで、各点がフレームバッファの似たような位置に描画されるようになり、メモリ上の連続したデータにアクセスする可能性があがり最適化されます。しかし、モートンコードだけでは、特定のビューポイントで画面の一部の領域に点群が集中し、GPUの負荷が不均一になる可能性があります。これを解決するために、「シャッフルドモートン」は、空間的に近い点の小さなバッチをランダムにシャッフルします。
他にもこの論文では、より高品質なレンダリング方法(HQS, HQS1R）、atomicMinの呼び出しを減らす更なる最適化(early-z, reduce, dedup)なども紹介されていますが割愛します
Vertex Adaptive Precisionでメモリ使用を大幅に削減
下記論文ではさらに「Vertex Adaptive Precision」という手法が提案されています。（著者は上のCompute Shaderの点群描画を提案した人と同じ)
これは、点群の描画において、必要な座標精度のみをロードすることでメモリ帯域幅の使用量を削減する技術です。具体的には、それぞれの点群バッチについてAABB(Axis Aligned Bounding Box)を計算し、その中のどの位置にあるかの情報のうち必要な精度だけ取り出して描画するという内容です。
もっとも低解像度で良い場合は12バイト(XYZのfloat x 3)の位置データを4バイトに圧縮できます。
// 従来の頂点バッファの中身の例 struct Vertex{ float x; float y; float z; uint8_t r; uint8_t g; uint8_t b; }; // これだと、float x 3 + uint8 x3で 12 + 3 = 15バイト / 点 が必要になってしまう
// 改善後 Vertex vert; // 1. 各点に対して、バッチのバウンディングボックスのどの位置にあるか計算 float x_ = (vert.x - aabb.min_x) / aabb.size_x; float y_ = (vert.y - aabb.min_y) / aabb.size_y; float z_ = (vert.z - aabb.min_z) / aabb.size_z; // 位置を整数で表現 constexpr int UINT32_MAX = std::numeric_limits<uint32_t>::max(); uint32_t X30 = x_ * UINT32_MAX; uint32_t Y30 = y_ * UINT32_MAX; uint32_t Z30 = z_ * UINT32_MAX; // 位置情報の上位10ビットを取り出して、encoded変数に格納 uint32_t X𝑙𝑜𝑤 = ( X30 >> 20) & 1023; uint32_t Y𝑙𝑜𝑤 = ( Y30 >> 20) & 1023; uint32_t Z𝑙𝑜𝑤 = ( Z30 >> 20) & 1023; uint32_t encoded = X𝑙𝑜𝑤 | ( Y𝑙𝑜𝑤 << 10) | ( Z𝑙𝑜𝑤 << 20); // これが一番精度が低い10ビットの位置情報 // encoded変数だけで、各点がバウンディングボックスのどの位置にあるかのある程度の情報はとれる. // encoded変数は各点あたりuint32_t = 4bitなので、従来のfloatよりも莫大な容量削減ができる // より高精度が欲しい時はX_low, Y_low, Z_low変数を作る時に切り落とされたX30, Y30, Z30の下位ビットも別バッファに格納しておき、レンダリング時に随時読み込む
手法2: 可視範囲の点群だけを最低限の密度でレンダリングする
また、大容量の点群をレンダリングするために、「見えている領域の点群だけを動的に取得してGPUに渡して描画させる」というアプローチが考えられます。
>
例えばpotreeでは、8分木(octree)を利用して一度にメモリに乗らない量の点群を細かいセグメントに分け(chunking)、チャンクごとの適切な階層構造を作成することで、可視範囲の点群のみに高速にアクセスできるようにしています
potreeの描画アルゴリズムは、以下のchunking -> indexing -> merging -> 表示という4ステップで構成されます
- chunking：hierarchical counting sortを使い点群を最大1000万点のチャンクファイルに分割
- 1. カウンティング（Counting）: 点群のバウンディングボックスを、八分木（octree）と整合するように2^depthの解像度を持つ3次元グリッドに分割します(256 x 128 x 512など)。各セルは、その内部に含まれる点の数をカウントするためのカウンターとして機能します。これにより、データ全体を一度にメモリに読み込むことなく、点の空間的な分布を把握します。
- 2. 疎なセルのマージ（Merging Sparse Cells）: カウント後、隣接する8つのセル（八分木ノード）の合計点数が一定のしきい値（例：1,000万点）を下回る場合、それらを再帰的に結合してより大きなチャンクを作成します。これは、大量の微小なチャンクファイルが生成されるのを防ぐためです。点密度が不均一なデータセット（例：「ティーポットinスタジアム」問題）でも、この手法が有効に機能します。
- 3. 点群の分配（Distributing Points）: 最後に、どの点がどのチャンクに属するかを決定するためのルックアップテーブル（LUT）を作成します。その後、すべての点を再度走査し、このLUTを使って各点を適切なチャンクファイルに直接書き込みます。
- indexing
- リーフノードへの分割: hierarchical counting sortを再び使用し、各チャンク内の点を、最大サイズ（例：1万点）のリーフノードに分割します。これにより、リアルタイムレンダリングに適した、十分にきめ細かなLOD（Level-of-Detail）表現が得られます。
- ボトムアップでのサブサンプリング: リーフノードが作成された後、より粗いレベルのLODを構築するために、ボトムアップで階層をたどります。各ノードでは、直接の子ノードの点から代表的なサブサンプルが抽出され、その親ノードに格納されます。これにより、レンダリング時に必要なデータのみをロードし、効率的な描画が可能になります。
- ノードの書き込み: サブサンプリングが完了したノードは、octree.binという単一の出力ファイルに書き込まれます。これにより、各ノードが個別のファイルとして保存される従来の手法で発生していた、膨大なファイル数によるオーバーヘッドが解消されます。
- merging
- 表示
このようなプロセスを経ることで、メモリに乗らない容量の点群を必要な分だけ取り出してすぐ表示することができます。
ですが、ここまでデータ構造やファイル形式にこだわらなくても、Frustum CullingやLODなどの簡単なアルゴリズムで大幅にパフォーマンスを改善することができます
Frustum Culling (視錐台カリング)で不要なドローコールをなくす
画面上に表示されている領域の視錐台を計算し、その内部にあるオブジェクトだけの描画を行う手法をFrustum Cullingと呼ばれています(画像は燈作成）。
例えば、上図の赤い球体は描画しなくても、画面上の表示結果には影響がありません。これと同様のことを複数のチャンクに分割された点群についても適用することができます。
// Frustum Cullingのサンプル実装。glm (https://github.com/g-truc/glm 利用想定) // https://learnopengl.com/Guest-Articles/2021/Scene/Frustum-Culling using Vec4f = glm::vec4; using Mat4x4f = glm::mat4; inline std::array<Vec4f, 6> createFrustumPlanes(const Mat4x4f& viewProjectionMatrix) { std::array<Vec4f, 6> planes; Vec4f rowX(viewProjectionMatrix[0], viewProjectionMatrix[4], viewProjectionMatrix[8], viewProjectionMatrix[12]); Vec4f rowY(viewProjectionMatrix[1], viewProjectionMatrix[5], viewProjectionMatrix[9], viewProjectionMatrix[13]); Vec4f rowZ(viewProjectionMatrix[2], viewProjectionMatrix[6], viewProjectionMatrix[10], viewProjectionMatrix[14]); Vec4f rowW(viewProjectionMatrix[3], viewProjectionMatrix[7], viewProjectionMatrix[11], viewProjectionMatrix[15]); planes[0] = rowW + rowX; // Left Plane planes[1] = rowW - rowX; // Right Plane planes[2] = rowW + rowY; // Bottom Plane planes[3] = rowW - rowY; // Top Plane planes[4] = rowW + rowZ; // Near Plane planes[5] = rowW - rowZ; // Far Plane // Normalize the planes for(int i = 0; i < 6; i++) { Vec3f normal(planes[i][0], planes[i][1], planes[i][2]); float length = normal.norm(); planes[i] = planes[i] / length; } return planes; } inline bool isSphereInFrustum(const Vec3f& center, float radius, const std::array<Vec4f, 6>& planes) { for(int i = 0; i < 6; i++) { // Calculate the signed distance from the sphere's center to the plane Vec3f plane_normal(planes[i][0], planes[i][1], planes[i][2]); float plane_distance = planes[i][3]; float signedDistance = plane_normal.dot(center) + plane_distance; // If the signed distance is less than the negative radius, the sphere is completely outside the frustum if(signedDistance < -radius) return false; } return true; } bool is_bbox_visible(const Camera& camera, const AABB& bbox) { auto vp = camera.get_proj_matrix(); auto planes = createFrustumPlanes(vp); float sphere_radius = bbox.size().norm() * 0.5; return isSphereInFrustum(bbox.center(), sphere_radius, planes); }
また、昨今はCompute shaderを利用したGPUで高速にFrustum Cullingを実装する方法やOcclusion Cullingなど他のCulling手法も提案されています
LODをGPUで作ることの高速化
LOD(Level of detail)技術（カメラからの距離が遠いオブジェクトを粗く表示して描画コストを落とす方法）を点群に適用する方法もあり、たとえば以下の論文でもLODを用いた最適化が行われています。
PCIe 5.0 SSDとRTX 4090を搭載したシステムで、1秒あたり最大5億8000万点（約9.3GB/s）という驚異的な速度で、SSDからポイントをストリーミングし、GPU上でoctreeを更新できます。データセットにもよりますが、100万点をオクトリーに挿入するのに平均して1〜2ミリ秒しかかからず、1フレーム内で数百万点をLOD構造に挿入し、中間結果をレンダリングすることが可能です
この論文による面白い点は、Octreeを使うだけでなくここでもMorton Coding(Z階数曲線)による点群ソートを利用してバッチとして点群を分割し、メモリ上の局所性と物理的な点の位置の局所性を一致させていることです。
バッチの中に含まれる点の空間的な局所性が高いほど、カリングや座標圧縮の効果が高まり効率化につながっています。
類似事例
以下のような既存サービスでもこの記事で紹介した点群レンダリング手法が使われています。
主にWebサイトなど使えるリソースが限られている環境、ストリーミングでデータを取得する必要がある環境で使われることが多いようです
- Navvis Ivion
- Navvisという点群測量機のビューワーです.
- ブラウザで動作しグーグルストリートビューのような使い方ができます（上記画像）
- CesiumのTiling Point Cloud機能
- Cesiumは三次元の地形データを表示するためのWebフレームワーク
- 3D Tilesという大規模な3D地理空間情報データをストリーミング形式で配信・レンダリングするために設計されたデータ形式を作成
- Point Clouds – Cesium このCeciumが点群をタイリングし、膨大なデータを表示できる
- potreeなど多種実装やサービス
まとめ
この記事では、数千万、数十億点という大規模な点群をスムーズに表示するためのいくつかのアプローチを紹介しました。
- Compute Shaderを使って、従来のグラフィックスパイプラインの制約を打破し、描画速度を劇的に向上させる。
- morton code (Z階級曲線を利用してメモリの局所性をあげ効率化する）。
- そのうえで、局所的なバッチに分割してランダムにシャッフルすることで、メモリの局所性を保ちつつ、atomic処理によるデッドロックの発生を抑え、さらに高速化
- Frustum CullingやLODといった技術を組み合わせ、見えている範囲の点群だけを効率的に描画する。
3DCGの分野ではUnreal EngineのNanite(仮想ジオメトリ)など、大量のデータをリアルタイムに処理、描画する様々な技術が日々公開されています。
それらの最新の論文を読み解き、それを実装に落とし込むことで、技術の進歩を肌で感じることができました。
参考文献
- How we render extremely large point clouds — Magnopus
- https://github.com/AlfonsoLRz/PointCloudRendering
- https://www.cg.tuwien.ac.at/research/publications/2019/schuetz-2019-CLOD/schuetz-2019-CLOD-paper_preprint.pdf
- https://www.cg.tuwien.ac.at/research/publications/2021/SCHUETZ-2021-PCC/SCHUETZ-2021-PCC-paper.pdf
- Unreal Engine の Nanite 仮想化ジオメトリ | Unreal Engine 5.6 ドキュメンテーション | Epic Developer Community
- GitHub - Krixtalx/Nimbus: A virtualized point cloud renderer
- https://arxiv.org/abs/2302.14801
- [2104.07526] Rendering Point Clouds with Compute Shaders and Vertex Order Optimization
