text:
Đồ họa máy tính
Chia sẻ: Lê Văn Thành | Ngày: | Loại File: PDF | Số trang:173
lượt xem 582
download
Đồ họa máy tính
Đồ 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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Đồ họa máy tính
- Đồ họa máy tính
- D` HOA MAY T´ ˆ -O . ´ INH I Pham Tiˆn So.n . ´ e -a . D` Lat, 2005
- 2
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình kỹ thuật đồ họa máy tính
159 p | 2671 | 1233
-
Giáo trình đồ họa máy tính
159 p | 919 | 362
-
Thiết kế đồ họa máy tính
159 p | 438 | 201
-
Bài giảng Vẽ đồ họa máy tính - Bài 1: Giới thiệu
27 p | 645 | 194
-
Bài giảng đồ họa máy tính
27 p | 291 | 133
-
Một số ứng dụng của đồ họa máy tính
0 p | 359 | 128
-
Đề thi cuối kỳ và lời giải môn đồ họa máy tính
5 p | 478 | 120
-
GIÁO TRÌNH ĐỒ HỌA MÁY TÍNH_TỔNG QUAN VỀ ĐỒ HỌA MÁY TÍNH
14 p | 250 | 120
-
Bài giảng Đồ họa máy tính - ĐH Hàng hải
54 p | 332 | 100
-
Bài giảng môn Đồ họa máy tính - ĐH Kinh Tế Kỹ Thuật Công Nghiệp
39 p | 161 | 86
-
Bài giảng về Đồ họa máy tính
29 p | 238 | 86
-
Bài giảng đồ họa máy tính - Dương Anh Đức & Lê Đình Duy
34 p | 176 | 72
-
Bài giảng đồ họa máy tính - Ngô Quốc Việt
37 p | 104 | 30
-
Thảo luận Môn Đồ họa máy tính
8 p | 84 | 25
-
Bài giảng Đồ họa máy tính: Ánh sáng
32 p | 64 | 23
-
Đồ họa máy tính - Chương 1 Màn hình của máy tính - Bài 3
7 p | 99 | 21
-
Bài giảng Đồ họa máy tính - Ma Thị Châu
22 p | 93 | 17
-
Bài giảng Đồ họa máy tính: Các thuật toán mành hóa - Ma Thị Châu
18 p | 110 | 14

markdown:
# Đồ họa máy tính
Chia sẻ: Lê Văn Thành | Ngày: | Loại File: PDF | Số trang:173
lượt xem 582
download
![](http://image.tailieu.vn/document/thumbnail/2010/20100107/vanthanh8990/80x100/711345780998.jpg)
##
Đồ họa máy tính
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](images/down16x21.png)
Đồ 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.
![](images/graphics/blank.gif)
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Đồ họa máy tính
- Đồ họa máy tính
- D` HOA MAY T´ ˆ -O . ´ INH I Pham Tiˆn So.n . ´ e -a . D` Lat, 2005
- 2
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình kỹ thuật đồ họa máy tính
159 p |
2671 |
1233
-
Giáo trình đồ họa máy tính
159 p |
919 |
362
-
Thiết kế đồ họa máy tính
159 p |
438 |
201
-
Bài giảng Vẽ đồ họa máy tính - Bài 1: Giới thiệu
27 p |
645 |
194
-
Bài giảng đồ họa máy tính
27 p |
291 |
133
-
Một số ứng dụng của đồ họa máy tính
0 p |
359 |
128
-
Đề thi cuối kỳ và lời giải môn đồ họa máy tính
5 p |
478 |
120
-
GIÁO TRÌNH ĐỒ HỌA MÁY TÍNH_TỔNG QUAN VỀ ĐỒ HỌA MÁY TÍNH
14 p |
250 |
120
-
Bài giảng Đồ họa máy tính - ĐH Hàng hải
54 p |
332 |
100
-
Bài giảng môn Đồ họa máy tính - ĐH Kinh Tế Kỹ Thuật Công Nghiệp
39 p |
161 |
86
-
Bài giảng về Đồ họa máy tính
29 p |
238 |
86
-
Bài giảng đồ họa máy tính - Dương Anh Đức & Lê Đình Duy
34 p |
176 |
72
-
Bài giảng đồ họa máy tính - Ngô Quốc Việt
37 p |
104 |
30
-
Thảo luận Môn Đồ họa máy tính
8 p |
84 |
25
-
Bài giảng Đồ họa máy tính: Ánh sáng
32 p |
64 |
23
-
Đồ họa máy tính - Chương 1 Màn hình của máy tính - Bài 3
7 p |
99 |
21
-
Bài giảng Đồ họa máy tính - Ma Thị Châu
22 p |
93 |
17
-
Bài giảng Đồ họa máy tính: Các thuật toán mành hóa - Ma Thị Châu
18 p |
110 |
14

