Parametrické křivky

Křivky (Curves)

“Curve need not to be curved!”

Vyjádření křivek

Úsečka

“ One ring to rule them all,
one ring to find them,
one ring to bring them all,
and in the darkness bind them ”

Lomená čára

Přímka a úsečka

Úsečka leží na přímce, kterou můžeme vyjádřit pomocí:

Rasterizaci úsečky

Úsečka je část přímky, která je jednoznačně určena body $ P_{1} = [x_{1}, y_{1}]$ a $ P_{2} = [x_{2}, y_{2}] $. Směrnice přímky je:

Pro osmispojitou úsečku s tloušťkou jedna a rezignací na antialiasing lze použít například algoritmus DDA (Digital Differential Analyzer)

Algoritmus DDA

Varianta algoritmu pro $ k < 1 $:

var k = (y2 - y1)/(x2 - x1);
var x = x1;
var y = y1;
while(x < x2) {
	draw(x, y);
	x += 1;
	y += k;
}
						

Tlouťka, antialising, přerušování, ukončení

V praxi je často nutné vykreslovat úsečku jako geometrický útvar (nejčastěji obdelník) a řešit další netriviální problémy.

Naštěstí existuje spousta knihoven a API (HTML5 Canvas, WebGL, atd.), které tyto problémy řeší za nás.

Úsečka a HMTL5 - Canvas

Úsečku můžeme do canvasu vykreslit jednoduše pomocí následujícího kódu v Javascriptu.

var canvas = document.getElementById('myCanvas');
var ctx = canvas.getContext('2d');
ctx.beginPath();
ctx.moveTo(150, 100);
ctx.lineTo(390,170);
ctx.lineWidth = 10;
ctx.strokeStyle = 'white';
ctx.lineCap = 'round';
ctx.stroke();
							

Parametrické vyjádření křivky

• Bodová rovnice: $$ Q(t) = [x(t), y(t), z(t)] \quad 0 \leq t \leq 1 $$
• Polohový vektor: $$ \begin{align} \vec{q(t)} &= (x(t), y(t), z(t)) = \\ &= Q(t) = [0, 0, 0] \quad 0 \leq t \leq 1 \end{align} $$

Výhody parametrického vyjádření křivek

Oproti funkcím může křivka protínat samu sebe, může se uzavřít, může být rovnoběžná s libovolnou osou, apod.

Parametr $ t $ můžeme chápat jako čas.

Lze je používat jak ve 2D, tak i v 3D prostoru.

Spojitost

Parametrická spojitost

Říkáme, že křivku $ Q(t) $ nazýváme parametricky spojitou $ C^{n} $, pokud ve všech jejích bodech existuje derivace stupně $ n $

Geometrická spojitost

Dvě křivky $ Q_{1} $ a $ Q_{2} $ jsou geometricky spojité $ G^{n} $ ve společném bodě, pokud je zaručeno:

Jinými slovy pro $ G^{1} $ není potřeba rovnost tečných vektorů, ale pouze rovnost tečen v daném bodě.

Je-li křivka $ C^{1} $ je potom i $ G^{1} $ spojitá?

Ano, je-li křivka $ C^{n} $ tak je potom automaticky i $ G^{n} $ spojitá.

Modelování křivek

“Polynoms rule the world of parametric curves”

Polynomiální křivky

Vlastnosti polynomiálních křivek

• Jednoduchý výpočet
• Snadno diferencovatelné (tečné vektory)
• Používají se křivky po částech polynomiální
• Nejčastěji se používají kubiky

Často požadované vlastnosti křivek

• Invariace vůči lineárním transformacím a projekcím
• Křivka leží uvnitř konvexní obálce všech svých řídících bodů
• Lokalita změn polohy/váhy řídícího bodu (křivky po částech polynomiální)

Kubiky

Parametrické vyjádření kubik má následující tvar:

Maticové vyjádření

Matici $ C $ můžeme vyjádřit: $ C = MG $

kde $ M $ se nazývá bázová matice (určuje druh křivky) a $ G $ je vektor geometrických podmínek (řídící body a vektory)

Výsledný podoba maticového vyjádření:

Bázové polynomy

Určují váhu jednotlivých řídících bodů/vektorů pro různé hodnoty $ t \in \langle 0, 1 \rangle $

