Számítógépi geometria. Kovács Zoltán

Számítógépi geometria Kovács Zoltán

Lektorálta: Dr. Verhóczki László (ELTE)

A tananyagfejlesztés az Európai Unió támogatásával és az Európai Szociális Alap társfinanszírozásával a TÁMOP-4.1.2-08/1/A-2009-0046 számú Kelet-Magyarországi Informatika Tananyag Tárház projekt keretében valósult meg.

.

Tartalomjegyzék El˝oszó

4

1. fejezet. Geometriai transzformációk 1.1. Matematikai alapok: Rn szokásos euklideszi struktúrája 1.2. Affin transzformációk 1.3. Projektív transzformációk

6 6 11 19

2. fejezet. Vetítések 2.1. A térb˝ol a képerny˝ore 2.2. Szemléletes kép készítése 2.3. Ferde axonometria és centrális axonometria

23 23 28 31

3. fejezet. Szabad formájú görbék modellezése 3.1. Parametrizált görbék 3.2. A keverési elv 3.3. Szplájnok 3.4. Lagrange-interpoláció 3.5. Harmadfokú Hermite-görbék 3.6. Bézier-görbék 3.7. B-szplájn görbék 3.8. NURBS-görbék

39 39 41 43 46 50 56 83 95

4. fejezet. Felületek tervezése 4.1. A felület fogalma 4.2. Példák felületekre 4.3. Tenzorszorzat-felületek

100 100 105 111

Ábrák jegyzéke

121

Irodalomjegyzék

124

3

˝ ELOSZÓ

4

El˝oszó A Debreceni Egyetemen és a Nyíregyházi F˝oiskolán tíz éve tartok (id˝oközben változó nevekkel) Számítógépi geometria kurzusokat el˝obb alkalmazott matematikus, majd a Bologna-rendszer˝u képzésben programtervez˝o informatikus és matematikus hallgatóknak. A kurzusok anyaga öltött testet ebben a jegyzetben. Mindenekel˝ott magyarázattal tartozom a címet illet˝oen. Ha pontosan ki akarnám fejteni a címet, akkor inkább a Számítógépi grafika matematikai alapjai vagy Ábrázoló geometria számítógéppel nevet kellene választani, hangsúlyozva, hogy itt nem számítógépi grafikáról van szó. Pontos határvonalat meghúzni persze nehéz lenne a két terület között, így egyszer˝uen úgy fogalmazok, hogy raszterizáción innen és túl. Nagyon vázlatosan bontsuk fel lépésekre az „ötlett˝ol a megvalósításig” folyamatot, mondjuk egy térben elképzelt jelenetb˝ol hogyan lesz monitoron megjelen˝o (raszterizált) kép. A monitort most diszkrét képpontok hálót alkotó rendszerének tekintjük, a kép leegyszer˝usítve annyit jelent, hogy minden képpontról megmondjuk, hogy milyen szín˝u. 1. 2. 3. 4. 5. 6. 7. 8.

ötlet (terv, rajzvázlat, leírás) a matematikai modell megalkotása a modell transzformációja a térben vetítés a képerny˝o síkjára a kép transzformációja raszterizáció raszteres algoritmusok raszterizált kép.

A jegyzet tárgya a fenti folyamat 2-5. lépése, amely csak matematikai eljárásokat igényel. A raszterizáció folyamán lesznek a matematikai objektumokból képpontok, amelyekre esetleg még különböz˝o eljárásokat, ún. raszteres algoritmusokat alkalmazhatunk. (Ilyenek lehetnek pl. a fototechnikában gyökerez˝o eljárások, mint az elmosás, kontraszt nyújtás, stb.)1 Az anyag összeállításában igyekeztem mértéktartónak maradni, az egy féléves bevezet˝o kurzus tematikáját így a jegyzet alig haladja meg. Természetesen a további tanulmányok alatt szinte mindegyik anyagrész tovább gyarapítható, illetve számos, itt nem tárgyalt fontos témakör elsajátítására nyílik lehet˝oség. Az elméleti kurzushoz tartozó gyakorlatokon programozási feladatok is szerepelnek. Bár az itt leírtak a számítógépi grafika általános alapjaihoz tartoznak, a jegyzet szemléletéhez a vektoros grafika illik jobban. Így a gyakorlatokon a programozás PostScript nyelven történik. Remélhet˝oleg 1Bizonyos problémákat lehet matematikailag és raszteresen is kezelni. Például egy

konvex poliéder lapjainak láthatósága (azaz egy adott lap látszik-e a képen vagy sem) jól kezelhet˝o matematikailag is, ugyanakkor a láthatóság általános problémáját inkább raszteres algoritmusokkal lehet egyszer˝ubben kezelni.

˝ ELOSZÓ

5

a jegyzet rövidesen kiegészülhet PostScript gyakorlatokkal is. Bízom benne, hogy az anyag és a benne közölt pszeudokódok nyelvt˝ol függetlenül is jól használhatók. (Ezt bizonyítja, hogy a kiírt feladatokra a legkülönböz˝obb programnyelveken kapok megoldásokat hallgatóimtól, például Nokia mobiltelefonra írt programokat is kaptam már.) További érv a PostScript nyelv mellett, hogy a programozásban kevésbé járatos matematikus hallgatók is jól boldogulnak vele, továbbá az ablakozás problémakörét ki lehet kerülni. A pszeudokódoknál a programrészek összetartozását behúzással jelölöm, tehát „end” utasításokat nem használok. A jegyzet sikeres feldolgozása megköveteli a bevezet˝o lineáris algebra kurzus, valamint a differenciálszámítás biztos ismeretét. A klasszikus euklideszi vektorterekre, valamint az elemi görbe- és felületelméletre vonatkozó alapismereteket a szükséges minimumra korlátozva az 1.1. szakaszban összefoglaltam. Részletesebb matematikai összefoglalót talál az olvasó pl. a [2] jegyzetben. Minden szakasz végén egy rövid összefoglaló segíti felidézni az anyagrészben tanult legfontosabb elemeket. A jegyzet ábráit PostScript nyelven készítettem, kivéve a szerz˝o és Kozma László: Differenciálgeometria c. jegyzetében is használt 4.1-4.1. ábrákat, amelyekhez a K3DSurf programot használtam. Nyíregyháza, 2011. április Kovács Zoltán

1. FEJEZET

Geometriai transzformációk 1.1. Matematikai alapok: Rn szokásos euklideszi struktúrája Rn elemeit általában latin kis- és nagybet˝ukkel jelöljük, tehát x ∈ Rn , vagy P ∈ Rn , míg ezek komponenseit indexelve, tehát pl. x = (x1 , x2 ) ∈ R2 . Rn elemeit pontnak és vektornak is lehet nevezni, szövegkörnyezett˝ol függ˝oen. Ha pontra gondolunk, akkor használunk nagybet˝uket, míg ha vektorra, akkor kisbet˝uket. (0, . . . , 0) ∈ Rn neve lehet origó (ekkor pontra gondolunk és az O jelölést használjuk), vagy zérusvektor (ekkor vektorra gondolunk és 0-val jelöljük). Rn×m jelöli az n × m típusú valós mátrixok halmazát. Rn -et gyakran beazonosítjuk Rn×1 -el, azaz a pontokat (vagy vektorokat) oszlopmátrixként is felfoghatjuk. 1.1. Definíció. Az x = (x1 , . . . , xn ) ∈ Rn és y = (y1 , . . . , yn ) ∈ Rn rendezett szám-n-esek összege x + y = (x1 + y1 , . . . , xn + yn ); míg ha α ∈ R, akkor α és x szorzata

α · x = (α · x1 , . . . , α · xn ).

Az összeadás tehát egy Rn × Rn → Rn binér m˝uvelet. A skalárral való szorzás egy R×Rn → Rn leképezés. (Ennek „·” jelét gyakran el is hagyjuk.) (−1) · x nyilván az x additív inverze, ezért jogos helyette −x-et írni.

1.2. Tétel. Rn a fenti összeadás m˝uveletre Abel csoport, továbbá (Rn , +) vektortér R fölött, azaz ∀x, y ∈ Rn , ∀α, β ∈ R: (1) α(x + y) = αx + αy, (2) (α + β )x = αx + β x, (3) (αβ )x = α(β x), (4) 1 · x = x.

1.3. Definíció. Az x, y ∈ Rn vektorok skaláris szorzatán (vagy bels˝o szorzatán) az hx, yi = x1 y1 + · · · + xn yn számot értjük. A skaláris szorzás tehát egy Rn × Rn → R leképezés.

1.4. Tétel. Rn euklideszi vektortér a fenti skaláris szorzattal, azaz ∀x, y, z ∈ Rn , ∀α ∈ R: 6

1.1. MATEMATIKAI ALAPOK: RN SZOKÁSOS EUKLIDESZI STRUKTÚRÁJA

7

hx, y + zi = hx, yi + hx, zi, hx + y, zi = hx, zi + hy, zi, hx, αyi = α hx, yi = hαx, yi, hx, yi = hy, xi, hx, xi ≥ 0; hx, xi = 0 ⇐⇒ x = 0. p 1.5. Definíció. x ∈ Rn -re kxk = hx, xi az x vektor hossza vagy normája. (1) (2) (3) (4)

Tehát a norma egy k·k : Rn → R leképezés, q amelyet normafüggvénynek

is nevezünk. Komponensekkel kiírva, kxk =

x12 + · · · + xn2 .

1.6. Tétel (Cauchy–Schwarz-egyenl˝otlenség). ∀x, y ∈ Rn : hx, yi2 ≤ kxk2 · kyk2 .

Egyenl˝oség akkor és csakis akkor teljesül, ha x, y arányosak, azaz ∃α ∈ R: x = αy vagy y = αx. 1.7. Következmény. A Cauchy–Schwarz-egyenl˝otlenség közvetlen következménye, hogy ha x és y egyike sem nullvektor, akkor hx, yi ≤ 1, −1 ≤ kxk · kyk és az x és y vektorok szögére teljesül, hogy hx, yi (1.1) cos α = , α ∈ [0, π]. kxk · kyk Speciálisan, két vektor akkor és csakis akkor mer˝oleges, ha skaláris szorzatuk zéró. 1.8. Tétel. ∀x, y ∈ Rn , ∀α ∈ R: (1) kxk ≥ 0, (2) kxk = 0 ⇐⇒ x = 0, (3) kαxk = |α| · kxk, (4) kx+yk ≤ kxk+kyk, továbbá egyenl˝oség akkor és csakis akkor teljesül, ha x, y arányosak, nemnegatív faktorral (Minkowski egyenl˝otlenség). A számítógépi grafikában gyakran van szükségünk egy nem zéró vektor irányába mutató egységnyi hosszúságú vektorra (röviden egységvektorra). 1.9. Következmény. Az x 6= 0 vektor irányába mutató egységvektor

1 kxk · x.

1.10. Definíció. Ha P, Q ∈ Rn , akkor d(P, Q) = kP − Qk a P és Q pontok távolsága. A távolság tehát egy d : Rn × Rn → R leképezés, amelyet távolságfüggvénynek is nevezünk. Komponensekkel kiírva: q d(P, Q) = (P1 − Q1 )2 + · · · + (Pn − Qn )2 . 1.11. Tétel. ∀P, Q, R ∈ Rn :


8

(1) d(P, Q) ≥ 0, (2) d(P, Q) = 0 ⇐⇒ P = Q, (3) d(P, Q) = d(Q, P), (4) d(P, Q) + d(Q, R) ≥ d(P, R) (háromszög-egyenl˝otlenség), azaz (Rn , d) egy metrikus tér. Az eddigiekben elmondottakat általános (véges) dimenzióban fogalmaztuk meg, de természetesen a számítógépi grafikai alkalmazásoknál a dimenzió nagyon gyakran (de nem kizárólagosan) 2 vagy 3. A következ˝o szakaszban viszont a dimenzió 3, azaz a háromdimenziós euklideszi térben dolgozunk. Az R3 tér szokásos bázisa e1 = (1, 0, 0), e2 = (0, 1, 0), e3 = (0, 0, 1). 1.12. Definíció. Az x = (x1 , x2 , x3 ) és y = (y1 , y2 , y3 ) vektorok vektoriális szorzata x2 x3 x1 x3 x1 x2 e − e + e . x × y = y2 y3 1 y1 y3 2 y1 y2 3 1.13. Tétel (a vektoriális szorzás algebrai tulajdonságai.). A vektoriális szorzás egy R3 × R3 → R3 ferdén szimmetrikus, bilineáris leképezés, azaz teljesül (1) x × y = −y × x, (2) (x + y) × z = x × z + y × z, (3) x × (y + z) = x × y + x × z, (4) (αx) × y = α(x × y) = x × (αy). A vektoriális szorzást további, geometriai tulajdonságai teszik kitüntetett jelent˝oség˝uvé a számítógépi grafikában. 1.14. Tétel (a vektoriális szorzás geometriai tulajdonságai). (1) x × y = 0 akkor és csakis akkor, ha (x, y) lineárisan függ˝o vektorrendszer, (2) x × y ⊥ x, x × y ⊥ y, azaz a vektoriális szorzat mer˝oleges a tényez˝oire, (3) ha x és y lineárisan függetlenek, akkor (x, y, x × y) jobb-rendszert alkotnak, azaz úgy következnek egymás után, mint a jobb kéz hüvelykujja, mutató ujja és középs˝o ujja, (4) kx × yk = kxk · kyk sin ∠(x, y), azaz a vektoriális szorzat hossza megegyezik a tényez˝ok által kifeszített paralelogramma területével. Alkalmazások 1.15. Példa (irányított háromszöglemez normálisa). Sok grafikai problémánál (láthatósági, megvilágítási problémák) szükség van arra, hogy egy sokszöglemezt irányítással adjunk meg. Irányított sokszöglemezr˝ol akkor beszélünk, ha kitüntetjük a sokszöglemez síkjának egyik oldalát, azaz a sík egyik egység-normálisát (a síkra mer˝oleges egységvektort). A kitüntetett oldalt nevezzük küls˝o oldalnak, a másik oldalt bels˝o oldalnak. Ha egy háromszöglemezt a csúcsok rendezett megadásával határozunk meg, akkor


9

(megállapodás szerint) a küls˝o oldal normálisát a jobbkéz-szabály alapján kapjuk, azaz, ha a jobb kezünk ökölbe szorított ujjai a csúcsok sorrendjének megfelel˝o forgásirányt jelölik ki, akkor a megfeszített hüvelykujj mutatja a kifelé mutató normális irányát. Legyenek tehát az irányított háromszöglemez csúcsai (V0 ,V1 ,V2 ), ekkor a kifelé mutató normális (V1 −V0 ) × (V2 −V0 ). Egy konvex poliéder lapjait megállapodás szerint úgy irányítjuk, hogy a kitüntetett normálisok a poliéderb˝ol kifelé mutatnak. y

V0

V2 x V1

z

1.1. ábra. Háromszöglemez kifelé mutató normálisa

A skaláris szorzat két grafikai alkalmazását mutatjuk be. A grafikai alkalmazások alapja, hogy a skaláris szorzattal két vektor szögének koszinuszát az (1.1) alapján ki tudjuk számítani: 1.16. Példa (irányított sokszöglemez láthatósága). A kamera a sokszöglemez küls˝o oldalát látja, ha a sokszög egy csúcsából a kamerához mutató vektor és a kitüntetett felületi normális hegyesszöget zár be, azaz skaláris szorzatuk pozitív; míg a bels˝o oldalt, ha a skaláris szorzat negatív. Zéró skaláris szorzat esetén a lap profilból látszik, azaz a kamera egy szakaszt lát. (Ld. 1.2. ábra.) Konvex poliéder esetén csak azok a lapok látszanak, amelyeknek a kamera a küls˝o oldalát látja. 1.17. Példa (Lambert-féle koszinuszszabály). A fényforrással megvilágított diffúz felület megvilágításának intenzitása kifejezhet˝o a felületi normális


10

kamera cos α = -0.57735

1.2. ábra. Irányított sokszöglemez láthatósága. A kamera az ábrán látható lap bels˝o oldalát látja.

és a fényforrás iránya közötti α szög koszinuszával. Egy egyszer˝u modell szerint

(1.2)

g=

1 + cos α ∈ [0, 1] 2

a szürkeárnyalat intenzitása (ld. 1.3. ábra).

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

1.3. ábra. Lambert-féle koszinuszszabály. A modell megvilágításánál a szürkeárnyalat intenzitását az (1.2) reláció alapján számoltuk nemcsak a megvilágított, hanem a nem megvilágított lapokra is.

1.2. AFFIN TRANSZFORMÁCIÓK

11

Ö SSZEFOGLALÓ skaláris szorzás: x = (x1 , x2 , . . . , xn ), y = (y1 , y2 , . . . , yn ), n

hx, yi = ∑ xi yi . i=1

vektoriális szorzás: x = (x1 , x2 , x3 ), y = (y1 , y2 , y3 ), x2 x3 x1 x3 x1 x2 e . x×y = e − e + y2 y3 1 y1 y3 2 y1 y2 3 mer˝olegesség: x ⊥ y ⇐⇒ hx, yi = 0, x × y ⊥ x, x × y ⊥ y. háromszöglemez irányítása: a (V0 ,V1 ,V2 ) irányított háromszöglemez kifelé mutató normálisa (V1 −V0 ) × (V2 −V0 ). 1.2. Affin transzformációk A síkban a pontok és rendezett számpárok között kölcsönösen egyértelm˝u megfeleltetés van egy Descartes-féle koordináta-rendszer rögzítése után. A térbeli pontok a rendezett számhármasokkal hozhatók kölcsönösen egyértelm˝u kapcsolatba. A geometriai transzformációk (legalábbis az általunk vizsgált transzformációk többsége) a nemelfajuló (azaz nem zéró determinánsú) négyzetes mátrixokkal hozhatók kapcsolatba. Ebben a fejezetben csak egyenestartó transzformációkkal foglalkozunk, azaz a tér vagy sík olyan bijektív leképezéseivel, melyeknél tetsz˝oleges egyenes képe egyenes. Az egyenestartó transzformációkat algebrai megközelítésben affin transzformációknak nevezik (ld. alább az 1.18. definíció). El˝oször néhány geometriai fogalom szokásos algebrai modelljét adjuk meg. Legyenek P, Q ∈ Rn különböz˝o pontok! - A P, Q pontok egyenese: {tQ + (1 − t)P | t ∈ R}, - a P, Q pontokat összeköt˝o szakasz: [P, Q] = {tQ + (1 − t)P | t ∈ [0, 1]},

- osztóviszony: ha X = tQ + (1 − t)P és X 6= P, X 6= Q, akkor t (PQX) = , 1−t az X pont osztóviszonya a (P, Q) alappontokra. (Például a szakasz felez˝opontjának osztóviszonya a szakasz végpontjaira, mint alappontokra nézve 1, azaz a felez˝opont a szakaszt 1 : 1 arányban osztja.) A továbbiakban GL(n) jelöli az n×n-típusú, nem zéró determinánsú valós mátrixok csoportját, míg In jelöli a csoport egységelemét, azaz az n × n típusú egységmátrixot. 1.18. Definíció. Legyen A ∈ GL(n), b ∈ Rn . Az

F : Rn → Rn , X 7→ F(X) = AX + b, X ∈ Rn


12

x′ y y′

x 1.4. ábra. Affin transzformáció

leképezést affin transzformációnak nevezzük. Az A nemelfajuló mátrix az affin transzformáció lineáris része. Ha A = In , akkor a transzformáció speciálisan b vektorú eltolás: F(X) = X + b. 1.19. Tétel (az affin transzformáció tulajdonságai). Minden affin transzformáció (1) egyenestartó, (2) osztóviszonytartó (pl. felez˝opont képe felez˝opont), (3) párhuzamosságtartó (pl. paralelogramma képe paralelogramma). Az 1.18. definícióban az egyenestartó transzformációt algebrailag egy mátrixszal (A) és egy vektorral (b) reprezentáltuk. Sok szempontból kényelmes lehet, ha az affin transzformációt egyetlen mátrixszal reprezentáljuk. Ez a mátrix Ab (1.3) aff(A, b) = ∈ GL(n + 1), 01 tehát a bal fels˝o n × n-es részmátrix A, az utolsó sorban n darab nulla áll és egy egyes. Az utolsó sor szerinti kifejtési tétel mutatja, hogy ez a mátrix is nemelfajuló. Az el˝obbi mátrixot az F(X) = AX + b affin transzformáció homogén reprezentációjának nevezzük. Könny˝u látni, hogy az (1.3)-típusú mátrixok csoportot alkotnak a mátrixok szorzására nézve, ezt a csoportot affin csoportnak nevezzük és Aff(n)nel jelöljük. Tehát az affin csoport: Ab n Aff(n) = | A ∈ GL(n), b ∈ R . 01 Arra a kérdésre, hogy miért lehet hasznos az affin transzformáció homogén reprezentációja, az alábbi két tétel ad választ: a transzformáció végrehajtása és a transzformációk szorzása (egymás után való végrehajtása) mátrixszorzással számítható.


13

jel. 1.20. Tétel. Legyen A ∈ GL(n), b ∈ Rn , továbbá F(X) = X 0 = AX +b affin transzformáció. Ekkor 0 X Ab X = . 1 01 1 1.21. Tétel. Legyen az F1 affin transzformáció homogén reprezentánsa aff(A1 , b1 ), az F2 affin transzformáció homogén reprezentánsa aff(A2 , b2 ). Ekkor az F2 ◦ F1 szorzat transzformáció homogén reprezentánsa a két homogén reprezentáns szorzata, azaz A2 b2 A1 b1 · . 0 1 0 1 Felhívjuk a figyelmet arra, hogy a transzformációszorzás nem kommutatív. A transzformációk szorzását jobbról balra olvassuk, tehát az F2 ◦ F1 transzformációnál el˝oször F1 -et, majd F2 -t hajtjuk végre. A homogén reprezentánsok szorzatában a tényez˝ok sorrendjére ugyanez vonatkozik, jobbról áll az els˝oként végrehajtott transzformáció mátrixa. 1.22. Példa (eltolás síkban). A síkbeli (a, b) vektorú eltolás:    0  x x 10a y0  = 0 1 b y . 1 001 1 Részletesen kiírva: x0 = x + a y0 = y + b. 1.23. Példa (eltolás térben). A térbeli (a, b, c) vektorú eltolás:  0    x 100a x y0  0 1 0 b y  0 =     z  0 0 1 c   z  . 1 0001 1 A speciális affin transzformációk közül az eltolások után az egybevágósági transzformációkat tárgyaljuk. Geometriailag az egybevágósági transzformáció, vagy görög eredet˝u szóval izometria, távolságtartó bijektív leképezést jelent. Egyszer˝u geometriai eszközökkel könny˝u belátni, hogy minden izometria egyenestartó, azaz affin transzformáció. A kérdés, hogy az egybevágóságokat hogyan lehet jellemezni a lineáris részükkel. A válasz az, hogy az egybevágóság lineáris része ún. ortogonális mátrix (1.25. tétel). 1.24. Definíció. Egy négyzetes mátrixot ortogonális mátrixnak nevezünk, ha sorai egymásra mer˝oleges egységvektorok, illetve ezzel ekvivalens módon, ha az oszlopai egymásra mer˝oleges egységvektorok.


14

A definíció szerint könny˝u látni, hogy az ortogonális mátrixokat az jellemzi, hogy az inverzük megegyezik a transzponáltjukkal. Az n × n típusú ortogonális mátrixok GL(n)-ben részcsoportot alkotnak, ezt a csoportot ortogonális csoportnak nevezzük és O(n)-nel jelöljük: O(n) = {A ∈ GL(n) | A−1 = At }.

Az ortogonális mátrix determinánsa mindig ±1. Két dimenzióban nagyon könny˝u megadni az összes ortogonális mátrixot: cos α ± sin α O(2) = |α ∈ R , sin α ∓ cos α ahol a második oszlopban az el˝ojelek úgy értend˝ok, hogy ha az egyik el˝ojel + akkor a másik −. Speciálisan az O(2) csoport cos α − sin α SO(2) = |α ∈ R sin α cos α részhalmaza kommutatív csoport. (Ennek a csoportnak a geometriai jelentését rögtön megvizsgáljuk.) A csoport elemeire bevezetjük a cos α − sin α rot(α) = sin α cos α jelölést. A fordított el˝ojel-kombinációjú mátrixok halmaza nem csoport (nem zárt a szorzásra), ett˝ol függetlenül elemeinek fontos geometriai jelentése van, így külön jelölést is bevezetünk rá: cos(2α) − sin(2α) ref(α) = . sin(2α) cos(2α) 1.25. Tétel. F : Rn → Rn akkor és csakis akkor egybevágósági transzformáció, ha létezik olyan A ∈ O(n) ortogonális mátrix és b ∈ Rn vektor, hogy F : Rn → Rn , X 7→ F(X) = Ax + b.

Megjegyezzük, hogy a sík egybevágósági transzformációja csak elforgatás vagy eltolás vagy csúsztatva tükrözés lehet. Utóbbi olyan eltolás és tengelyes tükrözés szorzata, ahol az eltolás iránya megegyezik a tengely irányával. Speciális esetként csúsztatva tükrözések között találjuk a tengelyes tükrözéseket is. 1.26. Tétel. Az origó körüli α szög˝u elforgatásnál a P = (x, y) pont képe az a P0 = (x0 , y0 ) pont, melyre 0 x cos α − sin α x = . y0 sin α cos α y A tétel alapján megállapíthatjuk, hogy az SO(2) csoport elemei a sík origó körüli elforgatásai. 1.27. Tétel. A C pont körüli α szög˝u elforgatásnál a P pont képe az a P0 pont, melyre P0 = rot(α)(P −C) +C.


15

y y′ x′

x 1.5. ábra. Elforgatás az origó körül A tételben leírt összefüggést tol-forgat-tol vagy „TFT” szabálynak is mondjuk, mert valójában a transzformációt három transzformáció szorzataként adtuk meg: forgat tol tol P −→ (P −C) −→ rot(α)(P −C) −→ rot(α)(P −C) +C y x′ t x

y′ 1.6. ábra. Tengelyes tükrözés origón áthaladó egyenesre

1.28. Tétel. Az origón áthaladó, α irányszög˝u egyenesre vonatkozó tükrözésnél a P = (x, y) pont képe az a P0 = (x0 , y0 ) pont, melyre P0 = ref(α)P, azaz 0 x cos(2α) sin(2α) x = . y0 sin(2α) − cos(2α) y 1.29. Tétel. Az M ponton áthaladó, α irányszög˝u egyenesre vonatkozó tükrözésnél a P pont képe az a P0 pont, melyre P0 = ref(α)(P − M) + M. A tételben leírt összefüggés a tol-tükröz-tol vagy „TTT” szabály. tol tükröz tol P −→ (P − M) −→ ref(α)(P − M) −→ ref(α)(P − M) + M

A tér egybevágósági transzformációi leírásához az 1.25. tétel szerint az O(3) csoportot kell ismernünk.


16

1.30. Tétel. O(3) minden eleme origón áthaladó egyenes körüli elforgatás vagy origón áthaladó egyenes körüli elforgatás és síkra vonatkozó tükrözés szorzata, ahol a tükörsík mer˝oleges a forgástengelyre és áthalad az origón (röviden forgatva tükrözés). Ha a forgástengely irányvektora v és kvk = 1 valamint az elforgatás szöge α, akkor O(3) megfelel˝o eleme Rv (α) : R3 → R3 , P 7→ Rv (α)P = P0 , (1.4)

P0 = cos α · P − (cos α ∓ 1) · hv, Pi v + sin α · (v × P),

ahol a fels˝o el˝ojelet a forgatásnál, az alsó el˝ojelet a forgatva tükrözésnél kell alkalmazni. A tétel speciális eseteként kapjuk a koordinátatengelyek körüli elforgatásokat. 1.31. Következmény. A σ koordinátatengely körüli α szög˝u elforgatás a tér egy P pontjához a tér P0 = Rσ (α) · P pontját rendeli hozzá, ahol σ = x, y, z és   1 0 0 Rx (α) = 0 cos α − sin α  , 0 sin α cos α   cos α 0 sin α Ry (α) =  0 1 0  , − sin α 0 cos α   cos α − sin α 0 Rz (α) =  sin α cos α 0 . 0 0 1 A fenti mátrixokat az (1.4) összefüggésbe való direkt behelyettesítéssel kaptuk és a forgatás iránya a jobbkéz-szabály szerint értend˝o: ha a jobb kéz hüvelykujja mutat a v vektor irányába, akkor a jobb kéz ökölbe szorított ujjai jelölik ki a forgásirányt. Az y körüli forgatás mátrixában az el˝ojelek némileg másként vannak, mint a másik két mátrixban, ezért szokás az y tengely körüli elforgatás irányát a balkéz-szabály szerint venni, így mátrixa   cos α 0 − sin α R∗y (α) =  0 1 0  . sin α 0 cos α Ha a térben olyan tengely körül forgatunk el, mely nem megy át az origón, akkor a „tol-forgat-tol” szabályt alkalmazhatjuk: P0 = Rv (α)(P − M) + M,

ahol v a tengely irányvektora, M a tengely egy pontja, α a forgatás szöge. 1.32. Definíció. Egy F : Rn → Rn , P 7→ F(P) = P0 bijektív leképezést hasonlósági transzformációnak nevezünk, ha van olyan k > 0 valós szám, hogy ∀P, Q ∈ Rn : d(P0 , Q0 ) = k · d(P, Q).


17

végberendezés csukló

szegmens

