Differences

This shows you the differences between two versions of the page.

--- kurse:efcomputergrafik:kw47 [2019/11/08 08:51]
Ivo Blöchliger [Aufgaben]
+++ kurse:efcomputergrafik:kw47 [2019/11/22 09:09] (current)
Ivo Blöchliger [Eindeutigkeiten der Kombinationen]
@@ Line 39: / Line 39: @@
   * die Linearkombination von Linearkombinationen eine einfache Linearkombination ist.
   * die konvexe Kombination von konvexen Kombinationen eine einfache konvexe Kombination ist.
+==== Eindeutigkeiten der Kombinationen ====
+Gegeben ist ein Ortsvektor $\vec p$ und eine Menge von $n$ Vektoren $\vec v_i$. Angenommen $\vec p$ ist als Kombination (linear oder konvex) der Vektoren $\vec v_i$ darzustellen, dann
+  * ist die Linearkombination eindeutig, wenn die Vektoren linear unabhängig sind und damit einen $n$-dimensionalen Unterraum aufspannen.
+  * ist die konvexe Kombination eindeutig, wenn die Dimension der konvexen Hülle $n-1$ ist.
+Surafel hat einen sehr eleganten Beweis geliefert. Die Idee ist, dass man die verschobenen Vektoren $\vec u_i=\vec v_i - \vec v_1$ betrachtet.
+Sei $\vec p = \sum r_i \vec v_i$, mit $\sum r_i = 1$, $r_i \in [0,1]$.
+Die entsprechende konvexe Kombination der Vektoren $\vec u_i$ liefert
+$\sum r_i(\vec v_i - \vec v_1) = \sum r_i\vec v_i - \sum r_i \vec v_1 = \vec p-\vec v_1$.
+Die Vektoren $\vec u_i$ für $i \geq 2$ spannen einen $n-1$-dimensionalen Unterraum auf, womit die Linearkombination
+$\sum_{i=2}^n r_i \vec u_i =  \vec p - \vec v_1$ eindeutig ist. Damit ist der Koeffizient für $r_1$ (über die Bedingung $\sum r_i =1$) ebenfalls eindeutig.
 ====== Geometrische Definition von Bezierkurven ======
@@ Line 48: / Line 62: @@
 Bestimmen Sie eine Parametrierung dieser "Kurve":
 $$
-p(t) = \ldots =: I(t, p_0, p_1)
+p(t) = (1-t) \cdot p_0 + t \cdot p_1 =: I(t, p_0, p_1)
 $$
 Die Funktion $I$ interpoliert linear zwischen $p_0$ und $p_1$ für $t \in [0,1]$.
@@ Line 63: / Line 77: @@
 from vector import Vector
 # Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen.
 makeGPanel(0,2,0,2)
-#
+# t in [0,1]
-# Hier fehlt die Definition einer oder mehrerer Funktionen
+# p0, p1, sind Vektoren
-#
+# Liefert die lineare interpolation
+def interpolate(t, p0, p1):
+    return (1-t)*p0+t*p1
+def linie(p0, p1):
+    line(p0[0], p0[1], p1[0], p1[1])
+def kreis(p):
+    move(p[0], p[1])
+    fillCircle(0.02)
 n = 100
-enableRepaint(False)  #Während dem Zeichnen nichts anzeigen
+enableRepaint(False)  #Waehrend dem Zeichnen nichts anzeigen
 intpts = [Vector((0.1,0.3,0)), Vector((1.8,1.4,0))]  # Liste der zu interpolierenden 3D-Vektoren
 for i in range(n+1):
-    t=n/i
+    t=i/n
     clear()  # Bild löschen
-    #
+    # Ganze Linie
-    # Punkt p(t) berechnen und Situation schön anzeigen
+    linie(intpts[0],  intpts[1])
-    #
+    # Interpolierter Punkt
+    p = interpolate(t,intpts[0], intpts[1])
+    # Kreiszentrum
+    kreis(p)
     repaint()  # Gezeichnetes anzeigen (vermindert flackern)
     delay(60)
 </code>
@@ Line 100: / Line 127: @@
 Gegeben sind 4 **Kontrollpunkte** $p_i$ mit $i\in\{0,1,2,3\}$.
 Der Punkt $p(t)$ wird wie folgt berechnet:
