Bài giảng Khử đường và mặt khuất

CH
NG VII KH 
NG VÀ MT KHUT 7.1. CÁC KHÁI NIM M
t vt th 3D có th biu din trong máy tính bng nhiu mô hình khác nhau, song hai mô hình ph bin nh t ó là mô hình khung dây (WireFrame) và mô hình các m
t a giác ( Polygon mesh model) • Mô hình WireFrame: ã trình bày  ch ng 5, nó cho ta hình dáng ca vt th d i dng m
t b
khung • Mô hình các mt a giác:  ây m
t vt th 3D c xác nh thông qua các mt (thay vì các cnh nh trong mô hình WireFrame), và mi m
t mt li c xác nh thông qua các im mà các im này c xem nh là các nh ca mt a giác, vi mô hình các mt a giác thì chúng ta không ch to ra c hình dáng ca vt th nh mô hình Wireframe mà còn th hin c các c tính v màu sc và nhiu tính ch t khác ca vt th. Song  có th mô t vt th 3D m
t cách trung thc (nh trong th gii thc) thì òi hi ng i lp trình phi tính toán và gi lp nhiu thông tin, mà m u cht là v n  kh mt khu t và chiu sáng.Trong ch ng này chúng ta s tp trung nghiên c u v n  kh mt khu t. Ví d!: Mô t vt th nh trong hình 7.1. - Danh sách các nh: 1,2,3,4,5,6 - Danh sách các mt c xác nh theo bng sau: Mt nh 1 2 3 4 5 6 Mt 3 Mt 1 Mt 4 Mt 5 Mt 2 Hình 7.1 Ch
ng VII. Kh ng và m t khut 84 1 2 3 4 5 1,2,3 4,5,6 1,3,6,4 3,2,5,6 1,2,5,4 Chúng ta có th a ra nhiu c u trúc d" liu khác nhau  l u tr" cho a giác. D i ây là phát tho m
t kiu c u trúc: Type Point3D = Record {im 3 chiu} x,y,z:real; end; Vector3D = Record {Vector 3 chiu. Mc dù nó ging vi x,y,z:real; Point3D song ta v n khai  các thut toán end;
c t
ng minh} RGBColor = Record {Cu trúc màu sc ca mt mt} B,G,R:Byte; end; KieuMat = Record PhapVT:Vector3D; {Pháp vector ca mt} Sodinh:cardinal; {S nh ca mt} List:array of integer;{Danh sách th t các nh to nên mt.  ây ta dùng mng ng} Color:RGBColor; {màu sc ca mt} end; Obj3D = record {i t
ng 3 chiu} ObjName:string; {Tên ca i t
ng} Sodinh:cardinal; {S nh} Dinh: array of point3d; {Danh sách nh.  ây ta dùng kiu mng ng} SoMat:cardinal; {S mt} Mat:array of KieuMat; {Danh sách mt} Ch
ng VII. Kh ng và m t khut 85 Xworld,Yworld,Zworld,Zoom:Real; {To  và kích th
c tht ca vt trong h to  th gii} end; Khi cài t cho m
t ng d!ng c! thì vic s d!ng mng c nh có th gây ra các tr ngi v kích th c ti a hay ti thiu, c#ng nh vic s d!ng b
nh không ti u. Vì th ngoài cách dùng mng c nh, ta có th dùng mng
ng trong m
t s ngôn ng" nh Visual Basic, Delphi hay Visual C++,… hoc dùng c u trúc danh sách móc ni. Song song vi iu ó là vic bt i hay a thêm các thu
c tính c$n thit  biu din các c tính khác ca mt hay ca i t ng. * Vn  kh m t khut Khi th hin vt th 3D, m
t v n  ny sinh là làm sao ch th hin các mt có th nhìn th y c mà không th hin các mt khu t phía sau. Vic m
t mt b khu t hay không b khu t thì tu% thu
c vào c u trúc các mt ca vt th và v trí ca im nhìn c#ng nh bi cnh mà vt th ó c t vào. 7.2. CÁC PH
NG PHÁP KH MT KHUT 7.2.1. Gii thut ngi th sn và sp xp theo chiu sâu (Depth-Sorting) Ng i th sn (hay Depth-sorting) là tên ca m
t thut gii n gin nh t trong s các thut toán v nh thc 3 chiu. Nu  ý ng i th sn làm vic, chúng ta s th y anh ta sn b c tranh t& trong ra ngoài, vi các cnh vt t& xa n g$n. Chúng ta có th áp d!ng m
t cách t ng t  v các a giác trong danh sách các a giác. Song có m
t v n  c$n phi ch'n la, ó là m
t a giác t(n ti trong không gian 3D có ti ba bn nh, và nh"ng nh này có th có các giá tr z ( giá tr
sâu ) khác nhau. Chúng ta s không bit ch'n giá tr nào trong s chúng. T& nh"ng kinh nghim trong thc t, ng i ta cho rng nên s d!ng giá tr z trung bình s cho kt qu tt trong h$u ht các tr ng hp. Nh vy, chúng ta c$n phi sp xp các mt theo th t t& xa n g$n, r(i sau ó v các mt t& xa tr c, r(i v các mt  g$n sau, nh th thì các mt  g$n s không b che khu t bi các mt  xa, mà ch có các mt  xa mi có th b các mt  g$n che khu t, do các mt  g$n v sau nên có th c v ch(ng lên hình nh ca các mt xa. Ch
ng VII. Kh ng và m t khut 86 Nh vy, thut gii Depth-Sorting c thc hin m
t cách d dàng khi chúng ta xác nh m
t giá tr
sâu (là giá tr z trong h to
quan sát) i din cho c mt. Các mt da vào
sâu i din ca mình  so sánh r(i sp xp theo m
t danh sách gim d$n (theo
sâu i din). B c tip theo là v các mt lên mt ph)ng theo th t trong danh sách. Gii thut còn m
t s v ng mc sau (hình 7.2): Khi hai mt ct nhau thì thut gii này ch th hin nh chúng ch(ng lên nhau. Hình 7.2 Khi hai mt  trong cùng m
t khong không gian v
sâu và hình chiu ca chúng lên mt ph)ng chiu ch(ng lên nhau (hay ch(ng m
t ph$n lên nhau). Ch)ng hn nh :

 
 
Hình 7.3 T& nh"ng ví d! trên chúng ta có th th y rng, có nh"ng tr ng hp các a giác c sp xp sai d*n n kt qu hin th không úng. Liu chúng ta có th khc ph!c c v n  này không? Câu tr li d+ nhiên là có nh ng c#ng (ng ngh+a là chúng ta s phi x lý thêm r t nhiu các tr ng hp và làm t,ng
ph c tp tính toán. • Phép kim tra phn kéo dài Z Hình nh tht Khi v bng gii thut trên Ch
ng VII. Kh ng và m t khut 87 Phép kim tra này nhm xác nh ph$n kéo dài z ca hai a giác có gi lên nhau hay không? Nu các ph$n kéo dài Z là gi lên nhau r t có th các a giác này c$n c hoán i. Vì th phép kim tra tip theo phi c thc hin. • Phép kim tra phn kéo dài X Phép kim tra này t ng t nh phép kim tra tr c, nh ng nó s kim tra ph$n kéo dài X ca hai a giác có gi lên nhau hay không? Nu có, thì r t có th các a giác này c$n c hoán i. Vì th phép kim tra tip theo phi c thc hin. • Phép kim tra phn kéo dài Y Phép kim tra này kim tra ph$n kéo dài Y ca hai a giác có gi lên nhau hay không? Nu có, thì r t có th các a giác này c$n c hoán i. Vì th phép kim tra tip theo phi c thc hin. • Phép kim tra cnh xa Gi s A và B là hai a giác mà sau khi sp xp theo
sâu trung bình thì A ng tr c B. Song qua 3 phép kim tra trên mà v*n không xác nh c liu trt t trên là úng hay ch a. Lúc này chúng phi tin hành phép kim tra cnh xa. Phép kim tra cnh xa nhm xác nh xem a giác B có nm phía sau cnh xa ca a giác A hay không? Nu có thì trt t này là úng, ng c li thì phi qua b c kim tra tip theo.  kim tra a giác B có nm sau cnh xa ca a giác A hay không, chúng ta thc hin vic kim tra mi nh ca a giác B. Các nh này u nm v cùng m
t phía ca a giác A theo chiu tr!c Z không? Nu úng thì kt qu trt t trên là úng. Ng c li, có th xy ra m
t trong hai tình hung nh hình (7.2) hoc hình (7.3),  xác nh c ta phi tip t!c sang b c kim tra tip theo. • Phép kim tra cnh gn Phép kim tra cnh g$n nhm xác nh xem a giác A có nm phía sau cnh g$n ca a giác B hay không? Nu có thì trt t xác nh tr c ây không Ch
ng VII. Kh ng và m t khut 88 úng, chúng ta c$n phi hoán i li trt t. Ng c li thì rõ ràng hai a giác ang ct nhau (nh hình 7.2) hoc chéo vào nhau (hình 7.4), lúc này chúng ta phi tin hành chia nh hai a giác A và B thành 3 (hoc 4) a giác con, ng chia ct chính là ng giao ct ca 2 a giác. Sau phép chia chúng ta tin hành sp xp li các a giác con. Hình 7.4 7.2.2. Gii thut BackFace S r t n gin nu ta dùng Vector pháp tuyn  kh các mt khu t ca m
t i t ng 3D c và l(i. Ta s tính góc gi"a véc t h ng nhìn V và pháp vector N ca mt, nu góc này là ln hn 90o thì mt là không nhìn th y (b khu t), ng c li thì mt là kh kin. D u ca tích vô h ng ca 2 vector là d ng nu góc gi"a chúng nh hn hay bng 90 o . Vy thut toán  xét m
t mt b khu t hay không ch n gin là: If V.N >= 0 then M t thy Else M t không thy (m t khut); Vì υ<90 o nên mt quan sát c υ Mt nhìn Vector h ng nhìn Hình 7.5 Ch
ng VII. Kh ng và m t khut 89
Hình 7.6 Cài t minh ho cho thut toán chn lc m t sau Function Tich_vo_huong(v,n:Vector3D):real; {Tính tích vô h
ngca 2 vector} Begin Tich_vo_huong:=v.x*n.x+v.y*n.y+v.z*n.z; End; Procedure DrawObj_FilterRearFace(Obj:Obj3D; Canvas:TCanvas;Width,Height:integer; Zoom:real;V:Vector3D); {V i t
ng theo thut toán chn lc mt sau. Trong ó: + Obj: cha i t
ng 3D cn v + Canvas: Vi v (hay vùng m khung) + Width, Height: Kích th
c ca Canvas + Zooom: H s t l khi v i t
ng (Hay h s thu phóng) + V: Vector h
ng nhìn. Nu Obj ã
c chuyn sang h to  quan sát O’UVN thì V=(0,0,-1)} Var i,k,P,cx,cy:integer; Poly:array of TPoint; begin cx:=Width div 2;cy:=Height div 2; {Duyt qua tt c các mt ca i t
ng} Ch
ng VII. Kh ng và m t khut 90 For k:=0 to Obj.SoMat-1 do if Tich_vo_huong(v,Obj.Mat[K].PhapVT)>= 0 then {Mt kh kin} begin setlength(Poly,Obj.Mat[K].Sodinh); {Thit lp  dài ca mng Poly bng s nh ca a giác} For i:=0 to Obj.Mat[K].Sodinh -1 do {
a to  các nh ca a giác vào Poly} begin P:=Obj.Mat[K].list[i]; Poly[i].X:=round(Obj.dinh[P].x*zoom)+cx; Poly[i].Y:=-round(Obj.dinh[P].y*zoom)+cy; end; {Thit lp màu cho bút tô tr
c khi tô} canvas.Brush.Color:=rgb(Obj.Mat[K].Color.R, Obj.Mat[K].Color.G,Obj.Mat[K].Color.G); Canvas.Polygon(poly); {Tô a giác vi màu ã
c thit lp} end; setlength(poly,0); end; Rõ ràng, thut toán r t n gin và
ph c tp tính toán không cao. Song khi s d!ng phi luôn m bo rng i t ng có t tính là “
c và li”, nu i t ng không tho mãn iu kin ó thì chúng ta phi áp d!ng m
t thot toán khác hay có nh"ng sa i c$n thit  tránh s th hin sai lc. 7.2.3. Gii thut vùng m  sâu (Z-Buffer) Bng cách tính giá tr
sâu (là giá tr Z trong h to
quan sát) ca mi im trong t t c các mt a giác, ti mi im trên mt ph)ng chiu có th có nh ca nhiu im trên nhiu mt a giác khác nhau, song hình v ch c th hin hình nh ca im có
sâu th p nh t ( t c là im  g$n nh t). Vi cách thc hin này gii thut có th kh c t t c các tr ng hp mà các gii thut khác mc phi. Ch
ng VII. Kh ng và m t khut 91 Gii hn ca ph ng pháp này là òi hi nhiu b
nh và thc hin nhiu tính toán. Z-Buffer là m
t b
m dùng  l u
sâu cho mi pixel trên hình nh ca vt th, thông th ng ta t ch c nó là m
t ma trn hình ch" nht. Nu dùng 1 byte  biu din
sâu ca m
t pixel, thì m
t vt th có hình nh trên mt ph)ng chiu là 100x100 s c$n 10000 byte dùng  làm Depth Buffer, và khi ó vùng m
sâu s cho phép ta phân bit c 256 m c sâu khác nhau, iu này có ngh+a là nu có 257 pixel  257
sâu khác nhau thì khi ó bu
t ta phi quy 2 pixel nào ó v cùng m
t
sâu. Nu ta dùng 4 byte  biu din
sâu ca m
t pixel, thì khi ó vùng m
sâu s cho phép ta phân bit c 4294967296 (232) m c sâu khác nhau, song lúc ó s phi c$n 40000 byte cho m
t b
m kích th c 100x100. Do tính ch t 2 mt này nên tu% vào tình hung và yêu c$u mà ta có th t,ng hay gim s byte  l u gi"
sâu ca 1 pixel. Và thông th ng ng i ta dùng 4 byte  l u gi"
sâu ca m
t im, khi ó thì
chính xác r t cao. M
t câu hi có th t ra là làm sao có th tính
sâu ca mi im trong a giác. - ây có 2 ph ng pháp: ph ng pháp trc tip và ph ng pháp gián tip. • Ph ng pháp trc tip s tính
sâu ca mi im da vào ph ng trình mt ph)ng ch a a giác. Vi ph ng pháp này chúng ta c$n duyt qua t t các im ca a giác (t t nhiên ch h"u hn im), bng cách cho các thành ph$n x và y, nu cp giá tr (x,y) tho trong min gii hn ca a giác thì chúng ta s tìm thành ph$n th 3 là z bng cách thay th x và y vào ph ng trình mt ph)ng  tính ra thành ph$n z. V mt toán h'c thì ph ng pháp trc tip rõ ràng là r t khoa h'c, song khi áp d!ng ta s gp phi v ng mc: C$n phi tính bao nhiêu im  hình nh th hin ca a giác lên mt ph)ng chiu  mn và c#ng không b tình trng quá mn (t c là v r t nhiu im ch(ng ch t lên nhau không c$n thit mà li gây ra tình trng chm chp và t,ng
ph c tp tính toán. C#ng nên nh rng khi th hin m
t a giác lên mt ph)ng chiu thì nh ca nó có th c phóng to hay thu nh). • Ph ng pháp gián tip: Chúng ta s tính
sâu ca m
t im gián tip thông qua
sâu ca các im lân cn.  thc hin chúng ta tin hành theo các b c sau: Ch
ng VII. Kh ng và m t khut 92 G'i G là m
t mt a giác c biu din bi tp các im P1, P2, … Pn và G’ là hình chiu ca G xung mt ph)ng chiu vi tp các nh P1’,P2’,… Pn’.  th hin hình nh ca G lên mt ph)ng chiu thì rõ ràng là chúng ta phi tin hành tô a giác G’. Song nh thut toán ã phát biu, chúng ta c$n xác nh xem mi im M’ b t k% thu
c G’ là nh ca im M nào trên G và da vào
sâu ca M  so sánh vi
sâu ã có trong z- buffer  quyt nh là có v im M’ hay không. Nu ta gán thêm cho các im nh m
t thành ph$n n"a, ó là giá tr
sâu ca im to nh (t c là im ã to ra im nh sau phép chiu) thì lúc này ta không c$n thit phi xác nh M  tính
sâu, mà ta có th tính c giá tr
sâu này qua công th c sau: Nu M’ nm trên on th)ng P’Q’ vi t. l là: P’M’/P’Q’=t và nu bit c
sâu ca P’ và Q’ l$n l t là z(P’) và z(Q’) thì
sâu mà im nh M’ nhn c là z(M’)=z(P’)+(z(Q’)-z(P’))t (2.3.1) Ta có th s d!ng c công th c trên vi t t c các phép chiu có bo toàn ng th)ng. T& ó ta có th xác nh quy trình v a giác G’ là nh ca G nh sau: + Gán thêm cho mi im nh ca a giác G’ m
t thành ph$n z có giá tr bng
sâu ca im to nh. Có ngh+a là P’1 s ch a thêm giá tr z(P1), P’2 s ch a thêm giá tr z(P2), hay m
t cách tng quát P’i s ch a thêm giá tr z(Pi) vi i=1..n. Tin hành tô a giác G’ theo m
t quy trình t ng t nh thut toán tô a giác theo dòng quét. Có ngh+a là cho m
t dòng quét chy ngang qua a giác, ti mi v trí b t k% ca dòng quét, chúng ta tin hành tìm tp các giao im ca dòng quét vi a giác. G'i {xm} là tp các giao im, m
t iu c$n chú ý là ta c$n tính
sâu cho các giao im này. Gi s xi là giao im ca ng quét vi cnh Pi’Pj’ th thì ta có th tính ra
sâu ca xi thông qua công th c (2.3.1) nh sau: Ch
ng VII. Kh ng và m t khut 93 Nu g'i yscan là giá tr tung
ca dòng quét th thì: z(xi) = z(Pi’)+z(Pj’)*[(yscan – y(Pi’))/(y(Pj’)-y(Pi’))] (2.3.2) {trong ó y(P) là thành ph$n to
y ca im P} Rõ ràng qua công th c trên ta th y, nu xi là trung im ca Pi’Pj’ thì z(xi) = z(Pi’)+z(Pj’)*1/2 Cài t minh ho cho gii thut “vùng m  sâu” T& nh"ng phân tính trên chúng ta có th tin hành khai báo các c u trúc d" liu c$n thit và cài t cho thut toán. • Khai báo các c u trúc d" liu c$n thit: Sau ây là các khai báo c$n thit  cho phép l u tr" m
t i t ng 3D theo mô hình các mt a giác, cùng các khai báo c$n thit  tin hành kh mt khu t theo thut toán z-Buffer theo ngôn ng" Pascal trong môi tr ng ca trình biên dch Delphi {Bt $u ph$n khai báo ph!c v! cho gii thut Z-buffer} Type Z_BufferType=Array of Array of cardinal; {Kiu b m Z, ây là mt mng ng 2 chiu mà mi phn t có kiu cardinal, iu ó có ngh!a là vùng m  sâu s cho phép ta phân bit
c 4294967296 (232) mc sâu khác nhau} NutPoly_Z=record {Cu trúc ca mt nh ca a giác chiu G’ } x,y:Integer; {To  ca nh trên mt ph"ng chiu} z:real; {Thành phn  sâu i kèm (là  sâu ca to nh)} end; Polygon_Z =array of NutPoly_Z; {a giác chiu là mt mng ng. Nh
mt a giác 2 chiu, song mi mt nh có cha thêm thành phn  sâu ca nh} CanhCat_Z=record {Cu trúc ca các cnh a giác
c xây dng nhm ph#c v# cho quá trình tính giao im} y1,y2:Integer; {Tung  bt u và kt thúc ca mt cnh (y1<=y2)} Ch
ng VII. Kh ng và m t khut 94 xGiao:real; {hoành  xut phát ca cnh. Song trong quá trình tính toán nó s là tung  giao im ca cnh vi
ng quét ngang} xStep:real; {Giá tr$ thay %i ca x khi y thay %i 1 n v$, nó cho bit  dc ca cnh} zGiao:real; {Giá tr$  sâu ti im xut phát ca cnh. Song trong quá trình tính toán nó s là giá tr$  sâu ca giao im vi
ng quét ngang} zStep:real; {Giá tr$  sâu ca giao im tip theo so vi giá tr$  sâu ca giao im tr
c ó s chênh lch nhau mt khong là zStep} end; DanhSachCanhCat_Z=array of CanhCat_Z; {Danh sách các cnh
c to ra t& a giác chiu G’, danh sách này nhm ph# v# cho quá trình tính toán các giao im vi
ng quét c'ng nh
 sâu ca mi giao im} GiaoDiem_Z=record {L
u to  giao im và  sâu t
ng ng vi giao im ó} x,y:Integer; {To  giao im} z:real; {Giá tr$  sâu} ChiSoCanh:integer; {Ch s cnh ct to ra giao im (Nhm m#c ích kh các giao im th&a)} end; DanhsachGiaoDiem_Z=array of GiaoDiem_Z; {Kt thúc ph$n khai báo ph!c v! cho gii thut Z-buffer} Procedure DrawObj(Obj:Obj3D; Zmin,ZMax:Real; Z_Buffer:Z_BufferType; Canvas:TCanvas; Width,Height:integer; Zoom:real); {u vào: + i t
ng 3D cha trong Obj + Gii hn  sâu trong không gian mà ch
ng trình x lý là t& Zmin n Zmax. Ta s thc hin ánh x các giá tr$  sâu tính
c ca các im trên a Ch
ng VII. Kh ng và m t khut 95 giác sang on 0..4294967294. Bit rng  sâu Zmin ng vi 0 và Zmax ng vi 4294967294. (  sâu 4294967295 làm giá tr$ mc $nh cho các im nn + Z_Buffer: là ma trn cha  sâu các im nh ca các i t
ng ã th hin trên Canvas (xem nh
là mt ph"ng chiu). Nu ta ch
a v i t
ng nào tr
c ó thì Z_Buffer
c kh(i ng là 4294967295 Canvas: Tm vi v. Chúng ta s thc hin v hình nh ca i t
ng lên Canvas. Width,Height: Là chiu rng và cao ca Canvas + Zoom: t l th hin i t
ng lên Canvas sau khi thc hin phép chiu, ta có th hiu nôm na là t l thu phóng.} Var i,k,P,cx,cy:integer; Poly:Polygon_Z; CuongDoSang:Real; Color:Tcolor; Begin cx:=Width div 2;cy:=Height div 2; For k:=0 to Obj.SoMat-1 do {Duyt qua tt c các mt a giác} begin setlength(Poly,Obj.Mat[K].Sodinh); {Thit lp s phn t ca Poly bng s nh ca mt mà nó sp cha} For i:=0 to Obj.Mat[K].Sodinh -1 do {Duyt qua tt c các nh ca mt và thit lp giá tr$ cho mi nh ca Poly} begin P:=Obj.Mat[K].list[i]; {nh th i trong a giác K s là nh th P trong danh sách nh ca Obj} {Dùng phép chiu trc giao  chiu im Obj.dinh[P] xung mt ph"ng OXY ta
c ta  nh là (Obj.dinh[P].y,Obj.dinh[P].x), r)i sau ó phóng theo t l là Zoom và t$nh tin theo vector (cx,cy) nhm giúp
a hình nh ra vùng gi*a Canvas} Poly[i].X:=round(Obj.dinh[P].x*zoom)+cx; Ch
ng VII. Kh ng và m t khut 96 Poly[i].Y:=-round(Obj.dinh[P].y*zoom)+cy; Poly[i].Z:=((Obj.dinh[P].z-ZMin)/(ZMax-Zmin) *4294967294); //MaxCardinal=4294967295 {Giá tr$  sâu ca nh Poly[i] là giá tr$ Obj.dinh[P].z song
c ánh x vào on 0..4294967294} end; Color:=RGB(Obj.Mat[K].Color.R,Obj.Mat[K].Color.G, Obj.Mat[K].Color.B); FillPolygon3D(Poly,Color,Z_Buffer,CanVas); end; setlength(poly,0); end; Procedure FillPolygon3D(Poly:Polygon_Z;Color:TColor; Z_Buffer:Z_BufferType;Canvas:TCanvas); {Th t#c tô màu mt a giác theo thut toán Z_Buffer} var L,H,ND,NG,i,j,Y,MaxY,MinY:integer; D:DanhSachCanhCat_Z; G:DanhsachGiaoDiem_Z; Z_BufferW,Z_BufferH:Integer; {L,H:Gii hn ch s ca mng Poly D:Danh sách các cnh
c to ra t& Poly, cha nh*ng thông tin cn thit  tính giao im và  sâu ca giao im mt cách nhanh chóng ND: S phn t ca mng D G: Cha danh sách các giao im có
c sau mi ln dòng quét thay %i NG:s phn t ca mng G} Procedure TaoDanhSachCanhCat; {Th t#c này to ra danh sách D, là danh sách các cnh ca a giác t& thông tin u vào Poly} Var i,d1,d2,Dem,Dy,Cuoi:integer; begin Ch
ng VII. Kh ng và m t khut 97 {Xác $nh s cnh ca a giác} If (Poly[L].xPoly[H].x)or (Poly[L].yPoly[H].y) then begin ND:=H-L+1; setlength(D,ND); Cuoi:=H; end else begin ND:=H-L; setlength(D,ND); Cuoi:=H-1; end; Dem:=0; {To ra các cnh} For i:=L to Cuoi do begin If i<H then j:=i+1 else j:=L; {Xác $nh im u và im cui ca cnh, im u là im có giá tr$ y nh+} If Poly[i].y<=Poly[j].y then begin d1:=i;d2:=j end else begin d1:=j;d2:=i end; D[dem].y1:=Poly[d1].y;D[dem].y2:=Poly[d2].y; {L
u tr* tung  xut phát và kt thúc} D[dem].xGiao:=Poly[d1].x; {Tung  xut phát. Kh(i u thì (D[dem].y1,D[dem].xGiao) chính là to  ca im u ca cnh} D[dem].zGiao:=Poly[d1].z; { sâu ca giao im ti im im u ca cnh} Dy:=(Poly[d2].y-Poly[d1].y); Ch
ng VII. Kh ng và m t khut 98 { chênh lch tung  ca im u và im cui} If Dy0 then begin D[dem].xStep:=(Poly[d2].x-Poly[d1].x)/Dy; D[dem].zStep:=(Poly[d2].z-Poly[d1].z)/Dy; {T&  chênh lch Dy ta suy ra gia trng ca x và  sâu z khi giá tr$ y t,ng 1 n v$. Nu khi dòng quét i qua im u thì to  giao im là (D[dem].y1,D[dem].xGiao) vi  sâu là D[dem].zGiao, nu sau ó dòng quét t,ng 1 n v$ thì rõ ràng to  giao im s là (D[dem].y1+1,D[dem].xGiao+D[dem].xStep) và  sâu s là (D[dem].zGiao+D[dem].zStep)} end else begin D[dem].xStep:=0; D[dem].zStep:=0; end; Dem:=Dem+1; end; end; Procedure TaoDanhSachGiaoDiem; {To danh sách các giao im vi
ng quét có tung  y hin th i} Var i:integer; Begin Setlength(G,ND); NG:=0; {Duyt qua tt c các cnh} for i:=0 to ND-1 do begin If (D[i].y1<=y)and(y<=D[i].y2) then {Có giao im vi
ng quét y} Begin Ch
ng VII. Kh ng và m t khut 99 {L
u li to  giao im và  sâu} G[NG].x:=round(D[i].xGiao); G[NG].y:=y; G[NG].z:=D[i].zGiao; G[NG].ChiSoCanh:=i; {Ch s cnh ã to ra giao im. Nhm ph#c v# cho quá trình lc b+ các giao im không cn thit} {L
u li Tung  và  sâu ca giao im vi
ng quét tip theo (y+1) vào chính D[i].xGiao và D[i].zGiao} D[i].xGiao:=D[i].xGiao+D[i].xStep; D[i].zGiao:=D[i].zGiao+D[i].zStep; NG:=NG+1; end; end; end; Procedure SapXepVaLoc; {Sp xp li các giao im và lc b+ các giao im th&a} Var i,j,C1,C2:integer; Tg:GiaoDiem_Z; Begin {Sp xp li các giao im} for i:=0 to NG-2 do For j:=i+1 to NG-1 do If G[i].x>G[j].x then begin Tg:=G[i];G[i]:=G[j];G[j]:=Tg; end; i:=0; {Kh nh*ng Giao im th&a} While i<(NG-2) do begin If G[i].x=G[i+1].x then {2 giao im trùng nhau} Ch
ng VII. Kh ng và m t khut 100 begin C1:=G[i].ChiSoCanh; C2:=G[i+1].ChiSoCanh; {C1 và C2 là hai cnh ã to nên 2 giao im trùng nhau ang xét} If (D[C1].y1D[C2].y1)and(D[C1].y2D[C2].y2)) or(D[C1].y1=D[C1].y2)or(D[C2].y1=D[C2].y2) then {Xoá bt mt giao im nu nh
: 2 cnh to nên 2 giao im này nm v hai phía ca
ng quét hoc có mt cnh là nm ngang} begin For j:=i to NG-2 do G[j]:=G[j+1]; NG:=NG-1; end; end; i:=i+1; end; end; Procedure ToMauCacDoan; {Thc hin tô màu các on th"ng là phn giao ca
ng quét vi a giác. ó là các on x1x2, x3x4,…} Var i,x,K:integer;Dz:real; Z:Cardinal; begin i:=0; While i<NG-1 do begin K:=G[i+1].x - G[i].x; If k0 then Dz:=(G[i+1].z-G[i].z)/K else Dz:=0; For x:=G[i].x to G[i+1].x do {Vi mi on ta thc hin tính  sâu ca t&ng im r)i so sánh vi giá tr$ có trong Z_Buffer} begin Ch
ng VII. Kh ng và m t khut 101 If (0<=x)and(x<=Z_BufferW)and(0<=y) and(y<=Z_BufferH) then begin z:=round(G[i].z); If Z_Buffer[x,G[i].y]>Z then {So sánh
sâu ca im tính c vi
sâu ã có } {Nu  sâu ca im tính
c nh+ hn  sâu ã có trong Z_Buffer thì rõ ràng là im tính
c ( gn hn im ã v tr
c ó trong vùng m Z và Canvas} Begin Canvas.Pixels[x,G[i].y]:=Color; {V im lên Canvas} Z_Buffer[x,G[i].y]:=Z; {Cp nht  sâu ca im v&a v vào vùng m Z} end; end; G[i].z:=G[i].z+Dz; {Gán giá tr$  sâu ca im tip theo vào trong G[i].z} end; i:=i+2; end; end; {Th t#c chính} Begin L:=low(Poly); H:=High(Poly); {Xác $nh gii hn trên và gii hn d
i ca Poly} Z_BufferW:=high(Z_Buffer); {Xác $nh các chiu ca ma trn Z_Buffer} Z_BufferH:=high(Z_Buffer[0]); {Z_BufferW+1:Chiu rng (t& 0..Z_BufferW) Z_BufferH+1:Chiu cao (t& 0..Z_BufferH)} Ch
ng VII. Kh ng và m t khut 102 { Tìm giá tr$ y ln nht và nh+ nht ca a giác Poly  t& ó cho dòng quét thc hin quét t& trên min n max} MaxY:=Poly[L].y; MinY:=MaxY; For i:=L+1 to H do if MaxY<Poly[i].y then MaxY:=Poly[i].y else If MinY>Poly[i].y then MinY:=Poly[i].y; TaoDanhSachCanhCat; {To danh sách các cnh ca a giác Poly vi các tham s thit lp nhm giúp cho vic tính toán giao im
c d- dàng} For y:=MinY to MaxY do {Cho dòng quét chy t& MinY n MaxY } begin TaoDanhSachGiaoDiem; {Tìm danh sách các giao im ca
ng quét y vi các cnh ca Poly} SapXepVaLoc; {Sp xp li các giao im và lc b+ các giao im th&a} ToMauCacDoan; {Da vào các giao im  xác $nh ra các on nm trong a giác, t& ó tô màu t&ng im trên on ó da vào  sâu so sánh vi giá tr$  sâu t
ng ng trên Z_Buffer} end; Setlength(D,0); {Gii phóng mng D} Setlength(G,0); {Gii phóng mng G} end; Ch
ng VII. Kh ng và m t khut 103 BÀI TP 1. Cài t cho thut gii Depth-Sorting Cài t ch ng trình cho phép biu din và quan sát vt th 3D theo mô hình "các mt a giác" trong ó s d!ng thut gii Depth-Sorting  kh các mt khu t 2. Cài t cho thut gii chn lc m t sau Cài t ch ng trình cho phép biu din và quan sát vt th 3D theo mô hình "các mt a giác" trong ó s d!ng thut gii ch'n l'c mt sau  kh các mt khu t. Vi i t ng là các hình lp ph ng, t din, bát din, c$u,… 3. Cài t cho thut gii vùng m  sâu Cài t ch ng trình cho phép biu din và quan sát vt th 3D theo mô hình "các mt a giác" trong ó s d!ng thut gii ch'n l'c mt sau  kh các mt khu t. Vi i t ng là các mt ct nhau, các hình l(i lõm b t k%.