Tetraederzerlegung

TetraederzerlegungIna Ehmann

Tetraederzerlegung

1. Eigenschaften eines Tetraeders2. Allgemeine Tetraederzerlegung3. Reguläre Tetraederzerlegung4. Euler Formeln5. Tetraederzerlegung konstruieren

5.1 Type-4 5.2 Freudenthal Zerlegung5.3 Type-6

6. Verfeinerung einer Tetraederzerlegung6.1 Die Alfeld Verfeinerung6.2 Die Worsey-Farin Verfeinerung

Tetraederzerlegung

Inhalt:

Ina Ehmann

1. Eigenschaften eines Tetraeders

Ina Ehmann

• 4 Knoten• 6 Kanten• 4 Dreiecksflächen

v₁, v₂, v₃, v₄ in ³ℝTetraeder T := < v₁, v₂, v₃, v₄ >Knoten vi := (xi, yi, zi) von T

Bei einem regelmäßigen Tetraedersind alle 6 Kanten sind gleich lang. (4 gleichseitige Dreiecke)

Tetraederzerlegung

V4

V3

V2

V1

< v2 , v

3 , v4 ><

v 1, v

4 >

Definition 1:|T| sei die Länge der längsten Kante von T. pT sei der Radius der größten Kugel, die ganz in T liegt. Der Quotient KT := |T|/pT wird shape parameter von T genannt.

Der shape parameter KT beschreibt die Gestalt von T. Bei einem regelmäßigen Tetraeder ist KT = 12/√6.Für jedes andere Tetraeder ist KT größer.

2. Allgemeine Tetraederzerlegung

Ina Ehmann

Definition 2:Eine Sammlung ∆ := {Ti} von Tetraedern in ℝ³ wird Tetraederzerlegung einer

polygonalen Menge Ω := U Ti genannt, falls sich Tetraeder aus ∆ höchstens an Knoten schneiden, sich entlang einer Kante oder Dreiecksfläche berühren.

Diese Definition erlaubt also auch eine Tetraederzerlegung wie folgt:• Zwei Tetraeder die sich nicht berühren• Zwei Tetraeder die sich nur an einem Knoten berühren• Zwei Tetraeder die sich nur eine Kante teilen

Diese Definition lässt auch folgendes zu:• Ω hat eine durchgängige Lücke z.B. wenn Ω die Form eines Ringen hat• Ω hat Hohlräume

Tetraederzerlegung

Ni=1

Ni=1

Ina Ehmann

Definition 3:Sei v der Knoten einer Tetraederzerlegung ∆, star(v) ist die Menge aller Tetraeder aus Δ die sich den Knoten v teilen. Wir setzen star1(v) := star(v) und definieren star i (v) induktiv für alle i > 1als die Menge aller Tetraeder aus ∆ die einen Schnittpunkt mit star i-1 (v) haben. Ähnlich definieren wir star0 (T) := T und starj (T) := U{star (v) : v star∈ j-1 (T)} für alle j ≥ 1.

2. Allgemeine Tetraederzerlegung

Tetraederzerlegung

star(v) (dunkel blau) star²(v) (mittel und dunkel blau)

star(T) (dunkelgrün)star²(T) (dunkel und hellgrün)

Ina Ehmann

Definition 4:Eine Tetraederzerlegung wird shellable genannt, falls sie aus einem einzelnen Tetraeder besteht oder aus einer shellable Tetraederzerlegung entsteht, indem ein Tetraeder, der eins, zwei oder drei Dreiecksflächen von berührt, hinzugefügt wird.∆̃

∆̃

Definition 5:Eine Tetraederzerlegung heißt regulär, falls folgendes gilt:1) ∆ ist shellable, oder2) ∆ kann aus einer regulären Tetraederzerlegung entstehen, indem eine reguläre Lücke

oder regulären Hohlraum erzeugt wird.

3. Reguläre Tetraederzerlegung

Tetraederzerlegung

Nicht alle Tetraederzerlegungen sind shellable. Z.B. zwei Tetraeder die sich nur an einem Knoten oder einer Kante berühren, sind nicht shellable.

4. Euler Formeln

Ina Ehmann

Die Euler Formeln beschreiben die Beziehungen zwischen der Anzahl der Knoten, Kanten und Flächen in einer Tetraederzerlegung ∆

• VI, VB Anzahl der inneren Knoten und Knoten am Rand