Jednoduchý příklad bázových polynomů

Mějme křivku, která je určena body $ P_{1} $ a $ P_{2} $:

O jakou křivku se jedná?

Je to úsečka s krajními body $ P_{1} $ a $ P_{2} $.

Bézierovy křivky

“Aproximate or interpolate? That's the question!”

Bézierova křivka n-tého stupně

Je dána vztahem:

kde $ P_{i} $ je i-tý řídící bod a $ B_{i}^{n}(t) $ je Bernsteinův polynom n-tého stupně

Vlastnosti Bézierovy křivky

• Křivka prochází prvním a posledním řídícím bodem
• Křivka leží uvnitř ohraničující obálky, která je určena řídícimi body
• Při změně polohy jednoho řídícího bodu, dojde ke změně celé křivky
• Nejčastěji se používají kubiky, které se na sebe navazují

Tečné vektory v koncových bodech

Spojitost dvou Bézierových křivek

Mějme dvě Bézierovy křivky $ Q_{1}(t) $ a $ Q_{2}(t) $

• Křivky mají spojitost $ C^{0} $, pokud $$ Q_{1}(1) = Q_{2}(0) $$
• Křivky mají spojitost $ C^{1} $, pokud $$ (P_{n-1} - P_{n}) = (R_{0} - R_{1}) $$
• Křivky mají spojitost $ G^{1} $, pokud $$ (P_{n-1} - P_{n}) = k(R_{0} - R_{1}) $$

Bézierovy kubiky

Bézierova křivka 3. stupně

Bernstainovy polynomy 3. stupně:

Výsledná podoba bázových polynomů:

Průběh bázových polynomů

Maticový zápis Bézierovy kubiky

Vykreslování Bézierovy křivky

“Adaptive or non-adaptive? That's the question too.”

Neadaptivní vykreslování

Parameter $ t $ zvyšujeme o pevně daný krok (např.: $dt = 0.01$). Dostaneme množinu bodů, které spojíme lomenou čárou.

Prvním problémem je určit, jak má být tento krok jemný.

Druhým problémem je, že rovné části jsou často vykreslované zbytečně jemně a zakřivené části nedostatečně jemně.

Adaptivní algoritmus de Casteljau

Při vykreslování pomocí tohoto algoritmu se využívá dělení Bézierovy křivky na dvě části.

Aproximace množiny 2D bodů metodou nejmenších čtverců

Množina 2D bodů

Mějme množinu 2D bodů $ P^{T} = [ P_{1}, P{2}, \dots, P_{n} ]$, kde $ P_{i} = [ x_{i}, y_{i} ]$.

Následně můžeme definovat dva samostatné vektory:

Parametrizace aproximovaných bodů

Pro aproximaci množiny bodů $P=[P_{1}, P_{2}, \dots, P_{n}]$ potřebujeme definovat vektor parametrů:

, který mapuje jednotlivé body $P_{i}$ na body Bézierovy křivky. První nástřel mapování může být vytvořen pomocí vzdálenosti boduů $P_{i}$ od počátečního bodu $P_{0}$.

Výpočet parametrizace bodů

Vzdálenost i-tého bodu od počátku křivky je:

pak můžeme pro každý aproximovaný bod $P_{i}$ spočítat odpovídající parametr $t_{i}$:

Chyba aproximace

Pro výpočet aproximace metodou nejmenších čtverců potřebujeme vztah, který nám určuje celkovou chybu:

Pro parametrizaci bodů $P$ si definujeme matici:

Předhozí vztahy pro výpočet chyby tak můžeme přepsat na:

Pro nalezení minima vztah parciálně zderivujeme podle $C_{x}$ a dáme roven nule:

Výsledné vztahy mají tvar:

$$ C_{z} = M^{-1} (\Pi^{T}\Pi)^{-1}\Pi^{T} z $$

Průsečíky

V počítačové grafice má smysl se zabývat následujícími případy

• Průsečík dvou 2D křivek
• Průsečík 3D křivky s plochou
• Průsečík dvou ploch

Průsečík dvou 2D křivek

