Mesh

Als Mesh (engl. für Netz) bezeichnet man die Menge an Vertices, welche ein Objekt formen. Die Vertices bilden zusammen eine Art Gitter oder Netz, welches die Oberfläche des Objektes abbildet. (siehe auch: Primitive)

Eine beleuchtete (siehe glLight) Kugel.

Die selbe Kugel in der Gitternetz Darstellung (siehe glPolygonMode). Das Gitternetz entspricht dem Mesh.

Wenn man davon spricht, dass ein Objekt aus verschiedenen Meshes besteht, dann heißt dies, dass das Objekt aus verschiedenen Teilobjekten zusammen gesetzt ist. In vielen Modellformaten (z.B. 3ds, das Format von 3D Studio Max) werden alle Vertices eines Geometrieobjektes (das sind die Basisobjekte die 3D Studio Max anbietet. Z.B. Würfel, Kugel, etc.) einem Mesh zu geordnet. Besteht z.B. eine Figur aus den Einzelobjekten Kopf, Rumpf, Arm-Links, Arm-Rechts, Bein-Links, Bein-Rechts, so sind diese Einzelobjekte jeweils als ein Mesh in der 3ds Datei gespeichert. Jedes Mesh besteht dann wiederum aus vielen Vertices, die das oben genannte Gitter bilden.

Eigenschaften

Im folgenden werden einige Eigenschaften definiert die ein beliebiges Mesh haben kann. Erfüllt ein Mesh diese Eigenschaften können wir diverse Abschätzungen über das Verhältnis zwischen Vertices, Kanten (Edges) und Faces treffen. Diese helfen zum Beispiel bei Aussagen über den Speicherbedarf eines Meshes. Auch kann man beweisen das gewisse Meshes gar nicht realisierbar sind.

2-Mannigfaltigkeit

2-Mannigfaltigkeit ist eine wichtige Eigenschaft. Einfach ausgedrückt ist sie gegeben, wenn das Mesh aus einer einfachen Oberfläche besteht an der keine zusätzlichen Teile angebracht sind. Eine etwas formalere Definition folgt nun. Eine alternative Definition findet sich bei Wikipedia.

Ein Mesh ist 2-mannigfaltig, wenn die folgenden Eigenschaften gegeben sind.

• Local Disc Property: Um jeden beliebigen Punkt auf dem Mesh lässt sich immer eine ε-Umgebung (= Kugel mit Radius ε > 0) finden, so dass die Schnittmenge aus ε-Umgebung und Mesh homöomorph (nicht verwechseln mit homomorph) zu einer planaren Scheibe ist. Sofern es sich um einen Punkt auf dem Rand handelt, kann die Schnittmenge auch homöomorph zu einem Halbkreis sein.

• Edge Ordering Property: Die Nachbarvertices eines jeden Vertex lassen sich eindeutig im Uhrzeigersinn aufzählen.

• Face Count Property: Jede innere Kante hat genau zwei adjazente Faces. Jede Kante die am Rand liegt hat genau ein adjazentes Face.

Geschlossenheit

Ein Mesh heißt geschlossen, wenn es keinen Rand besitzt. Insbesondere besitzt das Mesh also ein "innen" und ein "außen". Ist das Mesh gleichzeitig auch 2-mannigfaltig, besitzt jede Kante genau zwei adjazente Faces.

Euler-Formel

Für geschlossene und 2-mannigfaltige Meshes gilt die Euler-Formel:

V - E + F = 2(1-g)

Die Variablen V, E und F stehen dabei für die Anzahl der Vertices, Kanten (Edges) und Faces. Die Variable g steht für den Genus des Objektes. Intuitiv ist der Genus eines Meshes die Anzahl der "Griffe". Ein Bild erklärt dies wohl am besten.

