Křivky 2D. Klasifikace křivek (1) Klasifikace křivek (2) Navazování a spojitost křivek. Přednáška 8

Klasifikace křivek (1)

Přednáška 8

Křivky 2D

Žára, J., Beneš, B., Felkel, P. Moderní počítačová grafika. Computer Press, Brno, 1998. ISBN 80-7226-049-9.

Cenek, P. Počítačová grafika. Skripta – Univerzita Pardubice, 1999. ISBN 80-7194-229-4. 1

Počítačová grafika, PV, UPCE-KID, [2010/2011]

Klasifikace křivek (2)


Přednáška 8

2

Navazování a spojitost křivek

Interpolační křivky prochází zadanými řídícími body Aproximační křivky nemusí procházet zadanými řídícími body snaží se je co nejlépe vystihnout

Přednáška 8

3

Navazování probíhá v koncových (krajních) bodech dvou křivek. Tyto body jsou označovány jako uzly. Samotné napojení dvou křivek (jednoduchá spojitost C0) není zárukou hladného napojení.

Existuje klasifikace napojení (spojitosti, kontinuity): C0: spojité napojení, koncový bod první a počáte-ční bod druhé křivky jsou totožné C1: tečné vektory obou křivek jsou si v daném uzlu rovny C2: první derivace tečných vektorů jsou si rovny

Vyšší stupeň spojitosti znamená "hladší" napojení. Vyšší stupeň spojitosti zahrnuje i nižší (Cn+1⇒Cn)


Podle prostoru 2D 3D Podle popisu Křivky zadané analytickým popisem Explicitní (křivka musí být funkcí), y = f(x) např. y = 2x3 + x – 5 Implicitní (problematický postupný výpočet bodů), F(x,y) = 0 např. x2 + y2 = 0 Křivky zadané parametricky Umožňují snadné interaktivní vytváření Rovnice založena na koeficientech a parametru t∈〈0, 1〉 Význam: dráha bodu v čase t


Přednáška 8

4

Příklady C spojitosti

Význam spojitosti, C a G spojitost

Q3 Q1 Q4

Q2

Q5 q’3(0) q’2(0)

q’4(0) q’1(1)

Q1Q2 Æ C0 (G0) Q1Q3 Æ C0 (G1) Q1Q4 Æ C1 (G1)

q’5(0)

Přednáška 8


5

Analytické křivky

Význam stupně spojitosti: vizuální stránka (vzhled) napojení dvou křivek animace (pohyb objektu po křivkách) Důsledky stupně spojitosti: C0 – animovaný objekt nezmění skokem polohu C1 – animovaný objekt nezmění skokem směr a rychlost C2 – animovaný objekt nezmění skokem zrychlení Opticky "hladké" napojení nemusí vždy vyhovovat definici stupně C1. Např. napojení dvou kružnic o různém poloměru nebo dvou rovnoběžných úseček. Geometrická spojitost G1 je méně přísná než C1: G0 – počáteční a koncový bod je totožný G1 – stačí, aby tečné vektory byly lineárně závislé


Bodová rovnice Q(t) = [x(t), y(t)], pro t∈〈0, 1〉

Vektorová rovnice q(t) = (x(t), y(t)), → kde vektor (polohový vektor) q(t) = Q(t) – [0, 0]

y = f (t )

Úsečka:

x = a x + t (bx − a x ) pro

Elipsa:

Přednáška 8

8

→

, kde t∈〈začátek, konec〉

y = a y + t (by − a y )

6

Parametrické křivky

Znalost matematického vyjádření Jednoduchý výpočet plochy, délky Vyjádření pomocí parametrických rovnic

x = g (t )

Přednáška 8

t ∈< 0,1 >

Tečný vektor v bodě Q(t) q’(t) = (x’(t), y’(t)) = (dx(t)/dt, dy’(t)/dt)

→

Rovnice tečny v bodě Q(t) → P(u) = Q(t) + u q’(t), pro u∈〈-∞, ∞〉

