Chương 1: Tổng quan về kỹ thuật đồ họa 3. Tính Video Ram của các màn hình lần lượt có độ phân giải là 640x480, 1024x768, 1280x1024 mà có mỗi pixel được mô tả là 8bít, 12 bit, 24 bit. Nếu chúng ta dùng các giá trị 12bit cho mỗi pixel trong một bảng tham chiếu lookup table, có bao nhiêu hạng mục mà lookup table có được? 5. Tại sao phải chuẩn hoá các phần mềm? Liệt kê và tìm hiểu các chuẩn hó phần mềm đồ hoạ.
Bài tập trắc nghiệm: 1. Tỷ số phương (aspect ratio) của màn hình là 1,4 vậy một hình tròn khi hiển thị trên màn hình đó sẽ cho: a. Hình ellipse nằm ngang (bán kính theo trục x dài hơn bán kính theo trục y) c. Hình ellipse đứng (bán kính theo trục x ngắn hơn bán kính theo trục y) d.
Cho màn có độ phân giải 1024x1024 và mỗi pixel được mô tả 24bít vậy video RAM của màn hình là: a. Nếu ta dùng các giá trị 24 bit cho mỗi pixel trong một bảng LUT. Thì bảng LUT có số màu là: a.com https://fb.com/tailieudientucntt Chương 2: Các giải thuật sinh thực thể cơ sở CHƯƠNG 2: CÁC GIẢI THUẬT SINH THỰC THỂ CƠ SỞ 1. CÁC ĐỐI TƯỢNG ĐỒ HOẠ CƠ SỞ 1.
Hệ toạ độ thế giới thực và hệ toạ độ thiết bị a. Hệ toạ độ thế giới thực (WCS: World Coordinate System) WCS hay hệ toạ độ thực là hệ toạ độ được dùng mô tả các đối tượng trong thế giới thực. Một trong hệ toạ độ thực được dùng nhiều nhất là hệ toạ độ Descartes. Bất kì điểm nào trong mặt phẳng được mô tả bằng cặp toạ độ (x,y) trong đó x,y ∈R.
Gốc toạ độ là điểm O có toạ độ (0,0), Ox,Oy lần lượt là trục hoành và trục tung và x,y là hoành độ và tung độ. Các toạ độ thế giới thực cho phép người sử dụng bất kì một thứ nguyên (dimension) qui ước: foot, cm, nm, km, inch. Hệ toạ độ thiết bị (DCS: Device Coordinate System) Hệ toạ độ thiết bị là hệ toạ độ được dùng bởi một thiết bị xuất cụ thể nào đó như máy in, màn hình. Các điểm được biểu diễn bởi cặp toạ độ (x,y), nhưng x,y ∈N.
Điểm trong toạ độ thực được định nghĩa liên tục, còn trong toạ độ thiết bị thì rời rạc do tính chất của tập các số tự nhiên. Các toạ độ (x,y) có giới hạn trong một khoảng nào đó. Điểm và đoạn thẳng a. Điểm Trong hệ toạ độ hai chiều (x,y), ngoài ra nó còn có tính chất màu sắc.
Đoạn thẳng + Biểu diễn tường minh: y = f(x) Một đoạn thẳng được xác định nếu biết 2 điểm thuộc nó. Phương trình đoạn thẳng đi qua 2 điểm P (x1,y1) và Q(x2,y2) như sau: (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) Q(x2 , y2) y = ((y2-y1)/(x2-x1))x + y1 - ((y2-y1)/(x2-x1))x1 y = kx + m k = (y2-y1)/(x2-x1) Độ dốc hay hệ số góc của đường P(x1, y1) m = y1- kx1Đoạn chắn trên trục y Δy = kΔx (tức là khi x thay đổi thì y thay đổi theo) m Hình 2.1 Vẽ đoạn thẳng PQ + Biểu diễn không tường minh: ax+by+c=0 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương 2: Các giải thuật sinh thực thể cơ sở Ta có (y2-y1)x - (x2-x1)y + (x2-x1)y1 - (y2-y1)x1 = 0 (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 hay rx + sy + t = 0 s = -(x2-x1 ) r = (y2-y1) và t = x2y1 - x1y2 + Biểu diễn thông qua tham số: P(u) = P1 + u(P2 - P1)u ∈[0,1] x(u) = x1 + u( x2 - x1 ) y (u)= y1 + u( y2 - y1 ) 2. CÁC GIẢI THUẬT XÂY DỰNG THỰC THỂ CƠ SỞ 2. Giải thuật vẽ đoạn thẳng thông thường Nguyên lý chung: cho một thành phần toạ độ x hay y biến đổi theo từng đơn vị và tính độ nguyên còn lại sao cho gần với toạ độ thực nhất.
y 2 − y1 Ta có y = (x − x1 ) − y1 x2 − x1 Cho x thay đổi tìm y, trong bài này cho x1 thay đổi tiến tới x2 ta chọn đơn vị nhỏ nhất của màn hình Δx=1. Giải thuật thông thường: void dline(int x1,int y1, int x2,int y2, int color) { float y; int x; for (x=x1; x<=x2; x++) { y = y1 + (x-x1)*(y2-y1)/(x2-x1) ; putpixel(x, Round(y), color ); } } 2. Thuật toán DDA (Digital Differential Analizer) Tiến hành tính tại mỗi bước vốn sử dụng kết quả từ bước trước đó. Giả sử bước i đã tính (xi,yi), bước tiếp (xi+1,yi+1) sẽ nghiệm đúng với Δy/Δx=k.
Δy = yi+1 -yi Δx = xi+1-xi Vậy:yi+1 =yi +kΔxvà xi+1 =xi + Δy/k - 0 < k < 1 (đảm bảo sự thay đổi của x trên trục toạ độ sẽ lớn hơn y) - Bắt đầu x=x1 (x1<x2) và y=y1 xi+1 = xi + 1 đặt Δx=1 (gia số theo x) yi+1= yi + k cứ như thế đến x2 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương 2: Các giải thuật sinh thực thể cơ sở - Khi k>1 bắt đầu y=y1 (y1<y2) và x=x1 - đặt Δy =1 (gia số theo y) xi+1 =xi + 1/k tiếp tục đến y2 Thuật toán void ddaline (int x1,int y1,int x2,int y2,int c) { int x=x1; float y=y1; float k=(float)(y2-y1)/(x2-x1); Begin putpixel(x,round(y),c); for(int i=x1;i<=x2;i++) { m=dy/dx; x++; x=x1; y=y+k; y=y1; putpixel(x,round(y),c); } } x<x2 Chú ý: - y=y+k nhanh hơn hẳn y=k*x+m (khử được phép nhân với số thực) x=x+1; - Hạn chế về tốc độ vì cộng số thực và làm tròn y=y+m; - Bài tập: viết thuật toán cho cả 4 trường hợp k.2 Sơ đồ khối thuật toán DDA 2. Giải thuật Bresenham 1960 Bresenham thuộc IBM theo nguyên lý tìm ra các điểm gần với đường thẳng dựa trên độ phân giải hữu hạn. Giải thuật này loại bỏ được các phép toán chia và phép toán làm tròn như ta đã thấy trong giải thuật DDA. Xét đoạn thẳng với 0 < k < 1 yi+1 d2 d1 yi xi xi+1 Hình 2.3 Mô tả giải thuật Bresenham 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương 2: Các giải thuật sinh thực thể cơ sở Gọi (xi+1,y) là điểm thuộc đoạn thẳng, ta có y=k(xi+1)+b d1 = y - yi = k(xi +1) + b - yi d2 = yi+1 - y = yi + 1 - k(xi + 1) - b - Nếu d1 <= d2 => yi+1 = yi - Ngược lại d1 > d2 => yi+1 = yi +1 Đặt D = d1 - d2= 2k(xi + 1) - 2yi + 2b - 1 Có k=Δy/Δx Đặt Pi = ΔxD = Δx (d1 - d2) Pi = Δx(2Δy/Δx(xi +1)- 2yi +2b-1) = 2Δyxi +2Δy -2Δxyi + 2bΔx -Δx Ta tính bước tiếp: Pi+1 = 2Δyxi+1 +2Δy -2Δxyi+1 + 2bΔx -Δx Pi+1 - Pi = -2Δx(yi+1 -yi) + 2Δy(xi+1 -xi) Có xi+1 =xi+1 nên: Pi+1 - Pi = - 2Δx(yi+1 -yi) + 2Δy = 2Δy - 2Δx(yi+1 -yi) Nếu Pi <= 0 thì yi +1 = yi Pi+1 = Pi + 2Δy Nếu Pi > 0 thì yi+1 = yi +1 Pi+1 = Pi + 2Δy - 2Δx Tính giá trị đầu: P1? P1 = Δx(d1 - d2) = Δx(2Δy/Δx(x1 +1)- 2y1 +2b-1) = 2Δyx1 +2Δy -2Δxy1 + 2bΔx -Δx Có y1=kx1 + b = Δy/Δx x1 +b P1 = 2Δyx1 +2Δy -2Δx((Δy/Δx)x1 +b) + 2bΔx -Δx = 2Δyx1 +2Δy -2Δyx1 - 2bΔx + 2bΔx -Δx P1 = 2Δy - Δx 21 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương 2: Các giải thuật sinh thực thể cơ sở /*Thuat toan Bresenham ve dthang (0<k<1) */ B¾t ®Çu void Bre_line(int x1, int y1, int x2, int y2, int c) {int x, y, dx, dy,p,const1,const2; x = x1 ; x=x1;y=y1; y = y1; y = y1; dxdx=x2-x1; = x2 - x1; dx = x2 - x1; dy = y2 - y1; P=dy=y2-y1; dx - 2dy; dy = y2 - y1; p = 2*dy - dx; Putpixel (x ,y); const1 = 2*dy; const2 = 2*(dy-dx); No P>0 for (x=x1; x<=x2; x++) { p= P = Pp+2dy-2dx - 2dy + 2dx putpixel(x, y, c); x=x+1 yes if (p < 0) p=p+2dy P = P - 2dy y=y+1 p += const1; // p=p + 2dy else { yes x < x2 p +=const2; //p=p+2dy-2dx y++; no } KÕt thóc } } Hình 2.4 Sơ đồ khối thuật toán Bresemham cho đường thẳng 2.
Giải thuật trung điểm-Midpoint Jack Bresenham 1965 / Pitteway 1967, áp dụng cho việc sinh các đường thẳng và đường tròn 1985. Xét trung điểm của đoạn AB (M) Nếu M ở trên đoạn thẳng AB thì chọn B còn M ở dưới đoạn thẳng AB chọn A Công thức đơn giản hơn, tạo được các điểm tương tự như với Bresenham d = f(xi + 1, yi + 1/2) là trung điểm của đoạn AB d<0 d>0 A A B Hình 2.5 Mô tả giải thuật Midpoint So sánh hay kiểm tra M sẽ được thay bằng việc xét giá trị d. - d > 0 điểm B được chọn khi đó yi+1 = yi 22 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương 2: Các giải thuật sinh thực thể cơ sở - nếu d < 0 điểm A được chọn khi đó yi+1 = yi + 1 Trường hợp d = 0 chúng ta có thể chọn điểm bất kỳ hoặc A, hoặc B. Sử dụng phương pháp biểu diễn không tường minh f(x,y)= ax +by +c =0 (1)dx =x2-x1 dy =y2-y1 Biểu diễn tường minh: y= (dy/dx)x +B hay f(x,y)=0= xdy - ydx +Bdx (2) So sánh (1) và (2) a=dyb=-dx c= Bdx Có f(x,y)=0 với mọi (x,y) thuộc đường thẳng Đặt di=f(xi+1,yi+1/2) = a(xi+1) +b(yi +1/2) +c + Nếu chọn A (d<0) thì M sẽ tăng theo 2 hướng x,y di+1=f(xi+2,yi+3/2) = a(xi+2) +b(yi +3/2) +c di+1 – di = a+b Hay di+1 = di + dy - dx + Nếu chọn B (d>0) thì M sẽ tăng theo x di+1=f(xi+2,yi+1/2) = a(xi+2) +b(yi +1/2) +c di+1 - di = a Hay di+1 = di + dy Tính d1 ? d1 = f(x1+1,y1+1/2) = a(x1+1) +b(y1 +1/2) +c = ax1 +by1 +c +a +1/2 b = f(x1,y1) +a +b/2 Có (x1,y1) là điểm bắt đầu, nằm trên đoạn thẳng nên f(x1,y1) = 0 Vậy d1 = a+ b/2 = dy - dx/2 23 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chương 2: Các giải thuật sinh thực thể cơ sở /* Thuat toan Midpoint de ve doan thang B¾t ®Çu (0<k<1) */ void Mid_line(int x1, int y1, int x2, int y2, int c) x = x1 ; y = y1; { int x, y, dx, dy,d; dx = x2 - x1; y = y1; dy = y2 - y1; d = dy - dx/2; dx = x2 - x1; dy = y2 - y1; Putpixel (x ,y); d= dy - dx/2; for (x=x1; x<=x2; x++) No { d <= 0 putpixel(x, y, c); d = d + dy - dx x=x+1 yes if (d <= 0) d = d + dy; d = d + dy y=y+1 else { yes x < x2 y ++; d = d + dy - dx; no }} KÕt thóc } Hình 2.6 Sơ đồ khối giải thuật Midpiont cho đoạn thẳng 2.
Giải thuật sinh đường tròn (Scan Converting Circles)(Bresenham) - Phương trình đường tròn đi qua tâm có toạ độ (xc,yc) là: (x - xc)2 + (y - yc)2 = r2 Hình tròn là hình đối xứng tám cách Hình 2.