intTypePromotion=1

Giáo trình đồ họa - Lesson 2

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:0

0
62
lượt xem
8
download

Giáo trình đồ họa - Lesson 2

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các giải thuật sinh các thực thể cơ sở 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

Chủ đề:
Lưu

Nội dung Text: Giáo trình đồ họa - Lesson 2

  1. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 Giải thuật xây dựng các Bài 2: thực thể cơ sở Các giải thuật sinh 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ự Le Tan Hung hunglt@it-hut.edu.vn 0913030731 (c) SE/FIT/HUT 2002 2 (c) SE/FIT/HUT 2002 Rời rạc hoá điểm ảnh Biểu diễn đoạn thẳng (Scan Conversion rasterization) Là tiến trình sinh các đối tượng hình học cơ sở bằng phương Biểu diễn tường minh pháp xấp xỉ dựa trên lưới phân giải của màn hình P(x2 , y2) (y-y1)/( x-x1) = ( y2-y1)/( x2-x1)1 y = kx + m Tính chất các đối tượng cần đảm bảo : k = (y2-y1)/( x2-x1) m = y1- kx1 u smooth Δ y = k Δx continuous Biểu diễn không tường minh pass through specified points P(x1, y1) (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 uniform brightness hay rx + sy + t = 0 s = -(x2-x1 ) efficient r = (y2-y1) và t = x2y1 - x1y2 Biểu diễn tham biến m P(u) = P1 + u(P2 - P1) u [0,1] X = x1 + u( x2 - x1 ) Y = y1 + u( y2 - y1 ) 3 4 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Thuật toán DDA Giải thuật Bresenham (Digital Differential Analizer) Giải thuật thông thường 1960 Bresenham thuộc IBM Thuậttoán ddaline (x1, y1, x2, y2) DrawLine(int x1,int y1, int x2,int y2, điểm gần với đường thẳng dựa x1, y1, x2, y2 : tọa độ 2 điểm đầu cuối int color) 2 k : hệ số góc trên độ phân giai hưu hạn d2 { x,y,m :biến loại bỏ được các phép toán float y; d1 chia và phép toán làm tròn 1 begin int x; như ta đã thấy trong gỉai thuật m =(x2-x1)/(y2-y1); for (x=x1; x
  2. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 Giải thuật Bresenham Giải thuật Bresenham Pi = -2Δyxi + 2Δxyi + c d2 = y - yi = k(xi +1) + b - yi Pi+1 - Pi d1 = yi+1 - y = yi + 1 - k(xi + 1) - b = -2Δy(xi+1 - xi) + 2Δx(yi+1 - yi) yi+1 Nếu Pi ≤ 0 ⇒ yi+1 = yi + 1 d1 If d1 ≤ d2 => yi+1 = yi + 1 Pi+1 = Pi - 2Δy + 2Δx d2 else d1 > d2 => yi+1 = yi yi Nếu Pi > 0 ⇒ yi+1 = yi D = d1 - d2 Pi+1 = Pi - 2Δy = -2k(xi + 1) + 2yi - 2b + 1 P1 = Δx(d1 - d2) Pi = ΔxD = Δx (d1 - d2) P1 = -2Δy + Δx xi xi+1 7 8 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Bresenham’s Algorithm: Giải thuật trung điểm-Midpoint Midpoint Algorithm Jack Bresenham 1965 / Pitteway 1967 Sử dụng phương pháp biểu diễn không tường minh VanAken áp dụng cho việc sinh các đường thẳng và đường tròn 1985 ax + by + c = 0 Các công thức đơn giản hơn, tạo được các điểm axi + byi + c = 0 ⇒ ( xi , yi ) A tương tự như với Bresenham on line yi+1 M d = F (xi + 1, yi + 1/2) là trung điểm của đoạn axi + byi + c < 0 ⇒ ( xi , yi ) B above line AB M axi + byi + c > 0 ⇒ ( xi , yi ) below line Việc so sánh, hay kiểm tra M sẽ được thay bằng việc xét giá trị d. ( xi , yi ) Tại mỗi trung điểm của đoạn thẳng giá trị được tính là: 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 + xi xi+1 ⎛ 1⎞ 1 di = a( xi +1) + b⎜ yi + ⎟ + c Trong trường hợp d = 0 chúng ta có thể ⎝ 2⎠ chọn điểm bất kỳ hoặc A, hoặc B. Chúng ta gọi di là biến quyết định của bước thứ i 9 10 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Bresenham’s Algorithm: Bresenham’s Algorithm: Midpoint Algorithm Midpoint Algorithm If di > 0 then chọn điểm A ⇒ trung điểm tiếp theo sẽ có dạng: if di < 0 then chọn điểm B và trung điểm mới là ⎛ 1⎞ ⎛ 1⎞ ⎜ xi + 2, yi + ⎟ ⇒ di+1 = a(xi + 2) + b⎜ yi + ⎟ + c ⎛ 3⎞ ⎛ 3⎞ ⎜ xi + 2, yi + ⎟ ⇒ di+1 = a( xi + 2) + b⎜ yi + ⎟ + c 2⎠ 2⎠ ⎝ ⎝ = di + a Ta có: ⎝ 2⎠ ⎝ 2⎠ a = Δy = yend − ystart ⎫ = di + a + b Δy ⎪ b = −Δx = xend − xstart ⎬ where y = x + C Δx ⎪ c = CΔx ⎭ Ðiểm đầu ⎛ 1⎞ ⎛ 1⎞ ⎜ x start + 1, y start + ⎟ ⇒ d start = a ( x start + 1) + b⎜ y start + ⎟ + c ⎝ 2⎠ ⎝ 2⎠ b = [ax start + by start + c] + a + b = 0+a+ 2 2 11 12 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 2
  3. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 Giải thuật B¾t ®Çu Midpoint Line Algorithm Bresenham's Midpoint x = x1 ; y = y1; dx = x2 - x1; dy = y2 - y1; d = a(xi + 1) + b(yi + 1/2) + c d = dy - dx/2; dx = x_end-x_start Nếu điểm được chọn là B thi M sẽ tang dy = y_end-y_start initialisation theo x một đơn vị d = 2*dy-dx Putpixel (x ,y); di +1 = F(xi +2, yi + 1/2) x = x_start = a(xi +2) + b(yi + 1/2) + c y = y_start No d 0 then it is outside the circle. f(x,y) < 0 then it is inside the circle. 15 16 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Midpoint Circle Algorithm Midpoint Circle Algorithm As with the line, we determine the value of the decision variable by Again, as with the line algorithm, the choice of A or B can be used to substituting the mid-point of the next pixel into the implicit form of the determine the new value of di+1 circle: 2 ⎛ 1⎞ di = ( xi +1) + ⎜ yi − ⎟ − r 2 If A chosen then next midpoint has the following decision variable: 2 ⎝ 2⎠ 2 ⎛ 1⎞ ⎛ 1⎞ ⎜ xi + 2, yi − ⎟ ⇒ di +1 = ( xi + 2) + ⎜ yi − ⎟ − r 2 2 If di < 0 we choose pixel A otherwise we choose pixel B 2⎠ 2⎠ ⎝ ⎝ Note: we currently assume the circle is centered at the origin = di + 2xi + 3 Otherwise if B is chosen then the next decision variable is given by: 2 ⎛ 3⎞ ⎛ 3⎞ ⎜ xi + 2, yi − ⎟ ⇒ di+1 = ( xi + 2) + ⎜ yi − ⎟ − r 2 2 2⎠ 2⎠ ⎝ ⎝ = di + 2xi − 2 yi + 5 17 18 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 3
  4. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 Midpoint Circle Algorithm Midpoint Circle Algorithm If we assume that the radius is an integral value, then the first pixel d = 1-r initialisation x=0 drawn is (0, r) and the initial value for the decision variable is given stop at diagonal ⇒ end of octant y=r by: ⎛ 1⎞ ⎛2 1⎞ 2 while y < x ⎜1, r − ⎟ ⇒ d0 = 1 + ⎜ r − r + ⎟ − r if d < 0 then ⎝ 2⎠ ⎝ 4⎠ d = d+2*x+3 choose A 5 x = x+1 = −r else 4 d = d+2*(x-y)+5 Although the initial value is fractional, we note that all other values are choose B x = x+1 integers. y = y-1 d0 = 1 − r endif we can round down: ⇒ SetPixel(cx+x,cy+y) endwhile Translate to the circle center 19 20 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Scan Converting Ellipses: Algorithm Scan Converting Ellipses A M tiep tuyen = -1 F ( x, y ) = b 2 x 2 + a 2 y 2 − a 2 b 2 = 0 B gradient B C M i 2a is the length of the major axis along the x axis. Firstly we divide the quadrant into two regions 2b is the length of the minor axis along the y axis. Boundary between the two regions is the point at which the curve has a slope of -1 The midpoint can also be applied to ellipses. the point at which the gradient vector has the i and j components of equal For simplicity, we draw only the arc of the ellipse that lies magnitude in the first quadrant, the other three quadrants can be drawn grad F(x, y) = ∂F / ∂x i +∂F / ∂y j = 2b2 x i + 2a2 y j by symmetry 21 22 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Ellipses: Algorithm (cont.) Ký tự Bitmap At the next midpoint, if a2(yp-0.5)2 Trên cơ sỏ định nghĩa mỗi ký tự với một font chư cho trước là một In region 1, choices are E and SE bitmap chữ nhật nhỏ Initial condition: dinit = b2+a2(-b+0.25) Font/typeface: set of character For a move to E, dnew = dold+DeltaE with DeltaE = b2(2xp+3) shapes For a move to SE, dnew = dold+DeltaSE with fontcache DeltaSE = b2(2xp+3)+a2(-2yp+2) các ký tự theo chuỗi liên tiếp nhau trong In region 2, choices are S and SE bộ nhớ Initial condition: dinit = b2(xp+0.5)2+a2((y-1)2-b2) Dạng cơ bản ab For a move to S, dnew = dold+Deltas with Deltas = a2(-2yp+3) (thường N, nghiêng I, đậm B, nghiêng For a move to SE, dnew = dold+DeltaSE with đậm B+I) DeltaSE = b2(2xp+2)+a2(-2yp+3) Thuộc tính Stop in region 2 when the y value is zero. Also colour, size, spacing and orientation 23 24 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 4
  5. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 Cấu trúc font chữ Ký tự vector Typedef struct Xây dựng theo phương pháp { định nghĩa các ký tự bởi int leftx, đường cong mềm bao ngoài int width; } Char location; //Vị trí của text của chúng. Tốn kém nhất về mặt tính Typedef struct toán { CacheId; Chất lượngcao Heiglit; // Độ rộng chữ CharSpace; // Khoảng cách giữa các ký tự Charlocation Table [128]; } fontcache 25 26 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Giải thuật đường quét sinh đa giác So sánh Polygon Scan Conversion Tồn tại rất nhiều giải thuật sinh đa giác. Phức tạp (Tính toán phương Đơn giản trông việc sinh ký tự trình) Mỗi giải thuật phục vụ cho 1 loại đa giác nhất ( copypixel) Lưu trữ gọn nhẹ định: Lưu trữ lớn Các phép biến đổi dựa vào các some algorithms allow triangular polygons only Các phép biến đổi (I,B, scale) công thức biến đổi others require that the polygons are convex and non self- đòi hỏi lưu trữ thêm Kích thước phụ thuôc vào môi intersecting and have no holes trường ( ko có kích thước cố Kích thước không dổi định) triangular convex non-convex self-intersecting religious 27 28 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Polygon Scan Conversion Polygon Scan Conversion Polygon scan conversion là giải thuật chung kinh điển cho các loại Dùng giải thuật (trung điểm) để xác khác nhau định các điểm biên cho mỗi đa giác 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 theo thứ tự tăng của x. đoạn thẳng compute spans representing the interior portions of the Các diểm phải: polygons along this scan-line and fill the associated pixels. Không bị chia sẻ bởi các đa giác lân This represents the heart of a scan-line rendering algorithm used in cận many commercial products including Renderman and 3D Studio Các đa giác chỉ toàn các điểm cạnh( MAX. đ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. 29 30 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 5
  6. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 Polygon Scan Conversion Polygon Scan Conversion is on integer x value right = exterior 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) ymax not horizontal edge rounded down for A included removed rounded up for B 31 32 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Giải thuật đường quét Polygon Scan Conversion Scan-Line Algorithm Determining intersections with polygon edges is expensive The scan-line algorithm uses edge-coherence and incremental rather than re-computing all intersections at each iteration, use integer calculations for maximum efficiency: incremental calculations Tạo bảng edge table (ET) tập của các cạnh đa giác theo thứ tự giá trị 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) ymin của chúng Assume slope of the edge > 1 (other edges obtained via symmetries) Tạo bảng active edge table (AET) tập các cạnh giao vớI đoạn thẳng 1 quét scan-line incremental DDA calculation was: yi +1 = yi + 1, xi +1 = xi + m Trong tiến trình quét các cạnh sẽ chuyển từ ET ra AET. ( yend − ystart ) slope m is given by m= Các cạnh sẽ ở trong AET cho đến khi giá trị ymax của cạnh đạt (xend − xstart ) tới = scanline note that numerator and denominator are integral ⇒ we can use integer DDA. Lúc nay cạnh sẽ bị loại ra khỏi AET. 33 34 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 Active Edge Table (AET) Edge Table (ET) (0,0) round down round up numerator 1 −3 ⇒= denominator m 5 ymax xmin (15,15) AET = scan-line current numerator Note: line (8,6) → (13,6) has been deleted according to the scan rules ymax current x denominator 35 36 (c) SE/FIT/HUT 2002 (c) SE/FIT/HUT 2002 6
  7. KHoa CNTT-DDHBK Hà nội hunglt@it-hut.edu.vn 0913030731 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 xmin fill spans using pairs of AET entries for all AET members if ymax = y then remove from AET y = y+1 for all AET members update numerator if numerator>denominator numerator=numerator-denominator x = x+1 until AET and ET empty 37 (c) SE/FIT/HUT 2002 7
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2