x = s x + a cos(t ) y = s y + b sin(t ) pro


t ∈< zač , kon > Přednáška 8

7


Polynomiální křivka

Interpolační křivky

Qn(t)=antn+an-1tn-1+...+a1t+a0, kde n představuje řád křivky

Nejpoužívanější případ: kubika – křivka třetího stupně Q3(t)=a3t3 + a2t2 + a1t + a0 Q3x(t)=a3xt3+a2xt2+a1xt+a0x Q3y(t)=a3yt3+a2yt2+a1yt+a0y

[

Q(t ) = TC = t 3 t 2

⎡ ( a 3 x, a 3 y ) ⎤ ⎢( a 2 x , a 2 y ) ⎥ ⎥ t 1 *⎢ ⎢ (a1x, a1 y ) ⎥ ⎢ ⎥ ⎣( a 0 x, a 0 y ) ⎦

]

P(1)

P(0)

Přednáška 8

9

Interpolace – soustava rovnic

Řešení: Nalezení polynomiální F(x) funkce daného stupně n, která v zadaných bodech x0<x1<…xn-1<xn nabývá hodnot F(x0)=y0, F(x1)=y1, … ,F(xn)=yn Interpolace pomocí splajnové křivky, která se skládá z n dílčích interpolačních polynomů, které platí jako náhrada v dílčích intervalech 〈x0, x1〉, 〈x1, x2〉, … , 〈xn-1, xn〉

Tečný vektor v bodě Q(t) → q’(t) = dQ(t)/dt = dT/dt * C = [3t2 2t 1 0] * C


Je dáno n+1 bodů (určující, opěrné body) Úlohou je nalézt takovou křivku, která těmito body prochází.

10

Interpolace – Lagrangeovy polynomy

Hledáme polynom P(x)=a0+a1x+a2x2+…+anxn Známe n+1 bodů (x, P(x)), sestavíme n+1 rovnic Řešíme soustavu s neznámými a0, a1, …, an

Polynom je dán funkcí n

n

P ( x) = ∑ yk k =0

n

a 0 + a1 x0 + a 2 x0 + ... + a n x0 = y 0 2

Přednáška 8


∏ (x − x ) j

j = 0 , j <> k n

∏ (x

k

− xj)

j = 0 , j <> k

n

a 0 + a1 x1 + a 2 x1 + ... + a n x1 = y1 2

...

n

a 0 + a1 x n + a 2 x n + ... + a n x n = y n 2


Přednáška 8

11

Při větším počtu bodů (vyšší stupeň polynomu) je nevýhodou značné „rozkmitání“ křivky u krajních bodů.


Přednáška 8

12

Vliv řádu křivky na rozkmit

Interpolace pomocí splajnových křivek

Přednáška 8


13

Kubický splajn

Interpolační křivky jsou vyjádřeny polynomem 3. stupně Zadání n+1 body (xi, yi), x0<x1<...<xn-1<xn Pro každý interval tvoříme polynom

3

Substituce

4.n rovnic


Přednáška 8

15

i = 1,2,...,n

Spojitost prvních derivací, spojitost druhých derivací c −c d i = i +1 i i = 1,2,..., n − 1 3t i ci ti + 2ci +1 (ti +1 + ti ) + ci +2ti +1 = 3(vi +1 / ti +1 − vi / ti ) i = 1,2,..., n − 1

Doplňující podmínky, spolu s předch. vztahem tvoří soustavu lin. rov., po jejím vyřešení získáme c1..cn+1 a následně di, bi, ai v /t −v /t c1 = y 0 ' ' / 2 c1 = 2 2 1 1 t 2 + t1 v / t − vn−1 / t n−1 cn+1 = y n ' ' / 2 cn+1 = n n t n + t n−1

ti = xi − xi −1 vi = yi − yi −1 , i = 0,1,..., n − 1

2

t = x − xi −1

Jednotlivé kubiky si ( x) = ai + bi t + ci t 2 + d i t 3