1.7. ábra. Két dimenziós robotkar rotációs csuklókkal k-t a hasonlóság arányának nevezzük. Minden egybevágósági transzformáció példát jelent hasonlóságra, mert k = 1 esetén a definiáló tulajdonság teljesül. Egybevágóságtól különböz˝o hasonlóságra is könny˝u példát adni. Legyen diag(α1 , . . . , αn ) olyan n × n típusú diagonális mátrix, melynek a f˝oátlója (α1 , . . . , αn ). 1.33. Tétel. Legyen adott egy k 6= 0 valós szám. Ekkor

F : Rn → Rn , P 7→ F(P) = diag(k, . . . , k)P

|k| arányú hasonlóság, melyet k arányú skálázásnak nevezünk. A skálázások jelent˝oségét az adja, hogy minden hasonlóság egybevágóság és skálázás szorzataként adható meg. Így a hasonlóságok analitikus leírásával már készen is vagyunk. 1.34. Tétel. A sík egy hasonlósági transzformációjának homogén reprezentánsa egy   a ∓c m c ±a n  0 0 1 √ mátrix, ahol a2 + c2 adja a hasonlóság arányát. Alkalmazás A számítógépi grafikában komplex alakzatok (pl. él˝olények) modellezésében gyakran alkalmazott módszer, hogy az alakzat „csontvázából” indulnak ki. A csontváz nem más, mint a robottechnikából is ismert csuklós szerkezet, vagy robotkar (1.7. ábra). A robotkar részei: - csuklók (rotációs, prizmatikus), - szegmensek, - végberendezés (end effector). A prizmatikus csukló a szegmensek hosszát változtatja. A továbbiakban csak rotációs csuklókat tartalmazó robotkarral foglalkozunk, amely csak egy rögzített síkban tud mozogni. Az ilyen robotkart a szegmensek hossza és a csatlakozó szegmensek szöge meghatározza (1.8. ábra). Rögzített hosszúságú szegmensek esetén a csatlakozó szegmensek szögének sorozata az állapotvektor. Határozzuk meg a csuklók helyzetét az állapotvektor ismeretében!


18

θ2 a2 a1 θ1

1.8. ábra. Robotkar megadása a szegmensek hosszával és a csatlakozó szegmensek szögével 1.35. A LGORITMUS (Két dimenziós robotkar leírása az állapotvektorral). A csuklókat a Ji ∈ R2 , (i = 1, . . . , n) koordináta párokkal adjuk meg, Jn = E a végberendezés. Az els˝o csukló legyen rögzített. 1.35. ROBOT(θ1 , . . . , θn−1 ) Input: θ1 , . . . , θn Output: J1 , . . . , Jn for k = 2 to n do for i = k to n do Ji ← rot(Jk−1 , θk−1 )Ji return (J1 , . . . , Jn ) Az algoritmusban alkalmazott rot(Jk−1 , θk−1 ) forgatásokat mindig a TFT-szabály szerint kell számítani, hiszen az elforgatás középpontja Jk−1 , általában nem az origó. Ö SSZEFOGLALÓ affin transzformáció: geometriailag egyenestartó bijektív leképezés. Algebrailag F : Rn → Rn , X 7→ F(X) = AX + b, ahol A ∈ GL(n) az F lineáris része, b ∈ Rn . egybevágósági transzformáció: geometriailag távolságtartó bijektív leképezés. Algebrailag olyan affin transzformáció, melynek lineáris része ortogonális mátrix. Az ortogonális mátrix olyan négyzetes mátrix, melynek inverze megegyezik a transzponáltjával. cos α − sin α origó körüli forgatás mátrixa (síkban): (α a forsin α cos α gatás szöge). origón vonatkozó tükrözés mátrixa (síkban): áthaladó egyenesre cos 2α sin 2α (α a tengely irányszöge). sin 2α − cos 2α origón áthaladó tengely körüli elforgatás: ha a forgástengely irányvektora v és kvk = 1 valamint az elforgatás szöge α, akkor P0 = cos α · P − (cos α − 1) · hv, Pi v + sin α · (v × P).

1.3. PROJEKTÍV TRANSZFORMÁCIÓK

19

1.3. Projektív transzformációk 1.36. Definíció. A P = (x¯1 , . . . , x¯n ) ∈ Rn pont homogén koordinátái alatt olyan (x1 , . . . , xn , xn+1 ) ∈ Rn+1 vektort értünk, amelyre x¯i = xi /xn+1 , i = 1, . . . , n. Egy pont homogén koordinátáihoz legegyszer˝ubben úgy jutunk, ha a pont komponenseit kiegészítjük egy egyessel. (Ha megfigyeljük az 1.20. tételt, akkor ott is homogén koordinátákat alkalmaztunk.) A definíció alapján azonnal látszik, hogy a pont homogén koordinátái nem egyértelm˝uek, az egymással arányos vektorok ugyanannak a pontnak a homogén koordinátáit adják. Jelölje [x1 , . . . , xn , xn+1 ] az (x1 , . . . , xn , xn+1 ) nemzéró vektorral arányos nemzéró vektorok halmazát (azaz a zéró arányossági tényez˝ot kizártuk). Magát a pontot pedig beazonosítjuk a homogén koordinátái halmazával. Például a síkban P = (x, y) = [x1 , x2 , x3 ], ahol x = x1 /x3 , y = x2 /x3 , vagy a térben P = (x, y, z) = [x1 , x2 , x3 , x4 ], ahol x = x1 /x4 , y = x2 /x4 , z = x3 /x4 . Homogén koordináták alkalmazásával egy fontos transzformáció típushoz juthatunk, melynek lényege, hogy a pont homogén koordinátáit szorozzuk egy nemelfajuló mátrixszal (ezt tettük az affin transzformáció homogén reprezentációjánál is, de most a mátrixunk nem feltétlenül affin transzformációt reprezentál), az eredmény vektor utolsó koordinátájával a többi koordinátát elosztva kapjuk a képpontot. Problémát jelenthet, hogy az utolsó koordináta esetleg 0 lesz, így az osztás nem végezhet˝o el. Hogy az eljárás ebben az esetben is értelmes maradjon a transzformáció értelmezési tartományának és képterének az ún. projektív teret (síkot) választjuk. 1.37. Definíció. A Pn = {[x] | x ∈ Rn+1 \{0}} halmazt n-dimenziós projektív térnek, speciálisan n = 2 esetén projektív síknak, míg a halmaz elemeit pontoknak nevezzük. Ha az X = [x] pontra xn+1 6= 0, akkor X-et közönséges pontnak, míg ha xn+1 = 0, akkor végtelen távoli pontnak nevezzük. A közönséges pontokat korábban már beazonosítottuk Rn pontjaival. Ezért a projektív teret (síkot) úgy is tekinthetjük, mint a szokásos euklideszi tér (sík) kiegészítését a végtelen távoli pontokkal. Ezek után precízen is megfogalmazhatjuk az el˝oz˝oekben már vázolt projektív transzformáció fogalmát. 1.38. Definíció. Legyen A ∈ GL(n + 1), a Pn → Pn , [x] 7→ [Ax], (x ∈ Rn+1 \ {0}) leképezést az n-dimenziós projektív tér projektív transzformációjának nevezzük. Megjegyezzük, hogy egy nemelfajuló négyzetes mátrix és annak egy nem zéró skalárral való szorzata ugyanazt a projektív transzformációt adják meg.


20

1.9. ábra. Projektív transzformáció: alakzat és képe

A projektív síkban a definíciót részletesen kiírva a következ˝o leképezést kapjuk x10 = p11 x1 + p12 x2 + p13 x3 x20 = p21 x1 + p22 x2 + p23 x3 x30 = p31 x1 + p32 x2 + p33 x3 , ahol P = (pi j ) ∈ GL(3). Ha mind a kiindulási pont, mind a képpont közönséges, akkor p11 x + p12 y + p13 p21 x + p22 y + p23 x0 = , y0 = . p31 x + p32 y + p33 p31 x + p32 y + p33 A nevez˝ok akkor válnak zérussá, amikor a képpont végtelen távoli pont lesz. A p31 x + p32 y + p33 = 0 egyenlet egy egyenes egyenlete. Ezt az egyenest nevezzük a transzformáció elt˝unési egyenesének. Ha egy pont az elt˝unési egyenesen van, akkor a képét nem tudjuk a síkban (képerny˝on) ábrázolni. 1.39. Tétel (a projektív transzformációk tulajdonságai). Minden projektív transzformációra teljesülnek az alábbiak: 1. Legyen (A, B,C) közönséges ponthármas úgy, hogy az (A0 , B0 ,C0 ) projektív képeik is közönségesek. (A, B,C) akkor és csakis akkor kollineárisak, ha (A0 , B0 ,C0 ) kollineárisak. 2. Legyen (A, B,C, D) közönséges kollineáris pontnégyes úgy, hogy az (A0 , B0 ,C0 , D0 ) projektív képeik is közönségesek. Ekkor az osztóviszonyokkal fennáll (ABC) (A0 B0C0 ) = 0 0 0 . (ABD) (A B D ) A második tulajdonságot úgy is szokás fogalmazni, hogy a projektív transzformáció kett˝osviszonytartó. Alkalmazás A következ˝oekben egy olyan algoritmust ismertetünk, mely a számítógépi grafika sok területén fontos. Négyszög alatt négy olyan pontot értünk, melyek között nincs három egy egyenesre illeszked˝o. 1.40. Tétel (projektív transzformációk meghatározása síkban). Négyszög és képe a projektív transzformációt egyértelm˝uen meghatározza.


21

B IZONYÍTÁS . A négy eredeti pont legyen {[xi , yi , zi ] | i = 1, . . . , 4}, a négy képpont pedig {[Xi ,Yi , Zi ] | i = 1, . . . , 4}. Olyan M ∈ GL(3) mátrixot keresünk, melyre M(xi , yi , zi )t = ξi (Xi ,Yi , Zi )t ,

i = 1, 2, 3, 4.

(Ne felejtsük el, hogy arányos számhármasok ugyanazt a pontot jelentik, ezért került a jobb oldalra egy-egy arányossági tényez˝o.) M megkeresését két lépésre osztjuk, ezek a lépések matematikailag teljesen egyenérték˝uek. El˝oször olyan P ∈ GL(3) mátrixot keresünk, melyre P : Ei 7→ [xi , yi , zi ],

i = 1, 2, 3, 4.

ahol E1 = [1, 0, 0], E2 = [0, 1, 0], E3 = [0, 0, 1], E4 = [1, 1, 1]. Majd olyan Q ∈ GL(3) mátrixot, melyre Q : Ei 7→ [Xi ,Yi , Zi ],

i = 1, 2, 3, 4.

A keresett mátrix M = QP−1 . Q és P megkeresése matematikailag ugyanaz a probléma, a módszert csak P-re mutatjuk be. P = (pi j ) ∈ GL(3)-ra teljesül, hogy valamely k1 , k2 , k3 , k4 konstansokra      p11 p12 p13 1001 k1 x1 k2 x2 k3 x3 k4 x4  p21 p22 p23  0 1 0 1  = k1 y1 k2 y2 k3 y3 k4 y4  . p31 p32 p33 0011 k1 z1 k2 z2 k3 z3 k4 z4 A fenti egyenletrendszerben 9 + 4 = 13 ismeretlen van (a P mátrix elemei, továbbá k1 , k2 , k3 , k4 ), ugyanakkor a mátrixelemek összehasonlításával 12 egyenletet kapunk. Egy ismeretlent tehát szabadon választhatunk (pontosabban szabadon paraméterezhetünk), legyen ez k4 , mely értékét 1-nek választjuk. Így az egyenletrendszer:      p11 p12 p13 1001 k1 x1 k2 x2 k3 x3 x4  p21 p22 p23  0 1 0 1  = k1 y1 k2 y2 k3 y3 y4  . 0011 k1 z1 k2 z2 k3 z3 z4 p31 p32 p33 A bal oldalon a szorzást elvégezve:     p11 p12 p13 p11 + p12 + p13 k1 x1 k2 x2 k3 x3 x4  p21 p22 p23 p21 + p22 + p23  = k1 y1 k2 y2 k3 y3 y4  . p31 p32 p33 p31 + p32 + p33 k1 z1 k2 z2 k3 z3 z4 A jobb oldali és a bal oldali mátrixelemek összehasonlításával az alábbi lineáris egyenletrendszert kapjuk a k1 , k2 , k3 ismeretlenekre: k1 x1 + k2 x2 + k3 x3 = x4 k1 y1 + k2 y2 + k3 y3 = y4 k1 z1 + k2 z2 + k3 z3 = z4 .


Innen kapjuk a k1 , k2 , k3 számokat, majd a P mátrixot:   −1      k1 x1 k2 x2 k3 x3 x4 x1 x2 x3 k1 k2  = y1 y2 y3  y4  , P = k1 y1 k2 y2 k3 y3  . k1 z1 k2 z2 k3 z3 z4 z1 z2 z3 k3

22

1.41. A LGORITMUS (a projektív transzformáció mátrixának kiszámítása). A bizonyításban leírt eljárást foglaltuk össze az alábbiakban: 1.41. P ROJECTIVE T RANSFORMATION Input: [xi , yi , zi ], [Xi ,Yi , Zi ] (i = 1, . . . , 4) Output: M    −1   k1 x1 x2 x3 x4      k2 = y1 y2 y3 y4  1: k3 z1 z2 z3 z4   k1 x1 k2 x2 k3 x3  2: P = k1 y1 k2 y2 k3 y3  k1 z1 k2 z2 k3 z3    −1   K1 X1 X2 X3 X4      K2 = Y1 Y2 Y3 Y4  3: K3 Z1 Z2 Z3 Z   4 K1 X1 K2 X2 K3 X3  4: Q = K1Y1 K2Y2 K3Y3  K1 Z1 K2 Z2 K3 Z3 5: return M = QP−1

Ö SSZEFOGLALÓ projektív tér: Pn = {[x] | x ∈ Rn+1 \ {0}}. projektív transzformáció: Pn → Pn , [x] 7→ [Ax] (x ∈ Rn+1 \ {0}), A ∈ GL(n + 1). projektív transzformáció tulajdonságai: - egyenestartó, - kett˝osviszonytartó, - a síkon négyszög és képe egyértelm˝uen meghatározza.

2. FEJEZET

Vetítések 2.1. A térb˝ol a képerny˝ore A számítógépi grafika egyik alapfeladata a térbeli pontok megjelenítése a képerny˝on. Vetítés alatt azt értjük, hogy a térbeli pont koordinátáihoz hozzárendeljük a neki megfeleltetett képerny˝opont koordinátáit. Ha a térben is és a képerny˝o síkján is Descartes-féle koordinátákat használunk, akkor a vetítés egy R3 → R2 leképezés. A tér síkra történ˝o R3 → R2 leképezésére nagyon sokféle klasszikus ábrázoló geometriai módszer ismert, jelen jegyzet keretei között a lineáris és a törtlineáris leképezésekkel foglalkozunk. A lineáris leképezések mátrixszorzásként hatnak, míg a törtlineáris leképezések a projektív tér leképezései. 2.1. Definíció. Egy R3 → R2 , P 7→ AP, (A ∈ R2×3 , rang A = 2), leképezést axonometriának vagy ferde axonometriának, míg egy P3 → P2 , [x] 7→ [Ax], (x ∈ R4 \ {0}, A ∈ R3×4 , rang A = 3) leképezést centrális axonometriának nevezünk. A továbbiakban a képsíkot rögzítjük, ez a képerny˝o síkja, azaz a z = 0 egyenlet˝u xy sík lesz. A fejezet további részében három egyszer˝u példát adunk projekcióra. A szemléltet˝o ábrákon a 2.1. ábrán látható csonkolt kocka különböz˝o vetületeit láthatjuk majd. 2.1.1. Ortogonális vetítés. Egyszer˝u lineáris leképezés a térb˝ol a képerny˝o síkjára a harmadik koordináta levágása, azaz az R3 → R2 , (x, y, z) 7→ (x, y) leképezés. Mátrixszorzással     x x 1 0 0 y 7→ y = x . 010 y z z Ez a leképezés geometriailag mer˝oleges vetítés a képerny˝ore, melyet a továbbiakban szokásos mer˝oleges vetítésnek is mondunk. Mátrixát, azaz az 100 mátrixot Π0 -val jelöljük. 010 23

˝ A KÉPERNYORE ˝ 2.1. A TÉRBOL

24

y

x z

2.1. ábra. A fejezetben használt modell. A kocka oldalai a koordinátatengelyekkel párhuzamosak, a csonkolt csúccsal szemközti csúcs az origóban van. y′

x′

2.2. ábra. A modell mer˝oleges vetülete a képerny˝ore

2.1.2. Párhuzamos vetítés. Vetítsük a teret a v = (v1 , v2 , v3 ) (v3 6= 0) vektorral párhuzamosan az xy síkra. A tárgypont P = (x, y, z). A P + tv egyenes azon pontját keressük, amelynek harmadik koordinátája zérus. A képpont (vetületi pont) keresett paraméterére z + tv3 = 0 teljesül, ahonnan t = − vz3 . Ezt a paraméterértéket visszahelyettesítve az egyenes P + tv el˝oállításába v1 x0 = x − z , v3 (2.1) v 2 y0 = y − z v3 adódik. A vetítés mátrixa tehát 1 0 − vv13 A= . 0 1 − vv23


25

y′

x′

z′

2.3. ábra. Párhuzamos vetítés v1 = v2 = 0 esetén speciálisan ortogonális vetítést kapunk. 2.1.3. Centrális vetítés. A vetítést˝ol megkövetelhetjük, hogy az emberi látásra adjon valamilyen modellt. A legegyszer˝ubb modell a lyukkamera, elterjedt latin kifejezéssel camera obscura). Fizikai megvalósítása egy minden oldalról fényt˝ol védett doboz, melybe a fény egy apró lyukon keresztül hatol be. A kép a lyukkamerán belül a lyukkal ellentétes oldalon válik láthatóvá (ld. 2.4. ábra).

T

K

2.4. ábra. A lyukkamera (camera obscura) képalkotása Fizikai szempontból a lyukkamera képe a tárgy távolságától függetlenül éles (nagy a mélységélessége), ugyanakkor fényszegény a lyuk kicsiny átmér˝oje miatt. A lyuk növelése viszont a képet elmosódottá teszi, ennek korrigálására van szükség a fényképez˝ogépekben lencsére. A 2.4. ábra szerinti elrendezésben a kép fordított állású a tárgyhoz képest. A matematikai


26

modell megalkotásakor azonban nem jelent gondot a 2.5. ábra szerinti elrendezés, amelyben a kép egyenes állású. képsík: z = 0

T

K

C

z

2.5. ábra. A képsík és a centrum geometriai elhelyezése. A képsík az xy sík, a vetítés C centruma a z tengely −1/r pontja. Írjuk le a lyukkamera m˝uködését algebrailag! A lyukkamera által megvalósított leképezés matematikai szempontból centrális vetítés. Legyen r 6= 0, a centrum C = (0, 0, −1/r), a képsík az xy sík, azaz a z = 0 sík. A tárgypont P = (x, y, z). A CP egyenes azon pontját keressük, amelynek harmadik koordinátája zérus. Az egyenes paraméteres el˝oállítása X = tP + (1 − t)C (t ∈ R) így a képpont (vetületi pont) keresett paraméterére 1 tz + (1 − t) − =0 r teljesül, ahonnan t=

1 . zr + 1

Ezt a paraméterértéket visszahelyettesítve az egyenes X = tP + (1 − t)C el˝oállításába x x0 = , zr + 1 (2.2) y y0 = zr + 1 adódik. Most térjünk át homogén koordinátákra! A bal oldalon elvégezve az x0 = x10 /x30 és y0 = x20 /x30 , valamint a jobb oldalon az x = x1 /x4 , y = x2 /x4 , z = x3 /x4 helyettesítéseket, x10 = x1 , x20 = x2 , x30 = rx3 + x4


27

adódik, amely eredményt mátrixszorzással felírhatjuk a következ˝o alakban:    x1  0  1000   x1 x20  = 0 1 0 0 x2  . (2.3) x3  00r1 x30 x4 A továbbiakban legyen   1000 Πr = 0 1 0 0 . 00r1 y′

x′

2.6. ábra. A modell centrális vetülete. A centrum a z tengelyen van és harmadik koordinátája ez esetben pozitív. A nem látható éleket vékonyabb vonallal rajzoltuk. A (2.3)-ben, illetve ekvivalens módon (2.2)-ben megadott leképezés tört lineáris leképezés. A képerny˝o síkjára történ˝o mer˝oleges vetítés megkapható a centrális vetítés határeseteként, r → 0 esetén (azaz „a centrum a végtelenhez tart”) a (2.2) összefüggés pontosan a harmadik koordináta levágását jelenti. 2.2. Példa (hamis perspektíva). A hamis perspektíva a két dimenziós kép olyan transzformálása, mely a térbeliség érzetét kelti: ld. 2.7. ábra. Képtranszformációval lehet megvalósítani, például úgy, hogy a centrális vetítés képletéhez analóg formulákat alkalmazunk. A centrális vetítésnél x y x0 = , y0 = , 1 + zr 1 + zr a hamis perspektívánál x y x0 = , y0 = 1 + f (x, y) 1 + f (x, y) ahol f egy alkalmasan választott függvény. Például 1 f (x, y) = − exp(−ax2 − by2 ) 2 esetén a függvény az origó környékét „nagyítja”.

2.2. SZEMLÉLETES KÉP KÉSZÍTÉSE

28

2.7. ábra. Hamis perspektíva: példa Vasarely stílusában. A piros pöttyök az eredeti képen egybevágó körök voltak.

Ö SSZEFOGLALÓ ferde axonometria: R3 → R2 , P 7→ AP, (A ∈ R2×3 , rang A = 2). 100 mer˝oleges vetítés: A = Π0 = . 010 1 0 − vv31 párhuzamos vetítés: A = , (v1 , v2 , v3 ) a vetítés iránya. 0 1 − vv23 centrális axonometria: P3 → P2 , [x] 7→ [Ax], (A ∈ R3×4 , rang A = 3).   1000 centrális vetítés: A = Πr = 0 1 0 0, (0, 0, −1/r) a centrum. 00r1 2.2. Szemléletes kép készítése 2.2.1. Ortogonális axonometria. Az ábrázoló geometria sokrét˝u feladatköréb˝ol most a szemléletes képalkotást emeljük ki. A szemléletes kép készítés problémájának lényege az, hogy a modellr˝ol könnyen el˝oállítható kép a modell valamely egyszer˝u vetülete, amely nem biztos, hogy szemléletes. A 2.2. ábrán látható kép a fejezetben szerepl˝o modellr˝ol egy egyszer˝u vetület, amelyet azonban egyáltalán nem érzünk szemléletesnek. Két egyszer˝u stratégiával juthatunk el a szemléletes képhez. Képzeljük el, hogy egy kisméret˝u tárgyat kell alaposan szemügyre vennünk, például egy autómodellt: kezünkbe vesszük és körbeforgatjuk. Ha az eredeti autót


29

tanulmányozzuk, akkor viszont körbejárjuk. Az els˝o stratégia a szemléletes képhez a modell transzformációjával jut el, a második stratégia a néz˝opontot változtatja. Ebben a tananyagban az els˝o stratégiát alkalmazzuk. A modell transzformációjaként izometriákat illetve (az el˝oz˝oekt˝ol csak skálázásban különböz˝o) hasonlóságokat engedünk meg. 2.3. Definíció. A tér egy hasonlósági transzformációjának és egy síkra történ˝o mer˝oleges vetítésnek a szorzatát ortogonális axonometriának nevezzük. A továbbiakban feltételezzük, hogy a hasonlóságnak az origó fixpontja, továbbá a mer˝oleges vetítés az xy koordinátasíkra történ˝o mer˝oleges vetítés, így az axonometria lineáris leképezés lesz. Az eltolások ortogonális axonometriánál a szemléletességhez nem járulnak hozzá, így a tárgyalásban az általánosság nem sérül. 2.4. Példa. (Ld. a 2.8. ábrát!) Forgassuk el a modellt az y tengely körül φ szöggel a balkéz-szabály szerint, majd az x tengely körül ψ szöggel a jobbkéz-szabály szerint, ezután vetítsünk mer˝olegesen az xy síkra. Az így kapott axonometria mátrixa: cos φ 0 − sin φ ∗ V = Π0 · Rx (ψ) · Ry (φ ) = . − sin ψ sin φ cos ψ − sin ψ cos φ y′

x′ z′

2.8. ábra. Ortogonális axonometria: mer˝oleges vetítés a képerny˝ore a modell ortogonális transzformációja után

A példában megadott ortogonális axonometria a függ˝oleges irányt „nem borítja föl”. Ha a két forgatást fordított sorrendben hajtanánk végre, már nem lenne így. Az ortogonális axonometria megadása a 2.4. példában a φ és ψ szögek megadását jelentette. Jóllehet ez nagyon egyszer˝u, mégis sok esetben intuitívabb lehet, ha R3 kanonikus bázisának a képét adjuk meg, azaz az ortogonális axonometria mátrixának oszlopait. A három képvektor (három


30

oszlop) azonban nem vehet˝o föl tetsz˝olegesen, a következ˝oekben ezt a problémát vizsgáljuk. 2.5. Tétel (Gauss-tétel). V ∈ R2×3 akkor és csakis akkor ortogonális axonometria mátrixa, ha sorai egymásra mer˝oleges, azonos hosszúságú vektorok. B IZONYÍTÁS . Az egyszer˝uség kedvéért olyan ortogonális axonometriára bizonyítjuk az állítást, ahol ortogonális transzformáció és mer˝oleges vetítés szorzatáról van szó, tehát a hasonlóság aránya 1. A tétel algebrai átfogalmazása ekkor a következ˝o: legyen V ∈ R2×3 . V akkor és csakis akkor áll el˝o V = Π0 · U alakban, ahol U ∈ R3×3 ortogonális mátrix, Π0 pedig az xy koordinátasíkra történ˝o mer˝oleges vetítés, ha V ·V t = I2 . U legyen ortogonális mátrix: U · U t = I3 . Legyen el˝oször V = Π0 · U. Ekkor V ·V t = Π0 ·U ·U t · Πt0 = Π0 · Πt0 = I2 . Megfordítva, ha V · V t = I2 teljesül, akkor ez azt jelenti, hogy V sorai egymásra mer˝oleges egységvektorok. Egészítsük ki a sorvektorokat R3 ortonormált bázisává. A kiegészített mátrix legyen U. Mivel U sorai egymásra mer˝oleges egységvektorok, ezért oszlopai is azok, és V = Π0 ·U nyilvánvalóan teljesül. 2.6. Következmény. Az (x1 , y1 ), (x2 , y2 ), (x3 , y3 ) vektorok akkor és csakis akkor alkotják R3 kanonikus bázisának ortogonális axonometrikus képét, ha x12 + x22 + x32 = y21 + y22 + y23 , (2.4) x1 y1 + x2 y2 + x3 y3 = 0 teljesül. Összefoglalva, az ortogonális axonometria x1 x2 x3 V= y1 y2 y3 mátrixát úgy is meg lehet adni, hogy az oszlopok közül fölveszünk tetsz˝olegesen kett˝ot, pl. az (x1 , y1 ) és (x2 , y2 ) oszlopokat, és a harmadik oszlopot kiszámítjuk a (2.4) egyenletrendszer alapján. (Általában két megoldás is lesz.) A számítást elvégezhetjük komplex aritmetikával is. Az R2 halmazt a szokásos módon azonosítjuk C-vel: (x, y) ↔ x + iy, továbbá legyen α = x1 + iy1 , β = x2 + iy2 , γ = x3 + iy3 . (2.4) ekvivalens az alábbi egyenlettel: (2.5)

α 2 + β 2 + γ 2 = 0.

(2.5)-ben elvégezve a négyzetre emelést: (x12 + x22 + x32 − y21 − y22 − y23 ) + 2i(x1 y1 + x2 y2 + x3 y3 ) = 0

adódik. A bal oldalon álló komplex szám akkor és csakis akkor 0, ha a valóspés képzetes része egyaránt zérus, ami éppen a megadott állítás, így γ = −α 2 − β 2 (ahol a gyökvonás kétérték˝u).

2.3. FERDE AXONOMETRIA ÉS CENTRÁLIS AXONOMETRIA

31

