intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Giáo trình đồ họa máy tính - Ths. Võ Phương Bình

Chia sẻ: Nguyễn Thị Quý | Ngày: | Loại File: PDF | Số trang:120

231
lượt xem
82
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đồ hoạ máy tính là 1 trong những lĩnh vực hấp dẫn và phát triển nhanh của công nghệ thông tin. Với giáo trình đồ họa máy tính của Ths.Võ Phương Bình các bạn sinh viên khoa công nghệ thông tin có thể học tốt hơn.Nó được ra đời bởi sự kết hợp của 2 lĩnh vực thông tin và truyền hình và được sử dụng rộng rãi trong hầu hết các ứng dụng như khoa học và công nghệ, y học, giáo dục, kiến trúc.

Chủ đề:
Lưu

Nội dung Text: Giáo trình đồ họa máy tính - Ths. Võ Phương Bình

  1. TRƯ NG Đ I H C ĐÀ L T KHOA CÔNG NGH THÔNG TIN ThS. VÕ PHƯƠNG BÌNH GIÁO TRÌNH Đ H A MÁY TÍNH Dành cho sinh viên ngành: Công ngh ph n m m, M ng và truy n thông Đà L t, 2010
  2. M CL C M U ...................................................................................................... 4 Chương 1 GI I THI U V H A MÁY TÍNH ................................................ 5 1.1 T ng quan h a máy tính ......................................................................... 5 1.2 Các thành ph n cơ b n c a h h a máy tính ................................................ 7 1.3 H t a th gi i th c, h t a thi t b và h t a chu n ............................... 7 Chương 2 CÁC THU T TOÁN V I TƯ NG H A CƠ B N .....................11 2.1 Thu t toán v o n th ng ............................................................................11 2.1.1 Thu t toán DDA (Digital DifferentialAnalyzer) ................................................. 12 2.1.3 Thu t toán MidPoint .......................................................................................... 17 2.2 Thu t toán MidPoint v ư ng tròn ..............................................................23 2.3 Thu t toán MidPoint v Ellipse ....................................................................27 2.4. ư ng cong tham s .................................................................................31 2.4.1. ư ng cong Bezier ................................................................................31 2.4.1.1. Thu t toán de Casteljau .............................................................................. 31 2.4.1.2. Thu t toán Horner....................................................................................... 34 2.4.2. ư ng cong B-Spline .............................................................................37 Bài t p chương 2 ...........................................................................................42 Chương 3 TÔ MÀU .......................................................................................44 3.1 Gi i thi u v màu s c ................................................................................44 3.2 Tô màu ơn gi n ......................................................................................44 3.3 Tô màu theo dòng quét (ScanConvert) ..........................................................48 3.4 Tô màu theo v t d u loang (FloodFill) ..........................................................52 Bài t p chương 3 ...........................................................................................54 Chương 4 PHÉP BI N I HAI CHI U............................................................55 4.1 Nh c l i các phép toán cơ s v i ma ma tr n. ..................................................55 4.2 Phép t nh ti n ...........................................................................................56 4.3 Phép bi n i t l ....................................................................................57 4.4 Phép quay ...............................................................................................57 4.5 Phép i x ng .........................................................................................60 4.6 Phép bi n d ng .........................................................................................60 Giáo trình H a Máy Tính 2
  3. 4.7 Phép bi n i Affine ngư c ........................................................................61 4.8 H t a thu n nh t ..................................................................................62 4.9 K t h p các phép bi n i ...........................................................................63 Bài t p chương 4 ...........................................................................................64 Chương 5 GIAO CÁC I TƯ NG H A ....................................................66 5.1. M u ..................................................................................................66 5.2. Giao c a hai o n th ng .............................................................................67 5.3. o n th ng và hình ch nh t .......................................................................68 5.3.1 Tìm giao b ng cách gi i h phương trình ....................................................... 69 5.3.2 Thu t toán chia nh phân ............................................................................... 69 5.3.3 Thu t toán Cohen-Sutherland ........................................................................ 72 5.3.4 Thu t toán Liang-Barsky ............................................................................... 74 5.4. Giao c a o n th ng và a giác l i ...............................................................77 5.5. Giao hai a giác .......................................................................................80 5.6. K thu t Ray tracing .................................................................................85 Chương 6 H A BA CHI U........................................................................91 6.1. Gi i thi u h a 3 chi u ...........................................................................91 6.2. Bi u di n i tư ng 3 chi u ........................................................................92 6.3. Các phép bi n i 3 chi u ..........................................................................98 6.3.1. H t a bàn tay ph i - bàn tay trái .................................................................. 98 6.3.2. Các phép bi n i Affine cơ s ......................................................................... 99 6.3.2.1 Phép quay quanh tr c x ................................................................................ 99 6.3.2.2 Phép quay quanh tr c y .............................................................................. 100 6.3.2.3 Phép quay quanh tr c z ............................................................................. 100 6.3.2.4 Phép quay quanh tr c song song v i tr c t a ....................................... 101 6.3.2.5 Phép quay quanh tr c b t kỳ ..................................................................... 103 PH L C: THƯ VI N H A OpenGL ....................................................... 107 TÀI LI U THAM KH O.............................................................................. 120 Giáo trình H a Máy Tính 3
  4. M U h a máy tính là m t trong nh ng lĩnh v c h p d n và phát tri n nhanh c a Công ngh Thông tin. Nó ư c ra i b i s k t h p c a 2 lĩnh v c thông tin và truy n hình, và ư c s d ng r ng rãi trong h u h t các ng d ng như khoa h c và công ngh , y h c, giáo d c, ki n trúc, và k c gi i trí. Ngày nay, nh vào s ti n b c a khoa h c k thu t nên ph n c ng và giá thành c a máy tính càng lúc càng phù h p, các k thu t h a ư c ng d ng trong th c t nhi u nên ngày càng có nhi u ngư i quan tâm nghiên c u n lĩnh v c này. Tuy nhiên, vi c d y và h c k thu t h a mày tính thì không ơn gi n vì ch này có nhi u v n ph c t p, liên quan n tin h c và c toán h c. H u h t các gi i thu t v , tô màu cùng các phép bi n hình u ư c xây d ng d a trên n n t ng c a hình h c không gian hai chi u và ba chi u. Giáo trình h a máy tính này ư c xây d ng d a trên kinh nghi m gi ng d y ã qua và d a trên tài li u tham kh o chính là : “Donald Hearn, M. Pauline Baker; Computer Graphics; Prentice-Hall, Inc., Englewood Cliffs, New Jersey , 1986”. Giáo trình h a máy tính là m t môn h c ư c gi ng d y cho sinh viên chuyên ngành Công ngh Thông tin v i 45 ti t lý thuy t và 30 ti t th c t p. N i dung c a giáo trình này g m có 3 v n chính như sau : • Trình bày các thu t toán v và tô các ư ng cơ b n như ư ng th ng, a giác, ư ng tròn, ellipse và các ư ng Bezier, B-Spline. Các thu t toán này giúp cho sinh viên có th t thi t k v và tô màu m t mô hình h a. • N i dung th hai cp n các phép bi n i Affine, tìm giao các i tư ng, tô màu c a h a hai chi u. • N i dung th ba trình bày v quan sát, hi n th và bi n i Affine trên không gian ba chi u. Trong quá trình biên so n ch c không tránh kh i thi u sót, tôi xin trân tr ng nh n ư c s góp ý c a các quý ng nghi p và sinh viên giáo trình ngày càng ư c hoàn thi n hơn. Giáo trình H a Máy Tính 4
  5. Chương 1 GI I THI U V H A MÁY TÍNH N i dung chính T ng quan v h a máy tính. Các ng d ng c a h a máy tính. Các thành ph n cơ b n c a h h a máy tính. H ta th c và h t a h a. 1.1 T ng quan h a máy tính h a máy tính bao g m t t c nh ng gì liên quan n vi c s d ng máy tính phát sinh ra hình nh. Các v n liên quan n công vi c này bao g m: t o, lưu tr , thao tác trên các mô hình và các nh. Ngày nay, h u h t các chương trình so n th o, b ng tính s d ng h a trong giao di n v i ngư i dùng. S phát tri n c a h a máy tính ngày càng r ng rãi v i các ch h a hai chi u (2D) và 3 chi u (3D), và cao hơn, nó ph c v trong các lĩnh v c xã h i h c khác nhau như khoa h c, giáo d c, y h c, k thu t, thương m i và gi i trí. Tính h p d n và a d ng c a h a máy tính có th ư c minh h a r t tr c quan thông qua vi c kh o sát các ng d ng c a nó. h a máy tính ư c s d ng r t r ng rãi vì có n 80% các ng d ng liên quan n hình nh và ư c ng d ng 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í, …v.v. S lư ng các chương trình h a ng d ng r t l n và phát tri n liên t c. Sau ây là m t s ng d ng tiêu bi u c a ha trong th c t : •H tr thi t k - CAD/CAM (Computer-Aided Design/ Computer-Aided Manufacturing): Các h th ng thi t k và ch t o v i s tr giúp c a máy tính ư c ng d ng trong các lĩnh v c như phân tích thi t k k t c u xây d ng, công nghi p i n t , công nghi p th i trang, các ngành công nghi p ch t o ôtô, máy bay, xe máy.... Giáo trình H a Máy Tính 5
  6. (Graphs and Charts): ây là ng d ng ch y u trong lĩnh v c • th và b n h a minh h a, ng d ng này cho phép hi n th các bi u d li u cũng như trong lĩnh v c bi u di n và x lý h a. M t trong s nh ng ng d ng hi n nay là h th ng thông tin a lí GIS (Geographical Information System).: • Gi i trí: V i s h tr h a hi n nay chúng ta có th s n xu t nhi u s n ph m ph c v cho lĩnh v c gi i trí c bi t là phim ho t hình và các trò chơi trên máy tính. Nhi u ph n m m và ngôn ng l p trình h tr ra i cho phép ta t o ra các hình nh ng g n v i v i cu c s ng th c. Trong giáo trình này chúng ta s làm quen v i công c OpenGL. • ng d ng mô ph ng và th c t i o (Simulation and Virtual Reality): Bên c nh vi c h tr thi t k ki n trúc và trong s n xu t công nghi p, h a máy tính còn có ng d ng r t quan tr ng trong mô ph ng các công trình ki n trúc, các di s n văn hóa, trong gi ng d y các môn h c. ng d ng th c t i o là m c cao hơn c a mô ph ng. Th c t i o áp d ng các k thu t h ak th pv i các thi t b 3D t o ra các ng d ng mô ph ng gi ng như th c nhưng ư c th c hi n trên máy tính như lái máy bay, b n súng trong quân s , gi i ph u trong y khoa, …. • X lý nh (Image Processing): Các kĩ thu t x lý và thay i m t b c nh có s n và ư c áp d ng trong nhi u lĩnh v c c a i s ng. Ví d ta có th s d ng ph n m m khôi ph c m t b c nh, phân tích các b c nh ư c ch p t v tinh... • Kĩ thu t nh n d ng (Pattern Recognition): ây là m t lĩnh v c c a kĩ thu t x lí nh, các chuyên gia s xây d ng m t thư vi n nh g c b ng cách áp d ng các thu t toán phân tích và ch n l c t nh ng nh m u có s n. D a trên thư vi n ó các chuyên gia có th phân tích và t h p nh h a ngư i dùng (Graphical User Interface-GUI): R t nhi u ph n • Giao di n m m ng d ng ngày nay cung c p GUI cho ngư i dùng. Thành ph n chính c a m t giao di n h a ó là chương trình qu n lí c a s cho phép ngư i s d ng hi n th nhi u c a s ngư i ta g i ó là các c a s hi n th . Nh có GUI mà ngư i s d ng có th d dàng thi t k giao di n cho các chương trình ng d ng. Giáo trình H a Máy Tính 6
  7. 1.2 Các thành ph n cơ b n c a h h a máy tính phát tri n h th ng h a máy tính ta c n ph i trang b c ph n c ng l n ph n m m cũng như các ng d ng khác. Trong ó, các thi t b ph n c ng là tùy thu c vào t ng ng d ng h a c th mà có th c n thi t ho c không c n thi t. P h n c ng • Thi t b thu nh n: l y d li u u vào cho ng d ng h a như bàn phím, chu t, máy quét, camera, ... • Thi t b hi n th : hi n th hình nh c a ng d ng h a như các lo i màn hình CRT, LCD, … • Thi t b tương tác: làm giao ti p trung gian gi a ngư i dùng và các ng d ng h a th c t i o, t o c m giác ngư i dùng gi ng như thao tác tr c ti p trong môi trư ng th gi i th c như găng tay, kính 3D, … Ph n m m Ph n m m h a có th phân thành 2 lo i: các công c l p trình và các trình ng d ng h a ph c v cho m t m c ích nào ó. Các công c l p trình cung c p m t t p các thư vi n h a có th ư c dùng trong các ngôn ng l p trình c p cao như Pascal, C/C++/C#, Java, … hay th m trí có c m t thư viên h a có th nhúng vào các ngôn ng l p trình c p b t kỳ như OpenGL, DirectX. Các hàm cơ s c a nó bao g m vi c t o các i tư ng cơ s c a hính nh như o n th ng, a giác, ư ng tròn, … thay i màu s c, ch n khung nhìn, bi n i affine, … phát tri n các ng d ng h a máy tính c n có các lo i ph n m m sau: • T o mô hình: 3DS Max, Maya, … • L p trình, phát tri n ng d ng: OpenGL, DirectX, … 1.3 H t a th gi i th c, h t a thi t b và h t a chu n M th h a bao g m 3 mi n như sau: • Mi n i u khi n : bao b c toàn b h th ng. Giáo trình H a Máy Tính 7
  8. • Mi n th c : n m trong mi n i u khi n. Khi m t giá tr n m trong mi n th c, nó s ư c chuy n thành s th c d u ph y ng, và khi có m t s r i kh i mi n này thì nó s ư c chuy n thành s nguyên. • Mi n hi n th : n m trong mi n i u khi n nhưng phân bi t v i mi n th c. Ch có giá tr s nguyên m i n m trong mi n hi n th . Trong lĩnh v c k thu t h a, chúng ta ph i hi u ư c r ng th c ch t c a h a là làm th nào có th mô t và bi n i ư c các i tư ng trong th gi i th c trên máy tính. Các i tư ng trong th gi i th c ư c mô t b ng t a trong mi n th c. Trong khi ó, h t a thi t b l i s d ng h t a nguyên hi n th các hình nh. ây chính là v n cơ b n c n gi i quy t. Ngoài ra, còn có m t khó khăn khác n a là v i các thi t b khác nhau thì có các c trưng v thông s k thu t khác nhau. Do ó, c n có m t phương pháp chuy n i tương ng gi a các h t a và i tư ng có th mô t g n úng v i hình nh th c bên ngoài. Hai mô hình cơ b n c a ng d ng h a là d a trên m u s hóa và d a trên c trưng hình h c. Trong ng d ng h a d a trên m u s hóa thì các i tư ng ha ư c t o ra b i lư i các pixel r i r c. Các pixel này có th ư c t o ra b ng các chương trình v , máy quét, ... Các pixel này mô t t a xác nh v trí và giá tr m u. Thu n l i c a ng d ng này là d dàng thay i hình nh b ng cách thay i màu s c hay v trí c a các pixel, ho c di chuy n vùng nh t nơi này sang nơi khác. Tuy nhiên, i u b t l i là không th xem xét i tư ng t các góc nhìn khác nhau. ng d n g h a d a trên c trưng hình h c bao g m các i tư ng h a cơ s như o n th ng, a giác, ...v.v. Chúng ư c lưu tr b ng các mô hình và các thu c tính. Ch ng h n, o n th ng ư c mô hình b ng hai i m u và cu i, có thu c tính như màu s c, dày. Ngư i s d ng không thao tác tr c ti p trên các pixel mà thao tác trên các thành ph n hình h c c a i tư ng. H ta th g i i th c H ta th c thư ng ư c dùng mô t các i tư ng trong th gi i th c là h ta Descartes. Trong h t a này, m i i m P ư c bi u di n b i m t c p t a (xp, yp) v i xp, yp ∈ R (xem hình 1.1). Giáo trình H a Máy Tính 8
  9. Hình 1.1 H t a th c Trong ó : • Ox : tr c hoành. • Oy : tr c tung. • xp : hoành i m P. • yp : tung i m P. H ta thi t b H ta thi t b ư c dùng cho m t thi t b xu t c th nào ó, ví d như máy in, màn hình, ...v.v. Trong h t a thi t b thì các i m cũng ư c mô t b i c p t a (x,y). Tuy nhiên, khác v i h t a th c là x, y ∈ . i u này có nghĩa là các i m trong h t a th c ư c nh nghĩa liên t c, còn các i m trong h t a thi t b là r i r c. Ngoài ra, các t a x, y c a h t a thi t b ch bi u di n ư c trong m t gi i h n nào ó c a . Ví d : phân gi i c a màn hình trong ch h a là 640x480. Khi ó, x ∈ (0,640) và y ∈ (0, 480) (xem hình 1.2). Giáo trình H a Máy Tính 9
  10. H ta màn hình H ta thi t b chu n Do cách nh nghĩa các h t a thi t b khác nhau nên hình nh hi n th chính xác trên thi t b này thì chưa ch c hi n th chính xác trên thí t b khác. Ngư i ta xây d ng m t h t a thi t b chu n i di n chung cho t t c các thi t b có th mô t các hình nh mà không ph thu c vào b t kỳ thi t b nào. Trong h t a chu n, các t a x, y s ư c gán các giá tr trong o n t [0,1]. Như v y, vùng không gian c a h t a chu n chính là hình vuông ơn v có góc trái dư i (0, 0) và góc ph i trên là (1, 1). Quy trình hi n th các i tư ng th c như sau (xem hình 1.3): Hình 1.3 H t a thi t b Giáo trình H a Máy Tính 10
  11. Chương 2 CÁC THU T TOÁN V I TƯ NG H A CƠ B N N i dung chính Các thu t toán v o n th ng: DDA, Bresenham, MidPoint. Thu t toán MidPoint v ư ng tròn, ellipse. V ư ng cong tham s Bezier, B-Spline. 2.1 Thu t toán v o n th n g Hình 2.1: Các i m g n o n th ng th c Xét o n th ng có h s góc m (0, 1] và ∆x > 0. V i các o n th ng d ng này, n u (xi, yi) là i m ã ư c xác nh bư c th i thì i m k ti p (xi+1, yi+1) bư c th i+1 s là m t trong hai i m sau: Vn t ra là ch n i m v như th nào o n th ng ư c v g n v i o n Giáo trình H a Máy Tính 11
  12. th ng th c nh t và t i ưu hóa v m t t c , th i gian th c. 2.1.1 Thu t toán DDA (Digital DifferentialAnalyzer) DDA (hay còn g i là thu t toán s gia) là thu t toán v o n th ng xác nh các i m d a vào h s góc c a phương trình ư ng th ng y = m.x + b. Trong ó, m = ∆y/∆x, ∆y = yi+1 - yi , ∆x = xi+1 - xi. Nh n th y trong hình v 2.1 thì t a c a i mx s tăng 1 ơn v trên m i i m v , còn vi c quy t nh ch n yi là yi + 1 hay yi s ph thu c vào giá tr sau khi làm tròn c a tung y. Tuy nhiên, n u tính tr c ti p giá tr th c c a y m i bư c t phương trình y = m.x + b thì c n m t phép toán nhân và m t phép toán c ng s th c: yi+1 = m.xi+1 + b = m(xi + 1) + b = m.xi + b + m t i ưu t c , ngư i ta kh phép nhân trên s th c. Ta có : yi = m.xi + b ⇒ yi+1 = yi + m • Tóm l i, khi 0 < m ≤ 1thì: xi+1 = xi + 1 yi+1 = yi + m • Trư ng h p m > 1: ch n bư c tăng trên tr c y m t ơn v . xi+1 = xi + yi+1 = yi + 1 Hai trư ng h p này dùng v m t i mb t u t bên trái n i m cu i cùng bên ph i c a ư ng th ng (xem hình 2.2). N u i m b t u t bên ph i n i m cu i cùng bên trái thì xét ngư c l i : • 0 < m ≤ 1: xi+1= xi – 1 Giáo trình H a Máy Tính 12
  13. yi+1:= yi - m • m > 1: xi+1 = xi – yi+1 = yi – 1 Hình 2.2 : Hai trư ng h p m >1 và 0 < m < 1 Cài t minh h a thu t toán DDA void DDALine(int x0, int y0, int x1, int y1) { int x; float dx, dy, y, m; dx:= x1 – x0; dy:= y1 – y0; m:= dy/dx; y = y0; for (x=x0; x
  14. y = y+m } } Tương t , ta có th tính toán các i m v cho trư ng h p m < 0, |m| ≤ 1 ho c |m| > 1. 2.1.2 Thu t toán Bresenham o n th ng có 0 ≤ m ≤ 1. Hình 2.3 : Thu t toán Bresenham v G i (xi +1, yi +1) là i m thu c o n th ng (xem hình 2.3). Ta có y = m(xi +1) + b. t d1 = yi +1 - yi ; d2 = (yi +1) - yi +1 Vi c ch n i m (xi +1, yi +1) là P1 hay P2 ph thu c vào vi c so sánh d1 và d2 hay d u c a d1 - d2 : • N u d1 - d2 < 0 : ch n i m P1, t c là yi +1 = yi • N u d1 - d2 ≥ 0 : ch n i m P2, t c là yi +1 = yi +1 Xét Pi = ∆x(d1 - d2) Ta có : d1 - d2 = 2yi+1 - 2yi - 1 = 2m(xi+1) + 2b - 2yi - 1 Giáo trình H a Máy Tính 14
  15. Pi = ∆x(d1 - d2) = ∆x[2m(xi+1) + 2b - 2yi - 1] ⇒ = ∆x[2(∆y/∆x)(xi+1) + 2b - 2yi - 1] = 2∆y(xi+1) - 2∆x.yi + ∆x(2b - 1) = 2∆y.xi - 2∆x.yi + 2∆y + ∆x(2.b - 1) V y C = 2∆y + ∆x(2b - 1) = Const (h ng s ) ⇒ Pi = 2∆y.xi - 2∆x.yi + C Nh n xét r ng n u t i bư c th i ta xác nh ư c d u c a Pi thì xem như ta xác n h ư c i m c n ch n bư c (i + 1). Ta có : Pi +1 - Pi = (2∆y.xi+1 – 2∆x.yi+1 + C) - (2∆y.xi - 2∆x.yi + C ) ⇔ Pi +1 = Pi + 2∆y – 2∆x( yi+1 - yi ) - N u Pi < 0 : ch n i m P1, t c là yi +1= yi và Pi +1 = Pi + 2∆y. - N u Pi ≥ 0 : ch n i m P2, t c là yi +1= yi +1 và Pi +1 = Pi + 2∆y – 2∆x - Giá tr P0 ư c tính t i mv u tiên (x0, y0) theo công th c : P0 = 2∆y.x0 – 2∆x.y0 + C Do (x0, y0) là i m nguyên thu c v o n th ng nên ta có : y0 = 2m.x0 + b = x0 + b Th vào phương trình trên ta ư c : P0 = 2 ∆ y – ∆ x Cài t minh h a thu t toán Bresenham void Bresenham_Line (int x1,int y1,int x2,int y2) Giáo trình H a Máy Tính 15
  16. { int dx, dy, x, y, P, incre1, incre2; dx = x2 - x1; dy = y2 - y1; P = 2*dy - dx; incre1 = 2*dy ; incre2 = 2*(dy - dx) ; x= x1; y=y1; glVertex2i(x, y); while (x < x2 ) { x = x +1 ; if (P < 0) P = P + incre1 else { y = y+1 ; P = P + incre2 } glVertex2i(x, y); } } Giáo trình H a Máy Tính 16
  17. Nh n xét - Thu t toán Bresenham ch thao tác trên s nguyên và ch tính toán trên phép c ng và phép nhân 2. i u này là m t c i ti n làm tăng t c áng k so v i thu t toán DDA. - Ý tư ng chính c a thu t toán này là ch xét d u Pi quy t nh i m k ti p, và s d ng công th c truy h i Pi +1 - Pi tính Pi b ng các phép toán ơn gi n trên s nguyên. - Tuy nhiên, vi c xây d ng trư ng h p t ng quát cho thu t toán Bresenham có ph c t p hơn thu t toán DDA. 2.1.3 Thu t toán MidPoint Pitteway công b thu t toán MidPoint vào 1967, Van Aken c i ti n 1984. Xét h s góc thu c [0, 1]. Gi thi t r ng ã ch n P v , xác nh pixel ti p theo s là t i N hay NE (xem hình 2.4). Giao c a ư ng th ng v i Xp+1 t i Q, M là trung i m c a NE v à E. Hình 2.4: Thu t toán MidPoint v o n th ng Ý tư ng c a thu t toán MidPoint là xét i m M xem n m phía nào c a ư ng th ng, n u M n m phía trên ư ng th ng thì ch n E (t c là ư ng th ng g n v i E hơn NE), ngư c l i ch n NE. Vì v y, ta c n xác nh v trí tương i c a M s o v i ư ng th ng ch a o n th ng c n v . • Phân tích thu t toán v o n th ng d a trên phương trình d ng t ng quát c a Giáo trình H a Máy Tính 17
  18. ư ng th ng ch a o n th ng: F(x, y)= a.x + b.y + c Ta có: Suy ra d ng t ng quát: . Hay tương ương: . T ó, ta có các h s c a phương trình d ng t ng quát là : a = dy, b = - dx, c = B.dx • Giá tr hàm t i M: F(M)=F(xp + 1, yp + ) = d o N u d > 0, M n m dư i ư ng th ng thì ch n NE. o N u d < 0, M n m phía trên thì ch n E. o N u d = 0, ch n E hay NE tùy ý. • Giá tr c a hàm t i M c a c a i m ti p theo s v o G i giá tr d v a tính là: o G i s v a c h n E: là s gia c a i m ti p theo. o Gi s v a ch n NE: là s gia c a i m ti p theo. Tính giá tr kh i u c a d t i các trung i m Giáo trình H a Máy Tính 18
  19. o Gi s v o n th ng t (x0, y0) n (x1, y1), t ó trung i m th nh t có ta (x0 + 1, y0 + ). Suy ra: o F(x0, y0) = 0 dstart = a + = dy – o Tránh s th p phân c a dstart, nh nghĩa l i hàm như sau: F(x, y)=2(a.x + b.y + c) o Do v y, ta có: dstart = 2dy - dx; E = 2dy; NE = 2(dy - dx) Cài t minh h a thu t toán MidPoint void MidPoint_Line(int x0, int y0, int x1, int y1, int color) { int dx, dy, x, y, d, incrE, incrNE ; dx = x1 – x0; dy = y1 – y0; d = 2*dy - dx; incrE = 2*dy; incrNE = 2*(dy - dx); x = x0; y =y0; Giáo trình H a Máy Tính 19
  20. glVertex2i(x, y); while (x
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2