Các Thuật toán trong đồ họa máy tinh

I.Thuật toán vẽ đường tròn Phương trình đường tròn có dạng: (x-xc)2 + (y-yc)2 = r2 Pt đường tròn có tâm ở gốc tọa độ: x2+y2 =r2 Do tính đối xứng của đường tròn nên ta chỉ cần vẽ cung ¼ hoặc 1/8 void put8pixel(int xc, int yc, int x, int y) { putpixel(x+xc, y+yc, color); putpixel(y+xc, x+yc, color); putpixel(y+xc, -x+yc, color); putpixel(x+xc, -y+yc, color); putpixel(-x+xc, -y+yc, color); putpixel(-y+xc, -x+yc, color); putpixel(-y+xc, x+yc, color); putpixel(-x+xc, y+yc, color); } 1.Thuật toán Bresenham Giả sử tại bước i đã vẽ được điểm (xi,yi) Điểm cần vẽ kế tiếp (xi+1, yi+1) là: (xi +1, yi) hay (xi +1, yi -1) Giá trị y thực sự thuộc đường tròn ứng với xi là: y2 = r2 – (xi +1)2 Gọi d1 = yi2 – y2 = yi2 –r2 +(xi +1)2 d2= y2 - (yi -1)2 = r2 – (xi +1)2 – (yi -1)2 Pi = d1-d2 = yi2 – r2 +(xi +1)2 –r2 + (xi +1)2 +(yi-1)2 = 2(xi +1)2 + yi2 +(yi -1)2 -2r2 Pi+1 – pi = 2(xi+1 +1)2 + yi+12 + (yi+1 -1)2 – 2r2 – 2(xi +1)2 – yi2 – (yi -1)2 + 2r2 = 4xi + 6 + 2(yi+12 – yi2) -2(yi+1-yi) Pi+1 = pi+4xi + 6 + 2(yi+12 – yi2) -2(yi+1-yi) Vậy: + nếu pi < 0 thì yi+1 = yi, khi đó pi+1 = pi+4xi+6 +Nếu pi >= thì yi+1 = yi-1, khi đó pi+1 = pi + 4(xi-yi)+10 Giá trị pi tại điểm đầu tiên (x1,y1) = (0,r) là: P1 = 2+r2+(r-1)2 – 2r2=3-2r void CircleBres(int xc, int yc, int r) { int x,y,p; x=0; y=r; p=3-2*r; while (x<=y) { put8pixel(xc,yc,x,y); if(p<0) p+ =4*x+6; else { p+ = 4*(x-y) +10; y--; } x++; }} 2.Thuật toán Midpoint Gọi F(x,y) = x2+y2-r2, ta có: F(x,y){<0 nếu (x,y) nằm trong đường tròn =0 nếu (x,y) thuộc đường tròn >0 nếu (x,y) nằm ngoài đường tròn Chọn điểm bắt đầu vẽ là (0,r) Giả sử đã vẽ được điểm (xi,yi), Điểm cần vẽ kế tiếp (xi+1,yi+1) là S hay P Việc chọn điểm S hau P dựa trên dấu của: Pi=F(Midpoint) = F(xi+1,yi-1/2) + Nếu pi chọn S + Nếu pi>=0 => chọn P Mặt khác: pi+1 – pi = F(xi+1 +1, yi+1 -1/2)- F(xi+1, yi-1/2) = [(xi+1 +1)2 + (yi+1 – ½)2 – r2] – [(xi+1)2 + (yi-1/2)2 – r2] = 2xi + 3 (yi+12 – yi2) – (yi+1 – yi) Vậy: + Nếu pi<0 thì yi+1 = yi, khi đó pi+1 = pi + 2xi + 3 + Nếu pi>=0 thì yi+1= yi -1, khi đó pi+1 = pi + 2(xi-yi) +5 Giá trị pi tại điểm đầu tiên (x1, y1)=(0,r) là: p1= F(x1+1, y1 -1/2) = f(1, r-1/2) = 5/4 – r void CircleMidpoint(int xc, int yc, int r) { int x,y,p; x=0; y=r; p=5/4; while (x<=y0 { put8pixel(xc,yc,x,y); if(p<0) p+ = 2*x +3; else{ p+=2*(x-y0+5; y--; } x++; } } II.Thuật toán tô màu theo đường biên: Ý tưởng: Bắt đầu từ điểm P(x,y) nằm bên trong vùng tô, kiểm tra các điểm lân cận cảu P đã được tô màu hay có phải là điểm biên hay không, nếu không phải là điểm đã tô và không phỉa là điểm biên thì ta sẽ tô màu nó. Quá trình này được lặp laijcho đến khi không còn tô được diểm nào nữa thì dừng. Có hai cách chọn điểm lan cận, đó là chọn 4 hoặc 8 điểm lân cận dối với điểm đang xét. Thủ tục minh hoajthuaatj toán tô màu theo đường biên: Void TOloang(int x, int y, int mauto, int mauvien) { int mau; mau=getpixel(x,y); if(mau != mauvien)& (mau != mauto) { Putpixel(x, y,mauto); Toloang(x-1,y, mauto, mauvien); Toloang(x, y+1, mauto, mauvien); Toloang(x+1, y, mauto, mauvien); Toloang(x, y-1, mauto, mauvien);}} =>Nhược điểm của phương pháp đệ quy là =>không thực hiện được khi vùng loang có diện =>tích lớn( dẫn đến tràn Stack 1.Phương pháp đệ quy: Bước 1: khởi tạo hang đợi (hoặc stack) với phần tử đầu tiên là P(x,y) đã được tô Bước 2: khi hàng đợi (hoặc stack) không rỗng thì: + Lấy ra từ hang đợi(hoặc stack) một điểm Q. + tìm các điểm lân cận của Q chưa tô thì tô chúng và đưa chúng vào hang đợi(hoặc stack) Bước 3 này được lặp đi lặp lại cho đến khi hang đợi (hoặc stack) rỗng struct DS { int x,y; struct DS*next; }; struct DS*dau; void push(int x, inty) { struct DS*P; P=(DS*) calloc(1,sizeof(DS)); P->x=x; P->y=; P->next=NULL; if(dau !=NULl) P->next= dau; dau=P;} Void pop(int *x, int*y) { struct DS*P; P=dau; dau=dau->next; *x=P->x; *y= P->y; free(P);} void tolancan(int x, inty, int mauto, int mauvien) { int mau; mau=getpixel(x,y); if((mau != mauto)&&(mau !=mauvien)) { putixel(x,y,mauto); push(x,y);} } Void toloang_stack(int x0, int y0, int mauto, int mauvien){ int x,y; putpixel(x0,y0,mauto); dau=NULL; push(xo,yo); while(dau != NULL) { pop(&x,&y); tolancan(x-1, y, mauto, mauvien); tolancan(x+1, y, mauto, mauvien); tolancan(x, y+1, mauto, mauvien); tolancan(x, y-1, mauto, mauvien);}} Flood Fill/boundary fill  Scan line fill/ scan conversion   Đơn giản  Phức tạp hơn   Thuật toán rời rạc hóa trong không gian màn hình  Thuật toán rời rạc hóa trong đối tượng hoặc/và không gian màn hình   Yêu cầu gọi hệ thống GetPixel/Val  Độc lập với thiêt bị   Đòi hỏi điểm seed  Không đòi hỏi điểm seed   Yêu cầu stack rất lớn  Yêu cầu stack nhỏ      III.Các thuật toán xén hình 1.Thuật toán Cohen-sutherland Chia mặt phẳng thành 9 vùng: cửa sổ và 8 vùng xung quanh nó. Mỗi vùng được gán bởi một mã nhị phân 4 bit Giả sử có điểm P(x,y), lúc đó gán mã cho điểm P: Pleft={ 1, nếu Px < xmin Pright={ 1, nếu Px>xmax 0, ngược lại 0, ngược lại Pbottom={ 1, nếu Py<ymin Ptop= { 1, nếu Py>ymax 0, ngược lại 0, ngược lại Hàm tính mã int ma(point M){ int m=0; if(M.x<min.x) ml=1; if(M.x>max.x) ml=2; if(M.y<min.y) ml=4; if(M.y>max.y) ml=8; return m;} Xét đoạn thẳng AB, ta có các trường hợp sau: 1.Nếu (Ma(A)=0000) và (Ma(B)=000) {hay(Ma(A) or Ma(B)=0000} thì =>ClipD(F)=AB 2.Nếu (Ma(A) and Ma(B))≠0000) thì => ClipD(F) = Ø 3.Nếu ((Ma(A) and Ma(B))=0000) và (Ma(A)≠0000 hoặc Ma(B)≠0000) thì Giả sử Ma(A)≠0000 { nếu ma(A)=0 ta đổi vai trò A và B} -Nếu Ax=Bx(AB thẳng đứng ) thì +Nếu Ay>ymax (A ở trên) thì Ay=ymax’ ngược lại (A ở dưới) Ay=ymin => ClipD(F)=AB -Ngược lại (trường hợp Ax≠Bx): +Tính hệ số góc m=(By-Ay)/(Bx-Ax) {để tính giao của AB với HCN} Vì A nằm ngoài hình chữ nhật nên: +Nếu Ax<xmin thì thay A bởi điểm giao của AB với cạnh trái(nối dài) của HCN +Nếu Ax>xmax thì thay A bởi điểm giao của Ab với cạnh phải(nối dài) cua HCN +Nếu Ay<ymin thì thay A bởi điểm giao của AB với cạnh dưới(nối dài) của HCN +Nếu Ay>ymax thì thay A bởi giao điểm của Ab với cạnh trên(nối dài) của HCN Quá trình lặp lại này dừng khi xảy ra một trong hai trường hợp 1hay 2 void ClipCohen(Point A, oint B, Point wmin, Point wmax) { int thoat,ve; double m; thoat=0; ve=1; while(thoat==0) { if((ma(A) | ma(B)==0) thoat=1; else if((ma(A)&ma(B))!=0) {thoat=1; ve=0} else { if(m(A)==0) hoanvi(&A,&B); if(A.x==B.x) { if(A.y>wmax.y) A.y=wmax.y; else A.y=wmin.y;} else{ m=(double)(B.y-A.y)/(b.x-A.x); if(A.x<wmin.x){ A.y=A.y+(wmin.x-A.x)*m; A,x=wmin.x; } Else if(A.x>wmax.x){ A.y=A.y+(wmax.x-A.x)*m; A.x=wmax.x; } else if(A.y<wmin.y){A.x= A.x+(wmin.y-A.y)/m; A.y=wmin.y; } else if(A.y>wmax.y) { A.x=A.x+(wmax.y-A.y)/m; A.y=wmax.y; }}}}//end while if (ve) veduongthang(A,B);} 2.Thuật toán chia nhị phân Chia mặt phẳng thành 9 vùng, mỗi vùng được gán bởi một mã nhị phân 4 bit -Ý tưởng của thuật toán như sau: Lấy trung điểm của đoạn thẳng và kiểm tra mã của nó để loại dần các đoạn con không chứa giao điểm, và cuối cùng cho điểm giữa hội tụ về giao điểm của đoạn thẳng với hình chữ nhật, kết quả là ta thu được đoạn con nằm trong hình chữ nhật(nếu có) -Mệnh đề : Cho M trung điểm của đoạn AB, Mã(A)≠0000, Mã(B)≠0000, Mã(M)≠0000 Thì ta có: [mã(A) AND Mã(M)]≠0000 hoặc[Mã(M) AND Mã(B)]≠0000. -Ý nghĩa hình học của mệnh đề: Nếu cả ba điểm A, B, M đều ở ngoài hình chữ nhật thì có ít nhất một đoạn hoàn toàn nằm ngoài hình chữ nhật. -Thuật toán: 1.Nếu (Mã(A) = 0000) và Mã(B)=0000) thì =>ClipD(F) = AB 2.Nếu (Mã(A) AND Mã(B))≠0000 thì =>ClipD(F)=Ø 3.Nếu (Mã(A)≠0000) và Mã(B) = 0000) thì: đỏi vai trò của A, B và áp dụng 4 4.Nếu (Mã(A) = 0000) và (Mã(B) ≠0000) thì: P:=A; Q:=B; Trong khi |xP – xQ| + |yP – yQ|>=2 thì: Lấy trung điểm M của PQ Nếu Mã(M)≠0000 thì Q:=M. Ngược lại: P:=M. =>ClipD(F) = AP 5.Nếu (Mã(A) ≠ 0000 ≠ Mã(B)) và [Mã(A) AND Mã(B)]= 0000 thì: P:=A; Q:=B; Lấy M: trung điểm PQ; Khi (Mã(M)≠0000) và (|xP-xQ| + |yP-yQ|>=2) thì: Nếu (Mã(M) AND Mã(Q))≠0000 thì Q:=M; Ngược lại: P:M; Lấy M: trung điểm PQ Nếu Mã(M)≠0000 thì ClipD(F)=Ø Ngược lại, áp dụng 4 ta có: ClipD(MP) = MA1 ClipD(MQ) = MB1 =>ClipD(F) = A1B1 Void XenHinhNhiPhan(Point A, Point B) { Point P,Q,M; if((Ma(A)|Ma(B))==0) VeDuongThang(A,B); if((Ma(A)&Ma(B))!=0) return; if((Ma(A)!=0)&&(Ma(B)=0)) HoanVi(&A,&B); if((Ma(A)==0)&&(Ma(B)!=0)) { P=A; Q=B; while((abs(P.x-Q.x)+abs(P.y-Q.y)).2) { M.x=(P.x+Q.x)/2; M.y=(P.y+Q.y)/2; If(Ma(M)==0) P=M; Else Q=M;} VeDuongThang(A,P);} if(((Ma(A)!=0)&&(Ma(B)!=0))&&((Ma(A)&Ma(B))==0)) { P=A; Q=B; M.x=(P.x+Q.x)/2; M.y=(P.y+Q.y)/2; while((Ma(M)!=0)&&((abs(P.x-Q.x)+abs(P.y-Q.y))>2)) { if((Ma(P)& Ma(M)!=0) P=M; else Q=M; M.x=(P.x+Q.x)/2; M.y=(P.y+Q.y)/2;} if(Ma(M)==0){ XenHinhNhiPhan(P,M); XenHihNhiPhan(M,Q);} IV.Biểu diễn các đối tượng 3D 1.Mô hình khung kết nối Mô hình khung kết nối (WF-WireFrame model) thể hiện hình dáng của một đối tượng 3D bởi 2 danh sách: -Danh sách các đỉnh (vertices): lưu tọa đọ các đỉnh. -Danh sách các cạnh (edges) nối gữa các đỉnh đó: lưu 2 đỉnh đầu và cuối của từng cạnh. (hình vẽ) Có nhiều cách để lưu trữ một mo hình WF trên máy tính. Có thể sử dụng cấu trúc sau: const maxDinh= 30; const maxCanh=50; typedef struct toado3D { int x; int y; int z; } typedef struct KieuCanh { int dau; int cuoi; } typedef struct WireFrame { int sodinh; toado3D dinh[maxDinh]; int socanh; KieuCanh canh[maxCnah]; }; 2.Mô hình mặt đa giác Mô hình các mặt đa giác(Polygon Mesh model) thể hiện hình dáng của một đối tượng 3D bởi 2 danh sách: -Danh sách các đỉnh -Danh sách các mặt: lưu thứ tự các đỉnh tạo nên mặt đó (hình vẽ) Chúng ta có thể đưa ra nhiều cấu trúc dữ liệu khác nhau để lưu trữ cho đa giác. Dưới đây là một kiểu cấu trúc: typedef struct toado3D { int x; int y; int z; } struct Kieumat { int sodinhmat; int chisodinh[MAX]; }; struct Mohinhmat { int sodinh; toado3D dinh[MAX]; int somat; Kieumat mat[MAX]; }; V.Biểu diễn đường và mặt cong: 1.Đường cong Benzier Bài toán: Cho n+1 điểm p0, p1, p2,…,pn được gọi là các điểm kiểm soát (điểm điều khiển). Xây dựng đường cong trơn đi qua 2 điểm p và pn được giới hạn trong bao lồi do n+1 điểm trên tạo ra Thuật toán Casteljau Để xây dựng đường cong P(t), ta dựa trên một dãy các điểm cho trước rồi tạo ra giá trị P(t) ứng với mỗi giá trị t nào đó. Phương pháp này tạo ra đường congdựa trên một dãy các bước nội suy tuyến tính hay nội suy khoảng giữa(In-Betweening). Với 3 điểm P0, P1, P2 ta có thể xây dựng một Parabol nội suy từ 3 điểm này bằng cách chọn một giá trị t ∊ [0,1] rồi chia đoạn P0P1 theo tỉ lệ t, ta được điểm P01, trên P0P1. Tương tự , ta chia tiếp P1P2 cũng theo tỉ lệ t, ta được P11. Nối P01 và P11 lại lấy điểm trên P01P11 chia theo tỉ lệ t, ta được P02. Tập điểm P02 chính là đường cong P(t). Ta biểu diễn bằng chương trình: P01(t)= (1-t).P0+t.P1 (1) P11(t)= (1-t).P1+t.P2 (2) P02(t)= (1-t).P01+t.P11 (3) Trong đó t ∊ [0. 1] Thay (1), (2) vào (3) ta được: P(t)= P02(t)= (1-t)2.P0 + 2t.(1-t).P1 + t2.p2 Đây là một đường cong bậc 2 theo t nên nó là một Parabol -Tổng quát hóa ta có thuật toán Casteljau cho (n+1) điểm kiểm soát: Giả sử ta có tập điểm: P0,P1,P2,…,Pn Với mỗi giá trị t cho trước, ta tạo ra điểm Pir(t) ở thế ệ thứ r, từ thế hệ thứ (r-1) trước đó, ta có: Pir(t)= (1-t).Pir-1(t)+t.Pi+1r-1(t) (r=0,1,…,n và i=0,…,n-r) Thế hệ cuối cùng: P0n(t)=∑ Pi.(1-t)n-i.ti.Cni Được gọi là dường cong benzier của các điểm P0,P1,P2,…,Pn. Các điểm pi, i=0,1,…,n gọi là các điểm kiểm soát hay các điểm beier. Đa gics tạo bởi các điểm kiểm soát gọi là đa giác kiểm soát hay đa giác benzier. Đường cong benzier dựa trên (n+1) điểm kiểm soát P0,P1,P2,…,Pn được cho bưởi công thức: P0n ( t)=P(t)= ∑pk.B nk(t) Trong đó: P(t): là một điểm trong mặt phẳng hoặc trong không gian. B nk(t): gọi là đa thức Bernstrin, được cho bởi coog thức: B nk(t)=Cnk .(1-t)n-k.tk =(n!/k!(n-k)! )(1-t)n-t.tk với n>=k Mỗi đa thức Bernstein có bậc là n. thong thuowgf ta còn gọi các B nk(t) là các hàm trộn. Đường cong Benzier dực trên (n+1) điểm kiểm soát p0,p1,…,pn được cho bưởi coog thức: P0n ( t)= P(t)= ∑Pk.B nk(t) Tương tự, đối với mặt benzier ta có phương trình sau: P(u,v)= ∑ ∑ P I,k . Bim (u) Bkn(V) Trong trường hợp này khối đa diện kiểm soát sẽ có (m+1)(n+1) đỉnh. Minh họa vẽ đường cong benzier trong mặt phẳng. Typedef struct { int x; int y; } CPoint; int GiaiThua (int n){ if(n==0) return 1 ; else return 1 n* GiaiThua(n-1); } float hamMu(float a, int n){ if(n==0) return 1; else return a*hamMu(a,n-1); } float BernStein(float t,int n, int k){ float ckn,kq; ckn=GiaiThua(n)/(GiaiThua(k)*GiaiThua(n-k)); kq=ckn*HamMu(1-t,n-k)*HamMu(t,k); return kq;} CPoint TPt(CPonit P[ ],float t,int n) {CPoint Pt; float B;int K; Pt.x=0; Pt.y=0; For(k=0;k<=n;k++) { B= BernStein(t,n,k); Pt.x=Pt.x+P[k].x*B; Pt.y=Pt.y+P[k].y*B; } return Pt; } Void DrawBenzier(int n, CPoint P[ ]) { CPoint PT; float dt,t,m; int I;t=0; m=100; dt=1/m; Moveto(P[0].x,P[0].y); For(i=1;i<=m;i++){ Pt=TPt(P,t,n); Lineto(Pt.x,Pt.y); t=t+dt; } Các mặt có quy tắc: (mặt trụ) Mặt trụ là mặt được tạo ra khi một dường thẳng (đường sinh) được quét dọc theo một đường cong P0(u) (đường chuẩn). đường cong P0(u) nằm trên một mặt phẳng nào đó . Gọi d là đường sinh,d=const. P0(u) là đáy dưới. P1(u)là đáy trên. Suy ra d= P0(u)- P1(u)p(u,v)= (1-v).P0(u)+v.P1(u) = P0(u)+(P1(u) -P0(u)).v= P0(u)+d.v Vậy: p(u,v)= P0(u)+d.v Pt mặt trụ : p(u,v)= P0(u)+d.v Dạng quen thuộc của mặt trụ là mặt trụ trònL trong mặt phẳng xoy, lấy P0(u) là đường tròn tâm o bán kính r. Ta có:d=(0,0,h) P0(u)=(r.cos(u),r.sin(u),0) Vậy: {X(u,v)=r.cos(u) Y(u,v)=r.sin(u) Z(u,v)=h.v với {0<=v<=1; 0<=u<=2π thủ tục mặt trụ: void DrawCylinder( float R,float h){ Point3D P; Point2D P1 ; doule Delta_U, Delta_V,u,v; Delta_U=0.06 ; Delta_V=0.03; for(u=0;u<2*M_PI;u+= Delta_U) { for(v=0;v<2*M_PI;v+= Delta_V) { P.x=R*cos(u); P.y=R*sin(u); P.z=v*h; P1=Chieu(KieuChieu,P); Putpixel(xc+P1.x+P1.y,Ưhite);}}} Mặt nón: Mặt nón là mặt được tạo ra khi một dường thẳng di chuyển dọc theo một đường cong phawmgr cho trước. các duowgf thẳng luôn di qua một điểm cố định gọi là đỉnh của mặt nón. P0(u) trùng với gốc tọa độ O. P1(u) là đường trong tâm (0,0,h) bán kính r. P0(u)=(r.cos(u),r.sin(u),h) Ta có: p(u,v)=(1-v). P0(u)+ v. P1(u)=v. P0(u) Vạy: p(u,v)= v. P0(u). Hay: {X(u,v)=v.r.cos(u) Y(u,v)=v.r.sin(u) Z(u,v)=h.v với {0<=v<=1; 0<=u<=2π thủ tục mặt nón: void DrawCone( float R,float h){ Point3D P; Point2D P1 ; doule Delta_U, Delta_V,u,v; Delta_U=0.03 ; Delta_V=0.1; for(u=0;u<2*M_PI;u+= Delta_U) { for(v=0;v<2*M_PI;v+= Delta_V) { P.x=v.R*cos(u); P.y=v.R*sin(u); P.z=v*h; P1=Chieu(KieuChieu,P); Putpixel(xc+P1.x+P1.y,White);}}} Các mặt tròn xoay(mặt cầu): Với mặt cầu tâm O bán kính r thì C là ½ đường tròn trong mặt phawmgr xoz. Ta có: X(v)=r.cos(u); Z(v)=r.sin(v); {X(u,v)=r.cos(u).cos(v) Y(u,v)=r.sin(u).cos(v) Z(u,v)=r.sin(v) với {- π /2<=v<= π /2 ; 0<=u<=2π thủ tục mặt cầu: void DrawSphere( float R){ Point3D P; Point2D P1 ; doule Delta_U, Delta_V,u,v,Pi_2; Pi_2=M_PI/2; Delta_U=0.1,;Delta_V=0.1; Delta_U=0.03 ; Delta_V=0.1; { for(v= -Pi_2;v<2*M_PI;v+= Delta_V) for(u=0;u<2*M_PI;u+= Delta_U) { P.x= R* sin(u).cos(v); P.y=R* sin(u).cos(v); P.z=R.sin(v); P1=Chieu(KieuChieu,P); Putpixel(xc+P1.x+P1.y,GREEN); }}}