Bài giảng môn học Đồ họa máy tính - Trường Đại học Hàng Hải Việt Nam

Nội dung text: Bài giảng môn học Đồ họa máy tính - Trường Đại học Hàng Hải Việt Nam

1. Tr
   ng H Hàng Hi Vit Nam Khoa Công ngh thông tin = = =&*&= = = Bài ging môn hc  HA MÁY TÍNH
2. Li nói u Nh
   m phc v cho công tác ging dy, hc tp môn hc  ha máy tính c a th y và trò khoa Công ngh thông tin - tr ng H HÀNG HI VIT NAM, b môn H thông thông tin tin hành tng hp, biên son s b tp bài ging môn hc  ha máy tính. Tp bài ging này c biên son ch yu da trên Giáo trình K thut  ha máy tính c a khoa CNTT - HBK Hà Ni và Giáo trình  ha máy tính (dùng cho h ào to t xa) c a HQG TP H Chí Minh. Ngoài ra chúng tôi có tham kho cun Computer Graphics c a Donald Hearn & M. Pauline Baker, nhà xut bn Prentice-Hall, New Jersey, 1986 cùng mt s tài liu khác (xem ph n tài liu tham kho).  hc tt môn hc này, ngoài nhng kin thc c s v lp trình, sinh viên c n phi c trang b nhng kin thc c bn v i s, gii tích, hình hc gii tích, hình hc ha hình, kin trúc máy tính và thit b ngoi vi, Thc s  ha máy tính là mt môn hc không n gin, s! dng nhiu công c toán hc và òi h"i kin thc tng hp. Vì ây là l n  u tiên biên son nên ch#c ch#n không tránh kh"i nhng thiu sót. Rt mong nhn c s óng góp ý kin c a quý ng nghip và c a các em sinh viên  công vic biên son ngày càng tt hn. B môn H thng thông tin Khoa Công ngh thông tin - Tr ng H Hàng Hi 2
3. M c l c M c l c 3 Ch
   ng 1: Tng quan v  ha máy tính 5 1.1 Khái ni
   m v  ha máy tính và lch s phát trin 5 1.2 K thu t  ha t ng tác(Interactive Computer Graphics) 6 1.3 Khái quát v h
   th ng  ha 7 1.3.1 Ph n cng 8 1.3.2. Ph n mm 11 1.4 Các h
   màu c bn 13 1.4.1 Không gian RGB (RGB space) 14 1.4.2 Không gian HSL 15 1.4.3 Không gian HSV 16 1.4.4 Không gian màu CMY (Cyan - Magenta - Yellow) 17 Ch
   ng 2: Các thut toán v
   ng và tô màu c bn 19 2.1 H
   ta  th gii thc, h
   ta  thit b và h
   ta  chun 19 2.1.1 H ta  th gi$i thc 19 2.1.3 H ta  thit b chu%n (Normalized device coordinates) 20 2.2 Các thu t toán v ng da trên im 21 2.2.1 Các thut toán v&  ng th'ng 21 2.2.2 Các thut toán v&  ng tròn 27 2.3 Các thu t toán tô màu 33 2.3.1 Tô màu theo tng im (phng pháp tô n gin) 33 2.3.2 Tô màu theo dòng quét (scan - line) 37 2.3.3 Phng pháp tô màu da theo  ng biên 41 Ch
   ng 3: Các phép bin i hình hc 2D 45 3.1 Các phép bin i hình hc c s 45 3.1.1 Phép t nh tin 45 3.1.2 Phép bin i t( l 46 3.1.3 Phép quay 47 3.1.4 Biu di)n ma trn c a phép bin i 47 3.1.5 H ta  thu n nht (hormogeneous coordinates) 48 3.2 Kt hp các phép bin i 49 3.2.1 Kt hp các phép t nh tin 49 3.2.2 Kt hp các phép t( l 50 3.2.3 Kt hp các phép quay 50 3.2.4 Phép quay có tâm quay là im bt k* 50 3.3 Mt s tính cht ca phép bin i Affine 51 3.3.1 Phép bin i affine bo toàn  ng th'ng 51 3.3.2 Tính song song c a các  ng th'ng c bo toàn 51 3.3.3 Tính t+ l v khong cách c bo toàn 51 3.4 Mt s phép bin i khác 52 3
4. 3.4.1 Phép i xng 52 3.4.2 Phép bin dng 52 3.4.3 Phép bin i ngc 53 3.4.4 Phân rã phép bin i 53 3.5 Phép bin i gia các h
   ta  54 Ch
   ng 4: Hin th các i t
   ng 2D 56 4.1 Quy trình hin th các  i tng 2D 56 4.1.1 Mt s khái nim 56 4.1.2 H ta  quan sát và h ta  thit b chu%n 58 4.1.3 Chuyn i t c!a s quan sát sang vùng quan sát 59 4.2 Các thu t toán ct xén hình 60 4.2.1 Thut toán Cohen - Sutherland 61 4.2.2 Thut toán Liang - Barsky 66 Ch
   ng 5: Tng quan v  ha 3D 71 5.1 Khái quát chung 71 5.1.1 S lc v quy trình hin th 72 5.1.2 Mô hình khung ni kt 73 5.1.3 V& các i tng theo mô hình khung ni kt s! dng các phép chiu 75 5.1.4 Phép chiu song song (Parallel Projection) 76 5.1.5 Phép chiu phi cnh (Perspective Projection) 78 5.2 Biu din các  i tng 3D 79 5.2.1 Biu di)n m,t a giác 80 5.2.2 Các  ng cong và m,t cong 85 5.2.3 Các m,t có quy lut(ruled surfaces) 85 5.2.4 Các m,t tròn xoay (Surfaces of revolution) 87 5.2.5 Các m,t cong bc hai 88 Ch
   ng 6: Các phép bin i trong  ha 3D 90 6.1 Các phép bin i hình hc 90 6.1.1. Mt s khái nim liên quan 91 6.1.2 Phép t nh tin 92 6.1.3 Phép t( l 93 6.1.4 Phép bin dng 94 6.1.5 Phép quay 94 6.1.6 Kt hp các phép bin i Affine 3 chiu 98 6.2 Phép bin i mô hình và phép bin i h
   trc ta  98 Tài li
   u tham kho 100 4
5. Chng 1 Tng quan v  ha máy tính 1.1 Khái nim v  ha máy tính và lch s phát trin K thut  ha máy tính là phng pháp và công ngh dùng trong vic chuyn i qua li gia d liu và hình nh trên màn hình b
   ng máy tính. K thut  ha hay  ha máy tính còn c hiu d$i dng phng pháp và k thut to hình nh t các mô hình toán hc mô t các i tng hay d liu ly c t các i tng trong thc t. Mt s chuyên gia máy tính cho r
   ng K thut  ha máy tính có th  nh ngh-a nh mt l-nh vc c a công ngh thông tin mà  ó nghiên cu, xây dng và tp hp các công c (mô hình lý thuyt và các th vin lp trình) khác nhau  kin to, xây dng, lu tr và x! lý các mô hình(model) và hình nh(image) c a các i tng, s vt khác nhau trong cuc sng, sn xut và nghiên cu. Các mô hình và hình nh này có th là kt qu thu c t nhng l-nh vc khác nhau c a rt nhiu ngành khoa hc - k thut ( Vt lý, toán hc, thiên v.n hc, c khí, kin trúc ) và bao trùm rt nhiu th loi a dng và phong phú: cu trúc phân t!, cu trúc sinh hc, mô hình tàu v/ tr, Thut ng k thut  ha máy tính (Computer Graphics) c  xut bi mt chuyên gia ng i M tên là William Fetter vào n.m 1960. Khi ó ông ang nghiên cu xây dng mô hình bung lái máy bay cho hãng máy bay Boeing. William Fetter ã da trên các hình nh 3D c a mô hình ng i phi công trong bung lái  xây dng nên mt mô hình ti u cho máy bay Boeing. ây là phng pháp nghiên cu rt m$i vào th i k* ó. Phng pháp này có nhng tính n.ng vt tri hn tt c các phng pháp nghiên cu xây dng mô hình bung lái máy bay truyn thng tr$c ó c áp dng ti Boeing. Phng pháp này cho phép các k s thit k quan sát mt cách trc quan v trí c a phi công trong bung lái. William Fetter ã ,t tên cho phng pháp c a mình là "Computer Graphics". L ch s!  ha t nhng n.m 1960 còn c ánh du bi d án Sketchpad ti MIT v$i Ivan Sutherland ti hi ngh Fall Joint Computer cùng v$i s kin l n  u tiên to m$i, hin th và thay i c d liu hình nh trc tip trên màn hình trong th i gian thc (hình 1.1) 5
6. Hình 1.1: Hình nh  ha tng tác  u tiên trên Sketchpad K thut  ha liên tc c hoàn thin vào nhng n.m 1970 v$i s xut hin c a các chu%n  ha làm t.ng c ng kh n.ng giao tip và tái s! dng c a các ph n mm c/ng nh các th vin  ha. S phát trin bùng n c a công ngh vi in t! và l-nh vc ph n cng máy tính trong nhng n.m 1980 làm xut hin hàng lot các v+ mch h0 tr cho vic truy xut  ha i cùng v$i s gim giá áng k c a máy tính cá nhân (PC) ã làm  ha càng i sâu vào cuc sng thc ti)n. K t n.m 1990 t$i nay các k thut  ha 3D và các phép x! lý c phát trin mnh m& và cho ra  i hàng lot các nhng sn ph%m  ha ng dng trong thc t nh thit k mô hình, games, phim hot hình, k xo in nh, Các v+ mch  ha cho máy tính cá nhân thng tr trong thi tr ng  ha nh: Nvidia, ATi, 3DLabs, ngày càng hoàn thin và cung cp ngày càng nhiu kh n.ng cho ng i s! dng. Liên tip hàng t( ô la c  u t cho  ha máy tính ha h1n s phát trin không ngng và nhng sn ph%m ngày càng c ci tin s& là quà t,ng mong i cho nhng ai yêu thích l-nh vc này. 1.2 K thut  ha t
   ng tác(Interactive Computer Graphics) C/ng nh mi l-nh vc khác trong công ngh thông tin, mt h thng s! dng k thut  ha tng tác là mt h thng x! lý thông tin bao gm 3 thành ph n v$i các thao tác tng ng: • Nhp d liu: thông qua các thit b vào nh nh chut, máy quét, bàn phím, • X! lý và lu tr d liu • Hin th /Kt xut kt qu: thông qua các thit b nh màn hình, máy in, Ngoài các ,c thù chung nh ã lit kê  trên, h thng k thut  ha tng tác còn có mt ,c im rt ,c trng c a mình: trong h thng này, các thông tin và các d liu ,c trng c hin th trên màn hình mt cách trc quan và ng i s! dng có th quan sát, theo dõi và thay i giá tr ho,c khuôn dng c a chúng mt cách tng tác (interactive) và ngay lp tc nhng thay i này s& c h thng ghi nhn và x! lý. Kt qu c a s thay i s& c h thng x! lý ngay trên các mô hình, cu trúc ho,c hình nh c a các i tng và hin th chúng ngay trên màn hình nh ng i s! dng mong mun. 6
7. Nhp/vào Lu tr và Hin th  !   d li u x lý k t qu USER Hình 1.2: Mô hình chung c a h  ha tng tác Nh trên mô hình chung c a mt h thng s! dng k thut  ha tng tác, chúng ta thy ng i s! dng có kh n.ng giao tip tng tác v$i h thng  c 3 giai on trong quá trình x! lý thông tin. H thng  ha tng tác  u tiên c thit k và xây dng bi IvanSutherland n.m 1963. H thng Sketchpad này c dùng  thit k mch in và bao gm nhng thành ph n sau: • CRT màn hình. • Bút sáng và mt keyboard bao gm 1 s phím bm chc n.ng • Máy tính cha chng trình x! lý các thông tin Ng i s! dng có th v& mch in trc tip lên màn hình thông qua bút sáng. chng trình s& phân tích và tính toán nhng thông s c n thit c a mch in do ng i s! dng v& nên. Hình 1.3: Ivan Sutherland và h thng Sketchpad (1962) 1.3 Khái quát v h thng  ha Mt h  ha bao gi c/ng có hai thành ph n chính ó là ph n cng và ph n mm. Ph n cng bao gm các thit b hin th và nhp d liu, Ph n mm bao gm các công c lp trình và các trình ng dng  ha. Chúng ta s& l n lt kho sát các thành ph n này. 7
8. 1.3.1 Phn cng 1.3.1.1 Thit b hin th Nói chung, màn hình là thit b hin th thông dng nht trong mt h  ha. Các thao tác c a h u ht màn hình u da trên thit k c a ng tia âm cc (CRT – cathode ray tube). A. Cu to chung c a CRT Hình 1.6 minh ha thao tác c s c a mt ng tia âm cc. Mt chùm các tia in t! (tia âm cc) phát ra t mt súng in t!, vt qua các h thng hi t (focusing) và d2n h$ng (deflection) s& h$ng t$i các v trí xác  nh trên màn hình c ph mt l$p phosphor. Ti m0i v trí tng tác v$i tia in t!, ht phosphor s& phát ra mt chm sáng nh". Vì ánh sáng phát ra bi các ht phosphor m d n rt nhanh nên c n phi có mt cách nào ó  duy trì nh trên màn hình. Mt trong các cách ó là l,p i l,p li nhiu l n vic v& li nh tht nhanh b
   ng cách h$ng các tia in t! tr li v trí c/. Kiu hin th này gi là refresh CRT. Hình 1.4: Cu to c a CRT Có nhiu loi phosphor c dùng trong mt CRT. Ngoài màu s#c ra, im khác nhau chính gia các loi phosphor là " bn” (persistent), ó là khong th i gian phát sáng sau khi tia CRT không còn tác ng. L$p phosphor có  bn thp c n tc  làm ti cao hn  gi cho hình nh trên màn hình kh"i nhòe. Loi này th ng rt tt cho hot hình, rt c n thay i hình nh liên tc. L$p phosphor có  bn cao th ng c dùng cho vic hin th các nh t-nh,  phc tp cao. M,c dù mt s loi phosphor có  bn l$n hn 1 giây, tuy nhiên các màn hình  ha th ng c xây dng v$i  bn dao ng t 10 n 60 micro giây. S lng ti a các im có th hin th trên mt CRT c gi là  phân gii (resolution). Mt  nh ngh-a chính xác hn c a  phân gii là s lng các im trên mt centimet mà có th c v& theo chiu ngang và chiu dc, m,c dù nó th ng c xem nh là tng s im theo m0i h$ng. Kích th$c vt lí c a màn hình  ha c tính t  dài c a  ng chéo màn hình, th ng dao ng t 12 n 27 inch ho,c l$n hn. Mt màn hình CRT có th c kt hp v$i nhiu loi máy khác nhau, do ó s lng các im trên màn hình có th c v& tht s còn tùy thuc vào kh n.ng c a h thng mà nó kt hp vào. 8
9. Mt thuc tính khác c a màn hình na là t+ s phng (aspect ratio). T+ s phng là t+ l c a các im dc và các im ngang c n  phát sinh các on th'ng có  dài n v theo c hai h$ng trên màn hình (trong mt s tr ng hp ng i ta th ng dùng t+ s phng nh là t+ s c a các im theo chiu ngang so v$i các im theo chiu dc). V$i các màn hình có t+ s phng khác 1, d) dàng nhn thy là các hình vuông hin th trên nó s& có dng hình ch nht, các hình tròn s& có dng hình ellipse. Thc ra khái nim t+ s phng xut phát t bn cht khong cách (nu tính cùng mt n v  dài) gia các im dc không b
   ng khong cách gia các im ngang. Mt t+ s phng có giá tr ¾ có ngh-a là v& 3 im theo chiu dc s& có cùng  dài v$i vic v& 4 im theo chiu ngang. B. Màn hình dng im (raster - scan display) Màn hình dng im là dng th ng g,p nht trong s các dng màn hình s! dng CRT da trên công ngh truyn hình. Trong h thng này, chùm tia in t! s& c quét ngang qua màn hình, m0i l n mt dòng và quét tu n t t trên xung d$i. S bt t#t c a các im sáng trên màn hình ph thuc vào c ng  c a tia in t! và ây chính là c s c a vic to ra hình nh trên màn hình. M0i im trên màn hình c gi là mt pixel hay là pel (vit t#t c a picture element). Các thông tin v hình nh hin th trên màn hình c lu tr trong mt vùng b nh$ gi là vùng m làm ti (refresh buffer) hay là vùng m khung (frame buffer). Vùng b nh$ này lu tr tp các giá tr c ng  sáng c a toàn b các im trên màn hình và luôn luôn tn ti mt song ánh gia m0i im trên màn hình và m0i ph n t! trong vùng này. Hình 1.5: Quá trình to hình nh c a các tia quét  thay i các hình nh c n hin th , các giá tr tng ng v$i v trí và  sáng phi c ,t vào vùng m khung. Hình 1.8 minh ha các giá tr tng ng trong vùng m khung  hin th hình nh c a ch A trên màn hình. i v$i màn hình en tr#ng, vùng m khung còn c gi là bitmap, v$i các màn hình khác vùng m khung th ng c gi là pixmap. 9
10.  to ra các nh en tr#ng, n gin ch+ c n lu thông tin c a m0i pixel b
    ng 1 bit (các giá tr 0, 1 s& tng trng cho vic t#t (ti), bt (sáng) pixel trên màn hình). Trong tr ng hp nh nhiu màu, ng i ta c n nhiu bit hn, nu thông tin c a m0i pixel c lu b
    ng b bit, thì ta có th có 2b giá tr màu phân bit cho pixel ó. Hình 1.6: Song ánh gia vùng m khung và màn hình Trong các màn hình màu, ng i ta  nh ngh-a tp các màu làm vic trong mt bng tra (LookUp Table - LUT). M0i ph n t! c a LUT  nh ngh-a mt b ba giá tr R (Red), G (Green), B (Blue) mô t mt màu nào ó. Khi c n s! dng mt màu, ta ch+ c n ch+  nh s th t (index) tng ng c a màu ó trong LUT. Bng LUT có th c thay i bi các ng dng và ng i lp trình có th can thip iu khin. V$i cách làm này chúng ta có th tit kim không gian lu tr cho m0i ph n t! trong vùng m khung. S ph n t! c a LUT c xác  nh t s lng các bits/pixel. Nu m0i ph n t! c a vùng m khung dùng b bits  lu thông tin c a mt pixel, thì bng LUT có 2b ph n t!. Nu b=8, LUT s& có 28=256 ph n t!, ó chính là s màu có th c hin th cùng mt lúc trên màn hình. Vic làm ti trên màn hình dng này c thc hin  tc  60 n 80 frame/giây. ôi khi tc  làm ti còn c biu di)n b
    ng n v Hertz (Hz – s chu kì/ giây), trong ó mt chu kì tng ng v$i mt frame. S! dng n v này, chúng ta có th mô t tc  làm ti 60 frame/giây n gin là 60Hz. Khi t n cui m0i dòng quét, tia in t! quay tr li bên trái c a màn hình  b#t  u dòng quét k tip. Vic quay tr li phía trái màn hình sau khi làm ti m0i dòng quét c gi là tia hi ngang (horizontal retrace). Và t$i cui m0i frame, tia in t! (tia hi dc – vertical retrace) quay tr li góc trên bên trái c a màn hình  chu%n b b#t  u frame k tip. Trong mt s màn hình, m0i frame c hin th thành hai giai on s! dng k- thut làm ti an xen nhau (interlaced refesh). 3 giai on  u tiên, tia quét s& quét mt s dòng t trên xung d$i, sau tia hi dc, các dòng còn li s& c quét. Vic an xen các dòng quét này cho phép chúng ta thy c toàn màn hình hin th ch+ trong mt n!a th i gian so v$i dùng  quét tt c các dòng mt l n t trên xung d$i. K- thut này th ng c dùng cho loi màn hình có tc  làm ti thp. 10
11. Hình 1.7: Hot ng c a màn hình interlaced 1.3.1.2. Các thit b nhp Hai loi thit b nhp c bn nht trong máy tính v2n là chut và bàn phím. A. Bàn phím : Xut hin trong h u ht các máy tính, nó là thit b  nhp d liu dng v.n bn và s. ây là loi thit b quen thuc nht v$i ng i s! dng tuy có hn ch là tng tác không cao. B. Chut : Cùng v$i s xut hin c a các ng dng  ha tng tác cao, chut là thit b nhp ngày càng quen thuc v$i ng i s! dng. Ng i ta dùng chut  tr" và chn (point-click) các chc n.ng phù hp v$i yêu c u c a mình. B
    ng cách này, giao tip gia ng i dùng và máy tính càng ngày càng thân thin và d) dàng hn. Ngoài ra chúng ta c/ng có mt s thit b nhp khác cùng h v$i chut nh track ball, 1.3.2. Phn m m Ph n mm  ha có th phân thành 2 loi : các công c lp trình và các trình ng dng  ha phc v cho mt mc ích nào ó. Các công c lp trình cung cp mt tp các hàm  ha có th c dùng trong các ngôn ng lp trình cp cao nh C, Pascal, Ví d nh các th vin  ha c a các ngôn ng nh C, Pascal hay GL (Graphics Library) c a Silicon Graphics. Các hàm c s c a nó bao gm vic to các i tng c s c a hình nh nh on th'ng, a giác,  ng tròn, , thay i màu s#c, chn khung nhìn, áp dng các phép bin i, Trong khi ó, các ng dng  ha c thit k cho nhng ng i dùng không phi là lp trình viên, cho phép ng i dùng to các i tng, hình nh, mà không c n quan tâm t$i vic chúng c to ra nh th nào. Ví d nh là Photoshop, AutoCAD, • Biu din ta Thông th ng các h  ha s! dng h ta  Descartes  mô t i tng. Nu các ta  c a i tng c mô t trong các h ta  khác nh ta  c u, , chúng phi c chuyn v ta  Descartes tr$c khi dùng. • Quy trình hin th i tng Tr$c tiên chúng ta mô t các i tng thành ph n c a mt nh phc tp trong các h ta  riêng  thun tin cho vic biu di)n ta  c a chúng. Các h ta  này c gi là h ta  mô hình (modeling coordinates) hay còn gi là h ta  cc b (local coordinates). Mt khi các i tng thành ph n c biu di)n xong, chúng ta s& ,t chúng vào các v trí tng ng trong nh s! dng h ta  th gi$i thc (world coordinates). Sau cùng, các mô t c a nh trong h ta  th gi$i thc s& c chuyn n mt ho,c nhiu h ta  khác 11
