imported>Aka: https, Links optimiert

2021-05-22T17:45:01Z

https, Links optimiert

Neue Seite

[[Datei:Transfer of a point and its effects on other points in the chainmail algorithm.svg|miniatur|400px|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.]]
[[Datei:Different states of the connections between points for the chainmail algorithm.svg|miniatur|300px|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 Sarah Gibson veröffentlicht.<ref name="gibson">Sarah Gibson: ''3D ChainMail: a Fast Algorithm for Deforming Volumetric Objects''. Mitsubishi Electric Research Lab Cambridge, 1997.</ref> Er kann allerdings nur auf [[Homogenität|homogenen]] Körpern angewandt werden. Aus diesem Grund entwarf Markus Schill 2001 den '''Enhanced Chainmail'''-Algorithmus (kurz: ''ECM''), welcher auch auf inhomogene Körper ausgeführt werden kann.<ref name="schill">Markus Schill: ''Biomechanical Soft Tissue Modeling – Techniques, Implementation and Applications''. Mannheim, Universität, Fakultät für Mathematik und Informatik, 2001, {{DNB|964635690}} (PDF; 24,6 MB)</ref>

Der Chainmail-Algorithmus wurde für die Deformation von [[1D|ein-]], [[2D|zwei-]] und [[3D|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.<ref name="schill" />

== Chainmail ==

Der ursprüngliche Chainmail-Algorithmus wurde erstmals 1997 von Sarah Gibson eingesetzt.<ref name="gibson" /><ref name="draeger">Christopher Dräger. ''A ChainMail Algorithm for Direct Volume Deformation in Virtual Endoscopy Applications''. Diplomarbeit, TU Wien, 2005. ([https://www.cg.tuwien.ac.at/research/publications/2005/draeger-2005-chain/draeger-2005-chain-PDF.pdf PDF])</ref> Sie hat einen schnellen Algorithmus zur Deformation von dreidimensionalen, homogenen Körpern entwickelt.

[[Datei:Allowed distances between two adjacent points in a point cloud for the chainmail algorithm.svg|miniatur|300px|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 (''xmin'' und ''xmax'' sowie ''ymin'' und ''ymax'') 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]], [[Iteration|iterativ]] abgearbeitet:

<syntaxhighlight lang="Java">
// 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);
// Solange es mindestens eine nicht-leere Liste gibt
while (!oben.istLeer() || !unten.istLeer() ||
!rechts.istLeer() || !links.istLeer()) {
liste = gibEineGefuellteListe(oben, unten, rechts, links);
// Solange diese 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);
}
}
}
</syntaxhighlight>

== 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.<ref name="schill" />

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.<ref name="schill" /> 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 (Computergrafik)|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 [[Abklingkonstante]]n versehen, verteilt es selbstständig die potenzielle Energie unter den verschobenen Elementen. Dadurch wird die Deformation gleichmäßiger.<ref name="schill" />

== Einzelnachweise ==

<references />

[[Kategorie:Algorithmus (Computergrafik)]]

Chainmail (Algorithmus) - Versionsgeschichte

imported>Aka: https, Links optimiert