Convex decomposition

• 又稱: approximate convex decomposition, ACD
• 類別: Software & tooling › Simulation & twins
• 標籤: collision-detection, simulation, geometry-processing, meshes, contact

把一個非凸形狀（通常是三角網格）拆成一組凸塊，讓它們的聯集近似原形狀，以便使用快速的凸碰撞演算法。

定義

凸分解（convex decomposition）把一個非凸形狀拆成一組凸部件，這些部件的聯集重現或近似原本的形狀。在機器人領域，輸入通常是物體、夾爪或機器人連桿的三角網格，輸出則是作為其碰撞幾何的一組凸包。原因出在演算法上：標準的窄相碰撞與距離計算程序（例如 GJK 與 EPA）都作用於凸形狀，許多物理引擎若不是要求移動物體使用凸幾何，就是在不提示的情況下把網格換成單一的凸包。以一個凸包表示的馬克杯既沒有開口，也沒有把手的孔；分解則以多個凸塊的形式把這些特徵找回來。

多面體的精確分解可能需要非常多的部件，而求出最少部件數在計算上很困難，因此實用工具計算的是近似凸分解。它們持續拆分形狀，直到每一塊在選定的容許誤差內都是凸的；容許誤差以凹度指標衡量，例如某一塊與它自身凸包之間的距離。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