Đồ họa máy tính

Chia sẻ: Lê Văn Thành | Ngày: | Loại File: PDF | Số trang:173

0
1.057
lượt xem
577
download

Đồ họa máy tính

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đồ họa máy tính là lĩnh vực hấp dẫn trong khoa học máy tính.Chúng được sử dụng như công cụ để quan sát thông tin trong nhiều lĩnh vực khác nhau, bao gồm khoa học công nghệ, hóa học, kiến trúc và giải trí. Các chương trình đồ họa tương tác cho phép người sử dụng làm việc theo cách tự nhiên.

Chủ đề:
Lưu

Nội dung Text: Đồ họa máy tính

  1. Đồ họa máy tính
  2. D` HOA MAY T´ ˆ -O . ´ INH I Pham Tiˆn So.n . ´ e -a . D` Lat, 2005
  3. 2
  4. Muc luc . . L`.i n´i d` u o o ¯ˆ a 7 1 C´c thuˆt to´n v˜ d .`.ng cong trˆn thiˆt bi raster a a . a e ¯u o e ´ e . 9 1.1 - . ˙ ’ Doan thˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 9 1.1.1 a . a o ´ Thuˆt to´n sˆ gia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.2 Thuˆt to´n d iˆ’m gi˜.a . . . . . . . . . . . . . . . . . . . . . . . . . . a . a ¯e ˙ u 13 1.1.3 . ´ ´ e o o a ¯ˆ e ´ ¯e a . a e ¯ . ˙ ’ Mˆt sˆ vˆ n d` liˆn quan dˆn thuˆt to´n v˜ d oan thˇng . . . . . . . . a 18 1.1.4 o ınh ˙ ¯ . ’ ˙ ’ C´c thuˆc t´ cua d oan thˇng . . . . . . . . . . . . . . . . . . . . . a . a 21 1.2 Du.`.ng tr`n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - o o 22 1.2.1 Dˆi x´.ng t´m d iˆ’m . . . . . . . . . . . . . . . . . . . . . . . . . . . . -o u ´ a ¯e ˙ 22 1.2.2 Thuˆt to´n d iˆ’m gi˜.a v˜ d u.`.ng tr`n . . . . . . . . . . . . . . . . . . a . a ¯e ˙ u e ¯ o o 23 1.3 Du.`.ng cong ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - o 28 1.3.1 o . ´ Ellipse c´ dang ch´ tˇc . . . . . . . . . . . . . . . . . . . . . . . . . ınh a 29 1.3.2 Ellipse trong tru.`.ng ho.p tˆ’ng qu´t . . . . . . . . . . . . . . . . . . . o . o ˙ a 34 2 H` hoc cu a c´c d .`.ng cong v` mˇt cong ınh . ˙ ’ a ¯u o a a. 47 2.1 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ¯a ’ ˆ 47 3
  5. 2.2 Du.`.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . - o 48 2.2.1 Thuˆt to´n de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . . a . a 48 2.2.2 Da th´.c Bernstein v` d u.`.ng cong Bezier . . . . . . . . . . . . . . . . - u a ¯ o 52 2.3 C´c t´ chˆ t cua d u.`.ng cong Bezier . . . . . . . . . . . . . . . . . . . . . . ´ ’ a ınh a ˙ ¯ o 55 2.3.1 Diˆu khiˆ’n d .a phu.o.ng . . . . . . . . . . . . . . . . . . . . . . . . . . - ` e ˙ e ¯i 59 2.4 Da th´.c t`.ng kh´c v` c´c h`m spline . . . . . . . . . . . . . . . . . . . . . . - u u u a a a 60 2.4.1 Su. dung c´c h`m spline nhu. c´c h`m trˆn . . . . . . . . . . . . . . . ˙ . ’ a a a a o . 63 2.4.2 Xˆy du.ng c´c h`m trˆn . . . . . . . . . . . . . . . . . . . . . . . . . a . a a o . 65 2.4.3 Du.`.ng cong spline v` c´c h`m co. so. . . . . . . . . . . . . . . . . . . - o a a a ˙ ’ 66 2.4.4 C´c h`m B-spline co. so. . . . . . . . . . . . . . . . . . . . . . . . . . a a ˙ ’ 66 2.4.5 Su. dung c´c knot bˆi . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ . ’ a o . 71 2.4.6 Vector knot chuˆ’n . . . . . . . . . . . . . . . . . . . . . . . . . . . . a˙ 73 2.5 C´c t´ chˆ t cua d u.`.ng cong B-spline . . . . . . . . . . . . . . . . . . . . . ´ ’ a ınh a ˙ ¯ o 75 2.6 Nˆi suy c´c d iˆ’m d iˆu khiˆ’n bˇ ng d u.`.ng cong B-spline . . . . . . . . . . . . o . ˙ a ¯ e ¯` e ˙ a e ` ¯ o 77 2.7 ´ ´ Thiˆt kˆ c´c mˇt Bezier v` B-spline . . . . . . . . . . . . . . . . . . . . . . . e e a a . a 80 2.7.1 Patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.7.2 D´n c´c patch Bezier . . . . . . . . . . . . . . . . . . . . . . . . . . . a a 81 2.7.3 Patch spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 3 Giao cu a c´c d oi tu.o.ng ˙ ’ a ¯ˆ ´ . 83 3.1 Mo. d` u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˙ ¯a ’ ˆ 83 3.2 ˙ ’ ˙ ’ Giao cua hai d oan thˇng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¯ . a 83 3.2.1 Phˆn t´ a ıch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4
  6. 3.2.2 . a a ¯. ¯ . ˙ ’ Thuˆt to´n x´c d inh giao hai d oan thˇng . . . . . . . . . . . . . . . . a a 86 3.3 Doan thˇng v` h` ch˜. nhˆt . . . . . . . . . . . . . . . . . . . . . . . . . . - . ˙ ’ a a ınh u a . 87 3.3.1 T` giao bˇ ng c´ch giai hˆ c´c phu.o.ng tr` . . . . . . . . . . . . . . ım ` a a ˙ e a ’ . ınh 89 3.3.2 Thuˆt to´n chia nhi phˆn . . . . . . . . . . . . . . . . . . . . . . . . a . a . a 89 3.3.3 Thuˆt to´n Cohen-Sutherland . . . . . . . . . . . . . . . . . . . . . . a . a 93 3.3.4 Thuˆt to´n Liang-Barsky a . a . . . . . . . . . . . . . . . . . . . . . . . . 97 3.4 ˙ ¯ . ’ ˙ ’ a ` Giao cua d oan thˇng v` d a gi´c lˆi . . . . . . . . . . . . . . . . . . . . . . . 100 a a ¯ o 3.4.1 Vi tr´ tu.o.ng d ˆi cua mˆt d iˆ’m v´.i d u.`.ng thˇng . . . . . . . . . . . . 100 . ı ´ ’ ¯o ˙ o ¯e . ˙ o ¯ o ˙ ’ a 3.4.2 ˙ ¯ . ’ ˙ ’ a ` Thuˆt to´n t` giao cua d oan thˇng v` d a gi´c lˆi . . . . . . . . . . 102 a . a ım a a ¯ o 3.5 Giao hai d a gi´c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 ¯ a 3.5.1 Thuˆt to´n Sutherland-Hodgman . . . . . . . . . . . . . . . . . . . . 108 a . a 3.5.2 Thuˆt to´n Weiler-Atherton . . . . . . . . . . . . . . . . . . . . . . . 111 a . a 3.5.3 C´c ph´p to´n tˆp ho.p trˆn c´c d a gi´c . . . . . . . . . . . . . . . . 113 a e a a . . e a ¯ a 3.6 ` ˙ ’ ` Ray tracing hai chiˆu: phan xa trong buˆng k´ . . . . . . . . . . . . . . . . 114 e . o ın 3.6.1 ˙ ’ Vector phan xa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 . 3.6.2 Giao cua tia s´ng v` d u.`.ng thˇng ˙ ’ a a ¯ o ˙ ’ a . . . . . . . . . . . . . . . . . . . 117 3.6.3 Giao cua tia s´ng v´.i d u.`.ng tr`n . . . . . . . . . . . . . . . . . . . . 121 ˙ ’ a o ¯ o o 3.6.4 Xˆy du.ng v´ du ray tracing . . . . . . . . . . . . . . . . . . . . . . . 124 a . ı . 3.6.5 ` Buˆng k´ l` ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 o ın a 4 Tˆ m`u v` ng o a u 127 4.1 C´c d inh ngh˜ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 a ¯. ıa 4.1.1 V`ng d inh ngh˜ bo.i pixel . . . . . . . . . . . . . . . . . . . . . . . . 127 u ¯. ıa ˙ ’ 5
  7. 4.1.2 V`ng d inh ngh˜ bo.i d a gi´c . . . . . . . . . . . . . . . . . . . . . . . 129 u ¯. ıa ˙ ¯ ’ a 4.2 e ` ´ a Thuˆt to´n tˆ m`u theo vˆt dˆu loang . . . . . . . . . . . . . . . . . . . . . 129 a . a o a 4.3 Thuˆt to´n tˆ m`u theo con chay . . . . . . . . . . . . . . . . . . . . . . . . 131 a . a o a . 4.4 Thuˆt to´n tˆ m`u theo biˆn . . . . . . . . . . . . . . . . . . . . . . . . . . 134 a . a o a e 4.5 So s´nh c´c thuˆt to´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 a a a . a 4.6 Tˆ m`u c´c h` ch˜. nhˆt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 o a a ınh u a . 4.7 Thuˆt to´n tˆ m`u d a gi´c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 a . a o a ¯ a 4.7.1 C´c d`ng qu´t ngang . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 a o e 4.7.2 ˙ ’ C´c manh vun a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 4.7.3 ´ Liˆn kˆt canh v` thuˆt to´n tr`n . . . . . . . . . . . . . . . . . . . . 151 e e . a a . a a 4.7.4 o a a ¯ a ` Tˆ m`u c´c d a gi´c chˆng nhau . . . . . . . . . . . . . . . . . . . . . 158 o 4.8 ˜ Tˆ m`u theo mˆ u tˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 o a a o Phˆn phu luc: Thu. viˆn graph2D.h ` a . . e . 163 a e . ˙ ’ T`i liˆu tham kha o 171 6
  8. L`.i n´i d` u o o ¯ˆ a D` hoa m´y t´ l` mˆt l˜ vu.c hˆ p dˆ n cua khoa hoc m´y t´ -ˆ . o a ınh a o ınh . a a ˙ . ´ ˜ ’ . a ınh. Ch´ng ta su. dung d` hoa u ˙ . ’ ¯ˆ . o m´y t´ nhu. mˆt cˆng cu dˆ’ quan s´t thˆng tin trong nhiˆu l˜ vu.c kh´c nhau, bao gˆm a ınh o o . . ¯e˙ a o ` ınh . e a `o ´ u a ˙ ı. a ’ khoa hoc v` cˆng nghˆ, ho´ hoc, kiˆn tr´c v` giai tr´ C´c chu .o.ng tr` d` hoa tu.o.ng t´c . a o e. a . e ınh ¯o . ˆ a cho ph´p ngu.`.i su. dung l`m viˆc theo c´ch tu. nhiˆn nhˆ t: ngu.`.i su. dung cung cˆ p thˆng e o ˙ .’ a e . a . e ´ a o ˙ .’ ´ a o tin cho tr` u ınh ´ .ng dung thˆng qua c´c hoat d ong bˆn ngo`i cua ho v` s˜ nhˆn d u.o.c thˆng o a a ˙’ . . ¯ˆ. e . a e a ¯ . . o tin tro. lai bˇ ng h` anh. D` hoa m´y t´ d ang gi´p con ngu.`.i thay d ˆ’i vˆ quan niˆm v` ˙ . ` ’ a ınh ˙’ -ˆ . o a ınh ¯ u o ˙ e ¯o ` e. a a .c su. dung m´y t´ c´ch th´ ˙ . u ’ a ınh. Gi´o tr` D` hoa m´y t´ I cung cˆ p mˆt sˆ k˜ thuˆt co. ban cua d` hoa m´y t´ a ınh - ˆ . o a ınh ´ a . ´ o o y a . ˙ ’ ˙ ¯ˆ . ’ o a ınh `e -ˆ . hai chiˆu. (D` hoa m´y t´ ba chiˆu, mˆt phˆn quan trong khˆng thˆ’ thiˆu d u . e ¯ . o a ınh `e o `a o e˙ e ¯ ´ .o.c s˜ d u.o.c . . d` cˆp trong mˆt gi´o tr` kh´c). Dˆ’ c´ mˆt khung canh to`n diˆn v` sˆu sˇc vˆ nh˜.ng ¯ˆ a e . o a . ınh a -e o o ˙ . ˙ ’ a e a a a ` . ´ e u nguyˆn l´ v` thu a e y a . .c h`nh cua d` hoa m´y t´ ˙ ¯ˆ . ’ o a ınh, xem c´c t`i liˆu dˆn [9] v` [11]. C´c phu.o.ng a a e a ˜ a a . ph´p phˆn t´ v` thiˆt kˆ c´c thuˆt to´n trong gi´o tr` cho ph´p sinh viˆn c´ thˆ’ viˆt a a ıch a ´ ´ e e a a. a a ınh e e o e e ˙ ´ dˆ d`ng c´c chu.o.ng tr` minh hoa. Gi´o tr` d u.o.c biˆn soan cho c´c d ˆi tu.o.ng l` sinh ˜ a e a ınh . a ınh ¯ . e . a ¯o´ . a viˆn To´n-Tin v` Tin hoc. e a a . Gi´o tr` su. dung ngˆn ng˜. C dˆ’ minh hoa, tuy nhiˆn c´ thˆ’ dˆ d`ng chuyˆ’n d o’i a ınh ˙ . ’ o u ¯e˙ . e o e ˜ a˙ e ˙ e ¯ˆ ˙ sang c´c ngˆn ng˜. kh´c; v` do d o, sinh viˆn cˆn c´ mˆt sˆ kiˆn th´.c vˆ ngˆn ng˜. C. Ngo`i a o u a a ¯´ e ` o o o e a . ´ ´ u ` o e u a ` a e a ´ ra, hˆu hˆt c´c chu .o.ng tr` thao t´c trˆn cˆ u tr´c d˜. liˆu nhu. danh s´ch liˆn kˆt, nˆn d oi ınh a e a ´ u u e a e e ´ e ¯` . hoi sinh viˆn phai c´ nh˜.ng k˜ nˇng lˆp tr` tˆt. ˙ ’ e ˙ o u ’ y a a . ınh o ´ Sinh viˆn c˜ng cˆn c´ co. so. to´n hoc cua nh˜.ng nˇm d` u d ai hoc: hiˆ’u biˆt vˆ d ai sˆ e u ` o a ˙ a . ˙ ’ ’ u a ¯ˆ ¯ . . a e˙ e ` ¯. o ´ e ´ ´ ˙ ıch, e ınh ’ tuyˆn t´ v` h` hoc giai t´ ph´p t´ vi t´ phˆn. e ınh a ınh . ıch a Muc d´ cua gi´o tr` l`, o. m´.c d o n`o d ´, cho thˆ y c´c tr` u.ng dung d` hoa . ¯ıch ˙ ’ a ınh a ˙ u ¯ˆ a ¯o ’ . ´ a a ınh ´ . ¯ˆ . o ¯ .o.c tao ra nhu. thˆ n`o: Ch´ng ta cˆn viˆt v` chay thu. c´c chu.o.ng tr` du . . ´ e a u `a ´ e a . ˙ a ’ ınh. Mˆt trong o. nh˜ u.ng muc d´ ch´ cua gi´o tr` l` gi´p sinh viˆn nˇm v˜.ng c´c phu.o.ng ph´p, tru.´.c ˙ ’ ´ . ¯ıch ınh a ınh a u e a u a a o hˆt to´n hoc ho´ c´c kh´c niˆm h` hoc v` sau d ´ chuyˆ’n tai th`nh c´c d oan m˜ chu e´ a a a a e ınh . a ¯o ˙ ’ e ˙ a a ¯ . a .o.ng . . tr` ınh. 7
  9. Gi´o tr` bao gˆm bˆn chu.o.ng v` mˆt phˆn phu luc v´.i nh˜.ng nˆi dung ch´ nhu. a ınh ` o ´ o a o. ` a . . o u o . ınh sau: • Chu.o.ng th´. nhˆ t d` cˆp dˆn c´c phu.o.ng ph´p v˜ c´c “nguyˆn so.” cua d` hoa m´y u ´ e . a ¯ˆ a ¯e a ´ a e a e ˙ ¯o . ’ ˆ a ınh: d oan thˇng, d u.`.ng tr`n v` ellipse. t´ ¯ . ˙ ’ a ¯ o o a • Phˆn t´ v` thiˆt kˆ bˇ ng h` hoc l` nˆi dung ch´ cua Chu.o.ng 2. Hˆu hˆt c´c a ıch a e e ` ´ ´ a ınh . a o . ınh ˙ ’ ` a e a´ phˆn mˆm d` hoa d` u c´ nh˜ `a ` ¯ˆ . ¯ˆ o u e o e .ng ch´.c nˇng tao ra c´c d u.`.ng cong du.a trˆn c´c d iˆ’m u a a ¯ o e a ¯e ˙ . . m` ngu.`.i su. dung lu.a chon. Chu.o.ng n`y cung cˆ p nh˜.ng nguyˆn l´ v` c´ch tiˆp cˆn a o ˙ . ’ . . a ´ a u e y a a ´ . e a .c h`nh m` c´c tr` u.ng dung d` hoa ´p dung. thu a a a ınh ´ ¯o . a ˆ . . . • Chu.o.ng 3 giai quyˆt b`i to´n x´c d inh giao cua nh˜.ng nguyˆn so. d` hoa: Giao hai ˙ ’ ´ e a a a ¯. ˙ ’ u e ¯ˆ . o d oan thˇng, giao cua d oan thˇng v` d a gi´c lˆi (bao h`m c´c h` ch˜. nhˆt) v` giao ¯ . ˙ ’ a ˙ ¯ . ’ a˙ ’ a ¯ a `o a a ınh u a . a ˙ ’ ´ cua hai d a gi´c. Cuˆi chu ¯ a o .o.ng l` mˆt v´ du cua k˜ thuˆt “ray tracing” hai chiˆu: a o ı . ˙ ’ y a ` e . . Chuyˆ’n d ong cua tia s´ng trong buˆng k´ c´ ch´.a c´c “chu.´.ng ngai vˆt”. ˙ e ¯ˆ . ˙ ’ a ` o ın o u a o . a . • Chu.o.ng 4 d` cˆp dˆn nh˜.ng thuˆt to´n tˆ m`u v`ng bˆ t k`: V`ng d inh ngh˜ bo.i ¯ˆ a ¯e e . ´ u a. a o a u ´ a y u ¯. ıa ˙ ’ ` ˙ ’.i d u.`.ng biˆn v` v`ng l` d a gi´c. phˆn trong, bo ¯ o a e a u a ¯ a • Phˆn phu luc l` thu. viˆn c´c cˆ u tr´c d˜. liˆu v` c´c h`m cˆn thiˆt v` thu.`.ng xuyˆn ` a . . a e a a . ´ u u e a a a ` . a ´ e a o e su. dung trong gi´o tr` ˙ . ’ a ınh. Trong lˆn xuˆ t ban th´. hai n`y, ch´ng tˆi d u.a thˆm c´c v´ du t´ to´n nhˇ m minh `a ´ ’ a ˙ u a u o ¯ e a ı . ınh a ` a ` y ´ hoa cho phˆn l´ thuyˆt c˜ng nhu u a e u . gi´p sinh viˆn nˇm v˜.ng kiˆn th´.c d ˜ hoc. Ngo`i ra, c´c e a ´ u ´ e u ¯a . a a . lˆi trong xuˆ t ban lˆn tru.´.c c˜ng d a d u.o.c chınh l´; mˇc d` vˆy, t´c gia vˆn mong c´ nh˜.ng ˜ o a ˙ ` ´ ’ a o u ¯˜ ¯ . ˙ ’ y a u a a . . ’ ˜ ˙ a o u ¯o o u . ban d oc. d ´ng g´p t` . ¯ . Tˆi xin cam o.n nh˜.ng gi´p d o. d ˜ nhˆn d u.o.c t`. nhiˆu ngu.`.i m` khˆng thˆ’ liˆt kˆ o ˙ ’ u u ¯˜ ¯a a ¯ . u . ` e o a o ˙ . e e e ´ hˆt, d ac biˆt l` c´c ban sinh viˆn, trong qu´ tr` biˆn soan gi´o tr` n`y. e ¯ˇ . e a a . . e a ınh e . a ınh a -a . D` Lat, ng`y 10 th´ng 1 nˇm 2005 a a a PHAM Tiˆn So.n . ´ e 8
  10. Chu.o.ng 1 C´c thuˆt to´n v˜ d .`.ng cong trˆn a a . a e ¯u o e ´ thiˆt bi raster e . Chu.o.ng n`y tr` b`y c´c thuˆt to´n v˜ d oan thˇng, d u.`.ng tr`n v` ellipse trˆn lattice a ınh a a a . a e ¯ . ˙ ’ a ¯ o o a e 2 a a a ˙ ’ nguyˆn Z . C´c thuˆt to´n chı thao t´c trˆn nh˜ e a e u.ng sˆ nguyˆn v` trong c´c v`ng lˇp chı su. ´ o e a a o a ˙ ˙ ’ ’ . . . a o . e a´ e . ˙ ’ dung ph´p to´n cˆng nˆn rˆ t hiˆu qua. e 1.1 - . ˙ ’ Doan thˇ ng a Thuˆt to´n v˜ d oan thˇng x´c d .nh toa d o cua c´c pixel nˇ m trˆn hoˇc gˆn v´.i d oan thˇng a . a e¯ . a˙ ’ a ¯i . ¯ˆ ˙ a . ’ ` a e a ` o ¯ . . a ˙ ’ a thu.c tˆ nhˆ t. Vˆ nguyˆn tˇc, ch´ng ta muˆn chon d˜y c´c pixel gˆn v´.i d oan thˇng thu.c tˆ . e a´ ´ `e e a ´ u ´ o . a a ` o ¯ . a a˙ ’ . e ´ ´ ˙ ’ ´ ˙ ’ .c tˆ d u.o.c xˆ p xı v´.i mˆt d o mˆt pixel; ta cˆn c´ nhˆ t v` thˇng nhˆ t. X´t d oan thˇng thu e ¯ . a ˙ o a a a a e ¯ . a . ´ ´ ’ a ¯ˆ o . . . ` o a nh˜.ng t´ chˆ t g` V´.i c´c d oan thˇng c´ hˆ sˆ g´c thuˆc d oan [−1, 1], c´ d ung mˆt pixel u ´ ınh a ı? o a ¯ . ˙ ’ a . ´ o e o o o ¯ . . o ¯´ o . .o.c v˜ lˆn trˆn mˆ i cˆt; v´.i c´c d oan thˇng m` hˆ sˆ g´c nˇ m ngo`i d oan n`y, c´ d ung du . e e ¯ e ˜ . o o o a ¯ . ˙ ’ a a e o o ` ´ a a ¯ . a o ¯´ . mˆt pixel d u.o.c v˜ trˆn mˆ i h`ng. Tˆ t ca c´c d oan thˇng d u.o.c v˜ v´.i c`ng mˆt d o s´ng, o. ¯ . e e ˜ o a ´ ’ a ˙ a ¯ . ˙ ’ a ¯ . e o u o ¯ˆ a . . khˆng phu thuˆc v`o d ˆ d`i v` hu o o o a ¯o a a .´.ng, v` nhanh nhˆ t c´ thˆ’ d u.o.c. Thuˆt to´n v˜ d oan a ´ a o e ¯ . ˙ a a e ¯ . . . . . ˙ ’ a u ` a u ´ ¯e a ´ o ınh ˙ ¯ . ’ thˇng c˜ng cˆn ch´ y dˆn c´c thuˆc t´ cua d oan thˇng nhu ¯o o ˙ ’ a . d ˆ rˆng, kiˆ’u v˜... Thˆm ch´ ˙ e e a ı . . . . ch´ng ta muˆn cu e u ´ . o .c tiˆ’u ho´ m´.c d o rˇng cu.a do tiˆn tr` r`.i rac ho´ d u.`.ng thˇng thu.c ˙ a u ¯ˆ a ´ e ınh o . a ¯ o ˙ ’ a . . ´ . su. dung k˜ thuˆt antialiasing (xem [9], [11]) bˇ ng c´ch ´p dung kha nˇng d ˇt cu.`.ng tˆ nh` ˙ . e o ’ y a ` a a a ˙ a ¯a ’ o . . . d ˆ cua mˆ i pixel trˆn c´c thiˆt bi hiˆ’n thi m` mˆt pixel tu ¯o ˙ ˜ ´ ˙ .o.ng u.ng nhiˆu bit. ` . ’ o e a e . e . a o . ´ e Tru.´.c hˆt ch´ng ta chı d` cˆp dˆn c´c d oan thˇng d o rˆng mˆt pixel v` c´ d ung mˆt o e ´ u ’ e . ´ ˙ ¯ˆ a ¯e a ¯ . ˙ ’ a ¯ˆ o . . o . a o ¯´ o. pixel trˆn mˆ o e o . a a ´ o ¯o .i c´c d oan thˇng dˆc). Phˆn cuˆi chu.o.ng s˜ d` cˆp ˜i cˆt (hoˇc h`ng d ˆi v´ a ¯ . ˙ ’ a ´ o `a ´ o e ¯ˆ a e . . 9
  11. dˆn d o rˆng c´c nguyˆn so. v` c´c mˆ u v˜. ´ . . ¯e ¯ˆ o a e a a ˜ a e Mˆt c´ch h` hoc, ch´ng ta biˆ’u diˆn mˆt pixel nhu. mˆt chˆ m tr`n v´.i tˆm tai vi o a . ınh . u e˙ ˜ e o . o . ´ a o o a . . .´.i c´c toa d o nguyˆn Z2 . Biˆ’u diˆn n`y l` mˆt xˆ p xı th´ ho.p ˙ ˜ a a o a ˙ ıch . ˙ ’ tr´ (x, y) cua pixel trˆn lu o a . ¯ˆ ı e . e e e . ´ ’ ´ y ˙’ nh´t cˇt ngang trong mˆt chu k` cua ch`m tia electron cua CRT; xˆ p xı n`y phu thuˆc v`o a a o . u ˙ ’ ´ ’ a ˙ a . o a . .a c´c vˆt trˆn m`n h` hiˆ’n thi. Trong mˆt sˆ ˙ ˙ ’ khoang c´ch (tu` thuˆc v`o hˆ thˆng) gi˜ a e a y o a e o . . ´ u ´ e a ınh e . . ´ o o hˆ thˆng, c´c chˆ m kˆ nhau phu lˆ p mˆt phˆn lˆn nhau; v´.i nh˜.ng hˆ thˆng kh´c c´ nh˜.ng . ´ e o a a ` ´ e ’ ´ ˙ a o. ` e a o u . ´ e o a o u ˙ ’ khoang c´ch gi˜ a a u .a c´c pixel d u.ng kˆ nhau; trong hˆu hˆt c´c hˆ thˆng, khoang c´ch theo ¯´ `e ` ´ a e a e o ´ ˙ ’ a . chiˆu ngang nho ho.n theo chiˆu d u.ng. Mˆt kh´c biˆt n˜.a tu` theo hˆ thˆng trong viˆc biˆ’u ` e ˙ ’ ` ¯´ e o. a e u . y . ´ e o e. e˙ diˆn hˆ toa d o, chˇng han Macintosh xem c´c pixel d u.o.c d at tai tˆm cua h` ch˜. nhˆt ˜ e . ¯ˆ e . . a˙ ’ . a ¯ . ¯ˇ . a . ˙ ’ ınh u a . .a c´c d u.`.ng thˇng kˆ nhau cua lu.´.i d iˆu khiˆ’n thay cho nˇ m trˆn c´c d u.`.ng thˇng cua gi˜ a ¯ o u a˙ ’ ` e ˙ ’ o ¯e ` e ˙ ` a e a ¯ o ˙ a’ ˙ ’ .´.i. Theo c´ch n`y, c´c h` ch˜. nhˆt (x´c d inh bo.i hai g´c) gˆm c´c pixel thuˆc phˆn lu o a a a ınh u a a ¯. ˙ ’ o ` o a o ` a . . trong cua n´. D.nh ngh˜ n`y cho ph´p c´c v`ng d ˆ rˆng bˇ ng khˆng: H` ch˜. nhˆt t`. ˙ o -i ’ ıa a e a u ¯o o . . ` a o ınh u a u . ´ (x, y) dˆn (x, y) khˆng ch´ ¯e o u.a pixel n`o, trong khi v´.i nh˜.ng hˆ thˆng kh´c, c´ d ung mˆt a o u e o ´ a o ¯´ o . . pixel tai d iˆ . ¯e ˙m n`y. Du.´.i d ay ch´ng ta s˜ biˆ’u diˆn c´c pixel nhu. c´c h` tr`n r`.i nhau c´ ’ a o ¯ˆ u e e ˙ ˜ a e a ınh o o o a ` tˆm nˇ m trˆn lu o a e .´.i. H` 1.1 l` ph´ng to cua d u.`.ng thˇng thu.c tˆ v` xˆ p xı d o rˆng mˆt pixel cua n´. ınh a o ˙ ¯ o ’ ˙ ’ a ´ ´ ’ . . . e a a ˙ ¯ˆ o o. ˙ ’ o a ¯ .o.c v˜ tu.o.ng u.ng c´c h` tr`n m`u d en v` c´c pixel khˆng d u.o.c v˜ tu.o.ng u.ng C´c pixel d u . e ´ a ınh o a ¯ a a o ¯ . e ´ h` tr`n khˆng tˆ. Trˆn m`n h` thu.c tˆ, d u.`.ng k´ cua h` tr`n biˆ’u diˆn pixel l´.n ınh o o o e a ınh . e ¯ o ´ ınh ˙ ınh o ’ e˙ ˜ e o ho.n khoang c´ch gi˜.a c´c pixel kˆ nhau, bo.i vˆy biˆ’u diˆn bˇ ng k´ hiˆu cua ch´ng ta l` ˙ ’ a u a ` e ˙ a ’ . e˙ ˜ a e ` y e ˙ ’ u a . mˆt ph´ng d ai m´.c d o r`.i rac cua c´c pixel. o . o ¯. u ¯ˆ o . ˙ a . ’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............i ............ . . . i . . . . . . i . . . . . . i . . . . . . . i . . ...................... ...................... ....................................................... . .................................................................................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . .... . . ..... . . . . . . . . . . . . . . ...... . . . . . . . . . . . . . .... .... .. . . . . . . .... . .... . i. . . . . i . . . . . . i . . . . . . i y . . .. . ... . . .. . ....... . .. . i y . ................................................................................................................. .............................................................................. .................................. . . . . . . . . . . . . . . . . . ..... .... . . . . . . . ..... . . . . . . . . . . ..... .. . . . . . . . . . . . . . . . .. . .... .... . . . . . . . . . . ....... . .... . . . . . . . . . . . .... .. . ....... . . . . . . . . . .... . . . . . . . . ... .. . . . . . . . . . . . .... . .... . . . i. . . i y . . . . .. .. .. i y . i . . i . . ................................................................................................................. ............................................................................... ................................. . . . . . . . .... . ....... . . . . . . . . . . . . . . . . .... ... . . . . . . . . . . . . .. . . . . . . .... . .... . .. . . . . . . . . . . . . . . . .. . .... .... . . . . . . . . . . . . ....... . .... . . . . . . . . . .... . . ....... . . . . . . . . . . . . . .... . . . . . . . . . .... .. . . . . . . . . . . .... . .... . .. .. i y. . . i . . . . . . i . . . . . i . . . . . . i . . ................................................................................................................. .................................. ............................................ ................................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . H` 1.1: Doan thˇng xˆ p xı d u.o.c biˆ’u diˆn bo.i c´c h` tr`n d en. ınh - . ˙ ’ a ´ ’ a ˙ ¯ . e˙ ˜ e ˙ a ınh o ¯ ’ V` c´c nguyˆn so. trong hˆ thˆng ch´ng ta x´c d inh trˆn lu.´.i d iˆu khiˆ’n nguyˆn nˆn ı a e . ´ e o u a ¯. e o ¯` e e˙ e e c´c toa d o d` u cuˆi cua d oan thˇng l` nguyˆn. Thˆt ra, nˆu ch´ng ta cˇt d oan thˇng v´.i a . ¯ˆ ¯ˆ . a ´ ’ o ˙ ¯ . ˙ ’ a a e a . ´ e u ´ a ¯ . ˙ ’ a o h` ch˜ ınh u . nhˆt tru.´.c khi hiˆ’n thi n´ th` toa d ˆ c´c d iˆ’m d` u cuˆi cua d oan thˇng c´ thˆ’ a o e˙ ˙ ´ ’ o ˙ ¯ . ˙ ’ ˙ . . o ı . ¯o a ¯ e ¯ˆ . a a o e khˆng nguyˆn. (Ch´ng ta s˜ thao luˆn c´c giao d iˆ’m khˆng nguyˆn trong Phˆn 1.1.3). Gia o e u e ˙ ’ a a . ¯e˙ o e `a ˙ ’ 10
  12. su. d oan thˇng c´ hˆ sˆ g´c |m| ≤ 1; c´c tru.`.ng ho.p kh´c d u.o.c xu. l´ tu.o.ng tu.. Ho.n n˜.a ˙ ¯ . ’ ˙ ’ a . ´ o e o o a o . a ¯ . ˙ y ’ . u .`.ng ho.p c´c d oan thˇng ngang, d u.ng hoˇc c´ hˆ sˆ g´c ±1 l` tˆm thu.`.ng v` ch´ng chı ˙ ’ tru o . a ¯ . a ¯´ . ´ a o e o o . a `a o ı u ˙ ’ d i qua c´c pixel trˆn lu.´.i. ¯ a e o 1.1.1 a . a o ´ Thuˆt to´n sˆ gia X´t hai pixel A = (xA , yA ) v` B = (xB , yB ) (t´c c´c phˆn tu. cua lattice nguyˆn Z2 ). Phu.o.ng e a u a ` ˙ ˙ a ’ ’ e tr` d u.`.ng thˇng AB c´ dang y = mx + t, trong d o hˆ sˆ g´c m = dy/dx v` t = yA − mxA . ınh ¯ o a˙ ’ o . . ´ ¯´ e o o a C´ch d o a ¯ .n gian nhˆ t dˆ’ v˜ d oan thˇng AB l`: ˙ ’ ´ ˙ a ¯e e ¯ . ˙ ’ a a . ´ 1. T´ hˆ sˆ g´c m; ınh e o o 2. Tˇng x mˆt d o.n vi (kho.i d` u t`. d iˆ’m bˆn tr´i nhˆ t), v´.i mˆ i xi t´ yi = mxi + t v` a o ¯ . . ˙ ¯ˆ u ¯ e ’ a ˙ e a ´ a o o ˜ ınh a sau d ´ v˜ pixel tai (xi , yi + 0.5 )1 . ¯o e . Theo c´ch n`y ta chon pixel tˆt nhˆ t, t´.c l` pixel m` khoang c´ch dˆn d u.`.ng thˇng thu.c a a . ´ o ´ a u a a ˙ ’ ´ a ¯e ¯ o ˙ ’ a . ´ ˙ ’ a ´ tˆ nho nhˆ t. Phu e .o.ng ph´p n`y khˆng hiˆu qua do mˆ i bu.´.c lˇp cˆn t´ mˆt ph´p nhˆn, a a o e ˙ ’ ˜ o o a ` ınh o . . a . e a mˆt ph´p cˆng v` mˆt ph´p to´n l`m tr`n. Ta c´ thˆ’ khu e o e o a o e a a o o e ˙ ˙ ’. ph´p nhˆn bˇ ng c´ch ch´ y rˇ ng a ` a a u´ `a . . . yi+1 = mxi+1 + t = m(xi + ∆x) + t = yi + m∆x, v` nˆu bu.´.c tˇng ∆x = 1 th` yi+1 = yi + m. a e´ o a ı Do d o nˆu x tˇng mˆt d o.n vi th` y tˇng m d o.n vi. V´.i moi d iˆ’m (xi , yi ) trˆn d oan ¯´ e ´ a o ¯ . . ı a ¯ . o . ¯e˙ e ¯ . thˇng ta biˆt rˇ ng nˆu xi+1 = xi + 1 th` yi+1 = yi + m; t´.c l`, c´c gi´ tri x v` y d u.o.c t´ ˙ a’ e ` ´ a ´ e ı u a a a . a ¯ . ınh a a . .´.c d ´ cua n´ (xem H` 1.2). Dˆy ch´ l` “thuˆt to´n sˆ gia”: v´.i mˆi theo c´c gi´ tri tru o ¯o ˙ o ’ ınh -a ınh a a ´ a o o o ˜ . bu.´.c lˇp ta thu.c hiˆn c´c ph´p to´n sˆ gia du.a trˆn bu.´.c tru.´.c. o a . . e a . e a o´ . e o o Kho.i tao ta g´n (x0 , y0 ) l` toa d o nguyˆn cua d iˆ’m xuˆ t ph´t, chˇng han A. Ch´ y ˙ . ’ a a . ¯ˆ . e ˙ ¯e ’ ˙ a´ a ˙ ’ a . u´ rˇ ng trong tru.`.ng ho.p |m| > 1 nˆu x tˇng mˆt d o.n vi th` y tˇng ho.n mˆt d o.n vi. Do d ´ ` a o . ´ e a o ¯ . . ı a o ¯ . . ¯o ` a a ¯ˆ ˙ o ˙ ’ a ` a a a .´.c tˇng mˆt d o.n vi cho y v` tˇng x mˆt cˆn ho´n d o’i vai tr` cua x v` y bˇ ng c´ch g´n bu o a o ¯ a a o . . . .o.ng ∆x = lu . ∆y 1 = m. m 1 K´ hiˆu [x], x v` x tu.o.ng u.ng l` phˆn nguyˆn, l`m tr`n xuˆng v` l`m tr`n lˆn cua x. y e . a ´ a ` a e a o ´ o a a o e ˙ ’ 11
  13. Du.`.ng thˇng - o ˙ ’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a . . . . . . . . .c tˆ . ´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . thu e .... .... . . . . . . . . . . .... .... . . . . . . . . ... ... . . . . . . . . . w . . . . . . . . .... ................................................................................................ .................................................... .................... ................................................ ........................ . . . . ...... . . . . . . . . . . . .... . ... . . . . .... . . . . . . . .... . .... . . . . . . . . . . ...... .... . . . . . . . . . . . . .... .... . . . . . ...... (xi + 1, yi + m ) ......... ......... ......... ......... . . . . . .......... . .......... . .. . ....... . . . . . . . . . .... ... . ... . . . ....... . .... .. .... . . . . . . . . . . .............. . . .......... . . .... . .... . . . . . . . . . . w ..... . . . .... . . . ..... .. .. . .. w . . . . . . . ......................................................................... .............................................. ......................................................................................................................... . . . . . . . . . ..... . .. . . . . . . . (xi , yi ) ........... ........... . . . . . . . . . .... . .... . . . . ... .... ... .... ..... . ...... ....... .. . .. . . . . . . . . . . . . . . . . . . . . ........... ........... ........... ........... . . ..... . . ....... . . .. . . .. . . . . . . ............. . .... ............. . ... . . . ... . .. . . . . . . ....... .. . . ....... .... . . .. . . . . . .. . . ................... .................. .. .. . . w ........ ............................................................................................. .. . ... . . . . . . . . .... .. . . . . . . . ...................................................................................................... . . . . . .... .... . .. . . .... . ... . .. . . . . . .. .. . . . . . . . . . . . .... .... . ... . ... . . . .. .. . . . . . . .... .... . .... ... . . . . . . .. .. . . . . . . . .... ... . . . . . . .. . . . . . . ..... ... . . . . . . .. .. . . . . . . ..... ... . . . . . . .. .. . . . . . . . ..... ... . . . . . . .. . .. . . . . . ..... ... . . . . . . . . .. . . . . . ..... ... . . .. . .. . . . .. . ... ... .. .. (xi , yi ) (xi + 1, yi + m) ´ ˙ ’ H` 1.2: T´ to´n sˆ gia cua (xi , yi ). ınh ınh a o V´ du 1.1.1 Gia su. A(2, 0), B(9, 3). Khi d ´ d u.`.ng thˇng qua hai d iˆ’m A v` B c´ hˆ sˆ ı . ˙ ˙ ’ ’ ¯o ¯ o ˙ ’ a ¯e˙ a . ´ o e o g´c m = 3 ∈ (0, 1). Ap dung thuˆt to´n sˆ gia ta d u.o.c d˜y c´c d iˆ’m v˜ tˆt nhˆ t nhu. trong o 7 ´ . a . a o ´ ¯ . a a ¯e ˙ e o´ a´ ˙ ’ .´.i: bang du o i xi yi yi + 0.5 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 tuc Line() du.´.i d ay minh hoa thuˆt to´n v˜ d oan thˇng t`. (x0 , y0 ) dˆn (x1 , y1 ) ˙ . ’ o ¯ˆ . a . a e ¯ . ˙ ’ a u ´ ¯e v´.i gi´ tri m`u V alue. Diˆ’m kho.i d` u l` d iˆ’m bˆn tr´i nhˆ t. Ngo`i ra ta chı x´t tru.`.ng ho.p o a . a - e˙ ˙ ¯ˆ a ¯ e ’ a ˙ e a ´ a a ˙ e ’ o . −1 ≤ m ≤ 1 v` c´c tru o ı a .`.ng ho.p kh´c c´ thˆ’ thu.c hiˆn do t´ d oi x´.ng. Ho.n n˜.a, ch´ng ta a o e ˙ . e ´ u ınh ¯ˆ u u . . c˜ng bo qua viˆc kiˆ’m tra c´c tru o u ˙ ’ e e˙ a .`.ng ho.p d ac biˆt: d u.`.ng thˇng nˇ m ngang, d u.ng, xiˆn ˙ ’ ` . . ¯ˇ . e ¯ o . a a ¯´ e mˆt g´c ±450 . Ch´ y rˇ ng, trong ngˆn ng˜. C, (int)y bˇ ng y + 0.5 . o o . u´ ` a o u ` a void Line(int x_A, int y_A, int x_B, int y_B, int Value) { 12
  14. 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ˆt to´n d e’m gi˜.a a . a ¯iˆ ˙ u Thu tuc Line() thao t´c trˆn c´c sˆ thu.c y v` m. Bresenham d ˜ xˆy du.ng thuˆt to´n [2] v˜ ˙ . ’ a e a o . ´ a ¯a a . a . a e ¯ . a˙ ’ d oan thˇng chı su .˙ ˙ ’ ’. dung c´c ph´p to´n trˆn sˆ nguyˆn do d ´ tr´nh goi h`m l`m tr`n v` cho a e a e o ´ e ¯o a . a a o a ph´p x´c d .nh (xi+1 , yi+1 ) theo sˆ gia du.a trˆn nh˜.ng gi´ tri o. bu.´.c tru.´.c (xi , yi ). Thuˆt e a ¯i ´ o . e u a . ˙ ’ o o a. to´n n`y c´ thˆ’ mo o a a o e ˙ . ˙ ’ . rˆng dang dˆ u chˆ m d ˆng d oi v´.i c´c toa d o thu.c. Ho.n n˜.a, phu.o.ng ´ a ´ ´ a ¯o ¯ˆ o a . ¯ˆ . u . . . ph´p cua Bresenham c´ thˆ’ d u.o.c ´p dung t´ to´n trˆn sˆ nguyˆn v˜ d u.`.ng tr`n mˇc d` a ˙ ’ ˙ o e ¯ . a . ınh a e o ´ e e ¯ o o a u . ˜ a n´ khˆng dˆ d`ng mo o o o e ’. rˆng cho conic tu` y. V` vˆy ch´ng ta su. dung phu.o.ng ph´p tu.o.ng ˙ . y´ ı a u ˙ . ’ a . d ˆi kh´c, thuˆt to´n d iˆ’m gi˜.a, d u.o.c cˆng bˆ lˆn d` u tiˆn bo.i Pitteway [16], [17] v` d u.o.c ¯o´ a a . a ¯e ˙ u ¯ . o o ` ¯ˆ ´ a a e ˙ ’ a ¯ . ’ ´ ˙ .i Van Aken [26] v` mˆt sˆ t´c gia kh´c [28], [29]. Van Aken d ˜ chı ra [26] d ˆi v´.i ˙ e cai tiˆn bo ’ . ´ a o o a ˙ a ’ ¯a ˙ ’ ´ ¯o o c´c d u.`.ng thˇng v` d u.`.ng tr`n v´.i d˜. liˆu nguyˆn, cˆng th´.c d iˆ’m gi˜.a suy ra cˆng th´.c a ¯ o ˙ ’ a a ¯ o o o u e . e o u ¯e ˙ u o u ˙ ’ cua Bresenham v` do d ´ sinh ra c`ng d˜y c´c pixel. a ¯o u a a Khˆng mˆ t t´ tˆ’ng qu´t, gia su. hˆ sˆ g´c m cua d u.`.ng thˇng thuˆc khoang (0, 1) o ´ a ınh o ˙ a ’ ’ . ´ ˙ ˙ e o o ˙ ¯ o ’ ˙ ’ a o . ˙ ’ .`.ng ho.p kh´c c´ thˆ’ d u.o.c xu. l´ bo.i c´c ph´p lˆ y d oi x´.ng mˆt c´ch th´ ho.p qua (c´c tru o a a o e ¯ .˙ ˙ y ˙ a ’ ’ ´ ´ e a ¯ˆ u o a ıch . . . c´c truc toa d o). Ta c˜ng k´ hiˆu d iˆ’m xuˆ t ph´t l` (xA , yA ) v` d iˆ’m kˆt th´c l` (xB , yB ). a . . ¯ˆ . u y e ¯e. ˙ ´ a a a a ¯e ˙ ´ e u a -a Dˇt dy := yB − yA , dx = xB − xA . Phu .o.ng tr` d u.`.ng thˇng l qua hai d iˆ’m A v` B x´c ınh ¯ o ˙ ’ a ¯e ˙ a a . d .nh bo.i ¯i ˙ ’ dy y= x + t; dx 13
  15. D w .... .... . .. .... .... .... .... .... (l− ) M ....... ...... .... .... .... . .. .... ... .... .... .... .... .... .... .... ... Q w .... .... . .. .... .... w .... .... ... C .... .... . .. .... .... .... R .... .... .... ... .... .... . .. .... .... .... . .... .... .... .... .... .... .. . .... ... ... (l+ ) l H` 1.3: Lu.´.i c´c pixel v` vi tr´ d iˆ’m C, R, D, Q v` M. ınh o a a . ı ¯e ˙ a hay tu.o.ng d u.o.ng ¯ f (x, y) := ax + by + c = 0, trong d ´ a = dy, b = −dx, v` c = b × dx. K´ hiˆu c´c nu.a mˇt phˇng ngo`i v` nu.a mˇt ¯o a y e a ˙ . ’ a . ˙ ’ a a a ˙ ’ a . phˇ˙ ng trong x´c d .nh bo.i l tu.o.ng u.ng bo.i ’ a a ¯i ˙ ’ ´ ˙ ’ (l+ ) := {(x, y) ∈ R2 | f (x, y) > 0}, (l− ) := {(x, y) ∈ R2 | f (x, y) < 0}. Y tu.o.ng cua thuˆt to´n d iˆ’m gi˜.a l` xˆy du.ng mˆt d˜y c´c d iˆ’m v˜ “tˆt nhˆ t” (xi , yi ) ´ ˙ ’ ˙ ’ a. a ¯e˙ u a a . o a a ¯e . ˙ e o ´ ´ a a ¯ˆ u ˙ ´ a . d iˆ’m (x , y ) = (x , y ). Kh´i niˆm tˆt nhˆ t o. d ˆy l` nh˜.ng d iˆ’m (x , y ) d u.o.c bˇt d` u t` ¯ e a e ´ o ´ ’ a ˙ ¯a a u ¯e ˙ 0 0 A A . i i ¯ . chon gˆn v´.i d u.`.ng thˇng thu.c tˆ (dang liˆn tuc) nhˆ t. Theo gia thiˆt, 0 < m < 1, nˆn khi . ` o ¯ o a a˙ ’ ´ . e . e . ´ a ˙ ’ ´ e e x tˇng mˆt lu . a o .o.ng ∆x th` y tˇng khˆng qu´ ∆y = m∆x d o.n vi. ı a o a ¯ . . V` vˆy nˆu bu.´.c th´. i chon d u.o.c d iˆ’m v˜ tˆt nhˆ t C := (xi , yi ) th` o. bu.´.c th´. i + 1 ı a e . ´ o u . ¯ . ¯e ˙ e o´ a´ ı ˙ ’ o u ta s˜ chon d iˆ’m v˜ (xi+1 , yi+1 ), trong d o xi+1 = xi + 1 v` yi+1 = yi hoˇc yi+1 = yi + 1. e . ¯e ˙ e ¯´ a a . N´i c´ch kh´c, bu o o a a .´.c th´. i + 1 ch´ng ta s˜ chon mˆt trong hai pixel R := (x + 1, y ) hoˇc u u e . o a . i i . D := (xi + 1, yi + 1) (xem H` 1.3). K´ hiˆu Q l` giao d iˆ’m cua hai d u o ınh y e a ¯e ˙ ˙ ’ ¯ .`.ng thˇng l v` a˙ ’ a . x = xi + 1. Theo Bresenham, dˆ u cua biˆ’u th´.c x´c d inh bo.i hiˆu gi˜.a hai khoang c´ch t`. ´ ˙ a ’ e˙ u a ¯. ˙ ’ e . u ˙’ a u a ´ ¯e e a ¯. o´ R v` D dˆn Q cho ph´p x´c d inh pixel tˆt nhˆ t o ´ ’ a ˙ . bu.´.c i + 1. Trong thuˆt to´n d iˆ’m gi˜.a, o a a ¯e ˙ u . ta quan s´t vi tr´ cua d iˆ’m gi˜.a M v` c´c nu.a mˇt phˇng x´c d inh bo.i d u.`.ng thˇng l. Dˆ a . ı ˙ ¯e ’ ˙ u a a ˙ ’ a . ˙ ’ a a ¯. ˙ ¯ o ’ ˙ ’ a ˜ e a ˙ ’ ` ´ + d`ng chı ra rˇ ng, nˆu M ∈ (l ) th` pixel D gˆn v´ ¯ o a e ı ` a o .i d u.`.ng thˇng l ho.n; nˆu M ∈ (l− ) th` ˙ ’ a ´ e ı pixel R gˆn ho.n. Du.`.ng thˇng l c´ thˆ’ d i ngang qua M ; hoˇc ca hai pixel nˇ m vˆ c`ng ` a - o ˙ ’ a o e ¯˙ a ˙ . ’ ` a ` u e o ˙ mˆt nu ’.a mˇt phˇng (l+ ) (hoˇc (l− )) nhu.ng trong bˆ t c´. tru.`.ng ho.p n`o, ta vˆ n chon d iˆ’m a ˙ ’ a a ´ a u o a ˜ a ˙ . . . . . ¯e gˆn v´.i l nhˆ t. Ho.n n˜.a, sai sˆ-t´.c l` khoang c´ch gi˜.a pixel d u.o.c chon v` d u.`.ng thˇng ` a o ´ a u ´ o u a ˙ ’ a u ¯ . . a ¯ o ˙ a’ .c tˆ l-luˆn luˆn nho ho.n hoˇc bˇ ng 1/2. a ` . ´ thu e o o ˙ ’ . a 14
  16. Dˆ’ ´p dung thuˆt to´n d iˆ’m gi˜.a, chı cˆn t´ f (M ) = f (xi + 1, yi + 1 ) v` kiˆ’m tra -ea ˙ . a . a ¯e ˙ u ˙ ` ınh ’ a 2 a e ˙ ´ ˙ o a ’ ¯o ¯. ıa e ´ ´ dˆ u cua n´. Do d ´ ta d inh ngh˜ biˆn quyˆt d. nh e ¯i di := f (xi + 1, yi + 1 ) 2 1 = a(xi + 1) + b(yi + 2 ) + c. Khi d ´ ¯o ´ 1. Nˆu di > 0 chon pixel D; e . ´ 2. Nˆu di < 0 chon pixel R; e . ´ 3. Nˆu di = 0 chon mˆt trong hai pixel R hoˇc D, do d ´ chon R. e . o . a . ¯o . Kˆ tiˆp ta cˆn x´c d inh toa d ˆ d iˆ’m gi˜.a M v` do d o biˆn quyˆt d .nh di+1 o. bu.´.c i + 1; ´ ´ e e ` a a ¯. . ¯o ¯ e . ˙ u a ¯´ e ´ ´ e ¯i ˙ ’ o d˜ nhiˆn d iˆu n`y phu thuˆc v`o viˆc chon pixel R hoˇc D. Nˆu chon R th` ho`nh d o d iˆ’m ı e ¯` e a . o a . e . . a . ´ e . ı a ¯ˆ ¯ e . ˙ M tˇng mˆt d o.n vi v` tung d o khˆng d o’i. Do d o a o ¯ . . a ¯ˆ o ¯ˆ . ˙ ¯´ 1 1 di+1 = f (xi + 2, yi + ) = a(xi + 2) + b(yi + ) + c. 2 2 Nhu.ng 1 di = a(xi + 1) + b(yi + ) + c. 2 Suy ra di+1 = di + a. K´ hiˆu sˆ gia d u.o.c cˆng thˆm khi R d u.o.c chon l` ∆R := a = dy. N´i c´ch kh´c, ta . ´ y e o ¯ . o . e ¯ . . a o a a c´ thˆ’ suy ra biˆn quyˆt d .nh o o e ˙ ´ e ´ e ¯i ˙ ’. bu.´.c kˆ tiˆp t`. biˆn quyˆt d inh o. bu.´.c hiˆn h`nh bˇ ng ´ ´ o e e u e ´ ´ e ¯. ˙ ’ o e a ` a . o. e ´ o a o ` a ˙ ınh . a . ’ c´ch cˆng thˆm sˆ gia ∆R m` khˆng cˆn phai t´ lai gi´ tri f (M ). a Nˆu chon D th` ho`nh d o v` tung d o d iˆ’m M c`ng tˇng mˆt d o.n vi, nˆn ´ e . ı a ¯ˆ a . ¯ˆ ¯ e . ˙ u a o ¯ . . e 3 3 di+1 = f (xi + 2, yi + ) = a(xi + 2) + b(yi + ) + c. 2 2 V` do d ´ a ¯o di+1 = di + a + b. K´ hiˆu sˆ gia d u.o.c cˆng v`o di+1 sau khi chon D l` ∆D := a + b = dy − dx. . ´ y e o ¯ . o . a . a V` o. bu.´.c d` u tiˆn, ta chon (x0 , y0 ) = (xA , yA ) nˆn c´ thˆ’ t´ tru.c tiˆp gi´ tri kho.i ı ˙ ’ o ¯aˆ e . ˙ e o e ınh . ´ e a . ˙ ’ tao d0 . Thˆt vˆy, d iˆ’m gi˜.a d` u tiˆn c´ toa d ˆ (x0 + 1, y0 + 1 ), v` . a a ¯e . . ˙ u ¯ˆ a e o . ¯o . 2 a f (x0 + 1, y0 + 1 ) = a(x0 + 1) + b(y0 + 2 ) + c 2 1 = ax0 + by0 + c + a + b/2 = f (x0 , y0 ) + a + b/2. 15
  17. Nhu.ng (x0 , y0 ) thuˆc d u.`.ng thˇng l nˆn f (x0 , y0 ) = 0; do d ´ gi´ tri kho.i d` u cua biˆn o ¯ o . ˙ ’ a e ¯o a . ˙ ¯ˆ ’ a ˙ ’ ´ e ´ quyˆt d .nh l` d0 = a + b/2 = dy − dx/2. Su . e ¯i a ˙ ’. dung d ta c´ thˆ’ chon pixel th´. hai, th´. o e ˙ . u u 0 -e˙ ’. mˆu sˆ trong d ta d inh ngh˜ lai h`m f bˇ ng c´ch nhˆn n´ cho 2; t´.c l` ba, v.v. Dˆ’ khu a o ˙ ˜ ´ ¯. ıa . a ` a a a o u a 0 a a a a ` ´ o a e ´ ´ f (x, y) = 2(ax + by + c). N´i c´ch kh´c, nhˆn 2 cho c´c hˇ ng sˆ a, b, c v` biˆn quyˆt d inh; o a e ¯. m` d iˆu n`y khˆng anh hu.o.ng dˆn dˆ u cua biˆn quyˆt d .nh. a ¯`e a o ˙ ’ ˙ ’ ´ ´ ˙ ¯e a ’ ´ e ´ e ¯i Tˆ’ng qu´t ho´ thuˆt to´n d iˆ’m gi˜.a v˜ d oan thˇng AB (trong tru.`.ng ho.p xA < xB o˙ a a a . a ¯e ˙ u e ¯ . ˙ ’ a o . v` 0 < m < 1) nhu a . sau: 1. [Kho.i tao] Dˇt dx = xB − xA , dy = yB − yA , d0 = 2dy − dx, ∆R = 2dy, ∆D = 2(dy − ˙ . -a ’ . dx), x0 = xA , y0 = yA . 2. Gia su. o. bu.´.c th´. i ta c´ d iˆ’m v˜ tˆt nhˆ t (xi , yi ) v` biˆn quyˆt d .nh di . ˙ ˙ ˙ ’ ’ ’ o u o ¯e ˙ e o´ ´ a a e ´ ´ e ¯i e e a . -a ¯e 3. [V˜ pixel hiˆn h`nh] Dˇt d iˆ’m v˜ tai (xi , yi ). . ˙ e . 4. [Cˆp nhˆt] Nˆu xi = xB , thuˆt to´n d`.ng; ngu.o.c lai, d at a . a . ´ e a . a u . . ¯ˇ . xi+1 = xi + 1; yi ´ nˆu di ≤ 0, e yi+1 = yi + 1 nˆu ngu.o.c lai; ´ e . . di + ∆R nˆ´u di ≤ 0, e di+1 = di + ∆D nˆu ngu.o.c lai. ´ e . . 5. Thay i bˇ ng (i + 1) v` lˇp lai Bu.´.c 3. ` a a a . . o V´ du 1.1.2 Gia su. A(2, 0), B(9, 3). Khi d ´ d u.`.ng thˇng qua hai d iˆ’m A v` B c´ hˆ sˆ ı . ˙ ˙ ’ ’ ¯o ¯ o ˙ ’ a ¯e ˙ a . ´ o e o g´c m = 3 ∈ (0, 1). Dˆ d`ng kiˆ’m tra rˇ ng o 7 ˜ a e e˙ ` a dx = xB − xA = 7, dy = yB − yA = 3, d0 = 2dy − dx = −1, ∆R = 2dy = 6, ∆D = 2(dy − dx) = −8. 16
  18. Ap dung thuˆt to´n d iˆ’m gi˜.a ta c´ d˜y c´c d iˆ’m v˜ tˆt nhˆ t nhu. trong bang du.´.i: ´ . a . a ¯e ˙ u o a a ¯e ˙ e o´ ´ a ˙ ’ o 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ˆ’n nhiˆn rˇ ng c´c kˆt qua n`y tr`ng v´.i kˆt qua khi su. dung phu.o.ng ph´p sˆ gia trong e˙ e ` a a e ´ ˙ a ’ u o e ´ ˙ ’ ˙ . ’ a o ´ V´ du 1.1.1. ı . Ch´ y rˇ ng, ph´p t´ cˆn thiˆt d oi v´.i di+1 trong mˆ i bu.´.c lˇp l` ph´p cˆng v` khˆng u´ ` a e ınh ` a ´ ´ e ¯ˆ o ˜ o o a a e o . . a o c´ ph´p nhˆn. Ho o e a .n n˜.a, v`ng lˇp ho`n to`n d o.n gian nhu. trong thu tuc MidPointLine() u o a a a ¯ ˙ ’ ˙ . ’ . du.´.i d ˆy: o ¯a 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
  19. y++; } } } 1.1.3 . ´ ´ o o a ¯ˆ e e ¯ˆ´ a . a e ¯oa ˙ ’ Mˆt sˆ vˆ n d` liˆn quan d e n thuˆt to´n v˜ d . n thˇ ng a Th´. tu. cua c´c d e’m d` u cuˆi. Trong mˆt u.ng dung ta cˆn d `i hoi mˆt d oan thˇng u . ˙ ’ a ¯iˆ ˙ ¯ˆ a ´ o o ´ . . ` ¯o ˙ a ’ o ¯ . . ˙ ’ a d u.o.c v˜ t`. A dˆn B ch´.a c`ng tˆp c´c pixel nhu. d oan thˇng d u.o.c v˜ t`. B dˆn A; n´i ¯ . e u ¯e ´ u u a a . ¯ . ˙ ’ a ¯ . e u ´ ¯e o c´ch kh´c, d oan thˇng d u.o.c v˜ khˆng phu thuˆc v`o th´. tu. c´c d iˆ’m d` u cuˆi. Su. sai kh´c a a ¯ . ˙’ a ¯ . e o . o a . u . a ¯ e ¯a ˙ ˆ ´ o . a chı c´ thˆ’ xay ra tai nh˜ ˙ o e ˙ ’ ˙ ’ u.ng d iˆ’m v˜ m` d u.`.ng thˇng d i qua d iˆ’m gi˜.a v` biˆn quyˆt d inh ¯e ˙ e a ¯ o ˙ ’ a ¯ ¯e˙ u a e ´ ´ e ¯. . bˇ ng khˆng; trong tru.`.ng ho.p n`y, d i t`. tr´i sang phai ch´ng ta chon d iˆ’m v˜ R. Do t´ ` a o o . a ¯ u a ˙ ’ u . ¯e ˙ e ınh ´ d ˆi x´ ¯o u .ng, khi d i t`. phai sang tr´i v` d = 0 l˜ ra ta chon d iˆ’m v˜ R, nhu.ng chon lu.a n`y s˜ ¯ u ˙ ’ a a e ˙ . ¯e e . . a e sai lˆch mˆt d o.n vi theo th`nh phˆn y v´.i pixel d u.o.c chon khi d i t`. tr´i sang phai. Do d ´ e . o ¯ . . a ` a o ¯ . . ¯ u a ˙ ’ ¯o u ` ch´ng ta cˆn chon pixel D khi d i t` a ¯ u . phai sang tr´i trong tru.`.ng ho.p d = 0. L´ luˆn tu.o.ng ˙ ’ a o y a . . . . d oi v´.i c´c d oan thˇng c´ hˆ sˆ g´c bˆ t k`. ˙’ . ´ tu ¯ˆ o a ¯ . a . ´ o e o o a y ´ Phu.o.ng ph´p ho´n d o’i c´c d iˆ’m d` u cuˆi cua d oan thˇng dˆ’ thuˆt to´n xu. l´ theo a ˙ a ¯ˆ a ¯ e ¯ˆ ˙ a ´ ’ o ˙ ¯ . ˙ ’ a ¯e˙ a . a ˙ y ’ c`ng hu.´.ng khˆng thu.c hiˆn ch´ x´c khi ch´ng ta v˜ c´c d oan thˇng theo mˆ u tˆ. C´c u o o . e . ınh a u e a ¯ . ˙ ’ a ˜ a o a d oan thˇng v˜ theo mˆ u thu.`.ng “neo” nh˜.ng dˆ u hiˆu tai d iˆ’m xuˆ t ph´t, c´ thˆ’ l` d iˆ’m ¯ . a˙ ’ e ˜ a o u ´ a e . ¯e . ˙ a´ a o e a ¯e˙ ˙ du.´.i bˆn tr´i, khˆng phu thuˆc v`o hu.´.ng di chuyˆ’n. Dˇc biˆt, v´.i mˆu tˆ chˆ m-gach, o e a o . o a . o e˙ -a. e . o ˜ a o a ´ . chˇng han 111100, ch´ng ta muˆn v˜ mˆ u n`y tai d iˆ’m xuˆ t ph´t m` khˆng tu ¯o ¯o ˙ ’ a u ´ ˜ o e a a . ¯e ˙ ´ a a a o . d ˆng d ˆ’i ˙ . . . th`nh d iˆ’m du.´.i bˆn tr´i. Ngo`i ra, nˆu thuˆt to´n luˆn luˆn d at lai c´c d iˆ’m d` u cuˆi a ¯e ˙ o e a a ´ e a . a o o ¯ˇ . a ¯ e ¯a . ˙ ˆ ´ o . tu. ch´ tˇc, ta cˆn di chuyˆ’n t`. tr´i sang phai v´.i d oan thˇng AB v` t`. phai theo th´ . ınh a u ´ `a ˙ e u a ˙ o ¯ . ’ ˙ ’ a a u ˙ ’ sang tr´i v´.i d oan thˇng BA; d iˆu n`y tao ra su. gi´n d oan trong qu´ tr` v˜, chˇng han a o ¯ . ˙ ’ a ¯`e a . . a ¯ . a ınh e ˙ ’ a . d a gi´c, tai nh˜ ¯ a u.ng d ınh chung. ¯˙’ . - e Diˆ’m xuˆ t ph´t nˇ m trˆn canh cu a d gi´c cˇt. Mˆt vˆ n d` kh´c ch´ng ta cˆn ˙ a´ a ` a e . ˙ ¯a a a ’ ´ o a ¯ˆ a . ´ e u ` a ˙’.a d ˆ’i thuˆt to´n dˆ’ v˜ c´c d oan thˇng sau khi d u.o.c cˇt bo.i mˆt trong c´c thuˆt to´n su ¯o ˙ a ˙ a ¯e e a ¯ . ˙ ’ a ¯ . a ˙ ´ ’ o a a a . . . trong Phˆn 3.3. H` 1.4(a) minh hoa d oan thˇng d u.o.c cˇt bo.i canh bˆn tr´i, x = xmin , `a ınh . ¯ . ˙ ’ a ¯ . a ˙ .´ ’ e a ˙ ’ cua h` ch˜ ınh u . nhˆt. Giao d iˆ’m cua d oan thˇng v` canh bˆn tr´i c´ ho`nh d ˆ x nguyˆn a ¯e ˙ ˙ ¯ . ’ ˙ ’ a a . e a o a ¯o e . . nhu.ng tung d o y thu.c. Pixel (xmin , mxmin + t + 0.5 ) trˆn canh x = xmin ch´ l` pixel ¯ˆ. . e . ınh a ¯ .o.c v˜ tai ho`nh d o x du . e . a ˙ ¯ . ’ ˙ ’ ¯ˆ min cua d oan thˇng tru o a .´.c khi cˇt theo thuˆt to´n d iˆ’m gi˜.a2 . V´.i ´ a a a ¯e˙ u o . . ˙ ’.i tao d a biˆt, kˆ tiˆp ch´ng ta cˆn kho.i tao biˆn quyˆt d inh tai d iˆ’m gi˜.a d oan pixel kho . ¯˜ e ´ e e ´ ´ u ` a ˙ . ’ ´ e ´ e ¯. ˙ . ¯e u ¯ . . ´ ` u´ ` RD trong cˆt kˆ bˆn. Cˆn ch´ y rˇ ng, c´ch l`m n`y tao ra d˜y ch´ x´c c´c pixel, trong o e e a a a a a . a ınh a a 2 Khi mxmin + t nˇ m gi˜.a hai d u.`.ng thˇng ngang kˆ nhau, ch´ng ta cˆn l`m tr`n xuˆng. Dˆy l` hˆ qua ` a u ¯ o ˙ ’ a ` e u ` a a o ´ o -a a e . ˙ ’ ˙ a viˆc chon pixel R khi d = 0. ’ cu e . . 18
  20. x = xmin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . ..... ..... . . ..... ..... . . . . . . . . i D. . . . . . . ..... ..... ........................................................................................... ..................................................................... . . . ..... ..... ..... ..... .................................................................... ............................................. . . ... . ... . . . . . ..... ..... . . . ..... ..... . . . . . ..... ..... . . . ..... ..... M— . . . . ... ... . . . . . ..... ..... . . . ..... ..... . . . ..... ..... (xmin , mxmin + t + 0.5 ) ........ ........ ........ . . ........ . . y ....... . ...... . . . . i . . . . . . ..... . ..... . ......... ..... ..... .......................................... ............................................................................................. ......................................................................................................................................... .... .. ... . ... .. . . . . ... . . ..... ..... . . (xmin , mxmin + t) • . .................. .. . ......... .................. . . . ....... . ......... ..... ...... . .... .. . . ..... .. . . . R . . . . . . . .. .. ..... . ..... . . . . .. .. ..... ..... . . . . . . . .. .. ..... ..... . . . . . .. ..... ..... . . . . . . ......... ......... . .. . ..... ..... . . . . ............................................................................................................................. .............................................................................................................................. . . ... .. . . . . .. .. . .. .. ..... ..... . . . . . . . . .. .. ..... ..... . . . . . ..... ..... . . . . . ..... .... . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............................................................................................................... . ...................... ........................................................................................ . . y = ymin (a) x = .xmin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . ....... . ..... . . . . . . . . . . . . . . . . . . . . . . ....... ....... . . . . . . . . . . . . . . . . . . . . . . ....... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......... . . . ....... . . . . . . . . . . ....... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . y . . . . y ..... . . ..... ..... . y .................................................................................................................................................................................................................. . . ............................................................... ................................... ............................................................................................................. . . y . . . . . . . . . . . . . . . . . . . ....... ... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . ............ . . . .......... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .... .. ....... . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. ......... . ............ . . . . . . . . . . . . . . ....... ....... . . . iD y yC y . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . ........... .......... . . . . i. . . i . . . . . . . . i . . . . . . . . . . . . . . . . . . . . . . .... ..... . ..... .. . ....... . .. ... . . . . . . . . . . . y . . . . . . . i . . . . . . . i . . . . . . . i . ................. ................................... .......................................... ............ ......................................................................................... ....................................................................................................................................................................................................... . . y = ymin y = ymin − 1 ... ... ... ... .. . . . . . . . . . . . .... .... .... .... .... ... ... . .. ... ... . .. ............ . . . . . . . .. . ........ I• . . ... ... . ... . . . .. ....... . . ............. . . . . . . . . . . . . . . . . . . . . . . . . ..... ... ... . ... ... ... ... ... ... ... ... .. . ... ... ... ... ... .... ... ... . .. . . . . .. .... .... .... .... .... .... .... ............. .... ..... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ..... .... .... . . . . . . . . . . .. 2 . . . . . . . . ... .. . ....... ....... . . . . . . . . . . . . . . . . . . . . . . . . .. ......... . . . ............. . . . . . . . . . . . . . . . y = ymin − 1 y y . . . . ........... . . ............. . . y . ... . . . y . . . . . . . . . . y . . . . . . y . . . . . y . . . . . y . . . . . . . . . . . . . ........................... ........................................................................ ........................................................................................................... ................................................................................................................................................................................................................. . . . . . . . . . ..... . ..... . ... . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... ....... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .. ....... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... ....... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (b) H` 1.4: Diˆ’m xuˆ t ph´t nˇ m trˆn biˆn h` ch˜. nhˆt. (a) Giao v´.i canh d u.ng. (b) Giao ınh - e˙ ´ a a ` a e e ınh u a . o . ¯´ .i canh ngang. v´ . o 19
Đồng bộ tài khoản