Giáo trình Lý thuyết Đồ Họa

Nội dung text: Giáo trình Lý thuyết Đồ Họa

1. MC L C Ch ươ ng 1: CÁC Y U T C Ơ S C A ð H A 1.1. T ng quan v ñ h a máy tính 1 1.1.1. Gi i thi u v ñ h a máy tính 1 1.1.2. Các k thu t ñ h a 1 1.1.2.1. K thu t ñ h a ñim 1 1.1.2.2. K thu t ñ h a vector 2 1.1.3. ng d ng c a ñ h a máy tính 2 1.1.4. Các l ĩnh v c c a ñ h a máy tính 3 1.1.5. T ng quan v m t h ñ h a 4 1.2. Màn hình ñ h a 6 1.3. Các khái ni m 6 1.3.1. ðim 6 1.3.2. Các bi u di n t a ñ 8 1.3.3. ðon th ng 8 1.4. Các thu t toán v ñon th ng 8 1.4.1. Bài toán 8 1.4.2. Thut toán DDA 9 1.4.3. Thu t toán Bresenham 10 1.4.4. Thu t toán MidPoint 12 1.5. Thu t toán v ñưng tròn 14 1.5.1. Thu t toán Bresenham 14 1.5.2. Thu t toán MidPoint 16 1.6. Thu t toán v Ellipse 17 1.6.1. Thu t toán Bresenham 17 1.6.2. Thu t toán MidPoint 20 1.7. Ph ươ ng pháp v ñ th hàm s 21 Bài t p 23 Ch ươ ng 2: TÔ MÀU 2.1. Gi i thi u các h màu 25 2.2. Các thu t toán tô màu 28 2.2.1. Bài toán 28 2.2.2. Thu t toán xác ñnh P ∈ S 28 2.2.3. Thu t toán tô màu theo dòng quét 30 2.2.4. Thu t toán tô màu theo v t d u loang 30 Bài t p 31 Ch ươ ng 3: XÉN HÌNH 3.1. ðt v n ñ 32
2. 3.2. Xén ñon th ng vào vùng hình ch nh t 32 3.2.1. C nh c a hình ch nh t song song v i các tr c t a ñ 32 3.2.1.1. Thu t toán Cohen – Sutherland 33 3.2.1.2. Thu t toán chia nh phân 34 3.2.1.3. Thu t toán Liang – Barsky 35 3.2.2. Khi c nh c a hình ch nh t t o v i tr c hoành m t góc α 36 3.3. Xén ñon th ng vào hình tròn 37 3.4. Xén ñưng tròn vào hình ch nh t 38 3.5. Xén ña giác vào hình ch nh t 39 Bài t p 40 Ch ươ ng 4: CÁC PHÉP BI N ðI 4.1. Các phép bi n ñi trong m t ph ng 41 4.1.1. C ơ s toán h c 41 4.1.2. Ví d minh h a 43 4.2. Các phép bi n ñi trong không gian 45 4.2.1. Các h tr c t a ñ 45 4.2.2. Các công th c bi n ñi 46 4.2.3. Ma tr n ngh ch ño 48 4.3. Các phép chi u c a v t th trong không gian lên m t ph ng 48 4.3.1. Phép chi u ph i c nh 48 4.3.2. Phép chi u song song 50 4.4. Công th c c a các phép chi u lên màn hình 50 4.5. Ph l c 56 4.6. Ví d minh h a 59 Bài t p 61 Ch ươ ng 5: BI U DI N CÁC ðI TƯNG BA CHI U 5.1. Mô hình WireFrame 63 5.2. V mô hình WireFrame v i các phép chi u 64 5.3. V các m t toán h c 65 Bài t p 68 Ch ươ ng 6: THI T K ðƯNG VÀ M T CONG BEZIER VÀ B-SPLINE 6.1. ðưng cong Bezier và m t Bezier 69 6.1.1. Thu t toán Casteljau 70 6.1.2. D ng Bernstein c a ñưng cong Bezier 70 6.1.3. D ng bi u di n ma tr n c a ñưng Bezier 71 6.1.4. T o và v ñưng cong Bezier 72 6.1.5. Các tính ch t c a ñưng Bezier 74 6.1.6. ðánh giá các ñưng cong Bezier 76 6.2. ðưng cong Spline và B-Spline 77 6.2.1. ðnh ngh ĩa 77
3. 6.2.2. Các tính ch t h u ích trong vi c thi t k các ñưng cong B-Spline 78 6.2.3. Thi t k các m t Bezier và B-Spline 79 6.2.4. Các b ăng Bezier 80 6.2.5. Dán các b ăng Bezier v i nhau 81 6.2.6. Các b ăng B-Spline 81 Ch ươ ng 7: KH ðƯNG VÀ M T KHU T 7.1. Các khái ni m 83 7.2. Các ph ươ ng pháp kh m t khu t 85 7.2.1. Gi i thu t s p x p theo chi u sâu 85 7.2.2. Gi i thu t BackFace 88 7.2.3. Gi i thu t vùng ñm ñ sâu 90 Bài t p 103 Ch ươ ng 8: T O BÓNG V T TH 3D 8.1. Khái ni m 104 8.2. Ngu n sáng xung quanh 104 8.3. Ngu n sáng ñnh h ưng 105 8.4. Ngu n sáng ñim 109 8.5. Mô hình bóng Gouraud 110 Bài t p 121 Ph l c: M T S CH ƯƠ NG TRÌNH MINH H A I. Các thu t toán tô màu 122 II. Các thu t toán xén hình 129 III. V các ñi t ưng 3D 136 Tài li u tham kh o 143
4. LI M ðU ð h a là m t trong nh ng l ĩnh v c phát tri n r t nhanh c a ngành Công ngh thông tin. Nó ñưc ng d ng r ng rãi trong nhi u l ĩnh v c khoa h c và công ngh . Ch ng h n nh ư y h c, ki n trúc, gi i trí ð h a máy tính ñã giúp chúng ta thay ñi cách c m nh n và s d ng máy tính, nó ñã tr thành nh ng công c tr c quan quan tr ng không th thi u trong ñi s ng h ng ngày. Vì v y môn “ ð h a” ñã tr thành mt trong nh ng môn h c chính trong các chuyên ngành Công ngh thông tin các tr ưng ñi h c. Cu n sách “Giáo trình lý thuy t ñ h a” ñưc biên so n theo sát n i dung ch ươ ng trình ñào t o c nhân Công ngh thông tin. N i dung c a giáo trình này cung c p m t s ki n th c c ơ b n v lý thuy t và thu t toán xây d ng các công c ñ h a 2D và 3D. T ñó giúp sinh viên có th ñc l p xây d ng nh ng th ư vi n ñ ha cho riêng mình và phát tri n các ph n m m ng d ng ñ h a cao h ơn. Giáo trình ñưc chia làm 8 ch ươ ng và ph n ph l c, sau m i ch ươ ng ñu có ph n bài t p ñ ki m tra ki n th c và rèn luy n kh năng l p trình cho b n ñc. ð thu n ti n cho vi c trình bày thu t toán m t cách d hi u, các gi i thu t trong giáo trình ñưc vi t trên ngôn ng “t a Pascal” và các mã ngu n ñưc cài ñt trên Turbo Pascal 7.0. Nh m giúp b n ñc b t lúng túng trong quá trình cài ñt các gi i thu t, ph n ph l c li t kê m t s mã ngu n cài ñt các thu t toán trong các ch ươ ng. Tuy nhiên, b n ñc nên t cài ñt các thu t toán ph n lý thuy t, n u c m th y khó kh ăn l m m i nên tham kh o ph n ph l c này. Ch ươ ng 1, 2 và 3 trình bày v các y u t c ơ s c a ñ h a nh ư: màn hình ñ ha, ñim, ñon th ng, ñưng tròn, các h màu và các thu t toán tô màu, xén hình Ch ươ ng 4 trang b các ki n th c toán h c v các phép bi n ñi trong không gian 2D và 3D. Ch ươ ng 5, 6 và 7 gi i thi u các mô hình ñ h a 3D, các gi i thu t kh m t khu t và t o bóng cho v t th Ch ươ ng 8 trình bày v ph ươ ng pháp thi t k các ñưng cong Bezier và B-Spline. Mc dù ñã r t c g ng trong quá trình biên so n nh ưng ch c ch n giáo trình này v n không th tránh kh i nh ng thi u sót. Chúng tôi r t mong nh n ñưc nh ng ý ki n ñóng góp c a b n ñc c ũng nh ư các b n ñng nghi p trong l ĩnh v c ð h a ñ giáo trình ngày càng ñưc hoàn thi n h ơn trong l n tái b n sau. ða ch liên l c: Khoa Công ngh Thông tin, tr ưng ði h c Khoa h c Hu . ðin tho i: 054.826767. Email: paphuong@hueuni.edu.vn nhtai@hueuni.edu.vn Hu , tháng 08 n ăn 2003 Các tác gi
5. Updatesofts.com Ebooks Team CH ƯƠ NG I CÁC Y U T C Ơ S C A ð H A 1.1. T NG QUAN V ð H A MÁY TÍNH ð h a máy tính là m t lãnh v c phát tri n nhanh nh t trong Tin h c. Nó ñưc áp dng r ng rãi trong nhi u lãnh v c khác nhau thu c v khoa h c, k ngh , y khoa, ki n trúc và gi i trí. Thu t ng ñ h a máy tính (Computer Graphics) ñưc ñ xu t b i nhà khoa h c ng ưi M tên là William Fetter vào n ăm 1960 khi ông ñang nghiên c u xây d ng mô hình bu ng lái máy bay cho hãng Boeing. Các ch ươ ng trình ñ h a ng d ng cho phép chúng ta làm vi c v i máy tính m t cách tho i mái, t nhiên. 1.1.1 Gi i thi u v ñ h a máy tính ð h a máy tính là m t ngành khoa h c Tin h c chuyên nghiên c u v các ph ươ ng pháp và k thu t ñ có th mô t và thao tác trên các ñi t ưng c a th gi i th c b ng máy tính. V b n ch t: ñó là m t quá trình xây d ng và phát tri n các công c trên c hai lĩnh v c ph n c ng và ph n m m h tr cho các l p trình viên thi t k các ch ươ ng trình có kh n ăng ñ h a cao. Vi vi c mô t d li u thông qua các hình nh và màu s c ña d ng c a nó, các ch ươ ng trình ñ h a th ưng thu hút ng ưi s d ng b i tính thân thi n, d dùng, kích thích kh n ăng sáng t o và nâng cao n ăng su t làm vi c. 1.1.2. CÁC K THU T ð H A Da vào các ph ươ ng pháp x lý d li u trong h th ng, ta phân ra làm hai k thu t ñ h a: 1.1.2.1. K thu t ñ h a ñim
6. Ch ươ ng I. Các y u t c ơ s c a ñ h a Nguyên lý c a k thu t này nh ư sau: các hình nh ñưc hi n th thông qua t ng pixel (t ng m u r i r c). V i k thu t này, chúng ta có th t o ra, xóa ho c thay ñi thu c tính c a t ng pixel c a các ñi t ưng. Các hình nh ñưc hi n th nh ư m t l ưi ñim r i r c (grid), t ng ñim ñu có v trí xác ñnh ñưc hi n th v i m t giá tr nguyên bi u th màu s c ho c d sáng c a ñim ñó. T p h p t t c các pixel c a grid to nên hình nh c a ñi t ưng mà ta mu n bi u di n. 1.1.2.2. K thu t ñ h a vector Nguyên lý c a k thu t này là xây d ng mô hình hình h c (geometrical model) cho hình nh ñi t ưng, xác ñnh các thu c tính c a mô hình hình h c, sau ñó d a trên mô hình này ñ th c hi n quá trình tô trát (rendering) ñ hi n th t ng ñim c a mô hình, hình nh c a ñi t ưng. k thu t này, chúng ta ch l ưu tr mô hình toán h c c a các thành ph n trong mô hình hình h c cùng v i các thu c tính t ươ ng ng mà không c n l ưu l i toàn b t t c các pixel c a hình nh ñi t ưng. 1.1.3. ng d ng c a ñ h a máy tính hi n nay Ngày nay, ñ h a máy tính ñưc s d ng r ng rãi trong nhi u l ĩnh v c khác nhau nh ư: Công nghi p, th ươ ng m i, qu n lý, giáo d c, gi i trí, Sau ñây là m t s ng d ng tiêu bi u: 1.1.3.1. To giao di n (User Interfaces): nh ư các ch ươ ng trình ng d ng WINDOWS, WINWORD, EXCEL ñang ñưc ña s ng ưi s d ng ưa chu ng nh tính thân thi n, d s d ng. 1.1.3.2. To ra các bi u ñ dùng trong th ươ ng m i, khoa h c và k thu t: Các bi u ñ ñưc t o ra r t ña d ng, phong phú bao g m c hai chi u l n ba chi u góp ph n thúc ñy xu h ưng phát tri n các mô hình d li u h tr ñc l c cho vi c phân tích thông tin và tr giúp ra quy t ñnh. 1.1.3.3. T ñng hóa v ăn phòng và ch b n ñin t : dùng nh ng ng d ng c a ñ ha ñ in n các tài li u v i nhi u lo i d li u khác nhau nh ư: v ăn b n, bi u ñ, ñ th và nhi u lo i hình nh khác 1.1.3.4. Thi t k v i s tr giúp c a máy tính (Computer aided design): M t trong nh ng l i ích l n nh t c a máy tính là tr giúp con ng ưi trong vi c thi t k . Các ng 2
7. Ch ươ ng I. Các y u t c ơ s c a ñ h a dng ñ h a cho phép chúng ta thi t k các thi t b c ơ khí, ñin, ñin t , ô tô, máy bay, nh ư ph n m m AUTOCAD 1.1.3.5. Lĩnh v c gi i trí, ngh thu t: cho phép các h a s ĩ t o ra các hình nh ngay trên màn hình c a máy tính. Ng ưi h a s ĩ có th t pha màu, tr n màu, th c hi n m t s thao tác: c t, dán, t y, xóa, phóng to, thu nh nh ư các ph n m m PAINTBRUSH, CORELDRAW, 1.1.3.6. Lĩnh v c b n ñ: xây d ng và in n các b n ñ ña lý. M t trong nh ng ng dng hi n nay ca ñ h a là h th ng thông tin ña lý (GIS - Geographical Information System). 1.1.4. Các l ĩnh v c c a ñ h a máy tính 1.1.4.1. Các h CAD/CAM (CAD – Computer Aided Design, CAM – Computer Aided Manufacture) Các h này xây d ng t p h p các công c ñ h a tr giúp cho vi c thi t k các chi ti t và các h th ng khác nhau: các thi t b c ơ khí, ñin t Ch ng h n nh ư ph n m m Auto Cad c a h ng AutoDesk 1.1.4.2. X lý nh (Image Processing) ðây là l ĩnh v c x lý các d li u nh trong cu c s ng. Sau quá trình x lý nh, d li u ñu ra là nh c a ñi t ưng. Trong quá trình x lý nh, chúng ta s s d ng r t nhi u các k thu t ph c t p: khôi ph c nh, xác ñnh biên Ví d : ph n m m PhotoShop, Corel Draw, 1.1.4.3. Khoa h c nh n d ng (Pattern Recognition) Nh n d ng là m t l ĩnh v c trong k thu t x lý nh. T nh ng m u nh có s n, ta phân lo i theo c u trúc ho c theo các ph ươ ng pháp xác ñnh nào ñó và b ng các thu t toán ch n l c ñ có th phân tích hay t ng h p nh ñã cho thành m t t p h p các nh gc, các nh g c này ñưc l ưu trong m t th ư vi n và c ăn c vào th ư vi n này ñ nh n dng các nh khác. Ví d : Ph n m m nh n d ng ch vi t (VnDOCR) c a vi n Công ngh Thông tin Hà N i, nh n d ng vân tay, nh n d ng m t ng ưi trong khoa h c hình s 1.1.4.4. ð h a minh h a (Presentation Graphics) 3
8. Ch ươ ng I. Các y u t c ơ s c a ñ h a ðây là l ĩnh v c ñ h a bao g m các công c tr giúp cho vi c hi n th các s li u th ng kê m t cách tr c quan thông qua các m u ñ th ho c bi u ñ có s n. Ch ng h n nh ư các bi u ñ (Chart) trong các ph n m m Word, Excel 1.1.4.5. Ho t hình và ngh thu t Lĩnh v c ñ h a này bao g m các công c giúp cho các h a s ĩ, các nhà thi t k phim nh chuyên nghi p th c hi n các công vi c c a mình thông qua các k x o v tranh, ho t hình ho c các k x o ñin nh khác Ví d : Ph n m m x lý các k x o ho t hình nh ư: 3D Animation, 3D Studio Max , ph n m m x lý các k x o ñin nh: Adobe Primiere, Cool 3D, 1.1.5. T ng quan v m t h ñ h a (Graphics System) 1.1.5.1. H th ng ñ h a Ph n m m ñ h a: Là t p h p các câu l nh ñ h a c a h th ng. Các câu l nh l p trình dùng cho các thao tác ñ h a không ñưc các ngôn ng l p trình thông d ng nh ư PASCAL, C, h tr . Thông th ưng, nó ch cung c p nh ư là m t t p công c thêm vào trong ngôn ng . T p các công c này dùng ñ t o ra các thành ph n c ơ s c a m t hình nh ñ h a nh ư: ðim, ñon th ng, ñưng tròn, màu s c, Qua ñó, các nhà l p trình ph i t o ra các ch ươ ng trình ñ h a có kh n ăng ng d ng cao h ơn. Ph n c ng ñ h a: Là các thi t b ñin t : CPU, Card, màn hình, chu t, phím giúp cho vi c th c hi n và phát tri n các ph n m m ñ h a. 1.1.5.2. Các thành ph n c a m t h th ng ñ h a Tp h p các công c này ñưc phân lo i d a trên nh ng công vi c trong t ng hoàn cnh c th : xu t, nh p, bi n ñi nh, bao g m: • Tp công c t o ra nh g c (output primitives): cung c p các công c c ơ b n nh t cho vi c xây d ng các hình nh. Các nh g c bao g m các chu i ký t , các th c th hình h c nh ư ñim, ñưng th ng, ña giác, ñưng tròn, • Tp các công c thay ñi thu c tính (attributes): dùng ñ thay ñi thu c tính c a các nh g c. Các thu c tính c a nh g c bao g m màu s c (color), ki u ñưng th ng (line style), ki u v ăn b n (text style), m u tô vùng (area filling pattern), 4
9. Ch ươ ng I. Các y u t c ơ s c a ñ h a • T p các công c thay ñi h quan sát (viewing transformation): M t khi mà các nh g c và các thu c tính c a nó ñưc xác ñnh trong h t a ñ th c, ta c n ph i chi u ph n quan sát c a nh sang m t thi t b xu t c th . Các công c này cho phép ñnh ngh ĩa các vùng quan sát trên h t a ñ th c ñ hi n th hình nh ñó. • T p các công c ph c v cho các thao tác nh p d li u (input operations): Các ng d ng ñ h a có th s d ng nhi u lo i thi t b nh p khác nhau nh ư bút v , b ng, chu t, Chính vì v y, c n xây d ng thêm các công c này ñ ñiu khi n và x lý các d li u nh p sao cho có hi u qu . Mt yêu c u v ph n c ng không th thi u ñt ra cho các ph n m m ñ h a là: tính d mang chuy n (portability), có ngh ĩa là ch ươ ng trình có th chuy n ñi m t cách d dàng gi a các ki u ph n c ng khác nhau. N u không có s chu n hóa, các ch ươ ng trình thi t k th ưng không th chuy n ñi ñn các h th ng ph n c ng khác mà không vi t l i g n nh ư toàn b ch ươ ng trình. Sau nh ng n l c c a các t ch c chu n hóa qu c t , m t chu n cho vi c phát tri n các ph n m m ñ h a ñã ra ñi: ñó là GKS ( Graphics Kernel System - H ñ h a c ơ s). H th ng này ban ñu ñưc thi t k nh ư là m t t p các công c ñ h a hai chi u, sau ñó ñưc phát tri n ñ m r ng trong ñ h a ba chi u. Ngoài ra, còn có m t s chu n ñ h a ph bi n nh ư: • CGI (Computer Graphics Interface System): h chu n cho các ph ươ ng pháp giao ti p v i các thi t b ngo i vi. • OPENGL : th ư vi n ñ h a c a h ng Silicon Graphics. • DIRECTX : th ư vi n ñ h a c a h ng Microsoft. 1.2. MÀN HÌNH ð H A Mi máy tính ñu có m t CARD dùng ñ qu n lý màn hình, g i là Video Adapter hay Graphics Adapter. Có nhi u lo i adapter nh ư: CGA, MCGA, EGA, VGA, Hercules Các adapter có th làm vi c hai ch ñ: v ăn b n (Text Mode) và ñ h a (Graphics Mode). Có nhi u cách ñ kh i t o các mode ñ h a. Ta có th s d ng hàm $00 ng t $10 ca BIOS v i các Mode sau: 5
10. Ch ươ ng I. Các y u t c ơ s c a ñ h a • Mode $12: ch ñ phân gi i 640x480x16 • Mode $13: ch ñ phân gi i 320x200x256 Ta có th vi t m t th t c ñ kh i t o ch ñ ñ h a nh ư sau: Procedure InitGraph(Mode:Word); var Reg:Registers; Begin reg.ah := 0; reg.al := mode; intr($10,reg); End; Các b n có th tham kh o thêm các tài li u v l p trình h th ng. 1.3. CÁC KHÁI NI M 1.3.1. ðim (Pixel) Trong các h th ng ñ h a, m t ñim ñưc bi u th b i các t a ñ b ng s . Ví du : Trong m t phng, m t ñim là m t c p (x,y) Trong không gian ba chi u, m t ñim là b ba (x,y,z) Trên màn hình c a máy tính, m t ñim là m t v trí trong vùng nh màn hình dùng ñ l ưu tr các thông tin v ñ sáng c a ñim t ươ ng ng trên màn hình. S ñim v trên màn hình ñưc g i là ñ phân gi i c a màn hình (320x200, 480x640, 1024x1024, ) Cách hi n th thông tin lên màn hình ñ h a: Vùng ñm màn hình hay còn g i là b nh hi n th ñưc b t ñu t ña ch A000h:$0000h . Vì v y, ñ hi n th thông tin ra màn hình thì ta ch c n ñư a thông tin vào vùng ñm màn hình b t ñu t ña ch trên là ñưc. Có nhi u cách ñ v m t ñim ra màn hình: có th dùng các ph c v c a BIOS ho c cũng có th truy xu t tr c ti p vào vùng nh màn hình. • Nu dùng ph c v c a BIOS, ta dùng hàm $0C ng t $10: Procedure PutPixel(Col,Row:Word; Color:Byte); Var reg:Registers; Begin reg.ah:=$0C; reg.al:=Color; 6
11. Ch ươ ng I. Các y u t c ơ s c a ñ h a reg.bh:=0; reg.cx:=Col; reg.dx:=Row; Intr($10,reg); End; • Nu mu n truy xu t tr c ti p vào vùng ñm màn hình: Gi s m t ñim (x,y) ñưc v trên màn hình v i ñ phân gi i 320x200x256 (mode 13h), ñim ñó s ñưc ñnh v trong vùng ñm b t ñu t ña ch segment A000h và ña ch offset ñưc tính theo công th c: Offset = y*320 + x . Ta có th vi t th t c nh ư sau: Procedure PutPixel(x,y:Word; Color:Byte); Var Offset:Word; Begin Offset:=(y shl 8) + (y shl 6) + x; Mem[$A000:Offset]:=Color; End; 1.3.2. Các bi u di n t a ñ Hu h t các ch ươ ng trình ñ h a ñu dùng h t a ñ Decartes (Hình 1.1). Ta bi n ñi: O MaxX Y Y O X X MaxY Ta ñ th gi i th c Ta ñ thi t b màn hình. Hình 1.1 1.3.3. ðon th ng Trong các h th ng ñ h a, các ñon th ng ñưc bi u th b i vi c “tô” ñon th ng bt ñu t ñim ñu mút này kéo dài cho ñn khi g p ñim ñu mút kia. 1.4. CÁC THUT TOÁN V ðON TH NG 7
12. Ch ươ ng I. Các y u t c ơ s c a ñ h a 1.4.1. Bài toán : V ñon th ng ñi qua 2 ñim A(x1,y1) và B(x2,y2) * Tr ưng h p x1=x2 ho c y1=y2: r t ñơ n gi n. * Tr ưng h p ñưng th ng có h s góc m: Ý t ưng : Vì các Pixel ñưc v các v trí nguyên nên ñưng th ng ñưc v gi ng nh ư hình bc thang (do làm tròn). Vn ñ ñt ra là ch n các t a ñ nguyên g n v i ñưng th ng nh t. 1.4.2. Thu t toán DDA (Digital differential analyzer) Xét ñưng th ng có h s góc 0 1: ta hoán ñi vai trò c a x,y cho nhau. N u ch n ∆y=1 thì: xk+1 = x k + 1/m Tươ ng t , n u ñim B n m bên trái và A n m bên ph i thì: yk+1 = yk - m (0 1, ∆y= -1) Tóm l i: Ta có thu t toán v ñưng th ng DDA nh ư sau:
    Nh p A(x1,y1) B(x2,y2)
    Tính ∆x = x2 - x1 ∆y = y2 - y1 Step = Max(| ∆x| , | ∆y|)
    Kh i t o các giá tr : IncX = ∆x/Step; IncY = ∆y/Step; {b ưc t ăng khi v } x = x1; y = y1; {Ch n ñim v ñu tiên} V ñim (x,y);
    Cho i ch y t 1 ñn Step:  x = x + IncX; y = y + IncY;  V ñim (Round(x),Round(y)) T ñó ta có th t c v ñon th ng theo thu t toán DDA nh ư sau: Procedure DDALine(x1,y1,x2,y2:Integer); var dx,dy,step,i:integer; 8