14

Spojitost splajnové funkce ai = yi −1 i = 1,2,..., n

bi = vi / ti − ci ti − d i ti

si ( x) = ai + bi ( x − xi −1 ) + ci ( x − xi −1 ) + d i ( x − xi −1 ) , i = 1,2..., n

Přednáška 8


Kubický splajn – vyjádření rovnic

2

〈x0, x1〉, 〈x1, x2〉, … , 〈xn-1, xn〉 Výsledná interpolace je po částech spojitá. Je možno volit nižší stupeň interpolačního polynomu (3, 5, …). Vhodné i pro vyšší počet bodů Rozepsání jednotlivých podmínek pro krajní body intervalů a derivace v těchto bodech Jednotlivé polynomy platí jako náhrada na intervaly 〈xi-1, xi〉. Splajnová křivka vykazuje nižší zvlnění, než polynom n-tého stupně.


Přednáška 8

16

Aproximace polynomem metodou nejmenších čtverců

Aproximační křivky

Je dáno n bodů. Úlohou je nalezení vhodné aproximační funkce, která nemusí procházet danými body, ale přitom co nejlépe vystihuje (nahrazuje) existující funkční závislost. Regresní analýza Zvolení kritéria – druhé mocniny (čtverce) odchylek Zvolení regresní funkce – nejčastěji se používají polynomy k. stupně, popřípadě hyperbolická nebo exponenciální funkce, které lze převést na polynomy.

n

C = ∑[ F ( xi ) − yi ]2

Kritérium

í =1

∂C =0 ∂ai

Minimalizace kritéria

Dosazením a rozepsáním vznikne soustava n rovnic:

∂ ∂a0

n

∑ (a i =1

k

+ a1 xi + a2 xi + ... + ak xi − yi ) 2 = 0 2

0

∂ n 2 k (a0 + a1 xi + a2 xi + ... + ak xi − yi ) 2 = 0 ∑ ∂a1 i =1 ... ∂ ∂ak

Přednáška 8


17

pokračování …

k

k

k

n

n

i =1

i =1

n

2

i =1

n

n

n

i =1

i =1

k

i =1

n

2

n

n

a 0 ∑ xi + a1 ∑ xi

i =1

i =1


18

i =1

n

3

k +1

i =1

i =1

n

= ∑ y i xi i =1

...

2∑ [(a 0 + a1 xi + a 2 xi + ... + a k xi − y i ).xi ] = 0 k

n

a 0 ∑ xi + a1 ∑ xi + a 2 ∑ xi + ... + a k ∑ xi

... 2

Přednáška 8

Dělením jednotlivých rovnic 2, vytknutím společných členů a převedením pravých stran dostaneme:

1

i =1

n

2

a 0 ∑1 + a1 ∑ xi + a 2 ∑ xi + ... + a k ∑ xi = ∑ y i

2∑ [(a 0 + a1 xi + a 2 xi + ... + a k xi − y i ) xi ] = 0 2

i =1

k

+ a1 xi + a2 xi + ... + ak xi − yi ) 2 = 0

0

i =1 n

0


2∑ [(a 0 + a1 xi + a 2 xi + ... + a k xi − y i ) xi ] = 0 2