2.2.2. Hasonlóság és centrális projekció szorzata. A 2.1.3. pontban megadott egyszer˝u centrális projekció esetén (tehát a centrum a z koordinátatengelyen van és az xy síkra vetítünk) szemléletes képhez a modell transzformációjával juthatunk. Alkalmazhatjuk a modell x vagy y tengely körüli forgatását, tetsz˝oleges eltolást, skálázást illetve ezek kompozícióját. Pl. homogén koordináták alkalmazásával: V = Πr · T (l, m, n) · Rx (ψ) · R∗y (φ ) =   cos φ 0 − sin φ l   =  − sin ψ sin φ cos ψ − sin ψ cos φ m  . r cos ψ sin φ r sin ψ r cos ψ cos φ 1 + rn Az el˝obbi mátrix oszlopainak a geometriai jelentése egyszer˝u. Jelölje a mátrix oszlopait rendre a1 , a2 , a3 , a4 . Nyilván teljesül         0 0 0 1 1  0 0  0        a1 = V  0 , a2 = V 0 , a3 = V 1 , a4 = V 0 , 0 0 1 0 azaz az els˝o három oszlop a megfelel˝o tengely végtelen távoli pontjának a képe, míg a negyedik oszlop az origó képe. Aszerint, hogy a1 , a2 , a3 között hány közönséges pont van, beszélünk 1, 2 vagy 3 iránypontos perspektíváról. A gyakorlati ábrázolási feladatokban sokszor célszer˝u, ha az y tengely végtelen távoli pontjának a képe végtelen távoli marad, amelynek feltétele a V mátrix használata esetén ψ = 0, azaz x körül nem forgatunk. (Így a függ˝oleges egyenesek nem lesznek összetartóak.) Az y-körüli elforgatás és valamilyen eltolás általában szép szemléletes képet ad két iránypontos perspektívában. A 2.1. ábra ezzel a módszerrel készült; ld. még a 2.9–2.11. ábrákat. Ö SSZEFOGLALÓ szemléletes kép készítése modelltranszformációval: elforgatás a koordinátatengelyek körül (mer˝oleges vetítés alkalmazásakor); centrális vetítés esetén emellett még eltolások is. ortogonális axonometria: a tér egy hasonlósági transzformációjának és egy síkra történ˝o mer˝oleges vetítésnek a szorzata. Gauss-tétel: V ∈ R2×3 akkor és csakis akkor ortogonális axonometria mátrixa, ha sorai egymásra mer˝oleges, azonos hosszúságú vektorok. 2.3. Ferde axonometria és centrális axonometria A ferde axonometriát a 2.1. definícióban vezettük be. A ferde axonometria A mátrixának a1 , a2 , a3 oszlopait a tér kanonikus bázisvektorainak képei alkotják. Az ortogonális axonometriától eltér˝oen (ahol csak két képvektort


32

y′

z′

Ux

x′

Uz

2.9. ábra. Két iránypontos perspektíva a modell elforgatásával. A vetítés centruma a z tengelyen van, a modellt az y tengely körül forgattuk. Az ábrán Ux és Uz jelöli az x és z tengely végtelen távoli pontjának képét. y′

Ux

Uz

x′ z′

2.10. ábra. Két iránypontos perspektíva a modell elforgatásával és eltolásával. A vetítés centruma a z tengelyen van, a modellt az y tengely körül forgattuk, majd ugyanezen tengely irányában eltoltuk.


33

y′

x′

z′

2.11. ábra. Három iránypontos perspektíva. A modelltranszformáció során az x tengely körül is forgattuk.

vehettünk föl tetsz˝olegesen), mind a három képvektort fölvehetjük tetsz˝olegesen – egyetlen megkötés, hogy a fölvett vektorrendszer rangja 2 legyen. A mátrix megadására különböz˝o gyakorlati módszerek vannak, ezek közül megadunk néhány fontosabbat. Az ábrák alapján az axonometria mátrixának fölírása legyen az olvasó feladata! 2.7. Példa (Standard izometrikus projekció, 2.12. ábra). A ferde axonometriát akkor nevezzük izometrikusnak, ha a mátrixának oszlopai azonos hosszúságúak: ka1 k = ka2 k = ka3 k. A standard izometrikus projekció esetén a bázisvektorok képeinek szöge 120◦ . a2

30◦ a3

x a1

2.12. ábra. Standard izometrikus axonometria

2.8. Példa (45◦ -izometrikus, vagy katona perspektíva).


34

a2

45◦

x a1

a3

2.13. ábra. 45◦ -izometrikus axonometria 2.9. Példa (42◦ /7◦ -dimetrikus projekció). A dimetrikus axonometriánál két bázisvektor képének hossza azonas, a harmadiké pedig ett˝ol az értékt˝ol eltér˝o. Ennél a ferde axonometriánál ka1 k = ka2 k = 2ka3 k. a2

a3

42◦

7◦

a1

x

2.14. ábra. 42◦ /7◦ -dimetrikus axonometria

2.10. Példa (cabinet-dimetrikus, vagy kínai perspektíva). A 2.15. ábrán az α szög értéke leggyakrabban 45◦ vagy 30◦ . a2

a3

α

a1

x

2.15. ábra. Cabinet-dimetrikus axonometria


35

A továbbiakban azt vizsgáljuk meg, hogy a ferde axonometriának van-e valamilyen geometriai jelentése. 2.11. Tétel (Az axonometria alaptétele – I). Minden axonometrikus leképezés el˝oáll egy R3 → R2 párhuzamos vetítés és egy R2 → R2 lineáris izomorfizmus szorzataként, azaz az axonometrikus kép affin kapcsolatban van az alakzat egy párhuzamos vetületével. B IZONYÍTÁS . Legyen a11 a12 a13 , rang P = 2. P= a21 a22 a23 Az általánosság megszorítása nélkül föltehetjük, hogy az els˝o két oszlop lineárisan független, azaz a11 a12 . (2.6) det A 6= 0, A = a21 a22 P egydimenziós magterét generálja a v = (v1 , v2 , v3 ) 6= 0 vektor: ker P = L(v), a v által generált egy dimenziós altér. Azt állítjuk, hogy P az xy síkra v-vel párhuzamos vetítés és az A-val történ˝o bal szorzás (mint lineáris izomorfizmus) szorzata. Megjegyezzük, hogy v3 = 0 azt jelentené, hogy az xy sík nem zéró vektora A magterében lenne, így ez ellentmondana (2.6)-nak. Jelölje V a v irányú párhuzamos vetítés mátrixát! 1 0 − vv31 a11 a12 −a11 vv13 − a12 vv23 a11 a12 A ·V = · = . a21 a22 0 1 − vv23 a21 a22 −a21 vv13 − a22 vv23 Azonban v ∈ ker P:

v1 v2 − a12 = a13 v3 v3 v2 v1 a21 v1 + a22 v2 + a23 v3 = 0 =⇒ −a21 − a22 = a23 , v3 v3 tehát P = A ·V . a11 v1 + a12 v2 + a13 v3 = 0 =⇒ −a11

2.12. Tétel (Az axonometria alaptétele – II). Minden axonometrikus leképezés el˝oáll egy R3 → S mer˝oleges vetítés és egy S → R2 lineáris izomorfizmus szorzataként, ahol S a tér egy alkalmas két dimenziós altere. B IZONYÍTÁS . Az el˝oz˝o tétel bizonyításának jelöléseivel. S legyen P magterének ortogonális komplementere, azaz az L(v) egyenesre mer˝oleges, origóra illeszked˝o sík. 2.13. Tétel (Pohlke). Minden axonometria egy párhuzamos vetítés és egy hasonlóság szorzata, azaz egy alakzat axonometrikus képe hasonló az alakzat valamely síkra vonatkozó párhuzamos vetületéhez. B IZONYÍTÁS . A bizonyításhoz egy elemi segédtételre van szükségünk, nevezetesen minden ellipszis alapú hengernek van körmetszete. Az alaptétel els˝o változatának bizonyításakor már bevezetett jelöléseket használjuk,


36

tehát az axonometria A ·V alakban írható föl, ahol V párhuzamos vetítés, A pedig lineáris izomorfizmus. Vegyünk föl az xy síkban egy tetsz˝oleges, origó középpontú k kört. Leˆ S∗ legyen olyan origóra illeszked˝o sík, hogy ebben fölvett gyen A−1 (k) = k. alkalmas, origó középpontú k∗ kör v-vel párhuzamos vetülete éppen kˆ legyen. Az xy síkra történ˝o, v-vel párhuzamos vetítést, azaz V -t, bontsuk föl az S∗ síkra történ˝o v-vel párhuzamos V1 vetítés és az S∗ sík xy síkra történ˝o, szintén v-vel párhuzamos V2 vetítés szorzatára: V = V2 · V1 . Ezt azért tehetjük meg, mert S∗ nem lehet v-vel párhuzamos. Most P = A ·V2 ·V1 . Az A ·V2 lineáris izomorfizmus azonban a k∗ körhöz a k kört rendeli, azaz ez a leképezés hasonlóság az S∗ és R2 síkok között, ami a bizonyítandó állítást jelenti. A bizonyítást az alábbi diagrammon követhetjük: V

V

A

1 2 R3 −→ S∗ −→ R2 −→ R2 .

A centrális axonometriát a 2.1. definícióban vezettük be. A centrális projekció példa centrális axonometriára. Mivel [A · (tx)] = [tA · x] = [A · x], (t 6= 0), ezért A és tA ugyanazt a centrális axonometriát adja meg. Legyen A = (a1 , a2 , a3 , a4 ), ahol ai az A mátrix i-edik oszlopát jelöli. [a1 ] = Ux , [a2 ] = Uy , [a3 ] = Uz rendre az x, y, z tengelyek végtelen távoli pontjának a képe, [a4 ] = O pedig az origó képe. A tengelyek egységpontjainak képe rendre: [a1 + a4 ] = Ex , [a2 + a4 ] = Ey , [a3 + a4 ] = Ez . Az (O,Ux ,Uy ,Uz , Ex , Ey , Ez ) ponthetes a centrális axonometria bázisalakzata. Megjegyezzük, hogy (O,Ux ,Uy ,Uz ) még nem határozza meg a centrális axonometriát, hiszen a pontok különböz˝o reprezentánsai általában nem adnak egymáshoz arányos mátrixokat: (α1 a1 , α2 a2 , α3 a3 , α4 a4 ) 6= α(a1 , a2 , a3 , a4 ). A következ˝o, geometriai jelleg˝u elemzéshez, a speciális esetek elkerülése végett, tegyük föl, hogy a bázisalakzat pontjai különböz˝o pontok. Az (Ex , Ey , Ez ) és (Ux ,Uy ,Uz ) háromszögpár egy Désargues-féle háromszögpár, azaz csúcsaira ( =⇒ oldalaira) nézve perspektív háromszögpár. (A pontok között lehetnek végtelen távoli pontok is.) 2.14. Tétel (a bázisalakzat fölvételének szabadsága). Tetsz˝oleges Désargues-féle háromszögpár a perspektivitás centrumával egy centrális axonometria bázisalakzatát adja meg. B IZONYÍTÁS . Legyen A = ([a1 ], [a2 ], [a3 ]), B = ([b1 ], [b2 ], [b3 ]) a két perspektivikus háromszög, a perspektivitás centruma [a4 ]. (ai , bi , a4 ∈ ◦

R3 , i = 1, 2, 3.) Az összes olyan centrális axonometria mátrixa, melynél az origó képe [a4 ] és az egyes tengelyek végtelen távoli pontjának képe pedig A, megadható valamely nem zéró α1 , α2 , α3 skalárokkal a következ˝o


37

alakban: (α1 a1 , α2 a2 , α3 a3 , a4 ). (A negyedik oszlop arányossági tényez˝ojével lehet osztani.) A kérdés az, hogy vannak-e olyan α1 , α2 , α3 nem zéró skalárok, hogy [αi ai + a4 ] = [bi ]. Mivel (A, B) Désargues-féle háromszögpár, ezért rang(ai , bi , a4 ) = 2. Legyen i = 1, i = 2, 3-ra analóg módon. A zérusvektort lineárisan kombinálva: ta1 + rb1 + sa4 = 0, valamely nem triviális (t, r, s) együtthatórendszerre. S˝ot, a geometriai föltevés szerint (a bázisalakzat pontjai különböz˝oek) azt is tudjuk, hogy s 6= 0, ellenkez˝o esetben ugyanis (a1 , b1 ) lineárisan függ˝o rendszer, azaz [a1 ] = [b1 ] lenne. Tehát t r a1 + a4 = − b1 , s s azaz α1 = t/s mellett [α1 a1 + a4 ] = [b1 ].

A továbbiakban a centrális axonometria geometriai jelentésével foglalkozunk. 2.15. Tétel (a centrális axonometria f˝otétele). Minden centrális axonometria egy centrális projekció és egy projektív transzformáció szorzata, azaz a centrális axonometrikus kép projektív az alakzat valamely centrális vetületéhez. B IZONYÍTÁS . A bizonyítás analóg a 2.11 tétel bizonyításához.

A centrális axonometriára Pohlke tételét nem lehet direkt módon általánosítani, nem igaz az, hogy tetsz˝oleges centrális axonometria centrális vetítés és hasonlóság szorzata. 2.16. Tétel (Szabó–Stachel–Vogel). Legyen (O,Ux ,Uy ,Uz , Ex , Ey , Ez ) egy centrális axonometria bázisalakzata, továbbá a bázisalakzat egyetlen pontja se legyen végtelen távoli pont. (2.16. ábra) A bázisalakzat által meghatározott centrális axonometria akkor és csakis akkor centrális projekció és hasonlóság szorzata, ha fennáll

OEx ExUx

2 OEy 2 OEz 2 : : = tg α : tg β : tg γ, EyUy EzUz

ahol α = UyUxUz ^, β = UzUyUx ^, γ = UyUzUx ^.


y′

38

Uz

Ux Ey

Ex x′

Ez z

′

Uy

2.16. ábra. A centrális axonometria bázisalakzata Ö SSZEFOGLALÓ a ferde axonometria geometriai jelentése; Pohlke-tétel: minden axonometria egy párhuzamos vetítés és egy hasonlóság szorzata, azaz egy alakzat axonometrikus képe hasonló az alakzat valamely síkra vonatkozó párhuzamos vetületéhez. a centrális axonometria intuitív megadása: Désarguesháromszögpárral. Egy centrális axonometriának általában nincs Pohlke tételéhez analóg geometriai jelentése.

3. FEJEZET

Szabad formájú görbék modellezése 3.1. Parametrizált görbék Ha egy anyagi pont mozgását a síkban vagy a térben le akarjuk írni, akkor legegyszer˝ubb, ha –origó rögzítése után– megadjuk helyzetvektorát az id˝o függvényében. Ebb˝ol a helyzetvektor-id˝o függvényb˝ol a mozgás kinematikai jellemz˝oit már meg lehet adni, az els˝o deriváltja (ha létezik) a sebesség, a második deriváltja a gyorsulás. Parametrizált görbe alatt egy ilyen helyzetvektor-id˝o függvényt értünk. A mozgó pont pályája egy ponthalmaz a síkban vagy a térben – ezt egyszer˝uen görbének nevezzük. 3.1. Definíció. Egy c : [a, b] → Rn differenciálható leképezést parametrizált görbének nevezünk. A parametrizált görbe reguláris, ha ∀t ∈ (a, b)-re c0 (t) 6= 0 (regularitási feltétel). n = 2 esetén síkgörbér˝ol, n = 3 esetén térgörbér˝ol beszélünk. 3.2. Példa (egyenletes körmozgás). Egy pont állandó ω > 0 szögsebességgel mozog egy a > 0 sugarú, origó középpontú körön. Határozzuk meg a helyzetvektor-id˝o leképezést! A t = 0 id˝opontban a pont koordinátái (a, 0). A pont irányszöge t id˝opontban ϕ = ωt, így koordinátái (a cos(ωt), a sin(ωt)). Tehát a görbe paraméteres el˝oállítása: c : [0, ∞) → R2 , t 7→ c(t) = (a · cos(ωt), a · sin(ωt)). A regularitási feltétel nyilván teljesül: c0 (t) = (−aω · sin(ωt), aω · cos(ωt)), kc0 (t)k = aω 6= 0.

A kc0 (t)k = aω összefüggés, mely a kerületi sebesség és a szögsebesség közti kapcsolatot adja meg, a középiskolai fizikából ismer˝os lehet. A paraméteres el˝oállításból azonnal következik, hogy a mozgásra x2 + y2 = a2 teljesül, ami a kör egyenlete (x = a cos(ωt), y = a sin(ωt)). Az a sugár a mozgás geometriai jellemz˝oje, ω a mozgás fizikai jellemz˝oje. 3.3. Példa (hengeres csavarvonal). Egy a sugarú egyenes forgáshenger tengelye a z tengely. Kiválasztjuk egy alkotóját, az alkotón egy pont (a hengerhez képest) b > 0 sebességgel egyenletes mozgást végez, miközben a hengert a z tengely körül ω szögsebességgel forgatjuk. Határozzuk meg a helyzetvektor-id˝o függvényt. A t = 0 id˝opontban a pont koordinátái (a, 0, 0). 39

3.1. PARAMETRIZÁLT GÖRBÉK

40

y

z x