Set-Cookie: TLDEVNamespace=soa2e41ehef6h2gici7tttr103; path=/; domain=.tailieu.vn; HttpOnly

Server: Apache/2.2.31 (CentOS)


text:
- THÀNH ĐÔNG GOLF
- Hải Dương
-
- MỞ BÁN ĐẤT NỀN NHÀ VƯỜN, BIỆT THỰ KĐTM TUỆ TĨNH - TP HẢI DƯƠNG
- Chương trình bán 09 lô đất nền trong KĐT Tuệ Tĩnh.
-
-
- MỞ BÁN ĐẤT NỀN NHÀ VƯỜN, BIỆT THỰ KĐTM TUỆ TĨNH - TP HẢI DƯƠNG
- Chương trình bán 36 ô đất trong KĐT Tuệ Tĩnh.
-
- THÔNG TIN MỞ BÁN ĐẤT PHỐ THƯƠNG MẠI - DỰ ÁN KHU ĐÔ THỊ MỚI ĐÔNG BẮC
- Chương trình mở bán " ĐẤT PHỐ THƯƠNG MẠI " Vị Trí: Trung tâm Tp.Phan Rang - Tháp Chàm Tổng diện tích: 60,01ha Diện tích: Từ 65m2 - 207m2 Đơn vị TVTK quy hoạch: Viện quy hoạch Hà Nội Đơn vị TVTK công trình: Công ty NIHON SEIKEI ( Nhật Bản)
-
- THÔNG TIN MỞ BÁN CĂN HỘ PHỐ THƯƠNG MẠI - DỰ ÁN KHU ĐÔ THỊ DU LỊCH BIỂN BÌNH SƠN
- Thông tin mở bán: "CĂN HỘ PHỐ THƯƠNG MẠI". Vị trí: đường Yên Ninh, Tp.Phan Rang - Tháp Chàm Tổng diện tích: 25,01ha Diên tích căn hộ: Từ 91m2 - 110m2 Đơn vị TVTK Quy Hoạch: Viện quy hoạch Hà Nội Đơn vị TVTK Công Trình: Công ty tư vấn thiết kế Việt - Ý.
-
- Đại gia địa ốc đổ vốn vào dự án tỉnh lẻ
- Vị trí đẹp, nhiều ưu ái từ chính quyền địa phương, sức hút đầu tư lâu dài... là lý do khiến các đại gia bất động sản sẵn sàng đổ vốn vào.
-
- Tháng 7, thị trường BĐS "nóng" với hàng loạt chính sách mới
- Từ đầu năm 2014, hàng loạt chính sách mới cho thị trường BĐS có hiệu lực. Với những chính sách này, thị trường BĐS được kỳ vọng sẽ đạt được những bước "đột phá" mới. Trong tháng 7 này, thị trường nhà đất sẽ tiếp tục đón nhận thêm nhiều chính sách mới quan trọng.
-
- Thị trường bất động sản Hải Dương: Sôi động phân khúc bình dân
- Với mức giá trung bình từ 300 đến 500 triệu đồng/căn hộ, phân khúc bình dân của thị trường bất động sản Hải Dương đang có giao dịch tốt.
-
- BĐS tuần 3 tháng 6: 400 triệu USD vốn đầu tư "chảy" vào BĐS trong 5 tháng
- BĐS nhận gần 400 triệu USD vốn đầu tư trong 5 tháng, Quốc hội thông qua Luật Xây dựng (sửa đổi), phê duyệt Chương trình phát triển nhà ở TP. Hà Nội....là những thông tin nổi bật của thị trường tuần qua.
-
- BĐS tuần 2 tháng 6: Thị trường "nóng" với hàng loạt con số ấn tượng
- Giao dịch BĐS 6 tháng đầu năm 2014 tăng gấp đôi cùng kỳ, tồn kho giảm mạnh, một lượng vốn “khủng” đang đổ vào bất động sản khách sạn....là những thông tin làm "nóng" thị trường BĐS tuần qua.
-
-
- Thông báo số 263/TB-VPCP ngày 09/07/2014 của Văn phòng chính phủ
-
Kết luận của Phó Thủ tướng Hoàng Trung Hải - Trưởng Ban chỉ đạo quy hoạch và đầu tư xây dựng vùng thủ đô tại cuộc họp kiểm điểm tình hình thực hiện quy hoạch chung xây dựng Thủ đô Hà Nội
Download
-
- Quyết định số 23/QĐ-UBND ngày 20/06/2014 của UBND thành phố Hà Nội
-
Ban hành quy định các nội dung thuộc thẩm quyền của UBND thành phố Hà Nội do Luật Đất đai 2013 và các Nghị định của Chính phủ giao cho về bồi thường, hỗ trợ và tái định cư khi Nhà nước thu hồi đất trên địa bàn thành phố Hà Nội
Download
-
- Thông tư số 75/2014/TT-BTC ngày 12/06/2014 của Bộ Tài chính
-
Quy định mức thu, chế độ thu, nộp và quản lý và sử dụng phí thẩm tra thiết kế công trình xây dựng
Download
-
- Nghị định số 43/2014/NĐ-CP ngày 15/05/2014 của Chính phủ
-
V/v: Quy định chi tiết thi hành một số điều của Luật đất đai
Download
- Hỗ trợ chung
- +84 4.3972.5971
- Hotline: 19006609
Thời gian: 8h30 -> 17h30, Thứ 2 -> thứ 7.

