Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
kurse:efcomputergrafik:kw47 [2019/11/08 08:51] Ivo Blöchliger [Aufgaben] |
kurse:efcomputergrafik:kw47 [2019/11/22 09:09] Ivo Blöchliger [Eindeutigkeiten der Kombinationen] |
||
---|---|---|---|
Line 39: | Line 39: | ||
* die Linearkombination von Linearkombinationen eine einfache Linearkombination ist. | * die Linearkombination von Linearkombinationen eine einfache Linearkombination ist. | ||
* die konvexe Kombination von konvexen Kombinationen eine einfache konvexe Kombination 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, | ||
+ | * 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 ====== | ====== Geometrische Definition von Bezierkurven ====== | ||
Line 48: | Line 62: | ||
Bestimmen Sie eine Parametrierung dieser " | Bestimmen Sie eine Parametrierung dieser " | ||
$$ | $$ | ||
- | 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]$. | 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 | from vector import Vector | ||
# Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen. | # Die Datei vector.py muss im gleichen Verzeichnis wie diese Programm liegen. | ||
+ | |||
makeGPanel(0, | makeGPanel(0, | ||
- | + | ||
- | # | + | # t in [0,1] |
- | # Hier fehlt die Definition einer oder mehrerer Funktionen | + | # p0, p1, sind Vektoren |
- | # | + | # Liefert die lineare interpolation |
+ | def interpolate(t, | ||
+ | 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 | n = 100 | ||
- | enableRepaint(False) | + | enableRepaint(False) |
intpts = [Vector((0.1, | intpts = [Vector((0.1, | ||
for i in range(n+1): | for i in range(n+1): | ||
- | t=n/i | + | t=i/n |
clear() | clear() | ||
- | # | + | # Ganze Linie |
- | # Punkt p(t) berechnen und Situation schön anzeigen | + | linie(intpts[0], |
- | # | + | # Interpolierter |
+ | | ||
+ | # Kreiszentrum | ||
+ | kreis(p) | ||
repaint() | repaint() | ||
delay(60) | delay(60) | ||
+ | | ||
</ | </ | ||
Line 100: | Line 127: | ||
Gegeben sind 4 **Kontrollpunkte** $p_i$ mit $i\in\{0, | Gegeben sind 4 **Kontrollpunkte** $p_i$ mit $i\in\{0, | ||
Der Punkt $p(t)$ wird wie folgt berechnet: | 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 ==== | ==== Aufgaben ==== | ||
Line 106: | Line 138: | ||
Programmieren Sie eine Animation (ca. 50 Schritte), wie der Punkt $p(t)$ läuft. | 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, | ||
+ | |||
+ | # 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) |
+ | #pini = [Vector((0.4, | ||
+ | num = 20; | ||
+ | # Folge von Punkten auf einer Lissajou-Figur | ||
+ | pini = [Vector([math.sin(i/ | ||
+ | kurve=[] | ||
+ | for i in range(n+1): | ||
+ | t=i/n | ||
+ | clear() | ||
+ | p = pini | ||
+ | while len(p)> | ||
+ | # Neue Punkte | ||
+ | q = [] | ||
+ | for j in range(len(p)-1): | ||
+ | linie(p[j], p[j+1]) | ||
+ | q.append(interpolate(t, | ||
+ | kreis(q[j]) | ||
+ | p = q | ||
+ | kurve.append(p[0]) | ||
+ | for k in kurve: | ||
+ | kreis(k, | ||
+ | repaint() | ||
+ | delay(60) | ||
- | ====== Algebraische Form ====== | + | </ |
- | 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, | ||
- | ===== Form der Polynome | + | Man interpoliert aufeinanderfolgende Punktepaare linear |
- | + | Mit dieser Liste verfährt man gleich, bis nur noch 1 Punkt übrig bleibt. Das ist Punkt $p(t)$. | |
- | ===== Ableitungen | + | |
- | + | ||
- | + | ||
- | ====== 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 | + | |
- | + | ||
- | Variante | + | |
- | + | ||
- | Variante 2: Anstatt die kanonische Basis $1, | + | |
- | + | ||
- | ====== Interpolation mit Splines ====== | + | |