• Snažíme se nalézt množinu bodů (průsečíků)
• Pokud je možné křivky vyjádřit jako dvě funkce: $ y = f_{1}(x) $ a $ y = f_{2}(x) $, tak na výsledek nalezneme řešením rovnice: $ f_{1}(x) - f_{2}(x) = 0 $.
• Pokud jsou obě křivky vyjádřeny implicitně: $ f_{1}(x,y) = 0 $ a $ f_{2}(x,y) = 0 $, tak jejich průsečíky můžme nalézt vyřešením soustavy rovnic.
• Pokud je jedna křivka vyjádřena implicitně: $ f(x,y) = 0 $ a druhá parametricky: $ x = x(t), y=y(t)$, tak řešení je: $f(x(t), y(t)) = 0 $

Průsečík Bézierovy křivky s přímkou

Implicitní vyjádření přímky: $ y - kx - q = 0$

Parametrické vyjádření Bézierovy křivky:

Obecné rovnice má tvar:

Bézierovy kubiky a HMTL5 - Canvas

var canvas = document.getElementById('myCanvas');
var ctx = canvas.getContext('2d');
ctx.beginPath();
ctx.moveTo(150, 100);
ctx.bezierCurveTo(140,10, 390,10, 390,170);
ctx.lineWidth = 10;
ctx.strokeStyle = 'white';
ctx.lineCap = 'round';
ctx.stroke();
							

Canvas & Bézier & spol.

• lineTo() vykreslí úsečku
• arc() vykreslí kruhovou výseč
• quadraticCurveTo() vykreslí Bézierovu křivku 2. řádu
• bezierCurveTo() vykreslí Bézierovu kubiky
• beginPath() umožňuje navazovat křivky

Bézierovy kubiky a HTML5 - SVG

SVG - příklad

SVG & Javascript

• raphaeljs.com
• www.learnsvg.com
• svgdiscovery.com

Coonsovy kubiky

Označována také uniformní racionální B-spline, zkráceně B-spline a je důležitým mezikrokem k pochopení NURBS křivek a NURBS ploch

Konstrukce Coonsovy kubiky z řídících bodů

Výpočet Coonsovy kubiky

Je určena 4 řídícími body: $P_{0}$, $P_{1}$, $P_{2}$, $P_{3}$ a vztahem:

Bázové polynomy Coonsovy kubiky

Počáteční a koncový bod

• Počáteční bod leží v anitěžišti trojúhelníku tvořeného prvními třemi body ($P_{0}$, $P_{1}$, $P_{2}$), což lze jednoduše vyjádřit vztahem:
  $$ Q(0) = \frac{P_{0} + 4P_{1} + P_{2}}{6} $$
• Koncový bod leží naopak v anitěžišti trojúhelníku tvořeného posledními třemi body ($P_{1}$, $P_{2}$, $P_{3}$), což lze vyjádřit:
  $$ Q(1) = \frac{P_{1} + 4P_{2} + P_{3}}{6} $$

Tečné vektory

• Tečný vektor v počátečním bodu:
  $$ q_{0}^{\prime} = \frac{P_{2} - P_{0}}{2} $$
• Tečný vektor v koncovém bodu:
  $$ q_{1}^{\prime} = \frac{P_{3} - P_{1}}{2} $$

NURBS

“Non Uniform Rational B-spline! What?!”

NURBS křivky

• Zobecněním uniformních kubických B-splinů
• Neuniformita říká, že vzdálenost uzlů (koncových bodů segmentů), ve smyslu parametru t, nemusí být konstantní: $ t_{i+1} - t_{i} \neq c$
• Racionalita říká, že řídící body jsou dány svými homogeními souřadnicemi.
• NURBs křivka je tedy určena $ n + 1 $ řídícími body $ P_{i}; i = 0, 1, \dots, n $, řádem B-spline $ k $ a uzlovým vektorem $ U $ délky $ n + k + 1$.

Výpočet NURBs

NURBs křivka je dána následujícím vztahem:

Bázové funkce

Jsou definované následujícím rekurentním vztahem:

Předchozí vztah platí pro:

Pokud se ve jmenovateli vyskytuje nula, tak výsledná hodnota je v tomto případě rovna nule.

Využití NURBs

Především NURBs plochy se používají v CAD/CAM aplikacích.

NURBs a Web

B-spline nebo NURBs není podporováno v SVG ani v Canvasu. Je nutné použít externí knihovnu.