Convex decomposition

También llamado: approximate convex decomposition, ACD
Categoría: Software & tooling › Simulation & twins
Etiquetas: collision-detection, simulation, geometry-processing, meshes, contact

Dividir una forma no convexa, normalmente una malla de triángulos, en un conjunto de piezas convexas cuya unión la aproxima, para poder usar algoritmos de colisión convexos rápidos.

Definición

La descomposición convexa (convex decomposition) divide una forma no convexa en un conjunto de partes convexas cuya unión reproduce o aproxima la original. En robótica, la entrada suele ser una malla de triángulos de un objeto, de una pinza o de un eslabón de robot, y la salida es un conjunto de envolventes convexas que se usan como su geometría de colisión. La razón es algorítmica: las rutinas estándar de colisión y distancia de fase estrecha, como GJK y EPA, trabajan con formas convexas, y muchos motores de física o bien exigen geometría convexa para los cuerpos móviles o bien sustituyen sin avisar una malla por su única envolvente convexa. Una taza representada por una sola envolvente no tiene abertura ni hueco en el asa; una descomposición recupera esos rasgos como varias piezas convexas.

Una descomposición exacta de un poliedro puede necesitar un número muy grande de partes, y encontrar el número mínimo es computacionalmente difícil, por lo que las herramientas prácticas calculan una descomposición convexa aproximada. Dividen la forma hasta que cada pieza es convexa dentro de una tolerancia elegida, medida con una métrica de concavidad como la distancia entre una pieza y su propia envolvente convexa. V-HACD ha sido durante mucho tiempo la opción habitual en las cadenas de simulación; CoACD es un método más reciente, consciente de las colisiones, que corta la malla directamente e intenta conservar los rasgos que importan para el contacto, como las paredes finas y las aberturas. Ambos exponen parámetros para el umbral de concavidad y el número máximo de partes.

El resultado es un compromiso entre fidelidad y coste. Más piezas siguen más de cerca la superficie real, pero ralentizan la comprobación de colisiones y hacen más ruidosa la generación de contactos donde se unen las piezas; menos piezas son rápidas, pero rellenan regiones cóncavas en las que quizá tenga que entrar un dedo de la pinza o una clavija. Las descomposiciones también heredan la calidad de la malla de entrada: las mallas escaneadas con agujeros, autointersecciones o aristas no variedad a menudo necesitan reparación previa. La descomposición convexa está relacionada con representaciones de colisión como los campos de distancia con signo, las jerarquías de volúmenes envolventes de triángulos o las aproximaciones por esferas, pero es distinta de ellas, que hacen compromisos distintos entre velocidad y precisión.

Por qué importa

Que un agarre, una inserción o una tarea de empuje simulados se comporten como los reales depende en gran medida de la geometría de colisión. La descomposición convexa es el paso habitual que convierte las mallas visuales en geometría que un motor de física puede simular rápidamente, conservando los rasgos cóncavos de los que dependen las tareas con mucho contacto.

Aplicaciones clave

Mallas de colisión para objetos y eslabones de robot en simuladores físicos
Conjuntos de datos de agarre y manipulación a gran escala generados en simulación
Comprobación rápida de colisiones en planificadores de movimiento basados en muestreo
Tareas con mucho contacto, como la inserción, en las que deben conservarse los rasgos cóncavos
Conversión de mallas CAD o escaneadas en geometría de colisión URDF o MJCF

En la práctica

Un equipo que construye un conjunto de datos de agarres en simulación parte de varios miles de mallas escaneadas de objetos domésticos. Primero se repara cada malla para que sea estanca y se normaliza su escala, y después se pasa por CoACD con un umbral de concavidad y un límite en el número de partes. Las piezas convexas resultantes se escriben como mallas de colisión independientes en el archivo URDF o MJCF del objeto, mientras que la malla original se conserva para el renderizado. Antes de generar agarres, el equipo comprueba visualmente una muestra de objetos: los cuencos cuyas cavidades se rellenaron, o las asas fusionadas con el cuerpo, reciben un umbral más estricto. También vigila la velocidad de simulación, ya que los objetos que se descomponen en muchas decenas de piezas ralentizan los grandes entornos paralelos.

Ideas erróneas comunes

Un motor de física calcula las colisiones con la malla exactamente como se dibuja — muchos motores usan la envolvente convexa de cada malla de colisión, de modo que las regiones cóncavas desaparecen a menos que la malla se descomponga
Más piezas convexas siempre dan una simulación mejor — las piezas adicionales ralentizan la comprobación de colisiones y pueden crear contactos espurios en las uniones entre piezas
La descomposición convexa es exacta — las herramientas prácticas son aproximadas y rellenan las concavidades por debajo de la tolerancia elegida, lo que puede cerrar agujeros pequeños o huecos estrechos

Quién debería saberlo

Ingenieros de simulación que preparan recursos de robots y objetos
Investigadores en agarre y manipulación que construyen conjuntos de datos en simulación
Ingenieros de planificación de movimiento que trabajan en la comprobación de colisiones
Makers que convierten modelos CAD en archivos URDF o MJCF

Tecnologías relacionadas

V-HACD
CoACD
Algoritmo GJK (GJK Algorithm)
Envolvente convexa (Convex Hull)
MuJoCo
PhysX

Términos relacionados

Proyectos 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