Các giải thuật sinh các thực thể cơ sở

KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 1 (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 0913030731 (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) „ Là tiến trình sinh các đối tượng hình học cơ sở bằng phương pháp xấp xỉ dựa trên lưới phân giải của màn hình „ 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 „ k = (y2-y1)/( x2-x1) „ m = y1- kx1 „ Δy = k Δx „ Biểu diễn không tường minh (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 tham biến P(u) = P1 + u(P2 - P1) u [0,1] X = x1 + u( x2 - x1 ) Y = y1 + u( y2 - y1 ) 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.... Thuậttoán ddaline (x1, y1, x2, y2) x1, y1, x2, y2 : tọa độ 2 điểm đầu cuối k : hệ số góc x,y,m :biến begin m =(x2-x1)/(y2-y1); x = x1; y = y1; k = 1/m; putpixel(x,y); while x<x2 begin x = x+1; y = y+k; putpixel(round(x),round(y)); end; end; 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 gỉai thuật DDA „ Xét đoạn thẳng với 0 < k < 1 0 1 2 0 1 2 d2 d1 KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 2 (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 „ If d1 ≤ d2 => yi+1 = yi + 1 else d1 > d2 => yi+1 = yi „ D = d1 - d2 = -2k(xi + 1) + 2yi - 2b + 1 „ Pi = ΔxD = Δx (d1 - d2) d1 d2 xi xi+1 yi yi+1 (c) SE/FIT/HUT 2002 8 Pi = -2Δyxi + 2Δxyi + c Pi+1 - Pi = -2Δy(xi+1 - xi) + 2Δx(yi+1 - yi) „ Nếu Pi ≤ 0 ⇒ yi+1 = yi + 1 Pi+1 = Pi - 2Δy + 2Δx „ Nếu Pi > 0 ⇒ yi+1 = yi Pi+1 = Pi - 2Δy P1 = Δx(d1 - d2) P1 = -2Δy + Δx Giải thuật Bresenham (c) SE/FIT/HUT 2002 9 yi+1 M ( 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 „ Sử dụng phương pháp biểu diễn không tường minh „ Tại mỗi trung điểm của đoạn thẳng giá trị được tính là: „ Chúng ta gọi di là biến quyết định của bước thứ i 0=++ cbyax ( ) ( ) ( )iiii iiii iiii yxcbyax yxcbyax yxcbyax ,0 ,0 ,0 ⇒>++ ⇒<++ ⇒=++ on line above line below line ( ) cybxad iii +⎟⎠ ⎞⎜⎝ ⎛ +++= 2 11 (c) SE/FIT/HUT 2002 11 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 12 Bresenham’s Algorithm: Midpoint Algorithm „ if di < 0 then chọn điểm B và trung điểm mới là „ Ta có: „ Ðiểm đầu ( ) [ ] 2 2 11 2 1,1 bacbyax cybxadyx startstart startstartstartstartstart ++++= +⎟⎠ ⎞⎜⎝ ⎛ +++=⇒⎟⎠ ⎞⎜⎝ ⎛ ++ ( ) ad cybxadyx i iiiii += +⎟⎠ ⎞⎜⎝ ⎛ +++=⇒⎟⎠ ⎞⎜⎝ ⎛ ++ + 2 12 2 1,2 1 Cx x yy xCc xxxb yyya startend startend +Δ Δ= ⎪⎭ ⎪⎬ ⎫ Δ= −=Δ−= −=Δ= where 2 0 ba ++= KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 3 (c) SE/FIT/HUT 2002 13 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 14 Giải thuật Bresenham's Midpoint „ d = a(xi + 1) + b(yi + 1/2) + c „ Nếu điểm được chọn là B thi M sẽ tang theo x một đơn vị „ di +1 = F(xi +2, yi + 1/2) = a(xi +2) + b(yi + 1/2) + c „ di = a(xi + 1) + b(yi + 1/2) + c „ Nếu điểm A được chọn thi` M tăng theo 2 hướng x và y với cùng một đơn vị. di + 1 = F (xi + 2, yi + 3/2) „ = a(xi + 2) + b(yi +3/2) + c „ di + 1 = di + a + b. ¾ Với a + b = dy - dx. 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 15 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 16 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ó ( ) ( ) 0222 =−−+− ryyxx cc ( ) ( ) ( ) circle outside is , if 0 circleon is , if 0 circle inside is , if 0 ⎪⎩ ⎪⎨ ⎧ > = < = ii ii ii i yx yx yx d (c) SE/FIT/HUT 2002 17 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 18 Midpoint Circle Algorithm „ Again, as with the line algorithm, the choice of A or B can be used to determine the new value of di+1 „ If A chosen then next midpoint has the following decision variable: „ Otherwise if B is chosen then the next decision variable is given by: ( ) 32 2 12 2 1,2 2 2 2 1 ++= −⎟⎠ ⎞⎜⎝ ⎛ −++=⇒⎟⎠ ⎞⎜⎝ ⎛ −+ + ii iiiii xd ryxdyx ( ) 522 2 32 2 3,2 2 2 2 1 +−+= −⎟⎠ ⎞⎜⎝ ⎛ −++=⇒⎟⎠ ⎞⎜⎝ ⎛ −+ + iii iiiii yxd ryxdyx KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 4 (c) SE/FIT/HUT 2002 19 Midpoint Circle Algorithm „ If we assume that the radius is an integral value, then the first pixel drawn is (0, r) and the initial value for the decision variable is given by: „ Although the initial value is fractional, we note that all other values are integers. ⇒ we can round down: r rrrdr −= −⎟⎠ ⎞⎜⎝ ⎛ +−+=⇒⎟⎠ ⎞⎜⎝ ⎛ − 4 5 4 11 2 1,1 220 rd −=10 (c) SE/FIT/HUT 2002 20 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 21 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 22 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 23 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 24 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 KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 5 (c) SE/FIT/HUT 2002 25 Cấu trúc font chữ Typedef struct { int leftx, int width; } Char location; //Vị trí của text Typedef struct { CacheId; Heiglit; // Độ rộng chữ CharSpace; // Khoảng cách giữa các ký tự Charlocation Table [128]; } fontcache (c) SE/FIT/HUT 2002 26 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 27 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 28 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 29 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 30 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. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 6 (c) SE/FIT/HUT 2002 31 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 32 Polygon Scan Conversion rounded down for A rounded up for B integer x value is on right = exterior ymax not included horizontal edge removed (c) SE/FIT/HUT 2002 33 Polygon Scan Conversion „ Determining intersections with polygon edges is expensive „ rather than re-computing all intersections at each iteration, use incremental calculations „ i.e. if we intersect edge e on scan-line i then it is likely we will intersect the edge on scan-line i+1 (this is known as edge-coherence) „ Assume slope of the edge > 1 (other edges obtained via symmetries) „ incremental DDA calculation was: „ slope m is given by „ note that numerator and denominator are integral ⇒ we can use integer DDA. m xxyy iiii 1,1 11 +=+= ++ ( ) ( )startend startend xx yym − −= (c) SE/FIT/HUT 2002 34 Giải thuật đường quét Scan-Line Algorithm „ The scan-line algorithm uses edge-coherence and incremental integer calculations for maximum efficiency: „ Tạo bảng edge table (ET) tập của các cạnh đa giác theo thứ tự giá trị ymin của chúng „ Tạo bảng active edge table (AET) tập các cạnh giao vớI đoạn thẳng quét scan-line „ Trong tiến trình quét các cạnh sẽ chuyển từ ET ra AET. „ Các cạnh sẽ ở trong AET cho đến khi giá trị ymax của cạnh đạt tới = scanline „ Lúc nay cạnh sẽ bị loại ra khỏi AET. (c) SE/FIT/HUT 2002 35 Edge Table (ET) Note: line (8,6) → (13,6) has been deleted according to the scan rules ymax xmin numerator denominator scan-line (0,0) (15,15) 5 31 −=⇒ m (c) SE/FIT/HUT 2002 36 Active Edge Table (AET) ymax current x denominator AET = current numerator round up round down KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 7 (c) SE/FIT/HUT 2002 37 Scan-Line Algorithm y = y of first non empty entry in ET AET = null repeat move all ET entries in slot y to AET sort AET entries according to xminfill spans using pairs of AET entries for all AET members if ymax = y then remove from AETy = y+1 for all AET members update numerator if numerator>denominator numerator=numerator-denominator x = x+1 until AET and ET empty