3.1. ábra. Hengeres csavarvonal A mozgás vetülete az xy síkra egyenletes körmozgás, a z tengelyre pedig egyenesvonalú egyenletes mozgás. Így a paraméteres el˝oállítás: c : [0, ∞) → R3 , t 7→ c(t) = (a cos(ωt), a sin(ωt), b · t) (a, b > 0). √ kc0 (t)k = a2 ω 2 + b2 6= 0, azaz a regularitási feltétel teljesül. Ezt a görbét hengeres csavarvonalnak nevezzük (3.1. ábra). 3.4. A LGORITMUS (görbék poligonális approximációja). A c : [a, b] → Rn (n = 2 vagy 3) folytonos parametrizált görbe ábrázolásához osszuk fel a paraméter intervallumot egyenl˝o részekre, azaz jelöljük ki a b−a ti = a + · i, i = 0, . . . , N N paraméterértékeket valamely N természetes szám rögzítése után. A görbét a [c(a), c(t1 ] ∪ [c(t1 ), c(t2 )] ∪ . . . ∪ [c(tN−1 , c(tN )] poligonnal modellezzük. 3.4. D RAW C URVE Input: N move to c(a) for i = 1 to N do line to c(a + b−a N · i) Speciális esetben kapjuk a folytonos függvény grafikonját, ekkor c(t) = (t, f (t)), ahol f : [a, b] → R a szóban forgó függvény. 3.5. Megjegyzés. A paramétertartomány felosztására nem mindig az egyenletes (uniformális) felosztást érdemes használni. A nagyobb görbület˝u részeken a beosztást gyakran célravezet˝o s˝uríteni (adaptív mintavételezés.)

3.2. A KEVERÉSI ELV

41

Annak megállapítására, hogy kell-e a beosztást finomítani egy adott [u, v] intervallumban, több kritériumot is lehet használni. Ezek közül felsorolunk néhányat. Legyen m ∈ (u, v), - a c(u)c(m)c(v) háromszög területe kisebb, mint egy rögzített hibahatár - ∠c(u)c(m)c(v) ≈ π - c(m) egy rögzített hibahatárnál közelebb esik a [c(u), c(v)] szakaszhoz. - kc(u) − c(m)k + kc(m) − c(v)k ≈ kc(u) − c(v)k. Az m érték kiválasztására a módszer nagyon érzékeny. A legegyszer˝ubb, ha m = (u + v)/2. Ö SSZEFOGLALÓ parametrizált görbe: c : [a, b] → Rn differenciálható leképezés. parametrizált görbe rajza: poligonális approximáció uniformális vagy adaptív mintavételezéssel. 3.2. A keverési elv A számítógéppel támogatott tervezésben, rajzolásban fontos szerepe van a parametrizált görbéknek. A görbemodellezés általunk vizsgált alapfeladata, hogy egy szabad formájú görbe (pl. szabad kézzel megrajzolt görbe) parametrizált modelljét adjuk meg. A szabad formájú görbét nem biztos, hogy pontosan tudjuk paraméterezni, a cél az, hogy a modell valamilyen értelemben közelítse az eredeti görbét. Erre az egyik általános módszer a súlyozásos (vagy más szóval keveréses) módszer. Ez abból áll, hogy rögzítünk bizonyos pontokat –az úgynevezett kontrollpontokat– majd ezeket polinomiális súlyfüggvényekkel (a szakirodalomban elterjedt angol terminológia blending function, azaz kever˝o függvény) súlyozzuk (keverjük). 3.6. Definíció. A p0 , . . . , pn ∈ RN (N = 2 vagy 3) kontrollpontokhoz és W0 (u), . . . ,Wn (u), (u ∈ I ⊂ R) a súlyfüggvényekhez tartozó modellgörbe ∑n Wi (u)pi (3.1) p(u) = i=0 , u ∈ I. ∑ni=0 Wi (u) Tehát minden u paraméterértékre p(u) megegyezik a kontrollpontok W0 (u), . . . ,Wn (u) súlyokkal vett súlyozott közepével. N = 2-re síkgörbét, N = 3-ra térgörbét kapunk. 3.7. Definíció. Ha minden u ∈ I paraméterértékre ∑ni=0 Wi (u) = 1, akkor azt mondjuk, hogy a súlyfüggvények egységbontást alkotnak. Ha a súlyfüggvények egységbontást alkotnak, akkor a modell paraméteres el˝oállítása is egyszer˝usödik: (3.2)

n

n

i=0

i=0

p(u) = ∑ Wi (u)pi , ( ∑ Wi (u) = 1, u ∈ I ),

3.2. A KEVERÉSI ELV

42

továbbá a modellre egy fontos tulajdonság, az affin invariancia teljesül: a modellgörbe affin képe megegyezik a kontrollpontok affin képéhez tartozó modellgörbével, ugyanazon kever˝o függvényekkel. 3.8. Tétel (Affin invariancia). Legyen F : RN → RN ,

x 7→ F(x) = Ax + b, A ∈ GL(N), b ∈ RN

affin transzformáció, n

p(u) = ∑ Wi (u)pi , u ∈ I i=0

parametrizált görbe, ahol n

∑ Wi(u) = 1, u ∈ I

i=0

teljesül. Ekkor n

F(p(u)) = ∑ Wi (u)F(pi ), u ∈ I. i=0

B IZONYÍTÁS . n

F(p(u)) = A ∑ Wi (u)pi + b = i=0 n

n

= ∑ Wi (u)Api + ∑ Wi (u)b = i=0 n

i=0

n

= ∑ Wi (u)(Api + b) = ∑ Wi (u)F(pi ). i=0

i=0

Ha a súlyfüggvények az egységbontás tulajdonsága mellett ráadásul nem negatívak, akkor újabb fontos geometriai tulajdonság, a konvex burokban maradás is teljesül. Emlékeztet˝oül, egy ponthalmazt konvexnek nevezünk, ha bármely két pontjával együtt a két pont összeköt˝o szakaszát is tartalmazza, azaz a K ⊂ RN halmaz konvex, ha ∀p, q ∈ K, ∀t ∈ [0, 1] : tq + (1 − t)p ∈ K.

Egy ponthalmaz konvex burka alatt azt a legsz˝ukebb konvex halmazt értjük, amely az adott halmazt tartalmazza. Egyszer˝uen belátható, hogy egy halmaz konvex burkát megkaphatjuk a halmazt tartalmazó összes konvex halmaz metszeteként. Kevésbé nyilvánvaló, hogy egy ponthalmaz konvex burka megkapható a pontjaiból képezett összes konvex lineáris kombináció uniójaként. (A ∑ki=0 αi pi lineáris kombináció konvex, ha ∑ki=0 αi = 1 és αi ≥ 0.) Megjegyezzük még, hogy véges sok pont konvex burka esetleg elfajuló konvex sokszöglemez (síkban) vagy konvex poliédertest (térben). Mivel egységbontó és nemnegatív súlyfüggvények mellett (3.2) konvex lineáris kombináció, ezért p(u) a kontrollpontok konvex burkában van.

3.3. SZPLÁJNOK

43

3.9. Tétel (konvex burokban maradás). Ha n

p(u) = ∑ Wi (u)pi , u ∈ I i=0

parametrizált görbe, ahol n

∑ Wi(u) = 1, és Wi(u) ≥ 0, u ∈ I

i=0

teljesül, akkor p(u) a p0 , . . . , pn kontrollpontok konvex burkában van. Ha a modellgörbe a kontrollpontokat tartalmazza, akkor azt interpolációs görbének nevezzük. Az approximációs görbe nem feltétlenül tartalmazza a kontrollpontokat, de azokhoz (valamilyen értelemben) „közel” halad. Interpolációra a gyakorlatban sokszor el˝ofordul az ún. interpolációs alapfeladat. Adottak a p0 , p1 , . . . , pn ∈ RN pontok, valamint az u0 ≤ u1 ≤ · · · ≤ un paraméterértékek. Olyan p : [u0 , un ] → RN legalább Cr osztályú parametrizált görbét keresünk, hogy ∀i ∈ {0, . . . , n} :

p(ui ) = pi .

Ö SSZEFOGLALÓ ∑ni=0 Wi (u)pi . ∑ni=0 Wi (u) egységbontás: ∑ni=0 Wi (u) = 1. affin invariancia: ha a súlyfüggvények egységbontást alkotnak, akkor a modellgörbe affin képe megegyezik a kontrollpontok affin képéhez tartozó modellgörbével ugyanazon keveréssel. konvex burokban maradás: ha a súlyfüggvények nemnegatívak és egységbontást alkotnak, akkor a modellgörbét a kontrollpontok konvex burka tartalmazza. interpoláló görbe: p(ui ) = pi valamely adott (u0 , u1 , . . . , un ) paraméterrendszerre. modellgörbe: p(u) =

3.3. Szplájnok 3.10. Definíció. Az u0 ≤ u1 ≤ · · · ≤ un paraméterértékekhez, az ún. csomópontokhoz tartozó Cr osztályú szplájn alatt olyan p : [u0 , un ] → RN legalább Cr osztályú parametrizált görbét értünk, melyre a pi : [0, 1] → RN ,

pi (t) = p((ui+1 − ui ) · t + ui ) (i ∈ {0, . . . , n − 1})

parametrizált görbék sima (azaz C∞ ) görbeívek. A

pi (t) = p(u), (u = (ui+1 − ui ) · t + ui )

görbepontnak t a lokális, míg u a globális paramétere. [u0 , u1 , . . . , un ] a szplájn csomópontvektora. Ekvidisztáns csomópontvektorról akkor beszélünk, ha az egymást követ˝o csomópontok távolsága ugyanaz.

3.3. SZPLÁJNOK

44

A szplájn tehát szakaszonként sima parametrizált görbe, és a görbeszakaszok csatlakozási pontjában legalább r-szeri differenciálhatóságot írunk el˝o. 1 Vizsgáljuk meg a C1 osztályú differenciálhatóság feltételét. Globális paraméterrel u − ui p(u) = pi , u ∈ [ui , ui+1 ]; ui+1 − ui így az összetett függvény differenciálási szabálya szerint u − ui 1 0 0 . p (u) = pi · ui+1 − ui ui+1 − ui Az ui csomópontnál balról a pi−1 (t), jobbról a pi (t) görbeszakasz deriváltjait kell képezni: 1 1 u − ui−1 0 0 lim p (u) = lim pi−1 · = p0i−1 (1) · u→ui −0 u→ui −0 ui − ui−1 ui − ui−1 ui − ui−1 u − ui 1 1 lim p0 (u) = lim p0i · = p0i (0) · , u→ui +0 u→ui +0 ui+1 − ui ui+1 − ui ui+1 − ui így a C1 osztályú csatlakozás szükséges és elégséges feltétele, hogy

(3.3)

∆ui p0i−1 (1) = ∆ui−1 p0i (0) ahol ∆uk = uk+1 − uk .

Megjegyezzük, hogy el˝ofordulhat az, hogy a szplájn ugyan C1 osztályú, de mégsem reguláris, mert valamelyik csomópontban a sebességvektor zéróvektor: ekkor a görbének ebben a csomópontban fordulópontja van. Ekvidisztáns csomópontvektor pl. a (0, 1, . . . , n) ∈ Rn+1 . Ekkor p : [0, n] → RN ,

továbbá pi : [0, 1] → RN ,

pi (t) = p(t + i) (i ∈ {0, . . . , n − 1}).

Ekvidisztáns csomópontvektor esetén a C1 osztályú differenciálhatóság feltétele is egyszer˝usödik. Lokális paraméterekkel: p0i−1 (1) = p0i (0). Az el˝oz˝oekhez hasonlóan kaphatjuk meg a szplájn C2 osztályú differenciálhatóságának feltételét. A már megkapott ∆ui p0i−1 (1) = ∆ui−1 p0i (0) (ld. (3.3)) feltétel mellett teljesülnie kell még a (3.4)

(∆ui )2 p00i−1 (1) = (∆ui−1 )2 p00i (0)

1A gyakorlatban különösen fontos a C2 osztályú csatlakozás, mert reguláris görbék C2

osztályú csatlakozása görbületfolytonos szplájnt ad. A görbület a sebességb˝ol és a gyorsulásból kifejezhet˝o: kp0 × p00 k κ= . kp0 k3

3.3. SZPLÁJNOK

45

feltételnek is. A magasabb rend˝u szpálnokra analóg módon folytathatjuk a töréspontokban kirótt feltétel megadását: (r)

(r)

(∆ui )r pi−1 (1) = (∆ui−1 )r pi (0). 3.11. Példa (töröttvonal). A legegyszer˝ubb (nem triviális) szplájn a töröttvonal, amely az interpolációs alapfeladatnak C0 osztályú megoldása. Jelölje p0 , . . . pn az N-dimenziós kontrollpontokat és legyen p : [0, n] → RN ,   (1 − u)p0 + up1 , ha 0 ≤ u ≤ 1,     (2 − u)p1 + (u − 1)p2 , ha 1 ≤ u ≤ 2,    . . . p(u) =  (k + 1 − u)pk + (u − k)pk+1 , ha k ≤ u ≤ k + 1,     ...    (n − u)p n−1 + (u − n + 1)pn , ha n − 1 ≤ u ≤ n. Eszerint p0 súlyfüggvénye ( 1 − u, F0 : [0, n] → R, F0 (u) = 0

ha u ∈ [0, 1], egyébként.

pk (1 ≤ k ≤ n − 1) súlyfüggvénye   u − k + 1, Fk : [0, n] → R, Fk (u) = k + 1 − u,  0

ha u ∈ [k − 1, k], ha u ∈ [k, k + 1] egyébként,

végül pn súlyfüggvénye ( u − n + 1, Fn : [0, n] → R, Fn (u) = 0

ha u ∈ [n − 1, n], egyébként.

Megállapíthatjuk, hogy a súlyfüggvények nem negatívak és egységbontást alkotnak, tehát teljesül a konvex burokban maradás és az affin invariancia tulajdonsága. Mivel p(i) = pi (i = 0, 1, . . . , n), ezért ez egy interpolációs görbe. A szplájn görbeszakaszai a kontrollpontokban töréssel, azaz nem differenciálhatóan csatlakoznak: a szplájn C0 osztályú. (A csatlakozási pontokon kívül természetesen a szplájn C∞ osztályú, azaz sima.) Ez a szplájn lokálisan változtatható, egy kontrollpont legfeljebb két görbeszakaszra van hatással, a többi görbeszakaszt a kiválasztott kontrollpont változtatása nem érinti.

3.4. LAGRANGE-INTERPOLÁCIÓ

46

Ö SSZEFOGLALÓ Cr -osztályú parametrizált szplájn: p : [u0 , un ] → RN szakaszonként sima, az ui csomópontokban r-szer differenciálható görbe. a szplájn r-szer differenciálható az ui töréspontban: ha (s)

(s)

(∆ui )s pi−1 (1) = (∆ui−1 )s pi (0) (s = 1, . . . , r) ahol pi (t) = p((ui+1 − ui ) · t + ui ). 3.4. Lagrange-interpoláció A Lagrange-interpolációs polinom olyan legfeljebb n-ed fokú polinom, mely grafikonja áthalad az (x0 , y0 ), (x1 , y1 ), . . . , (xn , yn ) ∈ R2 páronként különböz˝o rendezett számpárokon. 3.12. Definíció. Az (x0 , y0 ), (x1 , y1 ), . . . , (xn , yn ) ∈ R2 pontokhoz tartozó Lagrange-interpolációs polinom n

(3.5)

p(u) =

n

u − xi . x − x j i i=0

∑ yj ∏

j=0

j6=i

A (3.5) képletben szerepl˝o n

(3.6)

u − xi i=0 x j − xi

L j,n (u; x0 , x1 , . . . , xn ) = ∏ j6=i

polinomokat az (x0 , x1 , . . . , xn ) alappontokhoz tartozó Lagrange-bázisfüggvényeknek nevezzük. i 3.13. A LGORITMUS . A (3.5) polinom „atomi” eleme az xu−x tört. Ennek j −xi kiszámítását úgy végezzük el, hogy xi = x j esetén értéke 1 legyen:

3.13.a. L AGRANGE(a, b, u) if a = b then return 1 else u−a return b−a A Lagrange-interpolációs polinom kiszámításánál az abszcissza értékek az x vektorban, a hozzájuk tartozó megfelel˝o ordináta értékek az y vektorban vannak. A polinomot u ∈ R-ben számítjuk ki. A definícióból közvetlenül következik, hogy ( 1 (3.7) L j,n (xi ; x0 , x1 , . . . , xn ) = δi j = 0

ha i = j, ha i 6= j;


47

3.13. L AGRANGE I NTERPOLATION Input: x, y, u Output: A Lagrange-interpolációs polinom értéke u-ban n ← length(x) − 1 sum ← 0 for j = 0 to n do prod ← 1 for i = 0 to n do prod ← prod·L AGRANGE(xi , x j , u) sum ← sum + y j · prod return sum továbbá ugyanazon alappontokhoz tartozó Lagrange bázisfüggvények egységbontást alkotnak: n

∑ L j,n(u; x0, x1, . . . , xn) = 1.

j=0

Ugyanis az egységbontás tulajdonsága az alappontokban (3.7) miatt teljesül, azonban nem konstans legfeljebb n-ed fokú polinom n + 1-szer ugyanazt az értéket nem veheti föl. A (3.5) képlet még síkban sem alkalmas közvetlenül az interpolációs feladat megoldására, mert az eredmény minden esetben polinom grafikonját adja, azaz a megoldás a kontrollpontok sorrendjét nem veszi figyelembe (ld. 3.2 ábra). p2

p3

p1 p0

p4

3.2. ábra. A Lagrange-interpolációs polinom a kontrollpontok sorrendjét nem veszi figyelembe. Ugyanezen kontrollpontokhoz tartozó interpolációs görbe p0 -tól indulna és p4 -ben végz˝odne, vö. 3.3. ábra. A módszer a Lagrange-interpolációs polinomok egységbontó tulajdonsága miatt alkalmas a (3.2) általános görbemodellezési elv alkalmazására, azaz görbék interpolációjára. Ehhez ki kell jelölnünk egy u0 < u1 < . . . < un ,


48

uk ∈ R paraméterrendszert. Az szeretnénk, ha az interpolációs görbe az ui pontban a pi kontrollpontot adná. 3.14. Definíció. A pi ∈ RN (i = 0, . . . , n, N = 2, 3) kontrollpontokhoz és (u0 , u1 , . . . , un ) ∈ Rn+1 paraméterrendszerhez tartozó Lagrangeinterpolációs görbe alatt a n

(3.8)

p(u) =

∑ L j,n(u; u0, u1, . . . , un)p j

j=0

parametrizált görbét értjük. (A paramétertartomány a valós számok tetsz˝oleges, a paraméterrendszert tartalmazó intervalluma lehet.) Az ui paraméterértékeket csomópontoknak is nevezzük. (3.7) miatt p(ui ) = pi (i = 0, . . . n), azaz az interpolációs feladat C∞ osztályú megoldását kapjuk. Az interpolációs görbe függ a csomópontok választásától, amely önkényes. Lehetséges, hogy az uk paraméterértékek egyenl˝o távolságra vannak egymástól, azaz uk − uk−1 = állandó (ekvidisztáns paraméterezés). Az is kézenfekv˝o választás, hogy a paraméterértékek távolsága vegye figyelembe a kontrollpontok távolságát azaz legyen u0 ∈ R tetsz˝oleges, továbbá u1 = u0 + d(p0 , p1 ), u2 = u1 + d(p1 , p2 ), .. . un = un−1 + d(pn−1 , pn ).

Az ilyen paraméterezést röviden arányos paraméterezésnek nevezzük. (Ld. 3.3. ábra!) p2

p3

p1 p0 p4

3.3. ábra. Lagrange-interpoláció ekvidisztáns paraméterrendszerrel (piros görbe) és arányos paraméterezéssel (kék görbe). A Lagrange-interpolációs módszer el˝onye, hogy az interpolációs feladatra C∞ osztályú megoldást ad, hátránya, hogy a kontrollpontok számának növelésével a fokszám n˝o, ugyanakkor ekvidisztáns csomópont vektorra az interpolációs görbe hibája a fokszám növelésével egyre nagyobb lehet, mint azt a következ˝o példa mutatja.


49

y

1

x 1

-1

3.4. ábra. A Runge-függvény (kékkel) és interpolációja 15-öd fokú Lagrange-interpolációs polinommal, mely ekvidisztáns csomópontokhoz tartozik

y 1

x

-1

1

3.5. ábra. A Runge-függvény (kékkel) és interpolációja 15-öd fokú Lagrange-interpolációs polinommal, mely Csebisev-féle csomópontokhoz tartozik

1 3.15. Példa (Runge-jelenség, ld. 3.4. és 3.5. ábra!). Legyen f (x) = 1+25x 2 (x ∈ [−1, 1]), az úgynevezett Runge-függvény. Vegyünk fel ekvidisztáns csomópont vektort a [−1, 1] intervallumban. Az interpolációs polinom hibája (különösen a −1, 1 közelében) a csomópontok számának növelésével

3.5. HARMADFOKÚ HERMITE-GÖRBÉK

50

egyre nagyobb: ekvidisztáns csomópontok általában alkalmatlanok magasabb fokszámú polinomiális interpolációra. Ha a Runge-függvény interpolációját az ui = cos 2i−1 π , i = 1, 2, . . . , n csomópontokra (az ún. Csebisev2n csomópontokra) végezzük el, akkor egészen más eredményt kapunk. Ö SSZEFOGLALÓ Lagrange-bázisfüggvények: adott az (u0 , u1 , . . . , un ) csomópont vektor . n u − ui . L j,n (u; u0 , u1 , . . . , un ) = ∏ i=0 u j − ui j6=i

Lagrange-interpolációs görbe: : adott az (u0 , u1 , . . . , un ) csomópont vektor és az p0 , p1 , . . . , pn kontrollpontok. n

p(u) =

∑ L j,n(u; u0, u1, . . . , un)p j .

j=0

3.5. Harmadfokú Hermite-görbék 3.16. Definíció. Parametrizált harmadfokú görbeíven, röviden harmadfokú görbén egy p : [0, 1] → RN , u 7→ p(u) = u3 a + u2 b + uc + d parametrizált görbét értünk. a, b, c, d ∈ RN a görbe algebrai együtthatói. 3.17. Tétel. A p harmadfokú görbeívet egyértelm˝uen meghatározzák a görbe geometriai együtthatói, azaz p(0), p(1), p0 (0), p0 (1). B IZONYÍTÁS . p0 (u) = 3u2 a + 2ub + c. A geometriai együtthatók egyszer˝uen kifejezhet˝ok az algebrai együtthatókkal: p(0) = d, 0

p (0) = c,

p(1) = a + b + c + d, p0 (1) = 3a + 2b + c.

Innen az algebrai együtthatókat kifejezve: a = 2p(0) − 2p(1) + p0 (0) + p0 (1),

b = −3p(0) + 3p(1) − 2p0 (0) − p0 (1), c = p0 (0),

d = p(0).

Tehát p(u) = (2u3 − 3u2 + 1)p(0) + (−2u3 + 3u2 )p(1)+ + (u3 − 2u2 + u)p0 (0) + (u3 − u2 )p0 (1).


51

3.18. Definíció. F03 (u) = 2u3 − 3u2 + 1, F13 (u) = −2u3 + 3u2 ,

F23 (u) = u3 − 2u2 + u, F33 (u) = u3 − u2

az ún. harmadfokú Hermite-polinomok. Azaz egy harmadfokú görbe a geometriai együtthatókkal az alábbiak szerint fejezhet˝o ki: p(u) = F03 (u) · p(0) + F13 (u) · p(1) + F23 (u) · p0 (0) + F33 (u) · p0 (1). v0 p0 v1 p1 3.6. ábra. Harmadfokú görbeív a geometriai együtthatókkal

p0

p1

3.7. ábra. A harmadfokú görbeív függése a végpontjaiban adott sebességvektorok irányától

3.5.1. Három pont interpolációja harmadfokú görbeívvel a síkban. Keressünk olyan harmadfokú görbeívet, melynek adottak végpontjai, a végpontokban az érint˝o egyenesek, valamint a görbe egy bels˝o pontja. Jelölje a végpontokat p0 és p1 ; a bels˝o pontot pedig pb . Az érint˝o egységvektorok legyenek t0 és t1 . A problémában három ismeretlen van: a v0 , v1 pályasebességek a kezd˝o és végpontban valamint a bels˝o pont t paramétere. Ezeket az ismeretleneket úgy keressük, hogy pb = F03 (t)p0 + F13 (t)p1 + F23 (t)v0 t0 + F33 (t)v1 t1 teljesüljön. Fölhasználva, hogy F03 (t) + F13 (t) = 1, azt kapjuk, hogy (3.9)

pb − p0 = F13 (t)(p1 − p0 ) + F23 (t)v0 t0 + F33 (t)v1 t1 .


p0

52

p1

3.8. ábra. A harmadfokú görbeív függése a végpontjaiban adott sebességvektorok nagyságától

pb

p0

p1

3.9. ábra. Három pont interpolációja harmadfokú görbeívvel

Tekintsük (3.9)-t, mint az F13 (t), F23 (t)v0 , F33 (t)v1 ismeretlenekre fölírt lineáris egyenletrendszert, ahol az egyenleteket a koordináták adják. Síkban a (3.9) lineáris egyenletrendszer csak két egyenletb˝ol áll. A t paramétert tetsz˝olegesen megválaszthatjuk. Legyen pl. t = 0, 5: pb − p0 − F13 (0, 5)(p1 − p0 ) = F23 (0, 5)v0 t0 + F33 (0, 5)v1 t1 , azaz 1 1 1 pb − p0 − (p1 − p0 ) = v0 t0 − v1 t1 . 2 8 8 Ha a két érint˝o egységvektor lineárisan független, akkor az egyenletrendszer v0 -ra és v1 -re egyértelm˝uen megoldható. A bal oldalt l-lel jelölve, és a megoldásokat Cramer-szabály segítségével kifejezve: v0 = 8 ·

|l, t1 | , |t0 , t1 |

v1 = −8 ·

|t0 , l| . |t0 , t1 |

3.5.2. Az interpolációs alapfeladat C1 osztályú megoldása harmadfokú Hermite-ívekkel. A p0 , p1 , . . . , pn kontrollpontok mellett adjuk meg


53

tetsz˝olegesen a v0 , v1 , . . . , vn sebességvektorokat. A csomópont vektor legyen (0, 1, . . . , n). A pi (u) görbeszakasz legyen a (pi , pi+1 , vi , vi+1 ) geometriai együtthatókhoz tartozó harmadfokú Hermite-görbe, azaz pi (u) = F03 (u)pi + F13 (u)pi+1 + F23 (u)vi + F33 (u)vi+1 , u ∈ [0, 1].

Mivel p0i (1) = vi = p0i+1 (0) ezért a   p1 (u),    p2 (u − 1),    . . . p(u) =  pi (u − i),     ...    p (u − n + 1), n−1

u ∈ [0, 1] u ∈ [1, 2] u ∈ [i, i + 1] u ∈ [n − 1, n]

szplájn az interpolációs alapfeladat C1 osztályú megoldását adja. A gyakorlatban el˝ofordul, hogy csak a kontrollpontokat ismerjük, a sebességvektorokat nem. A sebességvektorokat ilyenkor valamilyen „recept” alapján adjuk meg. Például legyen 1 (3.10) vi = (pi+1 − pi−1 ). 2 A „receptet” jól motiválja, ha a pillanatnyi sebesség fizikai fogalmára gondolunk: a pi−1 , pi+1 közötti ívet a mozgó pont (ekvidisztáns csomópontvektor mellett) 2 egység id˝o alatt teszi meg. Az elmozdulásvektor és a megtett id˝o hányadosa adja a pillanatnyi sebesség közelítését pi -ben. (3.10) nyilvánvalóan nem alkalmazható az i = 0 és i = n indexekre. i = 0-ra lehet például 1 v0 = (p02 − p0 ), 2 0 ahol p2 a p2 kontrollpont tükörképe a p0 és p1 pontok összeköt˝o egyenesére, míg 1 vn = (pn − p0n−2 ), 2 ahol p0n−2 a pn−2 kontrollpont tükörképe a pn−1 és pn összeköt˝o egyenesére (ld. 3.10. ábra). 3.5.3. Az interpolációs alapfeladat C2 osztályú megoldása harmadfokú Hermite-ívekkel. Ismét a (0, 1, . . . , n) csomópont vektorral dolgozunk. Ha a p szplájn legalább C2 osztályú, az azt jelenti, hogy: (3.11)

p0i (1) = p0i+1 (0),

p00i (1) = p00i+1 (0),

(i = 0, . . . , n − 2).

A p görbe sebességvektorát adjuk meg tetsz˝olegesen a rögzített kontrollpontokban a v0 , v1 , . . . , vn vektorokkal, azaz ∀i ∈ {1, . . . , n − 1} : p0 (i) = p0i−1 (1) = p0i (0) = vi ;

és p0 (0) = p00 (0) = v0 , p0 (n) = p0n−1 (1) = vn .


p1

p0

54

p2

p4

p3

3.10. ábra. Görbeillesztés Hermite-eljárással: C1 -osztályú interpolációs görbe

A második deriváltakra vonatkozó (3.11) feltételt használva: F03 00 (1)pi−1 + F13 00 (1)pi + F23 00 (1)vi−1 + F33 00 (1)vi = = F03 00 (0)pi + F13 00 (0)pi+1 + F23 00 (0)vi + F33 00 (0)vi+1 . A deriváltakat kiszámítva, behelyettesítve a 0 és 1 értékeket, valamint rendezve: vi−1 + 4vi + vi+1 = 3(pi+1 − pi−1 ) (i = 1, . . . , n − 1). Ez koordinátánként n − 1 egyenlet v0 , . . . , vn koordinátáira, azaz a v0 és vn vektorokat szabadon megválasztva koordinátánként egy (n − 1) × (n − 1) típusú lineáris egyenletrendszert kapunk: 4v1 + v2 = 3(p2 − p0 ) − v0 ,

v1 + 4v2 + v3 = 3(p3 − p1 ), .. .

vi−1 + 4vi + vi+1 = 3(pi+1 − pi−1 ), .. . vn−2 + 4vn−1 = 3(pn − pn−2 ) − vn . Az el˝obbi lineáris egyenletrendszer alapmátrixa:   4 1 0 0 0 ... 0 1 4 1 0 0 . . . 0   0 1 4 1 0 . . . 0 . (3.12) Mn−1 =    ...   0 0 . . . 0 1 4 1 0 0 ... 0 0 1 4


55

Belátjuk, hogy det Mn−1 6= 0, tehát v0 és vn tetsz˝oleges megválasztása esetén az egyenletrendszer a (v1 , . . . , vn−1 ) vektorokra egyértelm˝uen megoldható, így a görbeillesztési feladatnak egyértelm˝uen van megoldása. (v0 és vn megválasztására a C1 osztályú megoldásnál elmondottakat lehet alkalmazni.) Határozzuk meg a (3.12) mátrix determinánsát. (Belátva ezzel, hogy a determináns ténylegesen nem zéró.) A det Mn = ∆n determinánst az utolsó sor szerint kifejtve: ∆n = 4∆n−1 − ∆n−2 . Tekintsük a valós sorozatok vektorterét. Ebben a vektortérben kétdimenziós altér az an = 4an−1 − an−2

rekurziónak eleget tév˝o sorozatok tere, melyet jelöljön L. Olyan λ számot keresünk, melyre (λ , λ 2 , . . . , λ n , . . .) 2 eleme L-nek. A rekurziót leíró feltétel √ √ λ -ra a λ − 4λ + 1 = 0 feltételt adja, ahonnan λ1 = 2 + 3 és λ2 = 2 − 3. Tehát a

Λ1 = (λ1 , λ12 , . . . , λ1n , . . .),

Λ2 = (λ2 , λ22 , . . . , λ2n , . . .) sorozatok L bázisát adják. Határozzuk meg a (∆1 , ∆2 , . . . , ∆n , . . .) sorozat (α, β ) koordinátáit a (Λ1 , Λ2 ) bázisra vonatkozóan: √ √ α(2 + 3) + β (2 − 3) = 4, √ √ α(2 + 3)2 + β (2 − 3)2 = 15, ahonnan α=

1 1√ 1 1√ + 3, β = − 3. 2 3 2 3

Tehát ∆n =

√ n √ 1 1√ 1√ 1 + (2 − 3)n . 3 (2 + 3) − 3− 2 3 3 2

∆n 6= 0, mert az els˝o tag egyt˝ol nagyobb, a második tag pedig egyt˝ol kisebb. 3.19. Megjegyzés. Zárt göbe esetén p0 = pn . Ha azt is el˝oírjuk, hogy v0 = vn , továbbá a teljes görbe legalább C2 osztályú legyen, akkor az el˝oz˝oekhez hasonló módon: vi−1 + 4vi + vi+1 = 3(pi+1 − pi−1 ),

(i = 1, . . . , n, vn+1 = v1 ),

koordinátánként n egyenlettel és n ismeretlennel. Az alapmátrix determinánsa nem zéró, azaz zárt görbe esetén a kontrollpontok a görbét egyértelm˝uen meghatározzák a görbe legalább kétszeri folytonos differenciálhatóságát megkövetelve.

3.6. BÉZIER-GÖRBÉK

56

Ö SSZEFOGLALÓ harmadfokú görbeív: az a, b, c, d algebrai együtthatókkal p(u) = u3 a + u2 b + uc + d, u ∈ [0, 1].

a görbe geometriai együtthatói: - p(0) (kezd˝opont), - p(1) (végpont), - p0 (0) (kezd˝osebesség), - p0 (1) (végsebesség). harmadfokú Hermite-görbe: a görbe paraméteres el˝oállítása a geometriai együtthatókkal: p(u) = F03 (u) · p(0) + F13 (u)p(1) + F23 (u)p0 (0) + F33 (u)p0 (1),

ahol Fi3 (u) (i = 0, 1, 2, 3) a harmadfokú Hermite-polinomok. az interpolációs feladat megoldása: a kontrollpontokban tetsz˝olegesen megadva a sebességvektorokat, két kontrollpont között harmadfokú Hermite-görbét alkalmazva, az interpolációs alapfeladat C1 osztályú megoldását kapjuk. 3.6. Bézier-görbék 3.6.1. A Bernstein-polinomok. Ebben a szakaszban egy egységbontást alkotó nemnegatív polinomrendszert adunk meg. 3.20. Definíció. Legyen n nemnegatív egész, i tetsz˝oleges egész. A n i n Bi (u) = u (1 − u)n−i i polinomot Bernstein-polinomnak nevezzük, ahol ( n! 0 ≤ i ≤ n, n = i!(n−i)! i 0 egyébként. A definícióból közvetlenül leolvasható, hogy a Bernstein-polinomok nemnegatívak a [0, 1] intervallumon, pozitívak a (0, 1) intervallumon. Teljesül továbbá az alábbi szimmetria tulajdonság: Bni (u) = Bnn−i (1 − u). 3.21. Tétel. A Bernstein-polinomok kielégítik az alábbi rekurziót: (B1)

B00 (u) = 1,

(u) + uBn−1 Bni (u) = (1 − u)Bn−1 i i−1 (u),

továbbá Bni (u) = 0,

i∈ / {0, . . . , n}.


57

B IZONYÍTÁS . Az els˝o és az utolsó formula nyilvánvaló. A második állítás bizonyításához felhasználjuk a binomiális együtthatókra fennálló rekurzív formulát: n−1 n−1 n = + . i i−1 i Tehát n i u (1 − u)n−i i n−1 i n−1 i n−i = u (1 − u) + u (1 − u)n−i i i−1 n−1 i n − 1 i−1 n−1−i = (1 − u) u (1 − u) +u u (1 − u)n−i . i−1 i | {z } | {z }

Bni (u) =

Bn−1 (u) i

Bn−1 i−1 (u)

3.22. Tétel. A Bernstein-polinomok egységbontást alkotnak, azaz n

∑ Bni(u) = 1.

(B2)

i=1

B IZONYÍTÁS . Alkalmazzuk a binomiális tételt: n n n i n n−i 1 = [u + (1 − u)] = ∑ u (1 − u) = ∑ Bni (u). i=0 i i=0

3.23. Tétel. A Bernstein-polinomok deriváltja: (B3)

d n n−1 Bi (u) = n Bn−1 (u) . i−1 (u) − Bi du 1

0

1

3.11. ábra. Ötödfokú Bernstein-polinomok grafikonja a [0, 1] intervallumon


58

B IZONYÍTÁS . A szorzatfüggvény deriválási szabálya szerint: d n d n i Bi (u) = u (1 − u)n−i = du du i in! (n − i)n! i = ui−1 (1 − u)n−i − u (1 − u)n−i−1 = i!(n − i)! i!(n − i)!) (n − 1)! (n − 1)! ui−1 (1 − u)n−i − n ui (1 − u)n−i−1 = =n (i − 1)!(n − i)! i!(n − i − 1)! n−1 = n Bn−1 (u) − B (u) . i i−1

3.24. Következmény. i 6= 0, n esetén a Bni polinomnak u = ni -nél lokális maximuma van. 1

0

1

3.12. ábra. A Bernstein-polinomok „csúcsosodó” tulajdonsága a lokális maximum körül: Bnn−1 , (n = 1 . . . 16) grafikonja A kés˝obbiek során majd felhasználjuk az alábbi összefüggést. 3.25. Tétel. Bnk (u · t) = ∑ni=k Bni (u) · Bik (t). Ö SSZEFOGLALÓ Bernstein polinomok: tulajdonságai n i n - Bi (u) = i u (1 − u)n−i ≥ 0, ha u ∈ [0, 1], - egységbontás: ∑ni=0 Bni (u) = 1, - Bn0 (0) = 1, Bnn (1) = 1; 0, 1-ben minden más polinom értéke 0, - deriváltja d n Bi (u) = n Bn−1 (u) − Bn−1 (u) . i i−1 du


59

3.6.2. Bézier-görbék. A Bernstein-polinomokkal a „keverési elv” szerint (ld. 3.2. szakasz) lehet modellgörbét konstruálni. 3.26. Definíció. A (p0 , p1 , . . . , pn ) kontrollpontokhoz tartozó Bézier-görbe alatt a n N

p : [0, 1] → R ,

(3.13)

p(u) = ∑ Bni (u)pi i=0

görbét értjük. A [p0 , p1 ] ∪ [p1 , p2 ] ∪ . . . ∪ [pn−1 , pn ]

töröttvonalat a görbe kontrollpoligonjának nevezzük, míg n a görbe fokszáma. p1

p3

p0

p2

3.13. ábra. Harmadfokú Bézier-görbe és a kontrollpoligonja

3.27. Tétel. Minden Bézier-görbe rendelkezik az alábbi tulajdonságokkal: (1) Affin invariancia: ha F : RN → RN affin leképezés, akkor n

F(p(u)) = ∑ Bni (u)F(pi ); i=0

(2) Konvex burokban maradás: minden u paraméterértékre teljesül, hogy p(u) ∈ conv{p1 , . . . , pn } (3) Végpont interpoláció: p(0) = p0 , p(1) = pn . (4) Szimmetria: n

∑

i=0

n

Bni (u)pi

= ∑ Bni (1 − u)pn−i . i=0

Az els˝o és második tulajdonság minden nemnegatív, egységbontást alkotó súlyfüggvény rendszerre teljesül. A harmadik és negyedik tulajdonság pedig a Bernstein-polinomok definíciójából rögtön leolvasható. 3.28. Példa. n = 2. Belátjuk, hogy három nem kollineáris kontrollpont által meghatározott Bézier-görbe egy parabolaív. Vegyük tehát a másodfokú Bézier-görbét: p(u) = (1 − u)2 p0 + 2u(1 − u)p1 + u2 p2 .


60

Helyezzünk el egy Descartes koordináta-rendszert a következ˝oképpen: legyen p1 = 0, az y tengely irányvektora pedig p0 + p2 . p0 koordinátái legyenek (−a, b), p2 = (a, c). Ekkor, p(u) koordináta-függvényeit x(u)-val és y(u)-val jelölve: x(u) = −a(1 − u)2 + au2 = a(2u − 1)

y(u) = b(1 − u)2 + cu2 = u2 (c + b) − 2ub + b.

Az els˝o egyenletb˝ol u = x+a 2a , amit a második egyenletbe beírva: x+a 2 x+a y= b + b, (c + b) − 2a a ami egy parabola egyenlete. 3.29. Példa. A p0 , p1 , p2 , p3 kontrollpontokhoz tartozó harmadfokú Béziergörbe geometriai együtthatói: p(0) = p0 , p(1) = p1 , p0 (0) = 3(p1 − p0 ), p0 (1) = 3(p3 − p2 ). A harmadfokú Bézier-görbék és a korábbiakban tárgyalt szintén harmadfokú Hermite-görbék között nincs különbség, az el˝oállításhoz használt polinombázis más. Ö SSZEFOGLALÓ Bézier-görbe: n

p : [0, 1] → RN ,

p(u) = ∑ Bni (u)pi . i=0

3.6.3. Bézier-görbe deriváltja. Határozzuk meg a n

p(u) = ∑ Bni (u)pi i=0

Bézier-görbe deriváltját (sebesség vektormez˝ojét)! Felhasználva a Bernstein-polinomok deriváltjára kapott (B3) összefüggést: n n−1 p0 (u) = n ∑ Bn−1 (u) pi . i−1 (u) − Bi i=0

A zérus tagokat elhagyva: n

n−1

i=1

i=0

n−1 p0 (u) = n ∑ Bn−1 (u)pi . i−1 (u)pi − n ∑ Bi

Az els˝o tagban az indexet transzformálva: n−1

n−1

i=0

i=0

p0 (u) = n ∑ Bn−1 (u)pi+1 − n ∑ Bn−1 (u)pi , i i


61

tehát n−1

p0 (u) = n ∑ Bn−1 (u) (pi+1 − pi ) . i i=0

Bevezetve a ∆pi = pi+1 − pi jelölést: n−1

(3.14)

p0 (u) = n ∑ Bn−1 (u)∆pi = i i=0

n−1

(u)(n∆pi ). ∑ Bn−1 i

i=0

A végeredményr˝ol leolvasható, hogy a derivált maga is Bézier-görbe: 3.30. Tétel. A p0 , p1 , . . . , pn kontrollpontokhoz tartozó Bézier-görbe deriváltja nem más, mint az n∆p0 , n∆p1 , . . . , n∆pn−1 kontrollpontokhoz tartozó Bézier-görbe. Alkalmazzuk a (3.14) összefüggést speciálisan a végpontokra! A Bernstein polinomokat a 0, 1 paramétereknél kiértékelve: (3.15)

p0 (0) = n(p1 − p0 ), p0 (1) = n(pn − pn−1 ).

A fenti értékek a kezd˝oponttal és a végponttal együtt a görbe geometriai együtthatóit adják. 3.31. Következmény. A p0 , p1 , . . . , pn kontrollpontokhoz tartozó Béziergörbe geometriai együtthatói p0 , pn , n(p1 − p0 ), n(pn − pn−1 ). A Bézier-görbék magasabb rend˝u deriváltjait a 3.30 tétel alapján könny˝u meghatározni, hiszen magát a tételt kell szukcesszíven alkalmazni. n−2

p00 (u) = (n − 1) ∑ Bn−2 (u)[n∆pi+1 − n∆pi ] = i i=0 n−2

= n(n − 1) ∑ Bn−2 (u)[∆pi+1 − ∆pi ] = i | {z } i=0

(3.16)

jel.: ∆2 pi

n−2

= n(n − 1) ∑ Bn−2 (u)∆2 pi i i=0

A végpontokban: (3.17)

p00 (0) = n(n − 1)∆2 p0 = n(n − 1)(∆p1 − ∆p0 ) = = n(n − 1)(p2 − p1 − p1 + p0 ) = = n(n − 1)(p2 − 2p1 + p0 ),

illetve (3.18)

p00 (1) = n(n − 1)∆2 pn−2 = n(n − 1)(∆pn−1 − ∆pn−2 ) = = n(n − 1)(pn − pn−1 − pn−1 + pn−2 ) =

= n(n − 1)(pn − 2pn−1 + pn−2 ).

Tovább folytatva kiszámíthatjuk a magasabb rend˝u deriváltakat.


62

3.32. Definíció. Legyenek p0 , . . . , pn adott kontrollpontok, ∆0 pi = pi , ∆r pi = ∆r−1 pi+1 − ∆r−1 pi

(i = 0, . . . , n − r; r = 1, . . . , n).

A ∆r pi (r = 0, . . . , n, i = 0, . . . , n − r) vektorokat az adott kontrollpont sorozat r-differenciáinak nevezzük. 3.33. Tétel. Bézier-görbe r-edik deriváltja olyan Bézier-görbe, melynek kontrollpontjai az eredeti görbe kontrollpontjaival kifejezve: n! ∆r pi , (i = 0, . . . , n − r). (n − r)! Azaz: n! n−r n−r p(r) (u) = Bi (u) · ∆r pi (u ∈ [0, 1]). ∑ (n − r)! i=0 Ö SSZEFOGLALÓ Bézier-görbe deriváltja: - Bézier-görbe deriváltja Bézier-görbe, - p0 (0) = n(p1 − p0 ), - p0 (1) = n(pn − pn−1 ), - p00 (0) = n(n − 1)(p2 − 2p1 + p0 ), - p00 (1) = n(n − 1)(pn − 2pn−1 + pn−2 ). 3.6.4. Pont a Bézier-görbén: a de Casteljau-algoritmus. Ebben a szakaszban a Bézier-görbéknek egy geometriailag motivált, intuitív származtatását adjuk meg, amely Paul de Casteljau nevéhez f˝uz˝odik (1959). A Bézier-görbék elméletét ezen geometriai származtatás alapján is le lehet írni. Az algoritmus nem más, mint egy rekurzió. Az els˝o generációban a kontrollpontok vannak. Az új generációt a régib˝ol úgy kapjuk, hogy a régi generáció pontjai által meghatározott töröttvonal szakaszait u : (1 − u) arányban felosztjuk, ld. 3.14. ábra. A de Casteljau-algoritmus alapján a Bézier-görbe pontjai kiszámíthatók anélkül, hogy a Bernstein-polinomokba behelyettesítenénk. 3.34. Tétel. Legyenek adva a p0 , . . . , pn kontrollpontok, az általuk meghatározott Bézier-görbe p(u), u ∈ [0, 1] rögzített paraméterérték. Legyen továbbá p00 = p0 , . . . , p0n = pn és (3.19) Ekkor

j

j−1

pi = (1 − u)pi

j−1

+ upi+1 , j

pi =

(3.20)

j

∑ Bkj (u)pi+k , k=0

speciálisan

pn0

= p(u).

i = 0, . . . , n − j; j = 1, . . . , n.


63

p3 p12

p2

p21 p30

p11

p20 p0

p1

p10

3.14. ábra. A de Casteljau-algoritmus

B IZONYÍTÁS . A (3.20) relációt j szerinti teljes indukcióval látjuk be. j = 0-ra p0i = pi definíció szerint igaz. Tegyük fel, hogy az állítás a j-edik generációs pontokra igaz. Belátjuk a ( j + 1)-edik generációs pontokra. Alkalmazzuk a ( j + 1)-edik generációs pontok definícióját, majd az indukciós feltevést: j+1

pi

j

j

= (1 − u)pi + upi+1 = j

j

= (1 − u) ∑ Bsj (u)pi+s + u ∑ Bsj (u)pi+s+1 = s=0

s=0

a második szummációban indextranszformációval folytatva j

j+1

j

= (1 − u) ∑ Bsj (u)pi+s + u ∑ Bs−1 (u)pi+s = s=0

s=1

különválasztva az els˝o összeg els˝o és a második összeg utolsó tagját j

j

= (1 − u)B0 (u)pi + (1 − u) ∑ Bsj (u)pi+s + s=1

j

j

j

+ u ∑ Bs−1 (u)pi+s + uB j (u)pi+ j+1 . s=1

Mivel j

j+1

(1 − u)B0 (u) = (1 − u)u0 (1 − u) j = u0 (1 − u) j+1 = B0 (u), hasonlóan j

j+1

uB j (u) = uu j (1 − u)0 = u j+1 (1 − u)0 = B j+1 (u),


64

így az átalakítást tovább folytatva j h i j+1 j+1 j j+1 j pi = B0 (u)pi + ∑ (1 − u)Bs (u) + uBs−1 (u) pi+s + B j+1 (u)pi+ j+1 = s=1

a Bernstein-polinomok rekurzív tulajdonságát alkalmazva j+1 = B0 (u)pi +

j

∑

j+1 Bsj+1 (u)pi+s + B j+1 (u)pi+ j+1

s=1

j+1

=

∑ Bsj+1(u)pi+s.

s=0

j pi

A tételben szerepl˝o pontokat a u paraméterértékhez tartozó de Casteljau pontoknak nevezzük. 3.35. Példa. Keressük meg a (5, 2), (4, 1), (3, 2), (−1, 1) kontrollpontokhoz tartozó Bézier-görbe u = 0, 5 paraméterértékhez tartozó pontját a de Casteljau algoritmus alapján! A megoldáshoz érdemes az alábbi egyszer˝u sémát használni. Az oszlopokban az algoritmus egymást követ˝o lépéseiben szerepl˝o de Casteljaupontok találhatók. Az utolsó oszlop egyetlen eleme a keresett pont. (5, 2) ( 92 , 32 ) ( 16 , 6) 4 4

(4, 1) ( 72 , 32 )

, 12 ) ( 25 8 8 ( 94 , 64 )

(3, 2) ( 22 , 32 ) (−1, 1)

3.36. A LGORITMUS . A P OINT O N T HE C URVE(u) algoritmus a de Casteljau-algoritmus alapján kiszámítja a görbepontot. A számítás során a régi generáció pontjait nem o˝ rizzük meg (kivéve a nulladik generációt, vagyis a kontrollpontokat), hanem lecseréljük az új generációval. 3.37. A LGORITMUS . A számítás rekurzióval is programozható (ld. a DE C ASTELJAU (i, j) pszeudokódot). Ez a rekurzió egyszer˝ u és elegáns, de a görbepont kiszámításához a DE C ASTELJAU függvény meghívásainak száma egy n-ed fokú görbénél 2n − 1, azaz a kontrollpontok számának növekedésével exponenciálisan növekszik, tehát magasabb fokszámú görbék esetén nem célszer˝u alkalmazni. (A 3.35. példa megoldásában a szakasz osztást hatszor végeztük el, a rekurzióhoz viszont 15-ször kell elvégezni.


65

3.36. P OINT O N T HE C URVE(u) Input: u ∈ [0, 1] Output: p(u) for i = 0 to n do qi ← pi % Az eredeti kontrollpontokat meg˝orizzük. for j = 1 to n do for i = 0 to n − j do qi ← (1 − u) · qi + u · qi+1 return q0 Ennek oka, hogy ugyanazt a de Casteljau-pontot a rekurzív módszer esetén többször is ki kell számolni.) 3.37.

DE C ASTELJAU (i,

j)

Input: 0 ≤ j ≤ n, 0 ≤ i ≤ n − j j Output: pi if j = 0 then return pi else return (1 − u) · DE C ASTELJAU(i, j − 1) + u · DE C ASTELJAU(i + 1, j − 1)

Egy pont a Bézier-görbén a görbét két részgörbére osztja. A következ˝o tételben belátjuk, hogy ezen görbék maguk is Bézier-görbék, ráadásul kontrollpontjaik a de Casteljau-algoritmussal könnyen származtathatók. 3.38. Tétel (Bézier-görbe felosztása). Legyen p : [0, 1] 7→ RN a p0 , . . . , pn kontrollpontokhoz tartozó Bézier-görbe, t ∈ [0, 1] rögzített. Legyen p− : [0, 1] → RN , p− (u) = p(ut),

p+ : [0, 1] → RN , p+ (u) = p(t + u(1 − t)). Ekkor p− (u) és p+ (u) szintén n-edfokú Bézier-görbék, továbbá p− kontrollpontjai az eredeti görbe t paraméterértékhez tartozó de Casteljaupontjaival kifejezve: p0 = p00 , p10 , . . . , p(t) = pn0 ; míg p+ kontrollpontjai: 1 0 p(t) = pn0 , pn−1 1 , . . . , pn−1 , pn = pn .


p1

66

p2

p0

p3

3.15. ábra. Harmadfokú Bézier-görbe rajzolása a de Casteljau-algoritmus alapján. A felez˝o algoritmust ötször hajtottuk végre.

B IZONYÍTÁS . A bizonyítást a p− görbére végezzük el. A (3.20) relációt és a 3.25. tételt használva: n

n

∑ Bni(u)pi0 =

i=0

=

i=0 i

k=0

n

∑ pk ∑ Bni(u) · Bik (t) =

k=0 i

=

i

n

i

∑ Bni(u) · ∑ Bik (t)pk = ∑ i=0

∑ Bnk(u · t)pk = p(u · t).

∑ Bni(u) · Bik (t)pk =

i=0 k=0 i n

∑ pk ∑ Bni(u) · Bik (t) =

k=0

i=k

k=0

A de Casteljau-algoritmus alapján számítógéppel nagyon hatékonyan lehet Bézier görbét rajzolni. t = 1/2 értékre az algoritmus során csak 2-vel kell osztani, ami a kettes számrendszerben nagyon egyszer˝u. Kiszámítjuk és kirajzoljuk az t = 1/2-hez tartozó görbepontot. Nevezzük ezt a görbe felez˝opontjának. Ez a pont a görbét az el˝oz˝o tétel szerint két Bézier-görbére osztja, amelyek kontrollpontjait ismerjük, az algoritmus végrehajtása során kiszámítottuk. Meghatározzuk és kirajzoljuk mindkét görbe felez˝opontját és az eljárást tovább folytatjuk a keletkezett négy Bézier görbére, és így tovább, mindaddig, amíg az egymást követ˝o pontok a praktikus igényeknek megfelel˝o közelségben lesznek és a poligonális approximáció elvégezhet˝o. (Ld. 3.15. ábra.) 3.39. A LGORITMUS . A következ˝o algoritmus egy rekurzív eljárás a Béziergörbe rajzolására, amely a felezést használja. Az algoritmus adaptív mintavételezésen alapul, azaz ahol a Bézier-görbe nagyobb görbület˝u, ott több pontot rajzolunk meg. A lényeg, hogy ha a felezést „elég sokszor” elvégeztük, azaz a kontrollpoligon „elég egyenes”, akkor a Bézier-görbe helyett a kezd˝o- és végpontot összeköt˝o szakaszt rajzoljuk meg. Fontos kérdés, hogy milyen módon állapítjuk meg azt, hogy a kontrollpoligon „elég egyenes”. Egyszer˝u módszer, ha a kontrollpoligon hosszát összehasonlítjuk a kezd˝o és végpont távolságával. Ha a különbség egy hibahatár alatt marad, akkor a kontrollpoligonról kijelenthetjük, hogy „elég egyenes”, és a Bézier-görbét approximálhatjuk a kezd˝o- és végpontját összeköt˝o szakasszal.


67

3.39. B EZIER(p0 , p1 , . . . , pn ) Input: p0 , p1 , . . . , pn Output: Bézier-görbe poligonális approximációja if A kontrollpoligon „elég egyenes” then return p0 pn szakasz else 0 return B EZIER(p00 , p10 , . . . , pn0 ), B EZIER(pn0 , pn−1 1 , . . . , pn ) % A de Casteljau pontokat u = 1/2 paraméterértékhez számoljuk.

3.16. ábra. Bézier-görbe rajzolása szelektív mintavételezéssel (n = 9). Az ábrán a poligonális approximációhoz használt pontokat is berajzoltuk.

Ö SSZEFOGLALÓ de Casteljau-algoritmus: Kontrollpontok: p00 = p0 , . . . , p0n = pn , az u paraméterhez tartozó de Casteljau-pontok: j

j−1

pi = (1 − u)pi

j−1

+ upi+1 ,

Ekkor p(u) = pn0 .

i = 0, . . . , n − j; j = 1, . . . , n.


68

3.6.5. Bézier-görbe fokszám emelése. Egy bonyolultabb szabad formájú görbe Bézier-típusú modellezéséhez két f˝o stratégia vezethet. Az egyik, hogy több kontrollpont veszünk föl, és ezáltal alakítjuk a görbét, a másik, hogy több, alacsony fokszámú görbét illesztünk egymáshoz megfelel˝o feltételekkel. (És persze ezeket lehet kombinálni.) A több kontrollpont fölvételének az ára a magasabb fokszám, egyik el˝onye viszont az egész görbe akárhányszori differenciálhatósága. (Ennek következménye a görbület folytonos változása.) A magasabb fokszámot is megenged˝o modellezés egyik fontos technikája, hogy a valahogyan már kialakított n-edfokú „félkész” görbét el˝oállítjuk n + 2 kontrollponttal is (azaz a fokszámot eggyel megnöveljük) és a több kontrollponttal a görbét finomabban alakítjuk tovább. Legyen tehát p a p0 , p1 , . . . , pn kontrollpontokhoz tartozó Bézier-görbe. Keressük a q0 , q1 , . . . , qn+1 kontrollpontokat, hogy az ezekhez tartozó Bézier-görbe szintén p. Nyilván p0 = q0 és pn = qn+1 . Tehát n

∑ Bni(u)pi =

i=0

n+1

(u)qi , ∑ Bn+1 i

i=0

azaz n

n+1 n i n+1 i n−i ∑ i u (1 − u) pi = ∑ i u (1 − u)n+1−iqi. i=0 i=0 Szorozzuk meg a bal oldalt u + (1 − u)-val: n n+1 n n+1 i i+1 n−i i n+1−i pi = ∑ u (1−u)n+1−i qi . ∑ i u (1 − u) + u (1 − u) i i=0 i=0 ui (1 − u)n+1−i együtthatóját összehasonlítva mindkét oldalon: n n n+1 pi−1 + pi = qi , i = 1, . . . , n. i−1 i i A binomiális együtthatók definícióját beírva és a lehetséges egyszer˝usítéseket elvégezve adódik a következ˝o állítás. 3.40. Tétel. Legyen p : [0, 1] 7→ RN a p0 , . . . , pn kontrollpontokhoz tartozó Bézier-görbe, továbbá q0 = p0 , qn+1 = pn és i i pi−1 + 1 − pi (1 ≤ i ≤ n). qi = n+1 n+1 Ekkor a q0 , . . . , qn+1 kontrollpontokhoz tartozó Bézier-görbe szintén p. 3.6.6. Kvadratikus, C1 osztályú Bézier-szplájn. A p0 , p1 , p2 kontrollpontokhoz tartozó kvadratikus Bézier-görbe legyen p0 (t), a p2 , p3 , p4 kontrollpontokhoz tartozó kvadratikus Bézier-görbe pedig p2 (t), t ∈ [0, 1] a


69

p1

p0

p2

p3 3.17. ábra. Bézier-görbe fokszám emelése: ugyanazon görbét el˝oállítottuk harmad-, negyed-, ötöd- és hatodfokú Bézier-görbeként is görbék lokális paramétere. A csatlakozási pont p2 . A két görbe egyesítéséb˝ol adódó szplájnt jelölje p(u), melynek csomópont vektora (u0 , u1 , u2 ):  p0 u−u0 , u ∈ [u0 , u1 ], u1 −u0 p(u) = p2 u−u1 , u ∈ [u1 , u2 ]. u2 −u1 Emlékeztetünk arra (ld. (3.3)), hogy p0 (t) C1 osztályban csatlakozik p2 (t)-höz, ha ∆u1 p00 (1) = ∆u0 p02 (0) teljesül. A Bézier-görbe deriváltjára vonatkozó összefüggés szerint ennek szükséges és elégséges feltétele, hogy (3.21)

∆u1 (p2 − p1 ) = ∆u0 (p3 − p2 )

teljesüljön. Átrendezve: ∆u1 ∆u0 p1 + p3 ∆u0 + ∆u1 ∆u0 + ∆u1 adódik. Geometriailag a kapott képletb˝ol a p1 , p2 , p3 kontrollpontok kollinearitása is következik, mert p2 a p1 és p3 kontrollpontok konvex lineáris kombinációja. Speciálisan ekvidisztáns csomópontok (azaz ∆u1 = ∆u0 ) mellett 1 1 (3.23) p2 = p1 + p3 , 2 2 azaz p2 a [p1 , p3 ] szakasz felez˝opontja. A (3.22) feltételt átfogalmazhatjuk 0 úgy, hogy p2 a [p1 , p3 ] szakaszt ∆u ∆u1 arányban osztja: (3.22)

p2 =

∆u0 . ∆u1 Megfordítva, ha két csatlakozó kvadratikus Bézier-görbére p1 , p2 , p3 kollineárisak, azaz p2 − p1 , p3 − p2 egyirányú vektorok, akkor a csomópont vektort meg lehet úgy határozni, hogy a szplájn C1 osztályú legyen, (3.24)

(p1 p3 p2 ) =


70

ugyanis u0 < u1 szabad választása mellett az (u2 − u1 )kp2 − p1 k = (u1 − u0 )kp3 − p2 k egyenletb˝ol u2 egyértelm˝uen meghatározható úgy, hogy (3.21) teljesüljön: u2 = (u1 − u0 )

kp3 − p2 k + u1 . kp2 − p1 k

Gondolatmenetünket alkalmazhatjuk több csatlakozó kvadratikus Bézier-görbére: a C1 osztályú kvadratikus Bézier-szplájn differenciálhatóan csatlakozó másodfokú Bézier-görbékb˝ol, azaz parametrizált parabolaívekb˝ol áll. Ennek megadásához el˝oször kijelöljük a kontrollpontokat, a csatlakozási pontok nélkül – az általuk meghatározott poligont nevezik a szplájn de Boor-poligonjának: p0 , p1 , pb2 , . . . , p2i−1 , pc 2i , p2i+1 , . . . , p2L−1 , p2L (a kalap a kontrollpont hiányára utal), és megadjuk a csomópontvektort: u0 < u1 < · · · < uL . A hiányzó kontrollpontokat (3.22) alapján kiszámítjuk: p2i =

∆ui ∆ui−1 p2i−1 + p2i+1 (i = 1, . . . , L − 1). ∆ui−1 + ∆ui ∆ui−1 + ∆ui

A gyakorlati tervezésben a de Boor-poligon megadása általában könny˝u (jellemz˝o módon egérrel jelöljük ki a kontrollpontokat, majd vonszolással módosíthatjuk), de kevésbé intuitív a csomópont vektor meghatározása. Választhatunk ekvidisztáns csomópontokat, pl. ui = i (i = 0, . . . , L), de a gyakorlati tapasztalat az, hogy kedvez˝o, ha a csomópont vektor valamilyen módon tükrözi a de Boor-poligon geometriáját. Ilyen pl. a Lagrangeinterpolációnál már megismert arányos paraméterezés. Az egyszer˝ubb megadás végett jelöljük át a kontrollpontokat: q−1 = p0 , qk = p2k+1 , k = 0, . . . , L − 1, qL = p2L , a csomópontokat pedig a következ˝oképpen adjuk meg: u0 = 0, u1 = kq1 − q−1 k (Vigyázat: q0 -t nem használjuk!) uk = uk−1 + kqk − qk−1 k, k = 2, . . . , L. 3.41. A LGORITMUS . A következ˝o algoritmus a do Boor-poligont a teljes Bézier-poligonná konvertálja a csomópontok ismeretében. Egy gyakorlati példát adunk, amikor jól alkalmazható a szabadformájú görbék modellezésben a C1 osztályú kvadratikus Bézier-szplájn módszer. Legyenek adva interpoláló pontok a görbén: (p0 , p2 , . . . , p2L ) és a görbe


3.41.

71

DE B OORT O B EZIER (q−1 , q0 , . . . , qL )

Input: [q−1 , q0 , . . . , qL ] Output: [p0 , p1 , . . . , p2L ]

P ← [q−1 , q0 ] for i = 1 to L − 1 do ∆ui−1 ∆ui P ← augment(P, [ ∆ui−1 +∆ui qi−1 + ∆ui−1 +∆ui qi , qi ]) P ← augment(P, [qL ]) return P

érint˝o egyenesei ezekben a pontokban. Az érint˝ok metszéspontjainak meghatározásával megkapjuk a hiányzó kontrollpontokat, azaz a teljes Bézierpoligont. Ezek után a p0 (t), p2 (t), . . . , p2L−2 (t) kvadratikus Bézier-görbék lokális paraméterrel rajzolhatók: így készült a 3.18. ábra. Ha a szplájn mentén egy megmunkáló eszközt vezérlünk vagy egy robotot mozgatunk, akkor szempont lehet a sebesség folytonos változása. Ehhez szükség van a szplájn C1 osztályú globális paraméterezésére: (3.21) alapján a kollineáris kontrollpontok osztóviszonyából a csomópont vektor meghatározható. (A szplájnnak van olyan paraméterezése, amely C1 osztályú görbét ad, de ha csak rajzolni akarjuk a szplájnt, akkor erre nem feltétlenül van szükség.) A kvadratikus Bézier-szplájn tulajdonságai:

-

affin invariancia konvex burokban maradás végpont interpoláció lokális változtathatóság.

A konvex burokban maradás szigorúbb formában is teljesül, mint a Béziergörbéknél: a Bézier-szplájn a (p2i−1 , p2i , p2i+1 ) háromszöglemezek uniójában helyezkedik el. Megemlítjük még a kvadratikus Bézier-szplájn még egy tulajdonságát: a kvadratikus Bézier-szplájn parabolaívekb˝ol áll, amelyek síkgörbék. Ugyanakkor a kontrollpoligon lehet térbeli is, így a kvadratikus Bézier-szplájn szakaszonként síkgörbékb˝ol álló C1 osztályú térgörbe. Ez a tulajdonság rámutat a kvadratikus Bézier-szplájnok hátrányára: a simúlósík nem folytonosan változik, a csatlakozási pontoknál „ugrások” lehetnek a simulósík állásában.


72

3.18. ábra. Az ábrán látható kvadratikus Bézier-szplájn úgy készült, hogy felvettem a modellezend˝o szabadformájú görbén néhány kontrollpontot (telt piros) és ezekben (hozzávet˝oleges) érint˝ot húztam a görbéhez. Az érint˝ok metszéspontjai adták a szplájn hiányzó kontrollpontjait.

Ö SSZEFOGLALÓ kvadratikus, C1 osztályú Bézier-szplájn: A kvadratikus, C1 osztályú Bézier-szplájnt a p0 , p1 , pb2 , . . . , p2i−1 , pc 2i , p2i+1 , . . . , p2L−1 , p2L de Boor poligonnal és az u0 < u1 < · · · < uL csomópont vektorral adjuk meg. A hiányzó kontrollpontok a [p2i−1 , p2i+1 ] szakasz ∆ui−1 : ∆ui arányú felosztásával számíthatók: ∆ui ∆ui−1 p2i = p2i−1 + p2i+1 (i = 1, . . . , L − 1). ∆ui−1 + ∆ui ∆ui−1 + ∆ui


73

3.6.7. Kubikus C2 osztályú Bézier-szplájn. A p0 , p1 , p2 , p3 kontrollpontokhoz tartozó kubikus Bézier-görbe legyen p0 (t), a p3 , p4 , p5 , p6 kontrollpontokhoz tartozó kubikus Bézier-görbe pedig p1 (t), t ∈ [0, 1] a görbék lokális paramétere. A csatlakozási pont p3 . A két görbe egyesítéséb˝ol adódó szplájnt jelölje p(u), melynek csomópont vektora (u0 , u1 , u2 ):  p0 u−u0 , u ∈ [u0 , u1 ], u1 −u0 p(u) = p1 u−u1 , u ∈ [u1 , u2 ]. u2 −u1 p0 (t) C2 osztályban csatlakozik p1 (t)-hez, ha ∆u1 p00 (1) = ∆u0 p01 (0) és (∆u1 )2 p000 (1) = (∆u0 )2 p001 (0) teljesül (ld. (3.3) és (3.4)). Az els˝o feltételt már vizsgáltuk, ez ekvivalens a ∆u1 (p3 − p2 ) = ∆u0 (p4 − p3 )

(3.25) relációval, azaz

p3 =

(3.26)

∆u1 ∆u0 p2 + p4 . ∆u0 + ∆u1 ∆u0 + ∆u1

A második feltételre rátérve, alkalmazzuk a (3.17) és (3.18) összefüggéseket: (3.27)

(∆u1 )2 (p3 − 2p2 + p1 ) = (∆u0 )2 (p5 − 2p4 + p3 ).

Ha a p1 , p2 , p3 kontrollpontokhoz tartozó kvadratikus Bézier-görbe és a p3 , p4 , p5 kontrollpontokhoz tartozó kvadratikus Bézier-görbe C2 osztályú csatlakozását vizsgálnánk, akkor ugyanezeket a feltételeket kapnánk, így a két Bézier-görbe egyetlen Bézier-görbét ad (melyet p3 a két eredeti Béziergörbére oszt fel, ld. 3.38. Tétel), azaz létezik olyan q pont, hogy ∆u1 ∆u0 p1 + q = p2 , ∆u0 + ∆u1 ∆u0 + ∆u1 ∆u1 ∆u0 q+ p5 = p4 . ∆u0 + ∆u1 ∆u0 + ∆u1

(3.28)

A (3.26) és (3.28) képlet alapján a szplájn megadásában a p2 , p3 , p4 kontrollpontokat kiváltja a q segédpont és a csomópont vektor: (3.28) alapján kiszámítjuk p2 -t és p4 -et, majd (3.26) alapján p3 -t. (Ld. 3.19. ábra!) Most csatlakozzon több kubikus Bézier-görbe is C2 osztályban: p , p , p , p , . . . , p3(k−1) , p3k−2 , p3k−1 , p3k , . . . , p3(L−1) , p3L−2 , p3L−1 , p3L . | 0 1{z 2 }3 | {z } | {z } p0 (t)

pk−1 (t)

pL−1 (t)

A görbék egyben C1 osztályban is csatlakoznak, ezért a p3k csatlakozási pontnál (1 ≤ k ≤ L − 1) (3.29)

p3k =

∆uk−1 ∆uk p3k−1 + p3k+1 . ∆uk−1 + ∆uk ∆uk−1 + ∆uk


q u1

∆u

: ∆p2 0

74

∆u 0 p4

p3 ∆u0 : ∆u1

:∆ u1 p5

p1

p0

p6 3.19. ábra. C2 osztályú kubikus Bézier-szplájn

Továbbá létezik olyan qk segédpont (ld. (3.28)), hogy ∆uk−1 ∆uk p3k−2 + qk = p3k−1 , ∆uk−1 + ∆uk ∆uk−1 + ∆uk (3.30) ∆uk ∆uk−1 qk + p3k+2 = p3k+1 . ∆uk−1 + ∆uk ∆uk−1 + ∆uk Az els˝o egyenletben az indexet transzformálva: ∆uk+1 ∆uk p3k+1 + qk+1 = p3k+2 , ∆uk + ∆uk+1 ∆uk + ∆uk+1 (3.31) ∆uk−1 ∆uk qk + p3k+2 = p3k+1 . ∆uk−1 + ∆uk ∆uk−1 + ∆uk (3.31) (koordinátánként) egy inhomogén lineáris egyenletrendszer, amelyb˝ol p3k+1 és p3k+2 kifejezhet˝o. Az eredmény: ∆uk−1 ∆uk + ∆uk+1 p3k+1 = qk + qk+1 , ∆uk−1 + ∆uk + ∆uk+1 ∆uk−1 + ∆uk + ∆uk+1 (3.32) ∆uk+1 ∆uk−1 + ∆uk p3k+2 = qk + qk+1 . ∆uk−1 + ∆uk + ∆uk+1 ∆uk−1 + ∆uk + ∆uk+1 A p0 , p1 = q0 , q1 , q2 , . . . , qL−1 , p3L−1 = qL , p3L kontrollpontok és az (u0 , u1 , . . . , uL ) csomópont vektor tehát megadják a szplájnt. A (3.29) és a (3.32) egyenleteket még ki kell egészíteni (3.30) alapján (k = 1-et az els˝o, és k = L − 1-t a második egyenletbe beírva) ∆u1 ∆u0 p2 = q0 + q1 , ∆u0 + ∆u1 ∆u0 + ∆u1 (3.33) ∆uL−1 ∆uL−2 p3L−2 = qL−1 + qL . ∆uL−2 + ∆uL−1 ∆uL−2 + ∆uL−1


75

A fentiekben megadott konstrukció az ún. Böhm-szerkesztés. 3.42. A LGORITMUS . A következ˝o algoritmus a do Boor-poligont a teljes Bézier-poligonná konvertálja a csomópontok ismeretében, azaz elvégzi a Böhm-szerkesztést. A számolt kontrollpontok kiszámítási módja az algoritmusban nem szerepel, azokat az indexeknek megfelel˝oen kell az el˝oz˝o képletekb˝ol alkalmazni.

3.42.

DE B OORT O B EZIER (q−1 , q0 , . . . , qL+1 )

Input: [q−1 , q0 , . . . , qL+1 ] – a de Boor poligon Output: [p0 , p1 , . . . , p3L ] – a Bézier poligon P ← [q0 ] Q ← [p2 ] R←[] for k = 1 to L − 2 do P ← augment(P, [p3k+1 ]) P ← augment(P, [p3L−2 ]) for k = 1 to L − 2 do Q ← augment(Q, [p3k+2 ]) for k = 1 to L − 1 do R ← augment(R, [p3k ]) % Q[k − 1]-b˝ol és P[k]-ból kombinálva S ← [q−1 , q0 ] for k = 0 to L − 2 do S ← augment(S, [Q[k], R[k], P[k + 1]]) S ← augment(S, [qL , qL+1 ]) return S

A csomópontok megválasztása lehet ekvidisztáns: ui = i, i = 0, . . . , L, de a gyakorlatban bevált az arányosan felvett csomópont vektor:

u0 u1 ui uL

= 0, = kq−1 − q1 k, = ui−1 + kqi − qi−1 k, i = 2, . . . , L − 1, = uL−1 + kqL+1 − qL−1 k.

A kétféle csomópont vektor összehasonlításához ld. a 3.20. ábrát.


76

3.20. ábra. Kubikus, C2 osztályú Bézier-szplájn. Fekete vonal: a de Boorpoligon, piros vonal: a szplájn ekvidisztáns csomópontokkal, kék vonal: a szplájn arányosan felvett csomópontokkal.

Ekvidisztáns csomópontok esetén a Böhm-szerkesztés jelent˝osen egyszer˝usödik, és csak felez˝opont illetve harmadolópont számítására redukálódik. (ld. 3.21. ábra!) 1 1 p2 = p1 + q1 , 2 2 2 1 p3k+1 = qk + qk+1 , 3 3 1 2 p3k+2 = qk + qk+1 , 3 3 1 1 p3k = p3k−1 + p3k+1 , 2 2 1 1 p3L−2 = qL−1 + p3L−1 . 2 2 q2

q1

p1

p8

p0

p9

3.21. ábra. A Böhm-szerkesztés ekvidisztáns csomópontokkal


77

Ö SSZEFOGLALÓ Kubikus, C2 osztályú Bézier-szplájn: Kubikus, Bézier-szplájnt a

C2

osztályú

p0 , p1 = q0 , q1 , q2 , . . . , qL−1 , p3L−1 = qL , p3L de Boor-poligonnal és a (u0 , u1 , . . . , uL ) csomópont vektorral adunk meg. A hiányzó kontrollpontokat az alábbi, ún. Böhmszerkesztéssel kapjuk meg: ∆u1 ∆u0 p2 = q0 + q1 , ∆u0 + ∆u1 ∆u0 + ∆u1 ∆uk + ∆uk+1 ∆uk−1 p3k+1 = qk + qk+1 , ∆uk−1 + ∆uk + ∆uk+1 ∆uk−1 + ∆uk + ∆uk+1 ∆uk−1 + ∆uk ∆uk+1 qk + qk+1 , p3k+2 = ∆uk−1 + ∆uk + ∆uk+1 ∆uk−1 + ∆uk + ∆uk+1 ∆uk−1 ∆uk p3k−1 + p3k+1 , p3k = ∆uk−1 + ∆uk ∆uk−1 + ∆uk ∆uL−1 ∆uL−2 p3L−2 = qL−1 + qL . ∆uL−2 + ∆uL−1 ∆uL−2 + ∆uL−1

3.6.8. Racionális Bézier görbék 3.43. Példa. Határozzuk meg egy térbeli Bézier-görbe centrális vetületét! A vetítés centruma legyen a z tengely −1/r pontja, a képsík az xy sík. Jelölje a görbe komponensfüggvényeit px , py , pz , azaz p(u) = (px (u), py (u), pz (u)); a pi = (pix , piy , piz ) kontrollpont centrális vetületét jelölje p0i , tehát

p0i

=

piy pix , , rpiz + 1 rpiz + 1

a görbe centrális vetülete pedig

0

p (u) =

py (u) px (u) , . rpz (u) + 1 rpz (u) + 1


78

A vetület komponensfüggvényeit tovább alakítva: p0x (u) =

px (u) ∑ni=0 Bni (u)pix = = rpz (u) + 1 r ∑ni=0 Bni (u)piz + 1

a nevez˝oben az egyes helyett ∑ni=0 Bni (u)-t írva p ∑ni=0 Bni (u)(rpiz + 1) rpizix+1 ∑ni=0 Bni (u)pix = n = ∑i=0 Bni (u)(rpiz + 1) ∑ni=0 Bni (u)(rpiz + 1)

bevezetve az r˜i = rpiz + 1 jelölést ∑ni=0 Bni (u)˜ri p0ix = . ∑ni=0 Bni (u)˜ri Hasonlóan átalakítva p0y (u)-t, p0y (u) =

∑ni=0 Bni (u)˜ri p0iy , ∑ni=0 Bni (u)˜ri

p0i (u) =

∑ni=0 Bni (u)˜ri p0i . ∑ni=0 Bni (u)˜ri

így (3.34)

(3.34) nem a p0i kontrollpontokhoz tartozó Bézier-görbe, de a (3.2) általános görbemodellezési elvet kielégíti: p0i (u) =

n Bni (u)˜ri ∑ni=0 Bni (u)˜ri p0i = p0i , ∑ n n n (u)˜ n (u)˜ B r B r ∑i=0 i i j i=0 ∑ j=0 j

ahol a p0i kontrollponthoz tartozó súlyfüggvény Bni (u)˜ri ∑nj=0 Bnj (u)˜r j és a súlyfüggvények egységbontást alkotnak: n

Bni (u)˜ri ∑ n n r j = 1. i=0 ∑ j=0 B j (u)˜ A (3.34) görbetípust általánosan megfogalmazva egy új görbeosztályt kapunk. 3.44. Definíció. A ((p0 , r0 ), (p1 , r1 ), . . . , (pn , rn )), pi ∈ RN , ri ∈ R súlyozott pontrendszerhez tartozó racionális Bézier-görbe alatt a n

∑ Bni(u)ripi

(3.35)

p : [0, 1] → RN , u 7→ p(u) =

i=0 n

∑

j=0

parametrizált görbét értjük.

(N = 2, 3) Bnj (u)r j


79

Egy kontrollpont súlyának növelésével a görbe az adott kontrollponthoz „húz”, ld. 3.6.8. ábra! p1

p2

p0

p3

3.22. ábra. Az ábrán harmadfokú racionális Bézier-görbék láthatók. A görbe viselkedését figyelhetjük meg p1 súlyának változásával. (Kék: r1 = 0, 2, zöld: r1 = 1, piros: r1 = 1, 8. A többi kontrollpont súlya 1.)

A (3.35) kifejezésben pi súlya u ∈ [0, 1]-ben Bni (u)ri n

∑

,

Bnj (u)r j

j=0

így a súlyok összege n

∑

i=0

Bni (u)ri n

∑

= 1.

Bnj (u)r j

j=0

A súlyfüggvények egységbontása miatt a (3.35) racionális Bézier-görbére teljesül az affin invariancia, ha az ri súlyok mindegyike nemnegatív, akkor a konvex burokban maradás tulajdonsága is, emellett ha az els˝o és utolsó súly nem zéró, a végpont interpoláció is. Ha negatív súlyok is szerepelnek, akkor a konvex burokban maradás már nem feltétlenül teljesül (3.23 ábra). 3.45. Megjegyzés (Racionális Bézier-görbe, mint Bézier-görbe a projektív térben). Legyenek p0 , p1 , . . . , pn ∈ R3 a kontrollpontok, (r0 , r1 , . . . , rn ) a súlyok. pi komponenseit jelölje (pix , piy , piz ), így pri = [pix ri , piy ri , piz ri , ri ]


80

p1

p2

p0

p3

3.23. ábra. Harmadfokú racionális Bézier-görbe negatív súllyal. Az ábrán harmadfokú racionális Bézier görbe látható, r1 = −0, 5, megfigyelhetjük, hogy a konvex burokban maradás tulajdonsága nem teljesül. pi homogén koordinátáit adja. Írjuk föl a projektív tér pr0 , pr1 , . . . , prn kontrollpont rendszeréhez tartozó Bézier-görbét: n

pr (u) =

∑ Bin(u)pri =

i=0

" =

n

n

n

n

∑ Bni(u)pix ri, ∑ Bni(u)piyri, ∑ Bni(u)pizri, ∑ Bni(u)ri

i=0

i=0

i=0

# .

i=0

Áttérve Descartes-komponensekre: n ∑i=0 Bni (u)pix ri ∑ni=0 Bni (u)piy ri ∑ni=0 Bni (u)piz ri , , n p(u) = ∑ni=0 Bni (u)ri ∑ni=0 Bni (u)ri ∑i=0 Bni (u)ri ∑ni=0 Bni (u)ri pi = n , ∑i=0 Bni (u)ri azaz a kontrollpontokhoz és a súlypontokhoz tartozó racionális Bézier görbe. Egy Bézier-görbe nem projektív invariáns: a (nem elfajuló) másodfokú Bézier görbeívek parabolaívek, de parabolaív projektív képe lehet más affin típusú másodrend˝u görbe is, pl. hiperbolaív vagy ellipszisív. Utóbbi görbeívek azonban bizonyosan nem Bézier-görbék. Most vizsgáljuk meg a racionális Bézier-görbék projektív képét! 3.46. Tétel. Egy síkbeli racionális Bézier-görbe projektív invariáns: a ((p0 , r0 ), (p1 , r1 ), . . . (pn , rn )) súlyozott kontrollpont rendszerhez tartozó racionális Bézier-görbe projekt0 0 0 0 0 0 ív képe a (p0 , r0 ), (p1 , r1 ), . . . (pn , rn ) súlyozott kontrollpont-rendszerhez tartozó racionális Bézier-görbe, ahol p0i a pi projektív képe, továbbá ri0 =


81

ri (a31 pix + a32 piy + a33 ), ahol (ai j ) ∈ GL(3) a projektív transzformációt reprezentáló mátrix. B IZONYÍTÁS . Dolgozzunk tehát síkban (N = 2), a 3.44 definíció jelölései mellett legyen p(u) = (px (u), py (u)), pi = (pix , piy ). Homogén koordinátákkal " # n

p(u) =

n

n

∑ Bni(u)ri pix , ∑ Bni(u)ri piy, ∑ Bni(u)ri .

i=0

i=0

i=0

A projektív transzformációt reprezentálja a (ai j ) ∈ GL(3) mátrix. A görbe projektív képe (a továbbiakban minden összegzés 0-tól n-ig fut): p0x (u) =

a11 ∑ Bni (u)ri pix + a12 ∑ Bni (u)ri piy + a13 ∑ ri Bni (u) , a31 ∑ Bni (u)ri pix + a32 ∑ Bni (u)ri piy + a33 ∑ ri Bni (u)

p0y (u) =

a21 ∑ Bni (u)ri pix + a22 ∑ Bni (u)ri piy + a23 ∑ ri Bni (u) . a31 ∑ Bni (u)ri pix + a32 ∑ Bni (u)ri piy + a33 ∑ ri Bni (u)

Átalakításokkal: p0x (u) =

∑ Bni (u)ri (a11 pix + a12 piy + a13 ) = ∑ Bni (u)ri (a31 pix + a32 piy + a33 ) r0

z }|i { a11 pix + a12 piy + a13 n B (u) r (a p + a p + a ∑ i i 31 ix 32 iy 33) a31 pix + a32 piy + a33 = . ∑ Bni (u) ri (a31 pix + a32 piy + a33 ) | {z } ri0

Mivel a pi kontrollpont projektív képe a11 pix + a12 piy + a13 a21 pix + a22 piy + a23 0 pi = , , a31 pix + a32 piy + a33 a31 pix + a32 piy + a33 így p0x (u) =

∑ Bni (u)ri0 p0ix . ∑ Bni (u)ri0

p0y (u) =

∑ Bni (u)ri0 p0iy , ∑ Bni (u)ri0

p0 (u) =

∑ Bni (u)ri0 p0i ∑ Bni (u)ri0

Hasonlóan,

azaz

3.47. Példa (A kör, mint racionális Bézier görbe). Az egységkör szokásos r : [0, 2π] → R2 , t 7→ r(t) = (cost, sint)


82

paraméterezése helyett egy másik paraméterezésre térünk át. Az új paraméter u = tg(t/2) (0 ≤ t ≤ π/2). Egyszer˝u trigonometrikus átalakítással: 1 + u2 = 1 + tg2

t cos2 (t/2) sin2 (t/2) 1 = + = , 2 2 2 2 cos (t/2) cos (t/2) cos (t/2)

1 − u2 = 1 − tg2

cos2 (t/2) sin2 (t/2) cost t = − = , 2 2 2 cos (t/2) cos (t/2) cos2 (t/2)

így cost =

1 − u2 . 1 + u2

Mivel t ∈ [0, π/2] esetén sint ≥ 0, illetve u = tg(t/2) ≥ 0, s sint =

1−

1 − u2

s

2 =

1 + u2

4u2 2u = . 2 2 (1 + u ) 1 + u2

Így a nyílt negyedkörív paraméterezésére azt kaptuk, hogy [0, 1] 3 u 7→

1 − u2 2u , . 1 + u2 1 + u2

Legyen p0 = (1, 0), p1 = (1, 1), p2 = (0, 1), r0 = 0, r1 = 1, r2 = 2. A ((p0 , r0 ), (p1 , r1 ), (p2 , r2 )) súlyozott kontrollpont-rendszerhez tartozó racionális Bézier görbe pontosan ezt a paraméterezést adja: B20 (u) p(u) =

=

1 1 0 2 2 + B1 (u) + 2B2 (u) 0 1 1 B20 (u) + B21 (u) + 2B22 (u)

=

1 1 0 2 + 2u(1 − u) + 2u 0 1 1 = 2 2 (1 − u) + 2u(1 − u) + 2u

(1 − u)2

(1 − u)2 1 2u(1 − u) 1 2u2 0 = + + = 1 1 + u2 0 1 + u2 1 + u2 1 =

1 − u2 2u , 1 + u2 1 + u2

t .

3.7. B-SZPLÁJN GÖRBÉK

83

Ö SSZEFOGLALÓ racionális Bézier-görbe: A ((p0 , r0 ), (p1 , r1 ), . . . , (pn , rn )), pi ∈ RN , ri ∈ R súlyozott pontrendszerhez tartozó racionális Bézier-görbe n

∑ Bni(u)ripi

p : [0, 1] → RN , u 7→ p(u) =

i=0 n

∑

(N = 2, 3). Bnj (u)r j

j=0

- Racionális Bézier-görbe centrális vetülete, projektív képe racionális Bézier-görbe. - Racionális Bézier-görbeként minden kúpszelet el˝oállítható. 3.7. B-szplájn görbék A (racionális) Bézier görbéknek számos el˝onye mellett megemlíthetünk néhány hátrányát: (1) A Bernstein-polinomok a (0, 1) intervallumon nem zéró értéket vesznek föl, ezért az egyes kontrollpontok változtatása az egész görbét érinti. (2) Új kontrollpont bevezetése fokszám növekedésével jár. Ezzel szemben a B-szplájn görbék esetében a fokszám a kontrollpontok számától független, valamint a görbe az egyes kontrollpontokkal bizonyos értelemben „lokálisan” változtatható. A B-szplájn görbe alapkoncepciója az eddigiekhez hasonló, a kontrollpontokat súlyfüggvényekkel, az ún. B-szplájn függvényekkel súlyozzuk. 3.7.1. A kvadratikus uniformális B-szplájn. 3.48. Példa. Legyenek adva a p0 , p1 , p2 pontok. Határozzuk meg a p1 + p2 p0 + p1 , p1 , 2 2 kontrollpontokhoz tartozó Bézier-görbét: p0 + p1 p1 + p2 p(u) = (1 − u)2 + 2u(1 − u)p1 + u2 = 2 2 (1 − u)2 −2u2 + 2u + 1 u2 = p0 + p1 + p2 , u ∈ [0, 1]. 2 2 2 A kapott másodfokú görbeív ugyan nem megy át p0 , p2 kontrollpontokon, de egy nagyon könnyen illeszthet˝o görbetípust ad. Emellett teljesül a konvex burokban maradás tulajdonsága, ugyanis a (1 − u)2 −2u2 + 2u + 1 u2 , , , 2 2 2

u ∈ [0, 1]


84

p1

p0

p2

3.24. ábra. Kvadratikus B-szplájn görbeív 1

u

1

3.25. ábra. Kvadratikus uniformális B-szplájn függvények. súlyfüggvények (az ún. kvadratikus uniformális B-szplájn függvények) nem negatívak és egységbontást alkotnak. Az el˝obbi görbeív kifejezése mátrix alakban:    p0 1 −2 1 1 p(u) = u2 u 1 −2 2 0 p1  , u ∈ [0, 1], 2 1 10 p 2

vagy a tényez˝oket rövidítve: p(u) = UMS2 P, ahol t U = u2 u 1 ; P = p0 p1 p2 ;   1 −2 1 1 MS2 = −2 2 0 . 2 1 10 3.49. Definíció. A p0 , . . . , pn kontrollpontokhoz tartozó kvadratikus uniformális B-szplájn (röviden kvadratikus UBS): ahol

p : [0, n − 1] → RN ,

p(u) = pi (u − i + 1),

u ∈ [i − 1, i],

(1 − u)2 −2u2 + 2u + 1 u2 pi (u) = pi−1 + pi + pi+1 2 2 2 (i = 1, . . . , n − 1, u ∈ [0, 1]);


85

illetve mátrix alakban:    p 1 −2 1 i−1 1 pi (u) = u2 u 1 −2 2 0 pi  (i = 1, . . . , n − 1, u ∈ [0, 1]). 2 p 1 10 i+1

p1

p3 p0

p2

3.26. ábra. Kvadratikus UBS.

1

1 u

2

3.27. ábra. A kontrollpontok súlyfüggvényei az el˝oz˝o ábrában. Piros: p0 súlyfüggvénye, zöld: p1 , kék: p2 , szilva: p3 .

3.50. Tétel. (A definíció jelöléseivel.) A pi és pi+1 görbeívek egymáshoz C1 osztályban csatlakoznak. B IZONYÍTÁS . Egyszer˝u behelyettesítéssel: 1 pi (1) = pi+1 (0) = (pi + pi+1 ) . 2 Az i-edik B-szplájn görbeív deriváltja: p0i (u) = (u − 1)pi−1 + (1 − 2u)pi + upi+1 . Tehát p0i (1) = p0i+1 (0) = pi+1 − pi .

A kvadratikus uniformális B-szplájnra teljesül a lokális változtathatóság tulajdonsága: minden kontrollpont legfeljebb három görbeív el˝oállításában játszik szerepet, emellett minden görbeívet pontosan három kontrollpont befolyásol.


86

3.51. Példa (zárt görbe). A görbetípussal nagyon könny˝u C1 osztályú zárt görbét el˝oállítani: A p0 , . . . , pn , p0 , p1 kontrollpontok által meghatározott kvadratikus UBS zárt lesz, hiszen a görbe kezd˝o és végpontja egyaránt p0 + p1 . 2 A zárt görbe esetében minden kontrollpont pontosan három görbeív el˝oállításában szerepel. p1

p0

p2

p3

p5

p4

3.28. ábra. Zárt kvadratikus UBS 3.7.2. A kubikus uniformális B-szplájn. A kubikus (uniformális) B-szplájn koncepciója éppen olyan egyszer˝u, mint a kvadratikus (uniformális) B-szplájné. Legyenek adva a p0 , p1 , p2 , p3 , p4 kontrollpontok. A p0 , p1 , p2 , p3 kontrollpontok lineáris kombinációival úgy állítjuk el˝o a q0 , q1 , q2 , q3 kontrollpontokat, hogy az utóbbiakhoz tartozó kubikus Béziergörbe „jól” csatlakozzon a p1 , p2 , p3 , p4 kontrollpontokból analóg módon kapott r0 , r1 , r2 , r3 kontrollpontokhoz tartozó kubikus Bézier-görbéhez. Ha p0 + 4p1 + p2 2p1 + p2 p1 + 2p2 p1 + 4p2 + p3 , q1 = , q2 = , q3 = ; q0 = 6 3 3 6 és 2p2 + p3 p2 + 2p3 p2 + 4p3 + p4 p1 + 4p2 + p3 , r1 = , r2 = , r3 = , r0 = 6 3 3 6 akkor a két Bézier-görbe C2 osztályban csatlakozik. Ez könnyen ellen˝orizhet˝o a Bézier-görbe deriváltjára vonatkozó összefüggésb˝ol: p3 − p1 q0 (1) = 3(q3 − q2 ) = = 3(r1 − r0 ) = r0 (0), 2 továbbá q00 (1) = 6(q3 − 2q2 + q1 ) = p1 − 2p2 + p3 = = 6(r2 − 2r1 + r0 ) = r00 (0).

A keresett súlyfüggvényeket tehát úgy kapjuk, ha felírjuk a q0 , q1 , q2 , q3 kontrollpontokhoz tartozó Bézier-görbét, majd leolvassuk p0 , p1 , p2 , p3 függvény-együtthatóit.


87

3.52. Definíció. A p0 , . . . , pn kontrollpontokhoz tartozó kubikus (uniformális) B-szplájn: ahol

p : [0, n − 2] → RN ,

p(u) = pi (u − i + 1),

u ∈ [i − 1, i],

−u3 + 3u2 − 3u + 1 3u3 − 6u2 + 4 pi−1 + pi + 6 6 u3 −3u3 + 3u2 + 3u + 1 + pi+1 + pi+2 , (i = 1, . . . , n − 2, u ∈ [0, 1]); 6 6 illetve mátrix alakban:    −1 3 −3 1 pi−1  3 −6 3 0 pi  1   pi (u) = u3 u2 u 1  −3 0 3 0 pi+1  6 1 4 10 pi+2 pi (u) =

(i = 1, . . . , n − 2, u ∈ [0, 1]). 1

u

1

3.29. ábra. Kubikus (uniformális) B-szplájn függvények. A kubikus (uniformális) B-szplájn görbeívek els˝o és második deriváltjából könny˝u megállapítani, hogy a pi (u) és pi+1 (u) görbeívek C2 osztályban csatlakoznak. A zárt görbe el˝oállítása is analóg a kvadratikus esethez: az els˝o három kontrollpontot a kontrollpontok sorozatában meg kell ismételni (a felsorolás végén). 3.7.3. A B-szplájn függvények. A 3.11. példában a töröttvonalat, mint ekvidisztáns csomópontvektorhoz tartozó szplájnt értelmeztük. Térjünk vissza ehhez a nagyon egyszer˝u példához! 3.53. Példa (töröttvonal – újraolvasva). Most adjunk meg általános csomópontvektort: (u0 , u1 , . . . , un ). A töröttvonal paraméterezése így p : [u0 , un ] → RN u − ui u − ui ui+1 − u p(u) = pi = pi+1 + pi , ha u ∈ [ui , ui+1 ], ui+1 − ui ui+1 − ui ui+1 − ui ahol pi (t) = tpi+1 + (1 − t)pi .


88

p1

p3 p0

p2 p4

3.30. ábra. Ugyanazon kontrollpoligonhoz tartozó kvadratikus (pirossal) és kubikus (kékkel) B-szplájn

pi (1 ≤ i ≤ n − 1, azaz a két határponttól eltekintve) súlyfüggvénye  u−u i−1   ui −ui−1 ha u ∈ [ui−1 , ui ), −u Ni (u) = uui+1−u ha u ∈ [ui , ui+1 ], i i+1   0 egyébként. Bevezetve a csomópontvektortól függ˝o ( 1 Ni,1 : R → R, Ni,1 (u) = 0

ha u ∈ [ui , ui+1 ), egyébként

függvényeket, a súlyfüggvényt így is felírhatjuk: (3.36)

Ni (u) =

u − ui−1 ui+1 − u Ni,1 (u). Ni−1,1 (u) + ui − ui−1 ui+1 − ui

p0 a töröttvonal egyetlen szakaszát befolyásolja, súlyfüggvénye ( u1 −u ha u ∈ [u0 , u1 ), N0 (u) = u1 −u0 0 egyébként, hasonlóan pn -re, de az intervallumot jobbról is zárva: ( u−u n−1 ha u ∈ [un−1 , un ], Nn (u) = un −un−1 0 egyébként. A két határpontra is alkalmazhatjuk a (3.36) képletet, ha az els˝o csomópontot és utolsó csomópontot megismételjük, és megállapodunk abban, hogy a nullával való osztás eredménye 0. Tehát az új csomópontvektor képzése (u0 , u0 , u1 , . . . , un , un ) ← (u0 , u1 , . . . , un ),

így az új csomópontvektorban az elemek indexe 0-tól (n + 2)-ig fut, azaz az elemeket az egyszer˝uség kedvéért szintén u-val jelölve: (u0 , u1 , u2 , . . . , un+1 , un+2 )


89

lesz az új csomópontvektor. (3.36) jobb oldalán az index 1-gyel n˝o és már a határpontokban is helyes súlyfüggvényt ad: ui+2 − u u − ui Ni,1 (u) + Ni+1,1 (u), Ni (u) = ui+1 − ui ui+2 − ui+1 természetesen az Ni,1 függvényeket újra kiszámolva a megváltozott csomóponthoz. Egy kicsit átírva a súlyfüggvény megadását, ha k jelöli az elején és végén azonos kontrollpontok számát (azaz k = 2, ami éppen a görbe fokszáma +1), akkor a súlyfüggvények u − ui ui+k − u (3.37) Ni (u) = Ni,k−1 (u) + Ni+1,k−1 (u), ui+k−1 − ui ui+k − ui+1

azaz a görbe p(u) = ∑ni=0 Ni (u)pi .

Az el˝oz˝o példával motiválva vezetjük be a következ˝o definíciót. 3.54. Definíció. Legyenek adva az n ≥ 0, K ≥ 0 egész számok és az u = (u0 , u1 , . . . , un+K ) ∈ Rn+K+1 ,

csomópontvektor, ahol u0 ≤ u1 ≤ . . . ≤ un+K . Legyen 0 ≤ i ≤ n + K − 1-re ( 1 ha u ∈ [ui , ui+1 ) és ui < ui+1 , Ni,1 : R → R, Ni,1 (u) = 0 egyébként. Ha k > 1, akkor az u csomópontvektorhoz tartozó i-edik, k-ad rend˝u Bszplájn függvény u − ui ui+k − u Ni,k (u) = Ni,k−1 (u) + Ni+1,k−1 (u), ui+k−1 − ui ui+k − ui+1 (3.38) (u ∈ R, k = 2, . . . , K),

ahol ha a nevez˝oben 0 lép fel, akkor az osztás eredményét 0-nak értelmezzük. Ha a csomópontok sorozatában egy csomópont egymás után m-szer lép föl, akkor azt mondjuk, hogy a csomópont multiplicitása m. 3.55. Példa. n = 2, K = 3, u = (0, 0, 0, 1, 1, 1), azaz u0 = u1 = u2 = 0, u3 = u4 = u5 = 1. Az ui < ui+1 feltétel csak i = 2-re teljesül, így az egyetlen nem zéró els˝orend˝u (nullad fokú) bázisfüggvény ( 1 ha u ∈ [0, 1), N2,1 (u) = 0 egyébként. A továbbiakban azokat a tagokat nem írjuk ki, ahol a (3.38) összeg mindkét tagjában 0-val való osztás van. ( u3 − u 1 − u ha u ∈ [0, 1), N1,2 (u) = N2,1 (u) = (1 − u)N2,1 (u) = u3 − u2 0 egyébként.


90

1

0 n=4, K=3, u=[0,0,0,1,2,3,3,3]

3.31. ábra. Példák kvadratikus B-szplájn függvényekre

u − u2 N2,1 (u) = uN2,1 (u) = N2,2 (u) = u3 − u2 u3 − u N1,2 (u) = (1 − u)N1,2 (u) = N0,3 (u) = u3 − u1

( u 0

ha u ∈ [0, 1), egyébként.

( (1 − u)2 0

u − u1 u4 − u N1,2 (u) + N2,2 (u) = u3 − u1 u4 − u2 ( 2u(1 − u) = uN1,2 (u) + (1 − u)N2,2 (u) = 0

ha u ∈ [0, 1), egyébként.

N1,3 (u) =

u − u2 N2,3 (u) = N2,2 (u) = uN2,2 (u) = u4 − u2

( u2 0

ha u ∈ [0, 1), egyébként. ha u ∈ [0, 1), egyébként.

A megadott csomópontvektorhoz tartozó harmadrend˝u (másodfokú) bázisfüggvények a [0, 1) intervallumon megegyeznek a másodfokú Bernsteinpolinomokkal. A 3.31–3.32. ábrákon néhány további példát látunk. Az x tengelyen a háromszögek a csomópontokat mutatják. A középs˝o ábrán megfigyelhetjük, hogy egy csomópont multiplicitásának növelése a differenciálhatóság rendjét csökkenti. A legalsó esetben a bázisfüggvények az [u2 , u5 ) intervallumon kívül 0 értéket vesznek föl. 3.56. Tétel. Az Ni,k (u) B-szplájn bázisfüggvényekre teljesülnek a következ˝o tulajdonságok: - nem negatívak: Ni,k (u) ≥ 0, u ∈ R - az [uk−1 , un+1 ) intervallumon egységbontást alkotnak: ∑ni=0 Ni,k (u) = 1, ha u ∈ [uk−1 , un+1 )


91

1

0 n=4, K=3, u=[0,0,0,1,1,3,3,3]

3.32. ábra. Példák kvadratikus B-szplájn függvényekre

1

2 n=4, K=3, u=[0,1,2,3,4,5,6,7] 3.33. ábra. Példák kvadratikus B-szplájn függvényekre

- kompakt tartóval rendelkeznek2: supp(Ni,k ) = [ui , ui+k ] - differenciálhatóak: az Ni,k (u) függvény C∞ osztályú a csomópontokon kívül, egy m-szeres multiplicitású csomópontban Ck−1−m osztályú. B IZONYÍTÁS . Teljes indukcióval a bizonyítás egyszer˝u, de hosszadalmas, ezért mell˝ozzük. 3.57. A LGORITMUS (A B-szplájn függvények kiszámítása). A B-szplájn függvények kiszámításakor abból az egyszer˝u észrevételb˝ol indulunk ki, hogy egy adott paraméterértéknél csak egyetlen els˝orend˝u bázisfüggvény nem zéró, ebb˝ol az összes olyan bázisfüggvény kiszámítható, amely tartójában az adott paraméterérték benne van. Így számítottuk ki a B-szplájn 2Egy függvény tartója azon pontok halmazának lezártja, ahol a függvény értéke nem

zérus, az f függvény tartóját supp( f )-el jelöljük.


92

függvényeket a 3.55. példában: N0,3

N1,2

N2,1

z< zz z zz zz

z< zz z zz zz

DD DD DD DD "

DD DD DD DD "

< zz zz z z zz

N2,2

N1,3

DD DD DD DD "

N2,3

Az oszlopok els˝o és utolsó elemeinél (3.38) egyik tagja zéró (az els˝o elem a DNY-i, az utolsó elem az ÉNY-i szomszédból számolható). 3.57. BS PLINE AT U Input: n, K, u = (u0 , u1 , . . . , un+K ), u ∈ [uK−1 , un+1 ) Output: N = (N0,K (u), N1,K (u), . . . , Nn,K (u)) N ← (0, 0, . . . , 0) % N inicializálása % Megállapítjuk, hogy u melyik részintervallumban van: for i = K − 1 to n do if ui ≤ u and u < ui+1 then k←i N[k] ← 1 for m = 1 to K − 1 do u −u N[k − m] ← uk+1k+1 −uk−m+1 N[k − m + 1] for j = k − m + 1 to k − 1 do u j+m+1 −u u−u j N[ j] =← u j+m −u N[ j] + u j+m+1 −u j+1 N[ j + 1] j

N[k] ← return N

u−uk uk+m −uk N[k]

A nemnegativitás és az egységbontás miatt a B-szplájn függvényekkel az affin invariancia és a konvex burokban maradás tulajdonságát teljesít˝o modellgörbét lehet képezni a keverési elvnek megfelel˝oen. 3.58. Definíció. A p0 , p1 , . . . , pn kontrollpontokhoz és az u = (u0 , u1 , . . . , un+K ) csomópontvektorhoz tartozó K-adrend˝u B-szplájn alatt a n

p : [uK−1 , un+1 ] → RD , p(u) = ∑ Ni,K (u)pi , i=0

(D = 2, 3)


93

3.34. ábra. B-szplájn görbék parametrizált görbét értjük. A B-szplájn kontrollpontjait de Boorpontoknak, a kontrollpoligont de Boor-poligonnak is nevezzük. 3.59. Definíció. Az u csomópontvektor kötött, ha fennáll u0 = u1 = . . . = uK−1 és un+1 = un+2 = . . . = un+K . A 3.34. ábrán a 3.31–3.33. ábrák B-szplájn függvényeihez tartozó Bszplájn görbék vannak ugyanazon kontrollpontok esetén. A piros görbe: a 3.31. ábrán látható függvényrendszerhez, a zöld görbe a 3.32. ábrához, míg a szaggatott kék görbe a 3.33. ábrához tartozik.


94

Ö SSZEFOGLALÓ B-szplájn függvények: Az u = (u0 , u1 , . . . , un+K ) ∈ Rn+K+1 csomópontvektorhoz tartozó B-szplájn függvények: ( 1 ha u ∈ [ui , ui+1 ) és ui < ui+1 Ni,1 : R → R, Ni,1 (u) = 0 egyébként. Ni,k (u) =

u − ui ui+k − u Ni,k−1 (u) + Ni+1,k−1 (u), ui+k−1 − ui ui+k − ui+1 (u ∈ R, k = 2, . . . , K).

B-szplájn:

n

p : [uK−1 , un+1 ] → RN , p(u) = ∑ Ni,K (u)pi , i=0

ahol p0 , p1 , . . . , pn a kontrollpontok sorozata. 3.7.4. Pont a B-szplájn görbén: a de Boor-algoritmus. 3.60. Példa (csomópont beszúrása). Egy B-szplájn csomópontjaihoz adjunk hozzá egy új csomópontot úgy, hogy a görbe alakja ne változzon! Az új csomópont akár meglév˝o is lehet, ekkor a csomópont multiplicitását növeljük. A csomópontok száma (a korábbi jelölésekkel) n + K + 1, így a csomópontok számának növelése maga után vonja vagy a kontrollpontok számának, vagy a fokszámnak a növelését. A fokszám növelése (rögzített kontrollpontok mellett) a görbe alakjának változását is magával vonja, így csak az új kontrollpontok meghatározásával kell foglalkozni. Legyenek p0 , p1 , . . . , pn a görbe kontrollpontjai, u = (u0 , u1 , . . . , un+K ) a görbe csomópontvektora, t ∈ [uk , uk+1 ). Keressük meg, hogy ez az intervallum mely bázisfüggvények tartójában van benne. Az egyetlen ilyen els˝orend˝u bázisfüggvény Nk,1 , a másodrend˝uek Nk−1,2 , Nk,2 , . . . , a K-adrend˝uek Nk−K+1 , . . . , Nk,K . Így a pk−K+1 , . . . , pk kontrollpontokat kell újraszámolni. (Mivel a görbe az [uK−1 , un+1 ) intervallumon van értelmezve, így k − K + 1 ≥ 0, az indexek „nem fogyhatnak el” id˝o el˝ott.) Az új kontrollpontok meghatározását ahhoz teljesen hasonlóan kell végeznünk, mint ahogyan azt a Bézier-görbe fokszám emelésénél tettük (ld. 3.6.5). pk−K+1 és pk változatlanul maradnak, új kontrollpontok: pk−K+1 , qk−K+2 , . . . , qk , pk ahol (3.39)

qi = (1 − ai )pi−1 + ai pi t − ui ai = , k − K + 2 ≤ i ≤ k. ui+K−1 − ui

3.8. NURBS-GÖRBÉK

95

Speciálisan, ha t = uk , azaz egy meglév˝o csomópont multiplicitását növeljük, akkor qk = pk−1 . Ha uk multiplicitása eredetileg m, akkor az utolsó m új kontrollpont egyezik meg a régiekkel: qk = pk−1 , qk−1 = pk−2 , . . . , qk−m+1 = pk−m . Most tekintsük azt az esetet, amikor egy csomópont multiplicitását egymást követ˝o beszúrásokkal a fokszámig, azaz K − 1-ig növeltük. Az utolsó lépésben már csak egyetlen új kontrollpontot generáltunk, miközben a görbe alakja sosem változott. Ha azonban egy csomópont multiplicitása K − 1, akkor a görbe áthalad a kontrollponton, azaz az utolsónak generált kontrollpont a görbén van. Ez az eljárás alkalmas a B-szplájn görbe pontjainak generálására anélkül, hogy a B-szplájn bázisfüggvényeket külön meghatároznánk. 3.61. Tétel. Ha a csomópont beszúrás szukcesszív alkalmazásával egy csomópont fokszáma megegyezik a görbe fokszámával, akkor az utolsónak generált kontrollpont a görbén van. 3.62. A LGORITMUS (B-szplájn görbe rajzolása). A 3.61. tétel alapján, a (3.39) egyenletet figyelembe véve a görbepontot az alábbi algoritmus alapján számíthatjuk ki. Ö SSZEFOGLALÓ csomópont beszúrása: Ha (u0 , . . . , uk ≤ t < uk+1 , . . . , un+K ) ← (u0 , . . . , uk < uk+1 , . . . , un+K ), akkor

(pk−K+1 , qk−K+2 , . . . , qk , pk ) ← (pk−K+1 , . . . , pk ),

ahol

qi = (1 − ai )pi−1 + ai pi t − ui ai = , k − K + 2 ≤ i ≤ k. ui+K−1 − ui Ha beszúrásokkal egy csomópont multiplicitását K − 1-re növeljük, akkor az utolsónak generált q a görbén van. 3.8. NURBS-görbék A 3.45. megjegyzésben a racionális Bézier-görbér˝ol egy lehetséges bevezetési módját vázoltuk. Hasonló módon térhetünk át B-szplájn görbér˝ol racionális B-szplájn görbére, így eljutunk a görbemodellezés talán legnépszer˝ubb görbetípusához a NURBS görbékhez (az elnevezés az angolból származik: NonUniform Rational B-Spline). A továbbiakban egyszer˝uen racionális B-szplájn görbékr˝ol beszélünk.

3.8. NURBS-GÖRBÉK

96

3.62. P OINT O N BS PLINE Input: u ∈ [uK−1 , un+1 ) Output: p(u) % Megállapítjuk, hogy u melyik részintervallumban van: for i = K − 1 to n do if ui ≤ u and u < ui+1 then k←i if u 6= uk then h ← K − 1 % Ennyiszer végezzük el a beszúrást. m ← 0 % A multiplicitás beállítása 0-nak. if u = uk then % Megállapítjuk uk multiplicitását: for i = 0 to K − 1 do m←1 if uk−i = uk then m ← m+1 h ← K − 1 − m % Ennyiszer végezzük el a beszúrást. for i = k − K + 1 to k − m do pi,0 ← pi for j = 1 to h do for i = k − K + 1 + j to k − m do a ← (u − ui )/(ui+K− j − ui ) pi, j ← (1 − a) · pi−1, j−1 + a · pi, j−1 return pk−m,K−1−m Legyenek p0 , p1 , . . . , pn ∈ R3 a kontrollpontok, u0 , u1 , . . . , un a csomópontok, r0 , r1 , . . . , rn a súlyok. pi komponenseit jelölje (pix , piy , piz ), így pri = [pix ri , piy ri , piz ri , ri ] pi homogén koordinátáit adja. Írjuk föl a projektív tér pr0 , pr1 , . . . , prn kontrollpontjaihoz és az u0 , u1 , . . . , un csomópontokhoz tartozó K-adrend˝u Bszplájnt: n

pr (u) =

∑ Ni,K (u)pri =

i=0

" =

n

n

n

n

∑ Ni,K (u)pix ri, ∑ Ni,K (u)piyri, ∑ Ni,K (u)pizri, ∑ Ni,K (u)ri

i=0

i=0

i=0

i=0

Áttérve derékszög˝u koordinátákra: n ∑i=0 Ni,K (u)pix ri ∑ni=0 Ni,K (u)piy ri ∑ni=0 Ni,K (u)piz ri , , n p(u) = ∑ni=0 Ni,K (u)ri ∑ni=0 Ni,K (u)ri ∑i=0 Ni,K (u)ri n ∑ Ni,K (u)ri pi = i=0 . ∑ni=0 Ni,K (u)ri

# .

3.8. NURBS-GÖRBÉK

97

p5 n=7, K=4, u=[0,0,0,0,1,2,3,4,5,5,5,5] r=[1,1,1,1,1,1,1,1,1] r=[1,1,1,1,1,2,1,1,1] r=[1,1,1,1,1,0.5,1,1,1] 3.35. ábra. Racionális B-szplájn görbék: a p5 kontrollpont súlyának változtatásával alakítottuk a görbét.

Természetesen hasonlóan dolgozhattunk volna síkban is. 3.63. Definíció. A p0 , p1 , . . . , pn kontrollpontokhoz, u0 , u1 , . . . , un+K csomópontokhoz, r0 , r1 , . . . , rn súlyokhoz tartozó K-adrend˝u racionális Bszplájn görbe alatt a p : [uK−1 , un+1 ] → RD , (3.40)

p(u) =

∑ni=0 Ni,K (u)ri pi ∑ni=0 Ni,K (u)ri

parametrizált görbét értjük. A pi kontrollpont súlyfüggvénye (az ún. racionális B-szplájn bázisfüggvény) (3.41)

Ri,K (u) =

Ni,K (u)ri , n ∑ j=0 N j,K (u)r j

így a görbét a keverési elvnek megfelel˝oen felírva: n

p(u) = ∑ Ri,K (u)pi . i=0

(3.41)-b˝ol leolvasható, hogy a pi kontrollpont súlyának növelése vagy csökkentése Ri,K értékét növeli vagy csökkenti minden (nem zéró) paraméterérték mellett: ri növelésével a görbe pi -hez „húz”, míg csökkentésével pi -t˝ol „tart”, ráadásul a változtatás lokálisan hat. Ld. a 3.35. ábra. A definíció és a B-szplájn bázisfüggvények megfelel˝o tulajdonságai alapján egyszer˝uen levezethet˝ok az alábbiak.

3.8. NURBS-GÖRBÉK

98

3.64. Tétel (a racionális B-szplájn függvények tulajdonságai). Nemnegatív súlyok esetén a racionális B-szplájn függvényekre teljesülnek az alábbi tulajdonságok. nemnegativitás: ∀u ∈ [uK−1 , un+1 ]-re Ri,k (u) ≥ 0 egységbontás: ∀u ∈ [uK−1 , un+1 ]-re ∑ni=0 Ri,k (u) = 1 lokális tartó: supp Ri,k = [ui , ui+k ] differenciálhatóság: m-szeres multiplicitású csomópontban Ri,k (k − m)-szer differenciálható, a csomópont multiplicitásának növelése a bázisfüggvény differenciálhatóságának rendjét csökkenti specializáció: ha minden kontrollpont súlya azonos, akkor a racionális B-szplájn függvények megegyeznek a B-szplájn függvényekkel: Ni,k = Ri,k . 3.65. Tétel (a NURBS görbék tulajdonságai). Nemnegatív súlyok esetén a racionális B-szplájn görbékre teljesülnek az alábbiak: végpont interpoláció: kötött csomópontvektorra végpont interpoláló, azaz ha u0 = u1 = . . . = uK−1 , un+1 = un+2 = . . . un+K , akkor p(uK−1 ) = p0 , p(un+1 ) = pn projektív invariáns: NURBS görbe projektív képe, centrális vetülete NURBS görbe konvex burokban maradás: teljesül a konvex burokban maradás tulajdonsága differenciálhatóság: m-szeres multiplicitású csomópontban a görbe (k − m)-szer differenciálható, a csomópontokon kívül C∞ lokálisan változtatható: pi változtatása a görbét csak az [ui , ui+K ) intervallumon befolyásolhatja. specializáció: azonos súlyok esetén a NURBS görbe megegyezik egy B-szplájn görbével, ha ráadásul n = K és a csomópont vektor (0, . . . , 0, 1, . . . , 1), akkor a görbe Bézier-görbe. | {z } | {z } K×

K×

3.8. NURBS-GÖRBÉK

99

3.66. A LGORITMUS (Racionális B-szplájn görbe rajzolása). A fejezet bevezet˝ojében vázolt származtatás szerint a racionális B-szplájn görbe nem más, mint egy B-szplájn a projektív síkon/térben, ezért a 3.62. algoritmust minimálisan megváltoztatva kapjuk a görbepont meghatározásának algoritmusát. (A pszeudokód síkgörbére vonatkozik, az utolsó sor változtatásával kapjuk a térgörbékre.) 3.66. P OINT O N NURBS Input: (r0 , r1 , . . . , rn ) Output: p(u) % Áttérünk homogén koordinátákra: for i = 0 to n do pi ← (ri · pi , ri ) % Kiszámítjuk a görbepontot a projektív síkon P OINT O N BS PLINE % Áttérünk Descartes-koordinátákra return (pK−m,K−1−m [1]/pK−m,K−1−m [3], pK−m,K−1−m [2]/pK−m,K−1−m [3])

Ö SSZEFOGLALÓ racionális B-szplájn görbe: - kontrollpontok: p0 , p1 , . . . , pn , - csomópontok: u0 , u1 , . . . , un+K , súlyok: r0 , r1 , . . . , rn a racionális B-szplájn görbe: p : [uK−1 , un+1 ] → RD , ∑n Ni,K (u)ri pi p(u) = i=0 . ∑ni=0 Ni,K (u)ri

4. FEJEZET

Felületek tervezése 4.1. A felület fogalma A hétköznapi szóhasználatban nagyon sok geometriai objektumra mondjuk azt, hogy felület. Ebben a fejezetben a „felületek” lehetséges matematikai modelljeir˝ol lesz szó. Példaként tekintsük el˝oször a gömböt. Mint ponthalmaz, a gömb a tér egy rögzített O pontjától adott r > 0 távolságra elhelyezked˝o pontok halmaza: F = P ∈ R3 | kP − Ok = r . Ha O = (x0 , y0 , z0 ), akkor az el˝obbi ponthalmazt úgy adhatjuk meg, mint az (4.1)

F : R3 → R, F(x, y, z) = (x − x0 )2 + (y − y0 )2 + (z − z0 )2 − r2

függvény zérushelyeinek halmaza a térben.

4.1. ábra. Ismer˝os felület: gömb Sok, geometriailag könnyen definiálható felület pontjai el˝oállíthatók (4.1)-hez hasonlóan egy háromváltozós függvény zérushelyeinek halmazaként. Egy egyenes körhengert geometriailag egy rögzített egyenest˝ol rögzített r > 0 távolságra elhelyezked˝o pontok halmazaként definiálhatunk. Ha a tengely a z tengely, akkor egy egyenes körhenger egyenlete (4.2)

x2 + y2 − r2 = 0.

Tehát most F(x, y, z) = x2 + y2 − r2 .

100

4.1. A FELÜLET FOGALMA

101

4.2. ábra. Ismer˝os felület: henger

A következ˝o példánk az egyenes körkúp, amelyet geometriailag megkaphatunk úgy, hogy egy egyenest megforgatunk egy o˝ t metsz˝o egyenes körül. Legyen a forgástengely a z tengely, a forgatott egyenes pedig az xz sík x = a · z egyenese. Ekkor a kúp egyenlete (4.3)

x2 + y2 − a2 · z2 = 0.

4.3. ábra. Ismer˝os felület: kúp

A (4.1)–(4.3) egyenletek F(x, y, z) = 0 alakúak, ahol F : R3 → R differenciálható függvény. A kúpnak van egy speciális pontja, a csúcspont. Hogyan ismerhet˝o föl a kúp csúcspontja az egyenletéb˝ol? A számítógépi grafikában fontos jelent˝osége van, hogy a felület pontjaiban (legalábbis „majdnem minden” pontjában) tudjuk képezni a felület normálisát, vagyis a felületre mer˝oleges vektort. A felületi normálist a felület egy P pontjában


102

F gradiense adja, azaz grad F(P) =

∂F ∂F ∂F , , ∂x ∂y ∂z

,

(F(P) = 0).

P

Látható, hogy a csúcspont, (jelen esetben az origó) az F(x, y, z) = x2 + y2 − a2 z2

függvény kritikus pontja, azaz itt a gradiens zérus: grad F(x, y, z) = (2x, 2y, −2za2 ), grad F(0, 0, 0) = (0, 0, 0),

míg a többi felület egyetlen pontja sem kritikus pontja F-nek.

4.1. Definíció. Legyen F : R3 → R differenciálható függvény. Azt mondjuk, hogy az F(x, y, z) = 0 egyenlet egy reguláris implicit egyenlet, ha teljesül, hogy F(P) = 0 =⇒ grad F(P) 6= 0, (P ∈ R3 ). Egy térbeli ponthalmazt reguláris implicit felületnek nevezünk, ha el˝oállítható egy reguláris implicit egyenlet megoldáshalmazaként. Ha az F(x, y, z) = 0 egyenletb˝ol valamelyik változó kifejezhet˝o, pl. y = f (x, z), akkor speciálisan Euler–Monge felületr˝ol beszélünk. Az Euler– Monge felület lényegében kétváltozós függvény grafikonját jelenti. Ha f : U → R, (U ⊂ R2 ) kétváltozós differenciálható függvény, akkor a szóban forgó felület, vagyis f grafikonja F = {(x, f (x, z), z) | (x, z) ∈ U)} .

A felület matematikai reprezentálásának harmadik módja részben analógiát mutat a parametrizált görbékhez. Parametrizált görbe alatt egyváltozós vektorérték˝u leképezést értettünk, amely az egy szabadsági fokú mozgásnak felel meg. Ha a mozgás két szabadsági fokú, akkor jutunk el a parametrizált felület fogalmához. A parametrizált felület tehát kétváltozós, vektorérték˝u leképezés. A felületi normális képzéséhez szükség van a leképezés parciális deriváltjai vektoriális szorzatára. A továbbiakban U ⊆ R2 egy nem üres nyílt halmazt jelöl a síkon, de a számítógépi grafika szempontjából gyakran U = [a, b] × [c, d] ⊂ R2 egy téglalap. (Azaz a határpontokat is hozzávesszük a halmazhoz.) Megállapodunk néhány jelölésben. Egy r : U → R3 differenciálható leképezésnél a változókat általában u-val és vvel, a komponensfüggvényeket x, y, z-vel jelöljük, azaz r(u, v) = (x(u, v), y(u, v), z(u, v)). r els˝o és második változó szerinti parciális deriváltjait ru és rv jelöli, tehát ∂x ∂y ∂z ∂x ∂y ∂z ru (p) = , , , rv (p) = , , , ∂u ∂u ∂u p ∂v ∂v ∂v p ahol p = (u, v). A felületi normálist egy p ∈ U pontban ru (p) × rv (p) adja, így a reguláris parametrizált felület fogalmához fel kell tennünk, hogy ez a vektor nem nullvektor:


103

4.2. Definíció. Egy r : U → R3 differenciálható leképezést reguláris parametrizált felületnek (röviden parametrizált felületnek) nevezünk, ha teljesül, hogy (4.4)

∀p ∈ U : ru (p) × rv (p) 6= 0.

Az Euler–Monge-felületre mint parametrizált felületre is gondolhatunk, ahol x(u, v) = u, y(u, v) = f (u, v), z(u, v) = v. Szükségünk lehet arra, hogy egy felületen görbét rajzoljunk. Parametrizált felület esetében ehhez el˝oször egy görbét adunk meg a paramétertartományban. 4.3. Definíció. Legyen r : U → R3 parametrizált felület, c : I → U reguláris parametrizált görbe. A c˜ = r ◦ c : I → R3 parametrizált görbét felületi görbének nevezzük. I

c

>

U

c r◦ c˜ =

r >

∨ R3

4.4. Példa (a felület paramétervonalai). Legyen r : U → R3 parametrizált felület, v0 , u0 konstansok. Legyen c1 (t) = (t, v0 ), (t, v0 ) ∈ U,

így c˜ u (t) = r(t, v0 ); illetve

c2 (t) = (u0 ,t), (u0 ,t) ∈ U,

így c˜ v (t) = r(u0 ,t) az r felület paramétervonalai. Határozzuk meg a paramétervonalak sebességvektorait: c˜ 0u (t) = ru (t, v0 ), c˜ 0v (t) = rv (u0 ,t). A fenti relációk alapján az ru (p), rv (p) (p ∈ U) vektorokat paramétervonal érint˝oknek is szokás nevezni a p pontban. Parametrizált felületek ábrázolása. A parametrizált felületek ábrázolása kézenfekv˝onek t˝unik kijelölt paramétervonalak ábrázolásával, mert így a problémát parametrizált görbék ábrázolására vezetjük vissza. Valóban, a számítógépi grafika történetében ez a módszer is megjelent, azonban számos problémát vet föl. A felület a paramétervonalak egy részét takarhatja. A takart görbeszakaszok megkeresése nem túl egyszer˝u. (Az érdekl˝od˝o


104

olvasó keressen a takart vonal algoritmus, angolul hidden line algorithm kulcsszavakra.) Itt egy másik ábrázolási elvet, a triangularizációs elvet ismertetünk. Ennek lényege, hogy a felületet háromszöglapok rendszerével modellezzük. Legyen a parametrizált felület r : [a, b] × [c, d] → R3 . Az els˝o esetben legyen a háromszögek által meghatározott poliédermodell konvex!

4.4. T RIANGULAR S URFACE(N, M) Input: N, M Output: parametrizált felület ábrája for i = 0 to N − 1 do for j = 0 to M − 1 do ∆u = (b − a)/N ∆v = (d − c)/M ui = a + (b − a)/N · i v j = c + (d − c)/M · j if M r(ui , v j )r(ui + ∆u, v j + ∆v)r(ui + ∆u, v j ) látszik then ProjectAndDraw M r(ui , v j )r(ui + ∆u, v j + ∆v)r(ui + ∆u, v j ) if M r(ui , v j )r(ui , v j + ∆v)r(ui + ∆u, v j + ∆v) látszik then ProjectAndDraw M r(ui , v j )r(ui , v j + ∆v)r(ui + ∆u, v j + ∆v)

A pszeudokódban használt ProjectAndDraw parancs a vetítést és a színnel kitöltést is tartalmazza. A láthatóság eldöntésére konvex esetben már adtunk megoldást (1.16. példa). Nem konvex esetben a láthatóság eldöntését ki kell hagyni, hiszen lehetséges az is, hogy egy háromszöglemez egy része takart, másik része látszik. Így ebben az esetben valamennyi háromszöglemezt lerajzoljuk, de a takarás kezelését a programba beépítjük. Erre hatékony raszteres algoritmusok vannak (pl. z-tár algoritmus). Vektorgrafikus algoritmusok közül csak arra utalok, amellyel a jegyzet ábráit is készítettem, ez a fest˝o algoritmus. Ennek lényege, hogy a háromszöglemezeket a néz˝ot˝ol való nem csökken˝o távolság szerint sorrendbe rendezzük és a rajzolás sorrendjénél ezt figyelembe vesszük: a távolabbi háromszöglemezt˝ol haladunk a közelebbi felé, a háromszögeket pedig fed˝oszínekkel (esetleg csak részben fed˝o színekkel) töltjük ki. (A fest˝o algoritmus nem mindig ad helyes megoldást, a háromszöglemez nem pontszer˝u volta miatt.)

4.2. PÉLDÁK FELÜLETEKRE

105

4.4. T RIANGULAR S URFACE(N, M) Input: N, M Output: parametrizált felület ábrája M= [ ] for i = 0 to N − 1 do for j = 0 to M − 1 do ∆u = (b − a)/N ∆v = (d − c)/M ui = a + (b − a)/N · i v j = c + (d − c)/M · j M← [M, r(ui , v j )r(ui + ∆u, v j + ∆v)r(ui + ∆u, v j )] M← [M, r(ui , v j )r(ui , v j + ∆v)r(ui + ∆u, v j + ∆v)] M elemeit a néz˝ot˝ol való távolság szerint sorba rendezzük M elemeit (sorrendben) rajzoljuk, színnel kitöltjük

Ö SSZEFOGLALÓ implicit felület: F : R3 → R differenciálható függvény és teljesül, hogy F(P) = 0 =⇒ grad F(P) 6= 0. F = {P ∈ R3 | F(P) = 0} az implicit felület, míg grad F(P) a felület normálvektora P ∈ F-ben. Euler–Monge-felület: Az implicit felület speciális esete, ha valamelyik koordináta kifejezhet˝o a másik kett˝ob˝ol, pl. y = f (x, z). parametrizált felület: Legyen U = [a, b] × [c, d] ⊂ R2 , r : U → R3 differenciálható és ru × rv 6= 0. F = r(U) és F normálvektora p ∈ U-ban ru (p) × rv (p).

4.2. Példák felületekre 4.5. Példa (másodrend˝u felületek). Az el˝oz˝o fejezetben szerepl˝o felületek, vagyis a gömb, a kúp és a henger implicit egyenletei másodfokúak voltak. Általánosan másodrend˝u felületnek nevezzük az olyan felületet, amelynek implicit egyenlete ax2 + by2 + cz2 + 2dxy + 2exz + 2 f yz + gx + hy + iz + j = 0, ahol a, b, . . . , j ∈ R konstansok, továbbá a, b, . . . , f nem mindegyike zéró. Lineáris algebrai eszközökkel belátható, hogy egybevágósági transzformációval ezen felületek mindegyike átvihet˝o az 1. táblázatban szerepl˝o felületek valamelyikébe. 4.6. Példa (forgásfelületek). Legyen adva az xy síkban a c : [a, b] → R3 , c(u) = (x(u), y(u), 0)


1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

106

valós ellipszoid x2 /a2 + y2 /b2 + z2 /c2 = 1 képzetes ellipszoid x2 /a2 + y2 /b2 + z2 /c2 = −1 egyköpeny˝u hiperboloid x2 /a2 + y2 /b2 − z2 /c2 = 1 kétköpeny˝u hiperboloid x2 /a2 + y2 /b2 − z2 /c2 = −1 valós másodrend˝u kúp x2 /a2 + y2 /b2 − z2 /c2 = 0 képzetes másodrend˝u kúp x2 /a2 + y2 /b2 + z2 /c2 = 0 elliptikus paraboloid x2 /a2 + y2 /b2 + 2z = 0 hiperbolikus paraboloid x2 /a2 − y2 /b2 + 2z = 0 valós elliptikus henger x2 /a2 + y2 /b2 = 1 képzetes elliptikus henger x2 /a2 + y2 /b2 = −1 hiperbolikus henger x2 /a2 − y2 /b2 = 1 valós metsz˝o síkpár x2 /a2 − y2 /b2 = 0 képzetes metsz˝o síkpár x2 /a2 + y2 /b2 = 0 parabolikus henger x2 + 2ry = 0 valós párhuzamos síkpár x 2 = a2 képzetes párhuzamos síkpár x2 = −a2 egybees˝o síkpár x2 = 0 1. táblázat. A másodrend˝u felületek izometria osztályai y

x z

4.4. ábra. Parametrizált forgásfelület

reguláris parametrizált görbe, melyet megforgatunk az y tengely körül. Ha a forgatás v szöge befutja a [0, 2π] ⊂ R intervallumot, akkor egy forgásfelületet kapunk: (4.5)

r : [a, b] × [0, 2π] → R3 , r(u, v) = R∗y (v)c(u).


107

y

x z

4.5. ábra. Tórusz Koordinátákkal    cos v 0 − sin v x(u) r(u, v) =  0 1 0  · y(u) , sin v 0 cos v 0 

azaz r(u, v) = (x(u) cos v, y(u), x(u) sin v). Számítsuk ki a felületi normálist! (ru × rv )(u, v) = (y0 (u)x(u) cos v, −x0 (u)x(u), y0 (u)x(u) sin v).

Innen k(ru × rv )(u, v)k2 = x(u)2 · kc0 (u)k2 adódik, azaz x(u) 6= 0 esetén a felület reguláris. Parametrizált gömbfelülethez úgy juthatunk, hogy egy olyan félkört forgatnunk meg az y tengely körül, melynek átmér˝oje az y tengelyen van, maga a félkör pedig az xy síkban. Az el˝oz˝o példát alkalmazva c(u) = (R cos u, R sin u, 0) és u ∈ [−π/2, π/2], így r(u, v) = (R cos u cos v, R sin u, R cos u sin v), (v ∈ [0, 2π]).

u = ±π/2-re a regularitási feltétel nem teljesül: a teljes gömböt nem tudjuk úgy tekinteni, mint reguláris parametrizált felületet. A gömbnek ezt a paraméterezését hosszúsági kör-szélességi kör paraméterezésnek, röviden földrajzi paraméterezésnek nevezzük. Másik fontos példa forgásfelületre a tórusz. Legyen most c(u) = (a + b · cos u, b · sin u, 0),

azaz az (a, 0, 0) középpontú, b sugarú kört megforgatjuk az y tengely körül (a, b > 0, a > b). A kapott felület paraméteres el˝oállítása: (4.6) r(u, v) = (a + b cos u) cos v, b sin u, (a + b cos u) sin v .


108

y

x z

4.6. ábra. Hengerfelület A feltételek miatt a + b cos u > 0, így a regularitási feltétel minden pontban teljesül. Megjegyezzük, hogy egyes másodrend˝u felületeket is megkaphatunk forgásfelületként. 4.7. Példa (vonalfelületek). Legyen c : [a, b] → R3 egy parametrizált térgörbe (a vezérgörbe), E : [a, b] → R3 sehol sem zéró vektormez˝o, azaz ∀t ∈ [a, b]-re kE(t)k = 6 0. A c görbe minden t paraméterérték˝u pontjában tekintünk egy E(t) irányvektorú egyenest. Ezek az egyenesek alkotják a (c, E) által generált vonalfelületet. Paraméteres el˝oállítása r : [a, b] × R → R3 , (u, v) 7→ r(u, v) = c(u) + v · E(u).

A regularitási feltétel nem automatikusan teljesül. Legyen például c : [a, b] → R3 reguláris parametrizált görbe, E(u) = a ∈ 3 R rögzített nemzéró vektor, továbbá a 6 k c0 . A c vezérgörbéj˝u a alkotóirányú hengerfelület paraméteres el˝oállítása: r : [a, b] × R → R3 , r(u, v) = c(u) + v · a.

(ru × rv )(u, v) = c0 (u) × a 6= 0, ezért egy reguláris parametrizált felületet kapunk. 4.8. Példa (loft felület). A következ˝o példákban egy egyszer˝u technikát alkalmazunk, a „sraffozást”. A „sraffozás” a P és Q pontok összeköt˝o egyenesének pontjait a tQ + (1 − t)P (t ∈ R) alakban adja meg. Ha t ∈ [0, 1], akkor a PQ szakasz pontjait kapjuk. Legyen c : [a, b] → R3 reguláris parametrizált görbe, M ∈ R3 egy pont. A c vezérgörbéj˝u M csúcspontú kúpfelület paraméteres el˝oállítása r : [a, b] × R → R3 , r(u, v) = v · c(u) + (1 − v) · M,

azaz c(u) és M között sraffozunk. (Nyilvánvalóan vonalfelületet kaptunk, melyre E(u) = c(u) − M.)


109

y

x z

4.7. ábra. Kúpfelület

4.8. ábra. Loft felület két ellipszis között Legyenek f, g : [a, b] → R3 parametrizált görbék. Ha az azonos paraméterértékekhez tartozó pontok között sraffozunk, akkor az r : [a, b] × R → R3 , r(u, v) = (1 − v)f(u) + vg(u)

felületet kapjuk, a két görbe által meghatározott loft felület (4.8. ábra). Sraffozással könnyen konstruálhatunk négy pontot interpoláló felületet. Legyenek P, Q, R, S a pontok. Sraffozzunk a PQ és RS szakaszok között: r : [0, 1] × [0, 1] → R3 ,

r(u, v) = (1 − v) [uQ + (1 − u)P] + v [uS + (1 − u)R] .

A kapott felületnél (amely egyébként hiperbolikus paraboloid, azaz másodrend˝u felület) r(0, 0) = P, r(1, 0) = Q, r(0, 1) = R, r(1, 1) = S teljesül. Ezt a felületet négy pontot interpoláló bilineáris felületnek is nevezzük. 4.9. Példa (Coons-felület). Gyakran el˝oforduló tervezési feladat, hogy a keresett felületnek a határgörbéi ismertek, azaz a határgörbéket interpoláló


110

4.9. ábra. Coons-felület, melyet négy parabolaív határol felület keresünk. Legyenek a szemközti határgörbék f0 és f1 , illetve g0 és g1 . El˝oször sraffozással kössük össze f0 -t és f1 -t: r1 (u, v) = (1 − u)f0 (v) + uf1 (v).

A kapott felület hibája g0 -nál: míg g1 -nél:

h0 (u) = g0 (u) − r1 (u, 0);

h1 (u) = g1 (u) − r1 (u, 1). Most a „hibagörbéket” sraffozzuk: h(u, v) = (1 − v)h0 (u) + vh1 (u).

Ez a „hibafelület” v = 0-nál és v = 1-nél pontosan az r1 felület hibáját adja, így az r1 + h felület a kívánt tulajdonságokkal rendelkezik: r(u, v) = (1 − u)f0 (v) + uf1 (v) + (1 − v)h0 (u) + vh1 (u). 4.10. Példa (Súrolófelület). A súrolófelületet úgy kapjuk, hogy egy görbe mentén (ezt nevezzük trajektóriának) eltolunk egy másik görbét (utóbbit nevezzük keresztmetszetgörbének). Legyen f : [a, b] → R3 reguláris görbe, a trajektória, amely az egyszer˝uség kedvéért ívhossz paraméterezés˝u, azaz kf0 (u)k = 1, továbbá g : [c, d] → R2 , v 7→ g(v) = (g1 (v), g2 (v))

a keresztmetszetgörbe. A súrolófelület:

r : [a, b] × [c, d] → R3

r(u, v) = f(u) + g1 (v)x(u) + g2 (v)y(u), ahol (f0 , x, y) : [a, b] → R3 „mozgó” ortonormált bázis. Az x, y vektorok szokásos választása, x = f00 /kf00 k és y = f0 ×x. (Ha f ívhossz paraméterezés˝u, akkor f00 ⊥ f0 , egyébként a mer˝olegesség nem teljesül.) Ha g1 (v) = r cos v és g2 (v) = r sin v (r > 0), akkor szokás tubusról beszélni.

4.3. TENZORSZORZAT-FELÜLETEK

111

4.10. ábra. Hengeres csavarvonalra húzott tubus

4.3. Tenzorszorzat-felületek A szabad formájú felületek tervezésében az egyik leggyakrabban használt felülettípus a tenzorszorzat-felület. Tekintsünk az p0 , . . . , pm kontrollpontokhoz és f0 , . . . , fm bázisfüggvényekhez tartozó m

p(u) = ∑ fi (u)pi i=0

görbét, ahol a kontrollpontokat szintén egy paraméter függvényeként állítjuk el˝o a (g0 , . . . , gn ) bázisfüggvényekkel: n

pi (v) =

∑ g j (v)pi j .

j=0

4.11. Definíció. A p : [0, 1] × [0, 1] → R3 , (u, v) 7→ p(u, v) m

(4.7)

p(u, v) = ∑

n

∑ fi(u)g j (v)pi j

i=0 j=0

parametrizált felületet az Fi j (u, v) = fi (u)g j (v) bázisfüggvényekhez tartozó tenzorszorzat-felületnek nevezzük. Az el˝oz˝oekben már tárgyalt bilineáris felület egy tenzorszorzat-felület, mely négy kontrollponthoz és másodfokú bázisfüggvényekhez tartozik. A különböz˝o számítások könnyebb kivitelezése miatt célszer˝u a (4.7) el˝oállítást mátrixalakban felírni:     g0 (v) p00 . . . p0n g (v) ..    1.  . p(u, v) = f0 (u) f1 (u) . . . fm (u)  ... .  ..  pm0 . . . pmn gn (v)


112

p(u, v) parciális deriváltjai: ∂p (u, v) = pu (u, v) = ∂u    g0 (v) p . . . p 00 0n g (v) ..    1.  . = ∂∂ fu0 (u) ∂∂ fu1 (u) . . . ∂∂fum (u)  ... .  ..  pm0 . . . pmn gn (v) 

∂p (u, v) = pv (u, v) = ∂v 



 

..  .  ∂ gn ∂ v (v)

∂ g0 (v) p0n  ∂∂gv1   ..    ∂ v (v) .

p00 . . . = f0 (u) f1 (u) . . . fm (u)  ... . pm0 . . . pmn 



A tenzorszorzat-felület (4.7)-szerinti felírása megfelel a „keverési elvnek” (lásd. 3.2. fejezet), csak a kontrollpontoknak most kett˝os indexe van. Így a korábban megfogalmazott tulajdonságok is érvényben maradnak: - ha az Fi j (u, v) = fi (u)g j (v) függvények egységbontást alkotnak, n azaz ∑m i=0 ∑ j=0 Fi j (u, v) = 1, akkor a felületre teljesül az affin invariancia elve, - ha ráadásul a bázisfüggvények nem negatívak, akkor teljesül a konvex burokban maradás tulajdonsága. 4.12. Példa (bikubikus tenzorszorzat-felület). Általános alakja 3

p(u, v) = ∑

3

∑ ui v j ai j ,

i=0 j=0

ahol ai j a felület algebrai együtthatói. 4.3.1. Bikubikus Hermite-felület. Csakúgy, mint a görbetervezésnél, a bikubikus tenzorszorzat-felület algebrai együtthatói nem mindegyikének van közvetlen intuitív jelentése. A   p(0, 0) p(0, 1) pv (0, 0) pv (0, 1)  p(1, 0) p(1, 1) pv (1, 0) pv (1, 1)   B= pu (0, 0) pu (0, 1) puv (0, 0) puv (0, 1) pu (1, 0) pu (1, 1) puv (1, 0) puv (1, 1) mátrix elemeit a görbe geometriai együtthatóinak nevezzük. A második parciálisaktól eltekintve a mátrix elemeinek közvetlen intuitív jelentése van: a sarokpontok, illetve a sarokpontokba befutó peremgörbék érint˝ovektorai. Az els˝o két oszlop a p(u, 0) illetve p(u, 1) peremgörbe geometriai együtthatóit; az els˝o két sor pedig a p(0, v) illetve p(1, v) peremgörbe geometriai együtthatóit adja meg.


113

4.11. ábra. Ferguson-felület a peremvonalak érint˝oivel a sarokpontokban

A geometriai és algebrai együtthatók közötti kapcsolat megadásához a Hermite-görbéknél megismert módszert alkalmazva, hosszadalmas de elemi számítás után kapjuk a felület kifejezését a geometriai együtthatókból:  3  F0 (v)  F13 (v)  p(u, v) = F03 (u) F13 (u) F23 (u) F33 (u) B  F 3 (v) , 2 F33 (v) ahol Fi3 , (i = 0, . . . , 3) a harmadfokú Hermite-polinomok. A fentebb leírt felülettervezési módszer el˝onye a peremgörbék pontos kontrollja a geometriai együtthatókkal, hátránya a vegyes parciálisok (az ún. csavarvektorok) jelenléte. A legegyszer˝ubb esetben ezeket zérusvektornak választjuk, ekkor kapjuk az ún. Ferguson-felületet (4.11. ábra). A Ferguson-felület a sarokpontok közelében intuitíve „meglehet˝osen lapos”, a csavarvektorok nemzéró megadásával lehet a felületet módosítani (ld. 4.12. ábra). Hengerfelületeket Ferguson-felületként is könny˝u el˝oállítani, ha a geometriai együtthatók mátrixát megfelel˝oen választjuk. Legyen a vezérgörbe


114

4.12. ábra. A 4.11. ábra szerinti Ferguson-felület úgy módosítva, hogy puv (0, 1) 6= 0 olyan Hermite-görbe, melynek geometriai együtthatói (p0 , p1 , v0 , v1 ), alkotóiránya a. A megfelel˝o hengerfelület geometriai együtthatói:   p0 p0 + a a a p1 p1 + a a a  B= v0 v0 0 0 . v1 v1 0 0 Általánosabban, két különböz˝o Hermite-görbe közötti lineáris interpolációt kapunk, ha   p0 q0 a a p1 q1 b b  B= v0 w0 0 0 v1 w1 0 0 és a = q0 − p0 , b = q1 − p1 (ld. 4.13. ábra). 4.3.2. Bézier-négyszögfelületek. Egy Bézier-négyszögfelületet úgy kapunk, hogy a (4.7) egyenletbe bázisfüggvényekként a Bernsteinpolinomokat írjuk be. 4.13. Definíció. Legyenek pi j ∈ R3 , (i = 0, . . . m, j = 0, . . . , n) adott kontrollpontok. A p : [0, 1] × [0, 1] → R3 , (u, v) 7→ p(u, v), m

p(u, v) = ∑

n

∑ Bmi(u)Bnj(v)pi j

i=0 j=0

parametrizált felületet Bézier-négyszögfelületnek nevezzük. (4.14. ábra.)


115

4.13. ábra. Két Hermite-görbe közötti lineáris interpoláció

4.14. ábra. Bikubikus Bézier-négyszögfelület a kontrollhálójával

A Bézier-négyszögfelületek affin invariánsak és teljesül a konvex burokban maradás tulajdonsága is. Az alábbi tulajdonság pedig közvetlenül a definícióból következik. 4.14. Tétel. p(u, v) tartalmazza a p0,0 , pm,0 , pm,n , p0,n kontrollpontokat, nevezetesen p(0, 0) = p0,0 , p(1, 0) = pm,0 , p(1, 1) = pm,n , p(0, 1) = p0,n . (Sarokpont interpoláció.) A felület grafikai megjelenítése illetve a felületi pontok kiszámítása miatt fontos ismerni a paramétervonalakat. 4.15. Tétel. Egy Bézier-négyszögfelület paramétervonalai Bézier-görbék.


116

B IZONYÍTÁS . Tekintsük például a v = v0 = konstans paramétervonalakat! m

q(u) = p(u, v0 ) = ∑

n

∑ Bmi(u)Bnj(v0)pi j =

i=0 j=0

m

=∑

!

n

Bm i (u)

∑

i=0

Bnj (v0 )pi j

= ∑ Bm i (u)qi

j=0

|

m

i=0

{z qi

}

A paramétervonalak Bézier-görbék, de a paramétervonalak kontrollpontjai általában nem az eredeti kontrollpontok közül kerülnek ki; kivételt képeznek a peremvonalak, azaz az u = 0, u = 1, v = 0, v = 1 paramétervonalak, mert ezek kontrollpontjai az eredeti kontrollpontok közül valók. Pl. m

q0 (u) = p(u, 0) = ∑

n

m

∑ Bmi(u)Bnj(0)pi j = ∑ Bmi(u)pi0.

i=0 j=0

i=0

Ebb˝ol az is következik, hogy a sarokpontokban az érint˝osík a sarokpontokkal szomszédos kontrollpontokra illeszkedik, pl. az p00 sarokpontban az érint˝osík a p00 , p10 és p01 pontokon megy át. A 4.15. tétel rámutat arra, hogy hogyan lehet egy felületi pontot kiszámítani a de Casteljau-algoritmus alapján a kontrollpontokból. 1. meghatározzuk a v paraméterértékhez tartozó q0 , q1 , . . . , qm pontokat (qi -hez a pi0 , pi1 , . . . , pin kontrollpontokat használva, összesen m+1-szer alkalmazva a de Casteljau-algoritmust) 2. az q0 , q1 , . . . , qm kontrollpontokból meghatározzuk a Bézier-görbe u paraméterértékhez tartozó pontját (egy de Casteljau-algoritmus). 4.16. A LGORITMUS . A P OINT O N T HE S URFACE(u, v) algoritmus a de Casteljau algoritmus alapján kiszámítja a Bézier-négyszögfelület pontját. 4.16. P OINT O N T HE S URFACE(u, v) Input: u ∈ [0, 1], v ∈ [0, 1] Output: p(u, v) for i = 0 to m do Alkalmazzuk a de Casteljau-algoritmust a kontrollpontok mátrixának i. sorára v-vel return qi Alkalmazzuk a de Casteljau-algoritmust a q0 , q1 , . . . , qm pontokra u-val return p(u, v)


117

Összetettebb felületet a kontrollpontok számának növelésével alakíthatunk ki. Ennek célszer˝u módja nem a fokszám növelése, hanem több, alacsonyabb fokszámú (pl. bikubikus) felület egymáshoz illesztése. Csatlakoztassunk két bikubikus Bézier négyszögfelületet úgy, hogy egy-egy peremvonaluk egybeessen! Legyen a két felület 3

p : [0, 1] × [0, 1] → R3 , p(u, v) = ∑

3

∑ B3i (u)B3j (v)pi j ,

i=0 j=0 3

q : [0, 1] × [0, 1] → R3 , q(u, v) = ∑

3

∑ B3i (u)B3j (v)qi j .

i=0 j=0

Ha teljesül, hogy pi3 = qi0 , (i = 0, . . . , 3) akkor p(u, 1) = q(u, 0). (A két peremvonal paraméterértékenként ugyanaz.) A legegyszer˝ubb csatlakozási feltétel az, hogy a peremvonal mentén pv (u, 1) = qv (u, 0)

(4.8) teljesüljön. Mivel

pu (u, 1) = qu (u, 0) most automatikusan teljesül, így (4.8) azt jelenti, hogy a közös peremvonal mentén a két felület normálisai, így az érint˝osíkjaik is ugyanazok. Részletesen kiírva (4.8)-t, azt kapjuk, hogy 3

3

j=0

i=0

∑ B3j 0(1) · ∑ B3i (u)pi j =

3

3

j=0

i=0

∑ B3j 0(0) · ∑ B3i (u)qi j .

A Bernstein-polinomok deriváltjára vonatkozó (B3) összefüggést alkalmazva és felhasználva, hogy a Bernstein-polinomok értéke 0-nál és 1-nél 0 vagy 1: B33 0 (1) = 3B22 (1) = 3,

B32 0 (1) = −3B22 (1) = −3,

B30 0 (0) = −3B20 (0) = −3,

B31 0 (0) = 3B20 (0) = 3,

így 3

3

3

3

i=0

i=0

i=0

i=0

∑ B3i (u)pi3 − ∑ B3i (u)pi2 = − ∑ B3i (u)qi0 + ∑ B3i (u)qi1.

Felhasználva, hogy pi3 = qi0 , 3

3

i=0

i=0

2 ∑ B3i (u)pi3 = ∑ B3i (u)(pi2 + qi1 ), tehát a jobb oldali és a bal oldali polinomok együtthatói rendre megegyeznek. Végeredményként azt kapjuk, hogy (4.8) teljesülésének feltétele pi3 = qi0 =

1 (pi2 + qi1 ) , (i = 0, 1, 2, 3). 2


118

Geometriailag a fenti képlet azt jelenti, hogy a „csatlakozó” pi3 = qi0 kontrollpont a pi2 és qi1 kontrollpontok által meghatározott szakasz felez˝opontja. Az eredmény teljes analógiát mutat a (3.23) összefüggéssel. Az érint˝osík-folytonos csatlakozáshoz elegend˝o, ha a pi3 pont a pi2 , qi1 pontokat összeköt˝o szakaszon van. Ennek a ténynek az elemzése analóg a görbeelméletnél alkalmazott módszerhez (3.6.6. szakasz). 4.3.3. B-szplájn felületek. A B-szplájn görbék (ld. 3.7.3. szakasz) és B-szplájn felületek közötti kapcsolat analóg a Bézier-görbék és Béziernégyszögfelületek közötti kapcsolathoz. 4.17. Definíció. Legyen adva 1. kontrollpontok pi j , (i = 0, 1, . . . m; j = 0, 1, . . . n) rendszere 2. a felület u-irányú rendje, melyet K jelöl 3. a felület v-irányú rendje, melyet L jelöl 4. csomópontok u0 ≤ u1 ≤ . . . ≤ um+K rendszere az u paraméterértékre 5. csomópontok v0 ≤ v1 ≤ . . . ≤ vn+L rendszere a v paraméterértékre. A p : [uK−1 , um+1 ] × [vL−1 , vn+1 ] → R3 , m

p(u, v) = ∑

n

∑ Ni,K (u)N j,L (v)pi j

i=0 j=0

parametrizált felületet B-szplájn felületnek nevezzük (4.15. ábra). A pi j kontrollpont súlyfüggvénye Ni,K (u)N j,L (v), azaz két egyváltozós B-szplájn függvény szorzata

4.15. ábra. B-szplájn felület: n = m = 3, K = 4, L = 3, U = (0, 0, 0, 0, 1, 1, 1, 1), V = (0, 0, 0.25, .5, .75, 1, 1) A B-szplájn felület lehet egyik, vagy mindkét irányban kötött (a 4.15. ábrán a felület u irányban kötött, v irányban nem); egyik, vagy mindkét irányban zárt. A 4.16. ábrán ugyanazt a kontrollponthalmazt használtuk, mint a 4.15. ábrán, de a megfelel˝o kontrollpontokat ismételve v irányban zárt felületet kaptunk.


119

4.16. ábra. Egyik irányban zárt B-szplájn felület: n = 3, m = 5 (az ismétlések miatt), K = 4, L = 3, U = (0, 0, 0, 0, 1, 1, 1, 1), V = (0, 1, 2, 3, 4, 5, 6, 7, 8)

A B-szplájn felületek tulajdonságai a B-szplájn görbék és a tenzorszorzat-felületek tulajdonságai alapján könnyen megállapíthatók. A 4.17. ábra a lokális változtathatóságot szemlélteti.

4.17. ábra. Bikvadratikus B-szplájn felület; a síkból csak egyetlen kontrollpont lép ki, a „hegy” csak ennek a környékén emelkedik ki a síkból


120

Ö SSZEFOGLALÓ tenzorszorzat-felület: A p : [0, 1] × [0, 1] → R3 , (u, v) 7→ p(u, v) m

n

p(u, v) = ∑

∑ fi(u)g j (v)pi j

i=0 j=0

parametrizált felületet az Fi j (u, v) = fi (u)g j (v) bázisfüggvényekhez tartozó tenzorszorzat-felületnek nevezzük. Speciálisan: - Bikubikus Hermite-felület  3  F0 (v)  F13 (v)  p(u, v) = F03 (u) F13 (u) F23 (u) F33 (u) B  F 3 (v) , 2 F33 (v) ahol B a geometriai együtthatók mátrixa; - Bézier-négyszögfelület m

n

p(u, v) = ∑

∑ Bmi(u)Bnj(v)pi j ;

i=0 j=0

- B-szplájn felület m

p(u, v) = ∑

n

∑ Ni,K (u)N j,L (v)pi j .

i=0 j=0

Ábrák jegyzéke 1.1.Háromszöglemez kifelé mutató normálisa 1.2.Irányított sokszöglemez láthatósága 1.3.Lambert-féle koszinuszszabály 1.4.Affin transzformáció 1.5.Elforgatás az origó körül 1.6.Tengelyes tükrözés origón áthaladó egyenesre 1.7.Két dimenziós robotkar rotációs csuklókkal 1.8.Robotkar megadása 1.9.Projektív transzformáció

9 10 10 12 15 15 17 18 20

2.1.Csonkolt kocka 2.2.Mer˝oleges vetítés 2.3.Párhuzamos vetítés 2.4.A lyukkamera (camera obscura) képalkotása 2.5.A képsík és a centrum geometriai elhelyezése 2.6.Centrális vetítés 2.7.Hamis perspektíva 2.8.Ortogonális axonometria 2.9.Két iránypontos perspektíva a modell elforgatásával 2.10.Két iránypontos perspektíva a modell elforgatásával és eltolásával 2.11.Három iránypontos perspektíva 2.12.Standard izometrikus axonometria 2.13.45◦ -izometrikus axonometria 2.14.42◦ /7◦ -dimetrikus axonometria 2.15.Cabinet-dimetrikus axonometria 2.16.A centrális axonometria bázisalakzata

24 24 25 25 26 27 28 29 32 32 33 33 34 34 34 38

3.1.Hengeres csavarvonal 3.2.Lagrange-interpolációs polinom grafikonja 3.3.Lagrange-interplációs görbék 3.4.A Runge-függvény és interpolációja ekvidisztáns csomópontokkal 3.5.A Runge-függvény és interpolációja Csebisev. . .

40 47 48 49 49

121

ÁBRÁK JEGYZÉKE

3.6.Harmadfokú görbeív a geometriai együtthatókkal 3.7.Harmadfokú görbeív függése. . . 3.8.Harmadfokú görbeív függése. . . 3.9.Három pont interpolációja harmadfokú görbeívvel 3.10.Görbeillesztés Hermite-eljárással 3.11.Ötödfokú Bernstein-polinomok grafikonja 3.12.A Bernstein-polinomok „csúcsosodó” tulajdonsága 3.13.Harmadfokú Bézier-görbe és a kontrollpoligonja 3.14.A de Casteljau-algoritmus 3.15.Harmadfokú Bézier-görbe rajzolása a felez˝o algoritmussal 3.16.Bézier-görbe rajzolása szelektív mintavételezéssel 3.17.Bézier-görbe fokszám emelése 3.18.Kvadratikus Bézier-szplájn 3.19. C2 osztályú kubikus Bézier-szplájn 3.20.Kubikus, C2 osztályú Bézier-szplájn 3.21.A Böhm-szerkesztés ekvidisztáns csomópontokkal 3.22.Harmadfokú racionális Bézier-görbék 3.23.Harmadfokú racionális Bézier-görbe negatív súllyal 3.24.Kvadratikus B-szplájn görbeív 3.25.Kvadratikus uniformális B-szplájn függvények. 3.26.Kvadratikus UBS. 3.27.A kontrollpontok súlyfüggvényei 3.28.Zárt kvadratikus UBS 3.29.Kubikus (uniformális) B-szplájn függvények. 3.30.Kvadratikus és kubikus B-szplájn 3.31.Példák kvadratikus B-szplájn függvényekre 3.32.Példák kvadratikus B-szplájn függvényekre 3.33.Példák kvadratikus B-szplájn függvényekre 3.34.B-szplájn görbék 3.35.Racionális B-szplájn görbék 4.1.Ismer˝os felület: gömb 4.2.Ismer˝os felület: henger 4.3.Ismer˝os felület: kúp 4.4.Parametrizált forgásfelület 4.5.Tórusz 4.6.Hengerfelület 4.7.Kúpfelület

122

51 51 52 52 54 57 58 59 63 66 67 69 72 74 76 76 79 80 84 84 85 85 86 87 88 90 91 91 93 97 100 101 101 106 107 108 109

ÁBRÁK JEGYZÉKE

4.8.Loft felület két ellipszis között 4.9.Coons-felület, melyet négy parabolaív határol 4.10.Hengeres csavarvonalra húzott tubus 4.11.Ferguson-felület 4.12.Nem zéró csavarvektorral módosított Ferguson-felület 4.13.Két Hermite-görbe közötti lineáris interpoláció 4.14.Bikubikus Bézier-négyszögfelület a kontrollhálójával 4.15.B-szplájn felület 4.16.Egyik irányban zárt B-szplájn felület 4.17.Bikvadratikus B-szplájn felület

123

109 110 111 113 114 115 115 118 119 119

Irodalomjegyzék [1] M. K. Agoston. Computer Graphics and Geometric Modeling. Springer-Verlag London Limited, 2005. Implementation and Algorithms. [2] Bácsó S., Hoffmann M. Fejezetek a geometriából. EKF Líceum Kiadó, 2003. [3] G. Farin. Curves and surfaces for computer-aided geometric design. Computer Science and Scientific Computing. Academic Press Inc., San Diego, CA, fourth edition, 1997. [4] M. E. Mortenson. Geometric modeling. John Wiley & Sons Inc., New York, 1985. [5] D. Rogers and J. A. Adams. Mathematical Elements for Computer Graphics. McGrawHill, second edition, 1990. [6] D. Salomon. Transformations and Projections in Computer Graphics. Springer-Verlag, 2006. [7] C. K. Shene. Introduction to computing with geometry notes. http://www.cs.mtu.edu/˜shene. [8] Szabó, J. A számítógépi grafika elemei. Debreceni Egyetemi Kiadó, 2010. [9] Kurusa Á, Szem˝ok Á. A számítógépes ábrázoló geometria alapjai. Polygon, Szeged, 1999.

124

Számítógépi geometria. Kovács Zoltán

Recommend Documents