Bài giảng Đồ họa hiện thực ảo - Bài 2: Các giải thuật sinh các thực thể cơ sở - Lê Tấn Hưng

(c) SE/FIT/HUT 2002 Bài 2: Các giải thuật sinh các thực thể cơ sở Le Tan Hung hunglt@it-hut.edu.vn (c) SE/FIT/HUT 2002 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 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 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 y = kx + m „ Biểu diễn không tường minh (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 hay rx + sy + t = 0 „ Biểu diễn tham biến P(u) = P1 + u(P2 - P1) u [0,1] m P(x1, y1) P(x2 , y2) u (c) SE/FIT/HUT 2002 5 Thuật toán DDA (Digital Differential Analizer) Giải thuật DDA „ Với 0 < k < 1 xi+1 = xi + 1 yi+1 = yi + k với i=1,2,3.... Giải thuật thông thường DrawLine(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) WritePixel(x, Round(y), color ); }} (c) SE/FIT/HUT 2002 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 „ 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 0 1 2 0 1 2 d1 d2 (c) SE/FIT/HUT 2002 7 Giải thuật Bresenham d2 = y - yi = k(xi +1) + b - yi d1 = yi+1 - y = yi + 1 - k(xi + 1) - b d1 d2 xi xi+1 yi yi+1 A B (c) SE/FIT/HUT 2002 8 Giải thuật Bresenham (c) SE/FIT/HUT 2002 9 yi+1 ( xi , yi ) xi xi+1 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 „ d = F (xi + 1, yi + 1/2) là trung điểm của đoạn AB „ Việc so sánh, hay kiểm tra M sẽ được thay bằng việc xét giá trị d. „ Nếu d > 0 điểm B được chọn, yi+1 = yi „ 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. A M B (c) SE/FIT/HUT 2002 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: ( ) bad cybxadyx i iiiii ++= +   +++=⇒   ++ + 2 32 2 3,2 1 (c) SE/FIT/HUT 2002 11 Midpoint Line Algorithm dx = x_end-x_start dy = y_end-y_start d = 2*dy-dx x = x_start y = y_start while x < x_end if d <= 0 then d = d+(2*dy) x = x+1 else d = d+2*(dy-dx) x = x+1 y = y+1 endif SetPixel(x,y) endwhile initialisation choose B choose A (c) SE/FIT/HUT 2002 12 Giải thuật Bresenham's Midpoint d <= 0 B¾t ®Çu x = x1 ; y = y1; dx = x2 - x1; dy = y2 - y1; d = dy - dx/2; Putpixel (x ,y); x < x2 KÕt thóc d = d + dy d = d + dy - dx y = y + 1 yes no No yes x = x + 1 (c) SE/FIT/HUT 2002 13 Sinh đường tròn Scan Converting Circles „ Implicit: f(x) = x2+y2-R2 „ Explicit: y = f(x) „ Parametric: 2 2y R x= ± − cos sin x R y R θ θ = = 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. Usually, we draw a quarter circle by incrementing x from 0 to R in unit steps and solving for +y for each step. - by stepping the angle from 0 to 90 - avoids large gaps but still insufficient. (c) SE/FIT/HUT 2002 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 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: „ If di < 0 we choose pixel A otherwise we choose pixel B „ Note: we currently assume the circle is centered at the origin ( ) 222 2 11 ryxd iii −   −++= (c) SE/FIT/HUT 2002 16 Midpoint Circle Algorithm d = 1-r x = 0 y = r while y < x if d < 0 then d = d+2*x+3 x = x+1 else d = d+2*(x-y)+5 x = x+1 y = y-1 endif SetPixel(cx+x,cy+y)endwhile initialisation choose B choose A Translate to the circle center stop at diagonal ⇒ end of octant (c) SE/FIT/HUT 2002 17 Scan Converting Ellipses „ 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 2 2 2 2 2 2( , ) 0F x y b x a y a b= + − = (c) SE/FIT/HUT 2002 18 Scan Converting Ellipses: Algorithm „ Firstly we divide the quadrant into two regions „ 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 2 2( , ) / / 2 2grad F x y F x F y b x a y=∂ ∂ +∂ ∂ = +i j i j A M tiep tuyen = -1 B gradient B C M i (c) SE/FIT/HUT 2002 19 Ellipses: Algorithm (cont.) „ At the next midpoint, if a2(yp-0.5)2 „ In region 1, choices are E and SE „ Initial condition: dinit = b2+a2(-b+0.25) „ For a move to E, dnew = dold+DeltaE with DeltaE = b2(2xp+3) „ For a move to SE, dnew = dold+DeltaSE with DeltaSE = b2(2xp+3)+a2(-2yp+2) „ In region 2, choices are S and SE „ Initial condition: dinit = b2(xp+0.5)2+a2((y-1)2-b2) „ For a move to S, dnew = dold+Deltas with Deltas = a2(-2yp+3) „ For a move to SE, dnew = dold+DeltaSE with DeltaSE = b2(2xp+2)+a2(-2yp+3) „ Stop in region 2 when the y value is zero. (c) SE/FIT/HUT 2002 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 „ (thường N, nghiêng I, đậm B, nghiêng đậm B+I) „ Thuộc tính „ Also colour, size, spacing and orientation ab (c) SE/FIT/HUT 2002 21 Cấu trúc font chữ (c) SE/FIT/HUT 2002 22 Ký tự vector „ Xây dựng theo phương pháp định nghĩa các ký tự bởi đường cong mềm bao ngoài của chúng. „ Tốn kém nhất về mặt tính toán „ Chất lượngcao (c) SE/FIT/HUT 2002 23 So sánh „ Đơn giản trông việc sinh ký tự ( copypixel) „ Lưu trữ lớn „ Các phép biến đổi (I,B, scale) đòi hỏi lưu trữ thêm „ Kích thước không dổi „ Phức tạp (Tính toán phương trình) „ Lưu trữ gọn nhẹ „ Các phép biến đổi dựa vào các công thức biến đổi „ Kích thước phụ thuôc vào môi trường ( ko có kích thước cố định) (c) SE/FIT/HUT 2002 24 Giải thuật đường quét sinh đa giác Polygon Scan Conversion „ Tồn tại rất nhiều giải thuật sinh đa giác. „ Mỗi giải thuật phục vụ cho 1 loại đa giác nhất định: „ some algorithms allow triangular polygons only „ others require that the polygons are convex and non self- intersecting and have no holes triangular convex non-convex self-intersecting religious (c) SE/FIT/HUT 2002 25 Polygon Scan Conversion „ Polygon scan conversion là giải thuật chung kinh điển cho các loại khác nhau „ Cho mỗi đoạn thẳng quét, chúng ta xác định các cạnh của đa giác cắt đoạn thẳng compute spans representing the interior portions of the polygons along this scan-line and fill the associated pixels. „ This represents the heart of a scan-line rendering algorithm used in many commercial products including Renderman and 3D Studio MAX. (c) SE/FIT/HUT 2002 26 Polygon Scan Conversion „ Dùng giải thuật (trung điểm) để xác định các điểm biên cho mỗi đa giác theo thứ tự tăng của x. „ Các diểm phải: „ Không bị chia sẻ bởi các đa giác lân cận „ Các đa giác chỉ toàn các điểm cạnh( điểm biên) „ Đảm bảo các đa giác chia sẻ điểm biên mà không chia sẻ các điểm ảnh bên trong của mình. (c) SE/FIT/HUT 2002 27 Polygon Scan Conversion „ Thủ tục chung: „ Xác định giao của đường thẳng quét với cạnh đa giác „ Sắp xếp các giao điểm theo mức độ tăng dần của x value „ Điền các điểm ảnh vào giữa cặp các điểm x „ Need to handle 4 cases to prevent pixel sharing: „ if intersection has fractional x value, do we round up or down? • if inside (on left of span) round up, if outside (on right) round down „ what happens if intersection is at an integer x value? • if on left of span assume its interior otherwise exterior „ how do we handle shared vertices? • ignore pixel associated with ymax of an edge „ how do we handle horizontal edges? • handled as a result of previous rule (lower edges not drawn) (c) SE/FIT/HUT 2002 28 Polygon Scan Conversion rounded down for A rounded up for B integer x value is on right = exterior ymax not included horizontal edge removed