Convex decomposition

• 別名: approximate convex decomposition, ACD
• カテゴリ: Software & tooling › Simulation & twins
• タグ: collision-detection, simulation, geometry-processing, meshes, contact

非凸形状（通常は三角形メッシュ）を、和集合が元の形状を近似する凸ピースの集合に分割し、高速な凸形状用の衝突アルゴリズムを使えるようにすること。

定義

凸分解（convex decomposition）は、非凸形状を凸な部品の集まりに分割し、その和集合で元の形状を再現または近似する。ロボティクスでは、入力は通常、物体、グリッパー、ロボットのリンクの三角形メッシュであり、出力はその衝突形状として使う凸包の集合である。理由はアルゴリズムにある。GJK や EPA などの標準的なナローフェーズの衝突判定や距離計算のルーチンは凸形状に対して働き、多くの物理エンジンは、動く物体に凸形状を要求するか、メッシュを黙ってその単一の凸包に置き換える。1 つの凸包で表したマグカップには口も取っ手の穴もないが、分解すればそれらの特徴を複数の凸ピースとして取り戻せる。

多面体の厳密な分解には非常に多くの部品が必要になることがあり、部品数の最小値を求めるのは計算上困難なので、実用的なツールは近似的な凸分解を計算する。各ピースが選んだ許容誤差の範囲で凸になるまで形状を分割する。許容誤差は、ピースとそれ自身の凸包との距離のような凹度の指標で測る。V-HACD は長くシミュレーションのパイプラインで一般的な選択肢であった。CoACD はより新しい衝突を考慮した手法で、メッシュを直接切断し、薄い壁や開口部のような接触にとって重要な特徴を保とうとする。どちらも凹度のしきい値と部品の最大数をパラメータとして備えている。

結果は忠実度とコストのトレードオフになる。ピースが多いほど実際の表面によく沿うが、衝突判定が遅くなり、ピース同士の境目で接触の生成がノイズを含みやすくなる。ピースが少ないと高速だが、グリッパーの指やペグが入り込む必要のある凹部が埋まってしまう。分解は入力メッシュの品質も引き継ぐ。穴、自己交差、非多様体エッジのあるスキャンメッシュは、まず修復が必要なことが多い。凸分解は、符号付き距離場、三角形のバウンディングボリューム階層、球による近似といった衝突表現と関連するが、それらとは別物であり、それらは速度と精度の間で異なるトレードオフをとる。

重要な理由

シミュレーション上の把持、挿入、押し操作のタスクが実物と同じようにふるまうかどうかは、衝突形状に大きく左右される。凸分解は、見た目用のメッシュを、接触の多いタスクが依存する凹形状の特徴を保ったまま、物理エンジンが高速にシミュレーションできる形状に変える一般的な手順である。

主な用途

• 物理シミュレータにおける物体やロボットリンクの衝突メッシュ
• シミュレーションで生成する大規模な把持・マニピュレーションのデータセット
• サンプリングベースのモーションプランナーにおける高速な衝突判定
• 凹形状の特徴を保たなければならない挿入などの接触の多いタスク
• CAD やスキャンのメッシュを URDF や MJCF の衝突形状に変換すること

実際の使われ方

シミュレーションで把持データセットを構築するチームが、スキャンした数千個の家庭用品のメッシュから作業を始める。各メッシュはまず水密になるよう修復してスケールを正規化し、凹度のしきい値と部品数の上限を設定して CoACD にかける。得られた凸ピースは物体の URDF または MJCF ファイルに個別の衝突メッシュとして書き込み、元のメッシュはレンダリング用に残す。把持を生成する前に、チームは物体のサンプルを目で確認する。くぼみが埋まってしまったボウルや、取っ手が本体と一体化してしまった物体には、より厳しいしきい値を適用する。シミュレーション速度にも注意を払う。何十個ものピースに分解される物体は、大規模な並列環境を遅くするからである。

よくある誤解

• 物理エンジンは描画されたとおりのメッシュで衝突を扱う — 多くのエンジンは各衝突メッシュの凸包を使うので、メッシュを分解しない限り凹部は消えてしまう
• 凸ピースが多いほど常によいシミュレーションになる — 余分なピースは衝突判定を遅くし、ピース間の継ぎ目で偽の接触を生むことがある
• 凸分解は厳密である — 実用的なツールは近似的であり、選んだ許容誤差を下回る凹みを埋めるので、小さな穴や狭い隙間がふさがることがある

知っておくべき人

• ロボットや物体のアセットを準備するシミュレーションエンジニア
• シミュレーションでデータセットを構築する把持・マニピュレーションの研究者
• 衝突判定に取り組むモーションプランニングのエンジニア
• CAD モデルを URDF や MJCF ファイルに変換するメイカー

関連技術

• V-HACD
• CoACD
• GJK アルゴリズム（GJK Algorithm）
• 凸包（Convex Hull）
• MuJoCo
• PhysX

関連用語

• Penalty-Based Contact Model
• Signed Distance Field
• Axis-Aligned Bounding Box
• Graph of Convex Sets
• URDF
• Grasp Quality Metric

関連プロジェクト

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
• RLinf: Scalable infrastructure for post-training foundation models via RL
• Webots: Cross-platform robot simulator with built-in models, sensors, and development environment
• NVIDIA Isaac Sim: NVIDIA Omniverse app for AI-driven robot simulation and testing