Bài giảng Đồ họa máy tính chương 2: Các thuật toán cơ sở

BÀI GIẢNG ĐỒ HỌA MÁY TÍNH GV: Vũ Đức Huy SĐT: 0912316373 Bộ môn: HTTT-ĐHCNHN EMail: huyhaui@gmail.com Thời lượng: Số tín chỉ: 03 Lên lớp: 20 TH: 25 Bài tập lớn + Bảo vệ: 15 BÀI GIẢNG ĐỒ HỌA MÁY TÍNH Các điểm: Kiểm tra định kỳ: 02 Kiểm tra thường xuyên: Không định trước Thi: Kết quả BTL Chuyên cần:01 Tài liệu tham khảo [1] James D.Foley, Andrie van Dam, Steven K.Feiner, Jonhn F. Hughes, Computer Graphics Principles and Practice, Addison Wesley, 1994. [2] Hoàng Kiếm, Dương Anh Đức, Lê Đình Duy, Vũ Hải Quân. Giáo trình cơ sở Đồ hoạ Máy tính, NXB Giáo dục, 2000. [3] Lê Tấn Hùng, Huỳnh Quyết Thắng. Kỹ thuật đồ hoạ máy tính, NXB khoa học và kỹ thuật, 2002. [4] Học viện công nghệ bưu chính viễn thông. Kỹ thuật đồ họa (lưu hành nội bộ) [5] Lương Chi Mai. Nhập môn Đồ họa máy tính, NXB Khoa học và kỹ thuật. [6] Steven Harrington, Computer Graphics A Programming Approach, McGraw Hill International Edition, 1987. [7] Gerald Farin, Curves and Surfaces for Computer Aided Geometric Design A Practical Guide, Academic Press Inc, 1990. CHƯƠNG 2 CÁC THUẬT TOÁN CƠ SỞ 2.1. CÁC THUẬT TOÁN VẼ ĐƯỜNG THẲNG 2.1.1. Một số khái niệm Điểm Điểm là thành phần cơ sở được định nghĩa trong một hệ tọa độ. Đối với hệ tọa độ hai chiều mỗi điểm được xác định bởi cặp tọa độ (x, y). Ngoài thông tin về tọa độ, điểm còn có thuộc tính là màu sắc. Thủ tục vẽ một điểm (x,y) với mầu c: Putpixel(x,y,c) 2.1.1. Một số khái niệm Đoạn thẳng Biểu diễn tường minh: y = f(x) Phương trình đoạn thẳng đi qua 2 điểm P (x1,y1) và Q(x2,y2): (y-y1)/( x-x1) = ( y2-y1)/( x2-x1) (y-y1)(x2-x1)=(x-x1)(y2-y1) (x2-x1)y=(y2-y1)x + y1(x2-x1) - x1(y2-y1) y = ((y2-y1)/(x2-x1))x + y1 - ((y2-y1)/(x2-x1))x1 y = mx + b m = (y2-y1)/(x2-x1) Độ dốc hay hệ số góc của đường b = y1- mx1 Đoạn chắn trên trục y Δy = mΔx (tức là khi x thay đổi thì y thay đổi theo) 2.1.1. Một số khái niệm Đoạn thẳng Biểu diễn tường minh: y = f(x) 2.1.1. Một số khái niệm Đoạn thẳng Biểu diễn không tường minh: Ax+By+C=0 Ta có (y2-y1)x - (x2-x1)y + (x2-x1)y1 - (y2-y1)x1 = 0 (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 Tổng quát: Ax + By + C = 0 Với: A = (y2-y1) B = -(x2-x1 ) C = x2y1 - x1y2 2.1.1. Một số khái niệm Đoạn thẳng Biểu diễn thông qua tham số: P(t) = P1 + t(P2 - P1) t €[0,1] x(t) = x1 + t( x2 - x1 ) y (t)= y1 + t(y2 - y1 ) 2.1.2. Giải thuật làm tròn 2.1.2. Giải thuật làm tròn Cho phương trình đường thẳng d: y = mx+b m = (y2-y1)/(x2-x1) b = y1- mx1 Trường hợp d//Oy Gán x=x1; y =y1; Lặp Putpixel(x,y,c); y = y+1; Tới khi y =y2; 2.1.2. Giải thuật làm tròn Trường hợp d//Ox Gán x=x1; y =y1; Lặp Putpixel(x,y,c); x = x+1; Tới khi x =x2; 2.1.2. Giải thuật làm tròn Trường hợp d gần Ox Gán x=x1; y =y1;m = (y2-y1)/(x2-x1);b = y1- m*x1; Lặp Putpixel(x,round(y),c); x = x+1; y = m*x+b Tới khi x =x2; 2.1.2. Giải thuật làm tròn Trường hợp d gần Oy: x = (1/m)y – b/m Gán x=x1; y =y1;m = (y2-y1)/(x2-x1);b = y1- m*x1; Lặp Putpixel(round(x),y,c); y = y+1; x = (1/m)*y-b/m Tới khi y =y2; 2.1.2. Giải thuật làm tròn Nhận xét: Thao tác với số thực Sử dụng phép nhân, chia số thực Sử dụng hàm làm tròn  Tốn bộ nhớ, chạy chậm 2.1.3. Giải thuật DDA Cho phương trình đường thẳng d: y = mx+b m = (y2-y1)/(x2-x1) b = y1- mx1 2.1.3. Giải thuật DDA Giả sử vẽ được (xi,yi) Tiếp theo, chọn yi+1 là yi hay yi+1 dựa vào phương trình của đường thẳng d . 2.1.3. Giải thuật DDA Thay xi+1 vào phương trình đường thẳng d: yi+1 = m(xi+1)+b yi+1 = mxi+ b + m yi+1 = yi + m 2.1.3. Giải thuật DDA Lưu đồ thuật toán 2.1.3. Giải thuật DDA Thủ tục 2.1.3. Giải thuật DDA Nhận xét: Cải thiện tốc độ: Sử dụng công thức yi+1 = yi + m thay cho y = mx + b, tránh phép nhân số thực. Sai số tích lũy do việc cộng số thực m vào y, điểm vẽ chệch hướng với đường thẳng thực khi đường thẳng dài. Tốc độ vẫn chậm (sử dụng cộng số thực, làm tròn). 2.1.4. Giải thuật Bresenham Mục tiêu Hạn chế tối đa các phép toán trên số thực trong thuật toán. 2.1.4. Giải thuật Bresenham Cho phương trình đường thẳng d: y = mx+b dx = x2-x1 dy = y2-y1 m = dy/dx b = y1- mx1 2.1.4. Giải thuật Bresenham Không mất tính tổng quát, xét 0d2 (d1-d2>0) thì điểm tiếp theo là P(xi+1,yi+1) R 2.1.4. Giải thuật Bresenham Tính d1: d1 = y(xi+1)-yi d1 = (m(xi+1)+b)-yi d1 = m(xi+1)+b-yi R 2.1.4. Giải thuật Bresenham Tính d2: d2 = yi+1-y(xi+1) d2 = yi+1-(m(xi+1)+b) d2 = yi+1-m(xi+1)-b R 2.1.4. Giải thuật Bresenham Đặt Pi = dx(d1-d2) Pi là tham số quyết định để chọn điểm tiếp theo là P hay S dựa vào dấu của nó. 2.1.4. Giải thuật Bresenham Pi = dx((m(xi+1)+b-yi)-(yi+1-m(xi+1)-b)) Pi = dx(2(m(xi+1)+b)-2yi+1) (*) Thay m = dy/dx vào phương trình (*) Pi =2dyxi – 2dxyi + 2dy + (2b-1)dx Pi =2dyxi – 2dxyi + c với c = 2dy + (2b-1)dx 2.1.4. Giải thuật Bresenham Vấn đề: Sau khi chọn điểm P hoặc S. Phải tính được Pi+1. Tính Pi+1: Pi+1 = 2dyxi+1 – 2dxyi+1 + c Pi+1 = 2dy(xi+1) – 2dxyi+1 + c Xét mối liên hệ giữa Pi+1 và Pi Pi+1-Pi = (2dy(xi+1) – 2dxyi+1 + c)- (2dyxi – 2dxyi + c) Pi+1-Pi = 2dyxi+2dy–2dxyi+1+c -2dyxi + 2dxyi – c Pi+1-Pi = 2dy–2dx(yi+1-yi) 2.1.4. Giải thuật Bresenham Nếu d1-d20 thì yi+1 = yi+1(chọn P) Pi+1-Pi = 2dy–2dx(yi+1-yi) Pi+1-Pi = 2(dy – dx) Pi+1 = Pi + 2(dy – dx) 2.1.4. Giải thuật Bresenham Tính P1: Thay điểm (x1,y1) vào Pi P1 =2dyx1 – 2dxy1 + c với c = 2dy + (2b-1)dx b = y1- mx1 m = dy/dx P1 =2dyx1 – 2dxy1 + 2dy + (2(y1- x1dy/dx)-1)dx P1 =2dyx1 – 2dxy1 + 2dy + (2(dxy1- dyx1)-dx) P1 =2dyx1 – 2dxy1 + 2dy + 2dxy1- 2dyx1-dx P1 =2dyx1 – 2dxy1 + 2dy + 2dxy1- 2dyx1-dx P1 =2dy - dx 2.1.4. Giải thuật Bresenham Sơ đồ khối 2.1.4. Giải thuật Bresenham Thủ tục 2.1.4. Giải thuật Bresenham Nhận xét Cải thiện tốc độ (số nguyên, phép cộng, dịch bit) Kết quả tương tự thuật toán DDA 2.1.5. Giải thuật MidPoint Cho hai điểm (x1,y1) và (x2,y2) Phương trình đường thẳng dạng tổng quát: Ax + By + C =0 Với dy = y2-y1, dx = x2-x1 A = dy B= -dx C= x2y1-x1y2 Đặt F(x,y) = Ax + By + C 2.1.5. Giải thuật MidPoint Tư tưởng: Thuật toán Midpoint đưa ra cách chọn điểm yp+1 là yp hay yp+1 dựa vào so sánh điểm thực Q(xp+1,y) với trung điểm M(xp+1,yp+1/2) của ENE. Nếu Q nằm trên M thì chọn điểm NE(xp+1, yp+1) Nếu Q nằm dưới M thì chọn điểm E(xp+1,yp) 2.1.5. Giải thuật MidPoint Cơ sở toán học: 0 nếu (x,y) nằm phía dưới đường thẳng 2.1.5. Giải thuật MidPoint Cách thực hiện: Đặt Pp = F(M) = F(xp+1,yp+1/2) Nếu Pp = 0 thì M nằm dưới hoặc thuộc đường thẳng, chọn NE Pp gọi là tham số quyết định. Dấu của nó sẽ quyết định lựa chọn điểm tiếp theo. 2.1.5. Giải thuật MidPoint Tính Pp: Pp = A(xp+1)+B(yp+1/2)+C Đặt Pold = Pp Pold = A(xp+1)+B(yp+1/2)+C Nếu chọn E thì trung điểm mới:Mnew(xp+2,yp+1/2) PnewE = A(xp+2)+B(yp+1/2)+C PnewE = A(xp+1)+B(yp+1/2)+C + A PnewE = Pold + dy (vì A= dy) 2.1.5. Giải thuật MidPoint Nếu chọn NE thì trung điểm mới:Mnew(xp+2,yp+3/2) PnewNE = A(xp+2)+B(yp+3/2)+C PnewNE = A(xp+1)+B(yp+1/2)+C + A + B PnewNE = Pold + dy – dx (vì A= dy, B = -dx) 2.1.5. Giải thuật MidPoint Tính P1: M(x1+1,y1+1/2) P1 = A(x1+1)+B(y1+1/2)+C Thay: A = dy; B = -dx, C= x2y1-x1y2 dy = y2-y1; dx = x2-x1 vào P1 P1 = dy(x1+1)-dx(y1+1/2)+ x2y1-x1y2 P1 = dyx1+dy-dxy1-dx1/2+ x2y1-x1y2 P1 = y2x1-y1x1+dy-x2y1+x1y1-dx1/2+ x2y1-x1y2 P1 = dy-(1/2)dx Do chỉ xét dấu và để tránh chia hai: P1 = 2dy-dx 2.1.5. Giải thuật MidPoint Sơ đồ khối 2.1.5. Giải thuật MidPoint Thủ tục 2.1.5. Giải thuật MidPoint Nhận xét Cải thiện tốc độ (số nguyên, phép cộng, dịch bit) Kết quả tương tự thuật toán DDA 2.2. THUẬT TOÁN VẼ ĐƯỜNG TRÒN 2.2.1. Một số vấn đề Sự hình thành Tính đối xứng 2.2.2. Thuật toán làm tròn Phương trình đường tròn có tâm tại gốc tọa độ, bán kính r : x2 + y2 = r2 y2 = r2 - x2 Ý tưởng: Chạy từ 90o tới 45o(từ 0 đến ) Tại mỗi giá trị của x, tính Vẽ tám điểm (làm tròn giá trị y) 2.2.2. Thuật toán làm tròn Sơ đồ khối 2.2.2. Thuật toán làm tròn Thủ tục 2.2.2. Thuật toán làm tròn Nhận xét Sử dụng phép nhân Tính căn bậc hai Sử dụng hàm làm tròn  Tốc độ chậm, tốn bộ nhớ 2.2.3. Thuật toán lượng giác Phương trình đường tròn dưới dạng tham số: x = r cos(φ) y = r sin(φ) Với 00 nếu (x,y) nằm ngoài đường tròn 2.2.4. Thuật toán MidPoint Đặt pold = F(M) pold = (xp+1)2 + (yp-1/2)2 – R2 Nếu chọn E, MnewE(xp+2,yp-1/2) pnewE= (xp+2)2 + (yp-1/2)2 – R2 pnewE= pold + 2xp+3 Nếu chọn SE, MnewSE(xp+2,yp-3/2) pnewSE= (xp+2)2 + (yp-3/2)2 – R2 pnewSE= pold + 2(xp-yp)+5 2.2.4. Thuật toán MidPoint Điểm khởi tạo (0,r), M(1,r-1/2) p1 = 12 +(r-1/2)2-r2 p1 =5/4 - r Vì chỉ xét dấu, đặt h = d1 – ¼ h=1-r 2.2.4. Thuật toán MidPoint Sơ đồ khối 2.2.4. Thuật toán MidPoint Thủ tục 2.2.4. Thuật toán MidPoint Nhận xét Thao tác với số nguyên Thực hiện các phép toán cộng, trừ, nhân hai Vẽ 8 điểm  Tốc độ cao, tiết kiệm bộ nhớ 2.2.5. Thuật toán Bresenham Phương trình đường tròn: y2 = R2 –x2 Giả sử vẽ được điểm (xi,yi) Vấn đề: Chọn điểm tiếp theo Không thể là Q(xi+1,y) Mà là: S1(xi+1,yi) hoặc S2(xi+1,yi-1) 2.2.5. Thuật toán Bresenham Đặt d1 = QS1 d2 = QS2 Tư tưởng: So sánh d2 với d2 d1=d2: Chọn S2 Q 2.2.5. Thuật toán Bresenham Tính d1 d1 = (yi)2 - y2 = (yi)2 - (R2- (xi + 1)2 ) Tính d2 d2 = y2 - (yi - 1)2 = (R2- (xi + 1)2 ) - (yi - 1)2 2.2.5. Thuật toán Bresenham Đặt Pi = d1 - d2 Pi là tham số quyết định chọn S1 hoặc S2 dựa vào dấu của nó Pi = (yi)2 -(R2- (xi + 1)2 )-((R2- (xi + 1)2)-(yi - 1))2 Pi = (yi)2 -R2+ (xi + 1)2-R2+ (xi + 1)2+(yi - 1)2 Pi = (yi)2 -2R2+ 2(xi + 1)2+(yi - 1)2 2.2.5. Thuật toán Bresenham Tính Pi+1 - Pi Pi+1 = (yi+1)2 -2R2+ 2(xi+1 + 1)2+(yi+1 - 1)2 Pi+1 = 2(yi+1)2 -2R2+ 2(xi)2+8xi+8 -2yi+1 + 1 Pi = (yi)2 -2R2+ 2(xi + 1)2+(yi - 1)2 Pi = 2(yi)2 -2R2+ 2 (xi)2 +4xi+ 2 - 2yi+1 Pi+1 – Pi = 2(yi+1)2 -2R2+ 2(xi)2+8xi+8 -2yi+1 + 1 - (2(yi)2 -2R2+ 2 (xi)2 +4xi+ 2 - 2yi+1) Pi+1 – Pi = 2(yi+1)2 -2R2+ 2(xi)2+8xi+8 -2yi+1 + 1 - 2(yi)2 +2R2 - 2 (xi)2 -4xi- 2 + 2yi-1 Pi+1= Pi +4xi+6+2((yi+1)2-yi2)-2(yi+1-yi) 2.2.5. Thuật toán Bresenham Nếu chọn S1 yi+1 = yi Pi+1 = Pi + 4xi+6 Nếu chọn S2 yi+1 = yi-1 Pi+1 = Pi + 4(xi-yi)+10 2.2.5. Thuật toán Bresenham Điểm đầu tiên (0,R) P1 = (R)2 -2R2+ 2(0 + 1)2 +(R - 1)2 P1 = R2 -2R2+ 2 + R2 -2R +1 P1 = 3 -2R 2.2.5. Thuật toán Bresenham Sơ đồ khối 2.2.5. Thuật toán Bresenham Thủ tục 2.2.5. Thuật toán Bresenham Nhận xét 2.2.6. Thuật toán xấp xỉ Sinh viên tự tìm hiểu 2.3. THUẬT TOÁN VẼ ELIPSE 2.3.1. Thuật toán làm tròn Phương trình elip có tâm tại gốc tọa độ a: Độ dài trục chính b: Độ dài trục phụ  (*) 2.3.1. Thuật toán làm tròn Tính đối xứng Vẽ được 1 điểm ta suy ra 3 điểm khác bằng cách lấy đối xứng Tư tưởng Khởi tạo: x=0;y=b Cho x chạy từ 0 đến a Tính y theo công thức (*) Vẽ đối xứng 4 điểm 2.3.1. Thuật toán làm tròn Sơ đồ khối 2.3.1. Thuật toán làm tròn Thủ tục 2.3.1. Thuật toán làm tròn Nhận xét Thao tác với số thực Sử dụng phép nhân, chia Sử dụng căn bậc hai  Tốn bộ nhớ, chậm 2.3.2. Thuật toán lượng giác Phương trình elip x = a*cos(φ) y = b*sin(φ) Tư tưởng Cho φ chạy từ 0 đến π/2 Tại mỗi giá trị của φ xác định x và y theo phương trình Vẽ 4 điểm 2.3.2. Thuật toán lượng giác Sơ đồ khối 2.3.2. Thuật toán lượng giác Thủ tục 2.3.2. Thuật toán lượng giác Nhận xét Thao tác với số thực Dùng các hàm sin, cos, làm tròn Lưu trữ giá trị φ  Tốn bộ nhớ, chạy chậm 2.3.3. Thuật toán Vanaken Phương trình elip có tâm tại gốc tọa độ F(x,y)=b2x2 + a2y2 - a2b2=0 2.3.3. Thuật toán Vanaken Tìm ranh giới giữa hai miền trong ¼ elip Vị trí: P là tiếp điểm của tiếp tuyến có hệ số góc -1 Xác định: Vecto vuông góc với tiếp tuyến tại tiếp điểm -> gradient Tại P các thành phần i và j của vecto gradient có cùng độ lớn 2.3.3. Thuật toán Vanaken Vùng 1 x thay đổi thì y thay đổi theo Vùng 2 y thay đổi thì x thay đổi theo 2.3.3. Thuật toán Vanaken Xét vùng 1 Bắt đầu từ (0,b) Giả sử vẽ được (xi,yi) Vấn đề: Chọn điểm tiếp theo E(xi+1, yi) hoặc SE(xi+1,yi-1) 2.3.3. Thuật toán Vanaken Xét vùng 1 Tham số quyết định pi: pi =F(x,y)=F(xi+1,yi-1/2) pi = b2(xi+1)2 + a2(yi-1/2)2 -a2b2 Tính pi+1: pi+1 = F(xi+1+1,yi+1-1/2) pi+1 = b2(xi+1+1)2 + a2(yi+1-1/2)2 -a2b2 Tính pi+1 - pi pi+1 - pi = b2((xi+1+1)2 - (xi+1)2 )+ a2((yi+1-1/2)2 - (yi-1/2)2 ) pi+1 = pi + 2b2xi+1+ b2 + a2((yi+1-1/2)2 - (yi-1/2)2 ) 2.3.3. Thuật toán Vanaken Xét vùng 1 Nếu pi =0 chọn SE  xi+1=xi+1 yi+1=yi -1 pi+1 = pi + 2b2xi(xi+1) +b2 + a2((yi -1 -1/2)2 - (yi-1/2)2 ) pi+1 = pi + 2b2xi +3b2 +a2(-3yi +9/4 +yi -1/4) pi+1 = pi + 2b2xi +3b2 +a2(-2yi +2) pi+1 = pi + b2(2xi +3) + a2(-2yi +2) 2.3.3. Thuật toán Vanaken Xét vùng 1 Tính p1: Tại (0,b) p1 = F(x1+1,y1-1/2) p1 = b2 + a2(b-1/2)2 -a2b2 p1 = b2 - a2b +a2/4 2.3.3. Thuật toán Vanaken Xét vùng 2 Lấy toạ độ của Pixel sau cùng trong phần 1 để tính giá trị ban đầu cho phần 2. Giả sử pixel (xk,yk) vừa chuyển quét cuối cùng của phần 1 nhập vào bước j cho phần 2 (xj,yj). Pixel kế tiếp có thể là S(xj,yj-1) hoặc SE(xj+1, yj-1) 2.3.3. Thuật toán Vanaken Xét vùng 2 Tham số quyết định qj = F(xj+1/2,yj-1) qj = b2(xj+1/2)2 + a2(yj-1)2 -a2b2 Tính qj+1 = F(xj+1+1/2,yj+1-1) qj+1 = b2(xj+1+1/2)2 + a2(yj+1-1)2 -a2b2 Tính qj+1 - qj qj+1-qj=b2((xj+1+1/2)2-(xj+1/2)2)+ a2((yj+1-1)2 - (yj-1)2) qj+1=qj+b2((xj+1+1/2)2-(xj+1/2)2)+a2- 2a2yj+1 2.3.3. Thuật toán Vanaken Xét vùng 2 Nếu qj =0 chọn S yj+1=yj -1 xj+1= xj qj+1 = qj + a2- 2a2(yj-1) qj+1 = qj + a2(3 - 2yj ) 2.3.3. Thuật toán Vanaken Xét vùng 2 Tính q1: Tại (xk+1/2,yk -1) q1 = b2(xk+1/2)2 + a2(yk-1)2 -a2b2 2.3.3. Thuật toán Vanaken Sơ đồ khối 2.3.3. Thuật toán Vanaken Thủ tục 2.3.3. Thuật toán Vanaken Nhận xét 2.3.3. Thuật toán Bresenham Sinh viên tự tìm hiểu 2.4. Giải thuật sinh đa giác 2.4. Thuật toán sinh đa giác Biểu diễn đa giác thông qua Tập các đoạn thẳng Tập các điểm thuộc đa giác 2.4. Thuật toán sinh đa giác Các loại đa giác Đa giác lồi Là đa giác có đường thẳng nối bất ký 2 điểm bên trong nào của đa giác đều nằm trọn trong đa giác Đa giác lõm Là đa giác không lồi 2.4. Thuật toán sinh đa giác Xác định đa giác cần biết Số cạnh Toạ độ các đỉnh của đa giác 2.4. Thuật toán sinh đa giác Thuật toán Polygon (arrayx, arrayy,n) Begin if (nxmax; y1,y2>ymax x1,x2xmax  b2=1 yymax  b4=1 b1 là dấu của x-xmin b2 là dấu của xmax-x b3 là dấu của y-ymin b4 là dấu của ymax-y 2.5.2. Thuật toán CohenSutherland Quy ước nếu P(x,y) thuộc cạnh V thì Kod(P) =0000 Cho P1P2, các trường hợp xảy ra P1P2 thuộc V khi Kod(P1)=Kod(P2)=0000 P1P2 nằm ngoài V khi (Kod(P1)ANDKod(P2))0000 P1P2 chưa xác định khi (Kod(P1)ANDKod(P2)=0000)AND((Kod(P1)0000) OR (Kod(P20000)) 2.5.2. Thuật toán CohenSutherland Tư tưởng Xác định giao điểm của đoạn thẳng với các cạnh của cửa sổ sau đó bỏ phần không thuộc cửa sổ Cho cửa sổ V(xmin,ymin,xmax,ymax), P1(x1,y1), P2(x2,y2) B1: Tính Kod(P1), Kod(P2) B2: Nếu Kod(P1) = Kod(P2) = 0000  P1P2 thuộc V Nhảy tới B5 B3: Nếu (Kod(P1)ANDKod(P2))0000  P1P2 nằm ngoài V  Nhảy tới B6 2.5.2. Thuật toán CohenSutherland Tư tưởng B4: Nếu không thỏa mãn B2, B3 B4.1: Nếu Kod(P1) = 0000 thì hoán vị P1 với P2 để Kod(P1)0000. Đặt b1b2b3b4 = Kod(P1) Nếu b1=1 thì y1new = y1+(xmin-x1)*(y2-y1)/(x2-x1) x1new = xmin Nếu b2=1 thì y1new = y1+(xmax-x1)*(y2-y1)/(x2-x1) x1new = xmax Nếu b3=1 thì x1new = x1+(ymin-y1)*(x2-x1)/(y2-y1) y1new = ymin Nếu b4=1 thì x1new = x1+(ymax-y1)*(x2-x1)/(y2-y1) y1new = ymax 2.5.2. Thuật toán CohenSutherland Tư tưởng B5: Vẽ P1P2 B6: Thoát 2.5.2. Thuật toán CohenSutherland Sơ đồ khối 2.5.2. Thuật toán CohenSutherland Thủ tục 2.5.2. Thuật toán CohenSutherland Nhận xét Đơn giản Khi xác định nhiều giao điểm, sử dụng phép nhân, chia  Chậm, tốn bộ nhớ 2.5.3. Thuật toán Liang-Basky Cho P1(x1,y1), P2(x2,y2) Phương trình đường thẳng dạng tham số x = x1 + tdx y= y1+tdy Với dx = x2-x1 dy = y2-y1 t thuộc [0,1] Cho cửa sổ cắt V(xmin,ymin,xmax,ymax) 2.5.3. Thuật toán Liang-Basky P1P2 thuộc V khi xmin0 thì phải xác định t1 và t2 t1 = Max{0,Max(qk/pk)} với các pk0 2.5.3. Thuật toán Liang-Basky Xác định đoạn thẳng xv1 = x1 + t1dx yv1 = y1 + t1dy xv2 = x1 + t2dx yv2 = y1 + t2dy 2.5.3. Thuật toán Liang-Basky Tư tưởng B1: Đặt t1=0, t2=1 B2: Tính pk và qk theo công thức với k=1,2,3,4 B3: Nếu có pk=0 thì đoạn thẳng song song với cạnh cửa sổxử lý riêng B4: Nếu pk0 thì B4.1: Cho k chạy từ 1 đến 4 B4.2: Đặt t = qk/pk B4.3: Nếu pk 0 thì đặt t2 = min(t2,t) 2.5.3. Thuật toán Liang-Basky Tư tưởng B5: Nếu t1t2  P1P2 nằm ngoài VKết thúc 2.5.3. Thuật toán Liang-Basky Sơ đồ khối 2.5.3. Thuật toán Liang-Basky Thủ tục 2.5.3. Thuật toán Liang-Basky Nhận xét Số lượng phép nhân, chia trong vòng lặp ít hơn 2.5.4. Thuật toán chia nhỏ trung điểm Ý tưởng Dựa trên phương pháp chia đôi 2.5.4. Thuật toán chia nhỏ trung điểm Tiến hành Cho P1(x1,y1), P2(x2,y2): Đoạn thẳng P1P2 Chia đôi P1P2, trung điểm Pm xm =(x1+x2)/2 ym=(y1+y2)/2 Xác định hai đoạn thẳng mới P1Pm,PmP2 thuộc loại cắt nào Các đoạn thẳng thuộc loại thứ 3 được chia đôi tiếp Lặp lại quá trình này đến khi các đoạn thẳng thuộc loại 1(vẽ) hoặc loại 2 (hủy bỏ) 2.5.4. Thuật toán chia nhỏ trung điểm Số lần chia Đoạn thẳng có m điểm Số phép chia là n 2n = m  n=log2m 2.5.4. Thuật toán chia nhỏ trung điểm Nhận xét Sử dụng một phép cộng, một phép chia 2 Áp dụng tốt cho phần cứng thiết bị 2.5.5. Thuật toán xén vùng Tư tưởng Duyệt lần lượt (theo chiều kim đồng hồ) các cạnh đa giác Nếu đỉnh duyệt xuất phát từ trong cửa sổ theo cạnh đa giác đi ra ngoài cửa sổ: lưu trữ giao của cạnh đa giác với biên cửa sổ Nếu đường đi từ ngoài vào trong cửa sổ: lưu trữ đỉnh đa giác và giao điểm Ví dụ xét hai đỉnh đa giác S và P: 2.6. Thuật toán tô màu 2.6.1. Một số khái niệm Lân cận 4 Hai điểm ảnh được gọi là lân cận 4 nếu chúng kề nhau theo đường thẳng đứng hoặc nằm ngang Lân cận 8 Hai điểm ảnh được gọi là lân cận 8 nếu chúng kề nhau theo đường thẳng đứng, ngang và đường chéo. 2.6.2. Thuật toán tô màu loang Cho miền kín V có mầu biên Cb.Tô kín V bằng mầu tô Ct Cho điểm P(x,y) Є V Tư tưởng Tô điểm P(x,y) với màu Ct Tô lân cận 4 hoặc lân cận 8 của P nếu không phải là biên và chưa được tô Lặp lại quá trình trên đến khi tô hết V 2.6.2. Thuật toán tô màu loang Thủ tục 2.6.2. Thuật toán tô màu loang Nhận xét Đơn giản Tô được miền có hình dạng bất kỳ Sử dụng đệ quy tràn stack không tô được vùng lớn 2.6.2. Thuật toán tô màu loang Cải tiến Dựa vào điểm khởi tạo trong V để quyết định số lần gọi đệ quy 2.6.3. Thuật toán tô màu biên Cho miền kín V có mầu biên Cb.Tô kín V bằng mầu tô Ct Cho điểm P(x,y) Є V 2.6.3. Thuật toán tô màu biên Tư tưởng Từ điểm xuất phát P(x,y) Tăng x để xác định xmax Giảm x để xác định xmin Vẽ đường nối (xmin,y,xmax,y), chia V thành hai phần Tăng y xác định xmin, xmax mới và lặp lại quá trình trên cho nửa thứ nhất Giảm y, xác định xmin, xmax mới và lặp lại quá trình trên cho nửa thứ hai 2.6.3. Thuật toán tô màu biên Thủ tục Sinh viên tự viết 2.6.3. Thuật toán tô màu biên Nhận xét Không sử dụng đệ quy  tránh tràn stack Tô màu nhanh hơn Khó khăn khi tô vùng phức tạp 2.6.4. Tô màu đường tròn Tư tưởng Tìm hình vuông nhỏ nhất ngoại tiếp đường tròn Xác định điểm trên bên trái (xc-r, yc-r) Xác định điểm dưới bên phải (xc+r, yc+r) 2.6.4. Tô màu đường tròn Tư tưởng Cho i đi từ xc-r đến xc+r Cho j đi từ yc-r đến yc+r Tính khoảng cách d giữa hai điểm (i,j) và tâm (xc,yc) Nếu dx0 (y-y0)(yi+1-y0) Max ( Pi+1.y, Pi-1.y) Pi là đỉnh cực trị (cực đại ) Pi-1.y Pi.y > Pi+1.y  Pi là đỉnh đơn điệu. Pi = Pi+1 và Pi.y Max ( Pi+2.y, Pi-1.y) thì đoạn [Pi,Pi+1] là đoạn cực trị (cực tiểu hay cực đại ). Pi = Pi+1 và Pi-1.y Pi.y > Pi+2.y thì đoạn [Pi,Pi+1] là đoạn đơn điệu. 2.6.5. Tô màu đa giác Điểm trong đa giác Tư tưởng Với mỗi đỉnh của đa giác ta đánh dấu là 0 hay 1 theo qui ước như sau: nếu là đỉnh cực trị hay đoạn cực trị thì đánh số 0. Nếu là đỉnh đơn điệu hay đoạn đơn điệu thì đánh dấu 1. Xét số giao điểm của tia nửa đường thẳng từ P là điểm cần xét với biên của đa giác. Nếu số giao điểm là chẵn thì kết luận điểm không thụôc đa giác. Ngược lại, số giao điểm là lẻ thì điểm thuộc đa giác. 2.6.6. Tô màu dòng quét Ý tưởng Sử dụng giao điểm giữa các biên đa giác và đường quét để nhận ra pixel có trong đa giác? 2.6.6. Tô màu dòng quét Thuật toán Cho trước đa giác P với n đỉnh v0 đến vn-1(vnΞv0) Cho trước C là màu tô đa giác Giao của mỗi đường quét với các cạnh đa giác thì sẽ là điểm vào hay điểm ra đa giác Tìm ra các đoạn thẳng nằm trong đa giác để vẽ theo màu C 2.6.6. Tô màu dòng quét Với mỗi dòng quét Tìm giao điểm với các cạnh của đa giác Sắp xếp theo chiều tăng của x Tô các điểm ảnh giữa các cặp giao điểm 2.6.6. Tô màu dòng quét Tìm