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

Tài liệu tham khảo cho các bạn sinh viên ôn thi chuyên ngành đến toán trong máy tính.
Nội dung trích xuất từ tài liệu:
Các Thuật toán trong đồ họa máy tinhI.Thuật toán vẽ đường trònPhương trình đường tròn có dạng:(x-xc)2 + (y-yc)2 = r2Pt đường tròn có tâm ở gốc tọa độ:x2+y2 =r2Do tính đối xứng của đường tròn nên ta chỉcần vẽ cung ¼ hoặc 1/8void 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 1Giả 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)2Gọi d1 = yi2 – y2 = yi2 –r2 +(xi +1)2d2= y2 - (yi -1)2 = r2 – (xi +1)2 – (yi -1)2Pi = d1-d2 = yi2 – r2 +(xi +1)2 –r2 + (xi +1)2 +(yi-1)2 = 2(xi +1)2 + yi2 +(yi -1)2 -2r2Pi+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)+10Giá trị pi tại điểm đầu tiên (x1,y1) = (0,r) là:P1 = 2+r2+(r-1)2 – 2r2=3-2rvoid CircleBres(int xc, int yc, int r) 2{int x,y,p;x=0; y=r; p=3-2*r;while (xViệ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 PMặ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 -1, khi đó pi+1 = pi + 2(xi-yi) +5Giá 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 – rvoid CircleMidpoint(int xc, int yc, int r){int x,y,p;x=0; y=r; p=5/4;while (xif(pif(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 Stack1.Phương pháp đệ quy:Bước 1: khởi tạo hang đợi (hoặc stack) vớiphầ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ỗngstruct DS { int x,y; 6struct 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); 7push(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 Scan line fill/ Fill/boundary fill scan conversion Đơn giản Phức tạp hơn Thuật toán rời Thuật toán rời rạc hóa trong rạc hóa trong đối tượng không gian màn hoặc/và không hình gian màn hình 8 Yêu cầu gọi hệ Độc lập với thống thiêt bị GetPixel/Val Đòi hỏi điểm Không đòi hỏi điểm seed seed Yêu cầu stack rất Yêu cầu stack lớn nhỏIII.Các thuật toán xén hình1.Thuật toán Cohen-sutherlandChia mặt phẳng thành 9 vùng: cửa sổ và 8vùng xung quanh nó. Mỗi vùng được gán bởi một mã nhị phân 4bit Giả sử có điểm P(x,y), lúc đó gán mã cho điểm P:Pleft={ 1, nếu Px < xminPright={ 1, nếu Px>xmax0, ngược lại 0, ngược lạiPbottom={ 1, nếu Pyymax0, ngược lại 0, ngược lại ...