Ein doppelter Torus, also mit zwei Löchern, hätte dann den Genus Zwei. Sofern das Mesh nicht geschlossen ist, rechnet man einfach mit zusätzlichen Faces, welches das Mesh schließen. Aus diesem Grund ist der Genus der Röhre im obigen Bild auch Null. An jedem Ende der Röhre wird je ein Face benötigt welches die offenen Kanten abschließt. Üblicherweise ist der Genus im Vergleich zur Anzahl der Vertices und Faces sehr klein. Aus diesem Grunde wird der Genus häufig als konstant angenommen. Für Abschätzungen bei denen es sowieso nur auf die ungefähre Größenordnung ankommt wird daher meist die vereinfachte Formel verwendet:

V - E + F ≈ 0

Abschätzungen für Dreiecks-Meshes

Die im folgenden gezeigten Aussagen sind zum Teil nur Abschätzungen. Es gilt also keine echte Gleichheit, da der Genus zum Teil vernachlässigt wird!

Kanten vs. Faces

In einem geschlossenen und 2-mannigfaltigen Dreiecks-Mesh gibt es 1.5 mal so viele Kanten wie Faces. Es gilt also:

2*E = 3*F

Die obige Aussage lässt sich leicht nachvollziehen. Aufgrund der Geschlossenheit und 2-Mannigfaltigkeit besitzt jede Kante genau zwei adjazente Faces. Wir teilen nun jede Kante der Länge nach in zwei Teile und können so jedem Face eindeutig eine sogenannte Halbkante zuordnen. Offensichtlich gibt es doppelt so viele Halbkanten wie Kanten, also:

2*E = HE

Zusätzlich sind jedem Face drei Halbkanten zugeordnet, damit gilt:

HE = 3*F

Insgesamt folgt also

2*E = 3*F

Diese Aussage gilt unabhängig vom Genus.

Valenz

Die Valenz eines Vertex ist die Anzahl der Kanten zu denen er gehört. Diese Zahl ist gleich der Anzahl der Faces zu denen der Vertex gehört. In einem geschlossenen und 2-mannigfaltigen Dreiecks-Mesh mit vernachlässigbarem Genus beträgt durchschnittliche Vertexvalenz ungefähr 6. Also gehört jeder Vertex im Durchschnitt zu 6 Dreiecken. Diese Aussage hilft zum Beispiel den eingesparten Speicherplatz bei Verwendung von Indices abzuschätzen.

Auch diese Aussage lässt sich leicht zeigen. Dieses mal teilen wir jede Kante in der Mitte zwischen den Vertices und erhalten wieder zwei Halbkanten. Jede Halbkante kann eindeutig einem Vertex zugewiesen werden. Offensichtlich haben wir wieder doppelt so viele Halbkanten wie Kanten.

2*E = HE

Zusammen mit der oben gezeigten Aussage 2*E = 3*F setzen wir dies nun nacheinander in die vereinfachte Euler-Formel ein:

V - E + F ≈ 0

<=> V - E + (2/3)*E ≈ 0

<=> V - (1/3)*E ≈ 0

<=> V - (1/6)*HE ≈ 0

<=> 6*V ≈ HE

Jeder Vertex ist also adjazent zu durchschnittlich ungefähr 6 Kanten.

Vertices vs. Kanten

Aus der Valenz-Abschätzung können wir auch eine Relation zwischen Vertices und Kanten herstellen. Es gilt 2*E = HE und 6*V ≈ HE, also gilt insgesamt 3*V ≈ E. In einem geschlossenen und 2-mannigfaltigen Dreiecks-Mesh mit vernachlässigbarem Genus gibt es also ungefähr dreimal so viele Kanten wie Vertices.

Vertices vs. Faces

Aus 2*E = 3*F und 3*V ≈ E kann man natürlich auch leicht folgern, dass es ungefähr zweimal so viele Faces wie Vertices gibt. Dies gilt natürlich wieder nur, wenn es sich um ein geschlossenes und 2-mannigfaltiges Dreiecks-Mesh mit vernachlässigbarem Genus handelt.