Chainmail (Algorithmus)

Veranschaulichung des Algorithmus. Eine gleichmäßige Punktwolke wird verkettet dargestellt und einer der Punkte verschoben. Wie bei einer Kette werden die angrenzenden Glieder ab einer bestimmten Distanz mitgezogen.

Die verschiedenen Zustände der Verbindung zwischen Punkten in einer Punktwolke bei dem Chainmail-Algorithmus. Links ist der Ausgangszustand (lockerer Zustand) zu sehen. Die Mitte zeigt die Verbindungen maximal gespannt. Rechts sind die Verbindungen maximal gepresst.

Der Chainmail-Algorithmus (kurz: CM, auch 3D Chainmail) ist ein Verfahren in der Computergrafik, um die Form eines mehrdimensionalen Objekts zu verändern. Er wurde erstmals 1997 von S. Gibson veröffentlicht.^[1] Er kann allerdings nur auf homogenen Körpern angewandt werden. Aus diesem Grund entwarf M. Schill 2001 den Enhanced Chainmail-Algorithmus (kurz: ECM), welcher auch auf inhomogene Körper ausgeführt werden kann.^[2]

Der Chainmail-Algorithmus wurde für die Deformation von ein-, zwei- und dreidimensionalen Körpern entwickelt. Dabei wird das Verhalten einer Kette, bzw. einer mehrdimensionalen Kette (Kettenhemd, daher der Name) zum Vorbild genommen.

Er kann auf jede Punktwolke, die eine gleichmäßige Struktur aufweist, angewandt werden. Somit werden die Quellobjekte in Form von Nachbarschaften von Elementen dargestellt. So hat ein Element einer 1D-Kette bis zu zwei Nachbarn, ein Element einer 2D-Kette bis zu vier Nachbarn und ein Element einer 3D-Kette hat bis zu sechs Nachbarn. Der Chainmail-Algorithmus reagiert auch bei großen Punktmengen sehr schnell, da er wenig Rechenaufwand benötigt. Aus diesem Grund ist er für ein zeitgleiches Rendering von geometrischen Deformationen eine gute Wahl.^[2]

Chainmail

Der ursprüngliche Chainmail-Algorithmus wurde erstmals 1997 von Sarah Gibson eingesetzt.^[1][3] Sie hat einen schnellen Algorithmus zur Deformation von dreidimensionalen, homogenen Körpern entwickelt.

Das Bild zeigt die erlaubte Mindest- und Maximal-Distanz eines Punktes zu seinem Nachbarn.

Zum Beispiel werden bei einem zweidimensionalen Körper jeweils ein horizontaler und ein vertikaler Minimal- und Maximalabstand (x_min und x_max sowie y_min und y_max) zu den vier direkt benachbarten Elementen festgelegt, welche für alle „Kettenglieder“ gelten. Außerdem wird für jede der vier möglichen Richtungen (links, rechts, oben, unten) eine leere Liste angelegt. Wird nun ein Element verschoben, wird dessen Position gespeichert und die vier Nachbarn zur jeweiligen Liste hinzugefügt. Nun werden die Listen, wie im folgenden Pseudocode, iterativ abgearbeitet:

// Element x wurde verschoben
verschiebe(x);
// Alle 4 Nachbarn zur jeweiligen Liste hinzufügen
gibOberenNachbar(x).hinzufuegenZurListe(oben);
gibUnterenNachbar(x).hinzufuegenZurListe(unten);
gibRechtenNachbar(x).hinzufuegenZurListe(rechts);
gibLinkenNachbar(x).hinzufuegenZurListe(links);
// Für jede nicht-leere Liste
while (!oben.istLeer() && !unten.istLeer() &&
       !rechts.istLeer() && !links.istLeer()) {
  liste = gibEineGefuellteListe(oben, unten, rechts, links);
  // Solange Liste nicht leer ist
  while (!liste.istLeer()) {
    Element e = liste.gibNaechstes();
    if (e.verletztGrenzen()) {
      if (liste != oben)
        gibUnterenNachbar(x).hinzufuegenZurListe(unten);
      if (liste != unten)
        gibOberenNachbar(x).hinzufuegenZurListe(oben);
      if (liste != rechts)
        gibLinkenNachbar(x).hinzufuegenZurListe(links);
      if (liste != links)
        gibRechtenNachbar(x).hinzufuegenZurListe(rechts);
      // Aktuelles Element verschieben
      verschiebe(e);
      // Lösche aktuelles Element aus aktueller Liste
      liste.loesche(e);
    }
  }
}

Enhanced Chainmail

Für die Darstellung von Körpern in der Biomechanik wird vorausgesetzt, dass auch mit inhomogenen Daten gearbeitet werden kann. Dies unterstützt die Weiterentwicklung des Chainmail-Algorithmus – der Enhanced Chainmail-Algorithmus. Er wurde im Jahre 2001 von M. Schill veröffentlicht.^[2]

Hier wird nicht mehr für jede Richtung eine Liste angelegt, sondern nur noch eine Liste, in welcher alle zu verschiebenden Elemente eingetragen werden. Die Elemente werden absteigend nach Grad der Verschiebung sortiert. Sie erhalten den bereits korrigierten Verursacher als zusätzliche Informationen. Es wird immer das Element, das an der Spitze der Liste steht (also die Grenzen am stärksten verletzt) zu seinem Verursacher hin korrigiert. Nach jeder Korrektur muss die Liste aktualisiert werden.

Das regelmäßige Aktualisieren der Liste macht den Algorithmus komplexer als seinen Vorgänger.^[2] Somit sollte bei homogenen Objekten der ursprüngliche Chainmail-Algorithmus verwendet werden.

Elastische Entspannung

Der Chainmail-Algorithmus deformiert einen Körper verhältnismäßig schnell. Er basiert nur auf geometrischen Beziehungen zwischen benachbarten Elementen. Dabei ist allerdings nicht gesagt, dass die Elemente gleichmäßig verschoben werden. Bei einer Abbildung der Elemente auf ein Masse-Feder-System kann man dies damit beschreiben, dass die potenzielle Energie ungleichmäßig über die verschobenen Elemente verteilt ist. Wird dieses Masse-Feder-System mit hohen Abklingkonstanten versehen, verteilt es selbstständig die potenzielle Energie unter den verschobenen Elementen. Dadurch wird die Deformation gleichmäßiger.^[2]

Einzelnachweise

1. ↑ ^{a b} Sarah Gibson. 3D ChainMail: a Fast Algorithm for Deforming Volumetric Objects. Mitsubishi Electric Research Lab Cambridge, 1997. (PDF)
2. ↑ ^{a b c d e} Markus Schill. Biomechanical Soft Tissue Modeling - Techniques, Implementation and Applications. Mannheim, Universität, Fakultät für Mathematik und Informatik, 2001. (PDF, 24,6 MB)
3. ↑ Christopher Dräger. A ChainMail Algorithm for Direct Volume Deformation in Virtual Endoscopy Applications. Diplomarbeit, TU Wien, 2005. (PDF)