12. nhau c a thit b hin th , tùy vào chúng ta mun hin th trên thit b nào. Các h ta  này còn c gi là h ta  thit b (device coordinates). Các mô t trong các h ta  cc b và h ta  th gi$i thc cho phép chúng ta s! dng th nguyên thích hp cho các n v o mà không phi b ràng buc gì c a tng thit b hin th c th. Hình 1.8: Quy trình hin th i tng Thông th ng, các h  ha chuyn các mô t trong h ta  th gi$i thc t$i h ta  thit b chu%n (normalized device coordinates) có các chiu là n v tr$c khi chuyn t$i h ta  thit b . iu này làm cho h thng c lp v$i nhiu loi thit b khác nhau. • Các hàm  ha Các hàm  ha cung cp kh n.ng to và thao tác hình nh. Các hàm này c phân loi nh sau : -Tp các công c to ra các i tng  ha c s nh im, on th'ng,  ng cong, vùng tô, kí t, -Tp các công c thay i thuc tính dùng  thay i thuc tính c a các i tng  ha c s nh màu s#c, kiu  ng, kiu ch, m2u tô, -Tp các công c thc hin các phép bin i hình hc dùng  thay i kích th$c v trí, h$ng c a các i tng, -Tp các công c bin i h quan sát dùng  xác  nh v trí quan sát i tng và v trí trên thit b hin th c dùng  hin th i tng. -Tp các công c nhp liu : Các ng dng  ha có th s! dng nhiu loi thit b nhp khác nhau nh bút v&, bng, chut, bàn phím,  iu khin và x! lí dòng d liu nhp. 12
13. Cui cùng là tp các công c cha các thao tác dùng cho vic qun lí và iu khin ví d nh xóa toàn b màn hình, thit lp ch   ha, • Các chun phn m m Mc tiêu c.n bn c a các ph n mm  ha c chu%n là tính tng thích. Khi các công c c thit k v$i các hàm  ha chu%n, ph n mm có th c di chuyn mt cách d) dàng t h ph n cng này sang h ph n cng khác và c dùng trong nhiu cài ,t và ng dng khác nhau. Sau nhng n0 lc không nh" c a các t chc chu%n hóa c a các quc gia và quc t, mt chu%n cho vic phát trin các ph n mm  ha ã ra  i ó là GKS (Graphics Kernel System – H  ha c s). H thng này ban  u c thit k cho tp các công c  ha hai chiu, sau ó c phát trin và m rng cho  ha ba chiu. Các hàm c a GKS thc s ch+ là các mô t tru tng, c lp v$i bt kì ngôn ng lp trình nào.  cài ,t mt chu%n  ha cho ngôn ng c th nào, các cú pháp tng ng s& c xác  nh và c th hóa. M,c dù GKS xác lp c các ý tng ban  u cho các hàm  ha c s, tuy nhiên nó không cung cp mt cách thc chu%n cho vic giao tip  ha v$i các thit b xut. Nó c/ng không xác  nh các cách thc cho các mô hình th i gian thc c/ng nh các cách thc lu tr và chuyn i hình nh. Các chu%n cho các cách thc này c xây dng riêng, c th là : Các chu%n cho các cách thc giao tip thit b c cho bi h CGI (Computer Graphics Interface System), h CGM (Computer Graphics Metafile) xác  nh các chu%n cho vic lu tr và chuyn i hình nh, và h PHIGS (Programmer’s Hierarchical Interactive Graphics Standard) xác  nh các cách thc chu%n cho các mô hình th i gian thc và các kh n.ng lp trình  mc  cao hn mà cha c quan tâm t$i trong GKS. 1.4 Các h màu c bn Vic nghiên cu màu s#c bao gm nhiu l-nh vc nh: quang hc, sinh lí hc, tâm lí hc và các nhân t khác thuc v con ng i. Vì th, có rt nhiu quan nim c/ng nh các thành ng v khoa hc các màu s#c. i v$i nhng ng i làm tin hc, vn  mà h quan tâm là mi tng tác qua li gia s cm nhn màu s#c c a con ng i v$i các b phn ph n cng hin th màu s#c c a màn hình máy tính, và v$i các ph n mm thit k trên nó. 13
14. Bng d$i ây s& trình bày mi quan h này : S cm nhn c im ph n cng c im ph n ca con ng
    i mm Màu s#c Các màu hin th gc Thut toán trên không gian màu S#c  màu B$c sóng (Hue) (WaveLength)  bão hòa S thu n nht c a màu (Saturation)  sáng hay  C ng  sáng Hiu ch+nh gamma chói S "rung" c a Tc  làm ti (refresh) màn hình Không gian màu (color space) do ó c a ra   nh các màu hin th trên máy tính bi vì chúng làm n gin hóa các thao tác tính toán c n thit cho vic chuyn i màu s#c (color transformation). Không gian màu có th c thit k ho,c là da trên c s c a b phát sinh màu c a ph n cng (hardware color generation) (ví d nh không gian RGB) ho,c là da trên s cm nhn màu s#c c a m#t (nh không gian HSL). V$i mt ng dng, vic chn không gian màu nào  s! dng tùy thuc vào mt s nhân t sau :  chính xác mà các nhà thit k c n kim soát màu s#c (color control); yêu c u v s tng tác gia các màu s#c và tc  các tính toán cho ng dng ó. 1.4.1 Không gian RGB (RGB space) Không gian RGB mô t màu s#c b
    ng ba thành ph n Red, Green, Blue. Không gian này c minh ha b
    ng mt khi lp phng v$i các trc chính RED(R), GREEN(G), BLUE(B). M0i màu trong không gian RGB u c biu di)n nh là mt vector thông qua ba vector c s là Red, Green, Blue. Do ó, ng v$i các t hp khác nhau c a ba màu này s& cho ta mt màu m$i. 14