13. Ch ươ ng I. Các y u t c ơ s c a ñ h a xInc,yInc,x,y:real; Begin dx:=x2-x1; dy:=y2-y1; If abs(dx)>abs(dy) Then step:=abs(dx) else step:=abs(dy); xInc:=dx/step; yInc:=dy/step; x:=x1; y:=y1; Putpixel(round(x),round(y),15); for i:=1 to step do Begin x:=x+xInc; y:=y+yInc; Putpixel(round(x),round(y),15); End; End; 1.4.3. Thu t toán Bresenham Ph ươ ng trình ñưng th ng có th phát bi u d ưi d ng: y = m.x + b (1) yi+ Ph ươ ng trình ñưng th ng qua 2 ñim: 1 x − x1 y − y1 y = (*) x2 − x1 y2 − y1 yi ðt ∆x = x2 - x1 ∆y = y2 - y1 xi xi+1 ∆y ∆y (*) ⇔ y = x. + y1 - x1. Hình 1.2 ∆x ∆x ∆y Suy ra m = nên ∆y = m. ∆x (2) ∆x b = y1 - m.x1 (3) Ta ch xét tr ưng h p h s góc 0<m<1. Gi s ñim (xi,yi) ñã ñưc v . Ta ph i ch n ñim k ti p là: 9
14. Ch ươ ng I. Các y u t c ơ s c a ñ h a (x i + 1,y i) ho c (x i +1,y i +1) (Xem hình 1.2) Xét kho ng cách gi a 2 ñim ch n v i ñim n m trên ñưng th c. N u kho ng cách nào bé h ơn thì ta l y ñim ñó. ðt: d1 = y - y i = m.(x i +1) + b - y i d2 = (y i +1) - y = y i + 1 - m.(x i + 1) - b Suy ra: d1 - d 2 = 2m.(x i + 1) - 2y i + 2b - 1 ∆y = 2. .(x i + 1) - 2y i + 2b - 1 ∆x ⇔ ∆x(d 1 - d 2) = 2 ∆y.x i - 2 ∆x.y i + 2 ∆y + ∆x.(2b - 1) ðt pi = ∆x(d 1 - d 2) và C = 2 ∆y + ∆x.(2b - 1) thì pi = 2 ∆y.x i - 2 ∆x.y i + C (4) pi+1 = 2 ∆y.x i+1 - 2 ∆x.y i+1 + C Suy ra: pi+1 - p i = 2 ∆y(x i+1 - x i) - 2 ∆x(y i - y i+1 ) = 2 ∆y - 2 ∆x(y i+1 - y i) (5) ( vì x i+1 - x i = 1 ) * Nh n xét : . N u p i d 2) Vi ñim mút ñu tiên, theo (4) ta có: p1 = 2 ∆y.x 1 - 2 ∆x.y 1 + 2 ∆y + ∆x[2.(y 1 - m.x 1) - 1] = 2 ∆y - ∆x T ñó, ta có th tóm t t thu t toán v ñưng th ng theo Bresenham cho tr ưng h p h s góc 0<m<1 nh ư sau: • Bưc 1 : Nh p các ñim ñu mút. ðim ñu mút bên trái ch a t a ñ (x1,y1), ñim ñu mút bên ph i ch a t a ñ (x2,y2). • Bưc 2 : ðim ñưc ch n ñ v ñu tiên là (x1,y1). • Bưc 3 : Tính ∆x = |x2 - x1| , ∆y = |y2 - y1| và P 1 = 2 ∆y - ∆x Nu p i < 0 thì ñim k ti p là (x i + 1,y i) Ng ưc l i: ñim k ti p là (x i + 1,y i + 1) 10
15. Ch ươ ng I. Các y u t c ơ s c a ñ h a • Bưc 4 : Ti p t c t ăng x lên 1 Pixel. v trí x i +1, ta tính: pi+1 = p i + 2 ∆y nu p i x2 then begin x:=x2; y:=y2; xMax:=x1; end else begin x:=x1;y:=y1;xMax:=x2; end; putpixel(x,y,red); while x<xMax do begin x:=x+1; if p<0 then p:=p+c1 else begin y:=y+1; p:=p+c2; end; 11
16. Ch ươ ng I. Các y u t c ơ s c a ñ h a putpixel(x,y,red); end; end; 1.4.4. Thu t toán MidPoint Ta ch xét tr ưng h p h s góc 0 0 n u (x,y) n m phía d ưi ñưng th ng Lúc này, vi c ch n các ñim S hay P ñưc ñư a v vi c xét d u c a: 1 pi = F(M) = F(x i + 1,y i + ) 2
    Nu p i < 0 ⇒ M n m trên ñon th ng ⇒ Q n m d ưi M ⇒ Ch n S P y +
    Nu p i ≥ 0 ⇒ M n m d ưi ñon i 1 Q th ng ⇒ Q n m trên M ⇒ Ch n P M Mt khác: S 1 yi pi = F(x i + 1,y i + ) 2 1 xi pi+1 = F(x i+1 + 1,y i+1 + ) xi+1 2 Hình 1.3 nên 1 1 pi+1 - p i = F(x i+1 + 1,y i+1 + ) - F(x i + 1,y i + ) 2 2 12