• EI, EB Anzahl der inneren Kanten und Kanten am Rand

• FI, FB Anzahl der inneren Flächen und Flächen am Rand• N Anzahl der Tetraeder von ∆

Tetraederzerlegung

Ina Ehmann

Satz 1:∆ sei eine shellable Tetraederzerlegung.Wir erzeugen ∆ indem wir mit einem Tetraeder anfangen und ein Tetraeder nach dem anderen hinzufügen, so dass die Anzahl der Tetraeder, die die vorherige Zerlegung an exakt i Flächen berühren αi ist mit i= 1, 2, 3.

1) N = 1 + α1 + α2 + α3

2) FI = α1 + 2α2 + 3α3 3) FB = 2α1 - 2α3 + 44) EI = α2 - 3α3

5) EB = 3α1 - 3α3 + 66) VB = α1 – α3 + 47) VI = α3

Tetraederzerlegung

4. Euler Formeln

Ina Ehmann

Beweis:

zu 1) N = 1 + α1 + α2 + α3

Wir fangen mit einem Tetraeder an und notieren die Anzahl αi wie oft wir ein Tetraeder

hinzufügen, das genau i Flächen berührt, so dass die gesamte Anzahl von Tetraeder N = 1 + α1 + α2 + α3 ist.

zu 2) FI = α1 + 2α2 + 3α3 Jedesmal, wenn wir ein Tetraeder zu einer shellable Tetraederzerlegung hinzufügen, welches genau i Flächen berührt, steigt die Anzahl von inneren Flächen mit i. Also FI = α1 + 2α2 + 3α3

Rest analog. □

Tetraederzerlegung

4. Euler Formeln

Ina Ehmann

Diese Gleichungen können auf verschiedene Arten kombiniert werden, so dass sich verschiedene Beziehungen zwischen der Anzahl der Knoten, Kanten und Flächen zeigen.

Satz 2:Sei ∆ einen shellable Tetraederzerlegung.Dann gilt:

1) N = EI + VB – VI – 3

2) N = FI /2 + FB /4

3) EB = 3VB – 64) FB = 2EB – 3

Tetraederzerlegung

4. Euler Formeln

Ina Ehmann

Beweis:

Aus den Gleichungen aus Satz 1 folgt sofort:α3 = VI

VB = α1 - α3 + 4

VB = α1 - VI + 4

α1 = VB + VI – 4

EI = α2 + 3α3

EI = α2 + 3VI

α2 = EI – 3VI

Tetraederzerlegung

4. Euler Formeln

Zu 1) N = EI + VB – VI – 3

N = 1 + α1 + α2 + α3

= 1 + VB + VI – 4 + EI – 3VI + VI

= EI + VB – VI – 3

Rest analog. □

Ina Ehmann

5.1 Typ-4 TetraederzerlegungenSei B := [a1, b1] x [a2, b2] x [a3, b3] ein Rechteckiger Raum in ³ undℝ

a1 = x0 < x1 < … < xm = b1

a2 = y0 < y1 < … < yn = b2

a3 = z0 < z1 < … < zl = b3

V :={(xi, yj, zk)} und B:= {Bijk} die Menge von N:= m x n x l Teilräume

Bijk := [xi, xi+1] x [ yj, yj+1] x [zk, zk+1]

Tetraederzerlegung

5. Tetraederzerlegungen konstruieren

Lemma 1: Die Menge V kann unterteilt werden in die Menge V1 und V2, so dass alle Knoten v ∈ Vs, s ∈ {1,2} lediglich gemeinsame Kanten mit Knoten der Menge v ∈ Vt, t ∈ {1, 2} und s≠t.

Wir nennen die Konten von V1,Typ-1 und die Knoten V2 Typ-2

Ina Ehmann

Abbildung 1 zeigt die Zerlegungen eines einzelnen Teilraums in 5 Tetraeder. (Typ-1 Knoten sind rot, Typ-2 Knoten sind blau.) Das Tetraeder mit der roten Flächen hat ausschließlich Knoten vom Typ-2, alle Typ-2 Knoten wurden verbunden. Die vier anderen Tetraeder besitzen genau einen Typ-1 Knoten.

Tetraederzerlegung

5. Tetraederzerlegungen konstruieren

Abb. 1

Ina Ehmann

5.2 Freudenthal Zerlegung