∑ (a

pokračování …

Provedením derivací dostaneme soustavu: n

n

Přednáška 8

19

k

k +1

i =1


n

+ a 2 ∑ xi i =1

k +2

n

+ ... + a k ∑ xi i =1

2k

n

= ∑ y i xi

k

i =1

Přednáška 8

20

… dokončení

Fergusonova (Hermitovská) křivka

Provedeme substituci a získáme konečnou soustavu: n

S j = ∑ xi , j

pro

j = 0,1,2,...,2.k

i =1 n

T j = ∑ y i xi , j

pro

j = 0,1,2,..., k

i =1

Řešíme např. GEM a získané hodnoty a0 ..ak jsou koeficienty hledaného polynomu.

a0 S 0 + a1 S1 + a2 S 2 + ... + ak S k = T0

Přednáška 8

21

P0

P1 P’1

P0

Přednáška 8

P’1 22

Bezierova křivka

Parametrické vyjádření pomocí t∈〈0,1〉 Q(t)= P0F1(t)+ P1F2(t)+ P‘0F3(t)+ P‘1F4(t) F1(t).. F4(t) jsou kubické Hermitovské polynomy nastavené tak, aby Q(0)= P0 a Q(1)= P1.

Aproximační křivka Jednoznačné určení křivky n-tého řádu pomocí n+1 bodů řídícího polynomu n n Parametrické vyjádření: P(t ) = ∑ Pi Bi (t ) í =0

Bin (t )

F1(t) = 2t3 – 3t2 + 1 F2(t) = –2t3 + 3t2 (Upozornění – v MPG-Žára, str. 66 je chyba) F3(t) = t3 – 2t2 + t F4(t) = t3 – t2

Přednáška 8

představují Bernsteinovy polynomy n-tého stupně ⎛ n⎞ Bin (t ) = ⎜⎜ ⎟⎟t i (1 − t ) n−i ⎝i⎠ Křivka prochází krajními body pro t=0 a t=1. Tečny v krajních bodech P' (0) = n( P1 − P0 ) P' (1) = n( Pn − Pn−1 )

Hladkého napojení lze docílit identitou koncového a počátečního tečného vektoru navazujících úseků.


P’1

P1


P’0 P1

P0

P0

Fergusonova křivka – vyjádření

P’0 P’0

P1

... a0 S k + a1 S k +1 + a2 S k +2 + ... + ak S 2.k = Tk

P’1

P’0

a0 S1 + a1 S 2 + a2 S3 + ... + ak S k +1 = T1


Často používaná křivka Jednoznačné určení křivky Dva řídící body P0 a P1 Dva tečné vektory P’0 a P’1 Křivka vychází z bodu P0 ve směru vektoru P’0 a končí v bodu P1 ve směru vektoru P’1. Čím větší je velikost tečného vektoru, tím více se k němu křivka přimyká.

23

Spojitost navazujících křivek je zaručena je zaručena, je-li styčný bod středem úsečky tvořené sousedními body.


Přednáška 8

24

Bezierova křivka 3 řádu – příklad

Výpočet a zobrazení

n=3; 4 body P0(0,5); P1(38,33); P2(58,35); P3(78,0);

P(t ) = P0 (1 − t ) 3 + P1 3t (1 − t ) 2 + P2 3t 2 (1 − t ) + P3t 3 ,

pro t ∈ 〈0,1〉

3

P(t ) = ∑ Pi Bi3 (t ) í =0

q'0

⎛ 3⎞ B (t ) = ⎜⎜ ⎟⎟t 0 (1 − t ) 3 ⎝ 0⎠ ⎛ 3⎞ B13 (t ) = ⎜⎜ ⎟⎟t 1 (1 − t ) 2 ⎝ 1⎠

P1

3 0

⎛ 3⎞ B23 (t ) = ⎜⎜ ⎟⎟t 2 (1 − t )1 ⎝ 2⎠ ⎛ 3⎞ B33 (t ) = ⎜⎜ ⎟⎟t 3 (1 − t ) 0 ⎝ 3⎠ Počítačová grafika, PV, UPCE-KID, [2010/2011]

P0

Q0

P2

Q1

P3 q'1

Přednáška 8

25

Algoritmus de Casteljau

Algoritmus de Casteljau – výpočet

Odstraňuje nevýhodu rasterizace Bezierovy křivky s konstantním přírůstkem Δt Minimalizuje objem dat vzhledem ke křivosti různých částí křivky Rekurzivní algoritmus Křivka Q se rozdělí dle zvoleného t (0.5) na dvě části Q1 a Q2 Vstup (kroku): P0, P1, P2, P3 Výstup (kroku): Q1 [P0,0, P1,1, P2,2, P3,3]; Q2 [P3,3, P3,2, P3,1, P3,0]]

