Giáo trình lý thuyết đồ họa

Chia sẻ: Pham Ngoc An | Ngày: | Loại File: PDF | Số trang:146

0
392
lượt xem
154
download

Giáo trình lý thuyết đồ họa

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

Đồ 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 một trong những môn họa chính trong các chuyên ngành công nghệ thông...

Chủ đề:
Lưu

Nội dung Text: Giáo trình lý thuyết đồ họa

  1. M CL 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 ñi m........................................................................................ 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. ði m..................................................................................................................... 6 1.3.2. Các bi u di n t a ñ ............................................................................................ 8 1.3.3. ðo n th ng........................................................................................................... 8 1.4. Các thu t toán v ño n th ng................................................................................. 8 1.4.1. Bài toán ................................................................................................................ 8 1.4.2. Thu t 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 ño n 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 ño n 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 ñi m.................................................................................................. 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. L IM ð 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 m t 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 ñ h a 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 ñ h a, ñi m, ño n 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. M c 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 . ði n 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 d ng 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. V i 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 D a 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 ñi m
  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 ñi m r i r c (grid), t ng ñi m ñ 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 ñi m ñó. T p h p t t c các pixel c a grid t o 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 ñi m 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. T o 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. T o 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 ñi n t : dùng nh ng ng d ng c a ñ h a ñ 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 d ng ñ h a cho phép chúng ta thi t k các thi t b cơ khí, ñi n, ñi n 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 d ng hi n nay c a ñ 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í, ñi n 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 g c, 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 d ng 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 ñi n 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 ñi n 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ư: ði m, ño n 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 ñi n 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 T p 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 c nh c th : xu t, nh p, bi n ñ i nh, ... bao g m: • T p 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ư ñi m, ñư ng th ng, ña giác, ñư ng tròn,... • T p 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 ñ ñi u khi n và x lý các d li u nh p sao cho có hi u qu . M t 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 M i 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 c a 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. ði m (Pixel) Trong các h th ng ñ h a, m t ñi m ñư c bi u th b i các t a ñ b ng s . Ví du: Trong m t ph ng, m t ñi m là m t c p (x,y) Trong không gian ba chi u, m t ñi m là b ba (x,y,z) Trên màn hình c a máy tính, m t ñi m 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 ñi m tương ng trên màn hình. S ñi m 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 ñi m 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. • N u 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; • N u mu n truy xu t tr c ti p vào vùng ñ m màn hình: Gi s m t ñi m (x,y) ñư c v trên màn hình v i ñ phân gi i 320x200x256 (mode 13h), ñi m ñó 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 ñ H u 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 T a ñ th gi i th c T a ñ thi t b màn hình. Hình 1.1 1.3.3. ðo n th ng Trong các h th ng ñ h a, các ño n th ng ñư c bi u th b i vi c “tô” ño n th ng b t ñ u t ñi m ñ u mút này kéo dài cho ñ n khi g p ñi m ñ u mút kia. 1.4. CÁC THU T TOÁN V ðO N 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 ño n th ng ñi qua 2 ñi m 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 b c thang (do làm tròn). V n ñ ñ 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 01: ta hoán ñ i vai trò c a x,y cho nhau. N u ch n ∆y=1 thì: xk+1 = xk + 1/m Tương t , n u ñi m B n m bên trái và A n m bên ph i thì: yk+1 = yk - m (01, ∆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 ñi m v ñ u tiên} V ñi m (x,y); Cho i ch y t 1 ñ n Step: x = x + IncX; y = y + IncY; V ñi m (Round(x),Round(y)) T ñó ta có th t c v ño n 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 ñi m: 1 x − x1 y − y1 y = (*) x 2 − x1 y 2 − 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
  14. Chương I. Các y u t cơ s c a ñ h a (xi + 1,yi) ho c (xi +1,yi +1) (Xem hình 1.2) Xét kho ng cách gi a 2 ñi m ch n v i ñi m n m trên ñư ng th c. N u kho ng cách nào bé hơn thì ta l y ñi m ñó. ð t: d1 = y - yi = m.(xi +1) + b - yi d2 = (yi +1) - y = yi + 1 - m.(xi + 1) - b Suy ra: d1 - d2 = 2m.(xi + 1) - 2yi + 2b - 1 ∆y = 2. .(xi + 1) - 2yi + 2b - 1 ∆x ⇔ ∆x(d1 - d2) = 2∆y.xi - 2∆x.yi + 2∆y + ∆x.(2b - 1) ð t pi = ∆x(d1 - d2) và C = 2∆y + ∆x.(2b - 1) thì pi = 2∆y.xi - 2∆x.yi + C (4) pi+1 = 2∆y.xi+1 - 2∆x.yi+1 + C Suy ra: pi+1 - pi = 2∆y(xi+1 - xi) - 2∆x(yi - yi+1) = 2∆y - 2∆x(yi+1 - yi) (5) ( vì xi+1 - xi = 1 ) * Nh n xét: . N u pi < 0: Ch n yi+1 = yi T (5) ⇒ pi+1 = pi + 2∆y. (d1d2) V i ñi m mút ñ u tiên, theo (4) ta có: p1 = 2∆y.x1 - 2∆x.y1 + 2∆y + ∆x[2.(y1 - m.x1) - 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
  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í xi +1, ta tính: pi+1 = pi + 2∆y n u pi < 0 pi+1 = pi + 2.( ∆y - ∆x) n u pi ≥ 0 N u pi+1 < 0 thì ta ch n to ñ y k ti p là yi+1 Ngư c l i thì ta ch n yi+1 +1 • Bư c 5: L p l i bư c 4 cho ñ n khi x = x2. Sau ñây là th t c cài ñ t thu t toán: Procedure LINE(x1,y1,x2,y2:integer); { 0
  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
  17. Chương I. Các y u t cơ s c a ñ h a 1 1 = A(xi+1+1) + B(yi+1 + ) + C - A(xi+1) - B(yi + ) - C 2 2 = A(xi+1 - xi) + B(yi+1 - yi) = A + B(yi+1 - yi) (vì xi+1 - xi =1) Suy ra: pi+1 = pi + A + B(yi+1 - yi) (*) *Nh n xét: . N u pi < 0: Ch n ñi m S: yi+1 = yi T (*) suy ra pi+1 = pi + A . N u pi ≥ 0: Ch n ñi m P: yi+1 = yi + 1 T (*) suy ra pi+1 = pi + A + B V i ñi m mút ñ u tiên, ta có: 1 1 p1 = F(x1 + 1,y1 + ) = A(x1+1) + B(y1 + ) + C 2 2 B B = Ax1 + Bx1 + C + A + =A+ (vì Ax1 + Bx1 + 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(xc,yc) 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 - xc)2 + (y - yc)2 = R2 (*) (- (x,y x,y) ) ⇔ y = yc ± R2 − ( x − xC ) 2 (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 ñ (xc=0 và yc=0). x) y,- * Ý tư ng: Hình Do tính ñ i x ng c a ñư ng tròn nên n u ñi m 1.4 (x,y)∈(C) thì các ñi m (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 (xi,yi) ñã v ñư c. C n ch n ñi m k ti p là (xi +1,yi) ho c (xi +1,yi -1) (Hình 1.5) T phương trình: x2 + y2 = R2 ta tính ñư c giá tr y th c ng v i xi +1 là: 13
  18. Chương I. Các y u t cơ s c a ñ h a y2 = R2 - (xi +1)2 ð t: d1 = yi2 - y2 = yi2 - R2 + (xi + 1)2 d2 = y2 - (yi - 1)2 = R2 - (xi + 1)2 - (yi - 1)2 yi y Suy ra: yi- pi = d1 - d2 = 2.(xi + 1)2 + yi2 + (yi - 1)2 - 2R2 (2) 1 ⇒ pi+1 = 2.(xi+1 + 1)2 + y2i+1 + (yi+1 - 1)2 - 2R2 (3) T (2) và (3) ta có: xi xi+1 pi+1 - pi = 4xi + 6 + 2.(y2i+1 - yi2) - 2.(yi+1 - yi) Hình 1.5 ⇒ pi+1 = pi + 4xi + 6 + 2.(y2i+1 - yi2) - 2.(yi+1 - yi) (4) * Nh n xét: N u pi < 0: ch n yi+1 = yi (4) ⇒ pi+1 = pi + 4xi + 6 N u pi ≥ 0: ch n yi+1 = yi - 1 (4) ⇒ pi+1 = pi + 4.(xi - yi) + 10 Ta ch n ñi m ñ 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 ñi m ñ u c n v (x1,y1) = (0,R) • Bư c 2: Tính P ñ u tiên: p1 = 3 - 2R N u p < 0: ch n ñi m k ti p là (xi +1,yi). Ngư c l i ch n ñi m (xi + 1,yi - 1) • Bư c 3: x:=x + 1, tính l i p: N u pi < 0: pi+1 = pi + 4xi + 6. Ngư c l i: pi+1 = pi + 4.(xi - yi) + 10 Khi ñó: N u pi+1 < 0: ch n ñi m k ti p là (xi +1,yi+1). Ngư c l i ch n ñi m (xi+1,yi+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
Đồng bộ tài khoản