Convex decomposition

Auch genannt: approximate convex decomposition, ACD
Kategorie: Software & tooling › Simulation & twins
Schlagwörter: collision-detection, simulation, geometry-processing, meshes, contact

Zerlegen einer nicht konvexen Form, meist eines Dreiecksnetzes, in eine Menge konvexer Teile, deren Vereinigung sie annähert, damit schnelle konvexe Kollisionsalgorithmen verwendet werden können.

Definition

Konvexe Zerlegung (convex decomposition) zerlegt eine nicht konvexe Form in eine Sammlung konvexer Teile, deren Vereinigung das Original wiedergibt oder annähert. In der Robotik ist die Eingabe meist ein Dreiecksnetz eines Objekts, eines Greifers oder eines Roboterglieds, und die Ausgabe ist eine Menge konvexer Hüllen, die als dessen Kollisionsgeometrie dienen. Der Grund ist algorithmisch: Die üblichen Routinen für Kollision und Abstand in der Narrow Phase, etwa GJK und EPA, arbeiten mit konvexen Formen, und viele Physik-Engines verlangen entweder konvexe Geometrie für bewegte Körper oder ersetzen ein Netz stillschweigend durch seine einzige konvexe Hülle. Ein durch eine einzige Hülle dargestellter Becher hat weder Öffnung noch Henkelloch; eine Zerlegung stellt diese Merkmale als mehrere konvexe Teile wieder her.

Eine exakte Zerlegung eines Polyeders kann sehr viele Teile erfordern, und die minimale Anzahl zu finden ist rechnerisch schwer, daher berechnen praktische Werkzeuge eine approximative konvexe Zerlegung. Sie teilen die Form, bis jedes Teil innerhalb einer gewählten Toleranz konvex ist, gemessen mit einem Konkavitätsmaß wie dem Abstand zwischen einem Teil und seiner eigenen konvexen Hülle. V-HACD war lange die übliche Wahl in Simulationspipelines; CoACD ist ein neueres kollisionsbewusstes Verfahren, das das Netz direkt schneidet und versucht, Merkmale zu erhalten, die für den Kontakt wichtig sind, etwa dünne Wände und Öffnungen. Beide bieten Parameter für die Konkavitätsschwelle und die maximale Anzahl an Teilen.

Das Ergebnis ist ein Kompromiss zwischen Genauigkeit und Aufwand. Mehr Teile folgen der wahren Oberfläche enger, verlangsamen aber die Kollisionsprüfung und machen die Kontakterzeugung dort, wo Teile aufeinandertreffen, verrauschter; weniger Teile sind schnell, füllen aber konkave Bereiche auf, in die ein Greiferfinger oder ein Stift eindringen muss. Zerlegungen übernehmen außerdem die Qualität des Eingabenetzes: Gescannte Netze mit Löchern, Selbstdurchdringungen oder nicht mannigfaltigen Kanten müssen oft zuerst repariert werden. Konvexe Zerlegung ist verwandt mit, aber verschieden von Kollisionsdarstellungen wie vorzeichenbehafteten Distanzfeldern, Hüllkörperhierarchien von Dreiecken oder Kugelnäherungen, die andere Kompromisse zwischen Geschwindigkeit und Genauigkeit eingehen.

Warum es wichtig ist

Ob sich ein simulierter Griff, eine Einfüge- oder eine Schiebeaufgabe wie die reale verhält, hängt stark von der Kollisionsgeometrie ab. Konvexe Zerlegung ist der übliche Schritt, der visuelle Netze in Geometrie verwandelt, die eine Physik-Engine schnell simulieren kann, und dabei die konkaven Merkmale bewahrt, von denen kontaktreiche Aufgaben abhängen.

Wichtige Anwendungen

Kollisionsnetze für Objekte und Roboterglieder in Physiksimulatoren
In der Simulation erzeugte große Greif- und Manipulationsdatensätze
Schnelle Kollisionsprüfung in stichprobenbasierten Bewegungsplanern
Kontaktreiche Aufgaben wie das Einfügen, bei denen konkave Merkmale erhalten bleiben müssen
Umwandlung von CAD- oder gescannten Netzen in URDF- oder MJCF-Kollisionsgeometrie

In der Praxis

Ein Team, das in der Simulation einen Griffdatensatz erstellt, geht von mehreren tausend gescannten Netzen von Haushaltsobjekten aus. Jedes Netz wird zuerst wasserdicht repariert und in der Größe normiert und dann mit einer Konkavitätsschwelle und einer Obergrenze für die Anzahl der Teile durch CoACD geschickt. Die resultierenden konvexen Teile werden als separate Kollisionsnetze in die URDF- oder MJCF-Datei des Objekts geschrieben, während das ursprüngliche Netz für das Rendering erhalten bleibt. Vor dem Erzeugen von Griffen prüft das Team eine Stichprobe von Objekten visuell: Schalen, deren Hohlräume aufgefüllt wurden, oder Henkel, die mit dem Körper verschmolzen sind, erhalten eine strengere Schwelle. Es beobachtet außerdem die Simulationsgeschwindigkeit, da Objekte, die in viele Dutzend Teile zerfallen, große parallele Umgebungen verlangsamen.

Häufige Missverständnisse

Eine Physik-Engine berechnet Kollisionen mit dem Netz genau so, wie es gezeichnet ist — viele Engines verwenden die konvexe Hülle jedes Kollisionsnetzes, sodass konkave Bereiche verschwinden, wenn das Netz nicht zerlegt wird
Mehr konvexe Teile ergeben immer eine bessere Simulation — zusätzliche Teile verlangsamen die Kollisionsprüfung und können an den Nähten zwischen den Teilen Scheinkontakte erzeugen
Konvexe Zerlegung ist exakt — praktische Werkzeuge sind approximativ und füllen Konkavitäten unterhalb der gewählten Toleranz auf, was kleine Löcher oder schmale Spalte schließen kann

Wer das wissen sollte

Simulationsingenieure, die Roboter- und Objekt-Assets vorbereiten
Forschende in Greifen und Manipulation, die Datensätze in der Simulation erstellen
Ingenieure für Bewegungsplanung, die an Kollisionsprüfung arbeiten
Maker, die CAD-Modelle in URDF- oder MJCF-Dateien umwandeln

Open Source Robotics