Bài giảng Đồ họa máy tính I - Phạm Tiến Sơn

174 trang phuongnguyen 1590

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa máy tính I - Phạm Tiến Sơn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

do_hoa_may_tinh_i_pham_tien_son.pdf

Nội dung text: Bài giảng Đồ họa máy tính I - Phạm Tiến Sơn

Đồ họa mỏy tớnh
` D- Oˆ HO. AMAY´ T´INH I . Pha.m Tiˆe´n Son D- `aLa.t, 2005
Mu. c lu. c L`o.i n´oid¯ˆa` u 7 . . 1 C´acthuˆa.t to´anv˜ed¯u`ong cong trˆenthiˆe´t bi. raster 9 1.1 D- oa.n thˇa˙’ng 9 1.1.1 Thuˆa.t to´ansˆo´ gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 . 1.1.2 Thuˆa.t to´and¯iˆe˙’m gi˜ua 13 1.1.3 Mˆo.t sˆo´ vˆa´n d¯ˆe` liˆenquan d¯ˆe´n thuˆa.t to´anv˜ed¯oa.n thˇa˙’ng . . . . . . . . 18 1.1.4 C´acthuˆo.c t´ınhcu˙’a d¯oa.n thˇa˙’ng . . . . . . . . . . . . . . . . . . . . . 21 1.2 D- u.`o.ng tr`on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.2.1 D- ˆo´i x´u.ng t´amd¯iˆe˙’m 22 . . . 1.2.2 Thuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯u`ong tr`on. . . . . . . . . . . . . . . . . . 23 1.3 D- u.`o.ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.3.1 Ellipse c´oda.ng ch´ınhtˇa´c 29 . . . 1.3.2 Ellipse trong tru`ong ho. p tˆo˙’ng qu´at. . . . . . . . . . . . . . . . . . . 34 . . 2 H`ınhho.c cu˙’a c´acd¯u`ong cong v`amˇa.t cong 47 2.1 Mo˙’. d¯ˆa`u 47 3
2.2 D- u.`o.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.2.1 Thuˆa.t to´ande Casteljau . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.2.2 D- a th´u.c Bernstein v`ad¯u.`o.ng cong Bezier . . . . . . . . . . . . . . . . 52 2.3 C´act´ınhchˆa´t cu˙’a d¯u.`o.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . 55 . . 2.3.1 D- iˆe` u khiˆe˙’n d¯i.a phuong . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.4 D- a th´u.c t`u.ng kh´ucv`ac´ach`amspline . . . . . . . . . . . . . . . . . . . . . . 60 . . 2.4.1 Su˙’ du. ng c´ach`amspline nhu c´ach`amtrˆo.n . . . . . . . . . . . . . . . 63 . 2.4.2 Xˆaydu. ng c´ach`amtrˆo.n 65 2.4.3 D- u.`o.ng cong spline v`ac´ach`amco. so˙’. . . . . . . . . . . . . . . . . . . 66 2.4.4 C´ach`amB-spline co. so˙’. 66 . 2.4.5 Su˙’ du. ng c´acknot bˆo.i 71 2.4.6 Vector knot chuˆa˙’n 73 2.5 C´act´ınhchˆa´t cu˙’a d¯u.`o.ng cong B-spline . . . . . . . . . . . . . . . . . . . . . 75 . . 2.6 Nˆo.i suy c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n bˇa`ng d¯u`ong cong B-spline . . . . . . . . . . . . 77 2.7 Thiˆe´t kˆe´ c´acmˇa.t Bezier v`aB-spline . . . . . . . . . . . . . . . . . . . . . . . 80 2.7.1 Patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.7.2 D´anc´acpatch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 2.7.3 Patch spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 . . 3 Giao cu˙’a c´acd¯ˆo´i tuo. ng 83 3.1 Mo˙’. d¯ˆa`u 83 3.2 Giao cu˙’a hai d¯oa.n thˇa˙’ng 83 3.2.1 Phˆant´ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4
3.2.2 Thuˆa.t to´anx´acd¯i.nh giao hai d¯oa.n thˇa˙’ng . . . . . . . . . . . . . . . . 86 . 3.3 D- oa.n thˇa˙’ng v`ah`ınhch˜u nhˆa.t 87 . . 3.3.1 T`ımgiao bˇa`ng c´ach gia˙’i hˆe. c´acphuong tr`ınh. . . . . . . . . . . . . . 89 3.3.2 Thuˆa.t to´anchia nhi. phˆan . . . . . . . . . . . . . . . . . . . . . . . . 89 3.3.3 Thuˆa.t to´anCohen-Sutherland . . . . . . . . . . . . . . . . . . . . . . 93 3.3.4 Thuˆa.t to´anLiang-Barsky . . . . . . . . . . . . . . . . . . . . . . . . 97 3.4 Giao cu˙’a d¯oa.n thˇa˙’ng v`ad¯agi´aclˆo`i . . . . . . . . . . . . . . . . . . . . . . . 100 . . . . . 3.4.1 Vi. tr´ıtuong d¯ˆo´i cu˙’a mˆo.t d¯iˆe˙’m v´oi d¯u`ong thˇa˙’ng . . . . . . . . . . . . 100 3.4.2 Thuˆa.t to´ant`ımgiao cu˙’a d¯oa.n thˇa˙’ng v`ad¯agi´aclˆo`i . . . . . . . . . . 102 3.5 Giao hai d¯agi´ac. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 3.5.1 Thuˆa.t to´anSutherland-Hodgman . . . . . . . . . . . . . . . . . . . . 108 3.5.2 Thuˆa.t to´anWeiler-Atherton . . . . . . . . . . . . . . . . . . . . . . . 111 . 3.5.3 C´acph´epto´antˆa.p ho. p trˆenc´acd¯agi´ac . . . . . . . . . . . . . . . . 113 3.6 Ray tracing hai chiˆe` u: pha˙’n xa. trong buˆo`ng k´ın . . . . . . . . . . . . . . . . 114 3.6.1 Vector pha˙’n xa. 115 3.6.2 Giao cu˙’a tia s´angv`ad¯u.`o.ng thˇa˙’ng . . . . . . . . . . . . . . . . . . . 117 3.6.3 Giao cu˙’a tia s´angv´o.i d¯u.`o.ng tr`on . . . . . . . . . . . . . . . . . . . . 121 . 3.6.4 Xˆaydu. ng v´ıdu. ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124 3.6.5 Buˆo`ng k´ınl`aellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 4 Tˆom`auv`ung 127 4.1 C´acd¯i.nh ngh˜ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 . 4.1.1 V`ungd¯i.nh ngh˜ıabo˙’ i pixel . . . . . . . . . . . . . . . . . . . . . . . . 127 5
. 4.1.2 V`ungd¯i.nh ngh˜ıabo˙’ i d¯agi´ac. . . . . . . . . . . . . . . . . . . . . . . 129 4.2 Thuˆa.t to´antˆom`autheo vˆe´t dˆa`u loang . . . . . . . . . . . . . . . . . . . . . 129 4.3 Thuˆa.t to´antˆom`autheo con cha.y . . . . . . . . . . . . . . . . . . . . . . . . 131 4.4 Thuˆa.t to´antˆom`autheo biˆen . . . . . . . . . . . . . . . . . . . . . . . . . . 134 4.5 So s´anhc´acthuˆa.t to´an. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 . 4.6 Tˆom`auc´ach`ınhch˜u nhˆa.t 145 4.7 Thuˆa.t to´antˆom`aud¯agi´ac. . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 4.7.1 C´acd`ongqu´etngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 4.7.2 C´acma˙’nh vu. n 151 4.7.3 Liˆenkˆe´t ca.nh v`athuˆa.t to´antr`an . . . . . . . . . . . . . . . . . . . . 151 4.7.4 Tˆom`auc´acd¯agi´acchˆo`ng nhau . . . . . . . . . . . . . . . . . . . . . 158 4.8 Tˆom`autheo mˆa˜u tˆo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 . Phˆa` n phu. lu. c: Thu viˆe.n graph2D.h 163 T`ailiˆe.u tham kha˙’o 171 6
L`o.i n´oid¯ˆa` u . . D- `ˆo ho.a m´ayt´ınhl`amˆo.t l˜ınhvu. c hˆa´p dˆa˜n cu˙’a khoa ho.c m´ayt´ınh.Ch´ungta su˙’ du. ng d¯ˆo` ho.a . . m´ayt´ınhnhu mˆo.t cˆongcu. d¯ˆe˙’ quan s´atthˆongtin trong nhiˆe` u l˜ınhvu. c kh´acnhau, bao gˆo`m . . . . khoa ho.c v`acˆongnghˆe., ho´aho.c, kiˆe´n tr´ucv`agia˙’i tr´ı. C´acchuong tr`ınhd¯ˆo` ho.a tuong t´ac . . . . . . . cho ph´epngu`oi su˙’ du. ng l`amviˆe.c theo c´ach tu. nhiˆennhˆa´t: ngu`oi su˙’ du. ng cung cˆa´p thˆong . . . tin cho tr`ınh´ung du. ng thˆongqua c´achoa.t d¯ˆo.ng bˆenngo`aicu˙’a ho. v`as˜enhˆa.n d¯uo. c thˆong . . . tin tro˙’ la.i bˇa`ng h`ınha˙’nh. D- `ˆo ho.a m´ayt´ınhd¯anggi´upcon ngu`oi thay d¯ˆo˙’i vˆe` quan niˆe.m v`a . . c´ach th´uc su˙’ du. ng m´ayt´ınh. . Gi´aotr`ınh D- `ˆo ho. a m´ayt´ınhI cung cˆa´p mˆo.t sˆo´ k˜ythuˆa.t co ba˙’n cu˙’a d¯ˆo` ho.a m´ayt´ınh . . . . hai chiˆe` u. (D- `ˆo ho.a m´ayt´ınhba chiˆe` u, mˆo.t phˆa`n quan tro.ng khˆongthˆe˙’ thiˆe´u d¯uo. c s˜ed¯uo. c . d¯ˆe` cˆa.p trong mˆo.t gi´aotr`ınhkh´ac).D- ˆe˙’ c´omˆo.t khung ca˙’nh to`andiˆe.n v`asˆausˇa´c vˆe` nh˜ung . . . nguyˆenl´yv`athu. c h`anhcu˙’a d¯ˆo` ho.a m´ayt´ınh,xem c´act`ailiˆe.u dˆa˜n [9] v`a[11]. C´acphuong ph´apphˆant´ıch v`athiˆe´t kˆe´ c´acthuˆa.t to´antrong gi´aotr`ınhcho ph´epsinh viˆenc´othˆe˙’ viˆe´t . . . . . . dˆe˜ d`angc´acchuong tr`ınhminh ho.a. Gi´aotr`ınhd¯uo. c biˆensoa.n cho c´acd¯ˆo´i tuo. ng l`asinh viˆenTo´an-Tinv`aTin ho.c. . . Gi´aotr`ınhsu˙’ du. ng ngˆonng˜u C d¯ˆe˙’ minh ho.a, tuy nhiˆenc´othˆe˙’ dˆe˜ d`angchuyˆe˙’n d¯ˆo˙’i . . . sang c´acngˆonng˜u kh´ac;v`ado d¯´o,sinh viˆencˆa`n c´omˆo.t sˆo´ kiˆe´n th´uc vˆe` ngˆonng˜u C. Ngo`ai . . . . ra, hˆa`u hˆe´t c´acchuong tr`ınhthao t´actrˆencˆa´u tr´ucd˜u liˆe.u nhu danh s´ach liˆenkˆe´t, nˆend¯`oi . ho˙’i sinh viˆenpha˙’i c´onh˜ung k˜ynˇanglˆa.p tr`ınhtˆo´t. . . . Sinh viˆenc˜ungcˆa`n c´oco so˙’ to´anho.c cu˙’a nh˜ung nˇamd¯ˆa`u d¯a.i ho.c: hiˆe˙’u biˆe´t vˆe` d¯a.i sˆo´ tuyˆe´n t´ınhv`ah`ınhho.c gia˙’i t´ıch, ph´ept´ınhvi t´ıch phˆan. . . . Mu. c d¯´ıch cu˙’a gi´aotr`ınhl`a,o˙’ m´uc d¯ˆo. n`aod¯´o,cho thˆa´y c´actr`ınh´ung du. ng d¯ˆo` ho.a . . . . . . d¯uo. c ta.o ra nhu thˆe´ n`ao: Ch´ungta cˆa`n viˆe´t v`acha.y thu˙’ c´acchuong tr`ınh. Mˆo.t trong . . . . . . nh˜ung mu. c d¯´ıch ch´ınhcu˙’a gi´aotr`ınhl`agi´upsinh viˆennˇa´m v˜ung c´acphuong ph´ap,tru´oc . . hˆe´t to´anho.c ho´ac´ackh´acniˆe.m h`ınhho.c v`asau d¯´ochuyˆe˙’n ta˙’i th`anhc´acd¯oa.n m˜achuong tr`ınh. 7
. . . . . Gi´aotr`ınhbao gˆo`m bˆo´n chuong v`amˆo.t phˆa`n phu. lu. c v´oi nh˜ung nˆo.i dung ch´ınhnhu sau: . . . . . . • Chuong th´u nhˆa´t d¯ˆe` cˆa.p d¯ˆe´n c´acphuong ph´apv˜ec´ac“nguyˆenso” cu˙’a d¯ˆo` ho.a m´ay . . t´ınh:d¯oa.n thˇa˙’ng, d¯u`ong tr`onv`aellipse. . . • Phˆant´ıch v`athiˆe´t kˆe´ bˇa`ng h`ınhho.c l`anˆo.i dung ch´ınhcu˙’a Chuong 2. Hˆa`u hˆe´t c´ac . . . . . phˆa`n mˆe` m d¯ˆo` ho.a d¯ˆe` u c´onh˜ung ch´uc nˇangta.o ra c´acd¯u`ong cong du. a trˆenc´acd¯iˆe˙’m . . . . . . . m`angu`oi su˙’ du. ng lu. a cho.n. Chuong n`aycung cˆa´p nh˜ung nguyˆenl´yv`ac´ach tiˆe´p cˆa.n . . thu. c h`anhm`ac´actr`ınh´ung du. ng d¯ˆo` ho.a ´apdu. ng. . . . . • Chuong 3 gia˙’i quyˆe´t b`aito´anx´acd¯i.nh giao cu˙’a nh˜ung nguyˆenso d¯ˆo` ho.a: Giao hai . d¯oa.n thˇa˙’ng, giao cu˙’a d¯oa.n thˇa˙’ng v`ad¯agi´aclˆo`i (bao h`amc´ach`ınhch˜u nhˆa.t) v`agiao . . cu˙’a hai d¯agi´ac. Cuˆo´i chuong l`amˆo.t v´ıdu. cu˙’a k˜ythuˆa.t “ray tracing” hai chiˆe` u: . . . Chuyˆe˙’n d¯ˆo.ng cu˙’a tia s´angtrong buˆo`ng k´ınc´och´ua c´ac“chu´ong nga.i vˆa.t”. . . . . • Chuong 4 d¯ˆe` cˆa.p d¯ˆe´n nh˜ung thuˆa.t to´antˆom`auv`ungbˆa´t k`y:V`ungd¯i.nh ngh˜ıabo˙’ i phˆa`n trong, bo˙’.i d¯u.`o.ng biˆenv`av`ungl`ad¯agi´ac. . . . . • Phˆa`n phu. lu. c l`athu viˆe.n c´accˆa´u tr´ucd˜u liˆe.u v`ac´ach`amcˆa`n thiˆe´t v`athu`ong xuyˆen . su˙’ du. ng trong gi´aotr`ınh. . . Trong lˆa`n xuˆa´t ba˙’n th´u hai n`ay, ch´ungtˆoid¯ua thˆemc´acv´ıdu. t´ınhto´annhˇa`m minh . . . ho.a cho phˆa`n l´ythuyˆe´t c˜ungnhu gi´upsinh viˆennˇa´m v˜ung kiˆe´n th´uc d¯˜aho.c. Ngo`aira, c´ac . . . . . lˆo˜i trong xuˆa´t ba˙’n lˆa`n tru´oc c˜ungd¯˜ad¯uo. c chı˙’nh l´y;mˇa.c d`uvˆa.y, t´acgia˙’ vˆa˜n mong c´onh˜ung . d¯´ongg´opt`u ba.n d¯o.c. . . . . . . . . Tˆoixin ca˙’m on nh˜ung gi´upd¯˜o d¯˜anhˆa.n d¯uo. c t`u nhiˆe` u ngu`oi m`akhˆongthˆe˙’ liˆe.t kˆe hˆe´t, d¯ˇa.c biˆe.t l`ac´acba.n sinh viˆen,trong qu´atr`ınhbiˆensoa.n gi´aotr`ınhn`ay. D- `aLa.t, ng`ay10 th´ang1 nˇam2005 . PHA. M Tiˆe´n Son 8
Chu.o.ng 1 . . C´acthuˆa.t to´anv˜ed¯u`ong cong trˆen thiˆe´t bi. raster . . . . Chuong n`aytr`ınhb`ayc´acthuˆa.t to´anv˜ed¯oa.n thˇa˙’ng, d¯u`ong tr`onv`aellipse trˆenlattice 2 . . nguyˆen Z . C´acthuˆa.t to´anchı˙’ thao t´actrˆennh˜ung sˆo´ nguyˆenv`atrong c´acv`onglˇa.p chı˙’ su˙’ du. ng ph´epto´ancˆo.ng nˆenrˆa´t hiˆe.u qua˙’. 1.1 D- oa.n thˇa˙’ng . Thuˆa.t to´anv˜ed¯oa.n thˇa˙’ng x´acd¯i.nh to.a d¯ˆo. cu˙’a c´acpixel nˇa`m trˆenhoˇa.c gˆa`n v´oi d¯oa.n thˇa˙’ng . . . thu. c tˆe´ nhˆa´t. Vˆe` nguyˆentˇa´c, ch´ungta muˆo´n cho.n d˜ayc´acpixel gˆa`n v´oi d¯oa.n thˇa˙’ng thu. c tˆe´ . . . . nhˆa´t v`athˇa˙’ng nhˆa´t. X´etd¯oa.n thˇa˙’ng thu. c tˆe´ d¯uo. c xˆa´p xı˙’ v´oi mˆa.t d¯ˆo. mˆo.t pixel; ta cˆa`n c´o . . nh˜ung t´ınhchˆa´t g`ı?V´oi c´acd¯oa.n thˇa˙’ng c´ohˆe. sˆo´ g´octhuˆo.c d¯oa.n [−1, 1], c´od¯´ungmˆo.t pixel . . . d¯uo. c v˜elˆentrˆenmˆo˜i cˆo.t; v´oi c´acd¯oa.n thˇa˙’ng m`ahˆe. sˆo´ g´ocnˇa`m ngo`aid¯oa.n n`ay, c´od¯´ung . . . . . mˆo.t pixel d¯uo. c v˜etrˆenmˆo˜i h`ang.Tˆa´t ca˙’ c´acd¯oa.n thˇa˙’ng d¯uo. c v˜ev´oi c`ungmˆo.t d¯ˆo. s´ang, . . . . khˆongphu. thuˆo.c v`aod¯ˆo. d`aiv`ahu´ong, v`anhanh nhˆa´t c´othˆe˙’ d¯uo. c. Thuˆa.t to´anv˜ed¯oa.n . thˇa˙’ng c˜ungcˆa`n ch´u´yd¯ˆe´n c´acthuˆo.c t´ınhcu˙’a d¯oa.n thˇa˙’ng nhu d¯ˆo. rˆo.ng, kiˆe˙’u v˜e Thˆa.m ch´ı . . . . . . . ch´ungta muˆo´n cu. c tiˆe˙’u ho´am´uc d¯ˆo. rˇangcua do tiˆe´n tr`ınhr`oi ra.c ho´ad¯u`ong thˇa˙’ng thu. c . . . . tˆe´ nh`o su˙’ du. ng k˜ythuˆa.t antialiasing (xem [9], [11]) bˇa`ng c´ach ´apdu. ng kha˙’ nˇangd¯ˇa.t cu`ong . . . d¯ˆo. cu˙’a mˆo˜i pixel trˆenc´acthiˆe´t bi. hiˆe˙’n thi. m`amˆo.t pixel tuong ´ung nhiˆe` u bit. . . Tru´oc hˆe´t ch´ungta chı˙’ d¯ˆe` cˆa.p d¯ˆe´n c´acd¯oa.n thˇa˙’ng d¯ˆo. rˆo.ng mˆo.t pixel v`ac´od¯´ungmˆo.t . . . pixel trˆenmˆo˜i cˆo.t (hoˇa.c h`angd¯ˆo´i v´oi c´acd¯oa.n thˇa˙’ng dˆo´c). Phˆa`n cuˆo´i chuong s˜ed¯ˆe` cˆa.p 9
. d¯ˆe´n d¯ˆo. rˆo.ng c´acnguyˆenso v`ac´acmˆa˜u v˜e. . . Mˆo.t c´ach h`ınhho.c, ch´ungta biˆe˙’u diˆe˜n mˆo.t pixel nhu mˆo.t chˆa´m tr`onv´oi tˆamta.i vi. . . 2 . tr´ı(x, y) cu˙’a pixel trˆenlu´oi c´acto.a d¯ˆo. nguyˆen Z . Biˆe˙’u diˆe˜n n`ayl`amˆo.t xˆa´p xı˙’ th´ıch ho. p nh´atcˇa´t ngang trong mˆo.t chu k`ycu˙’a ch`umtia electron cu˙’a CRT; xˆa´p xı˙’ n`ayphu. thuˆo.c v`ao . khoa˙’ng c´ach (tu`ythuˆo.c v`aohˆe. thˆo´ng) gi˜ua c´acvˆe´t trˆenm`anh`ınhhiˆe˙’n thi Trong mˆo.t sˆo´ . . . hˆe. thˆo´ng, c´acchˆa´m kˆe` nhau phu˙’ lˆa´p mˆo.t phˆa`n lˆennhau; v´oi nh˜ung hˆe. thˆo´ng kh´acc´onh˜ung . . khoa˙’ng c´ach gi˜ua c´acpixel d¯´ung kˆe` nhau; trong hˆa`u hˆe´t c´achˆe. thˆo´ng, khoa˙’ng c´ach theo . . . chiˆe` u ngang nho˙’ hon theo chiˆe` u d¯´ung. Mˆo.t kh´acbiˆe.t n˜ua tu`ytheo hˆe. thˆo´ng trong viˆe.c biˆe˙’u . . . diˆe˜n hˆe. to.a d¯ˆo., chˇa˙’ng ha.n Macintosh xem c´acpixel d¯uo. c d¯ˇa.t ta.i tˆamcu˙’a h`ınhch˜u nhˆa.t gi˜u.a c´acd¯u.`o.ng thˇa˙’ng kˆe` nhau cu˙’a lu.´o.i d¯iˆe` u khiˆe˙’n thay cho nˇa`m trˆenc´acd¯u.`o.ng thˇa˙’ng cu˙’a . . . . lu´oi. Theo c´ach n`ay, c´ach`ınhch˜u nhˆa.t (x´acd¯i.nh bo˙’ i hai g´oc)gˆo`m c´acpixel thuˆo.c phˆa`n . . trong cu˙’a n´o.D- .inh ngh˜ıan`aycho ph´epc´acv`ungd¯ˆo. rˆo.ng bˇa`ng khˆong:H`ınhch˜u nhˆa.t t`u . . . (x, y) d¯ˆe´n (x, y) khˆongch´ua pixel n`ao,trong khi v´oi nh˜ung hˆe. thˆo´ng kh´ac,c´od¯´ungmˆo.t . . . . pixel ta.i d¯iˆe˙’m n`ay. Du´oi d¯ˆaych´ungta s˜ebiˆe˙’u diˆe˜n c´acpixel nhu c´ach`ınhtr`onr`oi nhau c´o tˆamnˇa`m trˆenlu.´o.i. . . . H`ınh1.1 l`aph´ongto cu˙’a d¯u`ong thˇa˙’ng thu. c tˆe´ v`axˆa´p xı˙’ d¯ˆo. rˆo.ng mˆo.t pixel cu˙’a n´o. . . . . . . . . . . C´acpixel d¯uo. c v˜etuong ´ung c´ach`ınhtr`onm`aud¯env`ac´acpixel khˆongd¯uo. c v˜etuong ´ung . . . . h`ınhtr`onkhˆongtˆo.Trˆenm`anh`ınhthu. c tˆe´, d¯u`ong k´ınhcu˙’a h`ınhtr`onbiˆe˙’u diˆe˜n pixel l´on . . . hon khoa˙’ng c´ach gi˜ua c´acpixel kˆe` nhau, bo˙’ i vˆa.y biˆe˙’u diˆe˜n bˇa`ng k´yhiˆe.u cu˙’a ch´ungta l`a . . mˆo.t ph´ongd¯a.i m´uc d¯ˆo. r`oi ra.c cu˙’a c´acpixel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .i. i. i. i. i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i. i. i.y i . yi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i. iy . iy . i. i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .iy . i. i. i. i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H`ınh1.1: D- oa.n thˇa˙’ng xˆa´p xı˙’ d¯uo. c biˆe˙’u diˆe˜n bo˙’ i c´ach`ınhtr`ond¯en. . . . V`ıc´acnguyˆenso trong hˆe. thˆo´ng ch´ungta x´acd¯i.nh trˆenlu´oi d¯iˆe` u khiˆe˙’n nguyˆennˆen . c´acto.a d¯ˆo. d¯ˆa`u cuˆo´i cu˙’a d¯oa.n thˇa˙’ng l`anguyˆen.Thˆa.t ra, nˆe´u ch´ungta cˇa´t d¯oa.n thˇa˙’ng v´oi . . . h`ınhch˜u nhˆa.t tru´oc khi hiˆe˙’n thi. n´oth`ıto.a d¯ˆo. c´acd¯iˆe˙’m d¯ˆa`u cuˆo´i cu˙’a d¯oa.n thˇa˙’ng c´othˆe˙’ khˆongnguyˆen.(Ch´ungta s˜etha˙’o luˆa.n c´acgiao d¯iˆe˙’m khˆongnguyˆentrong Phˆa`n 1.1.3). Gia˙’ 10
. . . . . . . . . . . . su˙’ d¯oa.n thˇa˙’ng c´ohˆe. sˆo´ g´oc |m| ≤ 1; c´actru`ong ho. p kh´acd¯uo. c xu˙’ l´ytuong tu. . Hon n˜ua . . . . . . tru`ong ho. p c´acd¯oa.n thˇa˙’ng ngang, d¯´ung hoˇa.c c´ohˆe. sˆo´ g´oc ±1 l`atˆa`m thu`ong v`ıch´ungchı˙’ d¯iqua c´acpixel trˆenlu.´o.i. 1.1.1 Thuˆa.t to´ansˆo´ gia . 2 . . X´ethai pixel A = (xA, yA) v`a B = (xB, yB) (t´ucc´acphˆa`n tu˙’ cu˙’a lattice nguyˆen Z ). Phuong . . tr`ınhd¯u`ong thˇa˙’ng AB c´oda.ng y = mx + t, trong d¯´ohˆe. sˆo´ g´oc m = dy/dx v`a t = yA − mxA. . C´ach d¯on gia˙’n nhˆa´t d¯ˆe˙’ v˜ed¯oa.n thˇa˙’ng AB l`a: 1. T´ınhhˆe. sˆo´ g´oc m; . . . . 2. Tˇang x mˆo.t d¯on vi. (kho˙’ i d¯ˆa`u t`u d¯iˆe˙’m bˆentr´ainhˆa´t), v´oi mˆo˜i xi t´ınh yi = mxi + t v`a 1 sau d¯´ov˜epixel ta.i (xi, byi + 0.5c) . . . . . Theo c´ach n`ayta cho.n pixel tˆo´t nhˆa´t, t´uc l`apixel m`akhoa˙’ng c´ach d¯ˆe´n d¯u`ong thˇa˙’ng thu. c . . . . tˆe´ nho˙’ nhˆa´t. Phuong ph´apn`aykhˆonghiˆe.u qua˙’ do mˆo˜i bu´oc lˇa.p cˆa`n t´ınhmˆo.t ph´epnhˆan, . mˆo.t ph´epcˆo.ng v`amˆo.t ph´epto´anl`amtr`on.Ta c´othˆe˙’ khu˙’ ph´epnhˆanbˇa`ng c´ach ch´u´yrˇa`ng yi+1 = mxi+1 + t = m(xi + ∆x) + t = yi + m∆x, . . v`anˆe´u bu´oc tˇang∆x = 1 th`ı yi+1 = yi + m. . . . Do d¯´onˆe´u x tˇangmˆo.t d¯on vi. th`ı y tˇang m d¯on vi V´oi mo.i d¯iˆe˙’m (xi, yi) trˆend¯oa.n . . . thˇa˙’ng ta biˆe´t rˇa`ng nˆe´u xi+1 = xi + 1 th`ı yi+1 = yi + m; t´uc l`a,c´acgi´atri. x v`a y d¯uo. c t´ınh . . . theo c´acgi´atri. tru´oc d¯´ocu˙’a n´o(xem H`ınh1.2). D- ˆaych´ınhl`a“thuˆa.t to´ansˆo´ gia”: v´oi mˆo˜i . . . . . . . . bu´oc lˇa.p ta thu. c hiˆe.n c´acph´epto´ansˆo´ gia du. a trˆenbu´oc tru´oc. . Kho˙’ i ta.o ta g´an(x0, y0) l`ato.a d¯ˆo. nguyˆencu˙’a d¯iˆe˙’m xuˆa´t ph´at,chˇa˙’ng ha.n A. Ch´u´y . . . . . . rˇa`ng trong tru`ong ho. p |m| > 1 nˆe´u x tˇangmˆo.t d¯on vi. th`ı y tˇanghon mˆo.t d¯on vi Do d¯´o . . . cˆa`n ho´and¯ˆo˙’i vai tr`ocu˙’a x v`a y bˇa`ng c´ach g´anbu´oc tˇangmˆo.t d¯on vi. cho y v`atˇang x mˆo.t . . ∆y 1 luo. ng ∆x = m = m . 1 . . . K´yhiˆe.u [x], bxc v`a dxe tuong ´ung l`aphˆa`n nguyˆen,l`amtr`onxuˆo´ng v`al`amtr`onlˆencu˙’a x. 11
. . . . . . . . . . . . - . . . . . . Du`ong thˇa˙’ng . . . . . . . . . . . . . . . . . . . . . thuc tˆe´ . . . . . . . . . . . . . . . . . . . . . . . w. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (xi + 1, dyi + me) . . . . . . . . . . . . . . w. w. . . . . . . . . . . . . . . . . . . (x , y ) . . . i i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . w. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (xi, byic) (xi + 1, yi + m) H`ınh1.2: T´ınhto´ansˆo´ gia cu˙’a (xi, yi). . . . V´ıdu. 1.1.1 Gia˙’ su˙’ A(2, 0),B(9, 3). Khi d¯´od¯u`ong thˇa˙’ng qua hai d¯iˆe˙’m A v`a B c´ohˆe. sˆo´ 3 ´ ´ . . ˙’ ´ ´ . g´oc m = 7 ∈ (0, 1). Ap du. ng thuˆa.t to´ansˆo gia ta d¯uo. c d˜ayc´acd¯iˆem v˜etˆot nhˆat nhu trong ba˙’ng du.´o.i: i xi yi byi + 0.5c 0 2 0 0 3 1 3 7 0 6 2 4 7 1 9 3 5 7 1 12 4 6 7 2 15 5 7 7 2 18 6 8 7 3 21 7 9 7 3 . . . Thu˙’ tu. c Line() du´oi d¯ˆayminh ho.a thuˆa.t to´anv˜ed¯oa.n thˇa˙’ng t`u (x0, y0) d¯ˆe´n (x1, y1) . . . . . v´oi gi´atri. m`au V alue. D- iˆe˙’m kho˙’ i d¯ˆa`u l`ad¯iˆe˙’m bˆentr´ainhˆa´t. Ngo`aira ta chı˙’ x´ettru`ong ho. p . . . . . . . −1 ≤ m ≤ 1 v`ıc´actru`ong ho. p kh´acc´othˆe˙’ thu. c hiˆe.n do t´ınhd¯ˆo´i x´ung. Hon n˜ua, ch´ungta . . . . . . c˜ungbo˙’ qua viˆe.c kiˆe˙’m tra c´actru`ong ho. p d¯ˇa.c biˆe.t: d¯u`ong thˇa˙’ng nˇa`m ngang, d¯´ung, xiˆen 0 . mˆo.t g´oc ±45 . Ch´u´yrˇa`ng, trong ngˆonng˜u C, (int)y bˇa`ng by + 0.5c. void Line(int x_A, int y_A, int x_B, int y_B, int Value) { 12
int x; int dx, dy; float y, m; dx = x_B - x_A; dy = y_B - y_A; m = dy/(float)dx; y = y0; for (x = x_A; x <= x_B; x ++) { putpixel(x, (int)(y), Value); y += m; } } . 1.1.2 Thuˆa.t to´and¯iˆe˙’m gi˜ua . . Thu˙’ tu. c Line() thao t´actrˆenc´acsˆo´ thu. c y v`a m. Bresenham d¯˜axˆaydu. ng thuˆa.t to´an[2] v˜e . d¯oa.n thˇa˙’ng chı˙’ su˙’ du. ng c´acph´epto´antrˆensˆo´ nguyˆendo d¯´otr´anhgo.i h`aml`amtr`onv`acho . . . . . . . ph´epx´acd¯i.nh (xi+1, yi+1) theo sˆo´ gia du. a trˆennh˜ung gi´atri. o˙’ bu´oc tru´oc (xi, yi). Thuˆa.t . . . . . . . to´ann`ayc´othˆe˙’ mo˙’ rˆo.ng da.ng dˆa´u chˆa´m d¯ˆo.ng d¯ˆo´i v´oi c´acto.a d¯ˆo. thu. c. Hon n˜ua, phuong . . . . ph´apcu˙’a Bresenham c´othˆe˙’ d¯uo. c ´apdu. ng t´ınhto´antrˆensˆo´ nguyˆenv˜ed¯u`ong tr`onmˇa.c d`u . . . . . . n´okhˆongdˆe˜ d`angmo˙’ rˆo.ng cho conic tu`y´y.V`ıvˆa.y ch´ungta su˙’ du. ng phuong ph´aptuong . . . . . . d¯ˆo´i kh´ac, thuˆa. t to´and¯iˆe˙’m gi˜ua, d¯uo. c cˆongbˆo´ lˆa`n d¯ˆa`u tiˆenbo˙’ i Pitteway [16], [17] v`ad¯uo. c . . ca˙’i tiˆe´n bo˙’ i Van Aken [26] v`amˆo.t sˆo´ t´acgia˙’ kh´ac[28], [29]. Van Aken d¯˜achı˙’ ra [26] d¯ˆo´i v´oi . . . . . . . . . c´acd¯u`ong thˇa˙’ng v`ad¯u`ong tr`onv´oi d˜u liˆe.u nguyˆen,cˆongth´uc d¯iˆe˙’m gi˜ua suy ra cˆongth´uc cu˙’a Bresenham v`ado d¯´osinh ra c`ungd˜ayc´acpixel. . . . Khˆongmˆa´t t´ınhtˆo˙’ng qu´at,gia˙’ su˙’ hˆe. sˆo´ g´oc m cu˙’a d¯u`ong thˇa˙’ng thuˆo.c khoa˙’ng (0, 1) . . . . . . . . . (c´actru`ong ho. p kh´acc´othˆe˙’ d¯uo. c xu˙’ l´ybo˙’ i c´acph´eplˆa´y d¯ˆo´i x´ung mˆo.t c´ach th´ıch ho. p qua c´actru. c to.a d¯ˆo.). Ta c˜ungk´yhiˆe.u d¯iˆe˙’m xuˆa´t ph´atl`a(xA, yA) v`ad¯iˆe˙’m kˆe´t th´ucl`a(xB, yB). . . . . D- ˇa.t dy := yB − yA, dx = xB − xA. Phuong tr`ınhd¯u`ong thˇa˙’ng l qua hai d¯iˆe˙’m A v`a B x´ac . d¯i.nh bo˙’ i dy y = x + t; dx 13
D w − (l ) M Q w w C R (l+) l . . H`ınh1.3: Lu´oi c´acpixel v`avi. tr´ıd¯iˆe˙’m C, R, D, Q v`a M. hay tu.o.ng d¯u.o.ng f(x, y) := ax + by + c = 0, . . trong d¯´o a = dy, b = −dx, v`a c = b ì dx. K´yhiˆe.u c´ac nu˙’ a mˇa. t phˇa˙’ng ngo`ai v`a nu˙’ a mˇa. t . . . . . phˇa˙’ng trong x´acd¯i.nh bo˙’ i l tuong ´ung bo˙’ i (l+) := {(x, y) ∈ R2 | f(x, y) > 0}, (l−) := {(x, y) ∈ R2 | f(x, y) < 0}. ´ . . . . Y tuo˙’ ng cu˙’a thuˆa.t to´and¯iˆe˙’m gi˜ua l`axˆaydu. ng mˆo.t d˜ayc´acd¯iˆe˙’m v˜e“tˆo´t nhˆa´t” (xi, yi) . . . . . bˇa´t d¯ˆa`u t`u d¯iˆe˙’m (x0, y0) = (xA, yA). Kh´ainiˆe.m tˆo´t nhˆa´t o˙’ d¯ˆayl`anh˜ung d¯iˆe˙’m (xi, yi) d¯uo. c . . . . cho.n gˆa`n v´oi d¯u`ong thˇa˙’ng thu. c tˆe´ (da.ng liˆentu. c) nhˆa´t. Theo gia˙’ thiˆe´t, 0 < m < 1, nˆenkhi . . . x tˇangmˆo.t luo. ng ∆x th`ı y tˇangkhˆongqu´a∆y = m∆x d¯on vi . . . . . . . . . V`ıvˆa.y nˆe´u bu´oc th´u i cho.n d¯uo. c d¯iˆe˙’m v˜etˆo´t nhˆa´t C := (xi, yi) th`ıo˙’ bu´oc th´u i + 1 ta s˜echo.n d¯iˆe˙’m v˜e(xi+1, yi+1), trong d¯´o xi+1 = xi + 1 v`a yi+1 = yi hoˇa.c yi+1 = yi + 1. . . . N´oic´ach kh´ac,bu´oc th´u i + 1 ch´ungta s˜echo.n mˆo.t trong hai pixel R := (xi + 1, yi) hoˇa.c . . D := (xi + 1, yi + 1) (xem H`ınh1.3). K´yhiˆe.u Q l`agiao d¯iˆe˙’m cu˙’a hai d¯u`ong thˇa˙’ng l v`a . . . . x = xi + 1. Theo Bresenham, dˆa´u cu˙’a biˆe˙’u th´uc x´acd¯i.nh bo˙’ i hiˆe.u gi˜ua hai khoa˙’ng c´ach t`u . . . . R v`a D d¯ˆe´n Q cho ph´epx´acd¯i.nh pixel tˆo´t nhˆa´t o˙’ bu´oc i + 1. Trong thuˆa.t to´and¯iˆe˙’m gi˜ua, . . . . . ta quan s´atvi. tr´ıcu˙’a d¯iˆe˙’m gi˜ua M v`ac´acnu˙’ a mˇa.t phˇa˙’ng x´acd¯i.nh bo˙’ i d¯u`ong thˇa˙’ng l. Dˆe˜ d`angchı˙’ ra rˇa`ng, nˆe´u M ∈ (l+) th`ıpixel D gˆa`n v´o.i d¯u.`o.ng thˇa˙’ng l ho.n; nˆe´u M ∈ (l−) th`ı . . . pixel R gˆa`n hon. D- u`ong thˇa˙’ng l c´othˆe˙’ d¯ingang qua M; hoˇa.c ca˙’ hai pixel nˇa`m vˆe` c`ung . + − . . . . . mˆo.t nu˙’ a mˇa.t phˇa˙’ng (l ) (hoˇa.c (l )) nhung trong bˆa´t c´u tru`ong ho. p n`ao,ta vˆa˜n cho.n d¯iˆe˙’m . . . . . . . . . gˆa`n v´oi l nhˆa´t. Hon n˜ua, sai sˆo´-t´uc l`akhoa˙’ng c´ach gi˜ua pixel d¯uo. c cho.n v`ad¯u`ong thˇa˙’ng . . thu. c tˆe´ l-luˆonluˆonnho˙’ hon hoˇa.c bˇa`ng 1/2. 14
- ˙’ ˙’ . ˙’ ` 1 ˙’ Dˆe ´apdu. ng thuˆa.t to´and¯iˆem gi˜ua, chı cˆan t´ınh f(M) = f(xi + 1, yi + 2 ) v`akiˆem tra dˆa´u cu˙’a n´o.Do d¯´ota d¯i.nh ngh˜ıa biˆe´n quyˆe´t d¯i.nh 1 di := f(xi + 1, yi + 2 ) 1 = a(xi + 1) + b(yi + 2 ) + c. Khi d¯´o 1. Nˆe´u di > 0 cho.n pixel D; 2. Nˆe´u di < 0 cho.n pixel R; 3. Nˆe´u di = 0 cho.n mˆo.t trong hai pixel R hoˇa.c D, do d¯´ocho.n R. . . . . Kˆe´ tiˆe´p ta cˆa`n x´acd¯i.nh to.a d¯ˆo. d¯iˆe˙’m gi˜ua M v`ado d¯´obiˆe´n quyˆe´t d¯i.nh di+1 o˙’ bu´oc i + 1; d˜ınhiˆend¯iˆe` u n`ayphu. thuˆo.c v`aoviˆe.c cho.n pixel R hoˇa.c D. Nˆe´u cho.n R th`ıho`anhd¯ˆo. d¯iˆe˙’m . M tˇangmˆo.t d¯on vi. v`atung d¯ˆo. khˆongd¯ˆo˙’i. Do d¯´o 1 1 d = f(x + 2, y + ) = a(x + 2) + b(y + ) + c. i+1 i i 2 i i 2 Nhu.ng 1 d = a(x + 1) + b(y + ) + c. i i i 2 Suy ra di+1 = di + a. . . . . K´yhiˆe.u sˆo´ gia d¯uo. c cˆo.ng thˆemkhi R d¯uo. c cho.n l`a∆R := a = dy. N´oic´ach kh´ac,ta . . . . . . . c´othˆe˙’ suy ra biˆe´n quyˆe´t d¯i.nh o˙’ bu´oc kˆe´ tiˆe´p t`u biˆe´n quyˆe´t d¯i.nh o˙’ bu´oc hiˆe.n h`anhbˇa`ng c´ach cˆo.ng thˆemsˆo´ gia ∆R m`akhˆongcˆa`n pha˙’i t´ınhla.i gi´atri. f(M). . Nˆe´u cho.n D th`ıho`anhd¯ˆo. v`atung d¯ˆo. d¯iˆe˙’m M c`ungtˇangmˆo.t d¯on vi., nˆen 3 3 d = f(x + 2, y + ) = a(x + 2) + b(y + ) + c. i+1 i i 2 i i 2 V`ado d¯´o di+1 = di + a + b. . . K´yhiˆe.u sˆo´ gia d¯uo. c cˆo.ng v`ao di+1 sau khi cho.n D l`a∆D := a + b = dy − dx. . . . . . V`ıo˙’ bu´oc d¯ˆa`u tiˆen,ta cho.n (x0, y0) = (xA, yA) nˆenc´othˆe˙’ t´ınhtru. c tiˆe´p gi´atri. kho˙’ i ˙’ . ` 1 ta.o d0. Thˆa.t vˆa.y, d¯iˆem gi˜ua d¯ˆau tiˆenc´oto.a d¯ˆo. (x0 + 1, y0 + 2 ), v`a 1 1 f(x0 + 1, y0 + 2 ) = a(x0 + 1) + b(y0 + 2 ) + c = ax0 + by0 + c + a + b/2 = f(x0, y0) + a + b/2. 15
. . . . Nhung (x0, y0) thuˆo.c d¯u`ong thˇa˙’ng l nˆen f(x0, y0) = 0; do d¯´ogi´atri. kho˙’ i d¯ˆa`u cu˙’a biˆe´n . . . quyˆe´t d¯i.nh l`a d0 = a + b/2 = dy − dx/2. Su˙’ du. ng d0 ta c´othˆe˙’ cho.n pixel th´u hai, th´u . . ba, v.v. D- ˆe˙’ khu˙’ mˆa˜u sˆo´ trong d0 ta d¯i.nh ngh˜ıala.i h`am f bˇa`ng c´ach nhˆann´ocho 2; t´uc l`a f(x, y) = 2(ax + by + c). N´oic´ach kh´ac,nhˆan2 cho c´achˇa`ng sˆo´ a, b, c v`abiˆe´n quyˆe´t d¯i.nh; . . m`ad¯iˆe` u n`aykhˆonga˙’nh huo˙’ ng d¯ˆe´n dˆa´u cu˙’a biˆe´n quyˆe´t d¯i.nh. . . . . Tˆo˙’ng qu´atho´athuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯oa.n thˇa˙’ng AB (trong tru`ong ho. p xA < xB v`a0 < m < 1) nhu. sau: . 1. [Kho˙’ i ta.o] D- ˇa.t dx = xB − xA, dy = yB − yA, d0 = 2dy − dx, ∆R = 2dy, ∆D = 2(dy − dx), x0 = xA, y0 = yA. . . . . . 2. Gia˙’ su˙’ o˙’ bu´oc th´u i ta c´od¯iˆe˙’m v˜etˆo´t nhˆa´t (xi, yi) v`abiˆe´n quyˆe´t d¯i.nh di. 3. [V˜epixel hiˆe.n h`anh]D- ˇa.t d¯iˆe˙’m v˜eta.i (xi, yi). . . . 4. [Cˆa.p nhˆa.t] Nˆe´u xi = xB, thuˆa.t to´and`ung; nguo. c la.i, d¯ˇa.t x = x + 1; i+1 (i yi nˆe´u di ≤ 0, yi+1 = y + 1 nˆe´u ngu.o.c lai; ( i . . di + ∆R nˆe´u di ≤ 0, di+1 = . . di + ∆D nˆe´u nguo. c la.i. . . 5. Thay i bˇa`ng (i + 1) v`alˇa.p la.i Bu´oc 3. . . . V´ıdu. 1.1.2 Gia˙’ su˙’ A(2, 0),B(9, 3). Khi d¯´od¯u`ong thˇa˙’ng qua hai d¯iˆe˙’m A v`a B c´ohˆe. sˆo´ 3 ˜ ˙’ ` g´oc m = 7 ∈ (0, 1). Dˆe d`angkiˆem tra rˇang dx = xB − xA = 7, dy = yB − yA = 3, d0 = 2dy − dx = −1, ∆R = 2dy = 6, ∆D = 2(dy − dx) = −8. 16
. . . . Ap´ du. ng thuˆa.t to´and¯iˆe˙’m gi˜ua ta c´od˜ayc´acd¯iˆe˙’m v˜etˆo´t nhˆa´t nhu trong ba˙’ng du´oi: i xi yi di 0 2 0 −1 1 3 0 5 2 4 1 −3 3 5 1 3 4 6 2 −5 5 7 2 1 6 8 3 −7 7 9 3 −1 . . . . Hiˆe˙’n nhiˆenrˇa`ng c´ackˆe´t qua˙’ n`aytr`ungv´oi kˆe´t qua˙’ khi su˙’ du. ng phuong ph´apsˆo´ gia trong V´ıdu. 1.1.1. . . . Ch´u´yrˇa`ng, ph´ept´ınhcˆa`n thiˆe´t d¯ˆo´i v´oi di+1 trong mˆo˜i bu´oc lˇa.p l`aph´epcˆo.ng v`akhˆong . . . . c´oph´epnhˆan. Hon n˜ua, v`onglˇa.p ho`anto`and¯on gia˙’n nhu trong thu˙’ tu. c MidPointLine() du.´o.i d¯ˆay: void MidPointLine(int x_A, int y_A, int x_B, int y_B, int Value) { int x, y, d, dx, dy, DeltaR, DeltaD; dx = x_B - x_A; dy = y_B - y_A; d = 2*dy - dx; DeltaR = 2*dy; DeltaD = 2*(dy - dx); y = y_A; for (x = x_A; x <= x_B; x++) { putpixel(x, y, Value); if (d <= 0) d += DeltaR; else { d += DeltaD; 17
y++; } } } 1.1.3 Mˆo.t sˆo´ vˆa´n d¯ˆe` liˆenquan d¯ˆe´n thuˆa.t to´anv˜ed¯oa.n thˇa˙’ng . . . Th´u tu. cu˙’a c´acd¯iˆe˙’m d¯ˆa` u cuˆo´i. Trong mˆo.t ´ung du. ng ta cˆa`n d¯`oiho˙’i mˆo.t d¯oa.n thˇa˙’ng . . . . . . . . d¯uo. c v˜et`u A d¯ˆe´n B ch´ua c`ungtˆa.p c´acpixel nhu d¯oa.n thˇa˙’ng d¯uo. c v˜et`u B d¯ˆe´n A; n´oi . . . . . c´ach kh´ac,d¯oa.n thˇa˙’ng d¯uo. c v˜ekhˆongphu. thuˆo.c v`aoth´u tu. c´acd¯iˆe˙’m d¯ˆa`u cuˆo´i. Su. sai kh´ac . . . . chı˙’ c´othˆe˙’ xa˙’y ra ta.i nh˜ung d¯iˆe˙’m v˜em`ad¯u`ong thˇa˙’ng d¯iqua d¯iˆe˙’m gi˜ua v`abiˆe´n quyˆe´t d¯i.nh . . . . bˇa`ng khˆong;trong tru`ong ho. p n`ay, d¯it`u tr´aisang pha˙’i ch´ungta cho.n d¯iˆe˙’m v˜e R. Do t´ınh . . . . d¯ˆo´i x´ung, khi d¯it`u pha˙’i sang tr´aiv`a d = 0 l˜era ta cho.n d¯iˆe˙’m v˜e R, nhung cho.n lu. a n`ays˜e . . . . . sai lˆe.ch mˆo.t d¯on vi. theo th`anhphˆa`n y v´oi pixel d¯uo. c cho.n khi d¯it`u tr´aisang pha˙’i. Do d¯´o . . . . . . ch´ungta cˆa`n cho.n pixel D khi d¯it`u pha˙’i sang tr´aitrong tru`ong ho. p d = 0. L´yluˆa.n tuong . . tu. d¯ˆo´i v´oi c´acd¯oa.n thˇa˙’ng c´ohˆe. sˆo´ g´ocbˆa´t k`y. . . . Phuong ph´apho´and¯ˆo˙’i c´acd¯iˆe˙’m d¯ˆa`u cuˆo´i cu˙’a d¯oa.n thˇa˙’ng d¯ˆe˙’ thuˆa.t to´anxu˙’ l´ytheo . . . c`unghu´ong khˆongthu. c hiˆe.n ch´ınhx´ackhi ch´ungta v˜ec´acd¯oa.n thˇa˙’ng theo mˆa˜u tˆo.C´ac . . . d¯oa.n thˇa˙’ng v˜etheo mˆa˜u thu`ong “neo” nh˜ung dˆa´u hiˆe.u ta.i d¯iˆe˙’m xuˆa´t ph´at,c´othˆe˙’ l`ad¯iˆe˙’m . . . . . du´oi bˆentr´ai,khˆongphu. thuˆo.c v`aohu´ong di chuyˆe˙’n. D- ˇa.c biˆe.t, v´oi mˆa˜u tˆochˆa´m-ga.ch, . chˇa˙’ng ha.n 111100, ch´ungta muˆo´n v˜emˆa˜u n`ayta.i d¯iˆe˙’m xuˆa´t ph´atm`akhˆongtu. d¯ˆo.ng d¯ˆo˙’i . . th`anhd¯iˆe˙’m du´oi bˆentr´ai. Ngo`aira, nˆe´u thuˆa.t to´anluˆonluˆond¯ˇa.t la.i c´acd¯iˆe˙’m d¯ˆa`u cuˆo´i . . . . . theo th´u tu. ch´ınhtˇa´c, ta cˆa`n di chuyˆe˙’n t`u tr´aisang pha˙’i v´oi d¯oa.n thˇa˙’ng AB v`at`u pha˙’i . . sang tr´aiv´oi d¯oa.n thˇa˙’ng BA; d¯iˆe` u n`ayta.o ra su. gi´and¯oa.n trong qu´atr`ınhv˜e,chˇa˙’ng ha.n . d¯agi´ac,ta.i nh˜ung d¯ı˙’nh chung. D- iˆe˙’m xuˆa´t ph´atnˇa`m trˆenca.nh cu˙’a d¯agi´accˇa´t. Mˆo.t vˆa´n d¯ˆe` kh´acch´ungta cˆa`n . . . . su˙’ a d¯ˆo˙’i thuˆa.t to´and¯ˆe˙’ v˜ec´acd¯oa.n thˇa˙’ng sau khi d¯uo. c cˇa´t bo˙’ i mˆo.t trong c´acthuˆa.t to´an . . . trong Phˆa`n 3.3. H`ınh1.4(a) minh ho.a d¯oa.n thˇa˙’ng d¯uo. c cˇa´t bo˙’ i ca.nh bˆentr´ai, x = xmin, . cu˙’a h`ınhch˜u nhˆa.t. Giao d¯iˆe˙’m cu˙’a d¯oa.n thˇa˙’ng v`aca.nh bˆentr´aic´oho`anhd¯ˆo. x nguyˆen . . nhung tung d¯ˆo. y thu. c. Pixel (xmin, bmxmin + t + 0.5c) trˆenca.nh x = xmin ch´ınhl`apixel . . . . . 2 . d¯uo. c v˜eta.i ho`anhd¯ˆo. xmin cu˙’a d¯oa.n thˇa˙’ng tru´oc khi cˇa´t theo thuˆa.t to´and¯iˆe˙’m gi˜ua . V´oi . . . pixel kho˙’ i ta.o d¯˜abiˆe´t, kˆe´ tiˆe´p ch´ungta cˆa`n kho˙’ i ta.o biˆe´n quyˆe´t d¯i.nh ta.i d¯iˆe˙’m gi˜ua d¯oa.n RD trong cˆo.t kˆe´ bˆen.Cˆa`n ch´u´yrˇa`ng, c´ach l`amn`ayta.o ra d˜aych´ınhx´acc´acpixel, trong 2 . . . Khi mxmin + t nˇa`m gi˜ua hai d¯u`ong thˇa˙’ng ngang kˆe` nhau, ch´ungta cˆa`n l`amtr`onxuˆo´ng. D- ˆayl`ahˆe. qua˙’ cu˙’a viˆe.c cho.n pixel R khi d = 0. 18
x = xmin . . . . . . . . . . . . . . . . . . . . . . . . . . D . . .i . . . . . . . . . . . . . . . —. . M . . . . . (xmin, bmxmin + t + 0.5c) . . . y i. . . . . . . . . (xmin, mxmin + t) . •. . R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y = ymin (a) x = xmin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .y. y . y y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiiyyyyiii. . . DC. . . . . . . . . . . . . . . . y = y . . . . . . . . . min . . . . . . . . . . . . . . . . . . . 1 . . . I . . . . . . . y = y − . . . • . . . . . . . min . . . . . . . . . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. y . y. y. y. y. y. y . . . y = ymin − 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (b) . . . H`ınh1.4: D- iˆe˙’m xuˆa´t ph´atnˇa`m trˆenbiˆenh`ınhch˜u nhˆa.t. (a) Giao v´oi ca.nh d¯´ung. (b) Giao . v´oi ca.nh ngang. 19
. . . . . . . . khi cˇa´t d¯u`ong thˇa˙’ng theo d¯u`ong biˆen xmin v`asau d¯´othu. c hiˆe.n v˜ed¯oa.n thˇa˙’ng d¯uo. c cˇa´t t`u . (xmin, bmxmin + t + 0.5c) d¯ˆe´n (xB, yB) theo thuˆa.t to´and¯iˆe˙’m gi˜ua s˜echo d˜ayd¯iˆe˙’m v˜ekhˆong . . ch´ınhx´acdo d¯u`ong thˇa˙’ng sau khi cˇa´t c´ohˆe. sˆo´ g´ockh´ac m. . . . . . . . . . . . Tru`ong ho. p ph´uc ta.p hon khi d¯u`ong thˇa˙’ng AB giao v´oi d¯u`ong thˇa˙’ng nˇa`m ngang nhu trong H`ınh1.4(b). Khi hˆe. sˆo´ g´oc m rˆa´t nho˙’, c´onhiˆe` u pixel nˇa`m trˆend`ongqu´et y = ymin . . . . . . tuong ´ung ca.nh bˆendu´oi cu˙’a h`ınhch˜u nhˆa.t. Ch´ungta muˆo´n bao h`amc´acpixel n`aytrong . . . h`ınhch˜u nhˆa.t, nhung do qu´atr`ınht´ınhto´angiao d¯iˆe˙’m v´oi d`ongqu´et y = ymin v`asau d¯´o . . . l`amtr`onho`anhd¯ˆo. x ta d¯uo. c pixel C khˆongpha˙’i pixel bˆentr´ainhˆa´t D trˆend`ongn`ay. Du. a trˆenh`ınhv˜e,ta thˆa´y rˇa`ng pixel bˆentr´ainhˆa´t D l`apixel trˆenbˆenpha˙’i giao d¯iˆe˙’m I cu˙’a d¯oa.n ˙’ . . ˙’ 1 ˙’ ` thˇang AB v`ad¯u`ong thˇang y = ymin − 2 . Do d¯´o,ta chı cˆan t`ım I v`al`amtr`onlˆenho`anhd¯ˆo.; pixel d¯ˆa`u tiˆen D ch´ınhl`a(dxI e, ymin). . . . . . Cuˆo´i c`ung,thuˆa.t to´and¯iˆe˙’m gi˜ua c˜ungthu. c hiˆe.n tˆo´t trong tru`ong ho. p c´acd¯iˆe˙’m d¯ˆa`u . . . cuˆo´i c´oto.a d¯ˆo. thu. c; kh´acbiˆe.t duy nhˆa´t l`abu´oc tˇangv`ac´acph´epto´anthao t´actrˆensˆo´ . thu. c. Thay d¯ˆo˙’i cu.`o.ng d¯ˆo s´angcu˙’a d¯oan thˇa˙’ng theo hˆe sˆo´ g´oc. X´ethai d¯oan thˇa˙’ng trong . . . √ . H`ınh1.5. D- oa.n thˇa˙’ng l2 c´ohˆe. sˆo´ g´oc1 v`ado d¯´oc´od¯ˆo. d`aibˇa`ng 2 lˆa`n d¯ˆo. d`aicu˙’a l1. Ch´ung . . . . ta d¯ˇa.t c`ungsˆo´ (10) pixel trˆenmˆo˜i d¯oa.n thˇa˙’ng. Nˆe´u cu`ong d¯ˆo. cu˙’a mˆo˜i pixel l`a I th`ıcu`ong . √ . d¯ˆo. trˆenmˆo.t d¯on vi. d¯ˆo. d`aicu˙’a d¯oa.n thˇa˙’ng l1 l`a I, trong khi cu˙’a l2 l`a I/ 2; su. khˆongnhˆa´t . . . . qu´ann`aydˆe˜ d`angph´athiˆe.n bo˙’ i ngu`oi quan s´at.Trˆenm`anh`ınhd¯on sˇa´c, khˆongc´oc´ach gia˙’i . . . quyˆe´t, nhung trˆenhˆe. thˆo´ng n-bit trˆenpixel ch´ungta c´othˆe˙’ ca˙’i thiˆe.n d¯uo. c t`ınhtra.ng n`ay . . bˇa`ng c´ach d¯ˇa.t cu`ong d¯ˆo. l`amˆo.t h`amcu˙’a hˆe. sˆo´ g´oc.K˜ythuˆa.t antialiasing cho kˆe´t qua˙’ tˆo´t . . . hon bˇa`ng c´ach xem d¯oa.n thˇa˙’ng nhu mˆo.t h`ınhch˜u nhˆa.t c´od¯ˆo. rˆo.ng he.p v`at´ınhto´anth´ıch . . . . . ho. p c´accu`ong d¯ˆo. v´oi nhiˆe` u pixel trˆenmˆo˜i cˆo.t nˇa`m trong hoˇa.c gˆa`n h`ınhch˜u nhˆa.t (xem [9], . . . [11]). Ngo`aira coi d¯oa.n thˇa˙’ng nhu h`ınhch˜u nhˆa.t c˜ungcho ph´epta.o c´acd¯oa.n thˇa˙’ng v´oi d¯ˆo. rˆo.ng tu`y´y. . . . Ph´actha˙’o c´acnguyˆenso x´acd¯i.nh bo˙’ i c´acd¯oa.n thˇa˙’ng. V´oi c´ach v˜ec´acd¯oa.n thˇa˙’ng, . . . . . . . . ch´ungta cˆa`n v˜ec´acnguyˆenso d¯uo. c xˆaydu. ng t`u c´acd¯oa.n thˇa˙’ng nhu thˆe´ n`ao?C´acd¯u`ong . . . . gˆa´p kh´ucc´othˆe˙’ d¯uo. c v˜ebˇa`ng c´ach xem n´onhu c´acd¯oa.n thˇa˙’ng kˆe` nhau. C´ach`ınhch˜u . . . nhˆa.t v`ad¯agi´acl`anh˜ung nguyˆenso v`ungv`ac´othˆe˙’ v˜ec´acca.nh liˆentiˆe´p nhung d¯iˆe` u n`ay . . dˆa˜n d¯ˆe´n mˆo.t sˆo´ pixel nˇa`m ngo`aiv`ungd¯i.nh ngh˜ıabo˙’ i nguyˆenso-xem c´acPhˆa`n 4.6 v`a4.7 . . . . vˆe` nh˜ung thuˆa.t to´anxu˙’ l´yvˆa´n d¯ˆe` n`ay. Ch´u´yrˇa`ng cˆa`n v˜ec´acd¯ı˙’nh chung cu˙’a d¯u`ong gˆa´p kh´ucmˆo.t lˆa`n do viˆe.c v˜ehai lˆa`n c´othˆe˙’ l`amthay d¯ˆo˙’i m`auhoˇa.c d¯ˇa.t m`aunˆe` n khi viˆe´t trong . . . chˆe´ d¯ˆo. XOR trˆenm`anh`ınh,hoˇa.c tˇangcu`ong d¯ˆo. gˆa´p d¯ˆoita.i d¯´o. Thˆa.t ra c´onh˜ung pixel kh´acl`achung cu˙’a hai d¯oa.n thˇa˙’ng nˇa`m gˆa`n nhau hoˇa.c cˇa´t nhau. 20
. . . . . . . . y . . . . . . . . . . - ˙’ . . . . . . . . Du`ong thˇang l2 . . . . . . . . . . . . . . . . . . y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. . . . . . . . . . . . . . . . . . . . . . . y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .yyyyyyyyyy. . . . . . . . . . . . . . . . . . - ˙’ . . . . . . . . . Du`ong thˇang l1 . . . . . . . . . . . . . . . . . . . . . H`ınh1.5: Thay d¯ˆo˙’i cu`ong d¯ˆo. cu˙’a c´acd¯u`ong thˇa˙’ng theo hˆe. sˆo´ g´oc. 1.1.4 C´acthuˆo.c t´ınhcu˙’a d¯oa.n thˇa˙’ng . . . . Thuˆo.c t´ınhmˆa˜u tˆod¯oa.n thˇa˙’ng c´othˆe˙’ a˙’nh huo˙’ ng d¯ˆe´n nh˜ung nguyˆenso kh´ac. N´oichung . ta cˆa`n su˙’ du. ng d¯iˆe` u kiˆe.n logic d¯ˆe˙’ kiˆe˙’m tra c´od¯ˇa.t d¯iˆe˙’m v˜ehay khˆong,chı˙’ d¯ˇa.t khi d¯iˆe` u kiˆe.n . . . . . d¯´ung(gi´atri. 1). Ch´ungta luu tr˜u mˆa˜u v˜enhu mˆo.t chuˆo˜i d¯ˆo. d`aiTile Size (thu`ong l`al˜uy . th`ua cu˙’a 2: N´oichung Tile Size = 16) l`amˆa˜u c´okiˆe˙’u Bool (chˇa˙’ng ha.n, 16 bit nguyˆen); . . do d¯´omˆa˜u tˆod¯uo. c lˇa.p la.i sau khi v˜e16 pixel. Ch´ungta thay d`onglˆe.nh khˆongd¯iˆe` u kiˆe.n . . . . putpixel() trong thuˆa.t to´anv˜ed¯oa.n thˇa˙’ng d¯ˆe˙’ xu˙’ l´ytru`ong ho. p n`ay;chˇa˙’ng ha.n, if bitstring[i % 16] putpixel(x, y, value); . trong d¯´ochı˙’ sˆo´ i l`amˆo.t biˆe´n tˇangm´oi trong v`onglˇa.p bˆentrong cu˙’a thuˆa.t to´an.Tuy nhiˆen, . . . c´ach l`amn`ayc´omˆo.t ha.n chˆe´ l`ado mˆo˜i bit trong mˇa.t na. tuong ´ung mˆo.t lˆa`n lˇa.p v`akhˆong . . . . tuong ´ung d¯ˆo. d`aid¯on vi. do.c theo d¯oa.n thˇa˙’ng nˆend¯ˆo. d`aicu˙’a n´etv˜ethay d¯ˆo˙’i theo hˆe. sˆo´ . g´occu˙’a d¯oa.n thˇa˙’ng; n´etv˜ecu˙’a d¯oa.n thˇa˙’ng xiˆens˜ed`aihon n´etv˜ecu˙’a d¯oa.n thˇa˙’ng ngang . . . . . . hay d¯´ung. D- iˆe` u n`ayl`akhˆongchˆa´p nhˆa.n d¯uo. c v´oi nh˜ung ´ung du. ng mang t´ınhch´ınhx´ac . . cao, chˇa˙’ng ha.n trong thiˆe´t kˆe´ cˆongnghiˆe.p, v`ado d¯´oc´acn´etv˜ecˆa`n t´ınhla.i sao cho phuong . . ph´apv˜ed¯oa.n thˇa˙’ng khˆongphu. thuˆo.c v`aohˆe. sˆo´ g´occu˙’a n´o.D- ˆo. rˆo.ng cu˙’a d¯oa.n thˇa˙’ng d¯uo. c . . . . xem nhu mˆo.t d˜ayc´ach`ınhch˜u nhˆa.t d¯ˇa.c v`atrong suˆo´t d¯uo. c d¯ˇa.t xen k˜enhau m`ac´acd¯ı˙’nh . . . cu˙’a n´od¯uo. c t´ınhch´ınhx´actheo h`amphu. thuˆo.c kiˆe˙’u v˜ed¯oa.n thˇa˙’ng. Sau d¯´othu. c hiˆe.n tˆo . . . . m`autrˆent`ung h`ınhch˜u nhˆa.t mˆo.t; v´oi c´acd¯oa.n thˇa˙’ng ngang hoˇa.c d¯´ung, ta c´othˆe˙’ d`ung . lˆe.nh sao ch´epc´ach`ınhch˜u nhˆa.t. . . . Kiˆe˙’u d¯oa.n thˇa˙’ng v`akiˆe˙’u b´utv˜ec´oa˙’nh huo˙’ ng lˆa˜n nhau trong c´acnguyˆenso liˆenquan . . . . . . . . d¯ˆe´n d¯ˆo. rˆo.ng d¯u`ong biˆen.Kiˆe˙’u d¯oa.n thˇa˙’ng thu`ong d¯uo. c su˙’ du. ng d¯ˆe˙’ x´acd¯i.nh c´ach`ınhch˜u . . . . . . . . . nhˆa.t tuong ´ung c´acn´etv˜ev`amˆo˜i h`ınhch˜u nhˆa.t d¯uo. c tˆom`auv´oi mˆa˜u b´utd¯uo. c cho.n. 21
1.2 D- u.`o.ng tr`on . . 2 2 2 . . . . X´etd¯u`ong tr`on f(x, y) := x +y −R = 0. C´omˆo.t v`aic´ach d¯on gia˙’n v˜ed¯u`ong tr`onnhung khˆonghiˆe.u qua˙’. . . . . . D- ˆe˙’ v˜emˆo.t phˆa`n tu d¯u`ong tr`ontrong g´ocphˆa`n tu th´u nhˆa´t {(x, y) ∈ R2 | x ≥ 0, y ≥ 0} (c´accung kh´acd¯u.o.c v˜edo t´ınhd¯ˆo´i x´u.ng) ta c´othˆe˙’ tˇang x t`u. 0 d¯ˆe´n R (mˆo˜i bu.´o.c mˆot d¯o.n √ . . 2 2 . . . vi.) v`agia˙’i y = R − x . Phuong ph´apn`aykhˆonghiˆe.u qua˙’ do su˙’ du. ng ph´epnhˆanv`alˆa´y . . . . . cˇanbˆa.c hai. Ngo`aira c´onh˜ung lˆo˜ hˆo˙’ng khi gi´atri. x gˆa`n v´oi R v`ıtiˆe´p tuyˆe´n v´oi d¯u`ong tr`on . . . . . . . . . ta.i nh˜ung d¯iˆe˙’m tuong ´ung tiˆe´n d¯ˆe´n d¯u`ong thˇa˙’ng song song v´oi tru. c tung. Phuong ph´ap . . . . kh´actuong tu. , c˜ungkhˆonghiˆe.u qua˙’, tr´anhnh˜ung lˆo˜ hˆo˙’ng l`av˜ec´acd¯iˆe˙’m (R cos θ, R sin θ) v´o.i θ thay d¯ˆo˙’i t`u. 0 d¯ˆe´n 900. 1.2.1 D- ˆo´i x´u.ng t´amd¯iˆe˙’m . . . . . Ch´ungta c´othˆe˙’ gia˙’m b´ot qu´atr`ınht´ınhto´andu. a trˆent´ınhd¯ˆo´i x´ung cu˙’a d¯u`ong tr`onqua . . . c´actru. c ch´ınh. Chı˙’ cˆa`n x´etd¯u`ong tr`ontˆamta.i gˆo´c v`ınˆe´u khˆongta thu. c hiˆe.n ph´epti.nh . . . tiˆe´n t`u tˆamvˆe` gˆo´c to.a d¯ˆo Nˆe´u d¯iˆe˙’m (x, y) nˇa`m trˆend¯u`ong tr`onth`ıba˙’y d¯iˆe˙’m (x, −y), (y, x), (y, −x), (−x, −y), (−y, −x), (−y, x), (−x, y) c˜ungnˇa`m trˆend¯u.`o.ng tr`on. 0 . . . . . . Do d¯´ota chı˙’ cˆa`n v˜emˆo.t cung 45 v`at`u d¯´osinh ra d¯u`ong tr`on.V´oi d¯u`ong tr`ontˆam . . . ta.i gˆo´c, t´amd¯iˆe˙’m d¯ˆo´i x´ung c´othˆe˙’ d¯uo. c hiˆe˙’n thi. bˇa`ng thu˙’ tu. c sau (m`adˆe˜ d`angtˆo˙’ng qu´at ho´av´o.i c´acd¯u.`o.ng tr`ontˆamtu`y´y): void CirclePoints(int x, int y, int Value) { putpixel(x, y, Value); putpixel(y, x, Value); putpixel(y, -x, Value); putpixel(x, -y, Value); putpixel(-x, -y, Value); putpixel(-y, -x, Value); 22
putpixel(-y, x, Value); putpixel(-x, y, Value); } . . Cˆa`n ch´u´yrˇa`ng khˆongnˆengo.i thu˙’ tu. c CirclePoints() khi x = y do c´obˆo´n pixel d¯uo. c . v˜ehai lˆa`n; ta chı˙’ cˆa`n thay d¯ˆo˙’i d¯oa.n m˜axu˙’ l´yd¯iˆe` u kiˆe.n biˆen. . . . 1.2.2 Thuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯u`ong tr`on . . . . . . . Bresenham [3] d¯˜atr`ınhb`aymˆo.t phuong ph´apv˜ed¯u`ong tr`onhiˆe.u qua˙’ hon c´ach d¯ua ra o˙’ . . . . . . . trˆen.Ch´ungta nˆeuthuˆa.t to´antuong tu. , su˙’ du. ng tiˆeuchuˆa˙’n d¯iˆe˙’m gi˜ua, m`atrong tru`ong . . ho. p b´ank´ınhv`ac´acto.a d¯ˆo. cu˙’a tˆaml`anh˜ung sˆo´ nguyˆens˜echo c`ungmˆo.t kˆe´t qua˙’ c´acpixel tˆo´t nhˆa´t. . . Ta chı˙’ cˆa`n x´etcung mˆo.t phˆa`n t´amd¯u`ong tr`on: (C1) := {(x, y) ∈ R2 | x2 + y2 = R2, 0 ≤ y 0) th`ı D gˆa`n d¯u`ong tr`onhon. Tru`ong ho. p M nˇa`m trˆend¯u`ong tr`on(t´uc f(M) = 0) ta c´othˆe˙’ cho.n mˆo.t trong hai, do d¯´ocho.n pixel D. D- ˇa.t 1 1 d := f(M) = f(x − , y + 1) = (x − )2 + (y + 1)2 − R2. i i 2 i i 2 i . . Nˆe´u di < 0 th`ıcho.n T v`ad¯iˆe˙’m gi˜ua kˆe´ tiˆe´p c´otung d¯ˆo. tˇangmˆo.t d¯on vi Nˆen 1 1 d = f(x − , y + 2) = (x − )2 + (y + 2)2 − R2; i+1 i 2 i i 2 i . . v`ado d¯´o di+1 = di + (2yi + 3); suy ra bu´oc tˇang∆T := 2yi + 3. 23
. D . T . w . w . M w C . . . . . H`ınh1.6: Lu´oi pixel trong thuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯u`ong tr`on. . . Nˆe´u di ≥ 0 th`ıcho.n D v`ad¯iˆe˙’m gi˜ua kˆe´ tiˆe´p c´oho`anhd¯ˆo. gia˙’m mˆo.t d¯on vi. v`atung d¯ˆo. . tˇangmˆo.t d¯on vi Nˆen 3 3 d = f(x − , y + 2) = (x − )2 + (y + 2)2 − R2. i+1 i 2 i i 2 i . . Suy ra di+1 = di + 2yi − 2xi + 5. Do d¯´obu´oc tˇang∆D := 2(yi − xi) + 5. . . . . . . . Nhˇa´c la.i l`a,trong tru`ong ho. p d¯u`ong thˇa˙’ng, c´acbu´oc tˇang∆R v`a∆D l`ac´achˇa`ng sˆo´; . . . . . tuy nhiˆen,trong tru`ong ho. p d¯u`ong cong bˆa.c hai, ∆T v`a∆D l`ac´ach`amphu. thuˆo.c v`aoc´ac . . . to.a d¯ˆo. cu˙’a d¯iˆe˙’m v˜ehiˆe.n h`anh(xi, yi). C´ach`amn`ayc´othˆe˙’ t´ınhto´antru. c tiˆe´p ta.i mˆo˜i bu´oc . . . . . . . . lˇa.p du. a v`aoc´acgi´atri. x v`a y cu˙’a pixel d¯uo. c cho.n trong bu´oc lˇa.p tru´oc. T´ınhto´annhu vˆa.y khˆonghiˆe.u qua˙’ do c´ach`amn`ayl`atuyˆe´n t´ınh(xem Nhˆa.n x´et1.2.1). . . Cuˆo´i c`ungcˆa`n t´ınh d0. V´oi gia˙’ thiˆe´t b´ank´ınhnguyˆen,ta biˆe´t rˇa`ng pixel kho˙’ i ta.o ` ˙’ . 1 1 ban d¯ˆau c´oto.a d¯ˆo. (R, 0) nˆend¯iˆem gi˜ua c´oto.a d¯ˆo. (R − 2 , 1) v`ado d¯´o d0 = f(R − 2 , 1) = 1 2 2 5 ˙’ ´ . . ´ (R − 2 ) + 1 − R = 4 − R. Tˆong kˆet ta c´othuˆa.t to´anv˜ed¯u`ong tr`ontˆamta.i gˆoc to.a d¯ˆo. v`a b´ank´ınh R nhu. sau: . 1. [Kho˙’ i ta.o] D- ˇa.t x0 = R, y0 = 0, d0 = 5/4 − R. . . . . . 2. Gia˙’ su˙’ o˙’ bu´oc th´u i ta c´od¯iˆe˙’m v˜etˆo´t nhˆa´t (xi, yi) v`abiˆe´n quyˆe´t d¯i.nh di. . 3. [V˜epixel hiˆe.n h`anh]D- ˇa.t t´amd¯iˆe˙’m v˜edu. a trˆen(xi, yi). 24
. . . 4. [Cˆa.p nhˆa.t] Nˆe´u xi = yi, thuˆa.t to´and`ung; nguo. c la.i, d¯ˇa.t ( xi nˆe´u di < 0, xi+1 = . . xi − 1 nˆe´u nguo. c la.i; y = y + 1; i+1 (i di + 2yi + 3 nˆe´u di < 0, di+1 = . . di + 2(yi − xi) + 5 nˆe´u nguo. c la.i. . . 5. Thay i bˇa`ng (i + 1) v`alˇa.p la.i Bu´oc 3. . . . Nhˆa.n x´et1.2.1 (i) Vˆa´n d¯ˆe` v´oi thuˆa.t to´anv`ua tr`ınhb`ay, ta l`amviˆe.c trˆenc´acsˆo´ thu. c v`ı . . . . . kho˙’ i ta.o biˆe´n quyˆe´t d¯i.nh l`asˆo´ thu. c. Mˇa.c d`uc´othˆe˙’ dˆe˜ d`angca˙’i tiˆe´n d¯ˆe˙’ xu˙’ l´ycho d¯u`ong tr`onc´otˆamhoˇa.c b´ank´ınhkhˆongnguyˆen,ta s˜etr`ınhb`ayc´ach t´ınhto´ansˆo´ nguyˆenhiˆe.u qua˙’ ho.n. N´oic´ach kh´acta s˜ekhu˙’. c´acmˆa˜u sˆo´ trong chu.o.ng tr`ınh. - ` ´ . 1 ˙’. 1 Dˆau tiˆen,x´etbiˆen m´oi hi = di − 4 v`athay di boi hi + 4 trong thuˆa.t to´an.Khi d¯´ota ˙’. . . . . 1 khoi ta.o h0 = 1 − R v`aso s´anh di < 0 tuong d¯uong hi < − 4 . Tuy nhiˆen,do h0 nguyˆenv`a . . . . d¯uo. c tˇangbo˙’ i c´acgi´atri. nguyˆen(∆T v`a∆D) nˆenchı˙’ cˆa`n so s´anh hi < 0. Nhu vˆa.y, ch´ung . . . . . . . ta c´othuˆa.t to´anv˜ed¯u`ong tr`onchı˙’ su˙’ du. ng c´acsˆo´ nguyˆennhu du´oi d¯ˆay;d¯ˆe˙’ nhˆa´t qu´anv´oi thuˆa.t to´anv˜ed¯oa.n thˇa˙’ng, ta thay h l`a d. void MidPointCircle(int R, int Value) { int x, y, d; x = R; y = 0; d = 1 - R; CirclePoints(x, y, Value); while (y < x) { if (d < 0) { d += 2*y + 3; y++; } else { 25
d += 2*(y - x) + 5; x ; y++; } CirclePoints(x, y, Value); } } . . . . . (ii) Ch´ungta c`onc´othˆe˙’ ca˙’i tiˆe´n tˆo´t hon thuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯u`ong tr`onnhu sau. Ch´u . . . ´yrˇa`ng c´ach`am∆ l`aphuong tr`ınhtuyˆe´n t´ınhv`ac´othˆe˙’ t´ınhtru. c tiˆe´p. Tuy nhiˆend`ung . . . . . . . phuong ph´ap sai phˆanbˆa. c mˆo. t-hai d¯ˆe˙’ x´acd¯i.nh ch´unghiˆe.u qua˙’ hon: u´oc luo. ng h`amta.i . . . . . hai d¯iˆe˙’m v˜ekˆe` nhau, t´ınhhiˆe.u (trong tru`ong ho. p d¯ath´uc, luˆonluˆoncho d¯ath´uc bˆa.c thˆa´p . . . hon) v`a´apdu. ng hiˆe.u trong mˆo˜i bu´oc lˇa.p. . . . Nˆe´u cho.n T trong bu´oc lˇa.p kˆe´ tiˆe´p th`ıd¯iˆe˙’m hiˆe.n h`anhs˜edi chuyˆe˙’n t`u (xi, yi) d¯ˆe´n (xi, yi + 1). Ta biˆe´t rˇa`ng, sai phˆanbˆa.c mˆo.t ∆T ta.i (xi, yi) bˇa`ng 2yi + 3. Do d¯´o∆T ta.i . . . (xi, yi + 1) bˇa`ng 2(yi + 1) + 3. Suy ra sai phˆanbˆa.c hai ∆T,i+1 − ∆T,i = 2. Tuong tu. , ∆D ta.i (xi, yi) bˇa`ng 2(yi − xi) + 5. Do d¯´o∆D ta.i (xi, yi + 1) bˇa`ng 2(yi + 1 − xi) + 5. Suy ra sai phˆan bˆa.c hai ∆D,i+1 − ∆D,i = 2. . . . Nˆe´u cho.n D trong bu´oc lˇa.p kˆe´ tiˆe´p th`ı d¯iˆe˙’m hiˆe.n h`anhdi chuyˆe˙’n t`u (xi, yi) d¯ˆe´n (xi −1, yi +1). Do d¯´o∆T ta.i (xi, yi) bˇa`ng 2(yi +1)+3, v`asai phˆanbˆa.c hai ∆T,i+1 −∆T,i = 2. . . . Tuong tu. , ∆D ta.i (xi − 1, yi + 1) bˇa`ng 2[(yi + 1) − (xi − 1)] + 5. Suy ra sai phˆanbˆa.c hai ∆D,i+1 − ∆D,i = 4. . . . Vˆa.y thuˆa.t to´anca˙’i biˆengˆo`m c´acbu´oc: (1) cho.n pixel du. a trˆendˆa´u cu˙’a biˆe´n quyˆe´t . . . . . . d¯i.nh di d¯uo. c x´acd¯i.nh trong bu´oc lˇa.p tru´oc; (2) cˆa.p nhˆa.t biˆe´n quyˆe´t d¯i.nh di theo ∆T hoˇa.c . . . ∆D; (3) cˆa.p nhˆa.t c´ach`am∆; v`a(4) di chuyˆe˙’n d¯ˆe´n pixel kˆe´ tiˆe´p. ∆T v`a∆D d¯uo. c kho˙’ i ta.o . du. a trˆenpixel ban d¯ˆa`u (R, 0). . . . V´ıdu. 1.2.2 Gia˙’ su˙’ d¯u`ong tr`onc´otˆam O(0, 0) b´ank´ınh R = 20. Ta c´o x0 = R = 20, y0 = 0, d0 = 1 − R = −19, ∆T,0 = 3, ∆D,0 = −2R + 5 = −35. . . . . . Ap´ du. ng thuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯u`ong tr`onta d¯uo. c d˜ayc´acd¯iˆe˙’m v˜etˆo´t nhˆa´t (trˆencung 26
. . . . . mˆo.t phˆa`n t´amtrong g´ocphˆa`n tu th´u nhˆa´t) nhu trong ba˙’ng du´oi: i xi yi di ∆T,i ∆D,i 0 20 0 −19 3 −35 1 20 1 −16 5 −33 2 20 2 −11 7 −31 3 20 3 −4 9 −29 4 20 4 5 11 −27 5 19 5 −22 13 −23 6 19 6 −9 15 −21 7 19 7 6 17 −19 8 18 8 −13 19 −15 9 18 9 6 21 −13 10 17 10 −7 23 −9 11 17 11 16 25 −7 12 16 12 9 27 −3 13 15 13 6 29 1 14 14 14 7 31 5 . . . . . Thu˙’ tu. c v˜ed¯u`ong tr`ontheo phuong ph´apsai phˆanbˆa.c hai nhu sau: void MidPointCircle(int R, int Value) { int x, y, d, DeltaT, DeltaD; x = R; y = 0; d = 1 - R; DeltaT = 3; DeltaD = -2*R + 5; CirclePoints(x, y, Value); while (y < x) { if (d < 0) { d += DeltaT; DeltaT += 2; 27
DeltaD += 2; y++; } else { d += DeltaD; DeltaT += 2; DeltaD += 4; x ; y++; } CirclePoints(x, y, Value); } } 1.3 D- u.`o.ng cong ellipse . . . . . . . C´acd¯u`ong cong conic d¯uo. c nghiˆenc´uu t`u rˆa´t lˆau.C´othˆe˙’ xem n´onhu giao cu˙’a mˆo.t mˇa.t . . . . phˇa˙’ng v´oi mˆo.t mˇa.t n´on. N´oc˜ungc´othˆe˙’ d¯uo. c x´acd¯i.nh nhu tˆa.p c´acd¯iˆe˙’m n`aod¯´o,chˇa˙’ng . . ha.n d¯u`ong tr`on,m`akhoa˙’ng c´ach d¯ˆe´n mˆo.t d¯iˆe˙’m khˆongd¯ˆo˙’i. Trong h`ınhho.c gia˙’i t´ıch, c´ac . . . 2 . . conic d¯uo. c xem nhu c´actˆa.p con cu˙’a R : Ch´ungta d¯i.nh ngh˜ıamˆo.t conic nhu tˆa.p ho. p c´ac d¯iˆe˙’m (x, y) ∈ R2 thoa˙’ m˜anphu.o.ng tr`ınh Ax2 + Bxy + Cy2 + Dx + Ey + F = 0. . . . . . v´oi c´acsˆo´ thu. c A, B, C, D, E, F n`aod¯´o.Viˆe.c phˆanloa.i conic (trong tru`ong ho. p kh´actrˆo´ng) . l`ahyperbol, ellipse hay l`aparabol phu. thuˆo.c v`aodˆa´u cu˙’a biˆe.t th´uc δ := B2 − 4AC du.o.ng, ˆam,hay bˇa`ng khˆong(xem [12]). . . . . Mˇa.t kh´ac,ellipse l`amˆo.t trong nh˜ung nguyˆenso cu˙’a d¯ˆo` ho.a m´ayt´ınhthu`ong xuyˆen . . . . . . d¯uo. c su˙’ du. ng trong c´ac´ung du. ng d¯ˆo` ho.a. Do d¯´oc´orˆa´t nhiˆe` u nghiˆenc´uu nhˇa`m d¯ua ra . . nh˜ung thuˆa.t to´anh˜uu hiˆe.u d¯ˆe˙’ v˜ec´acellipse trˆenc´acthiˆe´t bi. hiˆe˙’n thi. raster (xem [26], [16], [17], [28]). . . . . . Thuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯u`ong thˇa˙’ng v`ad¯u`ong tr`onc˜ungc´othˆe˙’ ´apdu. ng d¯ˆe˙’ v˜ec´ac . . d¯u`ong cong conic tˆo˙’ng qu´at.Mu. c d¯´ıch cu˙’a phˆa`n n`ayl`a: 28
. . . . 1. V˜eellipse “ch´ınhtˇa´c” v´oi tˆamta.i gˆo´c to.a d¯ˆo. (0, 0) cho bo˙’ i phuong tr`ınh b2x2 + a2y2 − a2b2 = 0 trong d¯´o2a l`ad¯ˆo. d`aitru. c ch´ınh Ox v`a2b l`ad¯ˆo. d`aitru. c phu. Oy. . . . 2. V˜eellipse trong tru`ong ho. p bˆa´t k`y. 1.3.1 Ellipse c´oda.ng ch´ınhtˇa´c D- ˆe˙’ d¯o.n gia˙’n, do t´ınhd¯ˆo´i x´u.ng, ch´ungta chı˙’ cˆa`n v˜eellipse nˇa`m trong g´ocphˆa`n tu. th´u. nhˆa´t: 2 2 2 2 2 2 2 (EI ) := {(x, y) ∈ R | f(x, y) := b x + a y − a b = 0, x ≥ 0, y ≥ 0}. . C˜ungch´u´yrˇa`ng, c´acellipse ch´ınhtˇa´c tˆamta.i to.a d¯ˆo. nguyˆenc´othˆe˙’ d¯ua vˆe` tˆamta.i gˆo´c to.a . . . d¯ˆo. bˇa`ng ph´epti.nh tiˆe´n. Thuˆa.t to´antr`ınhb`ayo˙’ d¯ˆaycu˙’a Da Silva [6] l`asu. tˆo˙’ng ho. p c´ac phu.o.ng ph´apcu˙’a Pitteway [16], Van Aken [26] v`aKappel [10]. Phˆant´ıch ´ . . . . . . . Y tuo˙’ ng cu˙’a c´acphuong ph´apd¯uo. c tr`ınhb`aytrong phˆa`n sau l`axuˆa´t ph´att`u pixel (x0, y0) . n`aod¯´otrˆencung (EI ) ch´ungta xˆaydu. ng mˆo.t d˜ayc´acpixel “tˆo´t nhˆa´t” (xn, yn). Kh´ainiˆe.m . . . . . . . . tˆo´t nhˆa´t o˙’ d¯ˆayd¯uo. c hiˆe˙’u l`acho.n d˜ayc´acpixel (xn, yn) gˆa`n v´oi d¯u`ong cong thu. c tˆe´ (o˙’ da.ng liˆentu. c) nhˆa´t. 1 2 . . Trˆencung (EI ) ta chia l`amhai v`ung(EI ) v`a(EI ). Biˆengi˜ua hai v`ungx´acd¯i.nh bo˙’ i . . . d¯iˆe˙’m trˆenellipse m`atiˆe´p tuyˆe´n v´oi d¯u`ong cong ta.i d¯´oc´ohˆe. sˆo´ g´ocbˇa`ng −1 (H`ınh1.7); . ˙’ ` ˙’ ∂f ∂f t . ` t´uc l`ata.i d¯iˆem m`ac´acth`anhphˆan cua vector gradient ∇f(x, y) := ( ∂x , ∂y ) c´od¯ˆo. l´on bˇang ` ∂f ˙’ . ` ∂f . ´ . . nhau. Th`anhphˆan ∂y nho hon th`anhphˆan ∂x trong v`ungth´u nhˆat v`anguo. c la.i trong v`ung th´u. hai. Ch´ınhx´acl`a df df (E1) := {(x, y) ∈ (E ) | ≤ }. I I dy dx v`a df df (E2) := {(x, y) ∈ (E ) | ≥ }. I I dy dx ´ ˙’ . ˙’ 2 2 1 ˙’ . Do d¯´o,nˆeu ta.i vi. tr´ıd¯iˆem gi˜ua xay ra a (yi + 1) ≥ b (xi − 2 ) th`ıch´ungta chuyˆen t`u v`ung th´u. nhˆa´t sang v`ungth´u. hai. 29
. . . . . . . . . . . . 2 . . (E ) . I ∇f(x, y) . . . . . . . . . . . . . . 1 . . (E ) . I . . . . H`ınh1.7: Hai v`ungcu˙’a ellipse. . . . . . qT`u phuong tr`ınhx´acd¯i.nh ellipse, cung (EI ) x´acd¯i.nh bo˙’ i c´accˇa.p to.a d¯ˆo. (x, y) v´oi x2 ˙’ ´ y = b 1 − a2 . Do d¯´ota c´othˆe viˆet la.i dy (E1) := {(x, y) ∈ (E ) | ≤ −1}. I I dx v`a dy (E2) := {(x, y) ∈ (E ) | − 1 ≤ ≤ 0}. I I dx X´etv`ungth´u. nhˆa´t . . . ˙’ 1 ˙’ dy dx Trong tru`ong ho. p n`ay, c´acd¯iˆem trˆencung (EI ) thoa dx ≤ −1. Do d¯´o −1 ≤ dy ≤ 0. Suy ra . . . . . . . khi y tˇangmˆo.t d¯on vi. th`ı x gia˙’m khˆongqu´amˆo.t d¯on vi V`ıvˆa.y nˆe´u bu´oc th´u i cho.n d¯uo. c . . . . d¯iˆe˙’m v˜etˆo´t nhˆa´t C := (xi, yi) th`ıo˙’ bu´oc th´u (i + 1) ta s˜echo.n d¯iˆe˙’m v˜e(xi+1, yi+1), trong . . . d¯´o yi+1 = yi + 1 v`a xi+1 = xi hoˇa.c xi+1 = xi − 1. N´oic´ach kh´ac,bu´oc th´u (i + 1) ch´ungta s˜echo.n mˆo.t trong hai pixel T := (xi, yi + 1) hoˇa.c D := (xi − 1, yi + 1) (xem H`ınh1.8). . . . . . . . . . . . . Tuong tu. thuˆa.t to´and¯iˆe˙’m gi˜ua v˜ed¯u`ong thˇa˙’ng v`ad¯u`ong tr`on,ta cˆa`n u´oc luo. ng h`am ˙’ . 1 ˙’ ˙’. ´ ˙’ f(x, y) ta.i d¯iˆem gi˜ua M := (xi − 2 , yi + 1) cua hai pixel T v`a D v`asu du. ng dˆau cua f(M) . . . d¯ˆe˙’ x´acd¯i.nh vi. tr´ıcu˙’a M v´oi ellipse, v`ado d¯´ox´acd¯i.nh pixel n`aogˆa`n v´oi ellipse hon. X´et biˆe´n quyˆe´t d¯i.nh 1 1 d := f(M) = f(x − , y + 1) = b2(x2 − x + ) + a2(y2 + 2y + 1) − a2b2. i i 2 i i i 4 i i . . . Nˆe´u di chuyˆe˙’n t`u pixel hiˆe.n h`anhd¯ˆe´n pixel T th`ıd¯iˆe˙’m gi˜ua c´otung d¯ˆo. tˇangmˆo.t d¯on vi., 30
D . T . w . w . . M . w. C H`ınh1.8: D- iˆe˙’m gi˜u.a M v`ac´acpixel T v`a D. nˆen 1 1 d = f(x − , y + 2) = b2(x2 − x + ) + a2(y2 + 4y + 4) − a2b2. i+1 i 2 i i i 4 i i 2 . . . 2 Do d¯´o di+1 = di + a (2yi + 3) v´oi bu´oc tˇang∆T := a (2yi + 3). . . Khi di chuyˆe˙’n t`u pixel hiˆe.n h`anhd¯ˆe´n pixel D th`ıd¯iˆe˙’m gi˜ua c´oho`anhd¯ˆo. gia˙’m mˆo.t . . d¯on vi. v`atung d¯ˆo. tˇangmˆo.t d¯on vi., nˆen 3 9 d = f(x − , y + 2) = b2(x2 − 3x + ) + a2(y2 + 4y + 4) − a2b2. i+1 i 2 i i i 4 i i 2 2 . . . 2 2 Suy ra di+1 = di + b (−2xi + 2) + a (2yi + 3) v´oi bu´oc tˇang∆D := b (−2xi + 2) + a (2yi + 3). . . Bˆaygi`o ta cˆa`n t´ınhgi´atri. kho˙’ i ta.o. Gia˙’ thiˆe´t a v`a b nguyˆen,ellipse bˇa´t d¯ˆa`u ta.i (a, 0) ˙’ . ` 1 v`ad¯iˆem gi˜ua d¯ˆau tiˆenc´oto.a d¯ˆo. (a − 2 , 1). Do d¯´o 2 2 2 d0 = a − ab + b /4. . . . . V´oi mˆo˜i bu´oc lˇa.p trong v`ungth´u nhˆa´t, ch´ungta khˆongchı˙’ kiˆe˙’m tra biˆe´n quyˆe´t d¯i.nh di v`a . . . cˆa.p nhˆa.t c´ach`am∆ m`ac`onx´etd¯˜akˆe´t th´ucv`ungth´u nhˆa´t chua du. a trˆenvector gradient . . . . ta.i d¯iˆe˙’m gi˜ua cu˙’a d¯oa.n T D. Vˆa.y d˜ay {(xi, yi)}i≥0 d¯uo. c xˆaydu. ng theo quy na.p thˆongqua . d˜aybiˆe´n quyˆe´t d¯i.nh {di} nhu sau: . 2 2 2 1. [Kho˙’ i ta.o] D- ˇa.t x0 = a; y0 = 0; d0 = a − ab + b /4. ´ ´ 2 2 1 . ´ . ´ ˙’ 2. [Kˆet th´uc?]Nˆeu a (yi + 1) ≥ b (xi − 2 ) th`ıd`ung (kˆet th´ucv`ungth´u nhˆat) v`achuyˆen sang v˜ev`ungth´u. hai. . . 3. [Cˆa.p nhˆa.t] Nguo. c la.i 31
• V˜ebˆo´n pixel: (xi, yi), (xi, −yi), (−xi, yi), (−xi, −yi). • Nˆe´u di < 0 th`ıd¯ˇa.t 2 di+1 = di + a (2yi + 3), xi+1 = xi. . . • Nguo. c la.i d¯ˇa.t 2 2 di+1 = di + b (−2xi + 2) + a (2yi + 3), xi+1 = xi − 1. . . . 4. D- ˇa.t yi+1 = yi + 1, thay i bo˙’ i i + 1 v`achuyˆe˙’n sang Bu´oc 2. X´etv`ungth´u. hai . . . . Bˇa`ng c´aclˆa.p luˆa.n tuong tu. , trong d¯´othay d¯ˆo˙’i vai tr`ocu˙’a x v`a y ta c´othˆe˙’ v˜ecung th´u . 2 dy ˙’ . hai. Thˆa.t vˆa.y, trˆenv`ungth´u hai (EI ) ta c´o −1 ≤ dx ≤ 0. Nˆenkhi x giam mˆo.t d¯on vi. th`ı . . . . . . . y tˇangkhˆongqu´amˆo.t d¯on vi V`ıvˆa.y, gia˙’ thiˆe´t o˙’ bu´oc th´u i ta cho.n d¯uo. c d¯iˆe˙’m v˜etˆo´t . . . nhˆa´t C := (xi, yi) th`ıbu´oc kˆe´ tiˆe´p (i + 1) ta s˜echo.n pixel (xi+1, yi+1) v´oi xi+1 = xi − 1 v`a . . . yi+1 = yi hoˇa.c yi+1 = yi + 1. N´oic´ach kh´ac,bu´oc th´u (i + 1) ch´ungta s˜echo.n mˆo.t trong hai pixel L := (xi − 1, yi) hoˇa.c D := (xi − 1, yi + 1) (xem H`ınh1.9). . . . . . . . Ta lˆa´y pixel d¯uo. c v˜eo˙’ bu´oc cuˆo´i cu˙’a v`ungth´u nhˆa´t l`apixel kho˙’ i ta.o (x0, y0) cu˙’a . v`ungth´u hai. Trong v`ungn`aych´ungta cˆa`n cho.n mˆo.t trong hai pixel L hoˇa.c D. D- ˇa.t M l`a ˙’ . ˙’ . 1 . . . . ˙’ d¯iˆem gi˜ua cua d¯oa.n LD; t´uc M c´oto.a d¯ˆo. l`a(xi − 1, yi + 2 ). Tuong tu. nhu trˆen,ta c´od¯iˆem M nˇa`m trong, trˆenhay ngo`aiellipse nˆe´u v`achı˙’ nˆe´u biˆe˙’u th´u.c f(M) ˆam,bˇa`ng khˆonghay . . . . . duong tuong ´ung. D- ˇa.t 1 1 d := f(M) = f(x − 1, y + ) = b2(x2 − 2x + 1) + a2(y2 + y + ) − a2b2. i i i 2 i i i i 4 . . . Nˆe´u di chuyˆe˙’n t`u pixel hiˆe.n h`anhd¯ˆe´n pixel L th`ıd¯iˆe˙’m gi˜ua c´oho`anhd¯ˆo. gia˙’m mˆo.t d¯on vi., nˆen 1 1 d = f(x − 2, y + ) = b2(x2 − 4x + 4) + a2(y2 + y + ) − a2b2. i+1 i i 2 i i i i 4 2 . . . 2 Do d¯´o di+1 = di + b (−2xi + 3) v´oi bu´oc tˇang∆L := b (−2xi + 3). . . Khi di chuyˆe˙’n t`u pixel hiˆe.n h`anhd¯ˆe´n pixel D th`ıd¯iˆe˙’m gi˜ua c´oho`anhd¯ˆo. gia˙’m mˆo.t . . d¯on vi. v`atung d¯ˆo. tˇangmˆo.t d¯on vi., nˆen 3 9 d = f(x − 2, y + ) = b2(x2 − 4x + 4) + a2(y2 + 3y + ) − a2b2. i+1 i i 2 i i i i 4 2 2 . . . 2 2 Suy ra di+1 = di + b (−2xi + 3) + a (2yi + 2) v´oi bu´oc tˇang∆D := b (−2xi + 3) + a (2yi + 2). 32
D w M L w w C H`ınh1.9: D- iˆe˙’m gi˜u.a M v`ac´acpixel L v`a D. . . Cuˆo´i c`ungta cˆa`n kho˙’ i ta.o biˆe´n quyˆe´t d¯i.nh d0 trong v`ungth´u hai: nˆe´u pixel cuˆo´i c`ung . . . ´ 1 ´ E d¯uo. c cho.n trong v`ungth´u nhˆat l`a(xE, yE) th`ıd¯ˇa.t d0 := f(xE − 1, yE + 2 ). Ch´ungta kˆet . . . . . th´ucv˜ev`ungth´u hai khi ho`anhd¯ˆo. xi = 0. Ta c´oc´acbu´oc mˆota˙’ cho v`ungth´u hai nhu sau: ˙’. - 2 2 2 2 1 2 2 1. [Khoi ta.o] Dˇa.t (x0, y0) = (xE, yE) v`a d0 = b (xE − 2xE + 1) + a (yE + yE + 4 ) − a b . . . 2. [Kˆe´t th´uc?]Nˆe´u (xi = 0) th`ıd`ung (kˆe´t th´ucv`ungth´u hai); . . 3. [Cˆa.p nhˆa.t] Nguo. c la.i • V˜ebˆo´n pixel: (xi, yi), (xi, −yi), (−xi, yi), (−xi, −yi). • Nˆe´u di > 0 th`ıd¯ˇa.t 2 di+1 = di + b (−2xi + 3), yi+1 = yi. . . • Nguo. c la.i d¯ˇa.t 2 2 di+1 = di + b (−2xi + 3) + a (2yi + 2), yi+1 = yi + 1. . . . 4. D- ˇa.t xi+1 = xi − 1, thay i bo˙’ i i + 1 v`achuyˆe˙’n sang Bu´oc 2. . . . Nhˆa.n x´et1.3.1 (i) Trong tru`ong ho. p c´acto.a d¯ˆo. tˆamellipse v`ac´acb´ank´ınh a, b nguyˆen, . . d¯ˆe˙’ tr´anht´ınhto´antrˆensˆo´ thu. c, ch´ungta c´othˆe˙’ khu˙’ phˆansˆo´ v`achı˙’ ´apdu. ng c´acph´epto´an trˆensˆo´ nguyˆen. . . . . . . (ii) C˜ungc´othˆe˙’ t´ınhc´ach`am∆ tru. c tiˆe´p trong mˆo˜i bu´oc lˇa.p hoˇa.c su˙’ du. ng phuong ph´ap . . . sai phˆanbˆa.c hai nhu trong thuˆa.t to´anv˜ed¯u`ong tr`on.Ch´ungta c´othˆe˙’ v˜ec´acellipse qua 33
H`ınh1.10: (a) H`ınhvuˆongbao d¯u.`o.ng tr`on. (b) H`ınhvuˆongv`ah`ınhtr`onqua ph´epbiˆe´n d¯ˆo˙’i. . . . . . . ph´epquay v`ac´acellipse c´o“d¯ˆo. dˆa`y” he.p; t´uc v´oi nh˜ung tru`ong ho. p |a| ¿ 1 ¿ |b| hoˇa.c . . nguo. c la.i (xem [6]). . . . 1.3.2 Ellipse trong tru`ong ho. p tˆo˙’ng qu´at . . . . . Trong phˆa`n tru´oc ta d¯˜axˆaydu. ng thuˆa.t to´anv˜ed¯u`ong cong ellipse m`ac´actru. c cu˙’a n´osong . . . . . song v´oi c´actru. c to.a d¯ˆo. cu˙’a mˇa.t phˇa˙’ng. Phˆa`n n`ayxˆaydu. ng thuˆa.t to´an,du. a trˆenphuong ph´apd¯iˆe˙’m gi˜u.a cu˙’a Van Aken, d¯ˆe˙’ v˜ec´acd¯u.`o.ng cong conic tˆo˙’ng qu´atbao gˆo`m c´acellipse, . . . hyperbol v`aparabol. Thuˆa.t to´ann`aydu. a trˆenthuˆa.t to´anv˜ed¯u`ong cong cu˙’a Pitteway [16] . . . d¯ua ra nˇam1967, hai nˇamsau khi Bresenham cˆongbˆo´ thuˆa.t to´anv˜ed¯u`ong thˇa˙’ng [4]. Thuˆa.t to´anconic chia l`amhai phˆa`n t´ach biˆe.t: D- ˇa.c ta˙’ conic c´oda.ng tˆo˙’ng qu´at f(x, y) := Ax2 + Bxy + Cy2 + Dx + Ey + F = 0. . . . . . . v´oi A, B, C, E, F l`ac´achˆe. sˆo´thu. c. Phuong ph´apx´acd¯i.nh conic bˇa`ng phuong tr`ınh f(x, y) = 0 kh´oh`ınhdung h`ınhho.c v`ado d¯´ota s˜ekha˙’o s´atmˆo.t c´ach kh´ac.Ch´ungta s˜echı˙’ tr`ınhb`ay . . . . . . . . vˆe` ellipse, nhung nh˜ung l´yluˆa.n tuong tu. c´othˆe˙’ ´apdu. ng cho l´op c´acd¯u`ong cong hyperbol v`aparabol. . . . D- u`ong tr`ontˆam O(0, 0) b´ank´ınhd¯on vi.: x2 + y2 = 1 nˇa`m trong h`ınhvuˆong V. 34
X´etph´epbiˆe´n d¯ˆo˙’i aﬃne T trˆenmˇa.t phˇa˙’ng R2. Khi d¯´o´anhxa. T biˆe´n d¯ˆo˙’i h`ınhvuˆong V th`anhh`ınhb`ınhh`anhv`ad¯u.`o.ng tr`onbiˆe´n d¯ˆo˙’i th`anhellipse (H`ınh1.10). C´acd¯iˆe˙’m gi˜u.a P, Q cu˙’a c´acca.nh cu˙’a h`ınhb`ınhh`anhnˇa`m trˆenellipse. C´acd¯iˆe˙’m P, Q v`atˆam J cu˙’a h`ınh b`ınhh`anhx´acd¯i.nh duy nhˆa´t mˆo.t h`ınhb`ınhh`anhv`ado d¯´ox´acd¯i.nh duy nhˆa´t ellipse. Nhˆa.n . . . x´etrˇa`ng nˆe´u c´othˆe˙’ x´acd¯i.nh c´achˆe. sˆo´ trong tru`ong ho. p tˆamellipse l`agˆo´c to.a d¯ˆo. th`ıch´ung . . . . ta c˜ungc´othˆe˙’ xu˙’ l´ytrong tru`ong ho. p tˆo˙’ng qu´at.Ta chı˙’ cˆa`n ´apdu. ng ph´epti.nh tiˆe´n d¯ˆe´n tˆam J. (D˜ınhiˆen,d¯iˆe` u n`aychı˙’ d¯´ungkhi J c´oc´acto.a d¯ˆo. nguyˆen).V`ıvˆa.y c´othˆe˙’ gia˙’ thiˆe´t J . . . . . . l`agˆo´c to.a d¯ˆo. v`a P, Q l`anh˜ung d¯iˆe˙’m d¯˜ad¯uo. c biˆe´n d¯ˆo˙’i tuong ´ung. Ch´ungta gia˙’ thiˆe´t rˇa`ng . . . . . cung (ngˇa´n) cu˙’a ellipse d¯i.nh hu´ong nguo. c chiˆe` u kim d¯ˆo`ng hˆo` (quanh tˆam J) t`u P d¯ˆe´n Q; . . nguo. c la.i, ho´and¯ˆo˙’i P v`a Q. - ˙’ . . ˙’ 2 ˙’ à ảDˆe x´acd¯ià ả.nh phuong tr`ınhellipseà taả cˆa`n t`ımph´epbiˆeà ả´n d¯ˆoi aﬃne trong R c´acd¯iˆem 1 0 xP xQ v`a tu.o.ng ´u.ng lˆen P = v`a Q = . Ph´epbiˆe´n d¯ˆo˙’i T trong tru.`o.ng 0 1 y y . . P Q ho. p n`ayx´acd¯i.nh bo˙’ i: à ả à ả à ả x xP xQ x 7→ . y yP yQ y Ph´epbiˆe´n d¯ˆo˙’i T biˆe´n d¯ˆo˙’i c´acd¯iˆe˙’m trˆend¯u.`o.ng tr`on: à ả à ả 1 0 cos(α) + sin(α), 0 1 v´o.i α ∈ [0, 1], th`anhc´acd¯iˆe˙’m trˆenellipse: à ả à ả à ả x xP xQ = cos(α) + sin(α). y yP yQ 2 2 . . Ch´u´yrˇa`ng cos (α) + sin (α) = 1. Suy ra c´achˆe. sˆo´ cu˙’a phuong tr`ınhx´acd¯i.nh ellipse l`a 2 2 2 2 A = yP + yQ,B = −2(xP yP + xQyQ),C = xP + xQ, 2 D = 0,E = 0,F = −(xP yQ − yP xQ) . . −→ . . . . Bˆaygi`o ti.nh tiˆe´n ellipse theo vector PJ, ta d¯uo. c ellipse m´oi c´otˆamta.i −P, t´uc l`a . . . . . . thay x = x + xP , y = y + yP v`aophuong tr`ınhellipse ta d¯uo. c phuong tr`ınhx´acd¯i.nh ellipse m´o.i 2 2 A(x + xP ) + B(x + xP )(y + yP ) + C(y + yP ) + D(x + xP ) + E(y + yP ) + F = A0 x2 + B0 xy + C 0 y2 + D0 x + E0 y + F 0 = 0, trong d¯´o A0 = A, B0 = B, C 0 = C, 0 0 0 D = 2yQ(xP yQ − yP xQ),E = −2xQ(xP yQ − yP xQ),F = 0. 35
. . . . . . . . . . . . . . . . . . . 4 . . . . . . 5 . . . 3 . . . . . . . 3 . 2 . . . . 4 1 . . . 6 2 5 . 8 . . . . . 6 . 7 . . . . . . . . 7 . . . . . . . . . 1 . . . . 8 . . . . . . . . . . (a) (b) Cung Di chuyˆe˙’n b`anc`o. Di chuyˆe˙’n ch´eo ∆x ∆y ∆x ∆y 1 1 0 1 1 2 0 1 1 1 3 0 1 −1 1 4 −1 0 −1 1 5 −1 0 −1 −1 6 0 −1 −1 −1 7 0 −1 1 −1 8 1 0 1 −1 (c) . . . . . H`ınh1.11: (a) T´amcung v˜e.(b) Ellipse v´oi ph´epphˆanhoa.ch. (c) Hu´ong di chuyˆe˙’n tuong ´u.ng. 36
. . . Nhˆa.n x´etrˇa`ng gˆo´c to.a d¯ˆo. nˇa`m trˆenellipse m´oi c´otˆamta.i −P, v`anˆe´u ta v˜ed¯uo. c . . . ellipse m´oi n`ayth`ıs˜ev˜ed¯uo. c ellipse ban d¯ˆa`u. V`ı A, B, C khˆongthay d¯ˆo˙’i qua ph´epti.nh 0 0 tiˆe´n, nˆend¯ˆe˙’ gia˙’n tiˆe.n, ta s˜ek´ıhiˆe.u D v`a C thay cho D ,C (trong d¯´o D v`a E ban d¯ˆa`u bˇa`ng 0). Tiˆe´n tr`ınhtiˆe´p theo l`av˜eellipse. Ch´ungta chia th`anht´am cung v˜e. C´accung v˜echo . . . biˆe´t hu´ong di chuyˆe˙’n trong thuˆa.t to´an.Trong cung th´u nhˆa´t ta di chuyˆe˙’n sang pha˙’i v`adi . chuyˆe˙’n ch´eolˆen.C´ohai c´ach di chuyˆe˙’n, go.i l`a di chuyˆe˙’n b`anc`o hoˇa.c di chuyˆe˙’n ch´eo, phu. thuˆo.c v`aomˆo.t hoˇa.c ca˙’ hai to.a d¯ˆo. thay d¯ˆo˙’i. H`ınh1.11 minh ho.a t´amcung v˜e,c´accung . . . . . . . . tuong ´ung mˆo.t ellipse v`aba˙’ng chı˙’ ra hu´ong di chuyˆe˙’n trong mˆo˜i tru`ong ho. p. . . . . Thuˆa.t to´andu´oi d¯ˆaychia l`amhai bu´oc lˇa.p kh´acnhau - mˆo.t lˆa`n theo c´accung d¯´anh . sˆo´ le˙’, kˆe´t th´uckhi d¯a.t d¯ˆe´n biˆencung ch´eov`amˆo.t d¯ˆo´i v´oi c´accung chˇa˜n, kˆe´t th´uckhi d¯a.t . . d¯ˆe´n biˆenb`anc`o.D- ˆe˙’ x´acd¯i.nh c´accung kho˙’ i d¯ˆa`u, ta nhˆa.n x´etrˇa`ng vector gradient à ∂f ả à ả ∂x 2Ax + By + D ∇f(x, y) := ∂f = ∂y Bx + 2Cy + E . . . . vuˆongg´ocv´oi tiˆe´p tuyˆe´n cu˙’a conic ta.i d¯iˆe˙’m d¯uo. c t´ınh. Ch´ungta su˙’ du. ng c´acto.a d¯ˆo. ˙’ ∂f ∂f t ˙’ . . ˙’ ` 0 . . cua vector ∇f(x, y) = ( ∂x , ∂y ) d¯ˆe x´acd¯i.nh hu´ong di chuyˆen (bˇang c´ach quay 90 nguo. c chiˆe` u kim d¯ˆo`ng hˆo`) v`ado d¯´ohu.´o.ng di chuyˆe˙’n cu˙’a cung v˜e.V`ıd¯iˆe˙’m bˇa´t d¯ˆa`u l`a(0, 0) nˆen ∇f(0, 0) = (D, E). Thu˙’ tu. c GetOctant() nhˇa`m phˆanloa.i c´accung xuˆa´t ph´attheo vector n`ay. char GetOctant(int D, int E) { if ((D > 0) && (E 0 tu.o.ng ´u.ng bˆenngo`aiellipse . . . nˆen d < 0 khi ellipse d¯iph´ıango`aid¯iˆe˙’m gi˜ua v`ado d¯´ota cho.n d¯iˆe˙’m ngo`ai;nguo. c la.i khi 37
. d > 0 ta cho.n d¯iˆe˙’m trong; v´oi d = 0, cho.n mˆo.t trong hai. C´othˆe˙’ cho.n theo c´ach cu˙’a Van Aken: d¯ˆo´i v´o.i c´accung d¯´anhsˆo´ le˙’ ta s˜edi chuyˆe˙’n b`anc`o. khi d < 0 v`adi chuyˆe˙’n ch´eonˆe´u . . . . . . nguo. c la.i. V´oi c´accung d¯´anhsˆo´ chˇa˜n, ta di chuyˆe˙’n ch´eokhi d < 0 v`ab`anc`o nˆe´u nguo. c la.i. . . . . . . . . Trong cung th´u nhˆa´t, gia˙’ su˙’ o˙’ bu´oc th´u i ta cho.n d¯uo. c pixel tˆo´t nhˆa´t C := (xi, yi). . K´yhiˆe.u di l`agi´atri. quyˆe´t d¯i.nh cho.n gi˜ua R := (xi + 1, yi) v`a D := (xi + 1, yi + 1). K´yhiˆe.u . . . . ui+1 v`a vi+1 l`ac´acd¯a.i luo. ng cˆo.ng v`ao di d¯ˆe˙’ ta.o di+1. Khi d¯´och´ungta cˆa`n thu. c hiˆe.n v´oi mˆo˜i pixel l`a 1. D- ˇa.t d¯iˆe˙’m v˜eta.i pixel (xi, yi); . 2. Cho.n pixel kˆe´ tiˆe´p (xi+1, yi+1) du. a trˆen di; . . . . . . . 3. Cˆa.p nhˆa.t ui+1 v`a vi+1 t`u ui, vi trˆenco so˙’ cho.n lu. a o˙’ Bu´oc 2; . . 4. Cˆa.p nhˆa.t di+1 t`u di du. a trˆen ui+1 hoˇa.c vi+1; 5. Kiˆe˙’m tra thay d¯ˆo˙’i cung v˜e. . . . . Nhˇa´c la.i l`a di+1 c´othˆe˙’ d¯uo. c t´ınht`u di bˇa`ng k˜ythuˆa.t sai phˆan.Gia˙’ thiˆe´t l`ad¯ango˙’ cung ` ˙’ ´ ´ ´ ´ 1 ˙’ v˜ed¯ˆau tiˆen,d¯iˆem v˜etˆot nhˆat l`a(xi, yi) v`ata c´obiˆen quyˆet d¯i.nh di = f(xi + 1, yi + 2 ) d¯ˆe . cho.n pixel kˆe´ tiˆe´p. Nˆe´u di di chuyˆe˙’n theo b`anc`o th`ı xi+1 = xi + 1 v`a yi+1 = yi. Do d¯´obiˆe´n ´ . 1 quyˆet d¯i.nh m´oi di+1 = f(xi + 2, yi + 2 ).Suy ra ui+1 = di+1 − di 1 1 = A(x + 2)2 + B(x + 2)(y + ) + C(y + )2 i i i 2 i 2 1 +D(x + 2) + E(y + ) + F i i 2 1 1 −A(x + 1)2 + B(x + 1)(y + ) + C(y + )2 i i i 2 i 2 1 +D(x + 1) + E(y + ) + F i i 2 1 = A[2(x + 1) + 1] + B(y + ) + D i i 2 1 = A(2x + 1) + B(y + ) + D + 2A. i i 2 ´ ˙’ . . 3 . . Mˇa.t kh´ac,nˆeu di chuyˆen theo hu´ong ch´eoth`ı di = f(xi + 2, yi + 2 ) v`abu´oc tˇangl`a vi+1 = di+1 − di B = (2A + B)x + (B + 2C)y + A + + D + E i+1 i+1 2 B = (2A + B)x + (B + 2C)y + A + + D + E + [2A + 2B + 2C]. i i 2 38
Nˆe´u d¯ˇa.t 1 u = A(2x + 1) + B(y + ) + D i i i 2 . . . . . th`ıv´oi viˆe.c di chuyˆe˙’n b`anc`o ta c´o ui+1 = ui + 2A. Tuong tu. , nˆe´u d¯ˇa.t B v = (2A + B)x + (B + 2C)y + A + + D + E i i i 2 th`ıkhi di chuyˆe˙’n ch´eota c´o vi+1 = vi + (2A + 2B + 2C). . . . . . D- ˆe˙’ luu gi˜u nh˜ung gi´atri. ui v`a vi d¯ˆo´i v´oi hai c´ach di chuyˆe˙’n b`anc`o v`ach´eo,ta cˆa`n . . . . cˆa.p nhˆa.t nh˜ung gi´atri. n`aykˆe˙’ ca˙’ khi ch´ungkhˆongd¯uo. c su˙’ du. ng. Do d¯´o, • v´o.i di chuyˆe˙’n b`anc`o. vi+1 = (2A + B)xi+1 + (B + 2C)yi+1 + A + B/2 + D + E = (2A + B)(xi + 1) + (B + 2C)yi + A + B/2 + D + E = vi + 2A + B; • d¯ˆo´i v´o.i di chuyˆe˙’n ch´eo, ui+1 = ui + 2A + B. D- ˇa.t k1 := 2A, k2 := 2A + B, v`a k3 := 2A + 2B + 2C. Khi d¯´ota c´othu˙’ tu. c cˆa.p nhˆa.t c´acbiˆe´n u v`a v nhu. sau: • Di chuyˆe˙’n b`anc`o. ui+1 = ui + k1, vi+1 = vi + k2. • Di chuyˆe˙’n ch´eo ui+1 = ui + k2, vi+1 = vi + k3. . ˙’ ` ´ 1 Bˆaygi`o kha˙’o s´atviˆe.c thay d¯ˆoi cung v˜e.Nhˆaà .nả x´etrˇang ch´ungta kˆet th´ucv˜ecung (E ) . 1 khi vector gradient ∇f(x, y) ty˙’ lˆe. v´oi vector . N´oic´ach kh´ac,ch´ungta kˆe´t th´ucv˜e −1 cung (E1) khi tˆo˙’ng cu˙’a hai th`anhphˆa`n cu˙’a vector ∇f(x, y) bˇa`ng khˆong(H`ınh1.12). Mˇa.t kh´ac,dˆe˜ d`angkiˆe˙’m tra rˇa`ng ∂f k ∂f ∂f k = u − 2 , + = v − 2 . ∂x i 2 ∂y ∂y i 2 39
. . . . 2 . . . . . . . . ` ˙’ . 1 Vector n`aynˇam trˆend¯u`ong thˇang c´ohˆe sˆo´ g´oc-1 . . . . . . H`ınh1.12: Trong cung th´u. nhˆa´t, tˆo˙’ng c´acth`anhphˆa`n cu˙’a vector gradient ˆam.Khi d¯iv`ao cung th´u. hai, tˆo˙’ng n`ayd¯ˆo˙’i dˆa´u. ´ ˙’ ˙’ . k2 ´ ´ 1 . . . Do d¯´o,dˆau cua biˆeu th´uc vi − 2 cho biˆet d¯˜akˆet th´ucv˜ecung (E ) hay chua. Tuong . ´ 2 ˙’. ´ k2 tu. , kˆet th´ucv˜ecung (E ) x´acd¯i.nh boi dˆau ui − 2 . . Kˆe´ tiˆe´p ch´ungta cˆa`n x´acd¯i.nh c´acbiˆe´n quyˆe´t d¯i.nh di v`a ui, vi cu˙’a cung th´u hai khi ta kˆe´t th´uccung th´u. nhˆa´t; ch´ungvˆa˜n tu.o.ng ´u.ng v´o.i c´acbiˆe´n tˇangd¯ˆo´i v´o.i di chuyˆe˙’n ch´eo . . . . . . . v`ab`anc`o. Nhung c´acdi chuyˆe˙’n b`anc`o bˆaygi`o l`ad¯´ung thay v`ıngang v`a di d¯uo. c x´acd¯i.nh ˙’. 1 1 boi f(xi + 2 , yi + 1) thay cho f(xi + 1, yi + 2 ). 0 0 0 . . K´yhiˆe.u di, ui, vi trong v`ungth´u hai thay cho di, ui, vi (v´oi c`ung´yngh˜ıa). Dˆe˜ d`ang kiˆe˙’m tra rˇa`ng 0 1 1 d − d = f(x + , y + 1) − f(x + 1, y + ) i i i 2 i i i 2 v 3 1 = i − u + k − k , 2 i 8 3 2 2 0 B v − v = (2A + B)x + (B + 2C)y + + C + D + E i i i i 2 B −(2A + B)x (B + 2C)y + A + + D + E i i 2 = −A + C, 0 k k u − u = v − u − 2 + 3 . i i i i 2 2 Ho.n n˜u.a, 0 0 0 k3 = k3, k2 = k3 − k2, k1 = k1 − 2k2 + k3. . Nhu vˆa.y ch´ungta d¯˜ac´oc´acd¯iˆe` u cˆa`n thiˆe´t d¯ˆe˙’ v˜eellipse, ´ıtnhˆa´t l`ahai cung. Ch´ungta bao . . h`amhˆe. sˆo´ F (th`anhphˆa`n hˇa`ng trong phuong tr`ınhx´acd¯i.nh conic) trong d¯oa.n m˜amˇa.c d`u . . d¯anggia˙’ su˙’ n´obˇa`ng 0; v´oi conic tˆo˙’ng qu´at,tˆamc´othˆe˙’ c´oto.a d¯ˆo. khˆongnguyˆenv`ado d¯´o . . . d¯iˆe˙’m bˇa´t d¯ˆa`u (d¯ˆe˙’ v˜e)c´othˆe˙’ khˆongnˇa`m trˆenellipse (trong tru`ong ho. p n`ay F c´othˆe˙’ kh´ac 0). 40
. . Sau d¯oa.n m˜aminh ho.a thuˆa.t to´antrong chuong tr`ınhConic.cpp l`athu˙’ tu. c Conjugate() . . nhˇa`m x´acd¯i.nh c´achˆe. sˆo´ cu˙’a mˆo.t ellipse (tˆamta.i gˆo´c to.a d¯ˆo.) t`u c´acd¯iˆe˙’m liˆenho. p P v`a Q : H`ınhb`ınhh`anhc´oc´acd¯ı˙’nh l`a P + Q, P − Q, −P − Q v`a −P + Q bao quanh ellipse v`a . ellipse tiˆe´p x´ucv´oi c´acca.nh cu˙’a h`ınhb`ınhh`anh. D- oa.n m˜akˆe´t th´uckhi d¯ihˆe´t cung cuˆo´i c`ung.D- ˆe˙’ v˜eellipse kh´epk´ın,cˆa`n d¯ˆe´m sˆo´ c´ac . . . bu´oc di chuyˆe˙’n cˆa`n thiˆe´t d¯ˆe˙’ d¯a.t t´oi pixel xuˆa´t ph´at(b`aitˆa.p). void Conic (long xs, long ys, long xe, long ye) { long x, y; long octant, octantCount; int dxsquare, dysquare, dxdiag, dydiag; long d, u, v, k1, k2, k3; long dfdx, dfdy; long tmp; octant = GetOctant(D, E); switch (octant) { case 1: { d = round(A + B/2 + C/4 + D + E/2 + F); u = round(A + B/2 + D); v = round(A + B/2 + D + E); k1 = 2*A; k2 = (2*A + B); k3 = k2 + B + 2*C; dxsquare = 1; dysquare = 0; dxdiag = 1; dydiag = 1; break; } case 2: { 41
d = round(A/4 + B/2 + C + D/2 + E + F); u = round(B/2 + C + E); v = round(B/2 + C + D + E); k1 = 2*C; k2 = B + 2*C; k3 = 2*A + 2*B + 2*C; dxsquare = 0; dysquare = 1; dxdiag = 1; dydiag = 1; break; } } x = xe - xs; y = ye - ys; dfdx = (2*A*x + B*y + D); dfdy = (B*x + 2*C*y + E); octantCount = GetOctant(dfdx, dfdy) - octant; if (octantCount 0) { if (octant % 2) { while (v <= k2/2) { putpixel(x, y, Value); if (d < 0) { x += dxsquare; y += dysquare; u += k1; v += k2; 42
d += u; } else { x += dxdiag; y += dydiag; u += k2; v += k3; d += v; } } d += v/2 - u + 3*k3/8 - k2/2; u = -u + v + k3/2 - k2/2; v += k3/2 - k2; k1 = k1 - 2*k2 + k3; k2 = k3 - k2; tmp = dxsquare; dxsquare = -dysquare; dysquare = tmp; } else { while (u < k2/2) { putpixel(x, y, Value); if (d < 0) { x += dxdiag; y += dydiag; u += k2; v += k3; d += v; } else { x += dxsquare; y += dysquare; 43
u += k1; v += k2; d += u; } } d = d + u - v + k1 - k2; v = 2*u - v + k1 -k2; u = u + k1 - k2; k3 = 4*(k1 - k2) + k3; k2 = 2*k1 - k2; tmp = dxdiag; dxdiag = -dydiag; dydiag = tmp; } octant++; if (octant > 8) octant -= 8; octantCount ; } } void Conjugate (long xp, long yp, long xq, long yq) { long xprod, tmp, xe, ye; xprod = xp*yq - xq*yp; if (xprod != 0) { if (xprod < 0) { tmp = xp; xp = xq; xq = tmp; tmp = yp; yp = yq; yq = tmp; xprod = -xprod; } A = yp*yp + yq*yq; B = -2*(xp*yp + xq*yq); 44
C = xp*xp + xq*xq; D = 2*yq*xprod; E = -2*xq*xprod; F = 0; xe = xp; ye = yp; Conic(xp, yp, xe, ye); } } . D- iˆe` u d¯´angnga.c nhiˆenl`ad¯oa.n m˜acˆa.p nhˆa.t c´acgi´atri. trong hai cung v˜ed¯ˆa`u tiˆenc˜ungthu. c . . . . hiˆe.n d¯´ungv´oi c´accung v˜ec`onla.i. Cuˆo´i c`ung,nhu trong H`ınh1.13, d¯ˆoikhi mˆo.t bu´oc di chuyˆe˙’n ch´eotrong thuˆa.t to´anbˇangqua ph´ıabˆenkia cu˙’a ellipse; ngh˜ıal`an´othay d¯ˆo˙’i nhiˆe` u . cung v˜eta.i mˆo.t th`oi d¯iˆe˙’m. Khi d¯iˆe` u n`ayxa˙’y ra, thuˆa.t to´anta.o ra mˆo.t d˜ayc´acpixel ra kho˙’i . . qu˜yd¯a.o cu˙’a ellipse. Nhˆa.n x´etrˇa`ng d¯ˆayl`amˆo.t da.ng cu˙’a aliasing-t´ınhhiˆe.u f(x, y) d¯uo. c lˆa´y mˆa˜u ch´u.a c´actˆa`n sˆo´ rˆa´t cao chuyˆe˙’n th`anhc´acd¯iˆe˙’m nguyˆen. . . . Pratt d¯ˆe` xuˆa´t mˆo.t phuong ´angi´aiquyˆe´t nhu sau [18]. Trong khi thuˆa.t to´andi chuyˆe˙’n . . . . . . . trong cung v˜eth´u nhˆa´t, viˆe.c bˇangch´eoqua ellipse s˜etuong ´ung su. thay d¯ˆo˙’i nhanh hu´ong . cu˙’a vector gradient. Thˆa.t vˆa.y, trong cung v˜eth´u nhˆa´t vector gradient luˆonluˆonc´oth`anh . . phˆa`n theo y ˆamv`ath`anhphˆa`n theo x duong. Sau khi bˇangqua ellipse, ta s˜ed¯ˆe´n mˆo.t d¯iˆe˙’m . . . trong cung v˜e3, 4, 5 hoˇa.c 6. Ch´ungta x´acd¯i.nh d¯u`ong thˇa˙’ng phˆanc´ach gi˜ua c´accung v˜en`ayv`ac´accung v˜e7, 8, 1 v`a2 bˇa`ng c´ach cho th`anhphˆa`n x cu˙’a vector gradient bˇa`ng . . khˆong-t´uc l`a2Ax + By + D = 0. V`ı ui = 2Axi + Byi + D + A + B/2 nˆenc´othˆe˙’ su˙’ du. ng . . . . . . biˆe´n ui d¯ˆe˙’ x´acd¯i.nh hiˆe.n tuo. ng bˇangch´eoxa˙’y ra. L´yluˆa.n tuong tu. v´oi c´accung v˜ekh´ac. D- ˆe˙’ c´othˆemthˆongtin vˆe` c´acthuˆa.t to´anv˜econic, xem Pitt1, [18], [6]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y. y. y. y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H`ınh1.13: Thuˆa.t to´ansai trong tru`ong ho. p ellipse he.p. . . . . . Wu v`aRokne [28] xˆaydu. ng mˆo.t phuong ph´apkh´acv˜econic ph`uho. p v´oi thiˆe´t bi. hiˆe˙’n 45
. . thi. c´acm´uc x´am. Thay cho viˆe.c tˇangmˆo.t pixel ta.i mˆo.t th`oi d¯iˆe˙’m, thuˆa.t to´antˇangmˆo.t . khˆo´i c´acpixel. Gia˙’ su˙’ ch´ungta di chuyˆe˙’n theo chiˆe` u ngang v`ad¯ˆo. cong lˆo`i lˆen.Nˆe´u ch´ung . . ta d¯˜av˜epixel (x, y) v`asau hai bu´oc lˇa.p ch´ungta v˜epixel (x + 2, y + 2) th`ıpixel trung gian . . . . . . . d¯uo. c nˆo.i suy l`a(x + 1, y + 1). Tuong tu. , nˆe´u sau hai bu´oc lˇa.p ta v˜epixel (x + 2, y) th`ıpixel . . . . trung gian d¯uo. c nˆo.i suy l`a(x + 1, y). Nˆe´u sau hai bu´oc lˇa.p l`apixel (x + 2, y + 1) th`ıcˆa`n cho.n mˆo.t trong hai pixel (x + 1, y) hoˇa.c (x + 1, y + 1). Trˆenm`anh`ınhgi´atri. x´am,ch´ungta . . . . . . . c´othˆe˙’ hiˆe˙’n thi. ca˙’ hai pixel n`aynhung v´oi cu`ong d¯ˆo. s´angmˆo.t nu˙’ a. Do d¯´ota.i mˆo˜i bu´oc lˇa.p, . . ta v˜ehai pixel c`ungmˆo.t l´ucv`av`ıvˆa.y gia˙’m th`oi gian thu. c hiˆe.n t´ınhto´an.Ta.i chˆo˜ nˆo´i cu˙’a hai cung v˜e,thuˆa.t to´ancˆa`n tr´anhviˆe.c v˜echˆo`ng lˆennhau v`akhˆongqu´akh´od¯ˆe˙’ gia˙’i quyˆe´t . . . . d¯iˆe` u n`ay. Hiˆe˙’n nhiˆenthuˆa.t to´anchı˙’ ph`uho. p v´oi nh˜ung thiˆe´t bi. hiˆe˙’n thi. gi´atri. x´am,nhung . . n´ominh ho.a c´othˆe˙’ d¯on gia˙’n ho´aqu´atr`ınhxu˙’ l´ykhi c´othˆe˙’ ´apdu. ng k˜ythuˆa.t antialiasing. 46
Chu.o.ng 2 . . H`ınhho.c cu˙’a c´acd¯u`ong cong v`amˇa.t cong . . . . . . Mu. c d¯´ıch ch´ınhcu˙’a chuong n`ayl`atr`ınhb`ayc´acphuong ph´apv˜ed¯u`ong cong Bezier v`a . . . . . . . B-spline. D- ˆayl`ahai d¯u`ong cong thu`ong d¯uo. c su˙’ du. ng trong c´acphˆa`n mˆe` m d¯ˆo` ho.a. 2.1 Mo˙’. d¯ˆa` u . . . . . . Chuong n`aytr`ınhb`ayphuong ph´aph`ınhho.c nhˇa`m phˆant´ıch v`athiˆe´t kˆe´ c´acd¯u`ong cong . . . . v`amˇa.t cong du´oi da.ng c´acphuong tr`ınhtham sˆo´ v`ado d¯´ocho ph´epdˆe˜ d`angv˜en´o. . . . . . . . . . . Nguo. c v´oi c´acd¯u`ong cong v`amˇa.t cong du. a trˆenc´acphuong tr`ınhto´anho.c tuong . . . d¯ˆo´i d¯on gia˙’n nhu ellipse cho bo˙’ i P (t) = (a cos(2πt), b sin(2πt)), c´accˆongcu. m`ach´ungta . . . . . . . tr`ınhb`aydu´oi d¯ˆaycho ph´epngu`oi thiˆe´t kˆe´ xˆaydu. ng nh˜ung h`ınhda.ng kh´acnhau du. a trˆen . . . . d˜u liˆe.u cho tru´oc v`ac´othˆe˙’ d¯iˆe` u khiˆe˙’n ch´ungmˆo.t c´ach dˆe˜ d`angthˆongqua mˆo.t tˆa.p nh˜ung . . . d¯iˆe˙’m m`ata go.i l`ac´ac“d¯iˆe˙’m d¯iˆe` u khiˆe˙’n”. Viˆe.c xˆaydu. ng mˆo.t d¯u`ong cong (hay mˇa.t cong) . . . . . tu`y´yl`arˆa´t kh´onˆe´u khˆongbiˆe´t tru´oc phuong tr`ınhx´acd¯i.nh n´o.Tuy nhiˆen,v´oi c´ach tiˆe´p . . . cˆa.n m´oi, ta c´othˆe˙’ ta.o ra nh˜ung h`ınhda.ng mong muˆo´n bˇa`ng c´ach chı˙’nh, su˙’ a vi. tr´ıc´acd¯iˆe˙’m . . . . . . d¯iˆe` u khiˆe˙’n-d¯iˆe` u n`aythu. c hiˆe.n dˆe˜ d`angbˇa`ng qu´atr`ınhtuong t´acgi˜ua ngu`oi thiˆe´t kˆe´ v`a m´ayt´ınh. . . . . . . . . Phuong ph´apxˆaydu. ng d¯u`ong cong o˙’ d¯ˆayl`amˆo.t nhˆantˆo´ co ba˙’n trong l˜anhvu. c ´ap du. ng m´ayt´ınhv`aothiˆe´t kˆe´ c´acmˆa˜u h`ınhho.c (computer aided geometric design-CAGD) v`a . . . . . . thu`ong d`ungtrong cˆongnghˆe. chˆe´ ta.o. Chuong n`ayd¯ˆe` cˆa.p mˆo.t sˆo´ phuong ph´apthiˆe´t kˆe´ 47
. . . c´acd¯u`ong cong v`amˇa.t cong. C´onhiˆe` u c´ach tiˆe´p cˆa.n (xem, chˇa˙’ng ha.n [1], [7], [8]), nhung . . . . . . . o˙’ d¯ˆaycho.n viˆe.c thiˆe´t kˆe´ su˙’ du. ng c´acd¯u`ong cong Bezier v`aB-spline. L´op d¯u`ong cong n`ay . rˆa´t quen thuˆo.c trong c´ac´ung du. ng CAD (computer-aided design) . D- ˆe˙’ d¯o.n gia˙’n, ch´ungta bˇa´t d¯ˆa`u v´o.i c´acd¯u.`o.ng cong phˇa˙’ng P (t) = (x(t), y(t)) v`asau . . . . d¯´omo˙’ rˆo.ng cho nh˜ung mˇa.t cong (c´acd¯u`ong cong ba chiˆe` u P (t) = (x(t), y(t), z(t)) dˆe˜ d`ang suy ra t`u. d¯´o). 2.2 D- u.`o.ng cong Bezier . . . Ch´ungta s˜etr`ınhb`aythuˆa.t to´ande Casteljau (xem [7]) xˆaydu. ng mˆo.t c´ach h`ınhho.c d¯u`ong . . . cong P (t) du. a trˆenmˆo.t tˆa.p c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n. Phuong ph´apn`aydˆe˜ d`angsuy ra c´ac . . . . . . d¯u`ong cong Bezier-l`anh˜ung d¯ˆo´i tuo. ng co ba˙’n trong CAGD. De Casteljau (nˇam1959), d¯ˆo.c . . . . . . lˆa.p v´oi Bezier (nˇam1962), d¯ua ra phuong ph´apthiˆe´t kˆe´ mˆo.t d¯u`ong cong m`asau n`aygo.i l`a . . . . . . . d¯u`ong cong Bezier. D- u`ong cong n`ayl`anh˜ung th`anhphˆa`n trong c´achˆe. thˆo´ng CAD d¯uo. c . su˙’ du. ng trong hai cˆongty Citroăenv`aR´enaultd¯ˆe˙’ ta.o ra c´ach`ınhda.ng bˆenngo`aicu˙’a xe ˆo tˆo. 2.2.1 Thuˆa.t to´ande Casteljau . . . Thuˆa.t to´ande Casteljau su˙’ du. ng mˆo.t d˜ayc´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n d¯ˆe˙’ xˆaydu. ng v´oi mˆo˜i gi´atri. t . . . . trong d¯oa.n [0, 1] tuong ´ung v´oi mˆo.t d¯iˆe˙’m P (t). Do d¯´othuˆa.t to´ansinh ra mˆo.t d˜ayc´acd¯iˆe˙’m . . . . . t`u mˆo.t tˆa.p c´acd¯iˆe˙’m cho tru´oc. Khi c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n thay d¯ˆo˙’i, d¯u`ong cong s˜ethay d¯ˆo˙’i . . theo. C´ach xˆaydu. ng du. a trˆenmˆo.t loa.t c´acph´epnˆo.i suy tuyˆe´n t´ınhv`ado d¯´orˆa´t dˆe˜ d`ang giao tiˆe´p. Ngo`aira, phu.o.ng ph´apc˜ungsuy ra nhiˆe` u t´ınhchˆa´t h˜u.u ´ıch cu˙’a d¯u.`o.ng cong. . Parabol du. a trˆenba d¯iˆe˙’m 2 Trong mˇa.t phˇa˙’ng R x´etba d¯iˆe˙’m P0,P1,P2. D- ˇa.t 1 P0 (t) := (1 − t)P0 + tP1, 1 P1 (t) := (1 − t)P1 + tP2, . 1 1 trong d¯´o t ∈ [0, 1]. N´oic´ach kh´ac,v´oi mˆo˜i t ∈ [0, 1], c´acd¯iˆe˙’m P0 (t) v`a P1 (t) nˇa`m trˆenc´ac . . . . d¯oa.n thˇa˙’ng P0P1 v`a P1P2 tuong ´ung. Lˇa.p la.i ph´epnˆo.i suy tuyˆe´n t´ınhtrˆenc´acd¯iˆe˙’m m´oi 48
P 1 (a) 1 P (t) 0 • . 1 2 P (t) P (t) 1 0 P0 P2 P 1 (b) • @t = 0 • @0.3 @0.5 • P0 @0.7 @ t = 1 P2 H`ınh2.1: Thuˆa.t to´ande Casteljau cho ba d¯iˆe˙’m d¯iˆe` u khiˆe˙’n. 1 1 . . . P0 (t) v`a P1 (t) (v´oi c`unggi´atri. t) ta d¯uo. c (H`ınh2.1(a)) 2 1 1 P0 (t) = (1 − t)P0 (t) + tP1 (t). 2 ˙’ . . . Qu˜yt´ıch cu˙’a P (t) := P0 (t) khi t thay d¯ˆoi trong d¯oa.n [0, 1] s˜echo ta d¯u`ong cong nhu H`ınh 2.1(b). Dˆe˜ d`angchı˙’ ra rˇa`ng 2 2 P (t) = (1 − t) P0 + 2t(1 − t)P1 + t P2. Suy ra P (t) l`ad¯u.`o.ng cong parabol theo biˆe´n t. . . . . . . . V´ıdu. 2.2.1 Phuong tr`ınhd¯u`ong cong Bezier P (t) tuong ´ung ba d¯iˆe˙’m d¯iˆe` u khiˆe˙’n P0(0, 0),P1(2, 2),P2(6, 0) l`a 2 2 P (t) = (1 − t) P0 + 2t(1 − t)P1 + t P2 = (1 − t)2(0, 0) + 2(1 − t)t(2, 2) + t2(6, 0) = (2t2 + 4t, −4t2 + 4t). . . . Tˆo˙’ng qu´atcho tru`ong ho. p sˆo´ d¯iˆe˙’m d¯iˆe` u khiˆe˙’n ≥ 3 ta c´o: 49
Thuˆa.t to´ande Casteljau cho L + 1 d¯iˆe˙’m d¯iˆe` u khiˆe˙’n 2 . . . . Trong mˇa.t phˇa˙’ng R x´et L + 1 d¯iˆe˙’m P0,P1, ,PL. V´oi mˆo˜i gi´atri. t cho tru´oc, ta xˆaydu. ng . . L . theo quy na.p d¯u`ong cong P0 (t) nhu sau: . - r . 1. [Kho˙’ i ta.o] Dˇa.t r = 0 v`a Pi (t) := Pi v´oi mo.i i = 0, 1, ,L − r. . . . 2. [Kˆe´t th´uc?]Nˆe´u r = L d`ung; nguo. c la.i d¯ˇa.t r+1 r r Pi (t) = (1 − t)Pi (t) + tPi+1(t), v´o.i i = 0, 1, ,L − r − 1. 3. Thay r bo˙’.i r + 1 v`achuyˆe˙’n sang Bu.´o.c 2. . . . . L . . . ˙’ ˙’ Kˆe´t th´uc,ta d¯uo. c d¯u`ong cong Bezier P (t) := P0 (t) tuong ´ung c´acd¯iˆem, go.i l`a d¯iˆem d¯iˆe` u . khiˆe˙’n, P0,P1, ,PL. D- a gi´acta.o bo˙’ i c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n go.i l`a d¯agi´acd¯iˆe` u khiˆe˙’n. . . . H`ınh2.2 minh ho.a d¯u`ong cong Bezier du. a trˆenbˆo´n d¯iˆe˙’m d¯iˆe` u khiˆe˙’n v`ad¯iˆe˙’m P (0.5), . . . . . . . . . tuong ´ung gi´atri. t = 0.5, trˆend¯u`ong cong ´ung v´oi t = 0.5. Hiˆe˙’n nhiˆend¯ˆayl`ad¯u`ong cong . d¯ath´uc bˆa.c ba. P2 P1 . • . P (0.5) . P3 P0 H`ınh2.2: D- u.`o.ng cong Bezier v´o.i bˆo´n d¯iˆe˙’m d¯iˆe` u khiˆe˙’n. . . V˜ed¯u`ong cong Bezier bˇa`ng thuˆa.t to´anCasteljau . Thu˙’ tu. c sau t´ınh P (t) theo thuˆa.t to´ande Casteljau du. a trˆenma˙’ng P [] gˆo`m NumV ertices d¯iˆe˙’m d¯iˆe` u khiˆe˙’n: Point2D Casteljau(float t) 50
{ Point2D Q[MaxVertices]; int i, r; for (i = 0; i <= NumVertices; i++) { Q[i].x = P[i].x; Q[i].y = P[i].y; } for (r = 1 ; r <= NumVertices; r++) { for (i = 0; i <= NumVertices - r; i++) { Q[k].x = (1 - t)*Q[k].x + t*Q[k + 1].x; Q[k].y = (1 - t)*Q[k].y + t*Q[k + 1].y; } } return(Q[0]); } . . . Nhˆa.n x´etrˇa`ng thu˙’ tu. c Casteljau() su˙’ du. ng mˆo.t ma˙’ng trung gian Q[]. Hon n˜ua, ma˙’ng n`ay . . . . . d¯uo. c kho˙’ i ta.o la.i mˆo˜i khi thu˙’ tu. c d¯uo. c go.i. Do d¯´okhˆonghiˆe.u qua˙’ trong t´ınhto´an. Mˆo.t . . . . . phuong ´annhanh hon s˜ed¯uo. c d¯ˆe` cˆa.p trong phˆa`n tiˆe´p theo. . . . . D- ˆe˙’ v˜ed¯u`ong cong Bezier, ch´ungta chı˙’ cˆa`n ´apdu. ng thu˙’ tu. c v˜ed¯u`ong cong tham sˆo´: void DrawCurve(float a, float b, int NumPoints, Function Func) { float Delta = (b - a)/(float)NumPoints; float t = a; int i; moveto(Func(t).x, Func(t).y); for (i = 1; i <= NumPoints; i++) { t += Delta; 51
lineto(Func(t).x, Func(t).y); } } . . Trong thu˙’ tu. c n`ay, miˆe` n x´acd¯i.nh cu˙’a d¯u`ong cong F unc l`ad¯oa.n [a, b]; sˆo´ d¯iˆe˙’m phˆan . . hoa.ch trˆend¯oa.n [a, b] l`a NumP oints; v`ad¯u`ong cong tham sˆo´ l`amˆo.t con tro˙’ h`amc´okiˆe˙’u Function v´o.i khai b´ao: typedef Point2D (*Function) (ﬂoat). 2.2.2 D- a th´u.c Bernstein v`ad¯u.`o.ng cong Bezier . . . . C´ach tiˆe´p cˆa.n trong phˆa`n tru´oc cho ta thuˆa.t to´anh`ınhho.c v˜ed¯u`ong cong Bezier. Phˆa`n n`aychı˙’ ra biˆe˙’u diˆe˜n gia˙’i t´ıch cu˙’a d¯u.`o.ng cong Bezier. . . . . . . Thˆa.t vˆa.y, dˆe˜ d`angch´ung minh rˇa`ng d¯u`ong cong Bezier P (t) tuong ´ung c´acd¯iˆe˙’m d¯iˆe` u . khiˆe˙’n P0,P1, ,PL, x´acd¯i.nh bo˙’ i XL L P (t) = PkBk (t), (2.1) k=0 trong d¯´o à ả L BL(t) := (1 − t)L−ktk k k à ả . . L . . v´oi k = 0, 1, . . . , L, l`ac´ac d¯ath´uc Bernstein, v`a l`atˆo˙’ ho. p chˆa.p k cu˙’a L phˆa`n tu˙’ . k . . V´ıdu. 2.2.2 T`u d¯i.nh ngh˜ıa,ta c´oc´acd¯ath´uc Bernstein bˆa.c ba: à ả 3 B3(t) = (1 − t)3t0 = (1 − t)3 0 0 à ả 3 B3(t) = (1 − t)2t1 = 3(1 − t)2t 1 1 à ả 3 B3(t) = (1 − t)1t2 = 3(1 − t)t2 2 2 à ả 3 B3(t) = (1 − t)0t3 = t3 3 3 . H`ınh2.3 minh ho.a d¯ˆo` thi. cu˙’a bˆo´n d¯ath´uc n`aykhi t ∈ [0, 1]. 52
. . . . 1 3 3 B (t) B (t) 0 3 . . . / \ . . . . . . . . . . . . . . . 3 3 . . B (t) B (t) . 1 2 . . . . . / \ . . . . . . . . . . . . . . . . . . . . . . t 0 1 . H`ınh2.3: C´acd¯ath´uc Bernstein bˆa.c ba. . . . . . . . V´ıdu. 2.2.3 Phuong tr`ınhtham sˆo´ cu˙’a d¯u`ong cong Bezier P (t) tuong ´ung bˆo´n d¯iˆe˙’m d¯iˆe` u khiˆe˙’n P0(0, 0),P1(2, 3),P2(6, 0),P3(9, 2) c´oda.ng 3 2 2 3 P (t) = (1 − t) P0 + 3(1 − t) tP1 + 3(1 − t)t P2 + t P3 = (1 − t)3(0, 0) + 3(1 − t)2t(2, 3) + 3(1 − t)t2(6, 0) + t3(9, 2) = [6(1 − t)2t + 18(1 − t)t2 + 9t3, 9(1 − t)2t + 2t3] = [6t − 12t2 + 6t3 + 18t2 − 18t3 + 9t3, 9t − 18t2 + 9t3 + 2t3] = (−3t3 + 6t2 + 6t, 11t3 − 18t2 + 9t). . L ˙’ Nhˆa.n x´etrˇa`ng c´acd¯ath´uc Bernstein Bk (t) ch´ınhl`ac´acsˆo´ ha.ng cu˙’a khai triˆen nhi. P . L L L . . . th´uc Newton cu˙’a [(1 − t) + t] . Do d¯´o k=0 Bk (t) ≡ 1 v´oi mo.i t ∈ R. Hon n˜ua . D- .inh l´y2.2.4 C´acd¯ath´uc Bernstein thoa˙’ quan hˆe. d¯ˆe. quy sau: L L−1 L−1 Bk (t) = (1 − t)Bk (t) + tBk−1 (t), 0 L . trong d¯´o B0 (t) = 1, v`a Bk (t) = 0 v´oi mo. i k∈ / {0, 1, ,L}. V˜ed¯u.`o.ng cong Bezier qua d¯ath´u.c Bernstein . . . . . . Tru´oc hˆe´t ch´ungta x´etthu˙’ tu. c xˆaydu. ng d¯u`ong cong Bezier hiˆe.u qua˙’ hon Casteljau(). . . . . . . . . Phuong ph´apdu. a trˆenluo. c d¯ˆo` Horner d¯ˆe˙’ t´ınhgi´atri. cu˙’a d¯ath´uc. Mˆo.t v´ıdu. cu˙’a luo. c d¯ˆo` 53
. . . . Horner, c`ongo.i l`a nhˆanlˆo`ng nhau, trong tru`ong ho. p d¯ath´uc bˆa.c ba: 2 3 c0 + tc1 + t c2 + t c3 = c0 + t(c1 + t(c2 + tc3)). . . . . . . Tuong tu. v´oi d¯u`ong cong Bezier (bˆa.c ba): à ả à ả à ả à ả 3 3 3 3 P 3(t) = (( sP + tP )s + t2P )s + t3P , 0 0 1 1 2 2 3 3 trong d¯´o s = 1 − t. Nhˆa.n x´etrˇa`ng à ả à ả L L − i + 1 L = ; i > 0, i i i − 1 . . L . . . Do d¯´ota c´od¯oa.n chuong tr`ınhsau t´ınhgi´atri. P (t) (tru`ong ho. p tˆo˙’ng qu´at).Trong thu˙’ tu. c n`ay, NumVertices ch´ınhl`a L + 1. Point2D Horner_Bezier(float t) { int i, L_choose_i; float Fact, s; Point2D Q; s = 1.0 - t; Fact = 1.0; L_choose_i = 1; Q.x = P[0].x*s; Q.y = P[0].y*s; for(i = 1; i < NumVertices; i++) { Fact *= t; L_choose_i *= (NumVertices - i + 1)/i; Q.x = (Q.x + Fact*L_choose_i*P[i].x)*s; Q.y = (Q.y + Fact*L_choose_i*P[i].y)*s; } Q.x += Fact*t*P[NumVertices].x; Q.y += Fact*t*P[NumVertices].y; 54
return(Q); } Nhˆa.n x´etrˇa`ng thu˙’ tu. c n`aykhˆongcˆa`n ma˙’ng trung gian; ngo`aira, Horner Bezier() c´od¯ˆo. . . 2 ph´uc ta.p t´ınhto´an O(L) trong khi Casteljau() c´od¯ˆo. ph´uc ta.p t´ınhto´an O(L ). Tuy nhiˆend¯iˆe` u n`aykhˆongc´ongh˜ıata d¯˜ac´oc´ach tˆo´t nhˆa´t v˜ed¯u.`o.ng cong Bezier. Chˇa˙’ng ha.n, ch´ungta go.i thu˙’ tu. c Horner Bezier() ta.i mˆo˜i d¯iˆe˙’m, v`ado d¯´ocˆa`n ta.o ra hˆe. sˆo´ . . . . L choose i hai lˆa`n. C´othˆe˙’ gia˙’m t´ınhto´annh`o gˆo.p hai l`oi go.i. Tˆo´t nhˆa´t l`at´ınhtru´oc mˆo.t . lˆa`n d˜ayc´achˆe. sˆo´ khai triˆe˙’n nhi. th´uc. 2.3 C´act´ınhchˆa´t cu˙’a d¯u.`o.ng cong Bezier . . . . . . D- u`ong cong Bezier c´omˆo.t sˆo´ t´ınhchˆa´t quan tro.ng v`ado d¯´othu`ong d¯uo. c d`ungtrong CAGD. . . . Viˆe.c kha˙’o s´atv`ach´ung minh c´act´ınhchˆa´t n`aycho ph´epch´ungta hiˆe˙’u sˆausˇa´c hon vˆe` l´op d¯u.`o.ng cong Bezier. D- i qua d¯iˆe˙’m d¯ˆa` u P0 v`ad¯iˆe˙’m cuˆo´i PL . . . . D- u`ong cong du. a trˆenc´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n P0,P1, ,PL khˆongd¯iqua c´acd¯iˆe˙’m n`aytr`u . . . . d¯iˆe˙’m d¯ˆa`u P0 v`ad¯iˆe˙’m cuˆo´i PL. D- ˆayl`amˆo.t t´ınhchˆa´t rˆa´t h˜uu du. ng, v`ıdu. a v`aod¯´ongu`oi thiˆe´t kˆe´ biˆe´t ch´ınhx´acd¯u.`o.ng cong Bezier s˜ebˇa´t d¯ˆa`u v`akˆe´t th´uco˙’. d¯ˆau.D- iˆe` u n`ayl`ahiˆe˙’n . nhiˆent`u thuˆa.t to´ande Casteljau. . . . . . . Ta c˜ungc´othˆe˙’ ch´ung minh t´ınhchˆa´t n`ayt`u phuong tr`ınhx´acd¯i.nh d¯u`ong cong thˆong . L L L L L qua c´acd¯ath´uc Bernstein. Thˆa.t vˆa.y do B0 (t) = (1 − t) v`a BL (t) = t , nˆen B0 (t) nhˆa.n . . . . . . L gi´atri. 1 v`a0 ta.i t = 0 v`a t = 1 tuong ´ung. Tuong tu. , BL (t) nhˆa.n gi´atri. 0 v`a1 ta.i t = 0 . . . . L v`a t = 1 tuong ´ung. Ngo`aira, tˆa´t ca˙’ c´acd¯ath´uc Bi (t), i = 1, 2, ,L − 1, nhˆa.n gi´atri. 0 ta.i t = 0 v`a t = 1. Hˆe. qua˙’ l`a P (0) = P0 v`a P (1) = PL. 55
Bˆa´t biˆe´n d¯ˆo´i v´o.i ph´epbiˆe´n d¯ˆo˙’i aﬃne X´etph´epbiˆe´n d¯ˆo˙’i aﬃne T : R2 → R2,P 7→ MP + tr, trong d¯´o M l`ama trˆa.n vuˆongcˆa´p 2 . 2 ì 2 v`a tr l`avector trong R . D- ˇa.t Q(t) = T [P (t)] v´oi mˆo˜i t ∈ [0, 1]. Dˆe˜ kiˆe˙’m tra rˇa`ng " # XL L Q(t) = M PkBk (t) + tr. k=0 . . . . N´oic´ach kh´ac,d¯u`ong cong Bezier qua ph´epbiˆe´n d¯ˆo˙’i aﬃne T c˜ungl`amˆo.t d¯u`ong cong Bezier . . . . tuong ´ung v´oi c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n Qk = MPk + tr, k = 0, 1, . . . , L,-l`ac´acd¯iˆe˙’m qua ph´ep biˆe´n d¯ˆo˙’i aﬃne T cu˙’a nh˜u.ng d¯ıˆe˙’m d¯iˆe` u khiˆe˙’n ban d¯ˆa`u. D- iˆe` u n`ayc´ongh˜ıarˇa`ng d¯u.`o.ng cong . . Bezier bˆa´t biˆe´n qua ph´epbiˆe´n d¯ˆo˙’i aﬃne. V`ıvˆa.y d¯ˆe˙’ thu. c hiˆe.n ph´epbiˆe´n d¯ˆo˙’i aﬃne d¯ˆo´i v´oi . . . . . . d¯u`ong cong Bezier, ch´ungta khˆongcˆa`n pha˙’i biˆe´n d¯ˆo˙’i t`ung d¯iˆe˙’m r`oi ra.c trˆend¯u`ong cong . . . . d¯´o,m`achı˙’ cˆa`n biˆe´n d¯ˆo˙’i aﬃne d¯ˆo´i v´oi c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n v`adu. ng d¯u`ong cong Bezier trˆen c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n m´o.i. . . . . . . V´ıdu. 2.3.1 Theo V´ıdu. 2.2.3, phuong tr`ınhtham sˆo´ cu˙’a d¯u`ong cong Bezier P (t) tuong . ´ung bˆo´n d¯iˆe˙’m d¯iˆe` u khiˆe˙’n P0(0, 0),P1(2, 3),P2(6, 0) v`a P3(9, 2) l`a P (t) = (−3t3 + 6t2 + 6t, 11t3 − 18t2 + 9t). X´etph´epbiˆe´n d¯ˆo˙’i aﬃne à ả à ả à ả 1 0 x 1 T : R2 → R2, (x, y) 7→ + . 0 −1 y 2 . . . . . . . Khi d¯´ophuong tr`ınhtham sˆo´ d¯u`ong cong Q(t) tuong ´ung bˆo´n d¯iˆe˙’m d¯iˆe` u khiˆe˙’n Qi = T (Pi) l`a à ả à ả à ả 1 0 −3t3 + 6t2 + 6t 1 Q(t) = T [P (t)] = + 0 −1 11t3 − 18t2 + 9t 2 à ả −3t3 + 6t2 + 6t + 1 = . −11t3 + 18t2 − 9t + 2 Bˆa´t biˆe´n d¯ˆo´i v´o.i ph´epbiˆe´n d¯ˆo˙’i aﬃne tham sˆo´ . . . . . C´acd¯u`ong cong Bezier x´acd¯i.nh trˆend¯oa.n [0, 1]. Tuy nhiˆen,trong mˆo.t v`aitru`ong ho. p d¯ˆe˙’ . . . . thuˆa.n tiˆe.n ta cˆa`n x´ettrˆend¯oa.n kh´ac.Gia˙’ su˙’ cˆa`n x´acd¯i.nh d¯u`ong cong Bezier v´oi c´acd¯iˆe˙’m ` ˙’ ´ ˙’. u−a . . d¯iˆeu khiˆen Pk, k = 0, 1, . . . , L, trˆend¯oa.n [a, b]. Muˆon vˆa.y, thay t boi b−a v`anhˆa.n d¯uo. c à ả XL u − a P BL , k k b − a k=0 . v´oi u thay d¯ˆo˙’i trong d¯oa.n [a, b]. 56
Bao lˆo`i Nhˇa´c la.i rˇa`ng, bao lˆo`i cu˙’a L+1 d¯iˆe˙’m d¯iˆe` u khiˆe˙’n Pk, k = 0, 1, . . . , L, k´yhiˆe.u Co(P0,P1, ,PL), . . l`atˆa.p lˆo`i nho˙’ nhˆa´t ch´ua c´acd¯iˆe˙’m n`ay. C´othˆe˙’ ch´ung minh rˇa`ng (xem [21]) ( ) XL XL . Co(P0,P1, ,PL) = λkPk | λk = 1 v`a λk ≥ 0 v´oi k = 0, 1, ,L . k=0 k=0 . . . Theo c´ach xˆaydu. ng h`ınhho.c cu˙’a thuˆa.t to´ande Casteljau, d¯u`ong cong Bezier nˇa`m . . trong bao lˆo`i cu˙’a c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n Pk, k = 0, 1, . . . , L. C˜ungc´othˆe˙’ suy tru. c tiˆe´p t`u biˆe˙’u . L ˙’ . diˆe˜n (2.1): c´acd¯ath´uc Bernstein Bk (t) khˆongˆamv`ac´otˆong bˇa`ng 1 v´oi mo.i t ∈ [0, 1]. . . . . Hˆe. qua˙’ l`anˆe´u c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n c`ungnˇa`m trˆenmˆo.t d¯u`ong thˇa˙’ng th`ıd¯u`ong cong Bezier l`amˆo.t d¯oa.n thˇa˙’ng. . M´uc d¯ˆo. dao d¯ˆo.ng b´e . . . . C´othˆe˙’ n´oid¯u`ong cong Bezier khˆongthˆe˙’ “qua mˇa.t” d¯uo. c d¯agi´acd¯iˆe` u khiˆe˙’n. Ch´ınhx´ac . . . . . . . hon, sˆo´ giao d¯iˆe˙’m cu˙’a mˆo.t d¯u`ong thˇa˙’ng bˆa´t k`yv´oi d¯u`ong cong Bezier nho˙’ hon hoˇa.c bˇa`ng . . . sˆo´ giao d¯iˆe˙’m cu˙’a d¯u`ong thˇa˙’ng d¯´ov´oi d¯agi´acd¯iˆe` u khiˆe˙’n (xem [7]). D- ˆayl`amˆo.t t´ınhchˆa´t . . . . h˜uu du. ng d¯ˆo´i v´oi c´acnh`athiˆe´t kˆe´ d¯u`ong cong: khi ho. cho.n c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n, ho. c´o . . . . . . . . . thˆe˙’ tin tuo˙’ ng rˇa`ng d¯u`ong cong d¯uo. c xˆaydu. ng t`u ch´ungkhˆonggo. n s´onglung tung hay c´o thˆemnh˜u.ng d¯u.`o.ng r˜enh´anh. . . D- a.o h`amcu˙’a d¯u`ong cong Bezier T`u. phu.o.ng tr`ınh(2.1) dˆe˜ d`angsuy ra dP (t) XL−1 = L ∆P BL−1(t), (2.2) dt k k k=0 trong d¯´o∆Pk := Pk+1 − Pk, k = 0, 1, ,L − 1. . . . . . . Do d¯´od¯a.o h`ambˆa.c nhˆa´t cu˙’a d¯u`ong cong Bezier l`amˆo.t d¯u`ong cong Bezier d¯uo. c xˆay . . . . du. ng trˆenco so˙’ cu˙’a L “vector d¯iˆe` u khiˆe˙’n” ∆Pk. Suy ra, t`u (2.2), ta c´od¯a.o h`ambˆa.c hai dP 2(t) XL−2 = L(L − 1) ∆2P BL−2(t), dt2 k k k=0 2 . . . . trong d¯´o∆ Pk = ∆Pk+1 − ∆Pk. Tuong tu. v´oi c´acd¯a.o h`amcˆa´p cao kh´ac. 57
. . . . . . . V´ıdu. 2.3.2 Theo V´ıdu. 2.2.1, phuong tr`ınhd¯u`ong cong Bezier P (t) tuong ´ung ba d¯iˆe˙’m d¯iˆe` u khiˆe˙’n P0(0, 0),P1(2, 2),P2(6, 0) l`a P (t) = (2t2 + 4t, −4t2 + 4t). Khi d¯´o P 0(t) = (4t + 4, −8t + 4). D- ˇa.c biˆe.t P 0(0) = (4, 4) v`a P 0(1) = (8, −4). Suy ra hˆe. sˆo´ ˙’ ´ ´ . . . . . . 4 −4 −1 . g´occua tiˆep tuyˆen v´oi d¯u`ong cong P (t) ta.i P0 v`a P2 tuong ´ung l`a 4 = 1 v`a 8 = 2 . T`u . . . . . . . d¯´oc´ophuong tr`ınhtiˆe´p tuyˆe´n v´oi d¯u`ong cong P (t) ta.i P0 l`a y = x v`aphuong tr`ınhtiˆe´p ´ . . . 1 ˜ ˙’ . . tuyˆen v´oi d¯u`ong cong P (t) ta.i P2 l`a y = − 2 x + 3. Dˆe kiˆem tra d¯´och´ınhl`ac´acphuong tr`ınh . . . . . d¯u`ong thˇa˙’ng qua P0,P1 v`a P1,P2 tuong ´ung. . . Da.ng ma trˆa.n cu˙’a d¯u`ong cong Bezier . . . Ch´ungta c´othˆe˙’ biˆe˙’u diˆe˜n d¯u`ong cong Bezier o˙’ da.ng ma trˆa.n (xem [8], [9]) rˆa´t thuˆa.n tiˆe.n khi xu˙’. l´yd¯u.`o.ng cong trˆenm´ayt´ınh. - L L L L t L+1 t Dˇa.t B (t) := (B0 (t),B1 (t), ,BL (t)) l`avector cˆo.t trong R , v`a P := (P0,P1, ,PL) l`ama trˆa.n cˆa´p (L + 1) ì 2. Khi d¯´ota c´othˆe˙’ viˆe´t P (t) = [BL(t)]tP. . . . . Mˇa.t kh´ac,theo d¯i.nh ngh˜ıa,c´acd¯ath´uc Bernstein c´othˆe˙’ viˆe´t o˙’ da.ng t´ıch vˆohu´ong. Chˇa˙’ng ha.n 3 2 0 1 2 3 t t B2 (t) = 3(1 − t)t = h(t , t , t , t ) , (0, 0, 3, −3) i. . L . . . L 0 1 L t Ngo`aira, mˆo˜i d¯ath´uc Bk (t) c´oc`ungmˆo.t vector co so˙’ l˜uyth`ua P ow (t) := (t , t , . . . , t ) . L . . . . L V`ıvˆa.y, ma˙’ng B (t) c´othˆe˙’ viˆe´t da.ng t´ıch cu˙’a vector co so˙’ l˜uyth`ua v´oi ma trˆa.n Bez nhˆa.n . . . . . . L . d¯uo. c t`u c´acvector n`aod¯´o(d¯ˆoimˆo.t kh´acnhau) tuong ´ung Bk (t). V´oi L = 3 ta c´o B3(t) = (t0, t1, t2, t3)Bez3, trong d¯´o   1 0 0 0    −3 3 0 0  Bez3 =   .  3 −6 3 0  −1 3 −3 1 Tˆo˙’ng qu´atta c´othˆe˙’ viˆe´t P (t) = [P owL(t)]tBezLP, (2.3) 58
L . . . trong d¯´o Bez l`ama trˆa.n cˆa´p (L + 1) ì (L + 1) v´oi phˆa`n tu˙’ h`ang i cˆo.t j x´acd¯i.nh bo˙’ i à ả à ả j−i n i mij := (−1) . i j . . . . . Nhˆa.n x´etrˇa`ng, khi ta muˆo´n thiˆe´t kˆe´ d¯u`ong cong v´oi c´acd¯ath´uc kh´acd¯ath´uc . . Bernstein, ta c˜ungnhˆa.n d¯uo. c c`ungmˆo.t biˆe˙’u diˆe˜n (2.3) (xem [8], [9]). . . 2.3.1 D- iˆe` u khiˆe˙’n d¯i.a phuong . . . . . D- u`ong cong Bezier l`amˆo.t cˆongcu. h˜uu ´ıch trong thiˆe´t kˆe´ c´acd¯u`ong cong. Bˇa`ng c´ach d¯ˇa.t . . c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n trong mˇa.t phˇa˙’ng, thˆa.m ch´ıtrong khˆonggian, ta c´oc´acd¯u`ong cong . . . . . . . . tron. Ngu`oi su˙’ du. ng quan s´atd¯u`ong cong d¯uo. c sinh ra v`ad¯iˆe` u khiˆe˙’n vi. tr´ıcu˙’a ch´ungd¯ˆe˙’ . . . . . . . c´omˆo.t d´angd¯iˆe.u th´ıch ho. p hon. Su. tuong t´acn`aytiˆe´p tu. c cho d¯ˆe´n khi to`anbˆo. d¯u`ong cong thoa˙’ m˜anmu. c d¯´ıch thiˆe´t kˆe´. . . . . Nhˆa.n x´etrˇa`ng d¯u`ong cong Bezier d¯uo. c d¯iˆe` u khiˆe˙’n mˆo.t c´ach “to`ancu. c”; ngh˜ıal`akhi . . . . thay d¯ˆo˙’i mˆo.t d¯iˆe˙’m d¯iˆe` u khiˆe˙’n th`ıto`anbˆo. d¯u`ong cong bi. thay d¯ˆo˙’i theo. Khˇa˙’ng d¯i.nh d¯uo. c . . . . suy t`u d¯i.nh ngh˜ıacu˙’a c´acd¯ath´uc Bernstein. Thˆa.t vˆa.y, c´acd¯ath´uc n`ayl`a“t´ıch cu. c” (kh´ac . . . khˆong)trˆento`and¯oa.n [0, 1]. Mˇa.t kh´ac,d¯u`ong cong Bezier l`atˆo˙’ ho. p cu˙’a c´acd¯iˆe˙’m d¯iˆe` u . . . . . khiˆe˙’n d¯uo. c “trˆo.n” v´oi c´ach`amBernstein. Do vˆa.y, mˆo˜i d¯iˆe˙’m d¯iˆe` u khiˆe˙’n c´oa˙’nh huo˙’ ng trˆen . . to`anbˆo. d¯u`ong cong. . . . . Trong thu. c tˆe´, ta muˆo´n d¯iˆe` u khiˆe˙’n mˆo.t c´ach d¯i.a phuong. Nhu trong H`ınh2.4(a), mˆo.t . . . sˆo´ d¯oa.n cong cu˙’a d¯u`ong cong Bezier ph`uho. p yˆeucˆa`u, trong khi phˆa`n kh´accˆa`n pha˙’i chı˙’nh . . . . su˙’ a la.i. D- u`ong cong Bezier n`aydu. a trˆennˇamd¯iˆe˙’m d¯iˆe` u khiˆe˙’n; phˆa`n liˆe` n n´etgˆa`n gi´atri. . . . . . t = 0 tr`ungv´oi yˆeucˆa`u, nhung d¯oa.n gˆa`n t = 1 th`ıkhˆong.Ngu`oi su˙’ du. ng muˆo´n di chuyˆe˙’n . . . hai d¯iˆe˙’m d¯iˆe` u khiˆe˙’n P2 v`a P3 d¯ˆe˙’ d¯iˆe` u khiˆe˙’n d¯oa.n cong n`aycho ph`uho. p. Nhung, nhu chı˙’ ra trong H`ınh2.4(b), d¯iˆe` u n`ayl`ama˙’nh hu.o˙’.ng d¯ˆe´n nu˙’.a d¯ˆa`u cu˙’a d¯u.`o.ng cong. . . . . . T´ınhchˆa´t thay d¯ˆo˙’i to`ancu. c ´ıtth´ıch ho. p trong thu. c tˆe´. V`ıvˆa.y d¯ˆe˙’ c´onh˜ung a˙’nh huo˙’ ng . . . . d¯i.a phuong trˆend¯u`ong cong khi thay d¯ˆo˙’i c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n ta x´ettˆa.p c´ach`am“trˆo.n” 1 kh´ac.V´ıdu. c´ach`amtrˆo.n R0(t),R1(t), ,R5(t) trong H`ınh2.5(a). Mˆo˜i h`amtrˆo.n c´ogi´a . . ch´ua trong d¯oa.n [0, 1]. Chˇa˙’ng ha.n, suppR0 = [0, 0.3] v`asuppR3 = [0.3, 1.0]. Ta.i th`oi d¯iˆe˙’m t 1Gi´a cu˙’a h`am f: Rn → R, k´yhiˆe.u suppf, l`abao d¯´ongcu˙’a tˆa.p {x ∈ Rn | f(x) 6= 0}. Theo d¯i.nh ngh˜ıa, h`am f bˇa`ng khˆongngo`aitˆa.p suppf. 59
P1 P4 . (a) • • \ Mong muˆo´n Hiˆen tai . . \ . • • P2 P3 • P0 P1 P4 . (b) • • \ Hiˆen tai . . Mong muˆo´n \ • • P2 P3 • P0 . . . H`ınh2.4: Su˙’ a c´acphˆa`n cu˙’a mˆo.t d¯u`ong cong. . . . . . . . bˆa´t k`ykhˆongc´ohon ba h`amtrˆo.n t´ıch cu. c. X´etd¯u`ong cong tuong ´ung c´ach`amtrˆo.n n`ay: X5 P (t) := PkRk(t). (2.4) k=0 . . . . . H`ınh2.5(b) minh ho.a d¯u`ong cong tuong ´ung c´acd¯iˆe˙’m d¯iˆe` u khiˆe˙’n (qua c´acd¯iˆe˙’m d¯ˆa`u v`a . cuˆo´i. Ta.i sao?). V´oi mˆo˜i t ∈ [0, 1] vi. tr´ıcu˙’a P (t) chı˙’ phu. thuˆo.c v`aonhiˆe` u nhˆa´t ba d¯iˆe˙’m . d¯iˆe` u khiˆe˙’n. D- ˇa.c biˆe.t, v´oi mo.i t ∈ [0.7, 1] chı˙’ c´oba d¯iˆe˙’m P3,P4,P5 d¯iˆe` u khiˆe˙’n h`ınhda.ng cu˙’a . . ˙’ ˙’ 0 . . d¯u`ong cong. Nˆe´u ta di chuyˆen d¯iˆem P4 d¯ˆe´n P4 th`ıchı˙’ c´omˆo.t phˆa`n cu˙’a d¯u`ong cong bi. thay . . . . d¯ˆo˙’i. N´oic´ach kh´ac,c´ach`amtrˆo.n n`aycho ta d¯iˆe` u khiˆe˙’n d¯i.a phuong d¯u`ong cong. . . . Do d¯´ota cˆa`n t`ımmˆo.t l´op c´ach`amtrˆo.n m`avˆa˜n gi˜u la.i nh˜ung t´ınhchˆa´t tˆo´t cu˙’a d¯a . . . . . . th´uc Bernstein v`ac´ach`amn`ayc´ogi´ach´ua thu. c su. trong d¯oa.n [0, 1] d¯ˆe˙’ ngu`oi thiˆe´t kˆe´ d¯iˆe` u . . . . . . . khiˆe˙’n d¯i.a phuong d¯u`ong cong. Ch´ungta s˜ethˆa´y rˇa`ng l´op h`amB-spline v`ad¯u`ong cong x´ac . . d¯i.nh bo˙’ i n´othoa˙’ tˆa´t ca˙’ nh˜ung yˆeucˆa`u n`ay. 2.4 D- a th´u.c t`u.ng kh´ucv`ac´ach`amspline . . . . H`amtrˆo.n m`ach´ungta t`ımd¯ˆe˙’ xˆaydu. ng c´acd¯u`ong cong c´othˆe˙’ xem nhu mˆo.t ho. c´acd¯a . . . . . th´uc x´acd¯i.nh trˆenc´acd¯oa.n kˆe` nhau v`ad¯uo. c “d´anla.i” d¯ˆe˙’ ta.o th`anhmˆo.t d¯u`ong cong liˆen . . . . . . . tu. c. Nh˜ung d¯u`ong cong n`aygo.i l`a d¯u`ong cong d¯ath´uc t`ung kh´uc. 60
. . . . . R0(t) R5(t). . . . . . . / \ . R2(t) R3(t) . . . . . . . . R1(t) R4(t) . . . . | | . . . . . . . . | | . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t .3 .5 .7 1 0 P4 P • •4 P1 • . . . . . . (b) . . . . . • . P3 . . . . . . . . . • • P5 P0 • P2 . H`ınh2.5: C´ach`amtrˆo.n c´ogi´ach´ua trong d¯oa.n [0, 1]. 61
. . . g(t) . . . . . . . . b(t) . . . . . | 3 . . .– 4 . . . . . Chˆo˜ nˆo´i . . . . . / . 1 . . .– •• 2 . . . . . . . . . . . . . . . . a(t) c(t) . . . . . . . . . . . . . . \ . . / . . . . . . . . . . . Knot . . . . . . . . . . . ./ . . . . . . t 0 1 2 3 | Gi´a |. H`ınh2.6: C´acth`anhphˆa`n cu˙’a d¯ath´u.c t`u.ng kh´uc. . D- ˆe˙’ gia˙’i th´ıch mˆo.t sˆo´ thuˆa.t ng˜u x´etd¯ˆo` thi. h`am g(t) trong H`ınh2.6. Ta thˆa´y rˇa`ng, g(t) gˆo`m ba th`anhphˆa`n tu.o.ng ´u.ng c´acd¯ath´u.c a(t) = 1 t2, 2 Ă Â 3 3 2 b(t) = 4 − t − 2 , 1 2 c(t) = 2 (3 − t) . . . . Gi´acu˙’a g(t) l`ad¯oa.n [0, 3]; cu˙’a a(t), b(t) v`a c(t) l`ac´acd¯oa.n [0, 1], [1, 2] v`a[2, 3] tuong ´ung. . . . . . C´acd¯iˆe˙’m ta.i chˆo˜ nˆo´i hai d¯u`ong cong go.i l`a d¯iˆe˙’m nˆo´i v`ac´acgi´atri. t ta.i c´acth`oi d¯iˆe˙’m tuong . ´ung chˆo˜ nˆo´i go.i l`ac´ac knot. C´obˆo´n knot trong v´ıdu. n`ay:0, 1, 2 v`a3. . ´ 1 1 0 0 0 T´ınhto´antru. c tiˆep ta c´o a(1) = b(1) = 2 , b(2) = c(2) = 2 v`a a (1) = b (1) = 1, b (2) = 0 . . . c (2) = −1. Mˇa.t kh´acc´ach`am a(t), b(t) v`a c(t) l`ac´acd¯ath´uc nˆend¯ath´uc t`ung kh´uc g(t) kha˙’ vi liˆentu. c trˆento`and¯oa.n [0, 3]. Tuy nhiˆen,d¯a.o h`amcˆa´p hai g00t) khˆongliˆentu. c ta.i c´ac knot. . . . . D- u`ong cong g(t) cho ta v´ıdu. minh ho.a h`am spline, mˆo.t d¯ath´uc t`ung kh´ucv`akha˙’ vi . . liˆentu. c v´oi m´uc cˆa`n thiˆe´t. D- ˇa.c biˆe.t, ta c´o . . D- .inh ngh˜ıa2.4.1 D- a th´uc t`ung kh´ucbˆa.c M v`akha˙’ vi liˆentu. c cˆa´p M − 1 ta.i c´acknot go.i l`a h`amspline bˆa. c M. . . Hiˆe˙’n nhiˆen, g(t) trong v´ıdu. trˆenl`amˆo.t spline bˆa.c hai: n´ol`ad¯ath´uc t`ung kh´ucbˆa.c 2 v`a . c´od¯a.o h`ambˆa.c mˆo.t liˆentu. c khˇa´p noi. 62