Obsah
1. Bézierovy křivky podrobněji
3. Zobecnění lineární interpolace
4. Binomická věta a Bernsteinovy polynomy
5. Bernsteinovy polynomy stupně jedna až pět
6. Ověření základních vlastností Bernsteinových polynomů
7. Součet všech Bernsteinových polynomů stupně jedna až pět
8. Jak je tomu v případě Coonsových kubik?
9. Konstrukce křivky z několika na sebe navazujících segmentů
10. Parametrická a geometrická spojitost Cn a Gn
11. Zajištění spojitosti C1 nebo G1 u Bézierových křivek
12. Poznámka k Coonsovým kubikám a uniformním racionálním B-spline křivkám
13. Křivky používané v animacích
15. Bázové polynomy Catmul-Romovy spline
16. Výpočet a vykreslení jednoho segmentu Catmul-Romovy spline
17. Vykreslení celé spline složené z většího množství segmentů
18. Násobné koncové body Catmul-Romovy spline
19. Repositář s demonstračními příklady
1. Bézierovy křivky podrobněji
Na předchozí část seriálu o křivkách používaných (nejenom) v počítačové grafice dnes navážeme. Minule jsme si totiž – prozatím ovšem bez větších podrobností – představili jeden velmi důležitý typ parametrických křivek. Jedná se o Bézierovy aproximační křivky, jenž se dnes používají například při popisu znaků (TrueType), dále v PostScriptu (a odvozeně taktéž v PDF), ve formátu SVG, taktéž v mnoha kreslicích programech (CorelDraw!, Adobe Illustrator, Inkscape) atd. (ovšem nenechme se unést, protože například v animacích se již používají odlišné křivky, o čemž se dnes záhy taktéž přesvědčíme).
Bézierovy křivky jsou reprezentovány polynomem n-tého stupně, kde n je volitelná celočíselná hodnota (typicky větší než jedna). Z mnoha praktických důvodů (výpočetní složitost, lokalita změn, omezení zákmitů, jednoduchost práce z pohledu uživatele) se ovšem setkáme zejména z Bézierovými křivkami druhého a třetího stupně, tedy s kubikami a kvadrikami. Tyto křivky lze na sebe navázat, popř. je zkombinovat s lineárními segmenty, kruhovými oblouky atd.
Připomeňme si, jak je možné Bézierovy křivky vykreslit. Použijeme přitom jednoduchý, ale současně i naivní algoritmus, který pro hodnoty t v rozsahu 0 až 1 vypočte x-ové a y-ové souřadnice křivky, které následně propojí. Nejprve je uveden příklad zobrazující Bézierovu kvadriku, tedy parametrickou křivku stupně 2, která je z pohledu uživatele specifikována třemi body – dvěma body koncovými (těmi křivka prochází) a jedním řídicím bodem, jímž tato křivka obecně neprochází (jen pokud by všechny body ležely na jedné přímce), ovšem poloha tohoto bodu ovlivňuje tvar křivky:
"""Parametrická křivka: Bézierova kvadrika."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body Bézierovy kubiky
xc = (1, 2, 3)
yc = (1, 2.9, 1)
# Bernsteinovy polynomy pro Bézierovu kvadriku
B = [(1-t)**2,
2*t*(1-t),
t**2]
# výpočet bodů ležících na Bézierově kvadrice
x = 0
y = 0
for i in range(0, 3):
x += xc[i]*B[i]
y += yc[i]*B[i]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bézierova kvadrika', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 3)
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, 'g-')
# řídicí body Bézierovy kvadriky
ax.plot(xc, yc, 'ro')
# uložení grafu do rastrového obrázku
plt.savefig("bezier_quadric.png")
# zobrazení grafu
plt.show()
S tímto výsledkem:
Obrázek 1: Bézierova kvadrika vykreslená předchozím demonstračním příkladem.
Prakticky stejným způsobem, ovšem s využitím čtyř bodů (dvou koncových a dvou řídicích) lze vykreslit Bézierovu kubickou křivku (neboli zkráceně kubiku). Zdrojový kód demonstračního příkladu se liší zejména tím, že se používají odlišné Bernsteinovy polynomu:
"""Parametrická křivka: Bézierova kubika."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body Bézierovy kubiky
xc = (1, 1, 3, 3)
yc = (1, 2.9, 0.1, 2)
# Bernsteinovy polynomy
B = [(1-t)**3,
3*t*(1-t)**2,
3*t**2*(1-t),
t**3]
# výpočet bodů ležících na Bézierově kubice
x = 0
y = 0
for i in range(0, 4):
x += xc[i]*B[i]
y += yc[i]*B[i]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bézierova kubika', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 3)
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, 'g-')
# řídicí body Bézierovy kubiky
ax.plot(xc, yc, 'ro')
# uložení grafu do rastrového obrázku
plt.savefig("bezier_cubic.png")
# zobrazení grafu
plt.show()
Nyní by měl výsledek vypadat následovně:
Obrázek 2: Bézierova kubika vykreslená předchozím demonstračním příkladem.
2. Lineární interpolace
Podívejme se ještě jednou podrobněji na to, jak se vlastně provádí výpočet bodů ležících na Bézierově křivce. Konkrétně se jedná o tuto část programového kódu, v níž se počítají souřadnice x,y:
# výpočet bodů ležících na Bézierově kubice
x = 0
y = 0
for i in range(0, 4):
x += xc[i]*B[i]
y += yc[i]*B[i]
Výše uvedený výpočet je jednou z forem lineární kombinace. Ovšem pro demonstrační účely je lepší nepoužít ani Bézierovu kvadriku (stupně 2) či kubiku (stupně 3), ale Bézierovu křivku stupně 1. Jedná se o křivku určenou pouze dvěma body, jimiž tato křivka prochází (což odpovídá i kvadrikám a kubikám, do nichž jsou přidány pouze další řídicí body). Tato parametrická křivka je zcela jistě všem dobře známá – jedná se totiž o běžnou úsečku. I tu lze pochopitelně vyjádřit parametricky a současně i formou lineární kombinace dvou polynomů. Konkrétně se bude jednat o polynomy 1-t a t, kde t leží v rozsahu 0 až 1. Bézierova křivka prvního stupně (tento název ovšem prakticky nikdo pochopitelně nepoužívá) se tedy může vykreslit tímto demonstračním příkladem:
"""Parametrická křivka: lineární interpolace."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body
xc = (1, 3)
yc = (1, 2)
# Bernsteinovy polynomy pro lineární interpolaci
B = [1 * (1-t),
1 * t]
# výpočet bodů ležících na interpolační křivce
x = 0
y = 0
for i in range(0, 2):
x += xc[i]*B[i]
y += yc[i]*B[i]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Lineární interpolace', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 3)
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, 'g-')
# řídicí body
ax.plot(xc, yc, 'ro')
# uložení grafu do rastrového obrázku
plt.savefig("linear_interpolation.png")
# zobrazení grafu
plt.show()
S výsledkem:
Obrázek 3: Bézierova křivka stupně 1 neboli úsečka.
3. Zobecnění lineární interpolace
Pierre Bézier své křivky odvodil matematicky, na rozdíl od jeho současníka Paula de Casteljau, který nezávisle na Bézierovi (vlastně již před ním) našel geometrickou konstrukci těchto křivek. Ovšem nejdříve se podívejme na způsob odvození, který zvolil Bézier. Ten se snažil zobecnit možnosti lineární interpolace popsané v předchozí kapitole. Ta je založena, jak již víme, na použití dvou polynomů prvního stupně:
f(t) = (1-t)
g(t) = t
Bézier si uvědomil, že (triviálně) platí:
f(t) + g(t) = 1
(1-t) + t = 1
tedy že součet obou funkcí pro libovolné t v daném rozsahu 0 až 1 je vždy roven jedné.
Dále Bézier umocnil obě strany předchozí rovnice:
((1-t) + t)2 = 12
Po úpravě tedy:
(1-t)2 + 2t(1-t) + t2 = 1
Výsledkem jsou tedy nám již známé bázové polynomy křivky druhého stupně (Bézierovy kvadriky):
(1-t)2
2t(1-t)
t2
Což přesně odpovídá vzorcům použitým v demonstračním příkladu uvedeného v úvodní kapitole.
4. Binomická věta a Bernsteinovy polynomy
Naprosto stejným způsobem, tedy umocněním (na třetí, čtvrtou atd.), lze odvodit bázové polynomy i pro Bézierovy křivky vyšších stupňů, tedy především pro Bézierovu kubiku. Ovšem ve skutečnosti si můžeme pomoci jednoduchou zkratkou – binomickou větou, díky níž dokážeme jednoduše spočítat ((1-t) + t)n. Jednotlivé členy rozvoje se nazývají Bernsteinovy bázové polynomy. Každý takový polynom má tvar:
bv,n(t) = Cvn tv (1-t)n-v
kde Cvn je binomický koeficient „n nad v“. Tento koeficient lze získat z Pascalova trojúhelníku:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Uveďme si příklady Bernsteinových bázových polynomů.
Lineární případ n=1 je triviální (druhý řádek v trojúhelníku):
1 × (1-t)
1 × t
Bázové polynomy druhého stupně pro n=2 (třetí řádek v trojúhelníku):
1 × (1-t)2
2 × t × (1-t)
1 × t2
Bázové polynomy třetího stupně pro n=3:
1 × (1-t)3
3 × t × (1-t)2
3 × t2 × (1-t)
1 × t3
atd. atd.
5. Bernsteinovy polynomy stupně jedna až pět
Nyní již víme, jakým způsobem je možné vypočítat Bernsteinovy bázové polynomy libovolného stupně. Ukažme si tedy jejich průběh graficky. Začneme (prakticky triviálním) lineárním případem:
"""Bázové polynomy pro lineární interpolaci."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.02)
# Bernsteinovy polynomy pro lineární interpolaci
B = [1 * (1-t),
1 * t]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bázové polynomy', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
# bázové polynomy
ax.plot(t, B[0], 'r-', label='b0,1')
ax.plot(t, B[1], 'g-', label='b1,1')
# zobrazení legendy
ax.legend()
# uložení grafu do rastrového obrázku
plt.savefig("linear_basis.png")
# zobrazení grafu
plt.show()
S výsledkem:
Obrázek 4: Bernsteinovy bázové polynomy stupně jedna.
Bernsteinovy bázové polynomy stupně dva použité pro Bézierovy kvadriky:
"""Bázové polynomy Bézierovy kvadriky."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.02)
# Bernsteinovy polynomy pro Bézierovu kvadriku
B = [1 * (1-t)**2,
2 * t * (1-t),
1 * t**2]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bázové polynomy', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
# bázové polynomy
ax.plot(t, B[0], 'r-', label='b0,2')
ax.plot(t, B[1], 'g-', label='b1,2')
ax.plot(t, B[2], 'b-', label='b2,2')
# zobrazení legendy
ax.legend()
# uložení grafu do rastrového obrázku
plt.savefig("bezier_quadric_basis_.png")
# zobrazení grafu
plt.show()
S výsledkem:
Obrázek 5: Bernsteinovy bázové polynomy stupně dva.
Bernsteinovy bázové polynomy stupně tři použité pro Bézierovy kubiky:
"""Bázové polynomy Bézierovy kubiky."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.02)
# Bernsteinovy polynomy
B = [1 * (1-t)**3,
3 * t * (1-t)**2,
3 * t**2 * (1-t),
1 * t**3]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bázové polynomy', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
# bázové polynomy
ax.plot(t, B[0], 'r-', label='b0,3')
ax.plot(t, B[1], 'g-', label='b1,3')
ax.plot(t, B[2], 'b-', label='b2,3')
ax.plot(t, B[3], 'k-', label='b3,3')
# zobrazení legendy
ax.legend()
# uložení grafu do rastrového obrázku
plt.savefig("bezier_cubic_basis.png")
# zobrazení grafu
plt.show()
Obrázek 6: Bernsteinovy bázové polynomy stupně tři.
Ovšem můžeme jít i dále a zobrazit si polynomy stupně čtyři:
"""Bázové polynomy Bézierovy kvartiky."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.02)
# Bernsteinovy polynomy pro Bézierovu kvartiku
B = [1 * (1-t)**4,
4 * t * (1-t)**3,
6 * t**2 * (1-t)**2,
4 * t**3 * (1-t),
1 * t**4]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bázové polynomy', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
# bázové polynomy
ax.plot(t, B[0], 'r-', label='b0,4')
ax.plot(t, B[1], 'g-', label='b1,4')
ax.plot(t, B[2], 'b-', label='b2,4')
ax.plot(t, B[3], 'k-', label='b3,4')
ax.plot(t, B[4], 'm-', label='b4,4')
# zobrazení legendy
ax.legend()
# uložení grafu do rastrového obrázku
plt.savefig("bezier_quartic_basis_.png")
# zobrazení grafu
plt.show()
Obrázek 7: Bernsteinovy bázové polynomy stupně čtyři.
Pro úplnost bázové polynomy stupně pět, i když ty již v grafice většinou neuvidíme:
"""Bázové polynomy Bézierovy křivky stupně 5."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.02)
# Bernsteinovy polynomy pro Bézierovu křivku stupně 5
B = [1 * (1-t)**5,
5 * t * (1-t)**4,
10 * t**2 * (1-t)**3,
10 * t**3 * (1-t)**2,
5 * t**4 * (1-t),
1 * t**5]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bázové polynomy', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 1)
ax.set_ylim(0, 1)
# bázové polynomy
ax.plot(t, B[0], 'r-', label='b0,5')
ax.plot(t, B[1], 'g-', label='b1,5')
ax.plot(t, B[2], 'b-', label='b2,5')
ax.plot(t, B[3], 'k-', label='b3,5')
ax.plot(t, B[4], 'm-', label='b4,5')
ax.plot(t, B[5], 'y-', label='b5,5')
# zobrazení legendy
ax.legend()
# uložení grafu do rastrového obrázku
plt.savefig("bezier_quintic_basis_.png")
# zobrazení grafu
plt.show()
Obrázek 8: Bernsteinovy bázové polynomy stupně pět.
6. Ověření základních vlastností Bernsteinových polynomů
Bernsteinovy polynomy, které jsou využity jako bázové polynomy Bézierových křivek, splňují několik podmínek, které jsou při tvorbě křivek a jejich využívání důležité. Jedná se o tyto podmínky:
- Pro t=0 má první polynom hodnotu 1 a ostatní polynomy hodnotu 0. Z geometrického hlediska to znamená, že je zaručeno, že křivka prochází prvním koncovým bodem (protože ostatní členy při výpočtu jsou vynulovány).
- Podobně pro t=1 mají všechny polynomy, až na polynom poslední, nulovou hodnotu. Tudíž křivka prochází i svým posledním koncovým bodem.
- Součet hodnot všech Bernsteinových polynomů pro libovolnét v rozsahu od 0 do 1 je vždy roven jedné, současně je hodnota každého Bernsteinova polynomu vždy nezáporná. Z geometrického hlediska to znamená, že se celá křivka nachází v konvexním obalu svých řídicích bodů (tedy v mnohoúhelníku, který získáme propojením řídicích bodů tak, že je mnohoúhelník konvexní).
- Současně můžeme z grafů zobrazených v předchozí kapitole zjistit, jak hodnoty Bernsteinových polynomů postupně (podle jejich indexu) rostou se změnou t a posléze zase klesají k nule. Výjimkou je první a poslední polynom, který jen klesá, resp. jen roste. Geometricky to znamená, že křivka se postupně přibližuje k jednotlivým řídicím bodům.
7. Součet všech Bernsteinových polynomů stupně jedna až pět
Základní a pro mnoho aplikací důležitá vlastnost Bernsteinových polynomů – jejich součet je pro libovolné t z definičního oboru vždy roven jedné – sice nemusí být z grafů přímo patrná, ale můžeme si ji ověřit numericky, a to pro polynomy různého stupně. V tabulkách, které jsou vypočteny a zobrazeny dále uvedenými demonstračními příklady, by měly hodnoty v posledních sloupcích být vždy jedničkové nebo alespoň v rámci přesnosti výpočtů velmi blízké jedničce.
Polynom prvního stupně:
"""Bázové polynomy lineární interpolace."""
import numpy as np
import pandas as pd
from tabulate import tabulate
# hodnoty parametru t
t = np.arange(0, 1.01, 0.10)
# Bernsteinovy polynomy pro lineární interpolaci
B = [1 * (1-t),
1 * t]
# vytvoření datového rámce pro uložení hodnot Bernsteinových polynomů
df = pd.DataFrame(index=t, columns=["b0,1", "b1,1", "sum"])
# inicializace jednotlivých sloupců datového rámce
df["b0,1"] = B[0]
df["b1,1"] = B[1]
# součet hodnot Bernsteinových polynomů
df["sum"] = B[0]+B[1]
# vytištění obsahu datového rámce
print(tabulate(df, headers = 'keys', tablefmt = 'psql'))
Výsledky:
+-----+--------+--------+-------+ | | b0,1 | b1,1 | sum | |-----+--------+--------+-------| | 0 | 1 | 0 | 1 | | 0.1 | 0.9 | 0.1 | 1 | | 0.2 | 0.8 | 0.2 | 1 | | 0.3 | 0.7 | 0.3 | 1 | | 0.4 | 0.6 | 0.4 | 1 | | 0.5 | 0.5 | 0.5 | 1 | | 0.6 | 0.4 | 0.6 | 1 | | 0.7 | 0.3 | 0.7 | 1 | | 0.8 | 0.2 | 0.8 | 1 | | 0.9 | 0.1 | 0.9 | 1 | | 1 | 0 | 1 | 1 | +-----+--------+--------+-------+
Polynom druhého stupně:
"""Bázové polynomy Bézierovy kvadriky."""
import numpy as np
import pandas as pd
from tabulate import tabulate
# hodnoty parametru t
t = np.arange(0, 1.01, 0.10)
# Bernsteinovy polynomy pro Bézierovu kvadriku
B = [1 * (1-t)**2,
2 * t * (1-t),
1 * t**2]
# vytvoření datového rámce pro uložení hodnot Bernsteinových polynomů
df = pd.DataFrame(index=t, columns=["b0,2", "b1,2", "b2,2", "sum"])
# inicializace jednotlivých sloupců datového rámce
df["b0,2"] = B[0]
df["b1,2"] = B[1]
df["b2,2"] = B[2]
# součet hodnot Bernsteinových polynomů
df["sum"] = B[0]+B[1]+B[2]
# vytištění obsahu datového rámce
print(tabulate(df, headers = 'keys', tablefmt = 'psql'))
Výsledky:
+-----+--------+--------+--------+-------+ | | b0,2 | b1,2 | b2,2 | sum | |-----+--------+--------+--------+-------| | 0 | 1 | 0 | 0 | 1 | | 0.1 | 0.81 | 0.18 | 0.01 | 1 | | 0.2 | 0.64 | 0.32 | 0.04 | 1 | | 0.3 | 0.49 | 0.42 | 0.09 | 1 | | 0.4 | 0.36 | 0.48 | 0.16 | 1 | | 0.5 | 0.25 | 0.5 | 0.25 | 1 | | 0.6 | 0.16 | 0.48 | 0.36 | 1 | | 0.7 | 0.09 | 0.42 | 0.49 | 1 | | 0.8 | 0.04 | 0.32 | 0.64 | 1 | | 0.9 | 0.01 | 0.18 | 0.81 | 1 | | 1 | 0 | 0 | 1 | 1 | +-----+--------+--------+--------+-------+
Polynom třetího stupně:
"""Bázové polynomy Bézierovy kubiky."""
import numpy as np
import pandas as pd
from tabulate import tabulate
# hodnoty parametru t
t = np.arange(0, 1.01, 0.10)
# Bernsteinovy polynomy pro Bézierovu kubiku
B = [1 * (1-t)**3,
3 * t * (1-t)**2,
3 * t**2 * (1-t),
1 * t**3]
# vytvoření datového rámce pro uložení hodnot Bernsteinových polynomů
df = pd.DataFrame(index=t, columns=["b0,3", "b1,3", "b2,3", "b3,3", "sum"])
# inicializace jednotlivých sloupců datového rámce
df["b0,3"] = B[0]
df["b1,3"] = B[1]
df["b2,3"] = B[2]
df["b3,3"] = B[3]
# součet hodnot Bernsteinových polynomů
df["sum"] = B[0]+B[1]+B[2]+B[3]
# vytištění obsahu datového rámce
print(tabulate(df, headers = 'keys', tablefmt = 'psql'))
Výsledky:
+-----+--------+--------+--------+--------+-------+ | | b0,3 | b1,3 | b2,3 | b3,3 | sum | |-----+--------+--------+--------+--------+-------| | 0 | 1 | 0 | 0 | 0 | 1 | | 0.1 | 0.729 | 0.243 | 0.027 | 0.001 | 1 | | 0.2 | 0.512 | 0.384 | 0.096 | 0.008 | 1 | | 0.3 | 0.343 | 0.441 | 0.189 | 0.027 | 1 | | 0.4 | 0.216 | 0.432 | 0.288 | 0.064 | 1 | | 0.5 | 0.125 | 0.375 | 0.375 | 0.125 | 1 | | 0.6 | 0.064 | 0.288 | 0.432 | 0.216 | 1 | | 0.7 | 0.027 | 0.189 | 0.441 | 0.343 | 1 | | 0.8 | 0.008 | 0.096 | 0.384 | 0.512 | 1 | | 0.9 | 0.001 | 0.027 | 0.243 | 0.729 | 1 | | 1 | 0 | 0 | 0 | 1 | 1 | +-----+--------+--------+--------+--------+-------+
Polynom čtvrtého stupně:
"""Bázové polynomy Bézierovy kvartiky."""
import numpy as np
import pandas as pd
from tabulate import tabulate
# hodnoty parametru t
t = np.arange(0, 1.01, 0.10)
# Bernsteinovy polynomy pro Bézierovu kvartiku
B = [1 * (1-t)**4,
4 * t * (1-t)**3,
6 * t**2 * (1-t)**2,
4 * t**3 * (1-t),
1 * t**4]
# vytvoření datového rámce pro uložení hodnot Bernsteinových polynomů
df = pd.DataFrame(index=t, columns=["b0,4", "b1,4", "b2,4", "b3,4", "b4,4", "sum"])
# inicializace jednotlivých sloupců datového rámce
df["b0,4"] = B[0]
df["b1,4"] = B[1]
df["b2,4"] = B[2]
df["b3,4"] = B[3]
df["b4,4"] = B[4]
# součet hodnot Bernsteinových polynomů
df["sum"] = B[0]+B[1]+B[2]+B[3]+B[4]
# vytištění obsahu datového rámce
print(tabulate(df, headers = 'keys', tablefmt = 'psql'))
Výsledky:
+-----+--------+--------+--------+--------+--------+-------+ | | b0,4 | b1,4 | b2,4 | b3,4 | b4,4 | sum | |-----+--------+--------+--------+--------+--------+-------| | 0 | 1 | 0 | 0 | 0 | 0 | 1 | | 0.1 | 0.6561 | 0.2916 | 0.0486 | 0.0036 | 0.0001 | 1 | | 0.2 | 0.4096 | 0.4096 | 0.1536 | 0.0256 | 0.0016 | 1 | | 0.3 | 0.2401 | 0.4116 | 0.2646 | 0.0756 | 0.0081 | 1 | | 0.4 | 0.1296 | 0.3456 | 0.3456 | 0.1536 | 0.0256 | 1 | | 0.5 | 0.0625 | 0.25 | 0.375 | 0.25 | 0.0625 | 1 | | 0.6 | 0.0256 | 0.1536 | 0.3456 | 0.3456 | 0.1296 | 1 | | 0.7 | 0.0081 | 0.0756 | 0.2646 | 0.4116 | 0.2401 | 1 | | 0.8 | 0.0016 | 0.0256 | 0.1536 | 0.4096 | 0.4096 | 1 | | 0.9 | 0.0001 | 0.0036 | 0.0486 | 0.2916 | 0.6561 | 1 | | 1 | 0 | 0 | 0 | 0 | 1 | 1 | +-----+--------+--------+--------+--------+--------+-------+
A konečně polynom pátého stupně:
"""Bázové polynomy Bézierovy křivky stupně 5."""
import numpy as np
import pandas as pd
from tabulate import tabulate
# hodnoty parametru t
t = np.arange(0, 1.01, 0.10)
# Bernsteinovy polynomy pro Bézierovu křivku stupně 5
B = [1 * (1-t)**5,
5 * t * (1-t)**4,
10 * t**2 * (1-t)**3,
10 * t**3 * (1-t)**2,
5 * t**4 * (1-t),
1 * t**5]
# vytvoření datového rámce pro uložení hodnot Bernsteinových polynomů
df = pd.DataFrame(index=t, columns=["b0,5", "b1,5", "b2,5", "b3,5", "b4,5", "b5,5", "sum"])
# inicializace jednotlivých sloupců datového rámce
df["b0,5"] = B[0]
df["b1,5"] = B[1]
df["b2,5"] = B[2]
df["b3,5"] = B[3]
df["b4,5"] = B[4]
df["b5,5"] = B[5]
# součet hodnot Bernsteinových polynomů
df["sum"] = B[0]+B[1]+B[2]+B[3]+B[4]+B[5]
# vytištění obsahu datového rámce
print(tabulate(df, headers = 'keys', tablefmt = 'psql'))
Výsledky:
+-----+---------+---------+--------+--------+---------+---------+-------+ | | b0,5 | b1,5 | b2,5 | b3,5 | b4,5 | b5,5 | sum | |-----+---------+---------+--------+--------+---------+---------+-------| | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | | 0.1 | 0.59049 | 0.32805 | 0.0729 | 0.0081 | 0.00045 | 1e-05 | 1 | | 0.2 | 0.32768 | 0.4096 | 0.2048 | 0.0512 | 0.0064 | 0.00032 | 1 | | 0.3 | 0.16807 | 0.36015 | 0.3087 | 0.1323 | 0.02835 | 0.00243 | 1 | | 0.4 | 0.07776 | 0.2592 | 0.3456 | 0.2304 | 0.0768 | 0.01024 | 1 | | 0.5 | 0.03125 | 0.15625 | 0.3125 | 0.3125 | 0.15625 | 0.03125 | 1 | | 0.6 | 0.01024 | 0.0768 | 0.2304 | 0.3456 | 0.2592 | 0.07776 | 1 | | 0.7 | 0.00243 | 0.02835 | 0.1323 | 0.3087 | 0.36015 | 0.16807 | 1 | | 0.8 | 0.00032 | 0.0064 | 0.0512 | 0.2048 | 0.4096 | 0.32768 | 1 | | 0.9 | 1e-05 | 0.00045 | 0.0081 | 0.0729 | 0.32805 | 0.59049 | 1 | | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | +-----+---------+---------+--------+--------+---------+---------+-------+
8. Jak je tomu v případě Coonsových kubik?
V předchozím článku jsme se mj. seznámili i s takzvanými Coonsovými kubikami, resp. s Coonsovými oblouky (Coons arc), které tvoří základ klasických (neracionálních uniformních) B-spline křivek. Tyto kubiky se počítají a vykreslují naprosto stejným způsobem jako kubiky Bézierovy, až na jednu „maličkost“ – jejich bázové polynomy jsou odlišné od Bernsteinovým polynomů. To má za následek nejenom odlišný tvar křivky, ale i to, že B-spline neprochází svými koncovými body. Tuto vlastnost můžeme vyčíst z grafu průběhu hodnot bázových polynomů, protože zde není splněna podmínka, že pro t=0 má první polynom hodnotu 1 a ostatní polynomy hodnotu 0 a pro t=1 mají všechny polynomy, až na polynom poslední, hodnotu nulovou. Křivka tedy začíná i končí v bodech, jejichž souřadnice jsou ovlivněny dalšími řídicími body:
Obrázek 9: Bázové polynomy Coonsovy kubiky.
Průběhy jsou tedy dosti odlišné od Bernsteinových polynomů, které jsme mohli vidět v předchozích kapitolách.
Předchozí graf byl vykreslen tímto skriptem:
"""Bázové polynomy Coonsovy kubiky."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.02)
# Coonsovy polynomy
C = [(1-t)**3,
3*t**3 - 6*t**2 + 4,
-3*t**3 + 3*t**2 + 3*t + 1,
t**3]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bázové polynomy', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 1)
ax.set_ylim(0, 4)
# bázové polynomy
ax.plot(t, C[0]/6, 'r-')
ax.plot(t, C[1]/6, 'g-')
ax.plot(t, C[2]/6, 'b-')
ax.plot(t, C[3]/6, 'k-')
# uložení grafu do rastrového obrázku
plt.savefig("coons_basis.png")
# zobrazení grafu
plt.show()
9. Konstrukce křivky z několika na sebe navazujících segmentů
Prozatím jsme se zabývali (a nutno dodat, že i nadále budeme zabývat) parametrickými křivkami vytvořenými postupně z několika na sebe navazujících segmentů, přičemž každý segment je popsán polynomem nízkého stupně (typicky stupně tři nebo čtyři, jedná se tedy o kvadriku nebo kubiku). Velmi důležité body v takovém případě vznikají v místě napojení jednotlivých segmentů. Samozřejmě je možné segmenty napojit libovolným způsobem (takže vznikne „roh“ nebo dokonce mezera mezi segmenty), ale většinou je požadováno hladké napojení. Přitom slovo „hladké“ má podle kontextu matematický nebo geometrický význam. Rozlišujeme parametrickou spojitost třídy Cn a taktéž geometrickou spojitost Gn. Různé aplikace, v nichž se křivky používají, přitom mají různé požadavky, takže například nelze říci, že nám všude budou vyhovovat pouze křivky se spojitostí G1. A naopak použití křivek se spojitostí C2 může být naopak značně limitující.
10. Parametrická a geometrická spojitost Cn a Gn
Dva segmenty jsou spojitě navázány (neboli mají spojitost třídy C0) v případě, že je koncový bod prvního segmentu počátečním bodem segmentu druhého – tudíž jsou dovoleny i výše zmíněné „rohy“. Dva segmenty mají spojitost C1 v případě, že je tečný vektor v koncovém bodě segmentu Q1, roven tečnému vektoru v jeho počátečním bodě navazujícího segmentu Q2. Analogicky rovnost vektoru první a druhé derivace je požadována pro spojité navázání třídy C2. Teoreticky je možné požadovat popř. i zajistit totožnost třetí i vyšší derivace, ovšem konkrétně u polynomů nižších stupňů to již postrádá praktický význam (derivace budou nulové).
Čím vyšší spojitost je požadována, tím delší „dobu“ (ve smyslu parametru t) se oba segmenty k sobě přimykají a tím pádem je křivka tužší při snaze o změnu jejího tvaru. Ze spojitosti C0 dále plyne, že bod se pohybuje po spojité dráze, ale v uzlu může měnit skokem směr pohybu, rychlost i zrychlení, což může vadit při animacích. Směr pohybu se nemůže měnit skokem při spojitosti C1 (ovšem může se skokově změnit rychlost) a zrychlení zůstává nezměněné až při spojitosti C2 (což je ideální právě pro animační křivky).
V počítačové grafice se mnohdy setkáme spíše s termínem geometrické spojitosti Gn. Opticky zaručuje G1 spojitost dvou segmentů křivky s prakticky stejnou vizuální hladkostí, jako je tomu u parametrické spojitosti C1. Důležitá je ovšem praktická implementace, tj. programový kód, který spojitost G1 nebo C1 zajišťuje. Z tohoto hlediska bývá daleko snazší zaručit spojitost G1 (dtto při požadavku na spojitost G2 resp. C2), protože případné tečné vektory nemusí být totožné, ale „pouze“ musí mít stejný směr, nikoli už velikost (jsou tedy kolineární).
Jak již bylo napsáno v předchozím odstavci, je jednodušší dosažení geometrické spojitosti G1, kde je nutné, mimo totožnosti posledního řídicího bodu první křivky a prvního bodu druhé křivky, dodržet alespoň kolinearitu tečného vektoru na konci první křivky a na začátku křivky druhé (vektory tedy musí mít stejný směr, ale mohou mít různou velikost, jinými slovy, tyto vektory jsou na sobě lineárně závislé). Geometrickou spojitost je snazší dodržet i z toho důvodu, že volnost uživatele při zadávání řídicích bodů je větší než v případě parametrické spojitosti, zejména při použití Bézierových kvadratických a (méně kriticky) kubických křivek – viz následující kapitolu.
11. Zajištění spojitosti C1 nebo G1 u Bézierových křivek
Podívejme se nyní, jak je tomu v případě Bézierových křivek. Pokud na sebe mají jednotlivé segmenty křivky hladce navazovat, tj. pokud mají mít parametrickou spojitost alespoň C1, musí být poslední bod první křivky totožný s prvním bodem křivky druhé: Pn=P'0 – tím je zajištěno napojení obou křivek, tj. spojitost C0. Také tečný vektor na konci první křivky musí být stejný jako tečný vektor na začátku druhé (navazující) křivky. Na dalším obrázku jsou zobrazeny dvě Bézierovy kvadratické křivky, které jsou hladce navázány se spojitostí C1. Vzhledem k tomu, že se jedná o kvadratické křivky, je každá křivka specifikována počátečním bodem, jedním řídicím bodem a koncovým bodem. Podobným způsobem jsou konstruovány obrysy písmen v TrueType fontech.
Obrázek 10: Hladké navázání dvou Bézierových kvadratických křivek.
12. Poznámka k Coonsovým kubikám a uniformním racionálním B-spline křivkám
Minule jsme se zmínili i o Coonsových kubikách, které se taktéž někdy nazývají Coonsovy oblouky. Tyto křivky začínají a končí v antitěžišti trojúhelníků vytvořených z trojice řídicích bodů – jedná se tedy o čisté aproximační křivky. Způsob vykreslení se až na rozdílné bázové polynomy neliší od Bézierových kubik:
"""Parametrická křivka: Coonsova kubika."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body Coonsovy kubiky
xc = (1, 1, 3, 3)
yc = (1, 2, 2, 0.5)
# Coonsovy polynomy
C = [(1-t)**3,
3*t**3 - 6*t**2 + 4,
-3*t**3 + 3*t**2 + 3*t + 1,
t**3]
# výpočet bodů ležících na Coonsově kubice
x = 0
y = 0
for i in range(0, 4):
x += xc[i]*C[i]
y += yc[i]*C[i]
# konečná úprava sumy
x /= 6
y /= 6
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Coonsova kubika', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 3)
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, 'g-')
# řídicí body Coonsovy kubiky
ax.plot(xc, yc, 'ro')
# uložení grafu do rastrového obrázku
plt.savefig("coons.png")
# zobrazení grafu
plt.show()
Obrázek 11: Coonsova kubika pro čtyři řídicí body.
Tyto kubiky lze snadno navázat takovým způsobem, že se vždy tři řídicí body opakují (resp. jsou společné pro dva na sebe navazující segmenty). Ovšem co je důležité – po vyjádření prvních a druhých derivací polynomů lze zjistit, že je zachována spojitost C2, a to bez jakýchkoli dalších podmínek:
"""Parametrická křivka: B-spline složená z Coonsových oblouků."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body B-spline
xc = (1, 1, 2, 2.5, 3, 2)
yc = (1, 2, 2, 0.1, 2.9, 2.9)
# Coonsovy polynomy
C = [(1-t)**3,
3*t**3 - 6*t**2 + 4,
-3*t**3 + 3*t**2 + 3*t + 1,
t**3]
def draw_coons_arc(xc, yc, ax, style):
# výpočet bodů ležících na Coonsově kubice
x = 0
y = 0
for i in range(0, 4):
x += xc[i]*C[i]
y += yc[i]*C[i]
# konečná úprava sumy
x /= 6
y /= 6
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, style)
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('B-spline', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 3)
# řídicí body B-spline
ax.plot(xc, yc, 'k--', alpha=0.5)
ax.plot(xc, yc, 'ro')
# první oblouk
draw_coons_arc(xc[0:4], yc[0:4], ax, "r-")
# druhý oblouk
draw_coons_arc(xc[1:5], yc[1:5], ax, "b-")
# třetí oblouk
draw_coons_arc(xc[2:6], yc[2:6], ax, "g-")
# uložení grafu do rastrového obrázku
plt.savefig("B-spline_1.png")
# zobrazení grafu
plt.show()
Obrázek 12: B-spline vytvořená z Coonsových oblouků.
13. Křivky používané v animacích
Konečně se dostáváme k další důležité oblasti počítačové grafiky, v níž jsou využívány parametrické křivky, konkrétně křivky definované s využitím polynomů nižších řádů. Jedná se o oblast animací, konkrétně animací založených na takzvaných klíčových snímcích neboli keyframes, mezi nimiž jsou automaticky dopočítány parametry mezisnímků, kterých může být libovolný počet (například třicet mezisnímků mezi každým klíčovým snímkem). Takový typ animací lze v případě potřeby vytvářet velmi precizním způsobem, protože pozice kamery a její orientaci, stejně jako další parametry vykreslované scény, je možné nastavit pomocí interaktivních metod a/nebo dialogů a poté pouze zvolit, jak se má dopočítat přechod mezi jednotlivými snímky.
14. Catmul-Romovy spline
Při vytváření a úpravách animací je vhodné vědět, jak vlastně interně pracuje algoritmus výpočtu mezisnímků, které jsou vkládány mezi jednotlivé klíčové snímky. Nejprve si musíme uvědomit, jak je interně celá animace reprezentována. Zjednodušeně řečeno se jedná o sadu neměnných parametrů a dále o sadu parametrů, které se v čase (tj. mezi jednotlivými snímky) mohou měnit (třeba pozice animované postavičky). Sadou neměnných parametrů se nemusíme dále zabývat, protože ty jsou pro všechny snímky shodné. U proměnných parametrů se většinou jedná o reálná čísla, ovšem v některých případech (pozice a orientace kamery) se taktéž může jednat o vektory různé délky. Tyto vektory se opět rozkládají na reálná čísla. Hodnoty všech parametrů jsou předem známé v jednotlivých klíčových snímcích, takže by se mohlo zdát, že postačuje mezihodnoty dopočítat tím nejprimitivnějším možným způsobem – lineární interpolací, kterou již velmi dobře známe.
To sice skutečně možné je, protože výsledkem bude animace, ve které nebude docházet ke skokové změně hodnot jednotlivých parametrů, ovšem bude docházet ke změně rychlosti změny hodnot (což je zrychlení). Výhodnější je tedy proložení hodnot nějakou vhodnou křivkou, která mj. zajistí, aby nedocházelo ani ke skokovému rozdílu v rychlosti změny parametrů (takzvaná parametrická spojitost C1, viz též předchozí kapitoly). V počítačové grafice, především právě při tvorbě animací (pohyb kamery), se k tomuto účelu používají křivky pojmenované podle svých tvůrců Edwina Catmulla a Raphaela Roma Catmull–Rom spline. Alternativní křivkou je Akima spline (Akimova spline křivka), která je opět pojmenovaná podle svého tvůrce (Hiroshi Akima).
Catmul-Romovy spline lze, podobně jako B-spline, vyjádřit sekvencí na sebe navazujících segmentů, přičemž každý segment je (opět) reprezentován kubikou. Ovšem zatímco B-spline jsou aproximačními křivkami, které neprochází svými řídicími body, Catmul-Romovy spline jsou interpolační křivky, tedy prochází všemi svými řídicími body. To je ostatně logické, protože řídicí body odpovídají hodnotám v klíčových snímcích a tyto snímky potřebujeme v animaci zobrazit přesně tak, jak je grafik vytvořil. Ovšem současně to – při požadavku na parametrickou spojitost – znamená, že tyto křivky obecně neleží v konvexním obalu vytvořeného z řídicích bodů, což může v některých případech způsobovat problémy.
15. Bázové polynomy Catmul-Romovy spline
Podívejme se nyní na to, jak vypadají bázové polynomy Catmul-Romovy spline. Vizualizaci provedeme tímto skriptem, ze kterého je patrné, jaké bázové polynomy jsou použity:
"""Bázové polynomy Catmul-Romovy spline."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.02)
# koeficient Catmul-Romovy spline
tau = 0.5
# bázové polynomy
Q = [-tau*t + 2*tau*t**2 - tau*t**3,
1+(tau-3)*t**2+(2-tau)*t**3,
tau*t + (3-2*tau)*t**2 + (tau-2)*t**3,
-tau*t**2+tau*t**3]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Bázové polynomy', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 1)
ax.set_ylim(-0.25, 1)
# bázové polynomy
ax.plot(t, Q[0], 'r-')
ax.plot(t, Q[1], 'g-')
ax.plot(t, Q[2], 'b-')
ax.plot(t, Q[3], 'k-')
# uložení grafu do rastrového obrázku
plt.savefig("catmul-rom_basis.png")
# zobrazení grafu
plt.show()
Výsledek:
Obrázek 13: Bázové polynomy Catmul-Romovy spline.
Vyjádřit můžeme i součet hodnot všech bázových polynomů:
"""Bázové polynomy Catmul-Romovy spline."""
import numpy as np
import pandas as pd
from tabulate import tabulate
# hodnoty parametru t
t = np.arange(0, 1.01, 0.10)
# koeficient Catmul-Romovy spline
tau = 0.5
# bázové polynomy
Q = [-tau*t + 2*tau*t**2 - tau*t**3,
1+(tau-3)*t**2+(2-tau)*t**3,
tau*t + (3-2*tau)*t**2 + (tau-2)*t**3,
-tau*t**2+tau*t**3]
# vytvoření datového rámce pro uložení hodnot polynomů
df = pd.DataFrame(index=t, columns=["q0", "q1", "q2", "q3", "sum"])
# inicializace jednotlivých sloupců datového rámce
df["q0"] = Q[0]
df["q1"] = Q[1]
df["q2"] = Q[2]
df["q3"] = Q[3]
# součet hodnot polynomů
df["sum"] = Q[0]+Q[1]+Q[2]+Q[3]
# vytištění obsahu datového rámce
print(tabulate(df, headers = 'keys', tablefmt = 'psql'))
Součet hodnot všech polynomů v daném místě je roven jedné, ovšem některé hodnoty konkrétních polynomů jsou záporné:
+-----+---------+--------+--------+---------+-------+ | | q0 | q1 | q2 | q3 | sum | |-----+---------+--------+--------+---------+-------| | 0 | 0 | 1 | 0 | 0 | 1 | | 0.1 | -0.0405 | 0.9765 | 0.0685 | -0.0045 | 1 | | 0.2 | -0.064 | 0.912 | 0.168 | -0.016 | 1 | | 0.3 | -0.0735 | 0.8155 | 0.2895 | -0.0315 | 1 | | 0.4 | -0.072 | 0.696 | 0.424 | -0.048 | 1 | | 0.5 | -0.0625 | 0.5625 | 0.5625 | -0.0625 | 1 | | 0.6 | -0.048 | 0.424 | 0.696 | -0.072 | 1 | | 0.7 | -0.0315 | 0.2895 | 0.8155 | -0.0735 | 1 | | 0.8 | -0.016 | 0.168 | 0.912 | -0.064 | 1 | | 0.9 | -0.0045 | 0.0685 | 0.9765 | -0.0405 | 1 | | 1 | 0 | 0 | 1 | 0 | 1 | +-----+---------+--------+--------+---------+-------+
16. Výpočet a vykreslení jednoho segmentu Catmul-Romovy spline
Jeden segment Catmul-Romovy spline se vykresluje stejně, jako segment Bézierovy křivky nebo Coonsova oblouku. Liší se pouze výpočet bodů na křivce na základě bázových polynomů:
"""Parametrická křivka: Catmul-Romova spline."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body
xc = (1, 1, 3, 3)
yc = (1, 2.9, 0.1, 2)
# koeficient Catmul-Romovy spline
tau = 0.5
# bázové polynomy
Q = [-tau*t + 2*tau*t**2 - tau*t**3,
1+(tau-3)*t**2+(2-tau)*t**3,
tau*t + (3-2*tau)*t**2 + (tau-2)*t**3,
-tau*t**2+tau*t**3]
# výpočet bodů ležících na spline
x = 0
y = 0
for i in range(0, 4):
x += xc[i]*Q[i]
y += yc[i]*Q[i]
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Catmul-Romova spline', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 3)
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, 'g-')
# řídicí body kubiky
ax.plot(xc, yc, 'ro')
# uložení grafu do rastrového obrázku
plt.savefig("catmul-rom_cubic.png")
# zobrazení grafu
plt.show()
Obrázek 14: Catmul-Romova spline složená z jednoho segmentu.
17. Vykreslení celé spline složené z většího množství segmentů
Z na sebe navazujících segmentů Catmul-Romovy kubiky lze vytvořit celou spline definovanou n řídicími body. Postup je snadný – vždy čtyři po sobě jdoucí body vytváří jeden segment; celkově je nutné vykreslit n-3 takových oblouků. Přitom je zaručeno, že tyto oblouky na sebe hladce navazují, což je ostatně ukázáno i v dalším (dnes již předposledním posledním) demonstračním příkladu:
"""Parametrická křivka: Catmul-Romova spline."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body B-spline
xc = (1, 1, 2, 2.5, 3, 2)
yc = (1, 2, 2, 0.1, 2.9, 2.9)
# koeficient Catmul-Romovy spline
tau = 0.5
# bázové polynomy
Q = [-tau*t + 2*tau*t**2 - tau*t**3,
1+(tau-3)*t**2+(2-tau)*t**3,
tau*t + (3-2*tau)*t**2 + (tau-2)*t**3,
-tau*t**2+tau*t**3]
def draw_catmul_rom_arc(xc, yc, ax, style):
x = 0
y = 0
for i in range(0, 4):
x += xc[i]*Q[i]
y += yc[i]*Q[i]
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, style)
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Catmul-Rom spline', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 4)
# řídicí body B-spline
ax.plot(xc, yc, 'k--', alpha=0.5)
ax.plot(xc, yc, 'ro')
# první oblouk
draw_catmul_rom_arc(xc[0:4], yc[0:4], ax, "r-")
# druhý oblouk
draw_catmul_rom_arc(xc[1:5], yc[1:5], ax, "b-")
# třetí oblouk
draw_catmul_rom_arc(xc[2:6], yc[2:6], ax, "g-")
# uložení grafu do rastrového obrázku
plt.savefig("catmul-rom_spline_A.png")
# zobrazení grafu
plt.show()
Obrázek 15: Catmul-Romova spline složená z několika segmentů.
18. Násobné koncové body Catmul-Romovy spline
Při práci s Catmul-Rom spline se, podobně jako u B-spline, často používají takzvané násobné řídící body, což jsou sousední řídící body, které jsou umístěny na stejné souřadnici v ploše či v prostoru. S využitím násobných řídících bodů lze na křivce vytvářet zlomy či úseky, které se k řídícím bodům více přimykají (tím se částečně nahrazují váhy řídících bodů). Také lze zajistit (což je důležitější), aby křivka procházela svými krajními body:
"""Parametrická křivka: Catmul-Romova spline s násobnými body."""
import numpy as np
import matplotlib.pyplot as plt
# hodnoty parametru t
t = np.arange(0, 1.05, 0.05)
# řídicí body B-spline
xc = (1, 1, 2, 2.5, 3, 2)
yc = (1, 2, 2, 0.1, 2.9, 2.9)
# koeficient Catmul-Romovy spline
tau = 0.5
# bázové polynomy
Q = [-tau*t + 2*tau*t**2 - tau*t**3,
1+(tau-3)*t**2+(2-tau)*t**3,
tau*t + (3-2*tau)*t**2 + (tau-2)*t**3,
-tau*t**2+tau*t**3]
def draw_catmul_rom_arc(xc, yc, ax, style):
x = 0
y = 0
for i in range(0, 4):
x += xc[i]*Q[i]
y += yc[i]*Q[i]
# vrcholy na křivce pospojované úsečkami
ax.plot(x, y, style)
# rozměry grafu při uložení: 640x480 pixelů
fig, ax = plt.subplots(1, figsize=(6.4, 4.8))
# titulek grafu
fig.suptitle('Catmul-Rom spline', fontsize=15)
# určení rozsahů na obou souřadných osách
ax.set_xlim(0, 4)
ax.set_ylim(0, 4)
# řídicí body B-spline
ax.plot(xc, yc, 'k--', alpha=0.5)
ax.plot(xc, yc, 'ro')
# oblouk s násobnými body
draw_catmul_rom_arc((xc[0], xc[0], xc[1], xc[2]),
(yc[0], yc[0], yc[1], yc[2]), ax, "k-")
# první oblouk
draw_catmul_rom_arc(xc[0:4], yc[0:4], ax, "r-")
# druhý oblouk
draw_catmul_rom_arc(xc[1:5], yc[1:5], ax, "b-")
# třetí oblouk
draw_catmul_rom_arc(xc[2:6], yc[2:6], ax, "g-")
# oblouk s násobnými body
draw_catmul_rom_arc((xc[3], xc[4], xc[5], xc[5]),
(yc[3], yc[4], yc[5], yc[5]), ax, "k-")
# uložení grafu do rastrového obrázku
plt.savefig("catmul-rom_spline_B.png")
# zobrazení grafu
plt.show()
Obrázek 16: Catmul-Romova spline složená z několika segmentů, která prochází svými krajními body.
19. Repositář s demonstračními příklady
Všechny předminule, minule i dnes popisované demonstrační příklady určené pro Python 3 a knihovnu Matplotlib byly uloženy do Git repositáře, který je dostupný na adrese https://github.com/tisnik/presentations. Příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý (dnes již poměrně rozsáhlý) repositář:
20. Odkazy na Internetu
- Famous Curves Index
https://mathshistory.st-andrews.ac.uk/Curves/ - Curve (Wikipedia)
https://en.wikipedia.org/wiki/Curve - Mathematical curves
https://www.2dcurves.com/index.html - Curves (Wolfram MathWorld)
https://mathworld.wolfram.com/topics/Curves.html - Smooth Curve (Wolfram MathWorld)
https://mathworld.wolfram.com/SmoothCurve.html - Spirals (Wolfram MathWorld)
https://mathworld.wolfram.com/topics/Spirals.html - An Interactive Introduction to Splines
https://ibiblio.org/e-notes/Splines/Intro.htm - Parabola
https://www.2dcurves.com/conicsection/conicsectionp.html - Hyperbola
https://www.2dcurves.com/conicsection/conicsectionh.html - Dioklova kisoida
https://cs.wikipedia.org/wiki/Dioklova_kisoida - Archimédova spirála
https://cs.wikipedia.org/wiki/Archim%C3%A9dova_spir%C3%A1la - Conchoid (mathematics)
https://en.wikipedia.org/wiki/Conchoid_(mathematics) - Algebraic curve
https://en.wikipedia.org/wiki/Algebraic_curve - Transcendental curve
https://en.wikipedia.org/wiki/Transcendental_curve - Spiral
https://en.wikipedia.org/wiki/Spiral - List of spirals
https://en.wikipedia.org/wiki/List_of_spirals - Hyperbolická spirála
https://cs.wikipedia.org/wiki/Hyperbolick%C3%A1_spir%C3%A1la - Hyperbolic Spiral
https://mathworld.wolfram.com/HyperbolicSpiral.html - Lituus (mathematics)
https://en.wikipedia.org/wiki/Lituus_(mathematics) - Spiral of Spirals Fractals 2 with Python Turtle (Source Code)
https://pythonturtle.academy/spiral-of-spirals-fractals-2-with-python-turtle-source-code/ - Cornu Spiral
http://hyperphysics.gsu.edu/hbase/phyopt/cornu.html - Spiral
https://www.2dcurves.com/spiral/spiral.html - Algebraic Curves
https://mathworld.wolfram.com/topics/AlgebraicCurves.html - Elliptic Curves
https://mathworld.wolfram.com/topics/EllipticCurves.html - Eukleidovská konstrukce
https://cs.wikipedia.org/wiki/Eukleidovsk%C3%A1_konstrukce - Euclidean Constructions
http://www.cs.cas.cz/portal/AlgoMath/Geometry/PlaneGeometry/GeometricConstructions/EuclideanConstructions.htm - Kvadratura kruhu
https://cs.wikipedia.org/wiki/Kvadratura_kruhu - Trisekce úhlu
https://cs.wikipedia.org/wiki/Trisekce_%C3%BAhlu - Straightedge and compass construction
https://en.wikipedia.org/wiki/Straightedge_and_compass_construction - C.a.R.
http://car.rene-grothmann.de/doc_en/index.html - CaRMetal (Wikipedia)
https://en.wikipedia.org/wiki/C.a.R. - CaRMetal (Španělsky a Francouzsky)
http://carmetal.org/index.php/fr/ - CaRMetal (Wikipedia)
https://en.wikipedia.org/wiki/CaRMetal - Regular Polygon
http://mathforum.org/dr.math/faq/formulas/faq.regpoly.html - Geometric Construction with the Compass Alone
http://www.cut-the-knot.org/do_you_know/compass.shtml - Kvadratura kruhu (Wikipedie)
https://cs.wikipedia.org/wiki/Kvadratura_kruhu - Compass equivalence theorem
https://en.wikipedia.org/wiki/Compass_equivalence_theorem - Curves we (mostly) don't learn in high school (and applications)
https://www.youtube.com/watch?v=3izFMB91K_Q - Can You Really Derive Conic Formulae from a Cone? – Menaechmus' Constructions
https://www.maa.org/press/periodicals/convergence/can-you-really-derive-conic-formulae-from-a-cone-menaechmus-constructions - Apollonius of Perga
https://en.wikipedia.org/wiki/Apollonius_of_Perga - Catenary arch
https://en.wikipedia.org/wiki/Catenary_arch - Parabolic arch
https://en.wikipedia.org/wiki/Parabolic_arch - Wattova křivka
https://www.geogebra.org/m/gNh4bW9r - Model stegosaura byl získán na stránce
http://www.turbosquid.com/HTMLClient/FullPreview/Index.cfm/ID/171071/Action/FullPreview - Obrázek nohy dinosaura byl získán na adrese
http://perso.wanadoo.fr/rimasson/3d/leg.htm - Spirograph
https://en.wikipedia.org/wiki/Spirograph - Epicykloida
https://cs.wikipedia.org/wiki/Epicykloida - Hypocykloida
https://cs.wikipedia.org/wiki/Hypocykloida - Hypotrochoida
https://cs.wikipedia.org/wiki/Hypotrochoida - Superelipsoidy a kvadriky v POV-Rayi
https://www.root.cz/clanky/superelipsoidy-a-kvadriky-v-pov-rayi/ - Fifty Famous Curves, Lots of Calculus Questions, And a Few Answers
https://elepa.files.wordpress.com/2013/11/fifty-famous-curves.pdf - Barr, A.H.: Superquadrics and Angle Preserving Transformations,
IEEE Computer Graphics and Applications, January 1981 - Bourke Paul: Quadrics,
July 1996 - Bourke Paul: Superellipse and Superellipsoid,
January 1990 - Faux, I.D. a Pratt, M.J.: Computational Geometry for Design and Manufacture,
Ellis Horwood Ltd., Wiley & Sons, 1979 - Wallace A.: Differential Topology,
Benjamin/Cummings Co., Reading, Massachussetts, USA, 1968 - Glossary of Bridge Terminology
http://sdrc.lib.uiowa.edu/eng/bridges/WaddellGlossary/GlossC.htm - Brachistochrona
https://cs.wikipedia.org/wiki/Brachistochrona - Missions: Cassini
https://solarsystem.nasa.gov/missions/cassini/overview/ - Giovanni Domenico Cassini
https://en.wikipedia.org/wiki/Giovanni_Domenico_Cassini - Cassini Ovals
https://mathworld.wolfram.com/CassiniOvals.html - Geocentrismus
https://cs.wikipedia.org/wiki/Geocentrismus - Who was Giovanni Cassini?
https://www.universetoday.com/130823/who-was-giovanni-cassini/ - Special plane curves
http://xahlee.info/SpecialPlaneCurves_dir/ConicSections_dir/conicSections.html - Why Does Slicing a Cone Give an Ellipse?
https://infinityisreallybig.com/2019/02/08/why-does-slicing-a-cone-give-an-ellipse/ - Interpolace
https://mathonline.fme.vutbr.cz/pg/Algoritmy/05_APROX_KRIVKY.htm - Lagrange Polynomial Interpolation
https://pythonnumericalmethods.berkeley.edu/notebooks/chapter17.04-Lagrange-Polynomial-Interpolation.html - Python Program for Lagrange Interpolation Method (with Output)
https://www.codesansar.com/numerical-methods/python-program-lagrange-interpolation-method.htm - Smooth Paths Using Catmull-Rom Splines
https://qroph.github.io/2018/07/30/smooth-paths-using-catmull-rom-splines.html - Lecture 11: Linear Interpolation Again – Bézier Curves
http://www.math.kent.edu/~reichel/courses/intr.num.comp.1/fall09/lecture12/bez.pdf - Geometrie/Úvod do křivek
https://cs.wikibooks.org/wiki/Geometrie/%C3%9Avod_do_k%C5%99ivek - B-Spline Curves and Surfaces (1)
http://www.cad.zju.edu.cn/home/zhx/GM/006/00-bscs1.pdf - Praktické ukázky možností aplikace Mandelbulber při tvorbě animací
https://www.root.cz/clanky/prakticke-ukazky-moznosti-aplikace-mandelbulber-pri-tvorbe-animaci/
ČLÁNKY DO MAILU