+  * Man berechne $s_i(t) = I(p_i, p_{i+1},t)$ für $i\in \{0,1,2\}$. Und daraus
+  * $q_i(t) = I(s_i, s_{i+1},t)$ für $i\in \{0,1\}$. Und daraus
+  * $p(t) = I(q_0, q_1, t)$
 ==== Aufgaben ====
@@ Line 106: / Line 138: @@
 Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft.
-===== Grad $n$ (wird selten für $n>3$ verwendet) =====
+<code python bezierallgemein.py>
-Gegeben sind $n+1$ Kontrollpunkte $p_i$ mit $i \in \{0,1,\ldots, n,n+1\}$.
+from gpanel import *
+from vector import Vector
+import math
+# Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen.
+makeGPanel(0,2,0,2)
+# t in [0,1]
+# p0, p1, sind Vektoren
+# Liefert die lineare interpolation
+def interpolate(t, p0, p1):
+    return (1-t)*p0+t*p1
+def linie(p0, p1):
+    line(p0[0], p0[1], p1[0], p1[1])
+def kreis(p, typ=0):
+    move(p[0], p[1])
+    if typ==0:
+        circle(0.04)
+    else:
+        fillCircle(0.02)
-===== Aufgabe * =====
+n = 100
-Die entsprechende Animation kann für beliebige $n$ sehr elegant rekursiv programmiert werden.
+enableRepaint(False)  #Waehrend dem Zeichnen nichts anzeigen
+#pini = [Vector((0.4,0.3,0)), Vector((1.8,1.9,0)), Vector((0.2,1.8,0)), Vector((1.8,0.2,0))]  # Liste der zu interpolierenden 3D-Vektoren
+num = 20;
+# Folge von Punkten auf einer Lissajou-Figur
+pini = [Vector([math.sin(i/num*4*math.pi)+1, math.cos(i/num*6*math.pi)+1,0]) for i in range(num)]
+kurve=[]
+for i in range(n+1):
+    t=i/n
+    clear()  # Bild löschen
+    p = pini
+    while len(p)>1:
+        # Neue Punkte
+        q = []
+        for j in range(len(p)-1):
+            linie(p[j], p[j+1])
+            q.append(interpolate(t, p[j], p[j+1]))
+            kreis(q[j])
+        p = q
+    kurve.append(p[0])
+    for k in kurve:
+        kreis(k,1)
+    repaint()  # Gezeichnetes anzeigen (vermindert flackern)
+    delay(60)
-====== Algebraische Form ======
+</code>
-Bestimmen Sie die algebraische Form der Bezierkurven von Grad 1,2,3 (und $n$, wer möchte), und zwar
-als konvexe Kombination der Kontrollpunkte mit den Koeffizienten als vollständig faktorisierte Polynome in $t$.
+===== Grad $n$ (wird selten für $n>3$ verwendet) =====
+Gegeben sind $n+1$ Kontrollpunkte $p_i$ mit $i \in \{0,1,\ldots, n,n+1\}$.
-===== Form der Polynome und deren Ableitungen =====
+Man interpoliert aufeinanderfolgende Punktepaare linear und bekommt so eine Liste von $n-1$ Punkten.
+Mit dieser Liste verfährt man gleich, bis nur noch 1 Punkt übrig bleibt. Das ist Punkt $p(t)$.
-===== Ableitungen von $p(t)$ für $t \in [0,1]$ =====
-====== Interpolation mit kubischen Funktionen ======
-Gesucht ist eine kubische Funktion durch 2 gegebene Punkte $P=(0,y_P)$ und $Q=(1,y_Q)$ mit gegebenen Tangentensteigungen $m_P$ und $m_Q$ in diesen Punkten.
-Variante 1: Ansatz $f(x) = ax^3+bx^2+cx+d$, Gleichungssystem aufstellen, lösen.
-Variante 2: Anstatt die kanonische Basis $1,x,x^2,x^3$ zu verwenden, soll eine Basis mit der Eigenschaft gefunden werden, dass von folgenden Werten immer nur genau einer Eins und die restlichen Null sind: $b(0), b(1), b'(0), b'(1)$. Die gesuchte Lösung ergibt sich dann als einfache Linearkombination mit den gegebenen Koeffizienten.
-====== Interpolation mit Splines ======