Convex decomposition

• Também chamado: approximate convex decomposition, ACD
• Categoria: Software & tooling › Simulation & twins
• Tags: collision-detection, simulation, geometry-processing, meshes, contact

Dividir uma forma não convexa, geralmente uma malha de triângulos, em um conjunto de peças convexas cuja união a aproxima, para que algoritmos de colisão convexos rápidos possam ser usados.

Definição

A decomposição convexa (convex decomposition) divide uma forma não convexa em um conjunto de partes convexas cuja união reproduz ou aproxima a original. Em robótica, a entrada costuma ser uma malha de triângulos de um objeto, de uma garra ou de um elo de robô, e a saída é um conjunto de envoltórias convexas usadas como sua geometria de colisão. O motivo é algorítmico: as rotinas padrão de colisão e distância de fase estreita, como GJK e EPA, trabalham com formas convexas, e muitos motores de física ou exigem geometria convexa para corpos móveis ou substituem silenciosamente uma malha por sua única envoltória convexa. Uma caneca representada por uma única envoltória não tem abertura nem o furo da alça; uma decomposição restaura essas características como várias peças convexas.

Uma decomposição exata de um poliedro pode exigir um número muito grande de partes, e encontrar o número mínimo é computacionalmente difícil, por isso as ferramentas práticas calculam uma decomposição convexa aproximada. Elas dividem a forma até que cada peça seja convexa dentro de uma tolerância escolhida, medida por uma métrica de concavidade, como a distância entre uma peça e sua própria envoltória convexa. O V-HACD foi por muito tempo a escolha comum nos pipelines de simulação; o CoACD é um método mais recente, que leva em conta as colisões, corta a malha diretamente e tenta preservar características que importam para o contato, como paredes finas e aberturas. Ambos expõem parâmetros para o limiar de concavidade e o número máximo de partes.

O resultado é um compromisso entre fidelidade e custo. Mais peças seguem mais de perto a superfície real, mas tornam a verificação de colisões mais lenta e a geração de contatos mais ruidosa onde as peças se encontram; menos peças são rápidas, mas preenchem regiões côncavas nas quais um dedo da garra ou um pino talvez precise entrar. As decomposições também herdam a qualidade da malha de entrada: malhas escaneadas com furos, autointerseções ou arestas não variedade muitas vezes precisam ser reparadas antes. A decomposição convexa é relacionada a representações de colisão como campos de distância com sinal, hierarquias de volumes envolventes de triângulos ou aproximações por esferas, mas distinta delas, que fazem compromissos diferentes entre velocidade e precisão.

Por que importa

Se uma preensão, uma inserção ou uma tarefa de empurrar simulada se comporta como a real depende muito da geometria de colisão. A decomposição convexa é o passo usual que transforma malhas visuais em geometria que um motor de física consegue simular rapidamente, mantendo as características côncavas das quais dependem as tarefas ricas em contato.

Principais aplicações

• Malhas de colisão para objetos e elos de robô em simuladores de física
• Conjuntos de dados de preensão e manipulação em grande escala gerados em simulação
• Verificação rápida de colisões em planejadores de movimento baseados em amostragem
• Tarefas ricas em contato, como inserção, em que as características côncavas precisam ser preservadas
• Conversão de malhas CAD ou escaneadas em geometria de colisão URDF ou MJCF

Na prática

Uma equipe que constrói um conjunto de dados de preensão em simulação parte de vários milhares de malhas escaneadas de objetos domésticos. Cada malha é primeiro reparada para ficar estanque e normalizada em escala, e depois passa pelo CoACD com um limiar de concavidade e um teto para o número de partes. As peças convexas resultantes são gravadas como malhas de colisão separadas no arquivo URDF ou MJCF do objeto, enquanto a malha original é mantida para a renderização. Antes de gerar preensões, a equipe verifica visualmente uma amostra de objetos: tigelas cujas cavidades foram preenchidas, ou alças fundidas ao corpo, recebem um limiar mais rigoroso. Ela também acompanha a velocidade da simulação, já que objetos que se decompõem em muitas dezenas de peças deixam mais lentos os grandes ambientes paralelos.

Equívocos comuns

• Um motor de física calcula colisões com a malha exatamente como ela é desenhada — muitos motores usam a envoltória convexa de cada malha de colisão, então as regiões côncavas desaparecem a menos que a malha seja decomposta
• Mais peças convexas sempre dão uma simulação melhor — peças extras tornam a verificação de colisões mais lenta e podem criar contatos espúrios nas emendas entre as peças
• A decomposição convexa é exata — as ferramentas práticas são aproximadas e preenchem concavidades abaixo da tolerância escolhida, o que pode fechar pequenos furos ou frestas estreitas

Quem deve saber

• Engenheiros de simulação que preparam assets de robôs e objetos
• Pesquisadores de preensão e manipulação que constroem conjuntos de dados em simulação
• Engenheiros de planejamento de movimento que trabalham com verificação de colisões
• Makers que convertem modelos CAD em arquivos URDF ou MJCF

Tecnologias relacionadas

• V-HACD
• CoACD
• Algoritmo GJK (GJK Algorithm)
• Envoltória convexa (Convex Hull)
• MuJoCo
• PhysX

Termos relacionados

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

Projetos relacionados

• 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