Sei n ∈ ℕ und h:= 1/n⋄ := {Q ijk := [ih, (i+1)h] x [jh, (j+1)h] x [kh, (k+1)h]; i,j,k = 0, …, n-1}

⋄ sei die regelmäßige Zerlegung des Einheitswürfels Ω = [0,1] x [0,1] x [0,1] ⊂ℝ³V := {vijk := (ih, jh, kh)}

Definition 6:

Sei △F die Tetraederzerlegung die aus ⋄ folgendermaßen entsteht:für alle 0 ≤ i,j,k ≤ n-1 wird der Würfel Qijk von den drei Ebenen

y – x = (j - i)h, z – x = (k – i)h, z – y = (k – j)hgeschnitten. △F wird als Freudenthal Zerlegung von Ω bezeichnet.

Tetraederzerlegung

5. Tetraederzerlegungen konstruieren

ni,j,k=0

Ina Ehmann Tetraederzerlegung

5. Tetraederzerlegungen konstruieren

T4

T³T² T1

T5T6

Freudenthal Zerlegung:Jeder Würfel wird in 6 Tetraeder zerlegt

Ina Ehmann

5.3 Typ-6 Zerlegung

Die 15 Knoten eines Würfels

8 Eckknoten 6 Flächenknoten 1 Würfelmittelpunktknoten

Tetraederzerlegung

5. Tetraederzerlegungen konstruieren

Ina Ehmann

5.3 Typ-6 Zerlegung

1. Verbinde den Würfelmittelpunkt mit den 8 Eckknoten 6 Pyramiden

2. Verbinde den Würfelmittelpunkt mit den 6 Flächenknoten und die Flächenknoten mit den 8 Eckknoten 4 Tetraeder welche die Pyramidenachse als gemeinsame Kante haben 24 Tetraeder

Tetraederzerlegung

5. Tetraederzerlegungen konstruieren

Ina Ehmann

6. Verfeinerung einer Tetraederzerlegung

6.1 Die Alfeld Verfeinerung

△,△R sind zwei Tetraederzerlegungen in ΩDefinition 7:△R ist eine Verfeinerung von △ falls gilt:

1) Jeder Knoten von △ ist ein Knoten von △R

2) Jeder Tetraeder t ∈△R ist ein Teiltetraeder von den Tetraeder T ∈ △

Definition 8:

Sei T := ‹v1, v2, v3, v4› , vt := (v1+v2+v3+v3)/4 der Mittelpunkt von T. Die Alfred Teilung TA von T besteht aus 4 Teiltetraeder die entstehen, indem vt mit jedem Knoten von T verbunden wird.

Tetraederzerlegung

Die Alfeld Aufteilung eines Tetraeders

Ina Ehmann

6.2 Die Worsey-Farin Verfeinerung

Tetraederzerlegung

6. Verfeinerung einer Tetraederzerlegung

Definition 7: △ sei eine Tetraederzerlegung. Für jeden Tetraeder T in △ sei vT der Mittelpunkt von T

und TA sei die dazugehörige Alfeld Teilung von T. Für jede innere Fläche F von △, die sich zwei Tetraeder teilen, sei vF der Punkt, in dem die Strecke, die die zwei Mittelpunkte von T verbindet, F schneidet.Für jede äußere Fläche F sei vF, der Mittelpunkt von F. Jetzt verbinden wir für jede Fläche F, vF mit den Knoten von F und mit dem Mittelpunkt vT von jedem Tetraeder, das sich die Fläche F teilt. Die daraus resultierende verfeinerte Zerlegung △WF wird Worsey-Farin Verfeinerung von △ genannt.

Eine teilweise Worsey-Farin Aufteilung eines Tetraeders

Ina Ehmann Tetraederzerlegung

Tetraederzerlegung

Quellen:

• Lai, Schumaker Spline Functions on Triangulations

• Hecklin, Nürnberger, Schumaker, Zeilfelder: A local Lagrange interpolation method based on C1 cubic splines on Freudenthal partitions

• Matt, Nürnberger: Local Lagrange interpolation using cubic C splines on type-4 cube partitions

• Nürnberger, Rhein, Schneider: Local Lagrange Interpolation by Quintic C1 Splines on Type-6 Tetrahedral Partitions

Ina Ehmann Tetraederzerlegung

Tetraederzerlegung

Vielen Dank für Ihre Aufmerksamkeit!