15. Hình 1.9: Mô hình không gian RGB Trong hình lp phng m0i màu gc (Red, Green, Blue) c ,t vào góc i din v$i các màu bù nó. (Hai màu bù nhau là hai màu mà khi kt hp to thành màu tr#ng hay xám (grey)). Nh vy Red i din v$i Cyan, Green i din v$i Magenta, Blue i din v$i Yellow. Giá tr xám n
    m trên  ng chéo ni các +nh (0,0,0);(1,1,1) c a hình lp phng. Th ng th ng các trc R, G, B c chu%n hóa. Khi kt hp hai màu li v$i nhau thì màu sinh ra có vector b
    ng tng các vector thành ph n. • Mt s thu n li khi dùng không gian RGB : - Không gian RGB là chu%n công nghip cho các thao tác  ha máy tính. Các thao tác màu s#c có th c tính toán trên các không gian màu khác nhng cui cùng c n phi chuyn v không gian RGB  có th hin th trên màn hình (do thit k c a ph n cng da trên mô hình RGB). - Có th chuyn i qua li gia không gian RGB v$i các không gian màu khác nh CIE, CMY, HSL, HSV, - Các thao tác tính toán trên không gian RGB th ng n gin hn. • Mt s bt li : - Các giá tr RGB c a mt màu là khác nhau i v$i các màn hình khác nhau : Ngh-a là các giá tr RGB c a màu tiùm trên màn hình màu này s& không sinh ra úng màu ó trên mt màn hình khác. - S mô t các màu trong th gi$i thc i v$i không gian RGB còn nhiu hn ch bi vì không gian RGB không hoàn toàn phù hp v$i s cm nhn màu s#c c a con ng i. Hai im phân bit trong không gian RGB, v$i m#t ng i có th ho,c không th là th hin c a hai màu khác nhau. Chính vì iu này mà không gian RGB không th ánh x trc tip n bt c chiu cm nhn nào khác (nh hue, saturation, lightness) ngoài hue (s#c ). 1.4.2 Không gian HSL Không gian này có chú trng hn không gian RGB n các thành ph n c a s cm nhn màu s#c c a m#t (Hue, Saturation, Lightness). Tuy nhiên, không 15
16. gian HSL thc ra c/ng ch+ là mt phép bin i g n úng c a không gian RGB mà thôi. Không ging nh các không gian màu khác xây dng trên s cm nhn màu s#c c a m#t, không gian HSL v2n còn b l thuc vào ph n cng c a CRT. Không gian HSL c biu di)n trong h ta  tr, hình minh ha là hai hình nón úp vào nhau. H (Hue) là to  ng v$i góc quay, S (Saturation) là ta  gc, L là trc th'ng ng. H u ht các màu t bão hòa khi S = 1 và L = 0.5. Hình 1.10: Mô hình không gian HSL • Mt s thu n li ca không gian HSL : - Không gian HSL g n v$i s cm nhn các thuc tính màu s#c c a con ng i hn không gian RGB (tuy cách tip cn ã n gin hóa i nhiu). Các màu c xác  nh d) dàng hn ch'ng hn do H quay quanh trc ng nên các màu bù c xác  nh mt cách d) dàng, i v$i các giá tr lightness c/ng vy. - Vic kim soát các màu c s HSL d) hn cho nhng ng i m$i làm quen v$i các chng trình  ha. • Mt s bt li : - Vic thêm vào mt vector không th thc hin n gin nh không gian RGB (ch+ thêm vào các thành ph n màu). Các thao tác lng giác khi bin i s& nh hng áng k n tc  c a chng trình. - C n phi qua hiu ch+nh gamma tr$c khi hin th (ging nh các không gian khác). 1.4.3 Không gian HSV Không gian HSV thc cht c/ng ch+ là mt s bin i khác c a không gian RGB. Không gian HSV c mô hình b
    ng hình lp phng RGB quay trên +nh Black c a nó. H (Hue) là góc quay quanh trc Values, S (Saturation) i t 0 n 1, trc V (Values) do vy tng ng v$i  ng chéo ni +nh White và Black. 16
17. Hình 1.11: Mô hình không gian HSV Theo cách này, các màu t bão hòa khi S=1 và V=1. Trong không gian HSV các màu c chu%n hóa v s các gam (gamut) màu c a thit b hin th . • Mt s thu n li ca không gian HSV : - Không gian HSV d) dàng áp ng các màu s#c c a các chng trình  ha do c xây dng da trên s b#t ch$c lut trn màu c a ng i ha s-. Ví d : Khi c n thêm màu tr#ng vào, phi ,t V=S=1 sau ó gim S t t cho t$i khi t c màu va ý; hay khi c n thêm màu en vào, iu ó có ngh-a là gim V (c ng  sáng) và c  nh S, - Do không c n s! dng các phép bin i lng giác khi mun chuyn sang không gian RGB nên không gian HSV có nhiu thun li v m,t tính toán hn so v$i không gian HSL. • Mt s bt li : - C n có các phép hiu ch+nh gamma. 1.4.4 Không gian màu CMY (Cyan - Magenta - Yellow) Tng t nh không gian màu RGB nhng 3 thành ph n chính là Cyan - Magenta - Yellow. Do ó, ta  các màu trong không gian CMY trái ngc v$i không gian RGB. Ví d : màu White có các thành ph n là (0,0,0), màu Black (1,1,1), màu Cyan (1,0,0), 17
18. Bng so sánh gia các không gian màu RGB HSL HSV Chu%n công Hình thc bin i Hình thc bin i nghip cho các khác c a không khác c a không thao tác  ha gian RGB gian RGB máy tính Liên h trc tip Liên h g n hn Liên h g n hn v$i v$i ph n cng v$i s cm nhn s cm nhn màu màu s#c c a con s#c c a con ng i ng i Là chuyn i òi h"i các phép ã n gin hóa các cui cùng cho tt bin i phc tp thao tác tính toán. c các nhu c u hin th Không th chuyn c lp thit b c lp thit b sang màn hình khác (ph thuc thit b ) Không có s Có Có tng ng 1-1 v$i cách cm nhn màu c a con ng i Mô hình là hình Mô hình là hai Mô hình là hình nón lp phng hình nón úp vào n nhau c chu%n hóa c chu%n hóa v c chu%n hóa v v 1 1 1  bão hòa t  bão hòa t  bão hòa t max max khi S =1 max khi S =1, L khi S =1, V =1 =0.5 Trn màu không Rõ ràng Rõ ràng rõ ràng 18
19. Chng 2 Các thut toán v
    ng và tô màu c bn 2.1 H
    ta th gii thc, h
    ta thit b và h
    ta chun Trong l-nh vc k thut  ha, chúng ta phi hiu c r
    ng thc cht c a  ha là làm th nào  có th mô t và bin i c các i tng trong th gi$i thc trên máy tính. Bi vì, các i tng trong th gi$i thc c mô t b
    ng ta  thc. Trong khi ó, h ta  thit b li s! dng h ta  nguyên  hin th các hình nh. ây chính là vn  c bn c n gii quyt. Ngoài ra, còn có mt khó kh.n khác na là v$i các thit b khác nhau thì có các  nh ngh-a khác nhau. Do ó, c n có mt phng pháp chuyn i tng ng gia các h ta  và i tng phi c  nh ngh-a bi các thành ph n n gin nh th nào  có th mô t g n úng v$i hình nh thc bên ngoài. Hai mô hình c bn c a ng dng  ha là da trên m2u s hóa và da trên ,c trng hình hc. Trong ng dng  ha da trên m2u s hóa thì các i tng  ha c to ra bi l$i các pixel r i rc. Các pixel này có th uc to ra b
    ng các chng trình v&, máy quét, Các pixel này mô t ta  xác  nh v trí và giá tr m2u. Thun li c a ng dng này là d dàng thay i nh b
    ng cách thay i màu s#c hay v trí c a các pixel, ho,c di chuyn vùng nh t ni này sang ni khác. Tuy nhiên, iu bt li là không th xem xét i tng t các góc nhìn khác nhau. 4ng dng  ha da trên ,c trng hình hc bao gm các i tng  ha c s nh on th'ng, a giác, Chúng c lu tr b
    ng các mô hình và các thuc tính. Ví d : on th'ng c mô hình b
    ng hai im  u và cui, có thuc tính nh màu s#c,  dày. Ng i s! dng không thao tác trc tip trên các pixel mà thao tác trên các thành ph n hình hc c a i tng. 2.1.1 H ta th gii thc Mt trong nhng h ta  thc th ng c dùng  mô t các i tng trong th gi$i thc là h ta  Descartes. V$i h ta  này, m0i im P c biu di)n b
    ng mt c,p ta  (x ,y ) v$i x , y ∈ R p p p p 19
20. y yp P( xp, yp) 0 x p x Hình 2.1: H ta  th gi$i thc . Ox : gi là trc hoành. . Oy : gi là trc tung. . x : hoành  im P. p . y : tung  im P. p 2.1.2 H
    ta thit b H ta  thit b (device coordinates) c dùng cho mt thit b xut c th nào ó, ví d nh máy in, màn hình, Trong h ta  thit b thì các im c/ng c mô t bi c,p ta  (x,y). Tuy nhiên, khác v$i h ta  thc là x, y ∈ N. iu này có ngh-a là các im trong h ta  thc c  nh ngh-a liên tc, còn các im trong h ta  thit b là r i rc. Ngoài ra, các ta  x, y c a h ta  thit b ch+ biu di)n c trong mt gi$i hn nào ó c a N. Ví d :  phân gii c a màn hình trong ch   ha là 640x480. Khi ó, x∈(0,640) và y∈(0,480) (xem hình 2.2). 0 640 x 480 y Hình 2.2: H ta  trên màn hình 2.1.3 H ta thit b chu n (Normalized device coordinates) Do cách  nh ngh-a các h ta  thit b khác nhau nên mt hình nh hin th c trên thit b này là chính xác thì cha ch#c hin th chính xác trên thít 20
21. b khác. Ng i ta xây dng mt h ta  thit b chu%n i din chung cho tt c các thit b  có th mô t các hình nh mà không ph thuc vào bt k* thit b nào. Trong h ta  chu%n, các ta  x, y s& c gán các giá tr trong on t [0,1]. Nh vy, vùng không gian c a h ta  chu%n chính là hình vuông n v có góc trái d$i (0, 0) và góc phi trên là (1, 1). Quá trình mô t các i tng thc nh sau Màn hình 
      : i t ng ha
    c nh Ta chu n hóa Ta thit b Máy in ngh"a trong ta th gii thc. Thit b khác 2.2 Các thut toán v ng da trên im 2.2.1 Các thut toán v
    ng th!ng Xét  ng th'ng có h s góc 0 0. V$i các on th'ng dng này, nu (xi, yi) là im ã c xác  nh  b$c th i thì im k tip (xi+1, yi+1)  b$c th i +1 s& là mt trong hai im sau: (xi + 1, yi) ho,c (xi + 1, yi + 1). Hình 2.3: Các im g n v$i im mun v& Vn  ,t ra là chn im v& nh th nào   ng th'ng c v& g n v$i  ng th'ng mun v& nht và t c ti u hóa v m,t tc  ? A. Thut toán DDA (Digital DifferentialAnalyzer) Là thut toán tính toán các im v& dc theo  ng th'ng da vào h s góc c a phng trình  ng th'ng y=mx+b. Trong ó, m=∆y/∆x , 5y = y - y , 5x = x - x i+1 i i+1 i 21
22. Nhn thy trong hình v& thì ta  c a im x s& t.ng 1 n v trên m0i im v&, còn vic quyt  nh chn y là y +1 hay y s& ph thuc vào giá tr sau khi i +1 i i làm tròn c a tung  y. Tuy nhiên, nu tính trc tip giá tr thc c a y  m0i b$c t phng trình y=mx+b thì c n mt phép toán nhân và mt phép toán cng s thc. y = mx + b = m(x + 1) + b = mx + b + m i +1 i +1 i i  ci thin tc , ng i ta kh! phép nhân trên s thc. Ta có : y = mx + b
    y = y + m 6 int(y ) i i i +1 i i +1 • Tóm li khi 0 1: chn b$c t.ng trên trc y mt n v . x = x + 1/m 6 int(x ) i +1 i i +1 y = y + 1 i +1 i Hai tr ng hp này dùng  v& mt im b#t  u t bên trái n im cui cùng bên phi c a  ng th'ng (xem hình 1.5). Nu im b#t  u t bên phi n im cui cùng bên trái thì xét ngc li : • 0 1: x = xi - 1/m 6 int(xi+1) i +1 y = yi - 1 i +1 Tng t, có th tính toán các im v& cho tr ng hp m 1 (sinh viên t tìm hiu thêm). Hình 2.4: Hai dng  ng th'ng có 0 1 22
23. Lu  thut toán DDA: Begin dx = x2 - x1 dy = d2 - d1 Yes abs(dx)>abs(dy) No steps=abs(dx steps=abs(dy) ) k=1 x_inc=dx/steps y_inc=dy/steps x=x1;y= y1 putpixel(x1,y1,c) No k ≤ steps Yes k=k+1 x = x+x_inc y = y+y_inc putpixel(round(x),round(y),c) End 23
24. Cài ,t minh ha thut toán DDA trên PASCAL Procedure DDA ( x1, y1, x2, y2, color : integer ); Var dx, dy, step : integer; x_inc, y_inc , x, y : real ; Begin dx:=x2-x1; dy:=y2-y1; if abs(dx)>abs(dy) then steps:=abs(dx) else steps:=abs(dy); x_inc:=dx/steps; y_inc:=dy/steps; x:=x1; y:=y1; putpixel(round(x),round(y), color); for k:=1 to steps do begin x:=x+x_inc; y:=y+y_inc; putpixel(round(x),round(y), color); end; end; B. Thut toán Bresenham Hình 2.5: Dng  ng th'ng có 0≤m≤1 Gi (x +1,y ) là im thuc on th'ng (xem hình). i i +1 Ta có y= m(x +1)+b. i 24
25. ,t d = y - y 1 i +1 i d = (y +1) - y 2 i i +1 Vic chn im (x , y ) là P1 hay P2 ph thuc vào vic so sánh d1 và d2 i +1 i +1 hay du c a d1-d2. - Nu d1-d2<0 : chn im P1, tc là y = y i +1 i - Nu d1-d2 70 : chn im P2, tc là y = y +1 i +1 i Xét P = 5x (d - d ) i 1 2 Ta có : d - d = 2 y - 2y - 1 1 2 i+1 i = 2m(x +1) + 2b - 2y - 1 i i
    P = 5x (d - d ) = 5x[2m(x +1) + 2b - 2y - 1] i 1 2 i i = 5x[2(5y/5x)(x +1) + 2b - 2y - 1] i i = 25y(x +1) - 25x.y + 5x(2b - 1) i i = 25y.x - 25x.y + 25y + 5x(2b - 1) i i Vy C = 25y + 5x(2b - 1) = Const
    P = 25y.x - 25x.y + C i i i Nhn xét r
    ng nu ti b$c th i ta xác  nh c du c a P thì xem nh ta i xác  nh c im c n chn  b$c (i+1). Ta có : P - P = (25y.x - 25x.y + C) - (25y.x - 25x.y + C ) i +1 i i+1 i+1 i i
    P = P + 25y - 25x ( y - .y ) i +1 i i+1 i - Nu P < 0 : chn im P1, tc là y = y và P = P + 25y. i i +1 i i +1 i - Nu P 7 0 : chn im P2, tc là y = y +1 và P = P + 25y - 25x i i +1 i i +1 i - Giá tr P c tính t im v&  u tiên (x ,y ) theo công thc : 0 0 0 P = 25y.x - 25x.y + C 0 0 0 Do (x ,y ) là im nguyên thuc v on th'ng nên ta có : 0 0 y = m x + b = (5y/5x).x + b 0 0 0 Th vào phng trình trên ta c : P = 25y - 5x 0 25
26. Lu  thut toán Bresenham Begin dx = x2-x1; dy = y2 - y1; P = 2dy-dx; c1 = 2dy; c2 = 2(dy-dx); x = x1; y = y1; putpixel (x,y,color); No x<x2 Yes No P<0 Yes P = P+c1 P = P + c2 y = y + 1 x=x+1 putpixel(x, y, color) End Cài ,t minh ha thut toán Bresenham trên PASCAL Procedure Bres_Line (x, y1, x2, y2 : integer); Var dx, dy, x, y, P, const1, const2 : integer; 26
27. Begin dx : = x2 - x1; dy : = y2 - y1; P : = 2*dy - dx; const1 : = 2*dy ; const2 : = 2*(dy - dx) ; x:= x1; y:=y1; Putpixel ( x, y, Color); while (x < x2) do begin x : = x +1 ; if (P < 0) then P : = P + const1 else begin y : = y+1 ; P : = P + const2; end ; putpixel (x, y, color) ; end ; End ; Nhn xét : Thut toán Bresenham ch+ thao tác trên s nguyên và ch+ tính toán trên phép cng và phép nhân 2 (phép d ch bit). iu này là mt ci tin làm t.ng tc  áng k so v$i thut toán DDA. Ý tng chính c a thut toán này là  ch xét du P  quyt  nh im k i tip, và s! dng công thc truy hi P - P  tính P b
    ng các phép toán n i +1 i i gin trên s nguyên. Tuy nhiên, vic xây dng tr ng hp tng quát cho thut toán Bresenham có phc tp hn thut toán DDA. 2.2.2 Các thut toán v
    ng tròn Trong h ta  Descartes, phng trình  ng tròn bán kính R có dng: 2 2 2 V$i tâm O(0,0) : x + y = R 2 2 2 V$i tâm C(x ,y ): (x - x ) + (y - y ) = R c c c c Trong h ta  cc thì x = x + R.cos8 c y = y + R.sin8 c v$i 8 ∈ [0, 29]. Do tính i xng c a  ng tròn C (xem hình) nên ta ch+ c n v& 1/8 cung tròn, sau ó ly i xng qua 2 trc ta  và 2  ng phân giác thì ta v& c c  ng tròn. 27
