Convex decomposition

Detto anche: approximate convex decomposition, ACD
Categoria: Software & tooling › Simulation & twins
Tag: collision-detection, simulation, geometry-processing, meshes, contact

Suddividere una forma non convessa, di solito una mesh triangolare, in un insieme di pezzi convessi la cui unione la approssima, così da poter usare algoritmi di collisione convessi veloci.

Definizione

La scomposizione convessa (convex decomposition) suddivide una forma non convessa in un insieme di parti convesse la cui unione riproduce o approssima l'originale. In robotica l'ingresso è di solito una mesh triangolare di un oggetto, di una pinza o di un link del robot, e l'uscita è un insieme di inviluppi convessi usati come sua geometria di collisione. Il motivo è algoritmico: le routine standard di collisione e distanza in fase stretta, come GJK ed EPA, lavorano su forme convesse, e molti motori fisici o richiedono una geometria convessa per i corpi in movimento o sostituiscono silenziosamente una mesh con il suo unico inviluppo convesso. Una tazza rappresentata da un solo inviluppo non ha né l'apertura né il foro del manico; una scomposizione ripristina queste caratteristiche come più pezzi convessi.

Una scomposizione esatta di un poliedro può richiedere un numero molto grande di parti, e trovare il numero minimo è computazionalmente difficile, per cui gli strumenti pratici calcolano una scomposizione convessa approssimata. Suddividono la forma finché ogni pezzo è convesso entro una tolleranza scelta, misurata con una metrica di concavità come la distanza tra un pezzo e il suo stesso inviluppo convesso. V-HACD è stato a lungo la scelta comune nelle pipeline di simulazione; CoACD è un metodo più recente, attento alle collisioni, che taglia direttamente la mesh e cerca di preservare le caratteristiche che contano per il contatto, come pareti sottili e aperture. Entrambi espongono parametri per la soglia di concavità e il numero massimo di parti.

Il risultato è un compromesso tra fedeltà e costo. Più pezzi seguono più da vicino la superficie reale ma rallentano il controllo delle collisioni e rendono più rumorosa la generazione dei contatti dove i pezzi si incontrano; meno pezzi sono veloci ma riempiono regioni concave in cui potrebbe dover entrare un dito della pinza o un perno. Le scomposizioni ereditano anche la qualità della mesh di ingresso: le mesh scansionate con fori, autointersezioni o spigoli non-manifold spesso vanno prima riparate. La scomposizione convessa è correlata a rappresentazioni di collisione come i campi di distanza con segno, le gerarchie di volumi di contenimento dei triangoli o le approssimazioni con sfere, ma distinta da esse, che fanno compromessi diversi tra velocità e accuratezza.

Perché è importante

Il fatto che una presa, un inserimento o un compito di spinta simulati si comportino come quelli reali dipende fortemente dalla geometria di collisione. La scomposizione convessa è il passo abituale che trasforma le mesh visive in una geometria che un motore fisico può simulare rapidamente, conservando le caratteristiche concave da cui dipendono i compiti ricchi di contatti.

Applicazioni principali

Mesh di collisione per oggetti e link dei robot nei simulatori fisici
Dataset di presa e manipolazione su larga scala generati in simulazione
Controllo rapido delle collisioni nei pianificatori del movimento basati su campionamento
Compiti ricchi di contatti come l'inserimento, in cui le caratteristiche concave devono essere preservate
Conversione di mesh CAD o scansionate in geometria di collisione URDF o MJCF

In pratica

Un gruppo che costruisce un dataset di prese in simulazione parte da diverse migliaia di mesh scansionate di oggetti domestici. Ogni mesh viene prima riparata perché sia chiusa e normalizzata in scala, poi passata a CoACD con una soglia di concavità e un tetto al numero di parti. I pezzi convessi risultanti vengono scritti come mesh di collisione separate nel file URDF o MJCF dell'oggetto, mentre la mesh originale viene conservata per il rendering. Prima di generare le prese, il gruppo controlla visivamente un campione di oggetti: le ciotole le cui cavità sono state riempite, o i manici fusi con il corpo, ricevono una soglia più stretta. Tiene d'occhio anche la velocità di simulazione, poiché gli oggetti che si scompongono in molte decine di pezzi rallentano i grandi ambienti paralleli.

Idee sbagliate comuni

Un motore fisico calcola le collisioni con la mesh esattamente come è disegnata — molti motori usano l'inviluppo convesso di ciascuna mesh di collisione, quindi le regioni concave spariscono a meno che la mesh non venga scomposta
Più pezzi convessi danno sempre una simulazione migliore — i pezzi in più rallentano il controllo delle collisioni e possono creare contatti spuri nelle giunzioni tra i pezzi
La scomposizione convessa è esatta — gli strumenti pratici sono approssimati e riempiono le concavità al di sotto della tolleranza scelta, il che può chiudere piccoli fori o fessure strette

Chi dovrebbe saperlo

Ingegneri di simulazione che preparano gli asset di robot e oggetti
Ricercatori di presa e manipolazione che costruiscono dataset in simulazione
Ingegneri di pianificazione del movimento che lavorano sul controllo delle collisioni
Maker che convertono modelli CAD in file URDF o MJCF

Tecnologie correlate

V-HACD
CoACD
Algoritmo GJK (GJK Algorithm)
Inviluppo convesso (Convex Hull)
MuJoCo
PhysX

Termini correlati

Progetti correlati

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