Page 2
Giải thuật xây dựng các thực thể cơ sở Giải thuật sinh đường thẳng – Line Giải thuật sinh đường tròn - Circle Giải thuật VanAken sinh Ellipse Giải thuật sinh đa giác Giải thuật sinh ký tự (c) SE/FIT/HUT 2002 2
Document content
Page 3
Rời rạc hoá điểm ảnh (Scan Conversion rasterization) Scan Conversion rasterization Tính chất các đối tượng cần đảm bảo : smooth continuous pass through specified points uniform brightness efficient (c) SE/FIT/HUT 2002 3
Page 4
Biểu diễn đoạn thẳng Biểu diễn tường minh (y-y1)/( x-x1) = ( y2-y1)/( x2-x1)1 P(x , y ) 2 2 y = kx + m Biểu diễn không tường minh u (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 hay rx + sy + t = 0 P(x , y ) 1 1 Biểu diễn tham biến P(u) = P1 + u(P2 - P1) u [0,1] m (c) SE/FIT/HUT 2002 4
Page 5
Thuật toán DDA (Digital Differential Analizer) Giải thuật thông thường Giải thuật DDA DrawLine(int x1,int y1, int x2,int y2, int color) Với 0 < k < 1 { x = x + 1 i+1 i float y; y = y + k i+1 i int x; với i=1,2,3.... for (x=x1; x<=x2; x++) { y = y1 + (x-x1)*(y2-y1)/(x2-x1) WritePixel(x, Round(y), color ); }} (c) SE/FIT/HUT 2002 5
Page 6
Giải thuật Bresenham 1960 Bresenham thuộc IBM điểm gần với đường thẳng dựa trên độ phân giai hưu hạn 2 d1 loại bỏ được các phép toán d2 chia và phép toán làm tròn 1 như ta đã thấy trong giải thuật DDA 0 Xét đoạn thẳng với 0 < k < 1 0 1 2 (c) SE/FIT/HUT 2002 6
Page 7
Giải thuật Bresenham d = y - yi = k(xi +1) + b - yi 2 A d = yi+1 - y = yi + 1 - k(xi + 1) - b 1 yi+1 d1 d2 yi B xi x+1 i (c) SE/FIT/HUT 2002 7
Page 9
Giải thuật trung điểm-Midpoint Jack Bresenham 1965 / Pitteway 1967 VanAken áp dụng cho việc sinh các đường thẳng và đường tròn 1985 Các công thức đơn giản hơn, tạo được các điểm tương tự như với Bresenham y A i+1 d = F (xi + 1, yi + 1/2) là trung điểm của M B đoạn AB Việc so sánh, hay kiểm tra M sẽ được thay ( x , y ) bằng việc xét giá trị d. i i Nếu d > 0 điểm B được chọn, yi+1 = yi xi xi+1 nếu d < 0 điểm A được chọn. yi+1 = yi + 1 Trong trường hợp d = 0 chúng ta có thể chọn điểm bất kỳ hoặc A, hoặc B. (c) SE/FIT/HUT 2002 9
Page 10
Bresenham’s Algorithm: Midpoint Algorithm If di > 0 then chọn điểm A ⇒ trung điểm tiếp theo sẽ có dạng: 3 ( ) 3 x +2, y + ⇒ d = a x +2 +by + +c i i 2 i+1 i i 2 = d +a+b i (c) SE/FIT/HUT 2002 10
Page 11
Midpoint Line Algorithm dx = x_end-x_start dy = y_end-y_start d = 2*dy-dx initialisation x = x_start y = y_start while x < x_end if d <= 0 then d = d+(2*dy) choose B x = x+1 else d = d+2*(dy-dx) x = x+1 choose A y = y+1 endif SetPixel(x,y) endwhile (c) SE/FIT/HUT 2002 11
Page 12
Giải thuật B¾t ®Çu Bresenham's Midpoint x = x1 ;y = y1; dx = x2 - x1; dy = y2 - y1; d = dy - dx/2; Putpixel (x ,y); No d <= 0 x = x + 1 d = d + dy - dx yes d = d + dy y = y + 1 yes x < x2 no KÕt thóc (c) SE/FIT/HUT 2002 12
Page 13
Sinh đường tròn Scan Converting Circles Explicit: y = f(x) y = ± R2 − x2 Usually, we draw a quarter circle by incrementing x from 0 to R in unit steps and solving for +y for each step. Parametric: x = Rcosθ - by stepping the angle from 0 to 90 y = Rsinθ - avoids large gaps but still insufficient. Implicit: f(x) = x2+y2-R2 If f(x,y) = 0 then it is on the circle. f(x,y) > 0 then it is outside the circle. f(x,y) < 0 then it is inside the circle. (c) SE/FIT/HUT 2002 13
Page 14
Midpoint Circle Algorithm Sử dụng phương pháp biểu diễn không tường minh trong giải thuật Thực hiện giải thuật trên 1/8 đường tròn và lấy đối xứng xho các góc còn lại. Với di là giá trị của đường tròn tại một điểm bất kỳ ta có (c) SE/FIT/HUT 2002 14
Page 15
Midpoint Circle Algorithm As with the line, we determine the value of the decision variable by substituting the mid-point of the next pixel into the implicit form of the circle: 1 2 d =(x +1)2 +y − −r2 i i i 2 If di < 0 we choose pixel A otherwise we choose pixel B Note: we currently assume the circle is centered at the origin (c) SE/FIT/HUT 2002 15
Page 16
Midpoint Circle Algorithm d = 1-r x = 0 initialisation y = r stop at diagonal ⇒ end of octant while y < x if d < 0 then d = d+2*x+3 x = x+1 choose A else d = d+2*(x-y)+5 x = x+1 choose B y = y-1 endif SetPixel(c +x,c +y) x y endwhile Translate to the circle center (c) SE/FIT/HUT 2002 16
Page 17
Scan Converting Ellipses F x y( , ) = b x2 2 + a y2 2 −a b2 2 = 0 2a is the length of the major axis along the x axis. 2b is the length of the minor axis along the y axis. The midpoint can also be applied to ellipses. For simplicity, we draw only the arc of the ellipse that lies in the first quadrant, the other three quadrants can be drawn by symmetry (c) SE/FIT/HUT 2002 17
Page 18
Scan Converting Ellipses: Algorithm A M tiep tuyen = -1 B gradient B C M Firstly we divide the quadrant into two regions i Boundary between the two regions is the point at which the curve has a slope of -1 the point at which the gradient vector has the i and j components of equal magnitude grad F x y( , )= ∂F/∂xi+∂F/∂yj=2b x2 i+2a y2 j (c) SE/FIT/HUT 2002 18
Page 19
Ellipses: Algorithm (cont.) At the next midpoint, if a2(yp-0.5)<=b2(xp+1), we switch region 1=>2 In region 1, choices are E and SE Initial condition: d = b2+a2(-b+0.25) init For a move to E, d = d +Delta with Delta = b2(2x +3) new old E E p For a move to SE, d = d +Delta with new old SE Delta = b2(2x +3)+a2(-2y +2) SE p p In region 2, choices are S and SE Initial condition: d = b2(x +0.5)2+a2((y-1)2-b2) init p For a move to S, d = d +Delta with Delta = a2(-2y +3) new old s s p For a move to SE, d = d +Delta with new old SE Delta = b2(2x +2)+a2(-2y +3) SE p p Stop in region 2 when the y value is zero. (c) SE/FIT/HUT 2002 19
Page 20
Ký tự Bitmap Trên cơ sỏ định nghĩa mỗi ký tự với một font chư cho trước là một bitmap chữ nhật nhỏ Font/typeface: set of character shapes fontcache các ký tự theo chuỗi liên tiếp nhau trong bộ nhớ Dạng cơ bản ab (thường N, nghiêng I, đậm B, nghiêng đậm B+I) Thuộc tính Also colour, size, spacing and orientation (c) SE/FIT/HUT 2002 20
Showing the first 20 pages. Download the document to see it all.
Comments (0)
No comments yet. Be the first!