28. Hình 2.6:  ng tròn v$i các im i xng A. Thut toán n gin R 2 Cho x = 0, 1, 2, , int( ) v$i R>1. 2 - Ti m0i giá tr x, tính int(y = R 2 − x 2 ). - V& im (x,y) cùng 7 im i xng c a nó. Cài ,t minh ha thut toán n gin b
    ng PASCAL: Procedure Circle (xc, yc, R : integer) Var x, y : integer ; Procedure doi_xung 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) ; putpixel (xc + y , yc + x, color) ; putpixel (xc - y , yc + x, color) ; putpixel (xc + y , yc - x, color) ; putpixel (xc - y , yc - x, color) ; End; Begin 28
29. For x : = 0 to round(R*Sqrt(2)/2) do Begin y : = round(Sqrt(R*R-x*x)); doi_xung; End ; End ; B. Thut toán MidPoint v
    ng tròn Do tính i xng c a  ng tròn nên ta ch+ c n v& 1/8 cung tròn sau ó ly i xng là v& c c  ng tròn. Ta s& s! dng li th tc DOIXUNG  trên. Thut toán MidPoint a ra cách chn y là y hay y -1 b
    ng cách so sánh im i+1 i i thc Q(x ,y) v$i im gia MidPoind là trung im c a S1 và S2. Chn im i+1 b#t  u  v& là (0,R). Gi s! (x , y ) là im nguyên ã tìm c  b$c th i i i (xem hình), thì im (x , y )  b$c i+1 là s la chn gia S1(xi + 1, yi) và i+1 i+1 S2(xi + 1, yi - 1) Hình 2.7:  ng tròn v$i im Q(xi +1, y) và im MidPoint ,t F(x,y) = x2 + y2 - R2 , ta có : - F(x, y) 0 nu im (x, y) n
    m ngoài  ng tròn. - F(x, y) = 0 nu im (x, y) n
    m trên  ng tròn. Xét P = F(MidPoint) = F(xi +1, yi -1/2) i - Nu P = 0 : im MidPoint n
    m ngoài ho,c n
    m trên  ng tròn. Khi ó i im thc Q g n v$i im S2 hn nên ta chn y = y - 1. i+1 i M,t khác : 29
30. P - P = F(xi+1 +1, yi+1 - 1/2) - F(xi + 1, yi - 1/2) = i+1 i 2 2 2 2 2 2 [(x +1) + (y - 1/2) - R ] - [(x +1) + (y - 1/2) - R ] = i+1 i+1 i i 2 2 2x + 3 + ((yi+1) + (yi) ) - (yi+1 - yi) i Vy : - Nu P = 0 : chn y = y - 1. Khi ó P = P + 2x - 2y +5. i i+1 i i+1 i i i - Pi ng v$i im ban  u ( x , y ) = (0,R) là: 0 0 P0 = F(x0 + 1, y0 - 1/2) = F(1, R - 1/2) = 5/4 - R 30
31. Lu  thut toán MidPoint v&  ng tròn P=5/4 - R; Begin x = 0; y = R; Putpixel(x, y, c); No x < y Yes No P < 0 Yes P = P + 2*x + 3 P = P + 2*(x - y) + 5 y = y -1 x = x + 1 putpixel(x, y, color) End 31
32. Cài ,t minh ha thut toán MidPoint b
    ng PASCAL Procedure DTR(xc, yc, r, mau : integer); var x, y, p : integer ; begin x:=0 ; y:=r; p:=1 - r; while ( y > x) do begin doi_xung; if (p<0) then p:=p+2*x+3 else begin p:=p+2*(x-y)+5 ; y:=y-1; end; x:=x+1; end; end; C. Thut toán Bresenham v
    ng tròn Tng t thut toán v&  ng th'ng Bresenham, các v trí ng v$i các ta  nguyên n
    m trên  ng tròn có th tính c b
    ng cách xác  nh mt trong hai pixel g n nht v$i  ng tròn thc hn trong m0i b$c (xem hình d$i). Hình 2.8:  ng tròn v$i 2 im lân cn S1, S2 Ta có : 2 2 2 2 2 d1 = (y ) - y = (y ) - (R - (x + 1) ) i i i 2 2 2 2 2 d2 = y - (y - 1) = (R - (x + 1) ) - (y - 1) i i i P = d1 - d2 i Tính P - P i+1 i 2 2
    P = P + 4x + 6 + 2((y ) - (y ) ) - 2(y - y ) i+1 i i i+1 i i+1 i - Nu P < 0 : chn y = y . Khi ó P = P + 4x +6 i i+1 i i+1 i i 32
33. - Nu P >= 0 : chn y = y - 1. Khi ó P = P + 4(x - y ) + 10. i i+1 i i+1 i i i - P ng v$i im ban  u ( x , y ) = (0,R) là: P = 3 - 2R. 0 0 0 0 Cài ,t minh ha thut toán v&  ng tròn b
    ng gii thut Bresenham Procedure DTR_BRES(xc,yc,r,mau : integer); var x,y,p:integer; begin x:=0 ; y:=r; p:= 3 – 2*r ; while ( x<y ) do begin doi_xung; if (p<0) then p:= p + 4*x + 6 else begin p:= p + 4*(x-y) + 10 ; y:=y-1; end; x:=x+1; end; end; 2.3 Các thut toán tô màu Tô màu mt vùng là thay i màu s#c c a các im v& n
    m trong vùng c n tô. Mt vùng tô th ng c xác  nh bi mt  ng khép kín nào ó gi là  ng biên. Dng  ng biên n gin th ng g,p là a giác. Vic tô màu th ng chia làm 2 công on : . Xác  nh v trí các im c n tô màu. . Quyt  nh tô các im trên b
    ng màu nào. Công on này s& tr nên phc tp khi ta c n tô theo mt m2u tô nào ó ch không phi tô thu n mt màu. Có 3 cách tip cn chính  tô màu. ó là : tô màu theo tng im (có th gi là tô n gin), tô màu theo dòng quét và tô màu da theo  ng biên. 2.3.1 Tô màu theo t#ng im (ph
    ng pháp tô n gin) Thut toán này b#t  u t vic xác  nh mt im có thuc vùng c n tô hay không ? Nu úng là im thuc vùng c n tô thì s& tô v$i màu mun tô. A. Tô
    ng tròn -  tô  ng tròn thì ta tìm hình vuông nh" nht ngoi tip  ng tròn b
    ng cách xác  nh im trên bên trái (xc-r, yc-r) và im d$i bên phi (xc+r, yc+r) c a hình vuông (xem hình 2.2). - Cho i i t xc-r n xc+r Cho j i t yc-r n yc+r Tính khong cách d gia hai im (i,j) và tâm (xc,yc) 33
34. Nu d<r thì tô im (i,j) v$i màu mun tô Hình 2.9:  ng tròn ni tip hình vuông B. Tô a giác - Tìm hình ch nht nh" nht có các cnh song song v$i hai trc ta  cha a giác c n tô da vào hai ta  (xmin, ymin), (xmax, ymax). Trong ó, xmin, ymin là hoành  và tung  nh" nht, xmax, ymax là hoành  và tung  l$n nht c a các +nh c a a giác. - Cho x i t xmin n xmax, y i t ymin n ymax (ho,c ngc lai). Xét im P(x,y) có thuc a giác không ? Nu có thì tô v$i màu c n tô (xem hình). Hình 2.10: a giác ni tip hình ch nht 34
35. Thông th ng mt im n
    m trong a giác thì s giao im t mt tia bt k* xut phát t im ó c#t biên c a a giác phi là mt s l: l n. ,c bit, ti các +nh cc tr (cc i hay cc tiu ) thì mt giao im phi c tính 2 l n (xem hình 2.5). Tia có th qua phi hay qua trái. Thông th ng ta chn tia qua phi. Ví d : Xét a giác gm 13 +nh là P , P , , P ≅ P 0 1 12 0 Hình 2.11: a giác có 13 +nh Gi tung  c a +nh P là P .y . Nu : i i - P .y Max ( P .y, P .y) thì P là +nh cc tr ( i i+1 i-1 i i+1 i-1 i cc tiu hay cc i ). - P .y P .y > P .y thì P là +nh n iu. i-1 i i+1 i i+1 i - P = P và P .y Max ( P .y, P .y) thì on i i+1 i i+2 i-1 i+2 i-1 [P ,P ] là on cc tr ( cc tiu hay cc i ). i i+1 - P = P và P .y P .y > P .y thì on [P ,P ] là on i i+1 i-1 i i+2 i i+2 i i+1 n iu. • Thut toán kim tra im có n$m trong a giác - V$i m0i +nh c a a giác ta ánh du là 0 hay 1 theo qui $c nh sau: nu là +nh cc tr hay on cc tr thì ánh s 0. Nu là +nh n iu hay on n iu thì ánh du 1. - Xét s giao im c a tia na  ng th'ng t P là im c n xét v$i biên c a a giác. Nu s giao im là ch'n thì kt lun im không thôc a giác. Ngc li, s giao im là l: thì im thuc a giác. Cài t minh ha thut toán xét im thuc a giác b$ng PASCAL function PointInpoly(d: dinh; P: d_dinh; n: integer): boolean; 35
36. var count, i: integer; x_cut: longint; function next(i: integer): integer; begin next := (i + n + 1) mod n end; function prev(i: integer): integer; begin prev := (i + n - 1) mod n end; begin count := 0; for i := 0 to n-1 do if d[i].y = P.y then begin if d[i].x > P.x then begin if ((d[prev(i)].y P.y) and (P.y > d[next(i)].y)) then count := count + 1; if d[next(i)].y = P.y then if ((d[prev(i)].y P.y) and (P.y > d[next(next(i))].y)) then count := count + 1; end; end else {d[i].y = P.y} if ((d[i].y P.y) and (P.y > d[next(i)].y)) then begin x_cut := d[i].x + Round((d[next(i)].x - d[i].x) / (d[next(i)].y - d[i].y) * (P.y - d[i].y)); if x_cut >= P.x then count := count + 1; end; if (count mod 2 = 0) then PointInPoly := false else PointInpoly := true; end; Cài t minh ha thut toán tô a giác (xmin, ymin, xmax, ymax: ã khai báo trong chng trình chính.) Procedure Todg ( d:dinh; n,maubien : integer ; d: dinh; n:integer ) ; var x, y:integer; P: d_dinh; begin 36
37. for x:=xmin to xmax do for y:= ymin to ymax do begin P.x:= x; P.y := y; if pointInpoly (d, P, n) then if getpixel(x,y)<>maubien then putpixel(x,y,color); end; end; • Nhn xét: Thut toán tô n gin có u im là tô rt m n và có th s! dng c cho a giác li hay a giác lõm, ho,c a giác t c#t,  ng tròn, ellipse. Tuy nhiên, gii thut này s& tr nên chm khi ta phi gi hàm PointInpoly nhiu l n.  kh#c phc nhc im này ng i ta a ra thut toán tô màu theo dòng quét. 2.3.2 Tô màu theo dòng quét (scan - line) Phng pháp này s& xác  nh ph n giao c a các dòng quét k tip nhau v$i  ng biên c a vùng tô. Sau ó, s& tin hành tô màu các im thuc ph n giao này. Phng pháp này th ng c dùng  tô màu a giác li , lõm hay a giác t c#t,  ng tròn, ellipse, và mt s  ng cong n gin khác. • Các b
    c chính ca thut toán - Tìm ymin, ymax l n lt là giá tr nh" nht, l$n nht c a tp các tung  c a các +nh c a a giác ã cho. - 4ng v$i m0i dòng quét y = k v$i k thay i t ymin n ymax, l,p : . Tìm tt c các hoành  giao im c a dòng quét y = k v$i các cnh c a a giác. . S#p xp các hoành  giao im theo th t t.ng d n : x ,x , , x , 0 1 n . Tô màu các on th'ng trên  ng th'ng y = k l n lt c gi$i hn bi các c,p (x , x ), ( x ,x ), (xem hình ). 0 1 1 2 37
38. Hình 2.12: Tô a giác b
    ng gii thut scanline • Các v%n  c n l
    u ý: - Hn ch c s cnh c n tìm giao im ng v$i m0i dòng quét vì ng v$i m0i dòng quét không phi lúc nào c/ng giao im v$i các cnh c a a giác. - Xác  nh nhanh hoàn  giao im vì nu l,p li thao tác tìm giao im c a cnh a giác v$i m0i dòng quét s& tn rt nhiu th i gian. - Gii quyt tr ng hp s giao im i qua +nh n iu thì tính s giao im là 1 hay i qua +nh cc tr .thì tính s giao im là 0 (ho,c 2). • T chc c%u trúc d liu và thut toán - Danh sách các cnh (Edge Table - ET) : cha toàn b các cnh c a a giác (loi các cnh song song v$i trc Ox) c s#p theo th t t.ng d n c a trc y. Xem hình 2.5 ta có th s#p xp các cnh trong ET là : AB, AI, HG, BC, GF, DC, EF (loi IH và DE) - Danh sách các cnh ang kích hat (Active Edge Table - AET) : cha các cnh c a a giác có th c#t ng v$i dòng quét hin hành, các cnh này c s#p theo th t t.ng d n c a hoành  giao im c a hoành  giao im gia cnh và dòng quét. - Khi dòng quét i t ymin n ymax, các cnh tho iu kin s& c chuyn t ET sang AET. Ngh-a là, khi dòng quét y=k b#t  u c#t mt cnh, khi ó k 7 ymin, cnh này s& c chuyn t ET sang AET. Khi dòng quét không còn c#t cnh này na, khi ó, k > ymax, cnh này s& b loi kh"i AET. Khi không còn cnh nào trong ET hay AET thì quá trình tô màu kt thúc (xem hình). 38
39. Hình 2.13: Dòng quét c#t a giác  i tìm giao im gia a giác và dòng quét, ta có nhn xét sau: 1 1 1 x - x = ( (k+1) - k ) = hay x = x + k+1 k m m k+1 k m Trong ó m là h s góc c a cnh. 39
40. Lu  thut toán tô màu theo dòng quét: Begin To danh sách tt c các cnh (ET) c a a giác i = ymin NO i < ymax YES Cp nht danh sách cnh kích hot AET Tìm hoành  giao im và s#p xp theo th t t.ng d n Tô màu các on giao c to bi tng c,p hoành  k tip nhau Cp nht li thông tin c a các cnh  s! dng cho dòng quét k tip i = i + 1 End 40
41. 2.3.3 Ph
    ng pháp tô màu da theo
    ng biên • Bài toán t ra : C n tô màu mt vùng nu bit c màu c a  ng biên vùng tô và mt im n
    m bên trong vùng tô. • Ý t
    &ng : B#t  u t mt im n
    m bên trong vùng tô, kim tra các im lân cn c a nó ã c tô v$i màu mun tô, hay im lân cn có màu trùng v$i màu biên không ? Nu c hai tr ng hp u không phi thì ta s& tô im ó v$i màu mun tô. Quá trình này c l,p li cho n khi không còn tô c na thì dng (xem hình 2.14). Hình 2.14: Tô màu theo  ng biên Có 2 quan im v cách tô này. ó là dùng 4 im lân cn (có th gi là 4 liên thông) hay 8 im lân cn (8 liên thông) (xem hình 2.15). (x,y-1) (x-1,y) (x,y) (x+1,y) (x,y+1) Hình 2.15: 4 liên thông và 8 liên thông. Cài ,t minh ha thut toán 4 liên thông trên PASCAL Procedure Boundary_fill ( x,y, mauto, maubien :integer); var mau_ht : integer; 41