P0

P1

Postupná aproximace křivky Kritéria ukončení Pokud vzdálenost sousedních bodů < úhlopříčka pixelu Pokud je plocha řídícího polygonu dostatečně malá


Přednáška 8

P2

P3

P0,0 1-t

P1,0 t

P2,0 t

1-t

P1,1

P2,1 t

1-t

P3,0

P2,2

P3,1 t

1-t

P2,1

P1

t

1-t

P2,2

P1,1

P2 P3,2

P3,3

P3,1

P3,2 t

P3,3 27

Ps,r = (t-1)Ps-1,r-1 + (t)Ps,r-1 pro r=1..n, s=r..n

1-t

26

Přednáška 8



P0

P3 Přednáška 8

28

Kubická Coonsova křivka

Aproximační křivka Parametrické vyjádření: 3

P(t ) = ∑ Pi * Coin (t ) í =0

Neprochází body P0 a P3 Krajní body pro t=0 a t=1 P(0) = ( P0 + 4 P1 + P2 ) / 6

Splajn křivky

1 1 1 1 Co0 (t ) = − t 3 + t 2 − t + 6 2 2 6 1 3 2 2 Co1 (t ) = t − t + 2 3 1 3 1 2 1 1 Co2 (t ) = − t + t + t + 2 2 2 6 1 3 Co3 (t ) = t 6

Upozornění: Oprava vztahů Co1 a Co3. V předchozí verzi přednášek byly polynomy uvedeny chybně.

P(1) = ( P1 + 4 P2 + P3 ) / 6

Tečny v koncových bodech:

1 = (1 − t )3 6 1 3 = (3t + 6t 2 + 4) 6 1 = (−3t 3 + 3t 2 + 3t + 1) 6

P2

q'0

P1

q'1

Q1

Polynomiální, po částech spojitá křivka Aproximační nebo interpolační křivka Nejčastěji se používají B-spline kubiky: Aproximační křivka Coonsův kubický B-spline (tvoří se navázáním Coonsových kubik) Změna polohy jednoho řídícího bodu neovlivní celou křivku, ale jen okolí daného řídícího bodu. n>=4 řídících bodů, n=3 segmentů Lze využít násobnosti bodů.

Q0 P3

p' (0) = ( P2 − P0 ) / 2 p' (1) = ( P1 − P3 ) / 2 Počítačová grafika, PV, UPCE-KID, [2010/2011]

P0

Přednáška 8

29

Podpora v Javě (1)

Kubická křivka

Neprochází řídícím bodem

Neprochází řídícími body

QuadCurve2D.Double QuadCurve2D.Float Float x1, y1 Float ctrlx, ctrly Float x2, y2

CubicCurve2D.Double CubicCurve2D.Float Float x1, y1 Float ctrlx1, ctrly1 Float ctrlx2, ctrly2 Float x2, y2

// souřadnice počátečního bodu // souřadnice řídícího bodu // souřadnice koncového bodu

Příklad

Graphics2D g2 = (Graphics2D) g; QuadCurve2D.Float qc = new QuadCurve2D.Float( P[0].x, P[0].y, P[1].x, P[1].y, P[2].x, P[2].y); g2.draw(qc);


30

Podpora v Javě (2)

Kvadratická křivka

Přednáška 8


Přednáška 8

// // // //

souřadnice souřadnice souřadnice souřadnice

počátečního bodu 1. řídícího bodu 2. řídícího bodu koncového bodu

Příklad Graphics2D g2 = (Graphics2D) g; CubicCurve2D.Float cc = new CubicCurve2D.Float( P[0].x, P[0].y, P[1].x, P[1].y, P[2].x, P[2].y, P[3].x, P[3].y); g2.draw(cc);

31


Přednáška 8

32

Křivky 2D. Klasifikace křivek (1) Klasifikace křivek (2) Navazování a spojitost křivek. Přednáška 8

Recommend Documents