[2026/8/25]

[Astro] #113 Point Cloud Viewer v8 — SOR高速化・Worker化・Delaunayメッシュ生成

概要

前回[#112]でSOR進捗表示を追加したが、処理速度自体は15分のままだった。今回はSORをWeb Worker化して根本から高速化し、さらにDelaunayメッシュ生成を追加した。

[Astro] #112 Point Cloud Viewer v7 — 任意直線断面＋SOR進捗表示

任意直線断面プロファイルとSOR非同期進捗表示を追加。

lain-lab.com

今回の追加機能

機能	概要
SOR Web Worker化＋高速化	メインスレッド完全非ブロック、15分→数分
SOR キャンセルボタン	overlay内に表示、Worker.terminate()で即中断
処理時間計測表示	SOR/Voxel完了時にalertで所要秒数を表示
Voxel Downsample Worker化	SORと同パターンでWorkerスレッドに移行
Delaunay メッシュ生成	点群→サーフェス変換、ワイヤフレーム/半透明切替
リファクタリング	ジオメトリ再構築3箇所の重複解消

スクリーンショット

SOR Worker — 進捗表示＋キャンセルボタン

Delaunay メッシュ（サーフェス表示）

メッシュワイヤフレーム表示

動画 (GIF)

SOR高速化 — 15分→数分

ボトルネック分析

v7のSORは200万点×K近傍探索がメインスレッドで同期実行されていた。ボトルネックは3つ：

全ソート: 近傍候補が数百個あっても全部ソートしてからK個取得
文字列グリッドキー: "${cx},${cy},${cz}" の文字列生成がGC圧力を生む
セル座標の再計算: KNN内で毎回 Math.floor(px / cellSize) を再計算

解決策

partial sort — K個だけ保持する挿入ソートで全ソートを廃止：

// 旧: 全ソート → O(n log n) per point
distances.sort((a, b) => a - b);
const k = Math.min(neighbors, distances.length);

// 新: K個だけ保持 → O(n·k) per point
const topK = new Float32Array(k);
topK.fill(Infinity);
// ... 各距離に対してK個の中で最大より小さければ挿入

整数グリッドキー — 文字列 → 整数ハッシュ：

// 旧: 文字列キー（メモリ確保＋文字列ハッシュ）
const key = `${cx},${cy},${cz}`;

// 新: 整数キー（即座にハッシュ可能）
const key = cx + cy * nx + cz * nx * ny;

セル座標キャッシュ — Int32Array に事前格納して再計算を省略。

Web Worker化

設計

メインスレッド                    Worker
─────────────                  ──────
Float32Array(positions) ──→    グリッド構築
                               K近傍計算(partial sort)
                               フィルタリング
                        ←──    進捗 (postMessage)
                        ←──    keepIndices: Uint32Array
ジオメトリ再構築(メイン側)

positions のみをWorkerに渡し（色・intensity等はフィルタ判定に不要）、結果は keepIndices（残す点のインデックス配列）で返す。メインスレッド側でインデックスを使って各属性をフィルタし、ジオメトリを再構築する。

Transferable による zero-copy

postMessage の第2引数に [posArray.buffer] を渡すことで、ArrayBufferの所有権をWorkerに移譲する。コピーが発生しないため、200万点（24MB）の転送がほぼゼロコスト。

// メイン→Worker: positions をゼロコピー転送
worker.postMessage(
  { positions: posArray, neighbors, stdRatio },
  [posArray.buffer]
);

// Worker→メイン: keepIndices をゼロコピー転送
postMessage(
  { type: 'result', keepIndices },
  [keepIndices.buffer]
);

キャンセルボタン

Loading overlay内に「Cancel」ボタンを配置。クリックで Worker.terminate() を呼び、処理を即中断する。処理中はSOR/Voxelボタンをdisabledにして二重実行を防止。

リファクタリング — ジオメトリ再構築の共通化

handleDeleteSelected、handleNoiseRemoval、handleVoxelDownsample の3箇所で全く同じ「インデックス配列→新ジオメトリ構築→state更新」パターンがあった。

// 共通ヘルパー
function rebuildGeometryFromIndices(
  geo: THREE.BufferGeometry,
  keepIndices: Iterable<number>
): THREE.BufferGeometry { ... }

// state更新も共通化
const applyNewGeometry = useCallback((newGeo: THREE.BufferGeometry) => {
  geometryRef.current = newGeo;
  setPointCount(newGeo.attributes.position.count);
  // boundingBox更新、updateTrigger++
}, []);

3箇所の40行前後のコピペコードがそれぞれ1〜2行の呼び出しに集約された。

Delaunay メッシュ生成

2.5D Delaunay三角形分割

delaunator を使い、点群のXY座標をDelaunay三角形分割する。Z値はそのまま保持するため、航空LiDAR等の「上から見た」地形データでサーフェスを生成できる。

npm install delaunator --legacy-peer-deps

maxEdgeLengthフィルタ

Delaunay三角形分割は凸包を生成するため、データの端や空隙に巨大な三角形ができる。maxEdgeLength パラメータで長辺三角形を除去する。

// 3D空間でのエッジ長でフィルタ
if (len01 <= maxLen2 && len12 <= maxLen2 && len20 <= maxLen2) {
  filteredIndices.push(i0, i1, i2);
}

小さい値（0.010）: 穴が多いが形状に忠実
大きい値（0.050）: 隙間が埋まるがアーティファクト増加

パフォーマンス

200万点の三角形分割が約1.6秒で完了。delaunator のアルゴリズムがO(n log n)で高速なため、Worker化しても体感は変わらないレベル。

表示オプション

Show Mesh: メッシュの表示/非表示切替
Wireframe: 三角形の輪郭のみ表示
半透明（opacity: 0.7）で点群との重ね表示
頂点カラー対応（Heatmap等のカラーモードが反映される）

変更ファイル

ファイル	変更内容
sorWorker.ts	新規 — SOR全計算をWorkerスレッドで実行
voxelWorker.ts	新規 — Voxel Downsampleの整数キー化＋Worker実行
meshWorker.ts	新規 — Delaunay三角形分割＋maxEdgeLengthフィルタ
PointCloudApp.tsx	Worker呼び出し、rebuildGeometryFromIndices/applyNewGeometry抽出、メッシュstate
PointCloudScene.tsx	メッシュ描画（THREE.Mesh、DoubleSide、ワイヤフレーム対応）
ControlPanel.tsx	キャンセルUI、メッシュUI（Generate/Show/Wireframe/Clear）、disabled制御

まとめ

v1: PLY読み込み、ヒートマップ、スライス、計測、SOR
v2: LAS/PCD読み込み、200万点サンプリング、正規化
v3: LAZ読み込み、XYZ/CSV入出力、ローディング
v4: Intensity/Classification表示、LAS/PCD/スクショエクスポート
v5: ボックス選択＋削除、断面ポリライン＋DXF、Octree LOD、座標系変換
v6: 計測ラベル3D表示、元座標復元、Voxel Downsampling
v7: 任意直線断面＋DXF、SOR進捗表示
v8: SOR高速化＋Worker化（15分→数分）、Voxel Worker化、Delaunayメッシュ生成、リファクタリング

今後の課題

Octreeに全点対応（サンプリング前の数千万点を扱う）
カメラパスアニメーション（ウォークスルー録画）
Potree形式読み込み（Octreeタイルストリーミング）
Poisson Reconstruction（3Dサーフェス復元）

概要