42. begin mau_ht:= getpixel(x, y); if (mau_ht maubien) then begin putpixel(x,y,color); Boundary_fill ( x+1,y, mauto, maubien ); Boundary_fill ( x-1,y, mauto, maubien ); Boundary_fill ( x,y+1, mauto, maubien ); Boundary_fill ( x,y-1, mauto, maubien ); end; end; Nhn xét : - Thut toán có th không chính xác khi có mt s im n
    m trong vùng tô có màu là màu c n tô c a vùng. - Vic thc hin gi  qui làm thut toán không th s! dng cho vùng tô l$n ( tràn stack). - Có th kh#c phc vic tràn stack b
    ng cách gim s l n gi  qui. Khi  u im (x,y) là im có v trí ,c bit trong vùng tô, sau ó, gi  qui các im lân cn c a (x,y) (xem hình 2.14). Hình 2.16: Tam giác v$i 3 ta  +nh Ví d 1: Trong hình 2.16, ta có th xét im (x,y) có ta  là (498, 200). V$i im khi  u này thì ch+ c n xét 3 im lân cn là (x-1,y), (x,y-1), (x,y+1). Khi ó th tc tô màu theo  ng biên c vit li nh sau : Procedure Boundary_fill ( x,y,mauto, maubien :integer); var mau_ht : integer; begin mau_ht:= getpixel(x,y); 42
43. if (mau_ht maubien) then begin putpixel(x,y,color); Boundary_fill ( x-1,y, mauto, maubien ); Boundary_fill ( x,y+1, mauto, maubien ); Boundary_fill ( x,y-1, mauto, maubien ); end; end; Ví d 2: Trong hình 2.16, ta có th xét im (x,y) có ta  là (102, 102). V$i im khi  u này thì ch+ c n xét 2 im lân cn là (x+1,y), (x,y+1). Khi ó th tc tô màu theo  ng biên c vit li nh sau : Procedure Boundary_fill ( x,y,mauto, maubien :integer); var mau_ht : integer; begin mau_ht:= getpixel(x,y); if (mau_ht maubien) then begin putpixel(x,y,color); Boundary_fill ( x+1,y, mauto, maubien ); Boundary_fill ( x,y+1, mauto, maubien ); end; end; - Mt ci tin khác : không cài ,t  qui mà tô theo tng dòng (xem hình 2.17). 43
44. Hình 2.17: Tô theo tng dòng 44
45. Chng 3 Các phép bin i hình hc 2D Các phép bin i hình hc s& làm thay i mô t v ta  c a các i tng, t ó làm cho i tng b thay i v h$ng, kích th$c và hình dng. Các phép bin i hình hc c s bao gm : t nh tin (translation), quay (rotation) và bin i t+ l (scaling). Ngoài ra mt s phép bin i khác c/ng th ng c áp dng ó là phép i xng (reflection) và bin dng (shearing). Có hai quan im v phép bin i hình hc ó là : bin i i tng (object transformation) và bin i h ta  (coordinate transformation). Bin i i tng là thay i ta  c a các im mô t nó theo mt quy t#c nào ó, còn bin i h ta  là to ra mt h ta  m$i và tt c các im mô t i tng s& c chuyn v h ta  m$i. Hai cách này có nhng mi liên h ch,t ch& v$i nhau và m0i cách u có nhng li th riêng. Chúng ta s& bàn v phép bin i i tng tr$c. 3.1 Các phép bin i hình hc c s& Mt phép bin i hai chiu s& bin i im P trong m,t ph'ng thành im có ta  m$i Q theo mt quy lut nào ó. V m,t bn cht, mt phép bin i im là mt ánh x T c  nh ngh-a : T: R2 → R2 P(x, y) → Q(x', y') Nói cách khác, T là hàm s T(x, y) theo hai bin (x, y): Àx'= f (x, y)  y'= g(x, y) Phép bin i affine là phép bin i v$i f(x, y) và g(x, y) là các hàm tuyn tính. Phép bin i này có dng : Àx'= ax + cy + e à V$i a, b, c, d, e, f∈R và ad-bc≠0 Õy'= bx + dy + f Ta ch+ kho sát các phép bin i affine nên t nay v sau ta dùng cm t "phép bin i" thay cho "phép bin i affine". 3.1.1 Phép tnh tin  t nh tin mt im P(x, y) t v trí này sang v trí khác trong m,t ph'ng, ta cng thêm các giá tr mô t  d i vào các ta  c a P. Nu gi trx và try l n lt là  d i theo trc hoành và trc tung thì ta  c a im m$i Q(x', y') s& là: Àx'= x + Œ tr x à Œy'= y + Õ tr y 45
46. (trx, try) còn c gi là vector t nh tin hay vector  d i. Chúng ta có th d ch chuyn toàn b mt i tng b
    ng cách áp dng quy t#c trên cho mi im thuc i tng.  t nh tin mt on th'ng, n gin ch+ c n t nh tin hai im  u và cui c a nó ri sau ó v& li on th'ng ni hai im m$i. V$i a giác, ta t nh tin các +nh c a nó sau ó v& li a giác v$i các +nh m$i. Mt cách tng t,  t nh tin các i tng nh  ng tròn, ellipse, ta t nh tin tâm c a chúng t$i v trí m$i ri v& li. Hình 3.1: T nh tin im P(x, y) theo vector (trx, try) 3.1.2 Phép bin i t l
    Phép bin i t+ l làm thay i kích th$c i tng.  co hay giãn ta  c a mt im P(x, y) theo trc hoành và trc tung l n lt là ∂x và ∂y, ta nhân ∂x và ∂y l n lt cho các ta  c a P. Àx'= .x  ∂x  (∂x và ∂y c gi là các h s t( l) y'= .y  ∂ y Khi các giá tr ∂x, ∂y nh" hn 1, phép bin i s& thu nh" i tng, ngc li khi các giá tr này l$n hn 1, phép bin i s& phóng l$n i tng. Khi ∂x, ∂y b
    ng nhau, ta gi ó là phép ng dng (uniform scaling), phép ng dng là phép bin i bo toàn tính cân xng c a i tng. Tâm t+ l là im không b thay i qua phép bin i t+ l. Phép bin i t+ l mô t nh trên còn gi là phép bin i t+ l quanh gc ta  vì có tâm t+ l là gc ta . Nhn xét r
    ng khi phép bin i t+ l thu nh" i tng, i tng s& c d i v g n gc ta  hn, tng t khi phóng l$n i tng, i tng s& c d ch chuyn xa gc ta  hn. 46
47. Hình 3.2: Phép bin i t( l v$i ∂x=2.5 và ∂y=0.5 3.1.3 Phép quay Phép quay làm thay i h$ng c a i tng. Mt phép quay òi h"i phi có tâm quay, góc quay. Góc quay dng th ng c quy $c là chiu ngc chiu kim ng h. Ta có công thc bin i c a phép quay im P(x, y) quanh gc ta  mt góc α thành im Q(x', y'): Àx'= x.cosα + y.sinα  y'= x.sinα + y.cosα Hình 3.3: Phép quay im P(x, y) quanh gc ta  mt góc α 3.1.4 Biu din ma trn c a phép bin i Trong nhiu ng dng  ha, ng i dùng th ng xuyên có nhu c u thc hin nhiu phép bin i hình hc khác nhau trên mt i tng  to ra các hiu qu nh mong mun. Ví d trong các ng dng thit k, chúng ta c n phi thc hin nhiu phép t nh tin, quay, t+ l  có th kh$p tng ph n c a i tng vào úng v trí c a chúng, hay sau khi thc hin các phép bin i nhng không c ng ý, ng i dùng mun tr li hin trng tr$c khi bin i (undo), Do ó c n phi có mt cách nào ó  có th x! lí dãy các phép bin i trên c nhanh chóng và hiu qu. Nu ta biu di)n ta  c a im P(x, y) và Q(x', y') d$i dng các vector dòng l n lt là (x y) và (x' y') thì các phép bin i t nh tin, t+ l, quay có th c biu di)n d$i dng ma trn nh sau : 47
48. A. Phép tnh tin x' y' = x y + ( ) ( ) (tr x tr y) hay Q = P + T v$i T = (tr x tr y) B. Phép bin i t' l 0 ’ (x' y') = (x y) ∂x  0  ∂ y  0  hay Q = P.S v$i S = ∂x  0  ∂ y  C. Phép quay quanh gc ta cosα sinα  (x' y') = (x y)  − sinα cosα  cosα sinα  hay Q = P.R v$i R =  − sinα cosα  V$i cách biu di)n này, chúng ta s& g,p khó kh.n khi mun kt hp các phép bin i li v$i nhau vì ma trn biu di)n c a phép t nh tin khác v$i ma trn biu di)n c a các phép bin i t+ l và quay. Chính vì vy mà c n phi có mt cách nào ó  biu di)n ba phép bin i này v mt dng ma trn duy nht  có th d) dàng x! lí sau này. 3.1.5 H
    ta thun nht (hormogeneous coordinates) Ta  thu n nht c a mt im trên m,t ph'ng c biu di)n b
    ng b ba s t+ l (xk, yk, h) không ng th i b
    ng 0 và liên h v$i các ta  (x, y)c a im ó bi công thc : y x = xk , y = k h h Nu mt im có ta  thu n nht là (x, y, h) thì nó c/ng có ta  thu n nht là (k.x, k.y, k.h) trong ó k là s thc khác 0 bt kì. Ta  thu n nht c a mt im trong không gian ba chiu hay có s chiu l$n hn c/ng c xác  nh mt cách tng t. V m,t toán hc, vic a ta  thu n nht vào là do s c n thit phi b sung cho m,t ph'ng Euclid các im xa vô tn (x, y, 0) (im phi chính) có ta  th ba b
    ng 0, iu này d2n n khái nim m,t ph'ng x nh trong hình hc x nh. Trong h ta  thu n nht, các im xa vô tn không óng mt vai trò gì ,c bit so v$i các im khác c a m,t ph'ng. V$i các phép bin i hình hc ang kho sát, nu mt im c biu di)n d$i dng ta  thu n nht, c ba phép bin i trên u c biu di)n d$i dng tích các ma trn. iu này giúp cho vic kho sát các tính cht và s kt hp c a các phép bin i này c thun tin do m0i phép bin i c i din bi mt ma trn duy nht. B ba các ta  th ng biu di)n các im trong không gian ba chiu, nhng  ây ta s! dng chúng  biu di)n các im trong không gian hai chiu. Mi liên h  ây n gin là : nu chúng ta xét tt c các b ba ta  thu n 48
49. nht biu di)n cho cùng mt im, ngh-a là b ba s có dng (h.x, h.y, h), v$i h ≠ 0, chúng ta s& nhn c mt  ng th'ng trong không gian ba chiu.  n gin hóa chúng ta có th chn h = 1, lúc này m0i im P(x, y) s& c biu di)n d$i dng ta  thu n nht là (x, y, 1) Biu di)n ma trn c a các phép bin i trong h ta  thu n nht A. Phép tnh tin ’ 1 0 0 (x' y' 1) = (x y 1) 0 1 0  1 tr x tr y   1 0 0 hay Q=P.M (tr , tr ) v$i M (tr , tr ) = 0 1 0 T x y T x y  1 tr x tr y  B. Phép bin i t l
    0 0 ∂x  (x' y' 1) = (x y 1) 0 0 ∂ y  0 0 1 0 0 ∂x  hay Q = P.MS(∂x, ∂y) v$i MS(∂x, ∂y) = 0 0 ∂ y  0 0 1 C. Phép quay quanh gc ta cosα sinα 0  (x' y' 1) = (x y 1) − sinα cosα 0  0 0 1 cosα sinα 0  hay Q = P.MR(α) v$i MR(α) = − sinα cosα 0  0 0 1 3.2 Kt hp các phép bin i Quá trình áp dng các phép bin i liên tip  to nên mt phép bin i tng th c gi là s kt hp các phép bin i (composing transformation). 3.2.1 Kt hp các phép tnh tin Nu ta thc hin phép t nh tin lên P(x, y) c P’ , ri li thc hin tip mt phép t nh tin khác lên P’, ta c im Q(x', y'). Nh vy, Q là nh c a phép bin i kt hp hai phép t nh tin liên tip MT1(trx1, try1) và MT2(trx2, try2). Ta có: Q = {P.MT1(trx1, try1)}.MT2(trx2, try2) = P.{MT1(trx1, try1).MT2(trx2, try2)} Ta có : 49
50. ’  1 0 0 1 0 0 M (tr , tr ).M (tr , tr ) = 0 1 0 0 1 0 T1 x1 y1 T2 x2 y2   1 1 tr x1 tr y1  tr x2 tr y2   1 0 0 = 0 1 0  + + 1 tr x1 tr x2 tr y1 tr y2  hay : MT1(trx1, try1).MT2(trx2, try2) = MT(trx1 + trx2, try1 + try2) Vy kt hp hai phép t nh tin là mt phép t nh tin. T ó ta có kt hp c a nhiu phép t nh tin c/ng là mt phép t nh tin. 3.2.2 Kt hp các phép t l
    Tng t nh phép t nh tin, ta có ta  im Q(x', y') là im có c sau khi kt hp hai phép t+ l Ms1(∂x1, ∂y1) và Ms2(∂x2, ∂y2) là : Q = {P.Ms1(∂x1, ∂y1)}. Ms2(∂x2, ∂y2) = P.{Ms1(∂x1, ∂y1).Ms2(∂x2, ∂y2)} Ta có : 0 0 0 0 . 0 0 ∂x1  ∂x2  ∂x1 ∂x2  Ms1(∂x1, ∂y1).Ms2(∂x2, ∂y2) = 0 0 0 0 = 0 . 0 ∂ y1  ∂ y2  ∂ y1 ∂ y2  0 0 1 0 0 1 0 0 1 hay : Ms1(∂x1, ∂y1).Ms2(∂x2, ∂y2) = Ms(∂x1.∂x2, ∂y1.∂y2) Vy kt hp hai phép t+ l là mt phép t+ l. D) dàng m rng cho kt qu : kt hp c a nhiu phép t+ l c/ng là mt phép t+ l. 3.2.3 Kt hp các phép quay Tng t, ta có ta  im Q(x', y') là im phát sinh sau khi kt hp hai phép quay quanh gc ta  MR1(α1) và MR2(α2) là : Q = {P.MR1(α1)}.MR2(α2) = P.{MR1(α1).MR2(α2)} Ta có : cosα1 sinα1 0 cosα 2 sinα 2 0   MR1(α1).MR2(α2) = − sinα1 cosα1 0 − sinα 2 cosα 2 0   0 0 1 0 0 1 cos(α1+ α 2) sin(α1+ α 2) 0  = − sin(α1+ α 2) cos(α1+ α 2) 0  0 0 1 hay : MR1(α1).MR2(α2) = MR(α1 + α2) Vy kt hp hai phép quay quanh gc ta  là mt phép quay quanh gc ta . T ó d) dàng suy ra kt hp c a nhiu phép quay quanh gc ta  c/ng là mt phép quay quanh gc ta . 3.2.4 Phép quay có tâm quay là im bt k Gi s! tâm quay có ta  I(xR, yR), ta có th xem phép quay quanh tâm I mt góc α c kt hp t các phép bin i c s sau: 50
