Chainmail (algorithm)

Illustration of the algorithm. A uniform point cloud is shown chained and one of the points is shifted. As with a chain, the adjacent links are pulled along from a certain distance.

The different states of the connection between points in a point cloud in the Chainmail algorithm. The initial state (loose state) can be seen on the left. The middle shows the connections as stretched as possible. On the right the connections are maximally pressed.

The Chain Mail - algorithm (abbreviated CM , even 3D Chain Mail ) is a process in the computer graphics , the shape change of a multidimensional object. It was first published in 1997 by Sarah Gibson. However, it can only be used on homogeneous bodies. For this reason, Markus Schill designed the Enhanced Chainmail algorithm ( ECM for short ) in 2001 , which can also be executed on inhomogeneous bodies.

The Chainmail algorithm was developed for the deformation of one- , two- and three-dimensional bodies. The behavior of a chain or a multidimensional chain ( chain mail , hence the name) is taken as a model.

It can be applied to any point cloud that has a uniform structure. The source objects are thus represented in the form of neighborhoods of elements. An element of a 1D chain has up to two neighbors, an element of a 2D chain has up to four neighbors and an element of a 3D chain has up to six neighbors. The chainmail algorithm reacts very quickly, even with large amounts of points, as it requires little computing effort. For this reason, it is a good choice for simultaneous rendering of geometric deformations.

Chainmail

The original Chainmail algorithm was first used by Sarah Gibson in 1997. She developed a fast algorithm for the deformation of three-dimensional, homogeneous bodies.

The picture shows the allowed minimum and maximum distance of a point to its neighbor.

For example, for a two-dimensional body, a horizontal and a vertical minimum and maximum distance ( x _min and x _max as well as y _min and y _max ) to the four directly adjacent elements are defined, which apply to all "chain links". In addition, an empty list is created for each of the four possible directions (left, right, up, down). If an element is now moved, its position is saved and the four neighbors are added to the respective list. Now the records are, as in the following pseudo code , iteratively processed:

// 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);
    }
  }
}

Enhanced chainmail

For the representation of bodies in biomechanics it is assumed that it is possible to work with inhomogeneous data. This supports the further development of the chainmail algorithm - the enhanced chainmail algorithm. It was published in 2001 by M. Schill.

A list is no longer created here for each direction, but only a list in which all elements to be moved are entered. The elements are sorted in descending order according to the degree of displacement. You will receive the already corrected polluter as additional information. The element that is at the top of the list (i.e. the limits that are most severely violated) is always corrected towards its originator. The list must be updated after each correction.

Regularly updating the list makes the algorithm more complex than its predecessor. The original chainmail algorithm should therefore be used for homogeneous objects.

Elastic relaxation

The chainmail algorithm deforms a body relatively quickly. It is based only on geometric relationships between neighboring elements. However, this does not mean that the elements are shifted evenly. If the elements are mapped onto a mass-spring system , this can be described by the fact that the potential energy is unevenly distributed over the displaced elements. If this mass-spring system is provided with high decay constants , it automatically distributes the potential energy among the displaced elements. This makes the deformation more even.

Individual evidence

^ ^A ^b Sarah Gibson: 3D ChainMail: a Fast Algorithm for Deforming Volumetric Objects . Mitsubishi Electric Research Lab Cambridge, 1997.
↑ ^a ^b ^c ^d ^e Markus Schill: Biomechanical Soft Tissue Modeling - Techniques, Implementation and Applications . Mannheim, University, Faculty of Mathematics and Computer Science, 2001, DNB 964635690 (PDF; 24.6 MB)
↑ Christopher Dräger. A ChainMail Algorithm for Direct Volume Deformation in Virtual Endoscopy Applications . Diploma thesis, Vienna University of Technology, 2005. ( PDF )

[gibson-1] A ^b Sarah Gibson: 3D ChainMail: a Fast Algorithm for Deforming Volumetric Objects . Mitsubishi Electric Research Lab Cambridge, 1997.

[schill-2] Markus Schill: Biomechanical Soft Tissue Modeling - Techniques, Implementation and Applications . Mannheim, University, Faculty of Mathematics and Computer Science, 2001, DNB 964635690 (PDF; 24.6 MB)

[draeger-3] Christopher Dräger. A ChainMail Algorithm for Direct Volume Deformation in Virtual Endoscopy Applications . Diploma thesis, Vienna University of Technology, 2005. ( PDF )