markdown:
[THÀNH ĐÔNG GOLF](http://thanhdong.com.vn/du-an/du-an-dau-tu/THANH-DONG-GOLF-14.html)
- Hải Dương
-
[MỞ BÁN ĐẤT NỀN NHÀ VƯỜN, BIỆT THỰ KĐTM TUỆ TĨNH - TP HẢI DƯƠNG](http://thanhdong.com.vn/bai-viet/tin-tuc/chuong-trinh-ban-hang/MO-BAN-DAT-NEN-NHA-VUON-BIET-THU-KDTM-TUE-TINH---TP-HAI-DUONG-1116.html)
- Chương trình bán 09 lô đất nền trong KĐT Tuệ Tĩnh.
-
-
[MỞ BÁN ĐẤT NỀN NHÀ VƯỜN, BIỆT THỰ KĐTM TUỆ TĨNH - TP HẢI DƯƠNG](http://thanhdong.com.vn/bai-viet/tin-tuc/chuong-trinh-ban-hang/MO-BAN-DAT-NEN-NHA-VUON-BIET-THU-KDTM-TUE-TINH---TP-HAI-DUONG-923.html)
- Chương trình bán 36 ô đất trong KĐT Tuệ Tĩnh.
-
[THÔNG TIN MỞ BÁN ĐẤT PHỐ THƯƠNG MẠI - DỰ ÁN KHU ĐÔ THỊ MỚI ĐÔNG BẮC](http://thanhdong.com.vn/bai-viet/tin-tuc/chuong-trinh-ban-hang/THONG-TIN-MO-BAN-DAT-PHO-THUONG-MAI---DU-AN-KHU-DO-THI-MOI-DONG-BAC-10.html)
- Chương trình mở bán " ĐẤT PHỐ THƯƠNG MẠI " Vị Trí: Trung tâm Tp.Phan Rang - Tháp Chàm Tổng diện tích: 60,01ha Diện tích: Từ 65m2 - 207m2 Đơn vị TVTK quy hoạch: Viện quy hoạch Hà Nội Đơn vị TVTK công trình: Công ty NIHON SEIKEI ( Nhật Bản)
-
[THÔNG TIN MỞ BÁN CĂN HỘ PHỐ THƯƠNG MẠI - DỰ ÁN KHU ĐÔ THỊ DU LỊCH BIỂN BÌNH SƠN](http://thanhdong.com.vn/bai-viet/tin-tuc/chuong-trinh-ban-hang/THONG-TIN-MO-BAN-CAN-HO-PHO-THUONG-MAI---DU-AN-KHU-DO-THI-DU-LICH-BIEN-BINH-SON-9.html)
- Thông tin mở bán: "CĂN HỘ PHỐ THƯƠNG MẠI". Vị trí: đường Yên Ninh, Tp.Phan Rang - Tháp Chàm Tổng diện tích: 25,01ha Diên tích căn hộ: Từ 91m2 - 110m2 Đơn vị TVTK Quy Hoạch: Viện quy hoạch Hà Nội Đơn vị TVTK Công Trình: Công ty tư vấn thiết kế Việt - Ý.
-
[Đại gia địa ốc đổ vốn vào dự án tỉnh lẻ](http://thanhdong.com.vn/bai-viet/tin-tuc/tin-thi-truong-bds/Dai-gia-dia-oc-do-von-vao-du-an-tinh-le-1115.html)
- Vị trí đẹp, nhiều ưu ái từ chính quyền địa phương, sức hút đầu tư lâu dài... là lý do khiến các đại gia bất động sản sẵn sàng đổ vốn vào.
-
[Tháng 7, thị trường BĐS "nóng" với hàng loạt chính sách mới](http://thanhdong.com.vn/bai-viet/tin-tuc/tin-thi-truong-bds/Thang-7-thi-truong-BDS-"-nong"--voi-hang-loat-chinh-sach-moi--1108.html)
- Từ đầu năm 2014, hàng loạt chính sách mới cho thị trường BĐS có hiệu lực. Với những chính sách này, thị trường BĐS được kỳ vọng sẽ đạt được những bước "đột phá" mới. Trong tháng 7 này, thị trường nhà đất sẽ tiếp tục đón nhận thêm nhiều chính sách mới quan trọng.
-
[Thị trường bất động sản Hải Dương: Sôi động phân khúc bình dân](http://thanhdong.com.vn/bai-viet/tin-tuc/tin-thi-truong-bds/Thi-truong-bat-dong-san-Hai-Duong-Soi-dong-phan-khuc-binh-dan-1107.html)
- Với mức giá trung bình từ 300 đến 500 triệu đồng/căn hộ, phân khúc bình dân của thị trường bất động sản Hải Dương đang có giao dịch tốt.
-
[BĐS tuần 3 tháng 6: 400 triệu USD vốn đầu tư "chảy" vào BĐS trong 5 tháng](http://thanhdong.com.vn/bai-viet/tin-tuc/tin-thi-truong-bds/BDS-tuan-3-thang-6-400-trieu-USD-von-dau-tu-"-chay"--vao-BDS-trong-5-thang-1103.html)
- BĐS nhận gần 400 triệu USD vốn đầu tư trong 5 tháng, Quốc hội thông qua Luật Xây dựng (sửa đổi), phê duyệt Chương trình phát triển nhà ở TP. Hà Nội....là những thông tin nổi bật của thị trường tuần qua.
-
[BĐS tuần 2 tháng 6: Thị trường "nóng" với hàng loạt con số ấn tượng](http://thanhdong.com.vn/bai-viet/tin-tuc/tin-thi-truong-bds/BDS-tuan-2-thang-6-Thi-truong-"-nong"--voi-hang-loat-con-so-an-tuong-1102.html)
- Giao dịch BĐS 6 tháng đầu năm 2014 tăng gấp đôi cùng kỳ, tồn kho giảm mạnh, một lượng vốn “khủng” đang đổ vào bất động sản khách sạn....là những thông tin làm "nóng" thị trường BĐS tuần qua.
-
-
[Thông báo số 263/TB-VPCP ngày 09/07/2014 của Văn phòng chính phủ](http://thanhdong.com.vn/bai-viet/tin-tuc/van-ban-phap-luat/Thong-bao-so-263-TB-VPCP-ngay-09-07-2014-cua-Van-phong-chinh-phu-1110.html)
-
Kết luận của Phó Thủ tướng Hoàng Trung Hải - Trưởng Ban chỉ đạo quy hoạch và đầu tư xây dựng vùng thủ đô tại cuộc họp kiểm điểm tình hình thực hiện quy hoạch chung xây dựng Thủ đô Hà Nội
[Download](http://thanhdong.com.vn/media/download/1405304581_263.signed.pdf)
-
[Quyết định số 23/QĐ-UBND ngày 20/06/2014 của UBND thành phố Hà Nội](http://thanhdong.com.vn/bai-viet/tin-tuc/van-ban-phap-luat/Quyet-dinh-so-23-QD-UBND-ngay-20-06-2014-cua-UBND-thanh-pho-Ha-Noi-1109.html)
-
Ban hành quy định các nội dung thuộc thẩm quyền của UBND thành phố Hà Nội do Luật Đất đai 2013 và các Nghị định của Chính phủ giao cho về bồi thường, hỗ trợ và tái định cư khi Nhà nước thu hồi đất trên địa bàn thành phố Hà Nội
[Download](http://thanhdong.com.vn/media/download/1405304429_QDPQ_23_2014.pdf)
-
[Thông tư số 75/2014/TT-BTC ngày 12/06/2014 của Bộ Tài chính](http://thanhdong.com.vn/bai-viet/tin-tuc/van-ban-phap-luat/Thong-tu-so-75-2014-TT-BTC-ngay-12-06-2014-cua-Bo-Tai-chinh-1104.html)
-
Quy định mức thu, chế độ thu, nộp và quản lý và sử dụng phí thẩm tra thiết kế công trình xây dựng
[Download](http://thanhdong.com.vn/media/download/1403680334_75-btc.signed.pdf)
-
[Nghị định số 43/2014/NĐ-CP ngày 15/05/2014 của Chính phủ](http://thanhdong.com.vn/bai-viet/tin-tuc/van-ban-phap-luat/Nghi-dinh-so-43-2014-ND-CP-ngay-15-05-2014-cua-Chinh-phu-1099.html)
-
V/v: Quy định chi tiết thi hành một số điều của Luật đất đai
[Download](http://thanhdong.com.vn/media/download/1401244671_43.pdf) [Hỗ trợ chung](ymsgr:sendIM?vietskygroup)
- +84 4.3972.5971
- Hotline: 19006609
Thời gian: 8h30 -> 17h30, Thứ 2 -> thứ 7.

WARC-Type: response

Content-Type: application/http; msgtype=response

Connection: close

Server: nginx

Pragma: no-cache

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Vary: Accept-Encoding,User-Agent

Content-Type: text/html