51. • T nh tin theo vector t nh tin (-xR, -yR) d ch chuyn tâm quay v gc ta  (a v tr ng hp quay quanh gc ta ). • Quay quanh gc ta  mt góc α. • T nh tin theo vector t nh tin (xR, yR)  a tâm quay v li v trí ban  u. Ta có ma trn c a phép bin i : MR(xR, yR, α) = MT(-xR,-yR).MR(α).MT(xR, yR) 1 0 0’ cosα sinα 0 1 0 0    = 0 1 0 − sinα cosα 0 0 1 0    1 0 0 1 1 −xR −yR  xR yR  3.3 Mt s tính ch%t ca phép bin i Affine 3.3.1 Phép bin i affine bo toàn ng thng nh c a  ng th'ng qua phép bin i affine là  ng th'ng. Tht vy, ta có phng trình tham s c a  ng th'ng qua hai im A, B là: P(t)=(1-t)A+tB. Q(t) là các im nhn c sau phép bin i M: Q(t) = P(t).M = [(1- t).A + t.B].M =(1- t).A.M + t.B.M Nu gi A’, B’ l n lt là nh c a A, B qua phép bin i M, ta s& có A' = A.M, B' = B.M Lúc này Q(t) = (1- t).A' + t.B'. ây chính là dng c a phng trình tham s on th'ng qua A’, B’. T kt qu trên,  bin i mt on th'ng i qua hai im A và B, ta ch+ c n áp dng phép bin i cho hai im A, B ri v& li on th'ng qua hai im m$i. 3.3.2 Tính song song c a các ng thng c bo toàn nh c a hai  ng th'ng song song là hai  ng song song. Chúng ta có th vit li phng trình tham s c a  ng th'ng d$i dng tia xut phát t A ng v$i t = 0 và theo phng β = B - A nh sau : A + β.t . Lúc này ta biu di)n hai  ng th'ng song song d$i dng tia :L1(t) = A1 + β.t và L2(t) = A2 + β.t có cùng phng β.t nhng xut phát t hai im khác nhau. Bây gi áp dng phép bin i lên hai  ng th'ng song song này, d) dàng nhn ra nh c a chúng s& có phng β.M nên chúng song song. Mt h qu quan trng c a tính cht này ó là nh c a các hình bình hành sau phép bin i là các hình bình hành. 3.3.3 Tính t l
    v khong cách c bo toàn Gi s! C là im chia on AB theo t+ s t. Nu A’, B’, C’ l n lt là nh A, B, C qua phép bin i thì C’ c/ng s& chia A’B’ theo t+ s t. Trong tr ng hp ,c bit, nu C là trung im c a AB thì C’ c/ng là trung im c a A’B’, t ó ta có th suy ra mt s tính cht sau : • Trong hình vuông, các  ng chéo c#t nhau ti trung im c a m0i  ng nên các  ng chéo c a bt c hình bình hành nào c/ng c#t nhau ti trung im c a m0i  ng. 51
52. • Trong tam giác u, giao im c a ba  ng trung tuyn chia m0i  ng theo t+ s 1:2. M,t khác, mt tam giác bt kì là nh c a tam giác u qua phép bin i affine, nên giao im c a các  ng trung tuyn c a nó c/ng s& chia chúng theo t+ l 1:2. 3.4 Mt s phép bin i khác 3.4.1 Phép i xng Phép i xng trc có th xem là phép quay quanh trc i xng mt góc 1800. Nu trc i xng là trc hoành hay trc tung, chúng ta có biu di)n c a phép i xng qua trc hoành, trc tung l n lt là : 1 0 0’  MRfx = 0 −1 0  0 0 1 −1 0 0  MRfy = 0 1 0  0 0 1 3.4.2 Phép bin dng Phép bin dng là phép bin i làm thay i, méo mó hình dng c a các i tng. Hai dng phép bin dng th ng g,p ó là bin dng theo phng trc x và bin dng theo phng trc y b
    ng cách thay i ta  (x, y) c a im ban  u theo cách sau : Bin dng theo phng trc x s& làm thay i hoành  còn tung  v2n gi nguyên 1 0 0  MShx = Sx 1 0  0 0 1 Bin dng theo phng trc y s& làm thay i tung  còn hoành  v2n gi nguyên 1 0 0  MShy = Sy 1 0  0 0 1 Sx và Sy l n lt c gi là các h s bin dng. Hình 3.4: Phép bin dng theo phng trc x v$i h s bin dng Sx = 3 52
53. 3.4.3 Phép bin i ngc Chúng ta th ng dùng phép bin i ngc  có th undo mt phép bin i ã thc hin. Ta có Q là nh c a P qua phép bin i T có ma trn bin i M là : Q = P.M, t ó phép bin i ngc T-1 s& có ma trn bin i là M-1 v$i M-1 là ma trn ngh ch o c a ma trn M. V$i gi thit ban  u v ma trn M là a.d - b.c ≠ 0, ta có công thc tính ma a b 0’  trn ngh ch o M-1 c a M = c d 0 là :  e f 1 d − b 0 -1 1  M = − c a 0 ad − bc  cf − de be − af 1 Nh vy ta có ma trn c a các phép bin i ngc c a các phép bin i c s t nh tin, t+ l, quay l n lt nh sau :  1 0 0 M -1(tr , tr ) = 0 1 0 = M (-tr , -tr ) T x y  T x y − 1 tr x −tr y  1  0 0  0 0 ∂x ∂x  -1 1 1  1 1 M (∂ , ∂ ) = 0 0 = 0 0 = M ( , ) S x y ∂ y S   ∂x ∂ y 0 0 1 ∂ y ∂x ∂ y 0 0 1   cosα − sinα 0  -1 MR (α) = sinα cosα 0 = MR(- α)  0 0 1 3.4.4 Phân rã phép bin i Mt phép bin i bt kì có th c phân rã thành tích các phép bin i c s nh t nh tin, quay, t+ l. Mt phép bin dng theo phng trc x có th c phân rã thành tích c a mt phép bin i t+ l và mt phép bin dng n v , và v$i mt phép bin i t+ l khác theo công thc sau : 1  1 0 0 0 0 1 0 0 Sx 0 0  Sx    Sx 1 0 = 0 1 0 1 1 0 0 1 0     0 0 1 0 0 1 0 0 1 0 0 1  Phép bin dng n v còn có th c phân rã tip : 53
54.  1 0 0’ cosα − sinα 0 φ 0 0 cos β sin β 0   1  1 1 0 = sinα cosα 0 0 0 − sin β cos β 0 φ      0 0 1 0 0 1 0 0 1 0 0 1  −1 0 α = tan (φ) = 58.28 trong ó  −1 1 0 β = ( ) =  tan φ 31.72 T ó, mt phép bin i bt kì có th c phân rã thành các phép bin i c s sau : a b   0  a b 0 1 0 0 Q 0 0 Q Q  1 0 0     ac + bd ad − bc  b a  c d 0 = 1 0 1 0 − 0 0 1 0 2 Q  Q Q  Q     e f 1  0 0 1 0 0 1 e f 1 0 0 1   trong ó Q2 = a2 + b2 V$i cách lp lun trên ta nhn thy : bt kì phép bin i nào c/ng c kt hp t các phép bin dng, t+ l, quay, và t nh tin. Tuy nhiên, theo kt qu  b$c tr$c, phép bin dng là s kt hp c a các phép quay, t+ l, nên t ó suy ra bt kì phép bin i nào c/ng c kt hp t các phép t nh tin, t+ l và quay. 3.5 Phép bin i gia các h ta  thun tin cho vic mô t i tng, thông th ng i tng s& c mô t trong các h ta  cc b g#n v$i chúng. Tuy nhiên  có th hin th toàn b mt khung cnh bao gm nhiu i tng thành ph n, các mô t này phi c chuyn v mt h ta  chung duy nht. Vic chuyn i này th ng c chia làm hai loi : chuyn t các h ta  không phi là h ta  Descartes nh h ta  cc, h ta  c u, h ta  elliptic, sang h ta  Descartes, và chuyn i gia hai h ta  Descartes. Trong ph n này chúng ta s& kho sát phép bin i gia hai h ta  Descartes v$i nhau. Hình 3.5: Phép bin i gia hai h ta  Gi s! ta có h ta  (I) có gc ta  O và các vector n v l n lt là i, j. H ta  (II) là nh c a h ta  (I) qua phép bin i T(M), có gc ta  là 54
55. O’ và các vector n v l n lt là u, v. Lúc này mt im P(x, y) bt kì trong h ta  (I) s& c bin i thành im Q(a, b) trong h ta  (II). Vn  ,t ra  ây là mi liên h gia a, b v$i x, y, M nh th nào. Ng i ta chng minh c r
    ng Q = P.M-1 Hình 3.6: Ta  c a mt im qua phép bin i h ta  55
56. Ch
    ng 4 Hin th các i t
    ng 2D Chng này s&  cp t$i các k- thut  hin th các i tng hai chiu trên các thit b nh màn hình, máy in, Các h  ha cho phép ng i dùng mô t các hình nh b
    ng h ta  th gi$i thc. Nó có th là bt kì h ta  Descartes nào mà ng i dùng cm thy thun tin nht khi s! dng. Các hình nh c mô t trong h ta  thc sau ó s& c các h  ha ánh x vào h ta  thit b . Thông th ng các h  ha cho phép ng i dùng xác  nh vùng nào c a hình nh c hin th và nó s& c hin th  âu trên màn hình. Ta có th chn mt vùng hay mt s vùng  hin th cùng mt lúc, các vùng này có th ,t  các ni khác nhau trên màn hình hay lng vào nhau. Quá trình bin i này òi h"i các phép bin i nh d ch chuyn, quay, bin i t+ l; và các thao tác loi b" các vùng hình nh n
    m ngoài vùng c  nh ngh-a, 4.1 Quy trình hin th các i t
    ng 2D 4.1.1 Mt s khái ni
    m • C!a s (window) là mt vùng c chn  hin th trong h ta  th gi$i thc. • Vùng quan sát (viewport) là vùng c chn trên thit b hin th  các i tng  trong c!a s ánh x vào. C!a s xác  nh cái gì c thy trên thit b hin th , còn vùng quan sát xác  nh ni nào nó s& c hin th . 3 ây chúng ta nên phân bit khái nim c!a s c dùng trong ph n này v$i khái nim c!a s c dùng trong các chng trình ng dng trên các h iu hành nh Windows. Thông th ng c!a s và vùng quan sát có dng hình ch nht, có các cnh song song v$i các trc ta . Tuy nhiên chúng c/ng còn có mt s dng khác nh a giác, hình tròn, Quá trình ánh x mt vùng  nh ngh-a trong h ta  th gi$i thc vào mt vùng trong h ta  thit b c gi là phép bin i h quan sát (viewing transformation). 56
57. Hình 4.1: Phép bin i h quan sát v$i c!a s và vùng quan sát có dng là các hình ch nht Quy trình hin th các i tng trong  ha hai chiu có th c mô t qua s  sau : Tr$c tiên, các i tng s& c mô t b
    ng các i tng  ha c s và các thuc tính c a chúng trong tng h ta  cc b (modeling coordinates - MC) nh
    m n gin hóa và tn dng các ,c trng riêng c a tng loi. Sau ó, chúng ta s& dùng các phép bin i h ta   chuyn các mô t t các h ta  cc b này sang mt h ta  th gi$i thc (world coordinates - WC) duy nht cha toàn b các i tng thành ph n. Phép chuyn i này c gi là phép chuyn i mô hình (modeling coordinates transformation). Tip theo, chúng ta s&  nh mt h ta  quan sát (viewing coordinates - VC), là h ta  mô t v trí c a ng i quan sát i tng. Nh vic s! dng h ta  này mà cùng mt mô t, các i tng có th c quan sát  nhiu góc  và v trí khác nhau. Sau khi chuyn các mô t i tng t h ta  th gi$i thc sang h ta  quan sát, chúng ta s&  nh ngh-a c!a s trong h ta  này, ng th i  nh ngh-a vùng quan sát trong h ta  thit b chu%n (normalized device coordinates - NDC) có ta  các chiu thay i trong khong t 0 n 1. Sau khi thc hin phép ánh x t c!a s sang vùng quan sát, tt c các ph n c a i tng n
    m ngoài vùng quan sát s& b xén (clip) và toàn b nhng gì n
    m trong vùng quan sát s& c ánh x sang h ta  thit b (device coordinates - DC). Vic a ra h ta  thit b chu%n nh
    m giúp cho vic tng thích d) dàng v$i nhiu loi thit b hin th khác nhau. Chuyn i t Chuyn i t h Chuyn i t Ánh x t h h ta  cc ta  th gi$i h ta  quan MC WC VC NDC ta  thit b b sang h thc sang h ta sát sang h ta chu%n sang h ta  th  quan sát  thit b chu%n ta  thit b gi$i thc DC Hình4.2: Quy trình hin th i tng hai chiu 57
58. B
    ng cách thay i v trí c a vùng quan sát chúng ta có th quan sát các i tng ti các v trí khác nhau trên màn hình hin th , ng th i, b
    ng cách thay i kích th$c c a vùng quan sát, chúng ta có th thay i kích th$c và tính cân xng c a các i tng c hin th . Chúng ta có th thc hin các hiu ng thu phóng b
    ng cách ánh x các c!a s có kích th$c khác nhau vào vùng quan sát có kích th$c c  nh. Khi các c!a s c thu nh", ph n n
    m trong c!a s s& c phóng to giúp chúng ta d) dàng quan sát các chi tit mà không th thy c trong các c!a s l$n hn. 4.1.2 H
    ta quan sát và h
    ta thit b chun A. H ta quan sát  thit lp h ta  quan sát, tr$c tiên ta s& chn mt im P0(x0, y0) trong h ta  th gi$i thc làm gc ta . Sau ó chúng ta s& s! dng mt vector V mô t h$ng quan sát   nh h$ng cho trc tung y0 c a h ta . Vector V c gi là view-up vector. T V chúng ta có th tính c các vector n v v = (vx, vy) và u = (ux, uy) tng ng cho các trc tung y0 và trc hoành x0 c a h ta . Các vector n v này s& c dùng  to thành hai dòng  u tiên c a ma trn quay MR  a các trc x0y0 trùng v$i các trc c a h trc ta  th gi$i thc. Hình 4.3: Phép bin i mt im t h ta  quan sát sang h ta  thc Ma trn c a phép chuyn mt im trong h ta  th gi$i thc sang h ta  quan sát là tích c a hai ma trn c a các phép bin i : phép t nh tin gc ta  h quan sát v gc ta  h ta  th gi$i thc, phép quay a các trc c a h ta  quan sát trùng v$i các trc c a h ta  th gi$i thc: M = MT.MR. B. H ta thit b chu n Do cách  nh ngh-a c a các h ta  thit b khác nhau nên mt hình nh hin th c trên thit b này cha ch#c hin th chính xác trên thit b kia. Chính vì vy c n phi xây dng h ta  thit b chu%n i din chung cho các 58
