Datenstruktur: Half Edge

In der Spieleentwicklung gibt es eine Menge Dinge, die man wissen kann und sollte. Sehr wichtig sind dabei immer die Grundlagen, vor allem Datenstrukturen. Oft hat man es in der Spieleentwicklung damit zu tun, daß man Datenmengen möglichst optimal bearbeiten muss oder vereinfachen muss und um nicht jedesmal das Rad neu erfinden zu müssen, ist es sehr hilfreich, wenn man sich ein wenig auskennt.

Eine sehr interessante und auch sehr hilfreiche Datenstruktur ist die Half-Edge Struktur, die zur Beschreibung von geometrischen Zusammenhängen im zwei- und dreidimensionalen Raum verwendet werden kann.

In diesem ersten Artikel möchte ich die Grundlagen dieser Datenstruktur erklären und diese dann in weiteren Teilen aufgreifen und weiter verfeinern.

Ein üblicher Weg ein Polygon Mesh bzw. Polygonnetz abzubilden ist eine Liste von Vertices und eine Liste von Referenzen auf diese Vertices, die Flächen bzw. Dreiecke bilden. Diese Abbildung ist sehr handlich und auch absolut gängig. Diese wird z.B. von den meisten Grafik-APIs (DirectX, OpenGL etc.) in Form von Vertex- und Index-Buffern verwendet. Diese Anordnung der Daten mag zwar für einige Anwendungsfälle sehr gut geeignet sein, aber eben nicht für alle.

Ein Beispiel ist die Vereinfachung eines Mesh. Oft müssen hier Kanten zu einem einzelnen Vertex zusammengefasst werden. Dies führt dazu, daß die angrenzenden Flächen entfernt und neu aufgebaut werden müssen. Derartige Operationen erfordern es, genaue Kenntnisse über die Zusammenhänge im Mesh zu haben. Dies geht zwar auch mit der zuvor beschriebenen Datenstruktur, ist dort aber sehr, sehr mühselig.

Weitere Fragen, die im Zusammenhang mit der Bearbeitung von Meshes auftreten können sind zum Beispiel:

  • Welche Flächen verwenden einen bestimmten Vertex?
  • Welche Kanten verwenden einen bestimmten Vertex?
  • Welche Flächen grenzen an eine Kante?
  • Welche Kanten grenzen an eine Fläche?
  • Welche Flächen grenzen an eine Fläche?

Extrem hilfreich sind diese Informationen und die Half Edge Struktur auch für die sogenannte Constructive Solid Geometry. Zur Erzeugung solcher Objekte werden exakt solche Informationen zuhauf benötigt.

Zur effektiven Beantwortung solcher Problemstellungen, verwendet man sogenannte Boundary Representations (brep). In solchen Datenstrukturen sind exakt diese Abhängigkeiten untereinander beschrieben. BREPs sind z.B. die Winged Edge oder die Radial Edge Struktur oder eben auch die hier beschriebene Half Edge Struktur. Diese Datenstrukturen sind dazu geeignet, die oben genannten Fragen zu beantworten, aber die hier hat einen entscheidenden Vorteil. Bei einigen dieser Abfragen arbeitet Half Edge einfach effektiver. Einige der unterschiedlichen Arten und der Laufzeiten finden sich in Wikipedia. Einen Nachteil möchte ich in diesem Zusammenhang aber auch nicht verschweigen. Die Half Edge Struktur benötigt deutlich mehr Speicherplatz.

Half Edge Struktur

Der Name der Half Edge Struktur kommt daher, da dort im Grunde genommen halbe Kanten gespeichert werden. Eine Half Edge ist die Hälfte einer Kante. Ein Paar von zwei Half Edges ergibt also eine Kante, wobei die Half Edges dabei in exakt entgegengesetzte Richtungen zeigen.

In C# sieht die Half Edge Datenstruktur ungefähr so aus:

public struct HalfEdge
{
  public HalfEdgeVertex vertex;
  public HalfEdge pair;
  public HalfEdgeFace face;
  public HalfEdge next;
}

Den referenzierten HalfEdgeVertex können wir dabei wie folgt darstellen:

public struct HalfEdgeVertex<T>
{
  public T vertex;
  public HalfEdge edge;
}

Ich habe hier eine generische Variante gewählt um zu verdeutlichen, daß die Half Edge Struktur unabhängig von der Anzahl der Dimensionen funktioniert. Für T kann also problemlos Vector2 oder Vector3 eingesetzt werden.

Die einzelne Fläche kann ganz einfach durch eine Referenz auf eine der Kanten dargestellt werden. Welche Kante dabei referenziert wird spielt keine Rolle, sie muss nur an die Fläche angrenzen. Diese Struktur wird in der Regel um weitere Daten angereichert um eine praktische Verwendung zu haben. Dies kann z.B. eine Normale sein oder Texturinformationen.

public struct HalfEdgeFace
{
  public HalfEdge edge;
}

Zum besseren Verständnis habe ich in der folgenden Grafik versucht, die einzelnen Elemente zu visualisieren:

In der vorliegenden Grafik sind folgende Elemente dargestellt:

  • rote Punkte
  • Vertices aus denen das Objekt besteht

  • schwarze Linien
  • sind die Kanten, die die Vertices verbinden

  • gelb
  • ist die aus den Vertices entstehende Fläche

  • blaue Kästen
  • sind jeweils ein Paar bestehenden aus zwei Half Edges

  • blaue Pfeile
  • sind Referenzen auf die nächste Half Edge Struktur

  • grüne Pfeile
  • sind eine Half Edge

Wie man sieht, sind in dieser Struktur eine ganze Menge an Daten enthalten, die es uns ermöglich alle der oben gestellten Fragen effektiv zu beantworten.

Wie diese Fragen im Detail beantwortet werden, werde ich erst in den folgenden Artikeln näher erläutern. Für die meisten sollte es jedoch anhand des Basiswissens, daß ich in diesem Beitrag beschrieben habe bereits möglich sein diese Fragen selbst zu beantworten und eine geeignete Lösung zu entwickeln.

Advertisements

Veröffentlicht am 15.06.2011 in Algorithmen, C# und mit , , , getaggt. Setze ein Lesezeichen auf den Permalink. Hinterlasse einen Kommentar.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: