© Nuthawut Somsuk, 123RF

Ob ein räumlich naher Punkt, eine ähnliche Farbe oder ein passender Vorschlag für eine Partnerin: Der Octree-Algorithmus hilft, schnell die nächsten Objekte unter Millionen anderer zu finden.

Oft ist es nötig, effizient ein benachbartes Objekte unter Hunderten oder gar Millionen anderer zu finden, etwa räumlich nahe Punkte, Pixel ähnlicher Farbe oder Personen aus einer Datenbank mit Tausenden von Einträgen. Beim Programmieren fallen dabei immer zwei Aufgaben an: die Berechnung des Abstands zweier Objekte und die effiziente Suche nach nahegelegenen Objekten. Die Berechnung des Abstands zweier Objekte hängt immer von der betrachteten Domäne ab und ist spätestens bei der Partnersuche eine Kunst für sich.

Für die Suche hingegen gibt es Lösungen, die unabhängig von der Domäne funktionieren. Am einfachsten klappt das mit Objekten, die durch einen einzigen Kennwert gekennzeichnet werden, wie etwa den Preis. Hier fügt man alle Objekte in eine Liste ein, sortiert sie entsprechend des Kennwerts und findet die Nachbarn sofort über deren Index. Was aber, wenn die Objekte zwei, drei oder mehr Parameter haben? Das stumpfe Berechnen aller Abstände verursacht bei großen Objektmengen so viel Aufwand, dass es keine realistische Lösung darstellt. Insgesamt wären (n*(n-1))/2) Abstände zu berechnen; schon bei knapp 1500 Objekten fielen also rund eine Million Operationen an.

Als Lösung für dieses Problem schlug Donald Meagher 1980 die Octrees vor. Diese Kombination aus Datenstruktur und Algorithmus sortiert Objekte für eine effiziente Suche benachbarter Objekte vor. Das funktioniert gleichermaßen für 2 wie für 100 Kennwerte; wir erläutern es im Folgenden anhand von drei Kennwerten wie Position (X,Y,Z) oder Farbe (R,G,B).

Blockweise

In Listing 1 enthält die Klasse »OctreeCell« das Kernstück der Octrees. Sie beschreibt mithilfe der beiden Eckpunkte »min« und »max« ein quaderförmiges Volumen. Da der Mittelpunkt »center« später noch öfter benötigt wird, berechnet man ihn sinnigerweise gleich im Konstruktor. Neben der geometrischen Beschreibung enthält »OctreeCell« die zu suchenden Objekte in »content« (hier »Point3d«) oder den Kinderzellen »children«. Einige wenige Verwaltungsinformationen vervollständigen die Information, wie die Tiefe im Baum und der Index.

