Convex decomposition

• Aussi appelé: approximate convex decomposition, ACD
• Catégorie: Software & tooling › Simulation & twins
• Mots-clés: collision-detection, simulation, geometry-processing, meshes, contact

Découpage d'une forme non convexe, généralement un maillage triangulaire, en un ensemble de pièces convexes dont l'union l'approche, afin de pouvoir utiliser des algorithmes de collision convexes rapides.

Définition

La décomposition convexe (convex decomposition) découpe une forme non convexe en un ensemble de parties convexes dont l'union reproduit ou approche l'original. En robotique, l'entrée est généralement un maillage triangulaire d'un objet, d'une pince ou d'un segment de robot, et la sortie est un ensemble d'enveloppes convexes utilisées comme géométrie de collision. La raison est algorithmique : les routines standard de collision et de distance en phase fine (narrow phase), comme GJK et EPA, travaillent sur des formes convexes, et de nombreux moteurs physiques exigent une géométrie convexe pour les corps mobiles ou remplacent silencieusement un maillage par son unique enveloppe convexe. Une tasse représentée par une seule enveloppe n'a ni ouverture ni trou d'anse ; une décomposition rétablit ces éléments sous forme de plusieurs pièces convexes.

Une décomposition exacte d'un polyèdre peut nécessiter un très grand nombre de parties, et trouver le nombre minimal est difficile sur le plan calculatoire, si bien que les outils pratiques calculent une décomposition convexe approchée. Ils découpent la forme jusqu'à ce que chaque pièce soit convexe à une tolérance choisie près, mesurée par une métrique de concavité comme la distance entre une pièce et sa propre enveloppe convexe. V-HACD a longtemps été le choix courant dans les chaînes de simulation ; CoACD est une méthode plus récente, sensible aux collisions, qui découpe directement le maillage et cherche à préserver les éléments importants pour le contact, comme les parois minces et les ouvertures. Tous deux exposent des paramètres pour le seuil de concavité et le nombre maximal de parties.

Le résultat est un compromis entre fidélité et coût. Davantage de pièces suivent plus fidèlement la surface réelle mais ralentissent la détection de collision et rendent la génération de contacts plus bruitée là où les pièces se rejoignent ; moins de pièces vont vite mais comblent des régions concaves dans lesquelles un doigt de pince ou une goupille peut avoir besoin d'entrer. Les décompositions héritent aussi de la qualité du maillage d'entrée : les maillages scannés présentant des trous, des auto-intersections ou des arêtes non manifold doivent souvent être réparés d'abord. La décomposition convexe est apparentée, mais distincte, à des représentations de collision comme les champs de distance signée, les hiérarchies de volumes englobants de triangles ou les approximations par sphères, qui font d'autres compromis entre vitesse et précision.

Pourquoi c'est important

Le fait qu'une saisie, une insertion ou une poussée simulée se comporte comme la tâche réelle dépend fortement de la géométrie de collision. La décomposition convexe est l'étape habituelle qui transforme des maillages visuels en une géométrie qu'un moteur physique peut simuler rapidement, tout en conservant les éléments concaves dont dépendent les tâches riches en contacts.

Applications principales

• Maillages de collision pour les objets et les segments de robot dans les simulateurs physiques
• Grands jeux de données de saisie et de manipulation générés en simulation
• Détection de collision rapide dans les planificateurs de mouvement par échantillonnage
• Tâches riches en contacts comme l'insertion, où les éléments concaves doivent être préservés
• Conversion de maillages CAO ou scannés en géométrie de collision URDF ou MJCF

En pratique

Une équipe qui construit un jeu de données de saisie en simulation part de plusieurs milliers de maillages scannés d'objets domestiques. Chaque maillage est d'abord réparé pour être étanche et normalisé en échelle, puis passé dans CoACD avec un seuil de concavité et un plafond sur le nombre de parties. Les pièces convexes obtenues sont écrites comme maillages de collision séparés dans le fichier URDF ou MJCF de l'objet, tandis que le maillage d'origine est conservé pour le rendu. Avant de générer des saisies, l'équipe vérifie visuellement un échantillon d'objets : les bols dont la cavité a été comblée, ou les anses fusionnées avec le corps, reçoivent un seuil plus strict. Elle surveille aussi la vitesse de simulation, car les objets qui se décomposent en plusieurs dizaines de pièces ralentissent les grands environnements parallèles.

Idées reçues

• Un moteur physique calcule les collisions avec le maillage exactement tel qu'il est dessiné — de nombreux moteurs utilisent l'enveloppe convexe de chaque maillage de collision, de sorte que les régions concaves disparaissent si le maillage n'est pas décomposé
• Plus de pièces convexes donnent toujours une meilleure simulation — des pièces supplémentaires ralentissent la détection de collision et peuvent créer des contacts parasites aux jointures entre pièces
• La décomposition convexe est exacte — les outils pratiques sont approchés et comblent les concavités inférieures à la tolérance choisie, ce qui peut fermer de petits trous ou des interstices étroits

Qui devrait le savoir

• Ingénieurs en simulation qui préparent des ressources de robots et d'objets
• Chercheurs en saisie et en manipulation qui construisent des jeux de données en simulation
• Ingénieurs en planification de mouvement travaillant sur la détection de collision
• Makers qui convertissent des modèles CAO en fichiers URDF ou MJCF

Technologies associées

• V-HACD
• CoACD
• Algorithme GJK
• Enveloppe convexe (Convex Hull)
• MuJoCo
• PhysX

Termes associés

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

Projets associés

• 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