17. Ch ươ ng I. Các y u t c ơ s c a ñ h a 1 1 = A(x i+1 +1) + B(y i+1 + ) + C - A(x i+1) - B(y i + ) - C 2 2 = A(x i+1 - x i) + B(y i+1 - y i) = A + B(y i+1 - y i) (vì x i+1 - x i =1) Suy ra: pi+1 = p i + A + B(y i+1 - y i) (*) *Nh n xét: . N u p i < 0: Ch n ñim S: yi+1 = y i T (*) suy ra p i+1 = p i + A . N u p i ≥ 0: Ch n ñim P: yi+1 = y i + 1 T (*) suy ra p i+1 = p i + A + B Vi ñim mút ñu tiên, ta có: 1 1 p1 = F(x 1 + 1,y 1 + ) = A(x 1+1) + B(y 1 + ) + C 2 2 B B = Ax 1 + Bx 1 + C + A + = A + (vì Ax 1 + Bx 1 + C = 0) 2 2 Thu t toán MidPoint cho k t qu t ươ ng t nh ư thu t toán Bresenham. 1.5. THU T TOÁN V ðƯNG TRÒN Xét ñưng tròn (C) tâm O(x c,y c) bán kính R. (- (y,x Ph ươ ng trình t ng quát c a ñưng tròn có d ng: y,x) ) (x - x )2 + (y - y )2 = R 2 (*) (- (x,y c c x,y) ) ⇔ ± 2− − 2 y = y c R() x xC (1) (-x,- (x,- ð ñơ n gi n thu t toán, ñu tiên ta xét ñưng y) y) (-y,- ( tròn có tâm g c t a ñ (x c=0 và y c=0). x) y, - * Ý t ưng : Hình 1.4 Do tính ñi x ng c a ñưng tròn nên n u ñim (x,y) ∈(C) thì các ñim (y,x), (-y,x), (-x,y), (-x,-y), (-y,-x), (y,-x), (x,-y) c ũng ∈ (C) (Hình 1.4) Vì v y, ta ch c n v m t ph n tám cung tròn r i l y ñi x ng qua g c O và 2 tr c to ñ thì ta có ñưc toàn b ñưng tròn. 1.5.1. Thu t toán Bresenham Gi s (x i,y i) ñã v ñưc. C n ch n ñim k ti p là (x i +1,y i) ho c (x i +1,y i -1) (Hình 1.5) T ph ươ ng trình: x 2 + y 2 = R 2 ta tính ñưc giá tr y th c ng v i x i +1 là: 13
18. Ch ươ ng I. Các y u t c ơ s c a ñ h a 2 2 2 y = R - (x i +1) 2 2 2 2 2 ðt: d1 = y i - y = y i - R + (x i + 1) 2 2 2 2 2 d2 = y - (y i - 1) = R - (x i + 1) - (y i - 1) yi y Suy ra: yi- 2 2 2 2 1 pi = d 1 - d 2 = 2.(x i + 1) + y i + (y i - 1) - 2R (2) 2 2 2 2 ⇒ pi+1 = 2.(x i+1 + 1) + y i+1 + (y i+1 - 1) - 2R (3) T (2) và (3) ta có: xi x +1 2 2 i pi+1 - p i = 4x i + 6 + 2.(y i+1 - y i ) - 2.(y i+1 - y i) Hình 1.5 2 2 ⇒ pi+1 = p i + 4x i + 6 + 2.(y i+1 - y i ) - 2.(y i+1 - y i) (4) * Nh n xét : Nu p i < 0: ch n y i+1 = y i (4) ⇒ p i+1 = p i + 4x i + 6 Nu p i ≥ 0: ch n y i+1 = y i - 1 (4) ⇒ p i+1 = p i + 4.(x i - y i) + 10 Ta ch n ñim ñu tiên c n v (0,R), theo (2) ta có: p1 = 3 - 2R Tóm l i: Ta có thu t toán v ñưng tròn: • Bưc 1 : Ch n ñim ñu c n v (x1,y1) = (0,R) • Bưc 2 : Tính P ñu tiên: p1 = 3 - 2R Nu p < 0: ch n ñim k ti p là (x i +1,y i). Ng ưc l i ch n ñim (x i + 1,y i - 1) • Bưc 3 : x:=x + 1, tính l i p: N u p i < 0: p i+1 = p i + 4x i + 6. Ng ưc l i: p i+1 = p i + 4.(x i - y i) + 10 Khi ñó: N u p i+1 < 0: ch n ñim k ti p là (x i +1,y i+1 ). Ng ưc l i ch n ñim (x i+1,y i+1 -1) • Bưc 4 : L p l i b ưc 3 cho ñn khi x = y. Sau ñây là th t c ñ cài ñt thu t toán: Procedure Circle(x0,y0,r:Integer); Var p,x,y:Integer; Procedure VeDiem; Begin PutPixel( x0 + x , y0 + y , color); PutPixel( x0 - x , y0 + y , color); PutPixel( x0 + x , y0 - y , color); PutPixel( x0 - x , y0 - y , color); 14
19. Ch ươ ng I. Các y u t c ơ s c a ñ h a PutPixel( x0 + y , y0 + x , color); PutPixel( x0 - y , y0 + x , color); PutPixel( x0 + y , y0 - x , color); PutPixel( x0 - y , y0 - x , color); End; Begin x:=0; y:=r; p:=3 - 2*r; While x 0 n u (x,y) ngoài ñưng tròn Lúc này, vi c ch n các ñim S(x i+1,y i) hay xi xi+1 P(x +1,y -1) ñưc ñư a v vi c xét d u c a: Hình i i 1.6 1 pi = F(M) = F(x i + 1,y i - ) (Hình 1.6) 2
    Nu p i < 0 ⇒ M n m trong ñưng tròn ⇒ Q g n S h ơn ⇒ Ch n S
    Nu p i ≥ 0 ⇒ M n m ngoài ñưng tròn ⇒ Q g n P h ơn ⇒ Ch n P 15
20. Ch ươ ng I. Các y u t c ơ s c a ñ h a Mt khác: 1 pi = F(x i + 1,y i - ) 2 1 pi+1 = F(x i+1 + 1,y i+1 - ) 2 nên 1 1 pi+1 - p i = F(x i+1 + 1,y i+1 - ) - F(x i + 1,y i - ) 2 2 2 1 2 2 2 1 2 2 = [(x i+1 +1) + (y i+1 - ) - R ] - [(x i+1) + (y i - ) - R ] 2 2 2 1 2 2 2 1 2 2 = [(x i+2) + (y i+1 - ) - R ] - [(x i+1) + (y i - ) - R ] 2 2 2 2 = 2x i + 3 + (y i+1 - y i ) - (y i+1 - y i) Suy ra: 2 2 pi+1 = p i + 2x i + 3 + (y i+1 - y i ) - (y i+1 - y i) (*) *Nh n xét: . N u p i < 0: Ch n ñim S : yi+1 = y i T (*) ⇒ pi+1 = p i + 2x i + 3 . N u p i ≥ 0: Ch n ñim P: yi+1 = y i - 1 T (*) ⇒ pi+1 = p i + 2(x i - y i) + 5 Vi ñim ñu tiên (0,R), ta có: 1 1 1 2 2 5 p1 = F(x 1 + 1,y 1 - ) = F(1,R - ) = 1 + (R - ) - R = - R 2 2 2 4 1.6. THU T TOÁN V ELLIPSE ð ñơ n gi n, ta ch n Ellipse có tâm g c t a ñ. Ph ươ ng trình c a nó có d ng: x 2 y 2 + = 1 a 2 b 2 b 2 Ta có th vi t l i: y2 = - .x 2 + b 2 (*) a 2 *Ý t ưng : Gi ng nh ư thu t toán v ñưng tròn. Hình 1.7 Ch có s khác bi t ñây là ta ph i v 2 nhánh: M t nhánh t trên xu ng và m t nhánh t d ưi lên và 2 nhánh này s g p nhau t i ñim mà ñó h s góc c a ti p tuy n v i Ellipse = -1 (Hình 1.7). Ph ươ ng trình tip tuy n v i Ellipse t i ñim (x 0,y 0) ∈ (E) : 16
21. Ch ươ ng I. Các y u t c ơ s c a ñ h a x y x0. + y0. = 1 a 2 b 2 2 x0 .b Suy ra, h s góc c a ti p tuy n t i ñim ñó là: - 2 . y0 a 1.6.1. Thu t toán Bresenham ñây, ta ch xét nhánh v t trên xu ng. Gi s ñim (x i,y i) ñã ñưc v . ðim ti p theo c n ch n s là (x i+1,y i) ho c (x i+1,y i-1) 2 2 b 2 2 Thay (x i +1) vào (*): y = - .(x i +1) + b a 2 ðt: 2 2 2 2 b 2 2 d1= yi - y = y i + .(x i +1) -b a 2 2 2 2 b 2 2 2 d2= y - (y i -1) = - .(x i +1) + b - (y i -1) a 2 2 b 2 2 2 ⇒ pi = d 1 - d 2 = 2.[ .(x i +1) - b ] + 2.(y i + y i) -1 a 2 2 b 2 2 2 pi+1 = 2.[ .(x i+1 +1) - b ] + 2.(y i+1 + y i+1 ) -1 a 2 Suy ra: 2 b 2 2 2 2 pi+1 - p i = 2. .[(x i+1 +1) - (x i +1) ] + 2.( y i+1 - y i + y i+1 - y i) ( ) a 2 *Nh n xét : • pi < 0: Ch n y i+1 = y i b 2 ( ) ⇒ p i+1 = p i + 2. .(2x + 3) a 2 • pi ≥ 0: Ch n y i+1 = y i -1 b 2 ( ) ⇒ p i+1 = p i + 2. .(2x + 3) - 4y i a 2 Vi ñim ñu tiên (0,b), ta có: b 2 p 1 = 2 - 2b + 1 a 2 T ñó, ta có th t c v Ellipse nh ư sau: 17
22. Ch ươ ng I. Các y u t c ơ s c a ñ h a Procedure Ellipse(xc,yc,a,b:Integer;Color:Byte); Var p,a2,b2:real; x,y:integer; (* *) Procedure VeDiem; Begin PutPixel(xc+x,yc+y,Color); PutPixel(xc-x,yc+y,Color); PutPixel(xc-x,yc-y,Color); PutPixel(xc+x,yc-y,Color); End; (* *) Begin a2:=a*a; b2:=b*b; {Nhanh 1} x:=0; y:=b; p:=2*b2/a2 - 2*b + 1; While (b2/a2)*(x/y)<1 do Begin VeDiem; If p<0 then p:=p + 2*(b2/a2)*(2*x+3) else Begin p:=p - 4*y + 2*(b2/a2)*(2*x+3); y:=y-1; End; x:=x+1; End; {Nhanh 2} y:=0; x:=a; p:=2*(a2/b2) - 2*a + 1; While (a2/b2)*(y/x)<=1 do 18
23. Ch ươ ng I. Các y u t c ơ s c a ñ h a Begin VeDiem; If p 0 Then p i+1 = p i + a - 2a yi+1 2 2 2 else p i+1 = p i + a + 2b xi+1 - 2a yi+1 Procedure MidEllipse(xc,yc,a,b:Integer;Color:Byte); Var p,a2,b2:real; x,y:Integer; (* *) Procedure VeDiem; Begin PutPixel(xc+x,yc+y,Color); PutPixel(xc-x,yc+y,Color); PutPixel(xc-x,yc-y,Color); 19
24. Ch ươ ng I. Các y u t c ơ s c a ñ h a PutPixel(xc+x,yc-y,Color); End; (* *) Begin a2:=a*a; b2:=b*b; {Nhanh 1} x:=0; y:=b; Vediem; p:=b2 - a2*b + 0.25*a2; While (b2/a2)*(x/y) 0 do Begin y:=y-1; If p>0 Then p:=p + a2 - 2*a2*y else begin x:=x+1; p:=p + a2 + 2*b2*x - 2*a2*y; end; Vediem; End; 20
25. Ch ươ ng I. Các y u t c ơ s c a ñ h a End; 1.7. PH ƯƠ NG PHÁP V ð TH HÀM S 1.7.1. Bài toán : V ñ th c a hàm s y = f(x) trên ñon [Min,Max]. *Ý t ưng : Cho x ch y t ñu ñn cu i ñ l y các t a ñ (x,f(x)) sau ñó làm tròn thành s nguyên r i n i các ñim ñó l i v i nhau. 1.7.2. Gi i thu t: • Bưc 1: Xác ñnh ñon c n v [Min,Max]. • Bưc 2: - ðt g c t a ñ lên màn hình (x0,y0). - Chia t l v trên màn hình theo h s k. - Ch n b ưc t ăng dx c a m i ñim trên ñon c n v . • Bưc 3: Ch n ñim ñu c n v : x = Min, tính f(x) ði qua t a ñ màn hình và làm tròn: x1:=x0 + Round(x.k); y1:=y0 - Round(y.k); Di chuy n ñn (x1,y1): MOVETO(x1,y1); • Bưc 4 : Tăng x lên v i s gia dx: x:=x + dx; ði qua t a ñ màn hình và làm tròn: x2:=x0 + Round(x.k); y2:=y0 - Round(y.k); V ñn (x2,y2): LINETO(x2,y2); • Bưc 5: L p l i b ưc 4 cho ñn khi x > Max thì d ng. Ví d : V ñ th hàm s f(x) = Sin(x) Uses crt,Graph; Var dau,cuoi:real; Gd,Gm:Integer; Function F(x:real):real; Begin F:=Sin(x); End; Procedure VeHinhSin(ChukyDau,ChuKyCuoi:real); 21
26. Ch ươ ng I. Các y u t c ơ s c a ñ h a var x1,y1,x2,y2:integer; a,x,k:real; x0,y0:word; Begin x0:=GetMaxX div 2; y0:=GetMaxY div 2; K:=GetMaxX/30; a:=Pi/180; x:=ChuKyDau; x1:=x0 + Round(x*k); y1:=y0 - Round(F(x)*k); Moveto(x1,y1); While x<ChuKyCuoi do Begin x:=x+a; x2:=x0 + Round(x*k); y2:=y0 - Round(F(x)*k); LineTo(x2,y2); End; End; BEGIN Gd:=0; InitGraph(Gd,Gm,’C:\BP\BGI’); Dau:=-4*Pi; cuoi:=4*Pi; VeHinhSin(Dau,cuoi); repeat until KeyPressed; CloseGraph; END. BÀI T P 1. Cho hai ñim A(20,10) và B(25,13). Hãy tính các giá tr Pi, xi, yi m i b ưc khi v ñon th ng AB theo thu t toán Bresenham/MidPoint và k t q a ñin vào b ng sau: i 1 2 3 4 5 6 22
27. Ch ươ ng I. Các y u t c ơ s c a ñ h a Pi ? ? ? ? ? ? xi ? ? ? ? ? ? yi ? ? ? ? ? ? 2. Cài ñt th t c v ñon th ng theo thu t toán Bresenham và MidPoint cho các tr ưng h p h s góc m>1, m<-1, -1<m<0. 3. Vi t th t c LineTo(x,y:Integer); ñ v ñon th ng t v trí hi n th i ñn ñim có ta ñ (x,y). 4. Vi t th t c LineRel(dx,dy:Integer); ñ v ñon th ng t v trí hi n th i ñn ñim mi cách ñim hi n th i m t kho ng theo tr c x là dx và theo tr c y là dy. 5. Cài ñt th t c v ñưng tròn theo thu t toán MidPoint. 6. Vi t th t c Arc(x0,y0,g1,g2:Integer; R:Word); ñ v cung tròn có tâm (x0,y0) bán kính R v i góc b t ñu là g1 và góc k t thúc là g2. 7. Vi t th tc Sector(x0,y0,g1,g2:Integer; Rx,Ry:Word); ñ v cung Ellipse có tâm (x0,y0) bán kính theo tr c X là Rx, bán kính theo tr c Y là Ry v i góc b t ñu là g1 và góc k t thúc là g2. 8. Vi t th t c DrawPoly(P:Array; n:Byte; xc,yc,R:Word); ñ v m t ña giác ñu có n ñnh l ưu trong m ng P n i ti p trong ñưng tròn tâm (xc,yc) bán kính R. 9. Vi t th t c Circle3P(A,B,C:ToaDo2D); ñ v ñưng tròn ñi qua 3 ñim A,B,C. 10. Vi t th t c Arc3P(A,B,C:ToaDo2D); ñ v cung tròn ñi qua 3 ñim A,B,C. 11. V ñ th các hàm s sau: y = ax 2 + bx + c, y = ax 3 + bx 2 + cx + d, y = ax 4 + bx 3 + cx 2 + dx + e ax + b ax 2 + bx + c y = , y = . cx + d dx + e 12. V các ñưng cong sau: x 2 y 2 x 2 y 2 y2 = 2px + = 1 - = ±1 a 2 b 2 a 2 b 2 Bài t p l n: Vi t ch ươ ng trình kh o sát và v ñ th các hàm s s ơ c p bài t p s 11. 23
28. CH ƯƠ NG 2 TÔ MÀU 2.1. GI I THI U V CÁC H MÀU Giác quan c a con ng ưi c m nh n ñưc các v t th xung quanh thông qua các tia sáng màu t t h ơn r t nhi u so v i 2 màu tr ng ñen. Vì v y, vi c xây d ng nên các chu n màu là m t trong nh ng lý thuy t c ơ b n ca lý thuy t ñ h a. Vi c nghiên c u v màu s c ngoài các y u t v m t v t lý nh ư b ưc sóng, c ưng ñ, còn có 3 y u t khác liên quan ñn c m nh n sinh lý c a m t ng ưi d ưi tác ñng ca chùm sáng màu ñi ñn t v t th là: Hue (s c màu), Saturation ( ñ bo hòa), Lightness ( ñ sáng). M t trong nh ng h màu ñưc s d ng r ng rãi ñu tiên do A.H.Munsell ñư a ra vào n ăm 1976, bao g m 3 y u t : Hue, Lightness và Saturation. Ba mô hình màu ñưc s d ng và phát tri n nhi u trong các ph n c ng là: RGB - dùng v i các màn hình CRT (Cathode ray bube), YIQ – dùng trong các h th ng ti vi màu b ăng t n r ng và CMY - s d ng trong m t s thi t b in màu. Ngoài ra, còn có nhi u h màu khác nh ư: HSV, HSL, YIQ, HVC, 2.1.1.H RGB (Red, Green, Blue) Mt c a chúng ta cm nh n ba màu rõ nh t là Red ( ñ), Green (l c), Blue (xanh). Vì v y, ng ưi ta ñã xây d ng mô hình màu RGB (Red,Green, Blue) là t p t t c các màu ñưc xác ñnh thông qua ba màu v a nêu. Chu n này ñu tiên ñưc xây d ng cho các h vô tuy n truy n hình và trong các máy vi tính. T t nhiên, không ph i là t t c các màu ñu có th bi u di n qua ba màu nói trên nh ưng h u h t các màu ñu có th chuy n v ñưc. H này ñưc xem nh ư m t kh i ba chi u v i màu Red là tr c X, màu Green là tr c Y và màu Blue là tr c Z. M i màu trong h này ñưc xác ñnh theo ba thành ph n RGB (Hình 2.1).
29. Ch ươ ng II. Tô màu Z Blue Cyan Magenta White Y Black Green Red Yellow X Hình 2.1. H màu RGB Ví d : Màu Red là (1, 0, 0) Màu Blue là (0, 0, 1) Red + Green = Yellow Red + Green + Blue = White 2.1.2. H CMY (Cyan, Magenta, Yellow) H này c ũng ñưc xem nh ư m t kh i ba chi u nh ư h RGB. Nh ưng h CMY trái ng ưc v i h RGB, ch ng h n: White có thành ph n (0, 0, 0) Cyan có thành ph n (1, 0, 0) Green có thành ph n (1, 0, 1) Sau ñây là công th c chuy n ñi t h RGB → CMY :  C  1 R   =   −   M  1 G  Y  1 B 2.1.3. H YIQ H màu này ñưc ng d ng trong truy n hình màu b ăng t n r ng t i M , do ñó nó có m i quan h ch t ch v i màn hình raster. YIQ là s thay ñi c a RGB cho kh năng truy n phát và tính t ươ ng thích vi ti vi ñen tr ng th h tr ưc. Tín hi u truy n s dng trong h th ng NTSC (National Television System Committee). Sau ñây là công th c bi n ñi t h RGB thành h YIQ: 26
30. Ch ươ ng II. Tô màu Y   .0 299 .0 587 .0 114  R   =  − −     I   .0 596 .0 275 .0 321  * G Q  .0 212 − .0 523 .0 311  B Ma tr n ngh ch ño c a ma tr n bi n ñi RGB thành h YIQ ñưc s d ng cho phép bi n ñi t h YIQ thành RGB. 2.1.4. H HSV (Hue, Saturation, Value) Mô hình màu này còn ñưc g i là h HSB v i B là Brightness ( ñ sáng) d a trên c ơ s n n t ng tr c giác v tông màu, s c ñ và s c thái m thu t (Hình 2.2). Hue có giá tr t 0 0 → 360 0 S, V có giá tr t 0 → 1 V Green Yellow 1.0 Cyan White Red Blue White H S 0.0 Black Hình 2. 2. H m àu HSV Ví d : Red ñưc bi u di n (0 0, 1, 1) Green ñưc bi u di n (120 0,1,1) 2.1.5. H HSL (Hue, Saturation, Lightness) H này ñưc xác ñnh b i t p h p hình chóp sáu c nh ñôi c a không gian hình tr (hình 2.3). 1.0 L White Green Yellow Cyan 0.5 Red Blue White H S 0.0 Black Hình 2.3. H màu HSL 27
31. Ch ươ ng II. Tô màu 2.2. CÁC THU T TOÁN TÔ MÀU 2.2.1. Bài toán P2 Cho ña giác S xác ñnh b i n ñnh : P 1, P 2, W , P n. Hãy tô màu mi n S. P1 P3 * Ph ươ ng pháp t ng quát : S - Tìm hình ch nh t W nh nh t ch a S P5 (hình 2.4). - Duy t qua t t c các ñim P(x, y) ∈ W. P4 Nu P ∈ S thì tô màu ñim P. Hình 2.4 2.2.2. Thu t toán xác ñnh P ∈∈∈ S 2.2.2.1. S là ña giác l i - L y P ∈ W, n i P v i các ñnh c a S thì ta ñưc n tam giác : S i= PP iPi+1 , v i Pn+1 =P 1. n - N u ∑dt(S i ) = dt(S) thì P ∈ S. i=1 Ta có công th c tính di n tích c a S: n 1 − S= |∑( iyx i+1 xi+1yi |) 2 i=1 2.2.2.2. Tr ưng h p t ng quát (Thu t toán Jordan) L y P(x, y) ∈ W, k n a ñưng th ng ∆P xu t phát t P và không ñi qua các ñnh ca ña giác S. Gi S(P) là s giao ñim c a ∆P v i các biên c a S. Nu S(P) l thì P ∈ S. * V n ñ còn l i là tìm S(P): Bưc 1 : K n a ñưng th ng ∆P // 0y và h ưng v phía y>0. Bưc 2 : V i m i c nh C i= P iPi+1 c a S: + N u x=x i thì xét 2 c nh có 1 ñu là P i: Nu y<y i thì 28
32. Ch ươ ng II. Tô màu • Nu c 2 ñu kia cùng m t phía c a ∆P thì ta tính ∆P c t c 2 c nh. • Ng ưc l i : ∆P c t 1 c nh. + Ng ưc l i: • Nu x>Max(x i,x i+1 ) ho c x = y 0 thì ∆P không c t C i. Ng ưc l i ∆P c t C i. Thu t toán này có th ñưc cài ñt b ng ñon ch ươ ng trình nh ư sau: Type ToaDo=record x,y:integer; End; Mang=array[0 30] of ToaDo; Function SOGIAODIEM(a:Mang; n:Byte):Integer; var dem,i,j,s:Integer; Begin dem:=0; for i:=1 to n do { Tim so giao diem } begin if i=n then j:=1 else j:=i+1; if i=1 then s:=n else s:=i-1; if x=a[i].x then begin if y =Max(a[s].x,a[j].x)) then dem:=dem+2 else dem:=dem+1; end else if (x>Min(a[i].x,a[j].x)) and (x<Max(a[j].x,a[i].x)) then if y<=Min(a[i].y,a[j].y) then dem:=dem+1 else if y <= (x-a[j].x)*(a[i].y-a[j].y)/ (a[i].x-a[j].x)+a[j].y then dem:=dem+1; end; SOGIAODIEM:=dem; End; 29
33. Ch ươ ng II. Tô màu 2.2.3. Thu t toán tô màu theo dòng quét (Scanline) ðt x = Min(x ), i ∈ [1,n]. 0 i y Bưc 1 : K Dy//0y ñi qua x 0 (hình 2.5). Dy Bưc 2 : Xác ñnh các giao ñim M i- (x,y) c a Dy v i các c nh C i. Nu có c nh C i = P iPi+1 song song và trùng v i Dy thì xem nh ư Dy c t Ci t i 2 ñim P i và P i+1 . Bưc 3 : S p x p l i các ñim M i theo x0 xi th t t ăng d n ñi v i y ( ñim ñu x i Hình 2.5 tiên có th t là 1). Bưc 4 : Nh ng ñim n m trên Dy gi a giao ñim l và giao ñim ch n liên ti p là nh ng ñim n m trong ña giác và nh ng ñim này s ñưc tô. Bưc 5 : T ăng x 0 lên m t Pixel. N u x 0 ≤ Max(x i) thì quay l i b ưc 1. 2.2.4. Thu t toán tô màu theo v t d u loang ∈ Ly P(x,y) S, tô màu P. X Xét các ñim lân c n c a P (Hình 2.6). X O X O Nu các ñim lân c n ñó v n còn thu c S và ch ưa X ñưc tô màu thì tô màu các ñim lân c n ñó Thu t toán trên có th ñưc minh h a b ng th t c Hình 2.6 ñ qui: Procedure TOLOANG(x,y:Integer; Color:Word); Begin If (P(x,y) ∈S)and(P(x,y)ch ưa tô) Then Begin PutPixel(x,y,Color); TOLOANG(x+1,y,Color); TOLOANG(x-1,y,Color); 30
34. Ch ươ ng II. Tô màu TOLOANG(x,y+1,Color); TOLOANG(x,y-1,Color); End; End; BÀI T P 1. Vi t hàm DienTich(P:Array; n:Byte); ñ tính di n tích c a ña giác l i có n ñnh lưu trong m ng P. 2. Vi t hàm KiemTra(x,y:Integer; P:Array; n:Byte):Boolean; ñ ki m tra ñim (x,y) n m trong hay ngoài ña giác có n ñnh ñưc l ưu trong m ng P theo hai cách: - Dùng công th c tính di n tích ña giác ( ñi v i ña giác l i). - Dùng thu t toán Jordan ( ñi v i ña giác b t k ỳ). 2. Vi t ch ươ ng trình cài ñt thu t toán tô màu m t ña giác theo thu t toán Scanline. 3. Vi t ch ươ ng trình cài ñt thu t toán tô màu m t ña giác theo v t d u loang theo hai ph ươ ng án: a. ð qui. b. Kh ñ qui. 4. Vi t th t c FillRec(x1,y1,x2,y2:Integer; color:Byte); ñ tô màu hình ch nh t xác ñnh b i 2 ñnh (x1,y1) và (x2,y2). 5. Vi t th t c FillEllipse(x,y,Rx,Ry:Integer; color:Byte); ñ tô màu Ellipse có tâm (x,y) và bán kính theo hai tr c là Rx và Ry. 6. Vi t th t c FillSector(x,y,Rx,Ry,g1,g2:Integer; color:Byte); ñ tô màu hình qu t Ellipse có tâm (x,y), bán kính theo hai tr c là Rx và Ry, góc b t ñu là g1 và góc k t thúc là g2. 7. Vi t th t c Donut(x,y,Rmin,Rmax:Integer; color:Byte); ñ tô màu hình vành kh ăn có tâm (x,y) và bán kính hai ñưng tròn t ươ ng ng là Rmin và Rmax. Bài t p l n: Xây d ng m t th ư vi n ñ h a MYGRAPH t ươ ng t nh ư th ư vi n GRAPH.TPU c a Turbo Pascal. 31
35. CH ƯƠ NG III XÉN HÌNH 3.1. ðT V N ð Cho m t mi n D ⊂ R n và F là m t hình trong R n (F ⊂ R n). Ta g i F ∩ D là hình có ñưc t F b ng cách xén vào trong D và ký hi u là Clip D(F) . Bài toán ñt ra là xác ñnh Clip D(F) . 3.2. XÉN ðON TH NG VÀO VÙNG HÌNH CH NHT C A R 2 3.2.1. C nh c a hình ch nh t song song v i các tr c t a ñ Lúc này:  X min ≤ x ≤ X max  D = (x, y) ∈ R2 |   Y min ≤ y ≤ Y max  và F là ñon th ng n i 2 ñim (x1,y1), (x2,y2) nên ph ươ ng trình c a F là: x= x1 +( x 2 − x 1 ). t  t ∈ [0,1] y= y1 +( y 2 − y 1 ). t Do ñó, F có th ñưc vit d ưi d ng: 2 F = {(x,y) ∈ R | x = x1 + (x2 -x1).t; y = y 1 + (y2 -y1).t; 0 ≤ t ≤ 1} Khi ñó, giao ñim c a F và D chính là A nghi m c a h b t ph ươ ng trình (theo t): y P yMax Xmin≤ x1+(x2-x1).t ≤ Xmax  Q  Ymin≤y 1+(y2-y1).t ≤ Y max yMin   0≤ t ≤ 1 B Gi N là t p nghi m c a h ph ươ ng trình xMin xMax X trên. Hình 3.1 Nu N = ∅ thì Clip D(F) = ∅ Nu N ≠ ∅ thì N = [t 1, t 2] (t 1 ≤ t 2) Gi P, Q là 2 giao ñim xác ñnh b i:
36. Ch ươ ng III . Xén hình Px= x1 +( x 2 − x 1 ). t 1 Qx= x1 +( x 2 − x 1 ). t 2   Py= y1 +( y 2 − y 1 ). t 1 Qy= y1 +( y 2 − y 1 ). t 2 thì: Clip D(F) = PQ (Hình 3.1) 3.2.1.1. Thu t toán Cohen - Sutherland • Chia m t ph ng ra làm 9 vùng, m i vùng ñánh m t mã nh phân 4 bit (hình 3.2). Bit 1: Qui ñnh vùng n m bên trái c a s 100 100 101 1 0 Bit 2: Qui ñnh vùng n m bên ph i c a s 0 000 000 001 Bit 3: Qui ñnh vùng n m bên d ưi c a s 1 0 0 Bit 4: Qui ñnh vùng n m bên trên c a s 010 010 011 1 0 0 2 • Xét ñim P ∈ R : Hình 3.2 1 nãúu P X max PRight =  x 0 Ngæåüc laûi 1 nãúu P 1 nãúu Py Y max PAbove =  0 Ngæåüc laûi • Xét ñon th ng AB, ta có các tr ưng h p sau: i/ Nu Mã(A) = Mã(B) = 0000 thì AB ∈ D ⇒ Clip D(F) = AB ii/ Nu Mã(A) AND Mã(B) ≠ 0000 thì ñon AB n m hoàn toàn bên ngoài hình ch nh t ⇒ Clip D(F) = ∅∅∅ Chú ý : Phép toán AND là phép toán Logic gi a các bit. iii/ Nu (Mã(A) AND Mã(B) = 0000) và (Mã(A) ≠ 0000 ho c Mã(B) ≠ 0000) thì: Gi s Mã(A) ≠ 0000 ⇔ A n m ngoài hình ch nh t. ♦ Nu Aleft = 1 : thay A b i ñim n m trên ñon AB và c t c nh trái (n i dài) ca hình ch nh t. 33
37. Ch ươ ng III . Xén hình ♦ Nu Aright = 1: thay A b i ñim n m trên ñon AB c t c nh ph i (n i dài) c a hình ch nh t. ♦ Nu ABelow = 1: thay A b i ñim n m trên ñon AB và c t c nh d ưi (n i dài) c a hình ch nh t. ♦ Nu AAbove = 1: thay A b i ñim n m trên ñon AB và c t c nh trên (n i dài) c a hình ch nh t. Chú ý : Quá trình này ñưc l p l i: Sau m i l n l p, ta ph i tính l i mã c a A. Nu c n, ph i ñi vai trò c a A và B ñ ñm b o A luôn luôn n m bên ngoài hình ch nh t. Quá trình s d ng khi x y ra m t trong 2 tr ưng h p: i/ ho c ii/ 3.2.1.2. Thu t toán chia nh phân • Ý t ưng c a thu t toán này t ươ ng t nh ư thu t toán tìm nghi m b ng ph ươ ng pháp chia nh phân. • Mnh ñ: Cho M: trung ñim c a ñon AB, Mã(A) ≠ 0000, Mã(B) ≠ 0000, Mã(M) ≠ 0000 thì ta có: [Mã(A) AND Mã(M)] ≠ 0000 ho c [Mã(M) AND Mã(B)] ≠ 0000. Ý ngh ĩa hình h c c a m nh ñ: Nu c ba ñim A, B, M ñu ngoài hình ch nh t thì có ít nh t m t ñon hoàn toàn n m ngoài hình ch nh t. • Ta phát th o thu t toán nh ư sau: i/ Nu Mã(A) = 0000 và Mã(B) = 0000 thì Clip D(F) = AB ii/ Nu Mã(A) AND Mã(B) ≠ 0000 thì Clip D(F) = ∅∅∅ iii/ Nu Mã(A) = 0000 và Mã(B) ≠ 0000 thì: P:=A; Q:=B; Trong khi |x P -xQ| + |y P - y Q| ≥ 2 thì: ♦ Ly trung ñim M c a PQ; ♦ Nu Mã(M) ≠ 0000 thì Q:= M. 34
38. Ch ươ ng III . Xén hình Ng ưc l i: P:= M. ⇒⇒⇒ Clip D(F) = AP iv/ Nu Mã(A) ≠ 0000 và Mã(B) = 0000 thì: ði vai trò c a A, B và áp d ng ii/ v/ Nu Mã(A) ≠ 0000 ≠ Mã(B) và [Mã(A) AND Mã(B)]= 0000 thì: P:=A; Q:=B; Ly M: trung ñim PQ; Trong khi Mã(M) ≠ 0000 và |x P - x Q| + |y P - y Q| ≥ 2 thì: ♦ Nu Mã(M) AND Mã(Q) ≠ 0000 thì Q:=M. Ng ưc l i P:=M. ♦ Ly M: trung ñim PQ. Nu Mã(M) ≠ 0000 thì Clip D(F) = ∅∅∅ . Ng ưc l i, áp d ng ii/ ta có: Clip D(MA) = MA 1 Clip D(MB) = MB 1 Suy ra: Clip D(F) = A 1B1 3.2.1.3. Thu t toán Liang - Barsky ðt ∆x = x2 - x1 ∆y = y2 - y1 p1 = - ∆x q1 = x1 - xMin p2 = ∆x q2 = xMax - x1 p3 = - ∆y q3 = y1 - yMin p4 = ∆y q4 = yMax - y1 thì h b t ph ươ ng trình giao ñim c a F và D có th vi t l i: P .t ≤ Q , k = 1 4  k k  0 ≤ t ≤1 Xét các trưng h p sau: i/ ∃k: Pk = 0 và Qk < 0: ( ðưng th ng song song v i các biên và n m ngoài vùng hình ch nh t ) 35
39. Ch ươ ng III . Xén hình ⇒ Clip D(F) = ∅∅∅ ii/ ∀k ∈ {1,2,3,4}: Pk ≠ 0 ho c Qk ≥ 0: ðt K1 = {k | Pk > 0 } K2 = {k | Pk u 2 thì Clip D(F) = ∅∅∅ Ng ưc l i: G i P, Q là 2 ñim th a Px = x1+ ∆x.u Qx = x1 + ∆x.u 1 và 2  = + ∆  = + ∆ Py y1 y.u1 Qy y1 y.u2 thì Clip D(F) = PQ 3.2.2. Khi c nh c a vùng hình ch nh t t o v i tr c hoành m t góc ααα∈α∈∈∈(0, ΠΠΠ/2) Ta dùng phép quay tr c t a ñ ñ ñư a bài toán v tr ưng h p các c nh c a hình ch nh t song song v i các tr c t a ñ (hình 3.3). y Gi R là ma tr n quay c a phép ñi tr c, ta có:  X min   X min    = R.   Y min  Y min  α  X max   X max    = R.   Y max  Y max  O x  cos(α ) sin( α ) vi R =   Hình 3.3 − sin(α ) cos( α ) 36
40. Ch ươ ng III . Xén hình 3.3. XÉN ðON TH NG VÀO HÌNH TRÒN Gi s ta có ñưng tròn tâm O(xc,yc) bán kính R và ñon th ng c n xén là AB v i A(x1,y1), B(x2,y2) (Hình 3.4). A * Thu t toán: B • Tính d(O,AB) • Xét các tr ưng h p: i/ Nu d > R thì Clip D(F) = ∅∅∅ Hình 3.4 ii/ Nu d = R thì Clip D(F) = A 0 v i A 0 là chân ñưng vuông góc h t O xu ng AB. iii/ Nu d R thì Clip D(F) = AI v i I là giao ñim duy nh t gi a AB và ñưng tròn. ♦ (OA > R) AND (OB > R) thì ClipD(F) = IJ v i I, J là hai giao ñim c a AB v i ñưng tròn. Sau ñây là ph ươ ng pháp tìm giao ñim gi a ñon th ng và ñưng tròn: ◊ Ph ương trình ñưng tròn: (x - xc) 2 + (y - yc) 2 = R 2 (1)  x = x1+ (x2 − x ).1 λ  ◊ Ph ươ ng trình ñon AB: y = y1+ (y2 − y ).1 λ (2)   0 ≤ λ ≤ 1 − a ± a2 − bc ◊ Thay (2) vào (1) ta suy ra: λ = b Trong ñó: a = ∆x.(x1 - x c) + ∆y.(y1 - yc) b = ( ∆x) 2 + ( ∆y) 2 2 2 2 c = (x1 - x c) + (y1 - yc) - R 37
41. Ch ươ ng III . Xén hình ∆x = x2 - x1 ∆y = y2 - y1 ◊ Da vào ñiu ki n 0 ≤ λ ≤ 1 ñ ch n giao ñim. 3.4. XÉN ðƯNG TRÒN VÀO HÌNH CH NH T CÓ CÁC C NH SONG SONG V I TR C T A ð Lúc này: D = {(x,y)| xMin ≤ x ≤ xMax ; yMin ≤ y ≤ yMax } 2 2 2 F = { (x,y)| (x - x C) + (y - y C) = R } Hình *Tr ưc h t, ta ki m tra các tr ưng h p ñc bi t sau: 3.5 i/ Nu xMin ≤ x C -R; x C +R ≤ xMax; yMin ≤ y C -R; y C +R ≤ yMax; thì Clip D(F) = F (Hình 3.5) ii/ Nu x C +R xMax ho c y C +R yMax C Hình 3.6 thì Clip D(F) = ∅∅∅ (Hình 3.6) *Xét tr ưng h p còn l i: Tìm các giao ñim c a F và D. S p x p các giao ñim ñó theo chi u ng ưc kim ñng h . • Các cung tròn ñưc t o b i 2 giao ñim liên ti p s hoàn toàn n m trong D ho c hoàn toàn n m bên ngoài D. • ð xác ñnh các cung này n m trong hay ngoài D, ta ch c n l y trung ñim M c a cung ñó. N u M ∈ D thì cung ñó n m trong D, ng ưc l i thì nó n m ngoài D. 38
42. Ch ươ ng III . Xén hình 3.5. XÉN ðA GIÁC VÀO HÌNH CH NH T Hình 3.7. Xén ña giác vào hình ch nh t Thu t toán SutherLand - Hodgman i/ Nu t t c các ñnh c a ña giác ñu n m trong hình ch nh t thì hình c n xén chính là ña giác và bài toán coi nh ư ñã ñưc gi i quy t. Ai Ai Ai + Ai + Ai + Ai + Ai + Ai Ai Ai Hình 3.8. Các tr ưng h p c n xét ii/ Tr ưng h p ng ưc l i: - Xu t phát t m t ñnh n m ngoài hình ch nh t, ta ch y theo d c biên c a ña giác. V i m i c nh c a ña giác, ta có các tr ưng h p sau:
    Nu c hai ñnh ñu n m ngoài hình ch nh t thì: Nu Ma(A i) and Ma(A i+1 ) ≠ 0000 thì không l ưu ñnh Ng ưc l i thì l ưu hai giao ñim.
    Ai ngoài, A i+1 trong: l ưu giao ñim P và A i+1 .
    C hai ñnh ñu n m trong hình ch nh t: l ưu A i và A i+1 .
    Ai trong, A i+1 ngoài: l ưu A i và giao ñim P. 39
43. Ch ươ ng III . Xén hình - Sau khi duy t qua t t c các c nh c a ña giác thì ta có ñưc m t dãy các ñnh m i phát sinh: B 1, B 2, , B n Nu trong dãy các ñnh m i này có hai ñnh liên ti p không n m trên cùng m t cnh c a hình ch nh t , gi s hai ñnh ñó là B i và B i+1 thì ta ñi d c các c nh c a hình ch nh t t B i ñn B i+1 ñ tìm t t c các ñnh c a hình ch nh t n m trong ña giác r i b sung chúng vào gi a B i và B j. Tp ñnh m i tìm ñưc chính là ña giác xén ñưc. - N u t p ñnh m i này là r ng: N u có m t ñnh c a hình ch nh t n m trong ña giác thì hình xén ñưc chính là toàn b hình ch nh t. Ng ưc l i, hình xén ñưc là rng. BÀI T P 1. Vi t hàm MA(P:ToaDo):Byte; ñ ñánh mã cho ñim P. 2. Cài ñt thu t toán xén m t ñon th ng vào m t hình ch nh t theo các thu t toán: Liang-Barsky, Cohen-Sutherland, chia nh phân. 3. Cài ñt thu t toán xén m t ñon th ng vào m t hình tròn. 4.Cài ñt thu t toán xén m t ña giác vào m t vùng hình ch nh t. 40
44. CH ƯƠ NG IV CÁC PHÉP BI N ðI 4.1. CÁC PHÉP BI N ðI TRONG M T PH NG 4.1.1. C ơ s toán h c Phép bi n ñi Affine 2D s bi n ñim P(x,y) thành ñim Q(x’,y’) theo h ph ươ ng trình sau: x’ = Ax + Cy + trx y’ = Bx + Dy + try Dưi d ng ma tr n, h này có d ng:  A B  (x’ y’) = (x y).   + (trx try) C D Hay vi t g n h ơn: X’ = X.M + tr vi X’=(x’,y’); X=(x,y); tr=(trx,try) - vector t nh ti n;  A B  M =   - ma tr n bi n ñi. C D 4.1.1.1. Phép ñng d ng Ma tr n c a phép ñng d ng là:  A 0 x' = Ax M =   ⇔   0 D y' = Dy Cho phép ta phóng to hay thu nh hình theo m t hay hai chi u. 4.1.1.2. Phép ñi x ng ðây là tr ưng h p ñc bi t c a phép ñng d ng v i A và D ñi nhau. −1 0   ñi x ng qua Oy  0 1
45. Ch ươ ng IV. Các phép bi n ñi 1 0    ñi x ng qua Ox 0− 1 −1 0    ñi x ng qua g c t a ñ  0− 1 4.1.1.3. Phép quay  Cos (α) Sin (α)  Ma tr n t ng quát c a phép quay là R =   − Sin (α) Cos (α) Chú ý : • Tâm c a phép quay ñưc xét ñây là g c t a ñ. • ðnh thc c a ma tr n phép quay luôn luôn b ng 1. 4.1.1.4. Phép t nh ti n Bi n ñi (x,y) thành (x’,y’) theo công th c sau x’ = x + M y’ = y + N ð thu n ti n bi u di n d ưi d ng ma tr n, ta có th bi u di n các t a ñ d ưi d ng ta ñ thu n nh t (Homogen):  1 0 0   (x y 1).  0 1 0 = (x + M y + N 1)    MN 1 4.1.1.5. Phép bi n d ng Ma tr n t ng quát là: M = 1 g    h 1 Trong ñó:   g = 0: bi n d ng theo tr c x. h = 0: bi n d ng theo tr c y. 4.1.1.6. H p c a các phép bi n ñi Có ma tr n bi n ñi là tích c a các ma tr n c a các phép bi n ñi. .42
46. Ch ươ ng IV. Các phép bi n ñi Ví d : Phép quay quanh m t ñim b t k ỳ trong m t ph ng có th th c hi n b i tích ca các phép bi n ñi sau: ° Phép t nh ti n tâm quay ñn g c t a ñ. ° Phép quay v i góc ñã cho. ° Phép t nh ti n k t qu v tâm quay ban ñu. Nh ư v y, ma tr n c a phép quay quanh m t ñim b t k ỳ ñưc th c hi n b i tích ca ba phép bi n ñi sau:  1 0 0  Cos()()α Sin α 0  1 0 0        0 1 0 . −Sin()()α Cos α 0 .  0 1 0       −MN − 1  0 0 1  MN 1 4.2. Ví d minh h a Vi t ch ươ ng trình mô ph ng phép quay m t tam giác quanh g c t a ñ. Uses crt,Graph; Type ToaDo=Record x,y:real; End; var k,Alpha,goc:real; P,PP,PPP,P1,P2,P3:ToaDo; x0,y0:word; ch:char; Procedure VeTruc; Begin Line(GetMaxX div 2,0,GetMaxX div 2,GetMaxY); Line(0,GetMaxY div 2,GetMaxX,GetMaxY div 2); End; Procedure VeHinh(P1,P2,P3:ToaDo); Begin Line(x0+Round(P1.x*k),y0-Round(P1.y*k), x0+Round(P2.x*k),y0- Round(P2.y*k)); Line(x0+Round(P2.x*k),y0-Round(P2.y*k), .43
47. Ch ươ ng IV. Các phép bi n ñi x0+Round(P3.x*k),y0- Round(P3.y*k)); Line(x0+Round(P3.x*k),y0-Round(P3.y*k), x0+Round(P1.x*k),y0- Round(P1.y*k)); End; Procedure QuayDiem(P:ToaDo;Alpha:real; var PMoi:ToaDo); Begin PMoi.x:=P.x*cos(Alpha)-P.y*sin(Alpha); PMoi.y:=P.x*sin(Alpha)+P.y*cos(Alpha); End; Procedure QuayHinh(P1,P2,P3:ToaDo;Alpha:real; var P1Moi,P2Moi,P3Moi:ToaDo); Begin QuayDiem(P1,Alpha,P1Moi); QuayDiem(P2,Alpha,P2Moi); QuayDiem(P3,Alpha,P3Moi); End; BEGIN ThietLapDoHoa; x0:=GetMaxX div 2; y0:=GetMaxY div 2; k:=GetMaxX/50; Vetruc; P.x:=5; P.y:=3; PP.x:=2; PP.y:=6; PPP.x:=6; PPP.y:=-4; P1.x:=5; P1.y:=3; P2.x:=2; P2.y:=6; P3.x:=6; P3.y:=-4; Alpha:=0; goc:=Pi/180; SetWriteMode(XORPut); VeHinh(P,PP,PPP); Repeat ch:=readkey; if ord(ch)=0 then ch:=readkey; case Upcase(ch) of #75: Begin .44
48. Ch ươ ng IV. Các phép bi n ñi VeHinh(P1,P2,P3); Alpha:=Alpha-goc; QuayHinh(P,PP,PPP,Alpha,P1,P2,P3); VeHinh(P1,P2,P3); End; #77: Begin VeHinh(P1,P2,P3); Alpha:=Alpha+goc; QuayHinh(P,PP,PPP,Alpha,P1,P2,P3); VeHinh(P1,P2,P3); End; End; Until ch=#27; CloseGraph; END. 4.2. CÁC PHÉP BI N ðI TRONG KHÔNG GIAN 4.2.1. Các h tr c t a ñ ð ñnh v m t ñim trong không gian, ta có th ch n nhi u h tr c t a ñ: Z Z Y Y O X H tr c ti p H gián ti p Hình 4.1 • H t a ñ tr c ti p : n u tay ph i c m tr c Z sao cho ngón cái h ưng theo chi u d ươ ng c a tr c Z thì b n ngón còn l i s quay t tr c X sang tr c Y (Qui t c bàn tay ph i). .45
49. Ch ươ ng IV. Các phép bi n ñi • H t a ñ gián ti p : ng ưc l i (Qui t c bàn tay trái). Thông th ưng, ta luôn luôn ñnh v m t ñim trong không gian qua h tr c ti p. Trong h t a ñ tr c ti p, ta chia ra làm 2 lo i sau: Z Z P(x,y,z) P(R, θ,φ ) R Y φ Y O O θ X X H t a ñ Descarter H c u Hình 4.2 Ta có công th c chuy n ñi t a ñ t h này sang h khác: x = R.Cos( θθθ).Cos( ΦΦΦ) y = R.Sin( θθθ).Cos( ΦΦΦ) z = R.Sin( ΦΦΦ) R2 = x 2 + y 2 + z 2 ð thu n ti n cho vi c tính toán, t t c các ñim trong không gian ñu ñưc mô t dưi d ng ma tr n 1x4, t c là (x,y,z,1). Vì v y, t t c các phép bi n ñi trong không gian ñu ñưc bi u di n b i các ma tr n vuông 4x4 (Ma tr n Homogen). 4.2.2. Các công th c bi n ñi Phép bi n ñi Affine 3D có d ng: X’=X.M + tr vi X’=(x’,y’,z’); X=(x,y,z); M - ma tr n bi n ñi; tr=(trx,try,trz) - vector tnh ti n 4.2.2.1. Phép thay ñi t l  A 0 0 0   x'.= A x 0B 0 0    ⇔ = M =   y'. B y 0 0C 0    z'.= C z  0 0 0 1 .46
50. Ch ươ ng IV. Các phép bi n ñi 4.2.2.2. Phép ñi x ng 1 0 0 0   0 1 0 0 Mz =   ñi x ng qua m t (XY) 0 0− 1 0   0 0 0 1 1 0 0 0   0− 1 0 0 My=   ñi x ng qua m t (XZ) 0 0 1 0   0 0 0 1 −1 0 0 0   0 1 0 0 Mx =   ñi x ng qua m t (YZ)  0 0 1 0    0 0 0 1 4.2.2.3. Phép t nh ti n  1 0 0 0   x'= x + M 0 1 0 0    ⇔ = + M =   y' y N 0 0 1 0     z'= z + P  MNP 1 4.2.2.4. Phép quay Ta nh n th y r ng, n u phép quay quay quanh m t tr c nào ñó thì t a ñ c a v t th t i tr c ñó s không thay ñi. Do ñó, ta có ma tr n c a các phép quay nh ư sau:  Cos (θ ) Sin (θ ) 0 0   − Sin (θ ) Cos (θ ) 0 0 RZ =    0 0 1 0    0 0 0 1 1 0 0 0   0 Cos (θ ) Sin (θ ) 0 RX =  − θ θ  0 Sin ( ) Cos ( ) 0   0 0 0 1 .47
51. Ch ươ ng IV. Các phép bi n ñi  Cos (θ ) 0 Sin (θ ) 0    0 1 0 0 RY = − θ θ   Sin ( ) 0 Cos ( ) 0    0 0 0 1 Chú ý : Tích c a 2 ma tr n nói chung không giao hoán nên k t qu c a 2 phép quay liên ti p tùy thu c vào th t th c hi n tích s . Ví d : R X.R Y ≠ R Y.R X 4.2.3. Ma tr n ngh ch ño ðnh ngh ĩa: Hai ma tr n ñưc g i là ngh ch ño c a nhau n u tích s c a chúng là ma tr n ñơ n v . Ma tr n ngh ch ño c a ma tr n M ký hi u là M -1 Ví d : 1 2 3  6− 2 − 3 1 0 0       1 3 3 . −1 1 0  = 0 1 0       1 2 4 −1 0 1  0 0 1 Ng ưi ta ch ng minh ñưc r ng: T t c các ma tr n c a các phép bi n ñi ñã nêu trên ñu có ma tr n ngh ch ño. • Ma tr n ngh ch ño c a phép t nh ti n có ñưc b ng cách thay M, N, P b ng - M, -N, -P. • Ma tr n ngh ch ño c a phép thay ñi t l có ñưc b ng cách thay A, B, C b ng 1/A, 1/B, 1/C. • Ma tr n ngh ch ño c a phép quay có ñưc b ng cách thay góc θθθ b ng -θθθ . 4.3. CÁC PHÉP CHI U C A V T TH TRONG KHÔNG GIAN LÊN M T PH NG 4.3. 1. Phép chi u ph i c nh (Perspective) Phép chi u này cho hình nh gi ng nh ư khi nhìn v t th . ð tìm hình chi u P’(y’,z’) c a P(x,y,z), ta n i P v i m t (tâm chi u). Giao ñim ca ñưng này v i m t quan sát chính là P’ (hình 4.3). Gi s P n m phía tr ưc m t, t c là P.x < E. .48
52. Ch ươ ng IV. Các phép bi n ñi Z P(x,y,z) z ' P ' y ' (E,0,0) Maét X Y Maët phaúng chieáu Hình 4.3 Ph ươ ng trình c a tia ñi qua m t và P là: r(t) = (E,0,0).(1-t) + (x,y,z).t (*) Giao ñim v i m t ph ng quan sát có thành ph n x’ = 0. 1 Do thành ph n x’ c a tia r là E.(1-t) + x.t = 0 nên t = . Thay t vào (*) ta 1− x / E tính ñưc: y z y’ = va z’ = 1− x / E 1− x / E NH N XÉT i/ Phép chi u ph i c nh không gi nguyên hình d ng c a v t th . ii/ Ch có nh ng ñưng th ng song song v i m t ph ng chi u thì m i song song vi nhau. iii/ Phép chi u ph i c nh ñưc qui ñnh b i 5 bi n: • Hưng c a m t ph ng chi u so v i v t th . • ð cao c a tâm chi u so v i v t th . • Kho ng cách t tâm chi u ñn v t th (R). • Kho ng cách t m t ph ng chi u ñn tâm chi u (D). • ð d ch chuy n ngang c a tâm chi u so v i v t th . Chú ý : V i t a ñ c u, ta ch c n 4 tham s : R, ΦΦΦ, θθθ, D. .49
53. Ch ươ ng IV. Các phép bi n ñi 4.3. 2. Phép chi u song song (Parallel) Phép chi u này có tâm chi u vô c c và y’=y, z’=z.(Hình 4.4) Tính song song ñưc b o toàn. A A' Taâm chieáu ( ∝) B' B Maët phaúng chieáu Hình 4.4 4.4 . CÔNG TH C C A CÁC PHÉP CHI U LÊN MÀN HÌNH Khi quan sát m t v t th trong không gian d ưi m t góc ñ nào ñó, ta có 2 kh năng ch n l a: • ðim nhìn (màn hình) ñng yên và v t th di ñng. • Vt th ñng yên và ñim nhìn s ñưc b trí thích h p. Ta th ưng ch n gi i pháp th hai vì nó sát v i th c t h ơn. Y0 X0 Z Z0 O' YE XE φ Y O θ X Maøn hình Hình 4.5 Khi quan sát m t v t th b t k ỳ trong không gian, ta ph i tuân th các nguyên t c sau (hình 4.5): • Vt th ph i ñưc chi u lên m t h tr c ti p (O,X,Y,Z). .50
54. Ch ươ ng IV. Các phép bi n ñi • Con m t ph i n m g c c a m t h gián ti p th hai (O’,X 0,Y 0,Z 0) • Màn hình là m t ph ng vuông góc v i ñưng th ng OO’. • Tr c Z 0 c a h quan sát ch ñn g c O. Nu dùng h t a ñ c u ñ ñnh v m t c a ng ưi quan sát thì ta d dàng thay ñi góc ng m b ng cách thay ñi góc θθθ và ΦΦΦ. Bây gi , ta kh o sát phép bi n ñi mà v t th (X,Y,Z) ph i ch u ñ cho nó trùng vi h quan sát (X 0,Y 0,Z 0) ñ cu i cùng t o ra h t a ñ màn hình (Xe,Ye). Bưc 1 : T nh ti n g c O thành O’ (hình 4.6). Z1 Z Y1 O' φ Y O θ X1 X Hình 4.6 Ma tr n c a phép t nh ti n (L y ngh ch ño):  1 0 0 0  1 0 0 0     0 1 0 0 0 1 0 0 A=   =    0 0 1 0  0 0 1 0     −MNP − − 1 −RCos. ().θ Cos () φ − RSin . (). θ Cos () φ − RSin . () φ 1 và h (X,Y,Z) bi n ñi thành h (X1,Y1,Z1). 0 Bưc 2: Quay h (X1,Y1,Z1) m t góc -θθθ‘ ( θθθ‘=90 - θθθ) quanh tr c Z1 theo chi u kim ñng h . Phép quay này làm cho tr c âm c a Y1 c t tr c Z (hình 4.7). Ta g i Rz là ma tr n t ng quát c a phép quay quanh tr c Z. Vì ñây là phép quay h -1 tr c nên phi dùng ma tr n ngh ch ño R z. .51
55. Ch ươ ng IV. Các phép bi n ñi  Cos()() a Sin a 0 0 Cos()() a− Sin a 0 0     −  Sin()() a Cos a 0 0 -1  Sin()() a Cos a 0 0 Rz = R =  0 0 1 0 z  0 0 1 0      0 0 0 1  0 0 0 1 ta thay góc a = -θθθ‘ . Theo các phép toán l ưng giác: Sin(-θθθ') = -Sin( θθθ') = -Sin(90 0 - θθθ) = -Cos( θθθ) Cos(-θθθ') = Cos( θθθ') = Cos(90 0-θθθ) = Sin( θθθ) Z Z2 O' Y2 φ Y O θ' θ X2 X Hình 4.7 Nên ma tr n c a phép quay tìm ñưc s có d ng:  Sin()()θ Cos θ 0 0   −Cos()()θ Sin θ 0 0 B =   và h (X1,Y1,Z1) bi n ñi thành h (X2,Y2,Z2).  0 0 1 0    0 0 0 1 0 Bưc 3: Quay h (X2,Y2,Z2) m t góc 90 + ΦΦΦ quanh tr c X2. Phép bi n ñi này s làm cho tr c Z2 h ưng ñn g c O (hình 4.8). Ta có: 1 0 0 0   0 Cos (a) Sin (a) 0 Rx =  −  0 Sin (a) Cos (a) 0   0 0 0 1 .52
56. Ch ươ ng IV. Các phép bi n ñi Z Y3 O' Z3 Y φ X3 O θ' θ X Hình 4.8 1 0 0 0   0Cos()() a− Sin a 0 R-1 =   x 0Sin()() a Cos a 0   0 0 0 1 Thay góc a = 90 0 + ΦΦΦ , ta có: Cos(90 0 + ΦΦΦ) = -Sin( ΦΦΦ) và Sin(90 0 + ΦΦΦ) = Cos( ΦΦΦ) nên ma tr n tìm ñưc s có d ng: 1 0 0 0   0−Sin()()φ − Cos φ 0 C =   0Cos()()φ− Sin φ 0   0 0 0 1 Lúc này, h (X2,Y2,Z2) bi n ñi thành h (X3,Y2,Z3). Bưc 4: Bi n ñi h tr c ti p (X3,Y3,Z3) thành h gián ti p (hình 4.9). Trong b ưc này, ta ph i ñi h ưng tr c X3 b ng cách ñi d u các ph n t c a ct X. Ta nh n ñưc ma tr n: −1 0 0 0   0 1 0 0 D =    0 0 1 0    0 0 0 1 và h (X3,Y3,Z3) bi n ñi thành h (X 0,Y 0,Z 0). .53
57. Ch ươ ng IV. Các phép bi n ñi Z Y0 X0 Z0 O' φ Y O θ' θ X Hình 4.9 TÓM L I Các ñim trong không gian s nh n trong h quan sát m t t a ñ có d ng: (x 0 ,y 0 ,z 0 ,1) = (x y z 1).A.B.C.D Gi T = A.B.C.D, ta tính ñưc: −sin()θ −Cos (). θ Sin () φ − Cos (). θ Cos () φ 0   Cos()θ− Sin (). θ Sin () φ − Sin (). θ Cos () φ 0 T =    0 Cos()()φ− Sin φ 0    0 0R 1 Cu i cùng ta có: (x 0 ,y 0 ,z 0 ,1) = (x y z 1).T hay: x0 = -x.Sin( θθθ) + y.Cos( θθθ) y0 = -x.Cos( θθθ).Sin( ΦΦΦ) - y.Sin( θθθ).Sin( ΦΦΦ) + z.Cos( ΦΦΦ) z0 = -x.Cos( θθθ).Cos( ΦΦΦ) - y.Sin( θθθ).Cos( ΦΦΦ) - z.Sin( ΦΦΦ) + R * Bây gi ờ ta chi ếu ảnh c ủa h ệ quan sát lên màn hình. 1. Phép chi u ph i c nh Cho ñim P(x,y,z) và hình chi u P’(x0,y0,z0) c a nó trên m t ph ng. Gi D là kho ng cánh t m t ph ng ñn m t (g c t a ñ). (Hình 4.10) .54
58. Ch ươ ng IV. Các phép bi n ñi Y0 P(x0,y0,z0) P'(xE,yE,zE) Z0 O X0 Maøn hình Y0 P(x0,y0,z0) yE O D Maøn hình Z0 O xE P(x0,y0,z0) X0 Hình 4.10 Xét các tam giác ñng d ng, ta có: xE/D = x 0/z 0 và yE/D = y 0/z 0 ⇒ xE = D.x 0/z 0 và yE = D.y 0/z 0 Chú ý : z 0 bao hàm vi c phóng to hay thu nh v t th . 2. Phép chi u song song Ta ñ quan sát (x 0,y 0,z 0) và t a ñ màn hình th a mãn công th c: xE = x 0 và yE = y 0 .55
59. Ch ươ ng IV. Các phép bi n ñi Phoùng to Thu nhoû Maét Vaät theå Maøn hình Maøn hình Hình 4.11 KT LU N Có 4 giá tr nh h ưng ñn phép chi u v t th 3D là: các góc θθθ , ΦΦΦ , kho ng cách R t O ñn O’ và kho ng cách D t O’ ñn m t ph ng quan sát. C th : • Tăng gi m θθθ s quay v t th trong m t ph ng (XY). • Tăng gi m ΦΦΦ s quay v t th lên xu ng. • Tăng gi m R ñ quan sát v t t xa hay g n. • Tăng gi m D ñ phóng to hay thu nh nh. 4.5. PH L C To UNIT DOHOA3D (DOHOA3D.PAS). UNIT DOHOA3D; INTERFACE USES graph,crt; { Cac hang de quay hinh } Const IncAng = 5; {Tang goc} Type ToaDo3D=Record x,y,z:real; End; ToaDo2D=Record x,y:integer; End; .56
60. Ch ươ ng IV. Các phép bi n ñi PhepChieu = (PhoiCanh,SongSong); VAR R,d,theta,phi : real; aux1,aux2,aux3,aux4 : real; aux5,aux6,aux7,aux8 : real; projection : PhepChieu; xproj,yproj : real; Obs,O : ToaDo3D; PE,PC : ToaDo2D; { cac bien dung quay hinh } ch : char; PROCEDURE ThietLapDoHoa; PROCEDURE KhoiTaoPhepChieu; PROCEDURE Chieu(P :ToaDo3D); PROCEDURE VeDen(P :ToaDo3D); PROCEDURE DiDen(P :ToaDo3D); PROCEDURE TrucToaDo; PROCEDURE DieuKhienQuay; {dung de quay hinh} IMPLEMENTATION Procedure ThietLapDoHoa; var gd,gm:integer; Begin Gd:=0; InitGraph(gd,gm,'C:\BP\BGI'); End; PROCEDURE KhoiTaoPhepChieu; VAR th,ph :real; BEGIN th := pi*theta/180; ph := pi*phi/180; aux1 := sin(th); aux2 := sin(ph); aux3 := cos(th); .57
61. Ch ươ ng IV. Các phép bi n ñi aux4 := cos(ph); aux5 := aux3*aux2; aux6 := aux1*aux2; aux7 := aux3*aux4; aux8 := aux1*aux4; PC.x := getmaxx div 2; PC.y := getmaxy div 2; END; PROCEDURE Chieu(P :ToaDo3D); BEGIN Obs.x := -P.x*aux1 + P.y*aux3 ; Obs.y := -P.x*aux5 - P.y*aux6 + P.z*aux4 ; IF projection = PhoiCanh THEN BEGIN obs.z:=-P.x*aux7 -P.y*aux8 -P.z*aux2 + R; Xproj := d*obs.x/obs.z; Yproj := d*obs.y/obs.z; END ELSE BEGIN Xproj := d*obs.x; Yproj := d*obs.y; END; END; PROCEDURE VeDen(P :ToaDo3D); BEGIN Chieu(P); PE.x := PC.x + round(xproj); PE.y := PC.y - round(yproj); lineto (PE.x,PE.y); END; PROCEDURE Diden(P :ToaDo3D); BEGIN .58
62. Ch ươ ng IV. Các phép bi n ñi Chieu(P); PE.x := PC.x + round(xproj); PE.y := PC.y - round(yproj); moveto (PE.x,PE.y); END; PROCEDURE TrucToaDo; { Ve 3 truc } var OO,XX,YY,ZZ:ToaDo3D; Begin OO.x:=0; OO.y:=0; OO.z:=0; XX.x:=3; XX.y:=0; XX.z:=0; YY.x:=0; YY.y:=3; YY.z:=0; ZZ.x:=0; ZZ.y:=0; ZZ.z:=3; DiDen(OO); VeDen(XX); DiDen(OO); VeDen(YY); DiDen(OO); VeDen(ZZ); END; PROCEDURE DieuKhienQuay; {Dieu khien Quay/Zoom hinh} BEGIN ch := readkey; IF ch = #0 THEN ch := readkey; cleardevice; CASE UpCase(ch) OF #72 : phi := phi + incang; #80 : phi := phi - incang; #75 : theta := theta + incang; #77 : theta := theta - incang; END; {of case ch} END; {of Procedure} END. {Of UNIT} 4.6. VÍ D MINH H A Vi t ch ươ ng trình mô t phép quay c a m t hình l p ph ươ ng quanh các tr c (hình 4.12). .59
63. Ch ươ ng IV. Các phép bi n ñi Z P6 P7 P5 P8 Y P1 P2 P4 P3 X Hình 4.12 Uses crt,graph,Dohoa3D; var P1,P2,P3,P4,P5,P6,P7,P8:ToaDo3D; Procedure KhoiTaoBien; Begin D:=70; R:=5; Theta:=40; Phi:=20; P1.x:=0; P1.y:=0; P1.z:=0; P2.x:=0; P2.y:=1; P2.z:=0; P3.x:=1; P3.y:=1; P3.z:=0; P4.x:=1; P4.y:=0; P4.z:=0; P5.x:=1; P5.y:=0; P5.z:=1; P6.x:=0; P6.y:=0; P6.z:=1; P7.x:=0; P7.y:=1; P7.z:=1; P8.x:=1; P8.y:=1; P8.z:=1; End; Procedure VeLapPhuong; begin Diden(P1); VeDen(P2); VeDen(P3); VeDen(P4); VeDen(P1); VeDen(P6); Veden(P7); VeDen(P8); VeDen(P5); VeDen(P6); DiDen(P3); VeDen(P8); .60
64. Ch ươ ng IV. Các phép bi n ñi DiDen(P2); VeDen(P7); DiDen(P4); VeDen(P5); end; Procedure MinhHoa; BEGIN KhoiTaoBien; KhoiTaoPhepChieu; TrucToaDo; VeLapPhuong; Repeat DieuKhienQuay; KhoiTaoPhepChieu; ClearDevice; TrucToado; VeLapPhuong; until ch=#27; END; BEGIN { Chuong Trinh Chinh } Projection:=SongSong{Phoicanh}; ThietLapDoHoa; MinhHoa; CloseGraph; END. BÀI TP 1. Cho 3 tam giác sau: ABC v i A(1,1) B(3,1) C(1,4) EFG v i E(4,1) F(6,1) G(4,4) MNP v i M(10,1) N(10,3) P(7,1) a. Tìm ma tr n bi n ñi tam giác ABC thành tam giác EFG. b. Tìm ma tr n bi n ñi tam giác ABC thành tam giác MNP. 2. Cài ñt thu t toán xén m t ñon th ng vào m t hình ch nh t có c nh không song song v i tr c t a ñ. .61
65. Ch ươ ng IV. Các phép bi n ñi 3. Vi t ch ươ ng trình v m t Ellipse có các tr c không song song v i h tr c t a ñ. 4. D a vào bài t p 2, hãy mô ph ng quá trình quay c a m t Ellipse xung quanh tâm ca nó. 5. Vi t ch ươ ng trình mô ph ng quá trình quay, ñi x ng, t nh ti n, phóng to, thu nh , bi n d ng c a m t hình b t k ỳ trong m t ph ng. 6. Mô ph ng chuy n ñng c a trái ñt xung quanh m t tr i ñng th i mô t chuy n ñng c a m t tr ăng xung quanh trái ñt. M r ng trong không gian 3 chi u. 7. Vi t ch ươ ng trình v ñng h ñang ho t ñng. 8. Vi t ch ươ ng trình v các kh i ña di n ñu trong không gian. M r ng : ñiu khi n phóng to, thu nh , quay các kh i ña di n quanh các tr c .62
66. CH ƯƠ NG V BI U DI N CÁC ðI T ƯNG BA CHI U 5.1. MÔ HÌNH WIREFRAME Mô hình WireFrame th hi n hình dáng c a ñi t ưng 3D b ng 2 danh sách : • Danh sách các ñnh : l ưu t a ñ c a các ñnh. • Danh sách các c nh : l ưu các c p ñim ñu và cu i c a t ng c nh. Các d nh và các c nh ñưc ñánh s th t cho thích h p. Ví d : Bi u di n 1 c ăn nhà thô s ơ (hình 5.1) ñ Danh sách các nh Z Vector x y z P4 1 0 0 0 2 0 1 0 P9 P5 3 0 1 1 P3 4 0 0.5 1.5 P10 5 0 0 1 P8 6 1 0 0 Y P1 7 1 1 0 P2 8 1 1 1 P6 9 1 0.5 1.5 P7 10 1 0 1 X Có nhi u cách ñ l ưu gi mô hình Hình 5.1 WireFrame. ñây, chúng ta dùng c u trúc record d a trên 2 m ng: Const MaxDinh = 50; { S ñnh t i ña} MaxCanh = 100; {S c nh t i ña} Type ToaDo3D = record x, y, z:real; end; WireFrame = Record
67. Ch ươ ng V. Bi u di n các ñi t ưng ba chi u Sodinh: 0 MaxDinh; Dinh: array [1 MaxDinh] of ToaDo3D; Socanh : 0 Maxcanh; Canh :array[1 Maxcanh, 1 2] of 1 MaxDinh; end; Khi ñó, ta dùng m t bi n ñ mô t c ăn nhà : Var House : WireFrame; vi bi n house trên, ta có th gán giá tr nh ư Danh sách các c nh sau: Cnh ðnh ñu ðnh cu i With House Do 1 1 2 Begin 2 2 3 sodinh:=10; 3 3 4 socanh:=17; 4 4 5 dinh[1].x:=0; 5 5 1 dinh[1].y:=0; 6 6 7 dinh[1].z:=0; 7 7 8 8 8 9 canh[1, 1]:=1; {S ñnh th nh t c a 9 9 10 cnh s 1} 10 10 6 canh[1, 2]:=2; {S ñnh th hai c a 11 1 6 cnh s 1} 12 2 7 13 3 8 end; 14 4 9 5.2. V MÔ HÌNH WIREFRAME V I CÁC 15 5 10 PHÉP CHI U 16 2 5 17 1 3 ð v m t ñi t ưng WireFrame, ta v t ng cnh trong danh sách các c nh c a mô hình. V n ñ là làm th nào ñ v 1 ñưng th ng trong không gian 3 chi u vào m t ph ng? ð làm ñiu này, ta ph i b b t ñi 1 chi u trong mô hình bi u di n, t c là ta ph i dùng phép chi u t 3D → 2D . 64
68. Ch ươ ng V. Bi u di n các ñi t ưng ba chi u K thu t chung ñ v m t ñưng th ng 3D là:
    Chi u 2 ñim ñu mút thành các ñim 2D.
    V ñưng th ng ñi qua 2 ñim v a ñưc chi u. Sau ñây là th t c xác ñnh hình chi u c a m t ñim qua phép chi u ph i c nh: Procedure Chieu(P3D:ToaDo3D; E:Real; Var P2D:ToaDo2D); Var t:Real; Begin If (P3D.x >=E) OR (E=0) Then Writeln(‘ ðim n m sau m t ho c m t n m trên m t ph ng nhìn’); Esle Begin t := 1/(1 - P3D.x/E); P2D.y := t*P3D.y; P2D.z := t*P3D.z; End; End; 5.3. V CÁC M T TOÁN H C Ta s v các m t cong d a trên phươ ng trình tham s c a các m t ñó. Ví d : (a) (b) (c) Hình 5.2 • Mt Ellipsoid: (hình 5.2.a) x=Rx.cos(u).cos(v) y=Ry.sin(u).cos(v) 65
69. Ch ươ ng V. Bi u di n các ñi t ưng ba chi u z=Rz.sin(v) Trong ñó: 0 ≤ u ≤ 2 π -π/2 ≤ v ≤ π/2 • Mt Hypeboloid: (hình 5.2.b) x=u y=v z=u 2 - v 2 Trong ñó u,v ∈[-1,1] • Hình xuy n: (hình 5.2.c) x=(R + a.cos(v)).cos(u) y=(R + a.cos(v)).sin(u) z= a.sin(v) Trong ñó: 0 ≤ u ≤ 2 π -π/2 ≤ v ≤ π/2 • Hình tr tròn (Cylinder) x = R.cos(u) y = R.sin(u) z = h • Hình nón (Cone) p(u,v) = (1-v).P 0 + v.P 1(u) trong ñó: P0: ñnh nón x = R.cos(u) P1(u): ñưng tròn  u,v ∈ [0,1]  y = R.sin( u) • Ch o Parabol (Paraboloid) x = a.v.cos(u) y = b.v.sin(u) u∈[-π,π], v ≥ 0 z = v 2 Ph ươ ng pháp chính ñây c ũng là v các ñưng vi n theo u và v. 66
70. Ch ươ ng V. Bi u di n các ñi t ưng ba chi u ð v m t ñưng vin u t i giá tr u’ khi v ch y t VMin ñn VMax ta làm nh ư sau: • To m t t p h p các giá tr v[i] ∈ [VMin ,VMax], xác ñnh v trí P[i] = (X(u’,v[i]), Y(u’,v[i]), Z(u’,v[i])). • Chi u t ng ñim P[i] lên m t ph ng. • V các ñưng g p khúc d a trên các ñim 2D P’[i]. Sau ñây là th t c v h ñưng cong theo u: Procedure HoDuongCongU; Var P: ToaDo3D; u,v,du,dv:Real; Begin u:=UMin; du:=0.05; dv:=0.05; While u<=UMax do Begin v:=Vmin; P.x:=fx(u,v); P.y:=fy(u,v); P.z:=fz(u,v); DiDen(P); { ði ñn ñim xu t phát ban ñu } While v<=VMax do Begin v:=v+dv; P.x:=fx(u,v); P.y:=fy(u,v); P.z:=fz(u,v); VeDen(P); { V ñn ñim m i } End; u:=u + du; End; End; Tươ ng t , ta có th v h ñưng cong theo v. 67
71. Ch ươ ng V. Bi u di n các ñi t ưng ba chi u TÓM L I: Mu n v m t m t cong, ta th c hi n các b ưc sau • Nh p các h s c a ph ươ ng trình m t: a, b, c, d, Umin, Umax, Vmin, Vmax. • Tính các hàm 2 bi n: X(u,v), Y(u,v), Z(u,v). • Kh i t o phép chi u: Song song/Ph i c nh. • V h ñưng cong u. V h ñưng cong v. BÀI T P 1. Hãy xây d ng m t c u trúc d li u ñ l ưu tr mô hình WireFrame. 2. T o file text ñ l ưu các ñnh và c nh c a m t v t th trong không gian 3D theo mô hình WireFrame v i c u trúc nh ư sau:
    Dòng ñu tiên ch a hai s nguyên m, n dùng ñ l ưu s ñnh và s c nh c a mô hình.
    m dòng ti p theo, m i dòng l ưu t a ñ x, y, z c a t ng ñnh trong mô hình.
    n dòng ti p theo, m i dòng l ưu hai s nguyên là ñnh ñu và ñnh cu i c a t ng cnh trong mô hình. 3. Vi t th t c ñ ñc các giá tr trong file text l ưu vào mô hình WireFrame. 4. Vi t th t c ñ v v t th t mô hình WireFrame. 5. Vi t ch ươ ng trình bi u di n các kh i ña di n sau: T di n ñu, Kh i l p ph ươ ng, Bát di n ñu, Th p nh di n ñu, Nh th p di n ñu. 6. Vi t ch ươ ng trình ñ mô ph ng các m t toán h c: yên ng a, m t c u, hình xuy n 68
72. CH ƯƠ NG VI THI T K ðƯNG VÀ M T CONG BEZIER VÀ B-SPLINE Khác v i nh ng ph ươ ng pháp bi u di n m t và ñưng b i các công th c toán h c tưng minh, ñây ta s bàn ñn các công c cho phép ch ra các d ng ñưng và m t khác nhau d a trên các d li u. ðiu này có ngh ĩa là v i m t ñưng cong cho tr ưc mà ta ch ưa xác ñnh ñưc công th c toán h c c a nó thì làm th nào ñ có th n m b t ñưc d ng c a ñưng cong ñó mt cách t ươ ng ñi chính xác qua vi c s d ng m t t p nh các ñim P 0 , P 1 , cùng vi m t ph ươ ng pháp n i suy nào ñó t t p ñim này ñ t o ra ñưng cong mong mu n v i m t ñ chính xác cho phép. Có nhi u cách ñ n m b t ñưc ñưng cong cho tr ưc, ch ng h n: • Ly m t m u ñưng cong ch ng vài ch c ñim cách nhau t ươ ng ñi ng n r i tìm m t hàm toán h c và ch nh hàm này sao cho nó ñi qua các ñim này và kh p v i ñưng cong ban ñu. Khi ñó, ta có ñưc công th c c a ñưng và dùng nó ñ v l i ñưng cong. • Cách khác là dùng m t t p các ñim ki m soát và dùng m t thu t toán ñ xây dng nên m t ñưng cong c a riêng nó d a trên các ñim này. Có th ñưng cong ban ñu và ñưng cong t o ra không kh p nhau l m, khi ñó ta có th di chuy n m t vài ñim ki m soát và lúc này thu t toán l i phát sinh m t ñưng cong m i d a trên t p ñim ki m soát m i. Ti n trình này l p l i cho ñn khi ñưng cong t o ra kh p v i ñưng cong ban ñu. ñây, ta s ti p c n v n ñ theo ph ươ ng pháp th hai, dùng ñn các ñưng cong Bezier và B-Spline ñ t o các ñưng và m t. Gi s m t ñim trong không gian ñưc bi u di n d ưi d ng vector tham s p(t). Vi các ñưng cong 2D, p(t) = (x(t), y(t)) và các ñưng 3D, p(t) = (x(t), y(t), z(t)). 6.1. ðƯNG CONG BEZIER VÀ M T BEZIER 6.1.1. Thu t toán Casteljau
73. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline ð xây d ng ñưng cong p(t), ta d a trên m t dãy các ñim cho tr ưc r i t o ra giá tr p(t) ng vi m i giá tr t nào ñó. Vi c thay ñi các ñim này s làm thay ñi d ng ca ñưng cong. Ph ươ ng pháp này t o ra ñưng cong d a trên m t dãy các b ưc n i suy tuy n tính hay ni suy kho ng gi a (In-Betweening). Ví d : V i 3 ñim P 0 , P 1 , P 2 ta có th xây d ng m t Parabol n i suy t 3 ñim này bng cách ch n m t giá tr t ∈ [0, 1] nào ñó r i chia ñon P 0P1 theo t l t, ta ñưc 1 1 1 ñim P 0 trên P 0P1 . T ươ ng t , ta chia ti p P 1P2 c ũng theo t l t, ta ñưc P 1 . N i P 0 1 1 1 2 và P 1 , l i l y ñim trên P 0 P1 chia theo t l t, ta ñưc P 0 . 2 Vi cách làm này, ta s l y nh ng giá tr t khác ∈ [0, 1] thì s ñưc t p ñim P 0 . ðó chính là ñưng cong p(t). Ta bi u di n b ng ph ươ ng trình: 1 P0 (t) = (1-t).P 0 + t.P 1 (1) 1 P1 (t) = (1-t).P 1 + t.P 2 (2) 2 1 1 P0 (t) = (1-t).P 0 + t.P 1 (3) Thay (1), (2) vào (3) ta ñưc: 2 2 2 P(t) = P 0 (t) = (1-t) .P 0 + 2t.(1-t).P 1 + t .P 2 ðây là m t ñưng cong b c 2 theo t nên nó là m t Parabol. Tng quát hóa ta có thu t toán Casteljau cho (L+1) ñim: Gi s ta có t p ñim: P 0, P 1, P 2, , P L r Vi m i giá tr t cho tr ưc, ta t o ra ñim P i (t) th h th r, t th h th (r - 1) tr ưc ñó, ta có: r r-1 r-1 Pi (t) = (1-t).P i (t) + t.P i+1 (t) (3’) r = 0,1, ,L và i = 0, ,L-r L Th h cu i cùng P 0 (t) ñưc g i là ñưng cong Bezier c a các ñim P 0,P 1 ,P 2, ,P L Các ñim P i , i=0,1, ,L ñưc g i là các ñim ki m soát hay các ñim Bezier. ða giác t o b i các ñim ki m soát này g i là ña giác ki m soát hay ña giác Bezier. 6.1.2. D ng Bernstein c a các ñưng cong Bezier ðưng cong Bezier d a trên (L+1) ñim ki m soát P 0 ,P 1 , ,P L ñưc cho b i công th c: L L P(t) = ∑ Pk.B k (t) k=0 70
74. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline Trong ñó, P(t) là m t ñim trong m t ph ng ho c trong không gian. L Bk (t) ñưc g i là ña th c Bernstein, ñưc cho b i công th c: L L! L-k k Bk (t) = (1-t) .t vi L ≥ k k!( L− k )! L Mi ña th c Bernstein có b c là L. Thông th ưng ta còn g i các B k (t) là các hàm tr n (blending function). Tươ ng t , ñi v i m t Bezier ta có ph ươ ng trình sau: M L M L P(u,v) = ∑ ∑ Pi,k .B i (u).Bk (v) i=0 i=0 Trong tr ưng h p này, kh i ña di n ki m soát s có (M+1).(L+1) ñnh. P1 1 P0 1 P1 2 P0 P1 P2 ðưng cong Bezier b c 2 ðưng cong Bezier b c 3 Hình 6.1 6.1.3. D ng bi u di n ma tr n c a ñưng Bezier ð thích h p cho vi c x lý trên máy tính, ta bi u di n hai m ng BL(t) và P nh ư sau: L L L L B (t) = (B 0 (t), B 1 (t), , B L (t)) P = (P 0 ,P 1 , ,P L ) Do ñó: P(t) = B L(t).P (tích vô h ưng) hay P(t) = B L(t).P T (P T là d ng chuy n v c a P) L Dưi d ng ña th c, có th bi u di n B k (t) nh ư sau: L 2 L 0 1 L Bk (t) = a 0 + a 1.t + a 2.t + + a L.t = (t ,t , ,t ).(a 0 ,a 1 , ,a L) Do ñó P(t) có th bi u di n l i nh ư sau: P(t) = Pow L(t).Bez L.P T Vi: • Pow L(t) = (t 0,t 1, ,t L) 71
75. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline • Bez L là ma tr n bi u di n m ng B L(t) trong ñó m i hàng i c a ma tr n ng v i L L các h s t ươ ng ng (a 0 ,a 1 , ,a L) c a ña th c B i (t) và t i v trí (i,j) trong ma tr n Bez L j-i i j có giá tr Bez (i,j) = (-1) .C n .C i Ví d : Ma tr n Bez 3 cho các ñưng Bezier b c 3  1 0 0 0   −3 3 0 0 Bez 3 =    3− 6 3 0    −1 3 − 3 1 6.1.4. T o và v các ñưng Bezier ð t o ra m t ñưng cong Bezier t m t dãy các ñim ki m soát ta s áp d ng ph ươ ng pháp l y m u hàm p(t) các giá tr cách ñu nhau c a tham s t, ví d có th ly ti = i/N, i=0,1, ,N. Khi ñó ta s ñưc các ñim P(t i) t công th c Bezier. Ni các ñim này b ng các ñon th ng ta s ñưc ñưng cong Bezier g n ñúng. ð L tính P(t i) ta có th áp d ng ma tr n c a P(t) trên trong ñó ch có thành ph n Pow (t i) L T là thay ñi, còn tích Bez .P v i P = (P 0 ,P 1 , ,P L ) là không thay ñi. Sau ñây là th t c minh h a vi c v ñưng cong Bezier trong m t ph ng: Type Mang = array[0 50] of PointType; function tich(x,y:word):real; var s:real;i:word; begin if y<=1 then tich:=1 else begin s:=1; for i:=x to y do s:=s*i; tich:=s; end; end; function CLK(l,k:word):real; begin CLk:=tich(k+1,l)/tich(1,l-k); end; function Xmu(x:real;mu:word):real; 72
76. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline var i:word;s:real; begin if mu=0 then s:=1 else begin s:=1; for i:=1 to mu do s:=s*x; end; Xmu:=s; end; function BKL(t:real;l,k:word):real; begin BKL:=CLK(l,k)*xmu(1-t,l-k)*xmu(t,k); end; procedure Pt(t:real;L:word;A:Mang;var diem:PointType); var k:word;s,x,y:real; begin x:=0; y:=0; for k:=0 to L do begin s:=BKL(t,l,k); x:=x+A[k].x*s; y:=y+A[k].y*s; end; diem.x:=round(x); diem.y:=round(y); end; procedure Vebezier(A:Mang;L:integer); var i,SoDiem:word; Diem:PointType; dx,x:real; begin sodiem:=100; dx:=1/sodiem; 73
77. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline x:=0; if L>0 then begin for i:=1 to sodiem+1 do begin Pt(x,L,A,Diem); if i=1 then moveto(round(diem.x),round(diem.y)) else lineto(round(diem.x),round(diem.y)); x:=x+dx; end; end end; 6.1.5. Các tính ch t c a ñưng cong Bezier i/ Ni suy ñưc các ñim ñu và cu i. Ch ng minh : L L Ta có: P(t) = ∑ Pk.B k (t) k=0 L L Do ñó P(0) = ∑ Pk.B k (0) k=0 L L! L-k k trong ñó: B k (0) = (1-0) .0 ∀k ≠ 0 và k ≠ L k!( L− k )! L! = .0 = 0 k!( L− k )! L L Vì v y, P(0) = P 0.B 0 (0) + PL.B L (0) = P 0 + 0 = P 0 Lý lu n t ươ ng t cho P(1). Ta có P(1) = P L. ii/ Tính b t bi n Affine: Khi bi n ñi m t ñưng cong Bezier, ta không c n bi n ñi m i ñim trên ñưng cong m t cách riêng r mà ch c n bi n ñi các ñim ki m soát c a ñưng cong ñó r i s d ng công th c Bernstein ñ tái t o l i ñưng cong Bezier ñã ñưc bi n ñi. Ch ng minh : Gi s ñim P(t) bi n ñi Affine thành P’(t) 74
78. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline L L P’(t) = P(t).N + tr = ∑ Pk.B k (t).N + tr k=0 Trong ñó: N: ma tr n bi n ñi. tr: vector t nh ti n. L L Xét ñưng cong ∑ (P k.N + tr).B k (t) (*) k=0 ñưc t o ra b ng cách bi n ñi Affine các vector P k. Ta s ch ng minh ñưng cong này chính là P’(t). L L L L Khai tri n (*) ta có: ∑ Pk.N.B k (t) + ∑ tr.B k (t) k=0 k=0 L L L L = ∑ Pk.N.B k (t) + tr. ∑ Bk (t) ( ) k=0 k=0 L L L Nh ưng theo ña th c Bernstein thì ∑ Bk (t) = (1-t+t) = 1 nên s h ng th hai c a k=0 ( ) s là tr. Vì v y, P’(t) n m trên ñưng cong Bezier t o ra b i các ñim ki m soát P k. iii/ Tính ch t c a bao l i: ñưng cong Bezier P(t) không bao gi ñi ra ngoài bao l i ca nó. ñây, bao l i c a các ñim ki m soát là t p ñnh nh nh t ch a t t c các ñim ki m soát ñó. Ch ng minh : Bao l i c a các ñim ki m soát c ũng chính là t p h p các t h p l i c a các ñim ki m soát. Ta bi u di n t h p tuy n tính c a các ñim Pk: L P(t) = ∑ ak.P k , ak ≥ 0 k=0 L L Do P(t) là t h p l i ca các ñim ki m soát ∀t ∈ [0,1] và ∑ Bk (t) = 1 k=0 Nên ñưng cong Bezier s n m trong bao l i c a các ñim ki m soát. iv/ ð chính xác tuy n tính: ðưng cong Bezier có th tr thành m t ñưng th ng khi t t c các ñim ki m soát n m trên m t ñưng th ng vì khi ñó bao l i c a chúng là m t ñưng th ng 75
79. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline nên ñưng Bezier b k p vào bên trong bao l i nên nó c ũng tr thành ñưng th ng. v/ Bt k ỳ m t ñưng th ng hay m t ph ng nào c ũng luôn luôn c t ñưng cong Bezier ít l n h ơn so v i c t ña giác ki m soát. vi/ ðo hàm c a các ñưng Bezier: L−1 L-1 Ta có: (P(t))’ = L. ∑ ∆Pk.B k (t) , ∆Pk = P k+1 - P k k=0 Do ñó, ño hàm c a ñưng cong Bezier là m t ñưng cong Bezier khác ñưc to ra t các vector ki m soát ∆Pk ( Ta ch c n l y các ñim ki m soát g c theo tng c p ñ t o ra các ñim ki m soát cho (P(t))’. 6.1.6. ðánh giá các ñưng cong Bezier Bng các ñim ki m soát, ta có th t o ra các d ng ñưng cong khác nhau b ng cách hi u ch nh các ñim ki m soát cho t i khi t o ra ñưc m t d ng ñưng cong mong mu n. Công vi c này l p ñi l p l i cho ñn khi toàn b ñưng cong th a yêu cu. Tuy nhiên, khi ta thay ñi b t k ỳ m t ñim ki m soát nào thì toàn b ñưng cong b thay ñi theo. Nh ưng trong th c t , ta th ưng mong mu n ch thay ñi m t ít v d ng ñưng cong g n khu v c ñang hi u ch nh các ñim ki m soát. L Tính c c b y u c a ñưng cong Bezier ñưc bi u hi n qua các ña th c B k (t) ñu khác 0 trên toàn kho ng [0,1]. M t khác ñưng cong p(t) l i là m t t h p tuy n tính L ca các ñim ki m soát ñưc gia tr ng b i các hàm B k (t) nên ta k t lu n r ng m i ñim ki m soát có nh h ưng ñn ñưng cong t t c các giá tr t ∈ [0,1]. Do ñó, hi u ch nh b t k ỳ m t ñim ki m soát nào c ũng s nh h ưng ñn d ng c a toàn th ñưng cong. ð gi i quy t bài toán này, ta s dng m t t p h p các hàm tr n khác nhau. Các hàm tr n này có giá mang (support: kho ng mà trên ñó hàm l y giá tr khác 0) ch là mt ph n c a kho ng [0,1]. Ngoài giá mang này chúng có giá tr là 0. Th ưng ta ch n các hàm tr n là các ña th c trên các giá mang ñó, các giá mang này k nhau. Nh ư v y, các hàm tr n chính là m t tp các ña th c ñưc ñnh ngh ĩa trên nh ng kho ng k nhau ñưc n i l i v i nhau ñ t o nên m t ñưng cong liên t c. Các 76
80. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline ñưng cong k t qu ñưc g i là ña th c riêng ph n hay t ng ph n (piecewise polynomial). Ví d : ta ñnh ngh ĩa hàm g(t) g m 3 ña th c a(t), b(t), c(t) nh ư sau:  1 a(t) = t 2 coï giaï mang [0,1]  2  3 3 g(t) = b(t) = - (t - )2 coï giaï mang [1,2]  4 2 1 c(t) = (3 - t)2 coï giaï mang [2,3]  2 Giá mang c a g(t) là [0,3] Các giá tr c a t ng v i các ch n i ca các ñon g i là nút (knut), ch ng h n t=0,1,2,3 là b n nút c a g(t). H ơn n a, t i các ch n i c a ñưng cong g(t) là tr ơn, không b g p khúc. Do ñó, ta g i ñó là hàm Spline . Vy, m t hàm Spline c p m là ña th c riêng ph n c p m có ño hàm c p m -1 liên t c m i nút. Da trên tính ch t c a hàm Spline, ta có th dùng nó nh ư các hàm tr n ñ t o ra ñưng cong p(t) d a trên các ñim ki m soát P 0, ,P L. Khi ñó: L P(t) = ∑ Pk.g k(t) k=0 Tng quát hóa, ta xây d ng m t hàm p(t) v i L+1 ñim ki m soát nh ư sau: Vi m i ñim ki m soát P k , ta có m t hàm tr n t ươ ng ng R k(t) và tp các nút g i là vector nút T=(t 0,t 1, ,t n) v i t i ∈ R, t i ≤ t i+1 . Khi ñó: L P(t) = ∑ Pk.R k(t) k=0 6.2. ðƯNG CONG SPLINE VÀ B-SPLINE 6.2.1. ðnh ngh ĩa L Theo trên ta có: P(t) = ∑ Pk.R k(t) (*) k=0 trong ñó Pk v i k=1 L là các ñim ki m soát. Rk(t) là các hàm tr n liên t c trong m i ñon con [t i , t i+1 ]và liên t c trên mi nút. M i R k(t) là m t ña th c riêng ph n. Do ñó ñưng cong p(t) là t ng c a các ña th c này, l y trên các ñim ki m soát. 77
81. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline Các ñon ñưng cong riêng ph n này g p nhau các ñim nút và t o cho ñưng cong tr nên liên t c. Ta g i nh ng ñưng cong nh ư v y là SPLINE . Cho tr ưc m t vector nút thì có th có nhi u h hàm tr n ñưc dùng ñ t o ra m t ñưng cong Spline có th ñnh ngh ĩa trên vector nút ñó. M t h các hàm nh ư v y ñưc gi là cơ s cho các Spline. Trong s các h hàm này, có m t c ơ s c th mà các hàm tr n c a nó có giá mang nh nh t và nh v y nó ñem l i kh n ăng ki m soát c c b l n nh t. ðó là các B- Spline , v i B vit t t c a ch Basic (c ơ s ). ði v i các hàm B-Spline, m i ña th c riêng ph n t o ra nó có m t c p m nào ñó. Do ñó, thay vì dùng ký hi u Rk(t) cho các hàm riêng ph n này ta s ký hi u các hàm tr n này là Nk,m (t) . L Do ñó các ñưng cong B-Spline có th bi u di n l i: P(t) = ∑ Pk.N k,m (t) k=0 TÓM L I ð xây d ng các ñưng cong B-Spline ta c n có: • M t vector nút T=(t 0, t 1, t 2, ,t k+m-1). • (L+1) ñim ki m soát. • C p m c a các hàm B-Spline và công th c c ơ b n cho hàm B-Spline N k,m (t) là:  t− tk   tk+ m − t  Nk,m(t) =   .N k,m-1(t) +   .N k+1,m-1(t) v i k=0 L  tk+ m − 1 − t k   tk+ m− t k + 1 1 tk π t ≤ tk + 1 ðây là m t công th c ñ quy v i N k,L (t) =  0 ngæåüc laûi (Hàm h ng b ng 1 trên ñon (t k , t k+1 ) ði v i các m t B-Spline, ta có công th c bi u di n t ươ ng t : M L P(u,v) = ∑ ∑ Pi,k .N i,m (u).N k,m (v) i=0 k=0 Nh n xét : C ác ñưng Bezier là các ñưng B-Spline. 6.2.2. Các tính ch t h u ích trong vi c thi t k các ñưng cong B-Spline i/ Các ñưng B-Spline c p m là các ña th c riêng ph n c p m. Chúng là các Spline do chúng có m-2 c p ño hàm liên t c m i ñim trong giá mang c a chúng. 78
82. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline Các hàm B-Spline c p m t o thành mt c ơ s cho b t k ỳ Spline nào có cùng cp ñưc ñnh ngh ĩa trên cùng các nút . Các Spline có th ñưc bi u di n nh ư mt t h p tuy n tính c a các B-Spline. ii/ Hàm tr n B-Spline N k,m (t) b t ñu tk và k t thúc t k+m . Giá mang c a nó là [t k,t k+m ]. Giá mang c a h các hàm N k,m (t) v i k=0, L là kho ng [t 0,t m+L ]. iii/ Mt ñưng cong B-Spline ñóng d a trên L+1 ñim ki m soát có th ñưc t o ra bng cách dùng ph ươ ng trình ñưng B-Spline tu n hoàn sau: L P(t) = ∑ Pk.N 0,m ((t-k) mod (L+1)) k=0 Vi gi thi t các nút cách ñu nhau trong ñnh ngh ĩa c a hàm N 0,m ( ). iv/ Nu dùng vector chu n thì ñưng cong B-Spline s n i suy các ñim ki m soát ñu tiên và cu i cùng. Các h ưng kh i ñu và k t thúc c a ñưng cong ñó s nm d c theo các c nh ñu tiên và cu i cùng c a ña giác ki m soát. v/ Mi hàm B-Spline N k,m (t) là không âm ∀t, và t ng các h hàm này b ng 1: L ∑ Nk,m (t) = 1 ∀t ∈ [t 0 , t m+L ] k=0 vi/ Các ñưng cong d a trên các B-Spline là b t bi n Affin . Do ñó, ñ bi n ñi mt ñưng cong B-Spline, ch c n bi n ñi các ñim ki m soát, sau ñó kh i t o li ñưng cong t các ñim ki m soát ñã ñưc bi n ñi này. vii/ Mt ñưng cong B-Spline s n m trong bao l i c a các ñim ki m soát Mnh h ơn: b t k ỳ t nào, ch có m hàm B-Spline là khác 0. Vì v y, m i t ñưng cong ph i n m trong bao l i c a h u h t m ñim ki m soát kích ho t k nhau. (Các ñim ki m soát kích ho t là các ñim mà t i ñó hàm B-Spline khác 0) viii/ ð chính xác tuy n tính c a ñưng cong B-Spline: N u m ñim ki m soát k nhau là tuy n tính cùng nhau thì bao l i c a chúng là m t ñưng th ng. Do ñó ñưng cong c ũng s tr thành ñưng th ng. ix/ Tính ch t gi m ñ bi n thiên: S giao ñim gi a ñưng cong B-Spline v i b t kỳ m t m t ph ng nào (n u có) luôn luôn nh h ơn s giao ñim (n u có) gi a ña giác ki m soát c a nó v i m t ph ng ñó. 6.2.3. Thi t k các m t Bezier và B-Spline 79
83. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline Ta có th dùng các hàm tr n Bezier và B-Spline ñ mô t và v các m t cong. ði vi các m t cong, ta bi u di n chúng d ưi d ng tham s qua m t hàm vector v i 2 tham s là u, v. D ng t ng quát c a m t m t cong là: p(u,v) = (X(u,v),Y(u,v),Z(u,v)) ⇔ p(u,v) = X(u,v).i + Y(u,v).j + Z(u,v).k Khi u, v bi n thiên trên m t kho ng nào ñó thì các hàm X(u,v), Y(u,v) và Z(u,v) thay ñi giá tr , do ñó làm cho v trí c a p(u,v) thay ñi trong không gian 3 chi u. Chúng ta s không bi u di n các m t qua các hàm toán h c t ưng minh mà s bi u di n chúng qua các ñim ki m soát. Ví d : p(u,v) = (1-v).((1-u).P 00 + u.P 10 ) + v.((1-u).P 01 + u.P 11 ) dùng 4 ñim ki m soát 4 góc là Pij v i các hàm tr n là tuy n tính theo u, v. 6.2.4. Các b ăng Bezier ðưng cong Bezier trong không gian 3 chi u có th ñưc vi t d ưi d ng là m t hàm c a tham s v v i L+1 ñim ki m soát tùy thu c vào tham s u theo m t ki u nào L L ñó: Ch ng h n P(u,v) = ∑ Pk(u).B k (v) (*) k=0 Ngh ĩa là m i ñưng vi n u là m t ñưng cong Bezier chu n, nh ưng nh ng giá tr u khác nhau thì các ñim ki m soát c ũng n m nh ng v trí khác nhau. Khi u bi n thiên thì m i ñim ki m soát P k(u) s ch y trên m t ñưng cong c th . Do ñó, m t cong có th xem nh ư là m t s d ch chuy n ñưng Bezier trong không gian. Ta t ưng t ưng m t ña giác ki m soát chuy n ñng trong không gian và thay ñi dng khi chuy n ñng. m i v trí, ña giác này t o nên m t ñưng cong Bezier và mt cong t o thành chính là cái vt còn ñ l i bên d ưi c a ñưng cong này. Ví d : Phép chi u ph i cách c a m t m t ñưc t o ra b i vi c n i suy tuy n tính gi a 2 ñưng cong Bezier d a trên 2 ña giác ki m soát là P 0 và P 1. M i ñưng cong 0 1 ki m soát p k(u) ñưc n i suy tuy n tính gi a 2 ñim ki m soát P k và P k khi u bi n thiên gi a 0 và 1: 0 1 pk(u) = (1-u).P k + u.P k k=0,1,2,3 Gi s các ñưng cong ki m soát p k(u) chính là các ñưng cong Bezier, m i ñưng cong này d a trên m +1 ñim ki m soát c a chúng. 80
84. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline M M Vì v y: Pk(u) = ∑ Pi,k .B i (u) i=0 Kt h p p k(u) này vào ph ươ ng trình (*) ta ñưc: M L M L P(u,v) = ∑ ∑ Pi,k .B i (u).B k (v) ( ) i=0 k=0 Ta g i ñây là d ng tích Tensor cho b ăng Bezier. Cũng gi ng nh ư các ña giác ki m soát trong 2D, m t kh i ña di n ki m soát là m t mng g m có (M+1).(L+1) ñnh. Tóm l i, ñ t o ra m t b ăng ta ch c n ch ra các v trí c a các ñnh này r i sau ñó áp dng ph ươ ng trình ( ) ñ v các ñưng vi n hay ñnh ngh ĩa d ng m t cong. 6.2.5. Dán các b ăng Bezier v i nhau Mc ñích là ñ t o ra các d ng m t ph c t p g m nhi u b ăng Bezier k t l i v i nhau mt cách tr ơn tru các biên chung. Khi n i 2 b ăng Bezier l i v i nhau, m i b ăng có m t kh i ña di n ki m soát riêng và ñu ñưc t o ra t ph ươ ng trình (*) v i u, v bi n thiên trong kho ng [0,1]. V n ñ là làm sao cho 2 b ăng có th dán vào nhau m t cách tr ơn tru. • Hai b ăng s g p nhau t t c các ñim d c theo biên chung n u các kh i ña di n ki m soát c a chúng kh p nhau biên. Nh ư v y, ta ch c n ch n các ña giác ki m soát biên ñ cho 2 b ăng ñng nh t nhau biên. Có th th y ñưc ñiu này khi thay u=0 vào trong ph ươ ng trình (*) trên. • M t ñiu ki n ñ n a là m i c p c nh c a kh i ña di n mà nó g p nhau biên ph i tuy n tính cùng nhau. 6.2.6. Các b ăng B-Spline Các hàm B-Spline có th ñưc s d ng trong d ng tích Tensor thay cho các ña th c Bernstein ñ ñt ñưc tính ki m soát cao h ơn khi thi t k m t cong. ðiu ñó có ngh ĩa ta s thay ph ươ ng trình ( ) thành: M L P(u,v) = ∑ ∑ Pi,k .N i,m (u).N k,m (v) i=0 k=0 Kh i ña di n ki m soát g m có (L+1).(M+1) ñim ki m soát; u,v bi n thiên t 0 t i giá tr nút l n nh t trong các vector nút t ươ ng ng c a chúng. 81
85. Ch ươ ng VI. Thi t k ñưng cong và m t cong Bezier và B-Spline ði v i các b ăng B-Spline, ng ưi ta v n dùng các B-Spline b c 4. Do vi c ch n s ñim ki m soát là không gi i h n nên có th t o ra nhi u d ng m t cong r t ph c t p. Tt nhiên khi thi t k , ta ph i ch n kh i ña din nút ñ t o ra m t có d ng mong mu n. 82
86. CH ƯƠ NG VII KH ðƯNG VÀ M T KHU T 7.1. CÁC KHÁI NI M Mt v t th 3D có th bi u di n trong máy tính b ng nhi u mô hình khác nhau, song hai mô hình ph bi n nh t ñó là mô hình khung dây (WireFrame) và mô hình các m t ña giác ( Polygon mesh model) • Mô hình WireFrame: ðã trình bày ch ươ ng 5, nó cho ta hình dáng c a v t th dưi d ng m t b khung • Mô hình các m t ña giác: ñây m t v t th 3D ñưc xác ñnh thông qua các m t (thay vì các c nh nh ư trong mô hình WireFrame), và m i m t m t l i ñưc xác ñnh thông qua các ñim mà các ñim này ñưc xem nh ư là các ñnh c a m t ña giác, v i mô hình các m t ña giác thì chúng ta không ch t o ra ñưc hình dáng c a vt th nh ư mô hình Wireframe mà còn th hi n ñưc các ñc tính v màu s c và nhi u tính ch t khác c a v t th . Song ñ có th mô t v t th 3D m t cách trung th c (nh ư trong th gi i Mt 1 2 th c) thì ñòi h i ng ưi l p trình ph i tính toán và gi l p 1 nhi u thông tin, mà m u ch t Mt 5 là v n ñ kh m t khu t và 3 chi u sáng.Trong ch ươ ng Mt 4 Mt 3 này chúng ta s t p trung 5 nghiên c u v n ñ kh m t khu t. 4 Ví d : Mô t v t th nh ư trong Mt 2 hình 7.1. 6 - Danh sách các ñnh: 1,2,3,4,5,6 Hình 7.1 - Danh sách các m t ñưc xác ñnh theo b ng sau: Mt ðnh