VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA STROJNÍHO INŽENÝRSTVÍ ÚSTAV MATEMATIKY FACULTY OF MECHANICAL ENGINEERING INSTITUTE OF MATHEMATICS
SROVNÁNÍ KVALITATIVNÍCH VLASTNOSTÍ INTERPOLAČNÍCH NURBS KŘIVEK COMPARISON OF QUALITATIVE PROPERTIES OF NURBS INTERPOLATION CURVES
BAKALÁŘSKÁ PRÁCE BACHELOR'S THESIS
AUTOR PRÁCE
DAVID HALAS
AUTHOR
VEDOUCÍ PRÁCE SUPERVISOR
BRNO 2015
Mgr. JANA HODEROVÁ, Ph.D.
Vysoké učení technické v Brně, Fakulta strojního inženýrství Ústav matematiky Akademický rok: 2014/2015
ZADÁNÍ BAKALÁŘSKÉ PRÁCE student(ka): David Halas který/která studuje v bakalářském studijním programu obor: Matematické inženýrství (3901R021) Ředitel ústavu Vám v souladu se zákonem č.111/1998 o vysokých školách a se Studijním a zkušebním řádem VUT v Brně určuje následující téma bakalářské práce: Srovnání kvalitativních vlastností interpolačních NURBS křivek v anglickém jazyce: Comparison of qualitative properties of NURBS interpolation curves Stručná charakteristika problematiky úkolu: V počítačové geometrii a grafice se pro křivky technické praxe s výhodou užívají například NURBS křivky. Standartně je NURBS křivka zadávána řídícím polygonem, jde tedy o křivku aproximační. Uživatelsky příjemnější je však křivka, která prochází přímo zadanými body, tedy interpolační křivka. Vlastnosti interpolační NURBS křivky jsou zásadně ovlivněny napřílad konstrukcí vektoru parametrizace a uzlového vektoru. Práce bude zaměřena na různé volby těchto faktorů a sledování chování výsledných křivek. Cíle bakalářské práce: Práce bude mít část teoretickou, kde bude vysvětlen princip NURBS křivek a část aplikační. V aplikační části bude na konkrétních datech provedena interpolace NURBS křivkami s různě nastavenými parametry.
Seznam odborné literatury: Linkeová, I.: Interpolační NURBS křivky - článek Piegl, L, Tiller, W.: The NURBS Book - monografie, Springer
Vedoucí bakalářské práce: Mgr. Jana Hoderová, Ph.D. Termín odevzdání bakalářské práce je stanoven časovým plánem akademického roku 2014/2015. V Brně, dne 24.11.2014 L.S.
_______________________________ prof. RNDr. Josef Šlapal, CSc. Ředitel ústavu
_______________________________ doc. Ing. Jaroslav Katolický, Ph.D. Děkan fakulty
Abstrakt Tato pr´ace se zab´ yv´a prost´ ymi interpolaˇcn´ımi kˇrivkami, kter´e jsou ukotven´e. Konstrukce tˇechto kˇrivek je ˇreˇsena nˇekolika tvarovac´ımi metodami. Tak´e je uveden postup jejich v´ ypoˇctu. V´ ysledkem je porovn´an´ı r˚ uzn´ ych interpolaˇcn´ıch metod. Pr´ace je uˇziteˇcn´a k porozumˇen´ı interpolaˇcn´ıch NURBS kˇrivek a k v´ ybˇeru vhodn´ ych tvarovac´ıch metod. Summary This thesis deals with simple interpolation curves, which are clamped. Construction of the curves is solved by several forming tools. There is also brought procedure of their calculation. Result is comparating different interpolation methods. The thesis is useful to understanding for interpolation NURBS curves and for choosing apposite forming methods. Kl´ıˇ cov´ a slova NURBS, kˇrivka, interpolace Keywords NURBS, curve, interpolation
HALAS, D. Srovn´an´ı kvalitativn´ıch vlastnost´ı interpolaˇcn´ıch NURBS kˇrivek. Brno: Vysok´e uˇcen´ı technick´e v Brnˇe, Fakulta strojn´ıho inˇzen´ yrstv´ı, 2015. 38 s. Vedouc´ı bakal´aˇrsk´e pr´ace Mgr. Jana Hoderov´a, Ph.D..
Prohlaˇsuji, ˇze jsem bakal´aˇrskou pr´aci Srovn´an´ı kvalitativn´ıch vlastnost´ı NURBS kˇrivek vypracoval samostatnˇe pod veden´ım Mgr. Jany Hoderov´e, Ph.D. s pouˇzit´ım materi´al˚ u uveden´ ych v seznamu literatury. David Halas
Chtˇel bych podˇekovat sv´e vedouc´ı Mgr. Janˇe Hoderov´e, Ph.D. za odborn´e veden´ı, za pomoc a rady pˇri zpracov´an´ı t´eto bakal´aˇrsk´e pr´ace.
Obsah ´ Uvod
1
1 Prost´ a interpolaˇ cn´ı NURBS kˇ rivka 1.1 Z´akladn´ı pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Postup urˇcen´ı kˇrivky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 2 4
2 Tvarovac´ı n´ astroje 2.1 Uzlov´ y vektor . . . . . . . . . . . . . . . 2.1.1 Uniformn´ı uzlov´ y vektor . . . . . 2.1.2 Pr˚ umˇerov´ y uzlov´ y vektor . . . . . 2.1.3 Tˇeˇziˇst’ov´ y uzlov´ y vektor . . . . . 2.2 Vektor parametrizace . . . . . . . . . . . 2.2.1 Uniformn´ı vektor parametrizace . 2.2.2 Tˇetivov´ y vektor parametrizace . . 2.2.3 Dostˇrediv´ y vektor parametrizace 2.3 V´ahy ˇr´ıd´ıc´ıch bod˚ u . . . . . . . . . . . .
5 5 5 5 5 6 6 6 7 7
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
3 Konstrukce prost´ e interpolaˇ cn´ı NURBS kˇ rivky 3.1 Vektor parametrizace . . . . . . . . . . . . . . . . . . . . . 3.1.1 Uniformn´ı vektor parametrizace . . . . . . . . . . . 3.1.2 Tˇetivov´ y vektor parametrizace . . . . . . . . . . . . 3.1.3 Dostˇrediv´ y vektor parametrizace . . . . . . . . . . 3.2 Uzlov´ y vektor . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 B´azov´e funkce . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Tˇeˇziˇst’ov´e v´ahy definiˇcn´ıch bod˚ u a racion´aln´ı b´azov´e funkce 3.5 V´ ypoˇcet ˇr´ıdic´ıch bod˚ u . . . . . . . . . . . . . . . . . . . . 3.6 Analytick´e vyj´adˇren´ı NURBS kˇrivky . . . . . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
8 . 8 . 8 . 8 . 8 . 8 . 8 . 13 . 16 . 18
4 Porovn´ an´ı metod interpolace
20
Z´ avˇ er
23
Pouˇ zit´ a literatura
24
Seznam pouˇ zit´ ych symbol˚ u
25
Seznam pˇ r´ıloh
26
´ Uvod V poˇc´ıtaˇcov´e geometrii se s velkou v´ yhodou pouˇz´ıvaj´ı NURBS kˇrivky. Uˇzivatel pouˇz´ıvaj´ıc´ı program s tˇemito kˇrivkami, m˚ uˇze pˇristoupit k tˇemto kˇrivk´am dvˇema zp˚ usoby. Prvn´ı zp˚ usob zahrnuje volbu ˇr´ıd´ıc´ıch bod˚ u, kter´ ymi kˇrivka neproch´az´ı (v´ yjimka m˚ uˇze nastat u poˇca´teˇcn´ıho a koncov´eho bodu), potom p˚ ujde o aproximaˇcn´ı kˇrivky. Druh´ y zp˚ usob je takov´ y, ˇze si uˇzivatel zvol´ı body, kter´ ymi mus´ı kˇrivka proch´azet, napˇr´ıklad pˇri pr´aci s pˇresn´ ymi daty. S t´ımto pˇr´ıstupem se kˇrivky naz´ yvaj´ı interpolaˇcn´ı, a na nˇe je zamˇeˇrena tato pr´ace. NURBS (neuniformn´ı racion´aln´ı B-spliny) kˇrivky jsou zobecnˇen´ım B-spline kˇrivek.T´ım se n´am i rozˇsiˇruj´ı jej´ıch moˇznosti. Racion´aln´ı znamen´a, ˇze zav´ad´ıme v´ahy ˇr´ıd´ıc´ıch bod˚ u. Tyto v´ahy ovlivˇ nuj´ı v´ ysledn´ y tvar kˇrivky. V´aha tedy urˇcuje d˚ uleˇzitost vlivu ˇr´ıd´ıc´ıho bodu na tvar kˇrivky oproti ostatn´ım ˇr´ıd´ıc´ım bod˚ um. D´ıky v´ah´am je NURBS kˇrivka analyticky vyj´adˇrena racion´aln´ımi funkcemi p-t´eho stupnˇe. Jestliˇze rozd´ıly hodnot parametru, ve kter´ ych doch´az´ı k napojen´ı jednotliv´ ych segment˚ u kˇrivky jsou konstantn´ı, uˇz´ıv´ame pojem uniformn´ı. V pˇr´ıpadˇe kdy rozd´ıly konstantn´ı nejsou, bav´ıme se o neuniformnosti. V prvn´ı kapitole jsou uvedeny z´akladn´ı definice pro v´ ypoˇcet prost´e interpolaˇcn´ı NURBS kˇrivky. Definice jsou seˇrazeny podle postupu sestrojen´ı kˇrivky. Pokud se nebudeme zab´ yvat vektorem parametrizace, m˚ uˇzeme sestrojit aproximaˇcn´ı NURBS kˇrivku, ale potˇrebujeme zn´at ˇr´ıd´ıc´ı body m´ısto definiˇcn´ıch bod˚ u. Jestliˇze vynech´ame v´ ypoˇcet vah, m˚ uˇzeme sestrojit interpolaˇcn´ı nebo aproximaˇcn´ı B-spline kˇrivku. V druh´e kapitole jsou uvedeny z´akladn´ı metody tvarov´an´ı interpolaˇcn´ıch NURBS kˇrivek. Existuje v´ıce metod neˇz je uvedeno, na uk´azku jsou vybr´any uniformn´ı, tˇetivov´ y a dostˇrediv´ y vektor parametrizace a uniformn´ı, pr˚ umˇerov´ y a tˇeˇziˇst’ov´ y uzlov´ y vektor. Pro v´ ypoˇcet vah ˇr´ıd´ıc´ıch bod˚ u je vybr´ana tˇeˇziˇst’ov´a metoda. Ve tˇret´ı praktick´e kapitole je uk´az´an postup pˇri sestrojov´an´ı prost´e interpolaˇcn´ı NURBS kˇrivky s uniformn´ım uzlov´ ym vektorem. Jsou pouˇzity vˇsechny tˇri vektory parametrizace uveden´e v pr´aci. Na konci v´ ypoˇctu jsou zobrazeny vˇsechny tˇri kˇrivky do jednoho grafu pro porovn´an´ı. V posledn´ı kapitole jsou i obr´azky dalˇs´ıch kˇrivek s ostatn´ımi uzlov´ ymi vektory opˇet s r˚ uzn´ ymi vektory parametrizace. Pouˇzit´e metody porovn´av´ame a vyb´ır´ame ty nejpˇresnˇejˇs´ı, tedy nejvhodnˇejˇs´ı pro modelov´an´ı NURBS kˇrivek.
1
1
Prost´ a interpolaˇ cn´ı NURBS kˇ rivka
V t´eto kapitole budou zavedeny z´akladn´ı pojmy pro konstrukci prost´e interpolaˇcn´ı kˇrivky. Prostou interpolaci si vyb´ır´ame, pokud chceme, aby poˇcet ramen ˇr´ıd´ıc´ıho polygonu byl roven poˇctu ramen definiˇcn´ıho polygonu. Tak´e je zbyteˇcn´e uvaˇzovat okrajov´e podm´ınky. Na tvar kˇrivky maj´ı vliv definiˇcn´ı body Qi , stupeˇ n p, vektor parametrizace H, uzlov´ y vektor U a v´ahy ˇr´ıd´ıc´ıch bod˚ u W . Z praktick´ ych d˚ uvod˚ u se pouˇz´ıv´a stupeˇ n 2 a 3, aby pˇri vyˇsˇs´ıch stupn´ıch nedoch´azelo k nevhodn´ ym tvar˚ um kˇrivky. Obr´azek 1 zobrazuje jednoduchou interpolaˇcn´ı NURBS kˇrivku a jej´ı z´akladn´ı popis. Jedn´a se o ukotvenou kˇrivku, protoˇze proch´az´ı poˇca´teˇcn´ım a koncov´ ym ˇr´ıd´ıc´ım boˇ ıd´ıc´ı polygon (Pi )3 je tvoˇren uspoˇr´adan´ dem. R´ y mi ˇ r ´ ıdic´ ımi body P a na Obr´azku 1 i i=0 3 je zn´azornˇen ˇc´arkovanou ˇcarou. Definiˇcn´ı polygon (Qi )i=0 je vytvoˇren z uspoˇra´dan´ ych definiˇcn´ıch bod˚ u Qi a na Obr´azku 1 je uk´az´an teˇckovanou ˇcarou. Hodnoty parametru vektoru parametrizace hi jsou parametry, ve kter´ ych kˇrivka proch´az´ı definiˇcn´ımi body Qi . Uzlov´e rozteˇce hui , ui+1 ) jsou zv´ yraznˇeny r˚ uzn´ ymi tlouˇst’kami ˇcar kˇrivky.
Obr´azek 1: Interpolaˇcn´ı NURBS kˇrivka a jej´ı popis Definice z t´eto kapitoly jsou ˇcerp´any ze zdroj˚ u [1] a [3].
1.1
Z´ akladn´ı pojmy
Definice 1 (Vektor parametrizace) Necht’ H je neklesaj´ıc´ı posloupnost n+1 re´aln´ych ˇc´ısel h0 ≤ h1 ≤ . . . ≤ hn . Potom ˇc´ısla hi , i = 0, . . . , n, naz´yv´ame hodnotami parametru, mnoˇzinu H = (hi )ni=0 naz´yv´ame vektorem parametrizace. Definice 2 (Uzlov´ y vektor) Necht’ U je neklesaj´ıc´ı posloupnost (m+1) re´aln´ych ˇc´ısel u0 ≤ u1 ≤ . . . ≤ um . Potom ˇc´ısla ui , kde i = 0, . . . , m, naz´yv´ame uzly, mnoˇzinu U = (ui )m i=0 = (u0 , u1 , . . . , um ) naz´yv´ame uzlov´ym vektorem a polootevˇren´y interval hui , ui+1 ) naz´yv´ame i-tou uzlovou rozteˇc´ı (uzlov´ym intervalem).
2
Definice 3 (B-spline b´ azov´ e funkce) Na dan´em uzlov´em vektoru U = (ui )m i=0 , u0 = a, um = b, a, b ∈ R, jsou B-spline b´azov´e funkce Ni,p (u), i = 0, . . . , n, u ∈ ha, bi, stupnˇe p definov´any rekurentn´ım vzorcem 1, u ∈ hui , ui+1 ) Ni,0 (u) = , (1) 0, u ∈ / hui , ui+1 ) nebo na uzlov´e rozteˇci nulov´e d´elky Ni,k (u) =
ui+k+1 − u u − ui Ni,k−1 (u) + Ni+1,k−1 (u), k = 1, . . . , p. ui+k − ui ui+k+1 − ui+1
(2)
Definice 4 (V´ ahy ˇ r´ıd´ıc´ıch bod˚ u) Necht’ je d´an ˇr´ıd´ıc´ı polygon (Pi )ni=0 a posloupnost nez´aporn´ych re´aln´ych ˇc´ısel W = (w0 , w1 , . . . , wn ) = (wi )ni=0 , kter´a jsou pˇriˇrazena odpov´ıdaj´ıc´ım ˇr´ıd´ıc´ım bod˚ um P0 , P1 , . . . , Pn . Potom ˇc´ısla w0 , w1 , . . . , wn oznaˇcujeme jako v´ahy ˇr´ıd´ıc´ıch bod˚ u. Definice 5 (Racion´ aln´ı b´ azov´ e funkce) Necht’ jsou d´any v´ahy ˇr´ıd´ıc´ıch bod˚ u W = (wi )ni=0 . Potom jsou racion´aln´ı b´azov´e funkce Ri,p (u), i = 0, . . . , n, u ∈ ha, bi, stupnˇe p definov´ any Ni,p (u)wi Ri,p (u) = Pn , j=0 Nj,p (u)wj
(3)
kde Ni,p (u), i = 0, . . . , n, jsou B-spline b´azov´e funkce. Pozn´ amka 1 U vzorce (3) si m˚ uˇzeme vˇsimnout, ˇze pokud P budou vˇsechny v´ahy wi jednotkov´e nebo stejn´e, dostaneme vzorec (2) d´ıky vlastnosti ni=0 Ni,p (u) = 1 pro ∀u ∈ h0, 1i. ´ Pozn´ amka 2 Utvar, kter´y je d´an uspoˇr´adan´ymi definiˇcn´ımi body Qi se naz´yv´a definiˇcn´ı polygon a budeme ho znaˇcit (Qi )ni=0 . Analogicky je zaveden pojem ˇr´ıd´ıc´ı polygon. Definice 6 (Prost´ a interpolaˇ cn´ı NURBS kˇ rivka) Necht’ je d´an definiˇcn´ı polygon (Qi )ni=0 , n kˇrivky p. Necht’ jsou vektor parametrizace H = (hi )ni=0 , uzlov´y vektor U = (ui )ni=0 a stupeˇ n d´ale zn´amy kladn´e v´ahy W = (wi )i=0 . Potom je vektorov´a rovnice prost´e interpolaˇcn´ı NURBS kˇrivky C(u) stupnˇe p C(u) =
n X
Ri,p (u)Pi , u ∈ hu0 , um i,
(4)
i=0
kde Ri,p (u), u ∈ hu0 , um i, i = 0, . . . , n, jsou racion´aln´ı b´azov´e funkce. Pi , i = 0, . . . , n, jsou ˇr´ıd´ıc´ı body, kter´e obdrˇz´ıme ˇreˇsen´ım soustavy rovnic C(hi ) =
n X
Ri,p (hi )Pi = Qi , i = 0, ..., n,
(5)
i=0
jej´ıˇz maticov´y tvar je R0,p (h0 ) R1,p (h0 ) · · · R0,p (h1 ) R1,p (h1 ) · · · .. .. . . R0,p (hn ) R1,p (hn ) · · ·
Rn,p (h0 ) P0 Q0 Rn,p (h1 ) P1 Q1 . .. = .. . .. . . . Rn,p (hn ) 3
Pn
Qn
1.2
Postup urˇ cen´ı kˇ rivky
Po zad´an´ı definiˇcn´ıch bod˚ u Qi se pro modelov´an´ı kˇrivky postupuje takto: Zaˇcneme s urˇcen´ım vektoru parametrizace vybranou metodou z Kapitoly 2. V t´eto pr´aci jsou uvedeny dvˇe metody z´avisl´e na definiˇcn´ıch bodech (tˇetivov´a, dostˇrediv´a) a jedna metoda nez´avisl´a na definiˇcn´ıch bodech (uniformn´ı). D´ale postupujeme v´ ypoˇctem uzlov´eho vektoru, kter´ y napˇr´ıklad m˚ uˇze b´ yt z´avisl´ y na definiˇcn´ıch bodech (tˇeˇziˇst’ov´ y) nebo na vektoru parametrizace (pr˚ umˇerov´ y). Uzlov´ y vektor n´am urˇc´ı poˇcet segment˚ u kˇrivky. Metody jsou opˇet uvedeny v Kapitole 2. V dalˇs´ım kroku mus´ıme urˇcit B-spline b´azov´e funkce p-t´eho stupnˇe, kter´e jsou d´any rekurentn´ım vzorcem (1) a (2). Tedy je zapotˇreb´ı nejdˇr´ıve spoˇc´ıtat B-spline b´azov´e funkce 0. stupnˇe, d´ıky kter´ ym se postupnˇe dopracujeme k b´azov´ ym funkc´ım dalˇs´ıch stupˇ n˚ u. Poˇc´ıt´ame, dokud nedostaneme funkce stupnˇe p. V dalˇs´ım kroku mus´ıme urˇcit v´ahy ˇr´ıd´ıc´ıch bod˚ u, jestliˇze chceme z´ıskat racion´aln´ı b´azov´e funkce p-t´eho stupnˇe pro pr´aci s NURBS kˇrivkami. Bez tohoto kroku by se jednalo pouze o B-spline kˇrivky, kde se povaˇzuj´ı v´ahy ˇr´ıd´ıc´ıch bod˚ u za jednotkov´e nebo stejn´e. Pro urˇcen´ı vah ˇr´ıdic´ıch bod˚ u v t´eto pr´aci uv´ad´ıme metodu tˇeˇziˇst’ovou, jej´ıˇz definice je obsaˇzena v Kapitole 2. Racion´aln´ı b´azov´e funkce jdou d´any vzorcem (3). Nyn´ı pˇrich´az´ı na ˇradu urˇcit ˇr´ıd´ıc´ı body, a to ze soustavy rovnic (5). Lev´a matice soustavy je d´ana funkˇcn´ımi hodnotami racion´aln´ıch b´azov´ ych funkc´ı v jednotliv´ ych parametrech hi . Z algebraick´eho hlediska n´am vznikne tˇr´ıdiagon´aln´ı matice. Prav´ y vektor soustavy je posloupnost zadan´ ych definiˇcn´ıch bod˚ u. Hledan´ ym vektorem soustavy je posloupnost ˇr´ıd´ıc´ıch bod˚ u. Tyto body pouˇzijeme pro analytick´e vyj´adˇren´ı prost´e interpolaˇcn´ı NURBS kˇrivky p-t´eho stupnˇe podle pˇredpisu (4).
4
2
Tvarovac´ı n´ astroje
Vektor parametrizace H a uzlov´ y vektor U maj´ı hlavn´ı vliv na v´ ysledn´ y tvar NURBS kˇrivky. Tyto dva vektory lze sestrojit z´avisle i nez´avisle na sobˇe. Definice v t´eto kapitole jsou ze zdroje [1] a [3].
2.1 2.1.1
Uzlov´ y vektor Uniformn´ı uzlov´ y vektor
Uniformn´ı uzlov´ y vektor nen´ı z´avisl´ y na hodnot´ach vektoru parametrizace ani na definiˇcn´ıch bodech. Jeho uzlov´e rozteˇce jsou vˇsechny stejn´e d´elky, proto se uzlov´ y vektor naz´ yv´a uniformn´ı. Definice 7 (Uniformn´ı uzlov´ y vektor prost´ e interpolaˇ cn´ı NURBS kˇ rivky) Necht’ n n p. Potom jsou uzly uniformn´ıho uzlov´eho vektoru je d´an definiˇcn´ı polygon (Qi )i=0 a stupeˇ m U = (ui )i=0 prost´e interpolaˇcn´ı NURBS kˇrivky
ui =
0,
i = 0, . . . , p i = p + 1, . . . , m − p − 1 1, i = m − p, . . . , m,
i−p , m−2p
(6)
kde m=n+p+1 je poˇcet uzlov´ych rozteˇc´ı. 2.1.2
Pr˚ umˇ erov´ y uzlov´ y vektor
Podle t´eto metody spoˇc´ıt´ame pr˚ umˇery hodnot parametr˚ u vektoru parametrizace, kter´e tvoˇr´ı vnitˇrn´ı uzly uzlov´eho vektoru. Krajn´ı uzly z˚ ust´avaj´ı nezmˇenˇeny a pr˚ umˇerov´ y uzlov´ y vektor je tedy z´avisl´ y na parametrech vektoru parametrizace. Definice 8 (Pr˚ umˇ erov´ y uzlov´ y vektor prost´ e interpolaˇ cn´ı NURBS kˇ rivky) Necht’ n je d´an vektor parametrizace H = (hi )i=0 interpolaˇcn´ı NURBS kˇrivky a stupeˇ n p. Potom m jsou uzly pr˚ umˇerov´eho uzlov´eho vektoru U = (ui )i=0 prost´e interpolaˇcn´ı kˇrivky ui = 0, i = 0, . . . , p i−1 1 X hj , i = p + 1, . . . , m − p − 1 ui = p j=i−p
(7)
ui = 1, i = m − p, . . . , m, kde m=n+p+1 je poˇcet uzlov´ych rozteˇc´ı. 2.1.3
Tˇ eˇ ziˇ st’ov´ y uzlov´ y vektor
Tato metoda je nez´avisl´a na vektoru parametrizace, avˇsak pro v´ ypoˇcet jsou potˇreba de’ finiˇcn´ı body. Tyto body jsou pouˇzity pro v´ ypoˇcet tˇeˇziˇst . Proto se takto sestrojen´ y uzlov´ y vektor naz´ yv´a tˇeˇziˇst’ov´ y. 5
Definice 9 (Tˇ eˇ ziˇ st’ov´ y uzlov´ y vektor prost´ e interpolaˇ cn´ı NURBS kˇ rivky) Necht’ n n p a necht’ Ti , je tˇeˇziˇstˇe je d´an definiˇcn´ı polygon (Qi )i=0 interpolaˇcn´ı NURBS kˇrivky, stupeˇ d´ılˇc´ıho definiˇcn´ıho polygonu T 0 = Q0 , i+p 1 X Qj , i = 1, . . . , n − p Ti = p + 2 j=i−1
(8)
Tn−p+1 = Qn . Potom jsou uzly tˇeˇziˇst’ov´eho uzlov´eho vektoru U = (ui )m interpolaˇcn´ı NURBS kˇrivky i=0 ui = 0, i = 0, . . . , p i−p
1X lj , i = p + 1, . . . , m − p − 1 ui = L j=1
(9)
ui = 1, i = m − p, . . . , m, kde li , i = 1,. . . , n-p, je vzd´alenost dvou po sobˇe n´asleduj´ıc´ıch tˇeˇziˇst’ a L je souˇcet vˇsech tˇechto vzd´alenost´ı. m=n+p+1 je poˇcet uzlov´ych rozteˇc´ı.
2.2 2.2.1
Vektor parametrizace Uniformn´ı vektor parametrizace
Vektor parametrizace se naz´ yv´a uniformn´ı, protoˇze vzd´alenosti hodnot parametr˚ u jsou stejn´e. Hodnoty jsou stanoveny nez´avisle na geometrii definiˇcn´ıho polygonu. Definice 10 (Uniformn´ı vektor parametrizace interpolaˇ cn´ı NURBS kˇ rivky) Necht’ n je d´an definiˇcn´ı polygon (Qi )i=0 interpolaˇcn´ı NURBS kˇrivky. Potom jsou hodnoty parametru uniformn´ıho vektoru parametrizace H = (hi )ni=0 interpolaˇcn´ı NURBS kˇrivky hi = 2.2.2
i , i = 0, . . . , n. n
(10)
Tˇ etivov´ y vektor parametrizace
Tato metoda patˇr´ı mezi nejrozˇs´ıˇrenˇejˇs´ı a snaˇz´ı se pˇribl´ıˇzit obecnou parametrizaci kˇrivky na pˇrirozenou parametrizaci obloukem. Parametry jsou z´avisl´e na geometrii definiˇcn´ıho polygonu, pˇresnˇeji na d´elk´ach ramen tohoto polygonu. Definice 11 (Tˇ etivov´ y vektor parametrizace interpolaˇ cn´ı NURBS kˇ rivky) Necht’ n je d´an definiˇcn´ı polygon (Qi )i=0 interpolaˇcn´ı NURBS kˇrivky. Potom jsou hodnoty parametru tˇetivov´eho vektoru parametrizace H = (hi )ni=0 interpolaˇcn´ı NURBS kˇrivky h0 = 0, Pi j=1 |Qj−1 Qj | hi = Pn , i = 1, . . . , n. j=1 |Qj−1 Qj | 6
(11)
2.2.3
Dostˇ rediv´ y vektor parametrizace
Tato metoda je rozˇs´ıˇren´ım tˇetivov´e metody, kdy dostˇrediv´ y vektor parametrizace omez´ı pˇrekmity, kter´e vznikaj´ı pˇri ostr´ ych zlomech definiˇcn´ıho polygonu. Definice 12 (Dostˇ rediv´ y vektor parametrizace interpolaˇ cn´ı NURBS kˇ rivky) Necht’ n je d´an definiˇcn´ı polygon (Qi )i=0 interpolaˇcn´ı NURBS kˇrivky. Potom jsou hodnoty parametru dostˇrediv´eho vektoru parametrizace H = (hi )ni=0 interpolaˇcn´ı NURBS kˇrivky h0 = 0, Pi
q
hi = P n
q
j=1
j=1
2.3
|Qj−1 Qj |
, i = 1, . . . , n.
(12)
|Qj−1 Qj |
V´ ahy ˇ r´ıd´ıc´ıch bod˚ u
NURBS kˇrivky se liˇs´ı od B-spline kˇrivek t´ım, ˇze kaˇzd´emu ˇr´ıd´ıc´ımu bodu Pi je pˇriˇrazena v´aha wi . U B-spline kˇrivek jsou vˇsechny v´ahy jednotkov´e nebo stejn´e. Se zvyˇsov´an´ım v´ahy wi se pˇr´ısluˇsn´ y ˇr´ıd´ıc´ı bod Pi pˇribliˇzuje k definiˇcn´ımu bodu Qi . Tento efekt plat´ı u interpolaˇcn´ı NURBS kˇrivky. Pˇri zvyˇsov´an´ı vah tak´e doch´az´ı k tlumen´ı pˇrekmit˚ u a oscilac´ı. ’ V t´eto pr´aci uvedeme jednu metodu (tˇeˇziˇst ovou) urˇcen´ı vah, kter´a kˇrivce poskytuje lepˇs´ı pr˚ ubˇeh neˇz n´ahodn´e zad´an´ı vah. Definice 13 (Tˇ eˇ ziˇ st’ov´ e v´ ahy ˇ r´ıdic´ıch bod˚ u prost´ e interpolaˇ cn´ı kˇ rivky) Necht’ je n d´an definiˇcn´ı polygon (Qi )i=0 prost´e interpolaˇcn´ı NURBS kˇrivky a necht’ n
1 X Qi T= n + 1 i=0 je tˇeˇziˇstˇe definiˇcn´ıho polygonu. Potom je tˇeˇziˇst’ov´a v´aha ˇr´ıd´ıc´ıho bodu Pi p wi = |Qi T|, i = 0, . . . , n.
7
(13)
(14)
3
Konstrukce prost´ e interpolaˇ cn´ı NURBS kˇ rivky
V t´eto kapitole uvedeme detailn´ı postup konstrukce interpolaˇcn´ı NURBS kˇrivky 3. stupnˇe, kter´a je zad´ana 9-ti definiˇcn´ımi body Q0 = [1; 2], Q1 = [3; 2], Q2 = [5; 3, 5], Q3 = [4; 5], Q4 = [7; 5], Q5 = [9, 5; 3, 5], Q6 = [11; 4], Q7 = [13; 3], Q8 = [12; 2]. V´ahy definiˇcn´ıch bod˚ u urˇc´ıme tˇeˇziˇst’ovou metodou. Uzlov´ y vektor na intervalu h0, 1i sestroj´ıme jako uniformn´ı. Vektor parametrizace na stejn´em intervalu u ∈ h0, 1i urˇc´ıme metodou uniformn´ı, tˇetivovou a dostˇredivou, abychom n´aslednˇe vlastnosti tˇechto metod porovnali v Kapitole 4.
3.1 3.1.1
Vektor parametrizace Uniformn´ı vektor parametrizace
Pomoc´ı vztahu (10) urˇc´ıme uniformn´ı vektor parametrizace Hu = (0; 0, 125; 0, 25; 0, 375; 0, 5; 0, 625; 0, 75; 0, 875; 1). 3.1.2
(15)
Tˇ etivov´ y vektor parametrizace
Podle vzorce (11) dost´av´ame tˇetivov´ y vektor parametrizace Ht = (0; 0, 11; 0, 26; 0, 36; 0, 53; 0, 7; 0, 79; 0, 92; 1). 3.1.3
(16)
Dostˇ rediv´ y vektor parametrizace
Nakonec podle (12) dost´av´ame dostˇrediv´ y vektor parametrizace Hd = (0; 0, 12; 0, 26; 0, 37; 0, 52; 0, 66; 0, 77; 0, 9; 1).
3.2
Uzlov´ y vektor
Uniformn´ı uzlov´ y vektor vypoˇc´ıt´ame z rovnic (6) 1 1 1 2 5 U = 0; 0; 0; 0; ; ; ; ; ; 1; 1; 1; 1. . 6 3 2 3 6
3.3
(17)
(18)
B´ azov´ e funkce
Nejprve potˇrebujeme z´ıskat B-spline b´azov´e funkce 0. stupnˇe. K tomu pouˇzijeme vzorec (1). Funkce jsou pouze jednotkov´e nebo nulov´e a jsou zobrazeny na Obr´azku 2. N0,0 (u) = 0, u ∈ h0, 1i N1,0 (u) = 0, u ∈ h0, 1i N2,0 (u) = 0, u ∈ h0, 1i 1, u ∈ h0, 16 ) N3,0 (u) = 0, u ∈ h 16 , 1i 8
0, 1, N4,0 (u) = 0, 0, 1, N5,0 (u) = 0, 0, 1, N6,0 (u) = 0, 0, 1, N7,0 (u) = 0, 0, N8,0 (u) = 1,
u ∈ h0, 16 ) u ∈ h 16 , 13 ) u ∈ h 31 , 1) u ∈ h0, 13 ) u ∈ h 13 , 12 ) u ∈ h 21 , 1) u ∈ h0, 12 ) u ∈ h 12 , 23 ) u ∈ h 32 , 1) u ∈ h0, 23 ) u ∈ h 23 , 56 ) u ∈ h 65 , 1) u ∈ h0, 56 ) u ∈ h 16 , 1i
N9,0 (u) = 0, u ∈ h0, 1i N10,0 (u) = 0, u ∈ h0, 1i N11,0 (u) = 0, u ∈ h0, 1i
Obr´azek 2: B´azov´e funkce 0. stupnˇe 9
Pokud do rekurentn´ıho vzorce (2) dosad´ıme k=1, dostaneme B-spline b´azov´e funkce 1. stupnˇe, kter´e maj´ı line´arn´ı pr˚ ubˇeh a jsou zobrazeny na Obr´azku 3. N0,1 (u) = 0, u ∈ h0, 1i N1,1 (u) = 0, u ∈ h0, 1i 1 − 6u, u ∈ h0, 61 ) N2,1 (u) = 0, u ∈ h 16 , 1i 6u, u ∈ h0, 61 ) 2 − 6u, u ∈ h 16 , 31 ) N3,1 (u) = 0, u ∈ h 13 , 1i 0, u ∈ h0, 61 ) 6u − 1, u ∈ h 16 , 31 ) N4,1 (u) = 3 − 6u, u ∈ h 13 , 21 ) 0, u ∈ h 12 , 1i 0, u ∈ h0, 31 ) 6u − 2, u ∈ h 13 , 21 ) N5,1 (u) = 4 − 6u, u ∈ h 12 , 32 ) 0, u ∈ h 23 , 1i 0, u ∈ h0, 21 ) 6u − 3, u ∈ h 12 , 32 ) N6,1 (u) = 5 − 6u, u ∈ h 23 , 65 ) 0, u ∈ h 56 , 1i 6u − 4, u ∈ h0, 32 ) 6 − 6u, u ∈ h 23 , 65 ) N7,1 (u) = 0, u ∈ h 65 , 1) 0, u ∈ h0, 56 ) N8,1 (u) = 6u − 5, u ∈ h 56 , 1i N9,1 (u) = 0, u ∈ h0, 1i N10,1 (u) = 0, u ∈ h0, 1i Pro z´ısk´an´ı B-spline b´azov´ ych funkc´ı 2. stupnˇe, pouˇzijeme stejn´ y vzorec (2), do kter´eho dosad´ıme k=2. Funkce jsou vyj´adˇreny kvadratick´ ymi polynomy na Obr´azku 4. N0,2 (u) = 0, u ∈ h0, 1i N1,2 (u) =
(6u − 1)2 , u ∈ h0, 16 ) 0, u ∈ h 16 , 1i
−54u2 + 12u, u ∈ h0, 16 ) 2(3u − 1)2 , u ∈ h 16 , 31 ) N2,2 (u) = 0, u ∈ h 13 , 1i 10
Obr´azek 3: B´azov´e funkce 1. stupnˇe 18u2 , 2 −36u + 18u − 32 , 9 N3,2 (u) = (2u − 1)2 , 2 0, 0, 1 (6u − 1)2 , 2 2 −36u − 30u − 11 , N4,2 (u) = 2 2 2(3u − 2) , 0, 0, 2(3u − 2)2 , −36u2 + 42u − 23 , N5,2 (u) = 2 1 2 (6u − 5) , 2 0, 0, 9 (2u − 1)2 , N6,2 (u) = 2 −36u2 + 54u − 39 , 2 2 18(u − 1) , 11
u ∈ h0, 61 ) u ∈ h 16 , 13 ) u ∈ h 13 , 12 ) u ∈ h 21 , 1i u ∈ h0, 16 ) u ∈ h 16 , 13 ) u ∈ h 13 , 12 ) u ∈ h 12 , 23 ) u ∈ h 23 , 1i u ∈ h0, 13 ) u ∈ h 13 , 12 ) u ∈ h 12 , 23 ) u ∈ h 32 , 56 ) u ∈ h 65 , 1i u ∈ h0, 12 ) u ∈ h 21 , 23 ) u ∈ h 23 , 56 ) u ∈ h 65 , 1i
0, u ∈ h0, 23 ) 2(3u − 2)2 , u ∈ h 23 , 65 ) N7,2 (u) = 2 −54u + 96u − 42, u ∈ h 56 , 1) 0, u ∈ h0, 56 ) N8,2 (u) = (6u − 5)2 , u ∈ h 65 , 1i N9,2 (u) = 0, u ∈ h0, 1i
Obr´azek 4: B´azov´e funkce 2. stupnˇe Jako posledn´ı spoˇc´ıt´ame B-spline b´azov´e funkce 3. stupnˇe ze vzorce (2) pro k=3. Funkce jsou polynomy 3. stupnˇe a jejich pr˚ ubˇeh je vyj´adˇren na Obr´azku 5. −(6u − 1)3 , u ∈ h0, 16 ) N0,3 (u) = 0, u ∈ h 16 , 1i 378u3 − 162u2 + 18u, u ∈ h0, 61 ) −2(3u − 1)3 , u ∈ h 61 , 31 ) N1,3 (u) = 0, u ∈ h 13 , 1i −198u3 + 54u2 , u ∈ h0, 61 ) 3 126u − 108u2 + 27u − 23 , u ∈ h 16 , 13 ) N2,3 (u) = − 92 (2u − 1)3 , u ∈ h 31 , 12 ) 0, u ∈ h 21 , 1i 12
36u3 , u ∈ h0, 61 ) 3 + 72u2 − 12u + 32 , u ∈ h 16 , 13 ) −108u 3 , u ∈ h 13 , 12 ) 108u − 144u2 + 60u − 22 3 N3,3 (u) = 4 − (3u − 2)3 , u ∈ h 21 , 23 ) 3 0, u ∈ h 32 , 1i
N4,3 (u) =
N5,3 (u) =
0, 1 (6u − 1)3 , 6 −108u3 + 126u2 − 45u + 31 , 6 108u3 − 198u2 + 117u − 131 , 6 − 16 (6u − 5)3 , 0,
u ∈ h0, 16 ) u ∈ h 16 , 13 ) u ∈ h 13 , 12 ) u ∈ h 12 , 23 ) u ∈ h 23 , 56 ) u ∈ h 65 , 1i
0, u ∈ h0, 13 ) − 1)3 , u ∈ h 13 , 12 ) −108u3 + 180u2 − 96u + 50 , u ∈ h 12 , 23 ) 3 142 108u3 − 252u2 + 192u − 3 , u ∈ h 23 , 56 ) −36(u − 1)3 , u ∈ h 56 , 1i 4 (3u 3
0, u ∈ h0, 12 ) 9 (2u − 1)3 , u ∈ h 12 , 32 ) 2 N6,3 (u) = , u ∈ h 23 , 65 ) −126u3 + 270u2 − 189u + 87 2 3 2 198u − 540u + 486u − 144, u ∈ h 65 , 1i
0, u ∈ h0, 23 ) 2(3u − 2)3 , u ∈ h 23 , 56 ) N7,3 (u) = −378u3 + 972u2 − 828u + 234, u ∈ h 56 , 1) N8,3 (u) =
3.4
0, u ∈ h0, 56 ) (6u − 5)3 , u ∈ h 56 , 1i
Tˇ eˇ ziˇ st’ov´ e v´ ahy definiˇ cn´ıch bod˚ u a racion´ aln´ı b´ azov´ e funkce
Podle vzorce (13) spoˇc´ıt´ame tˇeˇziˇstˇe z definiˇcn´ıch bod˚ u Qi . 8
1 1X T= Qi = ([1; 2] + [3; 2] + [5; 3, 5] + [4; 5] + [7; 5] + [9, 5; 3, 5] + [11; 4] + [13; 3]+ 9 i=0 9 . + [12; 2]) = [7, 28; 3, 33] 13
Obr´azek 5: B´azov´e funkce 3. stupnˇe Pouˇzit´ım tˇeˇziˇstˇe a definiˇcn´ıch bod˚ u vypoˇc´ıt´ame v´ahy wi ˇr´ıdic´ıch bod˚ u Pi podle vzorce (14). qp p . (7, 28 − 1)2 + (3, 33 − 2)2 = 2, 53 w0 = |Q0 T| = qp p . w1 = |Q1 T| = (7, 28 − 3)2 + (3, 33 − 2)2 = 2, 12 qp p . w2 = |Q2 T| = (7, 28 − 5)2 + (3, 33 − 3, 5)2 = 1, 51 qp p . w3 = |Q3 T| = (7, 28 − 4)2 + (3, 33 − 5)2 = 1, 92 qp p . w4 = |Q4 T| = (7, 28 − 7)2 + (3, 33 − 5)2 = 1, 3 qp p . w5 = |Q5 T| = (7, 28 − 9.5)2 + (3, 33 − 3, 5)2 = 1, 5 qp p . w6 = |Q6 T| = (7, 28 − 11)2 + (3, 33 − 4)2 = 1, 94 qp p . (7, 28 − 13)2 + (3, 33 − 3)2 = 2, 39 w7 = |Q7 T| = qp p . w8 = |Q8 T| = (7, 28 − 13)2 + (3, 33 − 3)2 = 2, 21
14
Nyn´ı vyj´adˇr´ıme racion´aln´ı b´azov´e funkce 3. stupnˇe pomoc´ı vzorce (3) pro p=3. Funkce jsou vyj´adˇreny jako racion´aln´ı a jejich pr˚ ubˇeh je zobrazen na Obr´azku 6. ( −2,53(6u−1)3 , u ∈ h0, 61 ) 22,74u3 +12,29u2 −7,5u+2,53 R0,3 (u) = 0, u ∈ h 16 , 1i
R1,3 (u) =
R2,3 (u) =
R3,3 (u) =
R4,3 (u) =
R5,3 (u) =
R6,3 (u) =
R7,3 (u) =
2,12(378u3 −162u2 +18u ), 22,74u3 +12,29u2 −7,5u+2,53 −4,24(3u−1)3 , −84,19u3 +65,76u2 −16,4u+3,03
u ∈ h0, 61 )
1,51(−198u3 +54u2 ) , 22,74u3 +12,29u2 −7,5u+2,53 1,51(126u3 −108u2 +27u− 32 ) , −84,19u3 +65,76u2 −16,4u+3,03 3 − 13,59 (2u−1) 2 , 66,05u3 −84,48u2 +33,67u−2,54
u ∈ h0, 61 )
u ∈ h 61 , 13 ) 0, u ∈ h 31 , 1i u ∈ h 61 , 13 )
u ∈ h 31 , 12 ) 0, u ∈ h 21 , 1i
69,12u3 , 22,74u3 +12,29u2 −7,5u+2,53 2 3 2 1,92(−108u +72u −12u+ 3 ) , −84,19u3 +65,76u2 −16,4u+3,03 1,92(108u3 −144u2 +60u− 22 ) 3 , 66,05u3 −84,48u2 +33,67u−2,54 3 (3u−2) − 7,68 3 , −19,87u3 +44,39u2 −30,77u+8,2
u ∈ h0, 61 ) u ∈ h 61 , 13 ) u ∈ h 31 , 12 )
u ∈ h 21 , 23 ) 0, u ∈ h 32 , 1i u ∈ h0, 61 )
0, 1,3 (6u−1)3 6 3 −84,19u +65,76u2 −16,4u+3,03 1,3(−108u3 +126u2 −45u+ 31 ) 6 66,05u3 −84,48u2 +33,67u−2,54 1,3(108u3 −198u2 +117u− 131 ) 6 −19,87u3 +44,39u2 −30,77u+8,2 (6u−5)3 − 1,3 6 3 −1,3u +7,27u2 −6,02u+2,7
, u ∈ h 61 , 13 ) , u ∈ h 31 , 12 ) , u ∈ h 21 , 23 )
, u ∈ h 32 , 56 ) 0, u ∈ h 65 , 1i
0, 2(3u−1)3 ) , 66,05u3 −84,48u2 +33,67u−2,54
u ∈ h0, 31 ) u ∈ h 31 , 12 )
1,5(−108u3 +180u2 −96u+ 50 ) 3 , −19,87u3 +44,39u2 −30,77u+8,2 1,5(108u3 −252u2 +192u− 142 ) 3 , −1,3u3 +7,27u2 −6,02u+2,7 3 −54(u−1) , −95,23u3 +242,07u2 −201,69u+57,06
u ∈ h 56 ), 1i
0,
u ∈ h0, 21 )
17,46 (2u−1)3 2 −19,87u3 +44,39u2 −30,77u+8,2 1,94(−126u3 +270u2 −189u+ 87 ) 2 −1,3u3 +7,27u2 −6,02u+2,7 1,94(198u3 −540u2 +486u−144)
−95,23u3 +242,07u2 −201,69u+57,06
u ∈ h 21 , 23 ) u ∈ h 32 , 56 )
, u ∈ h 21 ), 23 ) ,
u ∈ h 32 , 56 )
,
u ∈ h 65 , 1i
0, u ∈ h0, 23 ) , u ∈ h 23 , 56 ) −1,3u3 +7,27u2 −6,02u+2,7 4,78(3u−2)3
2,39(−378u3 +972u2 −828u+234) , −95,23u3 +242,07u2 −201,69u+57,06
15
u ∈ h 65 , 1i
( R8,3 (u) =
0, u ∈ h0, 56 ) , u ∈ h 56 , 1i −95,23u3 +242,07u2 −201,69u+57,06 2,21(6u−5)3
Obr´azek 6: Racion´aln´ı b´azov´e funkce 3. stupnˇe
3.5
V´ ypoˇ cet ˇ r´ıdic´ıch bod˚ u
Pro v´ ypoˇcet ˇr´ıdic´ıch bod˚ u Pi sestav´ıme soustavu rovnic (5) jej´ıˇz maticov´ y tvar je P0 R0,3 (h0 ) R1,3 (h0 ) · · · R7,3 (h0 ) R8,3 (h0 ) Q0 R0,3 (h1 ) R1,3 (h1 ) · · · R7,3 (h1 ) R8,3 (h1 ) P1 Q1 R0,3 (h2 ) R1,3 (h2 ) · · · R7,3 (h2 ) R8,3 (h2 ) P2 Q2 R0,3 (h3 ) R1,3 (h3 ) · · · R7,3 (h3 ) R8,3 (h3 ) P3 Q3 R0,3 (h4 ) R1,3 (h4 ) · · · R7,3 (h4 ) R8,3 (h4 ) . P4 = Q4 . R0,3 (h5 ) R1,3 (h5 ) · · · R7,3 (h5 ) R8,3 (h5 ) P5 Q5 R0,3 (h6 ) R1,3 (h6 ) · · · R7,3 (h6 ) R8,3 (h6 ) P6 Q6 R0,3 (h7 ) R1,3 (h7 ) · · · R7,3 (h7 ) R8,3 (h7 ) P7 Q7 R0,3 (h8 ) R1,3 (h8 ) · · · R7,3 (h8 ) R8,3 (h8 ) P8 Q8
16
Lev´a matice soustavy obsahuje v ˇra´dc´ıch racion´aln´ı b´azov´e funkce 3. stupnˇe jednotliv´ ych segment˚ u kˇrivky R0,3 aˇz po R8,3 . V i-t´em ˇr´adku dosad´ıme do tˇechto funkc´ı hodnotu parametru hi . Prav´a matice je urˇcena z definiˇcn´ıch bodu Q0 aˇz Q8 . Nezn´am´ y vektor soustavy pˇredstavuje hledan´e ˇr´ıd´ıc´ı body P0 aˇz P8 . Jestliˇze do racion´aln´ıch funkc´ı dosad´ıme hodnoty parametru uniformn´ıho vektoru parametrizace (15), dost´av´ame matici 1 0 0 0, 021 0, 528 0, 377 0 0, 038 0, 412 0 0 0, 063 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0, 073 0, 534 0, 693 0, 223 0, 003 0 0 0
0 0 0, 157 0, 242 0, 604 0, 279 0, 016 0 0
0 0 0 0 P0 [1; 2] 0 0 0 0 P1 [3; 2] P2 [5; 3, 5] 0 0 0 0 0, 002 0 0 0) P3 [4; 5] 0, 173 0 0 0 . P4 = [7; 5] . P5 [9, 5; 3, 5] 0, 624 0, 093 0 0 P6 [11; 4] 0, 414 0, 527 0, 0433 0 0, 495 0, 419 0, 516 0, 016 P7 [13; 3] 0 0 0 1 P8 [12; 2]
Dosazen´ım hodnot tˇetivov´eho vektoru parametrizace (16) dost´av´ame matici 1 0 0 0 0 0 0, 041 0, 57 0, 332 0, 056 0 0 0 0, 028 0, 386 0, 565 0, 021 0 0 0 0, 085 0, 716 0, 198 0 0 0 0 0, 117 0, 583 0, 299 0 0 0 0 0, 069 0, 586 0 0 0 0 0, 002 0, 258 0 0 0 0 0 0, 013 0 0 0 0 0 0
0 0 0 P0 [1; 2] 0 0 0 P1 [3; 2] 0 0 0 P2 [5; 3, 5] 0 0 0 P3 [4; 5] 0, 009 0 0 . P4 = [7; 5] . 0, 342 0, 003 0 P5 [9, 5; 3, 5] 0, 606 0, 134 0 P6 [11; 4] 0, 216 0, 637 0, 134 P7 [13; 3] 0 0 1 P8 [12; 2]
Soustava rovnic s dosazen´ ym dostˇrediv´ ym vektorem parametrizace (17) je d´ana 1 0 0 0 0, 029 0, 547 0, 357 0, 066 0 0, 031 0, 394 0, 556 0 0 0, 07 0, 702 0 0 0 0, 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0, 019 0, 226 0, 602 0, 15 0, 006 0 0
P0 [1; 2] 0 0 0 0 0 0 0 0 P1 [3; 2] 0 0 0 0 P2 [5; 3, 5] P3 [4; 5] 0, 002 0 0 0 P4 = [7; 5] . 0, 238 0 0 0 . 0, 65 0, 2 0 0 P5 [9, 5; 3, 5] 0, 332 0, 58 0, 082 0 P6 [11; 4] [13; 3] 0, 025 0, 31 0, 604 0, 605 P7 [12; 2] 0 0 0 1 P8
Po v´ ypoˇctu tˇechto soustav z´ısk´ame tˇri r˚ uzn´e posloupnosti ˇr´ıdic´ıch bod˚ u Pi . Tabulka 1 ukazuje vypoˇcten´e ˇr´ıd´ıc´ı body vˇsemi tˇremi metodami, kter´e jsme pouˇzili. M˚ uˇzeme si vˇsimnout, ˇze ˇr´ıd´ıc´ı body P0 a P8 jsou totoˇzn´e s definiˇcn´ımi body Q0 a Q8 . Tento v´ ysledek jsme z´ıskali, protoˇze se zab´ yv´ame ukotven´ ymi kˇrivkami.
17
P0 P1 P2 P3 P4 P5 P6 P7 P8
uniformn´ı [1; 2] [-1,22; 1,85] [9,19; 1,57] [2,13; 5,04] [7,96; 5,81] [9,9; 2,13] [11,67; 5,66] [14,41; 0,95] [12; 2]
tˇ etivov´ y [1; 2] [-0,19; 2,2] [8,79; 1,14] [2,6; 5,07] [7,01; 6,39] [8,68; 2,25] [11,37; 5,06] [13,85; 2,53] [12; 2]
dostˇ rediv´ y [1; 2] [-0,73; 2,09] [8,95; 1,3] [2,44; 5,05] [7,27; 6,01] [9,38; 2,4] [11,54; 5,17] [14; 2.01] [12; 2]
Tabulka 1: Vypoˇcten´e ˇr´ıd´ıc´ı body NURBS kˇrivek
3.6
Analytick´ e vyj´ adˇ ren´ı NURBS kˇ rivky
Nyn´ı n´am zb´ yv´a podle vzorce (4) z´ıskat parametrick´e vyj´adˇren´ı prost´e interpolaˇcn´ı NURBS kˇrivky 3. stupnˇe s uniformn´ım uzlov´ ym vektorem. Po dosazen´ı do (19) z´ısk´ame vektorovou funkci prost´e interpolaˇcn´ı NURBS kˇrivky s uniformn´ım vektorem parametrizace. C(u) =
8 X
Ri,3 (u)Pi = R0,3 (u)P0 + R1,3 (u)P1 + R2,3 (u)P2 + R3,3 (u)P3 + R4,3 (u)P4 +
i=0
+ R5,3 (u)P5 + R6,3 (u)P6 + R7,3 (u)P7 + R8,3 (u)P8 .
(19)
Funkce (20) a (21) urˇcuj´ı parametrick´e vyj´adˇren´ı prost´e interpolaˇcn´ı NURBS kˇrivky. Na Obr´azku 7 vid´ıme grafick´ y v´ ysledek. −4126,69u3 +1441,84u2 −92,04u+2,53 , u ∈ h0; 61 ) 22,75u3 +12,29u2 −7,5u+2,53 1822,23u3 −1532,62u2 +403,7u−25 , u ∈ h 61 ; 13 ) −84,19u3 +65,76u2 −16,41u+3,03 3 2 −645,42u +935,03u −418,84u+66,39 , u ∈ h 31 ; 12 ) . 66,05u3 −84,48u2 +33,67u−2,54 (20) x(u) = 191,28u3 −320,02u2 +208,68u−38,2 1 2 , u ∈ h ; ) 3 2 −19,87u +44,39u −30,77u+8,2 2 3 227,58u3 −392,62u2 +257,08u−48,96 2 5 , u ∈ h ; ) 3 2 −1,31u +7,27u −6,02u+2,7 3 6 3 2 −7169,06u+2013,86 5 −3336,97u +8518,75u , u ∈ h 6 ; 1i −95,23u3 +242,07u2 −201,69u+57,06 292,62u3 +28,7u2 −19,37u+5,07 , u ∈ h0; 16 ) 22,75u3 +12,29u2 −7,5u+2,53 −688,42u3 +519,22u2 −101,13u+9,6 , u ∈ h 61 ; 31 ) −84,19u3 +65,76u2 −16,41u+3,03 257,11u3 −426,13u2 +214,05u−25,41 , u ∈ h 13 ; 21 ) . 66,05u3 −84,48u2 +33,67u−2,54 y(u) = (21) 3 2 520,27u −821,05u +411,42u−58,31 u ∈ h 21 ; 32 ) 3 +44,39u2 −30,77u+8,2 , −19,87u 3 +2603,52u2 −1871,62u+449,04 −1192,02u , u ∈ h 23 ; 65 ) −1,31u3 +7,27u2 −6,02u+2,7 3 2 +5111,39u−1490,69 2159,83u −5776,1u , u ∈ h 56 ; 1i −95,23u3 +242,07u2 −201,69u+57,06
18
Obr´azek 7: Prost´a interpolaˇcn´ı NURBS kˇrivka 3. stupnˇe; uzlov´ y vektor uniformn´ı, vektor parametrizace uniformn´ı (zelen´a), tˇetivov´ y (modr´a), dostˇrediv´ y (ˇcerven´a)
19
4
Porovn´ an´ı metod interpolace
Pro lepˇs´ı pˇrehlednost, jsou v Tabulce 2 vˇsechny vytvoˇren´e metody sepsan´e a oˇc´ıslovan´e. ozn. uzlov´ y vektor 1 uniformn´ı 2 uniformn´ı 3 uniformn´ı 4 pr˚ umˇerov´ y 5 pr˚ umˇerov´ y 6 pr˚ umˇerov´ y 7 tˇeˇziˇst’ov´ y 8 tˇeˇziˇst’ov´ y ’ 9 tˇeˇziˇst ov´ y
vektor parametrizace uniformn´ı tˇetivov´ y dostˇrediv´ y uniformn´ı tˇetivov´ y dostˇrediv´ y uniformn´ı tˇetivov´ y dostˇrediv´ y
Tabulka 2: Tabulka vytvoˇren´ ych NURBS kˇrivek Metody, kter´ ymi interpolujeme NURBS kˇrivky, lze rozdˇelit do tˇr´ı skupin. Tyto skupiny jsou: velmi pˇresn´e metody (chyba ≤ 6%), stˇrednˇe pˇresn´e (6% < chyba ≤ 8%) a nepˇresn´e metody (8% < chyba). Do tˇechto skupin zaˇrad´ıme metody z Tabulky 2. Mezi velmi pˇresn´e metody se ˇrad´ı metoda oznaˇcen´a ˇc´ıslem 4 s pr˚ umˇerov´ ym uzlov´ ym vektorem a uniformn´ım vektorem parametrizace, kter´a je vidˇet na Obr´azku 10. Tato metoda je nejspolehlivˇejˇs´ı. Avˇsak metoda s ˇc´ıslem 6 s pr˚ umˇerov´ ym uzlov´ ym vektorem a dostˇrediv´ ym vektorem parametrizace je tak´e velmi pˇresn´a a m´a dobr´e v´ ysledky. Metodu ˇc´ıslo 6 zn´azorˇ nuje opˇet Obr´azek 10. Dalˇs´ı velmi pˇresnou metodou je ˇc´ıslo 9 s tˇeˇziˇst’ov´ ym uzlov´ ym vektorem a dostˇrediv´ ym vektorem parametrizace, kterou vid´ıme na Obr´azku 9. Stˇrednˇe pˇresn´e metody maj´ı tu nev´ yhodu, ˇze jsou z´avisl´e na tvaru definiˇcn´ıho polygonu. Tuto vlastnost m´a metoda oznaˇcena ˇc´ıslem 1 s uniformn´ım uzlov´ ym vektorem a uniformn´ım vektorem parametrizace. Pouˇzit´ı t´eto metody obsahuje Kapitola 3 a je zobrazena na Obr´azku 8. Nepˇresn´e metody jsou nespolehliv´e a nevhodn´e pro matematickou konstrukci. Do t´eto skupiny patˇr´ı ostatn´ı metody z Tabulky 2. Metoda oznaˇcena ˇc´ıslem 5 s pr˚ umˇerov´ ym uzlov´ ym vektorem a tˇetivov´ ym vektorem parametrizace je zn´azornˇena na Obr´azku 10. Metody s uniformn´ım uzlov´ ym vektorem s vektorem parametrizace tˇetivov´ ym s ˇc´ıslem 2 a dostˇrediv´ ym s ˇc´ıslem 3 ukazuje Obr´azek 8. A nakonec Obr´azek 9 zobrazuje metody s tˇeˇziˇst’ov´ ym uzlov´ ym vektorem a s vektory parametrizace uniformn´ım ˇc´ıslo 7 a tˇetivov´ ym ˇc´ıslo 8.
20
Obr´azek 8: Prost´a interpolaˇcn´ı NURBS kˇrivka 3. stupnˇe; uzlov´ y vektor uniformn´ı, vektor parametrizace uniformn´ı (zelen´a), tˇetivov´ y (modr´a), dostˇrediv´ y (ˇcerven´a)
Obr´azek 9: Prost´a interpolaˇcn´ı NURBS kˇrivka 3. stupnˇe; uzlov´ y vektor tˇeˇziˇst’ov´ y, vektor parametrizace uniformn´ı (zelen´a), tˇetivov´ y (modr´a), dostˇrediv´ y (ˇcerven´a)
21
Obr´azek 10: Prost´a interpolaˇcn´ı NURBS kˇrivka 3. stupnˇe; uzlov´ y vektor pr˚ umˇerov´ y, vektor parametrizace uniformn´ı (zelen´a), tˇetivov´ y (modr´a), dostˇrediv´ y (ˇcerven´a)
22
Z´ avˇ er V dneˇsn´ıch dobˇe vˇetˇsina geometrick´ ych a konstrukˇcn´ıch poˇc´ıtaˇcov´ ych aplikac´ı pracuje s NURBS kˇrivkami, protoˇze maj´ı v´ yhodnˇejˇs´ı vlastnosti oproti jin´ ym. Programy, kter´e s nimi pracuj´ı jsou napˇr´ıklad CAD, CAM, CAE, Rhinoceros... NURBS kˇrivky dok´aˇz´ı vymodelovat velk´e mnoˇzstv´ı tvar˚ u. K jejich nejvˇetˇs´ım v´ yhod´am patˇr´ı schopnost pˇresnˇe interpolovat kuˇzeloseˇcky. Tato vlastnost je zp˚ usobena racionalitou. Kˇrivkami, kter´e jsou pops´any polynomem, nelze napˇr´ıklad vytvarovat pˇresnˇe kruˇznici nebo elipsu. Algoritmy pro vykreslov´an´ı NURBS kˇrivek jsou tak´e rychl´e a numericky stabiln´ı. Vyuˇz´ıv´a se i toho, ˇze NURBS kˇrivky jsou invariantn´ı v˚ uˇci projektivn´ım transformac´ım. To znamen´a, ˇze pokud aplikujeme transformaci na kˇrivku zadanou ˇr´ıd´ıc´ımi body, dostaneme stejn´ y v´ ysledek, jako kdybychom konstruovali kˇrivku na stejnˇe transformovan´ ych ˇr´ıdic´ıch bodech. B-spline splˇ nuj´ı pouze afinn´ı invarianci. Obyˇcejn´ y interpolaˇcn´ı polynom proch´az´ı definiˇcn´ımi body, ale vznikaj´ı mezi nimi nepˇekn´e kmitaj´ıc´ı tvary, kter´e se pˇri vyˇsˇs´ıch stupn´ıch zhorˇsuj´ı. Tento probl´em dobˇre ˇreˇs´ı spline, kter´ y se skl´ad´a z v´ıce spojitˇe napojen´ ych kˇrivek n´ızk´ ych stupˇ n˚ u. B-spline jsou zad´any polynomy, nejsou racion´aln´ı a oznaˇcuj´ı se za speci´aln´ı pˇr´ıpad NURBS kˇrivek. Nejvhodnˇejˇs´ı a nejm´enˇe vhodn´e metody pro tvarov´an´ı interpolaˇcn´ıch NURBS kˇrivek jsme uvedli v posledn´ı kapitole t´eto pr´ace. Vˇsechny tyto metody jsou naprogramov´any v programu Maple. Soubory jsou souˇc´ast´ı pˇr´ılohy.
23
Pouˇ zit´ a literatura ´ Ivana. NURBS kˇrivky: NeUniformn´ı Racion´aln´ı B-Spline kˇrivky. Vyd. 1. [1] LINKEOVA, ˇ Praha: Nakladatelstv´ı CVUT, 2007, 208 s. ISBN 978-80-01-03893-2. [2] Piegl, Les. The NURBS book /Berlin :Springer-Verlag,1997. 2nd ed. xiv, 300 s : il. ISBN 3540615458 ´ Ivana. 2006. Interpolaˇcn´ı NURBS kˇrivky. 26. konference o geometrii [3] LINKEOVA, a poˇc´ıtaˇcov´e grafice. : 6. Dostupn´e tak´e z: http://marian.fsik.cvut.cz/∼linkeova/vyuka/pubic/novemesto2006 li.pdf [4] Kundr´atov´a, K. - Linkeov´a, I.: Interpolaˇcn´ı NURBS kˇrivky. Maple worksheet, port´al Puma, 2015. http://puma.feld.cvut.cz/cs/maple/17/Interpol%20NURBS%20krivka2.html
24
Seznam pouˇ zit´ ych symbol˚ u ha, bi (a, b) [a; b] |AB| C(u) hi H, (h0 , h1 , . . . , hn ), (hi )ni=0 Hu Ht Hd li L m n Ni,p (u) p Pi (Pi )ni=0 (Qi )ni=0 Qi R Ri,p (u) u T Ti U, (u0 , u1 , . . . , um ), (ui )m i=0 ui hui , ui+1 ) wi W, (w0 , w1 , . . . , wn ), (wi )ni=0 x(u), y(u)
uzavˇren´ y interval z mnoˇziny re´aln´ ych ˇc´ısel otevˇren´ y interval z mnoˇziny re´aln´ ych ˇc´ısel x-ov´a a y-ov´a souˇradnice bodu vzd´alenost dvou bod˚ u vektorov´a funkce i-t´a hodnota parametru vektoru parametrizace vektor parametrizace uniformn´ı vektor parametrizace tˇetivov´ y vektor parametrizace dostˇrediv´ y vektor parametrizace i-t´a vzd´alenost dvou po sobˇe jdouc´ıch tˇeˇziˇst’ souˇcet vˇsech vzd´alenost´ı dvou po sobˇe jdouc´ıch tˇeˇziˇst’ poˇcet uzlov´ ych rozteˇc´ı poˇcet ramen ˇr´ıd´ıc´ıho nebo definiˇcn´ıho polygonu i-t´a B-spline b´azov´a funkce p-t´eho stupnˇe stupeˇ n b´azov´ ych funkc´ı i-t´ y ˇr´ıd´ıc´ı bod ˇr´ıd´ıc´ı polygon definiˇcn´ı polygon i-t´ y definiˇcn´ı bod mnoˇzina re´aln´ ych ˇc´ısel i-t´a racion´aln´ı b´azov´a funkce p-t´eho stupnˇe parametr tˇeˇziˇstˇe definiˇcn´ıho polygonu tˇeˇziˇstˇe i-t´eho d´ılˇc´ıho definiˇcn´ıho polygonu uzlov´ y vektor i-t´ y uzel i-t´a uzlov´a rozteˇc v´aha i-t´eho ˇr´ıdic´ıho bodu v´ahy ˇr´ıdic´ıch bod˚ u souˇradnicov´e funkce vektorov´e funkce jedn´e promˇenn´e
25
Seznam pˇ r´ıloh K pr´aci je pˇriloˇzen´e CD obsahuj´ıc´ı: • elektronickou verzi bakal´aˇrsk´e pr´ace ve form´atu PDF • Maple: uniknot.mw • Maple: average.mw • Maple: centerknot.mw
26