59. thit b  có th mô t các hình nh c a th gi$i thc mà không ph thuc vào bt c thit b nào. Trong h ta  này, các ta  x, y s& c gán các giá tr trong khong t 0 n 1. Nh vy, vùng không gian c a h ta  thit b chu%n chính là hình vuông n v có góc trái d$i là (0,0) và góc phi trên (1,1). y (1, 1) 1 0 1 x Hình 4.4 – H ta  thit b chu%n 4.1.3 Chuyn i t c!a s quan sát sang vùng quan sát Phép chuyn i t c!a s sang vùng quan sát bao gm 3 phép bin i : phép t nh tin  d ch chuyn góc trái d$i v gc ta  (hình 4.5a), phép bin i t+ l  ch+nh kích th$c c a c!a s v cùng kích th$c c a vùng quan sát (hình 4.5b, hình 4.5c), cui cùng là phép t nh tin d ch chuyn v góc trái d$i c a vùng quan sát (hình 4.5d). y y (x , y ) max max (xmin, ymin) x x (a) (b) u u (vmin, umin) (vmin, umin) v v (c) (d) Hình 4.5: Phép chuyn i t c!a s sang vùng quan sát 59
60. Ta có ma trn c a phép bin i : − − umax umin vmax vmin MWV = MTW(-xmin, -ymin)MS( , ) MTV(umin, vmin) − − xmax xmin ymax ymin ’ −  umax umin 0 0 − xmax xmin  −  = 0 vmax vmin 0 y − y  max min  − − umax umin vmax vmin  − min + min − y + min 1 x − u min − v  xmax xmin ymax ymin  Nh vy nu P(x, y) là im trong c!a s thì nó s& có ta  trong vùng quan − − umax umin vmax vmin sát là : (∂x(x - xmin)+umin, ∂y(y - ymin) + vmin) v$i ∂x = , ∂y = . − − xmax xmin ymax ymin 3 ây ∂x, ∂y là các h s t+ l c a các kích th$c c a c!a s và vùng quan sát. Khi ∂x = ∂y = 1 , các i tng qua phép chuyn i s& c gi nguyên hình dáng và tính cân xng. 4.2 Các thut toán c(t xén hình Thao tác loi b" các ph n hình nh n
    m ngoài mt vùng cho tr$c c gi là xén hình. Vùng c dùng  xén hình gi là c!a s xén (clip window). Tùy thuc vào tng ng dng c th mà c!a s xén có th có dng là a giác hay là  ng cong khép kín. Trong ph n này chúng ta s& kho sát các thut toán xén hình vào c!a s xén là hình ch nht tr$c, sau ó s& kho sát các c!a s xén có dng khác.  n gin, trong các thut toán xén hình, c!a s xén c gi là c!a s. Gi s! c!a s xén là c!a s hình ch nht có ta  c a các im d$i bên trái và im trên bên phi l n lt là (xmin, ymin) và (xmax, ymax). Mt im P(x, y) c coi là n
    m bên trong c!a s nu th"a h bt phng trình : xmin ≤ x ≤ xmax và ymin ≤ y ≤ ymax Bây gi , ta s& xét bài toán xén on th'ng c cho bi hai im P1(x1, y1) và P2(x2, y2) vào c!a s hình ch nht trên. 60
61. Hình 4.6: Minh ha thao tác xén các on th'ng vào mt c!a s hình ch nht. Tr$c khi xén (a). Sau khi xén (b). Thao tác xén hình là mt trong nhng thao tác c bn c a quá trình hin th i tng, do ó vn  ti u tc  luôn là ích cho các thut toán nh#m n. Ý tng chung c a các thut toán xén on th'ng ó là loi b" phép toán tìm giao im gia on th'ng v$i biên c a c!a s mt cách nhanh nht i v$i các on th'ng ,c bit nh n
    m hoàn toàn trong ho,c hoàn toàn bên ngoài c!a s (ví d nh on P1P2 và P3P4 trong hình 4.6). i v$i các on th'ng có kh n.ng c#t c!a s, c n phi a ra cách tìm giao im tht nhanh. Nhn xét r
    ng, các on th'ng mà có c hai im n
    m hoàn toàn trong c!a s thì c on th'ng n
    m trong c!a s, ây c/ng chính là kt qu sau khi xén (ví d nh on th'ng P1P2), m,t khác i v$i các on th'ng mà có hai im n
    m v cùng mt phía c a c!a s thì luôn n
    m ngoài c!a s và s& b mt sau khi xén (ví d nh on th'ng P3P4). V$i các on th'ng có kh n.ng c#t c!a s (ví d nh on th'ng P5P6 và P7P8)  vic tìm giao im nhanh c n rút gn vic tìm giao im v$i nhng biên c!a s không c n thit  xác  nh ph n giao nu có c a on th'ng và c!a s. Ng i ta th ng s! dng phng trình tham s c a on th'ng trong vic tìm giao im gia on th'ng v$i c!a s: x = x1 + t.(x2 - x1) = x1 + t.Dx y = y1 + t.(y2 - y1) = y1 + t.Dy v$i Dx = x2 - x1, Dy = y2 - y1 và 0≤ t ≤ 1 Nu giao im ng v$i giá tr t n
    m ngoài on [0, 1] thì giao im ó s& không thuc v c!a s. 4.2.1 Thut toán Cohen - Sutherland ây là mt trong nhng thut toán ra  i s$m nht và thông dng nht. B
    ng cách kéo dài các biên c a c!a s, ng i ta chia m,t ph'ng thành chín vùng gm c!a s và tám vùng xung quanh nó. • Khái ni
    m mã vùng (area code) Mt con s 4 bit nh phân gi là mã vùng s& c gán cho m0i vùng  mô t v trí tng i c a vùng ó so v$i c!a s. B
    ng cách ánh s t 1 n 4 theo th t t phi qua trái, các bit c a mã vùng c dùng theo quy $c sau  ch+ 61
62. mt trong bn v trí tng i c a vùng so v$i c!a s bao gm : trái, phi, trên, d$i. Bit 1 : trái (LEFT) Bit 2 : phi (RIGHT) Bit 3 : trên (TOP) Bit 4 : d$i (BOTTOM) Giá tr 1 tng ng v$i v trí bit nào trong mã vùng s& ch+ ra r
    ng im ó  v trí tng ng, ngc li bit ó s& c ,t b
    ng 0. Ví d mt vùng có mã là 1001, thì nó s& n
    m phía d$i (bit 4 b
    ng 1), bên trái (bit 1 b
    ng 1) so v$i c!a s, vùng có mã là 0000 chính là c!a s. Hình 4.7: Mã vùng quy  nh v trí tng i c a vùng so v$i c!a s Các giá tr bit trong mã vùng c tính b
    ng cách xác  nh ta  c a im (x, y) thuc vùng ó v$i các biên c a c!a s. Bit 1 c ,t là 1 nu x < xmin, các bit khác c tính tng t. Thut toán Gán mã vùng tng ng cho các im  u cui P1, P2 c a on th'ng c n xén l n lt là c1, c2. Ta có nhn xét : • Các on th'ng n
    m hoàn toàn bên trong c!a s s& có c1 = c2 = 0000, ng v$i các on này, kt qu sau khi xén là chính nó. • Nu tn ti k∈{1, ,4}, sao cho v$i bit th k c a c1, c2 u có giá tr 1, lúc này on th'ng s& n
    m v cùng phía ng v$i bit k so v$i c!a s, do ó n
    m hoàn toàn ngoài c!a s. on này s& b loi b" sau khi xén. Ví d, nu c1 = 1001, c2 = 0101, rõ ràng bit 1 c a chúng u b
    ng 1 (ng v$i biên trái), do ó on th'ng n
    m hoàn toàn v biên trái c a c!a s.  xác  nh tính cht này, n gin ch+ c n thc hin phép toán logic AND trên c1, c2. Nu kt qu khác 0000, on th'ng s& n
    m hoàn toàn ngoài c!a s. • Nu c1, c2 không thuc v hai tr ng hp trên, on th'ng có th ho,c không c#t ngang c!a s (ví d on P5P6, P7P8 trong hình 4.6) ch#c ch#n s& tn ti mt im n
    m ngoài c!a s, không mt tính tng quát gi s! im ó là P1. B
    ng cách xét mã vùng c a P1 là c1 ta có th xác  nh c các biên mà on th'ng có th c#t  t ó chn mt biên và tin hành tìm giao im P1' c a on th'ng v$i biên ó. Lúc này, on th'ng ban  u c xén thành P1P1'. T$i ây chúng ta li l,p li thao tác ã xét cho on 62
63. th'ng m$i P1P1' cho t$i khi xác  nh c ph n n
    m trong ho,c loi b" toàn b on th'ng. Chúng ta minh ha thut toán b
    ng hình v& 4.8. V$i on th'ng P1P2, ta s& kim tra P1 l n lt v$i các biên trái, phi, d$i, trên và tìm ra im này n
    m d$i c!a s, sau ó chúng ta tìm giao im P1' c a on th'ng v$i biên d$i. Lúc này on th'ng ban  u c xén ng#n li thành P1'P2. Vì P2 n
    m ngoài c!a s nên b
    ng cách xét tng t, chúng ta s& tin hành tìm giao im P2' c a P1'P2 v$i biên trên và lúc này on P1'P2', chính là ph n n
    m hoàn toàn trong c!a s. Trong tr ng hp on P3P4, P3 n
    m bên trái c!a s nên chúng ta có th xác  nh im giao P3', và t ó loi b" on th'ng P3P3'. B
    ng cách kim tra mã vùng, chúng ta d) dàng xác  nh c on th'ng P3'P4 n
    m hoàn toàn bên d$i c!a s nên có th b" i toàn b. Hình 4.8: Minh ha thut toán Cohen - Sutherland Các im giao v$i các biên c!a s c a on th'ng có th c tính t phng trình tham s nh ã  cp  ph n trên. Tung  y c a im giao on th'ng v$i biên ng c a c!a s có th tính t công thc y = y1+ m.(x - x1), trong ó x có th là xmin hay xmax. Tng t, hoành  x c a im giao on th'ng v$i biên ngang c a c!a s có th tính t công thc : x = x1 +(y - y1)/m, trong ó y có th là ymin hay ymax. Cài "t minh ha thut toán Cohen - Sutherland trên ngôn ng# lp trình C: #define TRUE 1 #define FALSE 0 #define LEFT 1 #define RIGHT 2 #define TOP 4 #define BOTTOM 8 63
64. typedef struct { int x, y; }POINT; typedef struct { int Left, Top, Right, Bottom; }RECT; typedef int CODE; #define Accept(a,b) (!(a|b)) #define Reject(a,b) (a&b) // Tra ve ma vung cua p la c void EnCode(POINT p, CODE &c, RECT rWin) { c = 0; if(p.x rWin.Right) c |= RIGHT; if(p.y > rWin.Top) c |= TOP; if(p.y < rWin.Bottom) c |= BOTTOM; } // Hoan vi hai diem p1 va p2 sao cho p1 luon nam ngoai cua so void SwapPoint(POINT& p1, POINT &p2, CODE &c1, CODE &c2) { if(!c1) // Neu p1 nam hoan toan trong cua so { POINT p; p = p1; p1 = p2; p2 = p; CODE c; c = c1; c1 = c2; c2 = c; } } 64
65. // Tra ve TRUE neu co cat cua so. Nguoc lai tra ve FALSE int CohenSutherlandClipping(POINT P1, POINT P2, POINT &Q1, POINT &Q2, RECT rWin) { int fStop = FALSE, fResult = FALSE; CODE c1, c2; while(!fStop) { EnCode(P1, c1, rWin); EnCode(P2, c2, rWin); // Neu duong thang nam hoan toan ben trong cua so if(Accept(c1, c2)) { fStop = TRUE; // break fResult = TRUE; } // Accept else { // Neu duong thang nam hoan toan ben ngoai cua so if(Reject(c1,c2)) { fStop = TRUE; // break } // Reject else // Xet truong hop duong thang co the cat cua so { SwapPoint(P1, P2, c1, c2); float m; if(P2.x!=P1.x) m = float(P2.y-P1.y)/(P2.x-P1.x); if(c1 & LEFT) { P1.y += (rWin.Left-P1.x)*m; P1.x = rWin.Left; } // Left else { if(c1 & RIGHT) { P1.y += (rWin.Right-P1.x)*m; P1.x = rWin.Right; } // Right else { 65
66. if(c1 & TOP) { if(P2.x!=P1.x) P1.x += (rWin.Top - P1.y)/m; P1.y = rWin.Top; } // Top else // Bottom { if(P2.x!=P1.x) P1.x += (rWin.Bottom - P1.y)/m; P1.y = rWin.Bottom; } // Bottom } } } // Xet truong hop duong thang co the cat cua so } } //while Q1 = P1; Q2 = P2; return (fResult); } //CohenSutherlandClipping 4.2.2 Thut toán Liang - Barsky Thut toán Liang-Barsky c phát trin da vào vic phân tích dng tham s c a phng trình on th'ng. x = x1 + t.(x2 - x1) = x1 + t.Dx y = y1 + t.(y2 - y1) = y1 + t.Dy 4ng v$i m0i giá tr t, ta s& có mt im P tng ng thuc  ng th'ng. • Các im ng v$i t ≥ 1 s& thuc v tia P2x. • Các im ng v$i t ≤ 0 s& thuc v tia P2x’. • Các im ng v$i 0 ≤ t ≤ 1s& thuc v on th'ng . Hình 4.9: Phng trình tham s c a on th'ng 66
67. Tp hp các im thuc v ph n giao c a on th'ng và c!a s ng v$i các giá tr t th"a h bt phng trình : xmin ≤ x1 + tDx ≤ xmax ymin ≤ y1 + tDy ≤ ymax 0 ≤ t ≤ 1 ,t: p1 = -Dx, q1 = x1 - xmin p2 = Dx, q2 = xmax - x1 p3 = -Dy, q3 = y1 - ymin P4 = Dy, q4 = ymax - y1 Lúc này ta vit h phng trình trên d$i dng : À p .t ≤ q  k k k = {1, 2, 3, 4}  0 ≤ t ≤ 1 Nh vy vic tìm on giao thc cht là tìm nghim c a h bt phng trình này. Có hai kh n.ng xy ra ó là : • H bt phng trình vô nghim, ngh-a là  ng th'ng không có ph n giao v$i c!a s nên s& b loi b". • H bt phng trình có nghim, lúc này tp nghim s& là các giá tr t th"a t∈[t1, t2] ⊆ [0, 1]. Ta xét các tr ng hp : • Nu ∃k∈{1, 2, 3, 4}:(pk = 0) ∧ (qk 0, ta có t ≤ qk / pk . Vy nghim c a h bt phng trình là [t1, t2] v$i : À ¤ Œ qk Œ t1 = max( à , p 0‹ ∪ {1}) Œ k Œ Õ pk › t1 ≤ t2 Nu h trên có nghim thì on giao Q1Q2 s& là: Q1(x1 + t1Dx, y1 + t1Dy), Q2(x1 + t2Dx, y1 + t2Dy) Nu xét thut toán này  khía cnh hình hc ta có : 67
68. • Tr ng hp ∃k∈{1, 2, 3, 4}:(pk = 0) ∧ (qk 0,  ng th'ng s& có h$ng i t bên trong c!a s i ra. Do ó hai  u mút c a on giao s& ng v$i các giá tr t1, t2 c tính nh sau : Giá tr t1 chính là giá tr l$n nht c a các rk = qk/pk mà pk 0 ( ng th'ng i t trong c!a s i ra) và 1. Hình 4.10 – Xét v$i biên trái on th'ng P1P2 có h$ng i t ngoài vào trong, nhng so v$i biên phi on th'ng P’1P’2 li có h$ng i t trong c!a s i ra Khi cài ,t thut toán Liang-Barsky, ban  u các giá tr t1, t2 c khi to là t1 = 0 và t2 = 1. V$i m0i l n xén on th'ng v$i mt biên c a c!a s, các giá tr p, q s& c truyn cho hàm ClipTest  xác  nh on th'ng có b loi b" hay b xén b$t mt on hay không. Khi p 0, r dùng  cp nht t2. Khi cp nht t1 và t2 nu t1> t2, on th'ng s& b loi b". Ngoài ra nu (p=0 và q<0), chúng ta c/ng s& loi b" on th'ng vì nó song song và n
    m ngoài c!a s. Nu on th'ng không b loi b" sau bn l n gi v$i các tham s p, q tng ng v$i các biên c a c!a s, các giá tr t1 và t2 s& c dùng  suy ra ta  hai im  u mút c a on giao. 68
69. Cài "t minh ha thut toán Liang - Barsky trên ngôn ng# C // Tra ve TRUE neu khong xay ra truong hop nam ngoai cua so int ClipTest(int p, int q, float &t1, float &t2) { float r; if (p t2) return FALSE; else if (r>t1) t1 = r; } else { if (p>0) { r = float(q)/p; if (r<t1) return FALSE; else if (r<t2) t2 = r; } else // p=0 { if (q<0) return FALSE; } } return TRUE; } int LiangBarskyClipping(POINT P1, POINT P2, RECT R, POINT *Q1, POINT *Q2) { float t1, t2; int Dx, Dy, x1, y1, x2, y2, xmin, ymin, xmax, ymax; t1 = 0; t2 = 1; x1 = P1.x; y1 = P1.y; x2 = P2.x; y2 = P2.y; Dx = x2 - x1; Dy = y2 - y1; 69
70. xmin = R.Left; ymin = R.Top; xmax = R.Right; ymax = R.Bottom; if (ClipTest(-Dx, x1 - xmin, t1, t2)) // Giai he bat phuong trinh 1 { if (ClipTest(Dx, xmax - x1, t1, t2)) // Giai he bat phuong trinh 2 { if (ClipTest(-Dy, y1 - ymin, t1, t2)) // Giai he bat phuong trinh 3 { if (ClipTest(Dy, ymax - y1, t1, t2)) // Giai he bat phuong trinh 4 { Q1.x = x1 + t1. Dx; Q1.y = y1 + t1. Dy; Q2.x = x1 + t2. Dx; Q2.y = y1 + t2. Dy; return TRUE; } // Giai he bat phuong trinh 4 } // Giai he bat phuong trinh 3 } // Giai he bat phuong trinh 2 } // Giai he bat phuong trinh 1 return FALSE; } // LiangBarskyClipping • Nhn xét Nói chung, thut toán Liang-Barsky cho tc  tt hn thut toán Cohen- Sutherland vì rút gn c s giao im c n tính. M0i l n cp nht các giá tr t1, t2, ch+ c n mt phép chia, và giao im c a on th'ng v$i c!a s ch+ c tính duy nht mt l n sau khi ã tìm ra c giá tr t1, t2. Trong khi ó thut toán Cohen-Sutherland ôi lúc phi tính giao im cho các im không n
    m trong biên c a c!a s òi h"i nhiu phép toán hn. 70
71. Chng 5 Tng quan v  ha 3D Các i tng trong th gi$i thc ph n l$n là các i tng ba chiu, nên vic th hin các i tng ba chiu trên máy tính là mt công vic ht sc c n thit  a tin hc g n g/i v$i thc t hn. C/ng ging nh các cách biu di)n các i tng ba chiu trên m,t ph'ng khác (nh c a máy nh, camera, ), biu di)n b
    ng máy tính c/ng phi tuân theo các quy lut v phi cnh, sáng, ti, nh
    m giúp ng i xem có th tng tng li hình nh mt cách g n úng nht. Ngoài ra biu di)n trên máy tính có u th giúp ta có th quan sát i tng  nhiu góc cnh khác nhau,  các khong cách khác nhau. Chng này s& gi$i thiu mt s k- thut biu di)n các i tng ba chiu trên máy tính, t các i tng n gin nh các hình khi, các a din, n các i tng tng i phc tp nh các m,t ã c tìm hiu  các chng tr$c. 5.1 Khái quát chung Khi chúng ta mô hình hóa và hin th mt cnh ba chiu, ta c n phi xem xét rt nhiu khía cnh và vn  khác nhau ch không n gin là thêm vào ta  th ba cho các i tng. B m,t i tng có th xây dng bi nhiu t hp khác nhau c a các m,t ph'ng và các m,t cong. Ngoài ra, ôi khi chúng ta c/ng c n mô t mt s thông tin v bên trong các i tng. Các công c h0 tr  ha (graphics package) th ng cung cp mt s hàm hin th các thành ph n bên trong, nhng  ng nét tiêu biu ho,c hin th mt ph n c a i tng ba chiu (solid object). Ngoài ra, các phép bin i hình hc th ng c s! dng nhiu hn và a dng hn trong  ha ba chiu so v$i trong  ha hai chiu. Phép bin i h quan sát trong không gian ba chiu phc tp hn nhiu so v$i trong không gian hai chiu do chúng ta phi chn la nhiu tham s hn khi mô t mt cnh ba chiu s& xut hin trên màn hình nh th nào. Hình 5.1: Mt khung cnh trong  ha ba chiu 71
