Differences

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

--- kurse:efcomputergrafik:kw47 [2019/11/06 08:01]
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 55: / Line 69: @@
 Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft.
-Verwenden Sie dazu die bereitgestellte {{ :kurse:efcomputergrafik:vector.py |Vector-Bibliothek}} (die die gleichen Methoden wie die entsprechende Bibliothek in Blender zur Verfügung stellt). Starten Sie Ihr Programm wie folgt.
+Verwenden Sie dazu die bereitgestellte {{ :kurse:efcomputergrafik:vector.py |Vector-Bibliothek}} (die die gleichen Methoden wie die entsprechende Bibliothek in Blender zur Verfügung stellt). Starten Sie mit folgendem Code unten.
 Für den Umgang mit der Klasse "Vector" studieren Sie bitten den Code am Ende der Datei vector.py (der nur dann ausgeführt wird, wenn die Datei vector.py direkt ausgeführt wird, nicht aber wenn die Datei mit "import" eingebunden wird.)
@@ 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 101: / Line 128: @@
 Der Punkt $p(t)$ wird wie folgt berechnet:
-===== Aufgaben =====
+  * 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 ====
 === Animation ===
 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 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\}$.
+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)$.