class OctreeCell {
  private final Point3d min;
  private final Point3d max;
  private final Point3d center;
  private Set<Point3d> content;
  private OctreeCell[] children;
  private final int octantNo;
  private final int level;
  private OctreeCell(int level, int oct, Point3d min, Point3d max) {
    this.level = level;
    ...
    this.center = new Point3d((min.x + max.x) / 2.0,
      (min.y + max.y) / 2.0,
      (min.z + max.z) / 2.0);
  }

Zum Start geht der Algorithmus von einer Stammzelle aus. Sie wird so groß dimensioniert, dass ihr Volumen alle zu untersuchenden Objekte enthält. Der Stammzelle fügt man dann die Objekte hinzu, und der eigentliche Algorithmus läuft ab. Dabei unterscheidet die Methode »insert« (Listing 2) drei Fälle: das Weiterreichen an die Kinderzelle, das finale Aufsammeln der Objekte sowie das Erstellen von Kinderzellen und deren Weiterreichen.

private void insert(Point3d point) {
  if (children == null && content == null) {
    if (needSplitting()) {
      children = splitCell();
    } else {
      content = new HashSet<>();
    }
  }
  if (content != null) {
    content.add(point);
  } else {
    int childOctantNo = indexFor(point);
    children[childOctantNo].insert(point);
  }
}
private boolean needSplitting() {
  double l = max.x - min.x;
  double w = max.y - min.y;
  double h = max.z - min.z;
  double e = Math.max(l, Math.max(w, h));
  return e > MAX_EDGE_LENGTH && level < MAX_DEPTH;
}
private OctreeCell[] splitCell() {
  OctreeCell[] retval = new OctreeCell[8];
  retval[0] = new OctreeCell(level + 1, 0, min, center);
  retval[1] = new OctreeCell(level + 1, 1,
     new Point3d(center.x, min.y, min.z),
     new Point3d(max.x, center.y, center.z));
  // gleiches Vorgehen in anderen Oktanten
  [...]
}
private int indexFor(Point3d point) {
  Vector3d dir = new Vector3d();
  dir.sub(point, center);
  if (dir.x >= 0 && dir.y >= 0 && dir.z >= 0) {
    return 6;
  } else if (dir.x >= 0 && dir.y >= 0 && dir.z < 0) {
    return 2;
  } else if  // gleiches Vorgehen in anderen Oktanten
}

Beim ersten Hinzufügen wird geprüft, ob die Zelle weiter unterteilt werden muss, oder ob sie die Objekte selbst aufsammelt. Als Kriterium dienen in der Regel die Größe und Tiefe der Zelle; zu große Zellen erhalten durch die Methode »splitCell« Kinderzellen. Diese halbieren das Volumen der Elternzelle jeweils in allen Dimensionen (Abbildung 1). Bei drei Dimensionen sind das 2³ gleich acht Kinder (Octree), bei zwei Dimensionen vier Kinder (Quadtree). Aus der Verknüpfung der Zellen mit ihren Kinderzellen ergibt sich eine baumähnliche Datenstruktur, der Octree.

Abbildung 1: Octree-Zellen teilen den Raum rekursiv auf und bilden eine Baumstruktur.

Ist das erledigt, werden die Objekte entweder im Set »content« aufgesammelt oder an die passende Kinderzelle weitergereicht. Dazu berechnet die Methode »indexFor« einen Vektor vom Mittelpunkt zu dem Objekt und ermittelt dann anhand der Vorzeichen die passende Kinderzelle (Abbildung 2). Dies ist gleichermaßen robust wie schnell, da zum Beispiel keine trigonometrischen Berechnungen anfallen. In den Kinderzellen läuft rekursiv wieder derselbe Algorithmus ab, bis schließlich eine Blattzelle die Objekte aufsammelt.

Abbildung 2: Für die Zellenzuordnung genügt das Vorzeichen des Differenzvektors zum Zellenmittelpunkt.

Nach dem kompletten Durchlauf dieses Algorithmus sind alle Objekte den Blattzellen des Baums zugeordnet. Für die Abbildung 3 wurde dies einmal für die Scan-Punkte des Stanford-Bunnys [1] vorgenommen und rechts nur die Zellen gezeichnet, die Punkte enthalten. Wie man sieht, unterteilt das Verfahren je nach Punkteverteilung nicht das ganze Volumen der Stammzelle bis hinunter zu den Blättern: In Bereichen ohne Objekte endet der Baum bei Zellen ohne Kinder oder Objekte.

Abbildung 3: Mit Octrees lassen sich schnell die Punkte eines 3D-Scans indizieren.

Jetzt lässt sich der Octree nutzen, um Objekte in der Nähe einer gegebenen X/Y/Z-Position zu finden, indem man, wie beim Hinzufügen auf Basis der Methode »indexFor«, die passende Zelle im Baum sucht. Entweder endet die Suche an einem leeren Knoten oder bei einem Blattknoten mit Objekten. Diese Objekte finden sich auf alle Fälle in der Nähe des untersuchten Punkts. Soll alles in einem bestimmten Abstand um einen Punkt herum gesucht werden, können die Objekte je nach Größe des Abstands und der Zelle auch in einer Nachbarzelle liegen. In diesem Fall berechnet man die acht Eckpunkte eines Kastens mit dem Abstand als Kastenlänge und sucht dann die Ergebnisse aus den dazugehörenden Blattknoten.

An dieser Stelle zeigt sich ein kleines Problem mit dem Octree. Alle Betrachtungen basieren auf den kastenförmigen Volumina, also linear auf den kartesischen Koordinaten der Hauptachsen. Der euklidische Abstand definiert aber eine Kugel, die Kästen liefern naturgemäß nur eine schlechte Näherung. Gegebenenfalls gilt es also, die schnell per Octree erhaltenen Objekte noch genauer zu filtern, um die Ergebnismenge zu erhalten. Diese Berechnung findet dann aber nur noch mit einem Bruchteil der Objekte statt.

Gut geteilt

Octrees haben sich als Suchbeschleuniger für Probleme mit zwei oder mehr Dimensionen bewährt. Mit ihnen lassen sich, unabhängig von der Domäne, benachbarte Objekte effizient finden. Viele 2D-Grafikbibliotheken nutzen Octree zum Beispiel beim Schreiben von Bildern. Füllt man den Baum mit den RGB-Werten eines Bilds, lassen sich schnell die genutzten Bereiche des gesamten Farbraums ermitteln. Verlustbehaftete Dateiformate wie GIF benötigen das, um die auf die Eingabedaten angepasste, reduzierte Farbpalette für ein Bild zu berechnen. In 3D-Bibliotheken kommt der Octree für die Kollisionsuntersuchung zum Einsatz, Gaming-Engines berechnen mit ihm die Geschossbahn gegen Monster und so weiter.

Daher bringen die meisten Visualisierungsbibliotheken, Gaming-Engines oder CAD-Kernel eine Octree-Implementierung mit. Eine ausgereifte Octree-Bibliothek lässt sich für jede Sprache finden, allein auf Github gibt es über 750 Implementationen in den verschiedensten Sprachen. Die für diesen Artikel geschriebene einfache Octree-Variante finden Sie im Download-Bereich zu diesem Artikel [2]. (jcb/jlu)