72. Các mô t v mt cnh ba chiu phi i qua mt quy trình x! lí gm nhiu công on nh phép bin i h ta  quan sát và phép chiu chuyn cnh t h ta  quan sát ba chiu xung h ta  thit b hai chiu. Nhng ph n nhìn thy c c a cnh, ng v$i mt h quan sát c chn nào ó, phi c xác  nh và cui cùng, các thut toán v& m,t s& c áp dng nh
    m to ra hình nh trung thc (g n v$i thc t) c a cnh. 5.1.1 S lc v quy trình hin th Quy trình x! lí thông tin trong  ha ba chiu là mt chu0i các b$c ni tip nhau, kt qu c a m0i b$c s& là  u vào c a b$c tip theo. Hình 5.2: Quy trình hin th i tng ba chiu Quy trình b#t  u b
    ng vic xây dng các mô hình i tng. Các mô hình này th ng c mô t trong không gian ba chiu (x,y,z). Các mô hình th ng th hin vt th (solid) ho,c b m,t (boundaries) c a i tng. Nh vy ta có hai kiu mô hình hóa. Trong solid modeling các i tng  ha c s th ng c dùng  mô t các i tng có th tích (volume). Trong boundary representations(B-reps), các i tng c  nh ngh-a bi b m,t c a chúng. Các mô hình th ng c biu di)n trong mt h ta  cc b, mà ta gi là h ta  i tng. Trong h ta  này ch+ có bn thân i tng c  nh ngh-a, vì vy gc ta  và n v o l ng th ng c chn sao cho vic biu di)n i tng tin li nht. B$c  u tiên trong quy trình hin th là bin i i tng t không gian i tng (object-space) vào mt không gian chung gi là không gian thc (world space). Trong không gian này các i tng, ngun sáng, và ng i quan sát cùng tn ti. B$c này c gi là giai on bin i mô hình (modeling transformation). 72
73. B$c tip theo là mt b$c ti u hóa. Trong giai on loi b" n gin (trivial rejection) ta c n loi tr tt c các i tng không th nhìn thy. iu này giúp chúng ta tránh c vic x! lí mt s ph n không c n thit c a cnh (scene) mà ta ang chu%n b hin th  các b$c sau. Tip theo ta phi chiu sáng (illumination) các i tng có th nhìn thy c b
    ng cách gán cho chúng màu s#c da trên các ,c tính c a các cht to nên vt và các ngun sáng tn ti trong cnh. Sau khi chiu sáng, ta phi thc hin mt phép bin i h ta   ,t v trí quan sát (viewing position) v gc ta  và m,t ph'ng quan sát (viewing plane) v mt v trí mong $c. B$c này gi là b$c i h quan sát. Sau b$c này, các i tng c chuyn t không gian thc sang không gian quan sát (eye space). Trong không gian quan sát, ta phi thc hin vic xén các i tng trong khung cnh  cnh n
    m gn trong mt ph n không gian chóp ct mà ta gi là viewing frustum. B$c này s& loi b" hoàn toàn các i tng (các mnh i tng) không nhìn thy c trong nh. B$c tip theo ta s& chiu các i tng xung m,t ph'ng hai chiu. B$c Projection thc hin phép bin i t không gian quan sát sang không gian màn hình (screen-space). Trong b$c r i rc hóa (rasterization) ta s& chuyn i tng thành các pixel. Cui cùng, toàn cnh s& c hin th lên màn hình. 5.1.2 Mô hình khung ni kt A. Khái nim Mt phng pháp thông dng và n gin  mô hình hóa i tng là mô hình khung ni kt. Mt mô hình khung ni kt gm có mt tp các +nh và tp các cnh ni gia các +nh ó. Khi th hin b
    ng mô hình này, các i tng ba chiu có v: r0ng và không ging thc t l#m.  hoàn thin hn, ng i ta dùng các k- thut to bóng và loi b" các  ng và m,t khut. (Chúng ta s&  cp vn  này  các chng sau). Tuy nhiên v& b
    ng mô hình này th ng nhanh nên ng i ta th ng dùng nó trong vic xem phác tho (preview) các i tng, ,c bit là trong các h CAD. B. Biu di)n các vt th ba chiu b$ng mô hình khung ni kt V$i mô hình khung ni kt, hình dng c a i tng ba chiu c biu di)n b
    ng hai danh sách (list) : danh sách các +nh (vertices) và danh sách các cnh (edges) ni các +nh ó. Danh sách các +nh cho bit thông tin hình hc ó là v trí các +nh, còn danh sách các cnh xác  nh thông tin v s kt ni, nó cho bit c,p các +nh to ra cnh. Chúng ta hãy quan sát mt vt th ba chiu c biu di)n b
    ng mô hình khung ni kt nh sau : 73
74. Bng danh sách các cnh và  nh biu din v t th: Vertex List Edge List Vertex x y z Edge Vertex1 Vertex2 1 0 0 0 back 1 1 2 side 2 0 1 0 2 2 3 3 0 1 1 3 3 4 4 0 0.5 1.5 4 4 5 5 0 0 1 5 5 1 6 1 0 0 front 6 6 7 side 7 1 1 0 7 7 8 8 1 1 1 8 8 9 9 1 0.5 1.5 9 9 10 10 1 0 1 10 10 6 11 1 6 12 2 7 13 3 8 14 4 9 15 5 10 16 2 5 17 1 3 74
75. Hình 5.3: Vt th ba chiu c biu di)n b
    ng mô hình khung ni kt Có nhiu cách  ,c t mô hình khung ni kt trên máy tính nh dùng xâu, mng, và m0i cách u có các u im riêng trong tng ng dng c th. 3 ây ta minh ha các biu di)n mô hình khung ni kt b
    ng cu trúc d liu mng trong ngôn ng lp trình C nh sau: #define MAXVERTS 50 //s +nh ti a có th biu di)n #define MAXEDGES 100 //s cnh ti a typedef struct { float x, y, z; } POINT3D; typedef struct { int NumVerts; //S +nh trong mô hình int NumEdges; //S cnh trong mô hình POINT3D Vert[MaxVerts]; int Edge[MaxEdges][2]; }WIREFRAME; Ngoài ra, ôi khi trong mô hình wireframe ng i ta còn mô t các m,t (ph'ng) c a i tng. M0i m,t c  nh ngh-a bi mt a giác bao. Ví d, i tng trong hình 5.3 có 7 m,t. 5.1.3 V các i tng theo mô hình khung ni kt s! d$ng các phép chiu  v& các i tng biu di)n b
    ng mô hình khung ni kt, n gin chúng ta ch+ c n v& các cnh trong danh sách các cnh mà thôi. Tuy nhiên do các +nh và cnh u c  nh ngh-a trong ba chiu nên vn  ,t ra  ây là làm th nào  v& các  ng th'ng ba chiu trong m,t ph'ng hai chiu.  làm iu này, chúng ta phi thc hin phép chiu t ba chiu vào hai chiu  b" b$t mt chiu. Có hai loi phép chiu n gin th ng dùng ó là phép chiu song song (parallel projection) và phép chiu phi cnh (perspective projection). Phép chiu song song s! dng các  ng th'ng song song i qua các +nh c a i 75
76. tng, trong khi ó phép chiu phi cnh dùng các  ng th'ng qua các +nh c a i tng hi t v mt im gi là tâm chiu (center of projection). Các  ng th'ng trên c gi là tia chiu và giao im c a các  ng th'ng này v$i m,t ph'ng chiu (hay còn gi là m,t ph'ng quan sát (view plane)) chính là các hình chiu c a các +nh hay còn gi là im chiu. Trong ph n này, chúng ta gi s! r
    ng m,t ph'ng chiu là m,t ph'ng z = 0. Phép chiu song song bo toàn c mi quan h gia các chiu c a i tng, ây chính là k- thut c dùng trong phác tho  to ra ph n khung c a i tng ba chiu. Ng i ta dùng phng pháp này  quan sát chính xác  các m,t khác nhau c a i tng. Tuy nhiên, phép chiu song song không cho mt biu di)n thc c a i tng ba chiu. Trong khi ó, phép chiu phi cnh to ra c biu di)n thc hn nhng li không bo toàn c mi liên h gia các chiu. Các  ng th'ng càng xa s& có các nh chiu nh" hn. Nói chung, k- thut  v& mt  ng th'ng ba chiu là : • Chiu m0i im  u mút thành các im hai chiu. • V&  ng th'ng ni hai im nh qua phép chiu. Hình 5.4: Phép chiu song song (a) và phép chiu phi cnh (b) S d- chúng ta làm c iu này vì các phép chiu mà chúng ta s! dng bo toàn  ng th'ng. 5.1.4 Phép chiu song song (Parallel Projection) Khi h$ng c a tia chiu vuông góc v$i m,t ph'ng chiu ta có phép chiu trc giao (orthographic projection). Ngc li, ta có phép chiu xiên (oblique projection). A. Phép chiu trc giao Xét im ba chiu P(Px, Py, Pz), cách n gin nht là b" i thành ph n z  chiu P thành P'(Px, Py). iu này tng ng v$i chiu im ó lên m,t ph'ng xy theo phng c a trc z. M,t ph'ng xy là m,t ph'ng quan sát. Xem hình v& minh ha 5.5,  ây im chiu chính là giao im c a tia a qua P và song song v$i trc z vuông góc v$i m,t ph'ng xy. Tia a là tia chiu. D) dàng thy r
    ng phép chiu này bo toàn  ng th'ng. 76