›

Giáo trình Đồ họa - Bài 3: Giải thuật sinh các thực thể cơ sở

pdf 32 trang huongle 2620
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Đồ họa - Bài 3: Giải thuật sinh các thực thể cơ sở", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_do_hoa_bai_3_giai_thuat_sinh_cac_thuc_the_co_so.pdf

Nội dung text: Giáo trình Đồ họa - Bài 3: Giải thuật sinh các thực thể cơ sở

  1. Bài 3 GIẢI THUẬT SINH CÁC THỰC THỂ CƠ SỞ © Copyright Showeet.com Trịnh Thành Trung trungtt@soict.hust.edu.vn 1
  2. NỘI DUNG 1. Biểu diễn đoạn thẳng a) Thuật toán DDA b) Giải thuật Bresenham c) Giải thuật trung điểm 2. Biểu diễn đường tròn 3. Biểu diễn đường ê-líp © Copyright Showeet.com 4. Giải thuật sinh ký tự - 2
  3. Rời rạc hóa điểm ảnh • 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 : – mượt - smooth – liên tục - continuous – đi qua các điểm xác định – độ sáng đồng nhất © Copyright Showeet.com – hiệu quả - efficient 3
  4. 1 © Copyright Showeet.com BIỂU DIỄN ĐOẠN THẲNG -
  5. •Biểu diễn tường minh (y-y1)/( x-x1) = ( y2-y1)/( x2-x1) y = kx + m – k = (y2-y1)/( x2-x1) P(x2 , y2) – m = y1- kx1 u – y = k x P(x1, y1) m © Copyright Showeet.com Biểu diễn đoạn thẳng 5
  6. •Biểu diễn không tường minh (y2-y1)x - (x2-x1)y + x2y1 - x1y2 = 0 hay rx + sy + t = 0 P(x , y ) – s = -(x2-x1 ) 2 2 – r = (y2-y1) và t = x2y1 - x1y2 u P(x1, y1) m © Copyright Showeet.com Biểu diễn đoạn thẳng 6
  7. •Biểu diễn tham biến P(u) = P1 + u(P2 - P1) u [0,1] X = x1 + u( x2 - x1 ) P(x2 , y2) Y = y1 + u( y2 - y1 ) u P(x1, y1) m © Copyright Showeet.com Biểu diễn đoạn thẳng 7
  8. Giải thuật thông thường Giải thuật DDA Với 0 < k < 1 xi+1 = xi + 1 yi+1 = yi + k với i=1,2,3 DrawLine(int x1,int y1, Thuậttoán ddaline (x1, y1, x2, y2) int x2,int y2, int color) x1, y1, x2, y2 : tọa độ 2 điểm đầu cuối { k : hệ số góc float y; x,y,m :biến int x; begin for (x=x1; x<=x2; x++) m =(x2-x1)/(y2-y1); { x = x1; y = y1 + (x- y = y1; k = 1/m; x1)*(y2-y1)/(x2-x1) putpixel(x,y); WritePixel(x, while x<x2 Round(y), color ); begin }} x = x+1; y = y+k; putpixel(x,round(y)); end; end; © Copyright Showeet.com Thuật toán DDA (Digital Differential Analyzer) 8
  9. 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 2 hạn d1 d2 • loại bỏ được các phép toán 1 chia và phép toán làm tròn như ta đã thấy trong gỉai 0 thuật DDA 0 1 2 • Xét đoạn thẳng với 0 < k < 1 © Copyright Showeet.com 9
  10. d2 = y - yi = k(xi +1) + b - yi d1 = yi+1 - y = yi + 1 - k(xi + 1) - b 2 d1 d2 if d1 d2 => yi+1 = yi + 1 1 else d1 > d2 => yi+1 = yi D = d1 - d2 0 = -2k(xi + 1) + 2yi - 2b + 1 Pi = xD = x (d1 - d2) 0 1 2 © Copyright Showeet.com Giải thuật Bresenham 10
  11. B¾t ®Çu x = x1 ; Pi = -2 yxi + 2 xyi + c y = y1; dx = x2 - x1; Pi+1 - Pi dy = y2 - y1; P = dx - 2dy; = -2 y(xi+1 - xi) + 2 x(yi+1 - yi) Putpixel (x ,y); •Nếu Pi 0 yi+1 = yi + 1 Pi = Pi - 2 y + 2 x +1 No P > 0 •Nếu Pi > 0 yi+1 = yi P = P - 2dy + 2dx x = x + 1 Pi+1 = Pi - 2 y yes P = P - 2dy y = y + 1 P1 = x(d1 - d2) P1 = -2 y + x yes x < x2 © Copyright Showeet.com no KÕt thóc 11
  12. •Jack Bresenham 1965 / Pitteway 1967 • VanAken áp dụng cho việc sinh các đường thẳng và đường tròn 1985 yi+1 •Các công thức đơn giản hơn, tạo A M M được các điểm tương tự như với B Bresenham ( xi , yi ) xi xi+1 •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. © Copyright Showeet.com Giải thuật trung điểm 12
  13. Giải thuật trung điểm • Sử dụng phương pháp biểu diễn không tường minh ax by c 0 • Tại mỗi trung điểm của đoạn thẳng giá trị được tính là: axi byi c 0 xi , yi on line axi byi c 0 xi , yi above line axi byi c 0 xi , yi below line • Chúng ta gọi di là biến quyết định của bước thứ i © Copyright Showeet.com 1 di a xi 1 b yi c 2 13
  14. Giải thuật trung điểm • If di > 0 then chọn điểm A trung điểm tiếp theo sẽ có dạng: 3 3 xi 2, yi di 1 a xi 2 b yi c 2 2 di a b © Copyright Showeet.com 14
  15. Giải thuật trung điểm 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 2 2 Ta có: di a a y yend ystart  b 0 a y 2 b x xend xstart where y x C x c C x  Ðiểm đầu © Copyright Showeet.com 1 1 xstart 1, ystart d start a xstart 1 b ystart c 2 2 b ax by c a start start 2 15
  16. Giải thuật trung điểm 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 © Copyright Showeet.com endif SetPixel(x,y) endwhile 16
  17. Giải thuật trung điểm • d = a(xi + 1) + b(yi + 1/2) + c B¾t ®Çu • Nếu điểm được chọn là B thi M sẽ tang theo x một đơn vị x = x1 ; y = y1; – dx = x2 - x1; di +1 = F(xi +2, yi + 1/2) dy = y2 - y1; – = a(xi +2) + b(yi + 1/2) + c d = dy - dx/2; – di = a(xi + 1) + b(yi + 1/2) + c Putpixel (x ,y); No • Nếu điểm A được chọn thì M tăng theo 2 hướng x và y với d <= 0 d = d + dy - dx x = x + 1 cùng một đơn vị. yes – di + 1 = F (xi + 2, yi + 3/2) d = d + dy y = y + 1 – = a(xi + 2) + b(yi +3/2) + c © Copyright Showeet.com – di + 1 = di + a + b. yes x < x2 • Với a + b = dy - dx. no K Õt thóc 17
  18. 2 BIỂU DIỄN ĐƯỜNG TRÒN © Copyright Showeet.com VÀ ĐƯỜNG Ê-LÍP -
  19. Giải thuật trung điểm cho đường tròn • Sử dụng phương pháp biểu diễn không tường minh trong giải thuật 2 2 2 x xc y yc r 0 • 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ó 0 if xi , yi is inside circle d 0 if x , y is on circle i i i © Copyright Showeet.com 0 if xi , yi is outside circle 19
  20. Giải thuật trung điểm cho đường tròn 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 © Copyright Showeet.com SetPixel(cx+x,cy+y) endwhile Translate to the circle center 20
  21. Giải thuật trung điểm cho đường ê-líp • Tương tự hình tròn • Áp dụng giải thuật cho ¼ đường ê-líp, sau đó lấy đối xứng cho các vị trí còn lại • Phương trình đường ê-líp F( x , y ) b2 x 2 a 2 y 2 a 2 b 2 0 – 2a: đường kính ngang © Copyright Showeet.com – 2b: đường kính dọc 21
  22. 3 © Copyright Showeet.com BIỂU DIỄN ĐA GIÁC -
  23. Giải thuật đường quét sinh đa giác • 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: • Một số giải thuật chỉ sử dụng được với các tam giác • Một số giải thuật đòi hỏi đa giác là lồi, không tự cắt chính nó và không có lỗ hổng bên trong © Copyright Showeet.com 23
  24. Giải thuật đường quét sinh đa giác • 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 © Copyright Showeet.com 24
  25. Giải thuật đường quét sinh đa giác • 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 điể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 © Copyright Showeet.com mình. 25
  26. Giải thuật đường quét sinh đa giác • 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 © Copyright Showeet.com 26
  27. Giải thuật đường quét sinh đa giác integer x value is on right = exterior © Copyright Showeet.com horizontal edge ymax not removed rounded down for A included rounded up for B 27
  28. 4 © Copyright Showeet.com BIỂU DIỄN KÝ TỰ -
  29. Giải thuật sinh ký tự • 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) © Copyright Showeet.com • Thuộc tính – Also colour, size, spacing ab and orientation 29
  30. Typedef struct { int leftx, int width; } Char location; //Vị trí Typedef struct { CacheId; Heiglit; // Độ rộng chữ CharSpace; // Khoảng cách // giữa các ký tự Charlocation Table [128]; } fontcache © Copyright Showeet.com Cấu trúc font chữ 30
  31. 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ượng cao © Copyright Showeet.com 31
  32. So sánh • Đơn giản trông việc sinh ký • Phức tạp (Tính toán tự (copypixel) phương trình) • Lưu trữ lớn • Lưu trữ gọn nhẹ • Các phép biến đổi (I,B, scale) • Các phép biến đổi dựa vào đòi hỏi lưu trữ thêm các công thức biến đổi • Kích thước không đổi • Kích thước phụ thuôc vào môi trường ( không có kích thước cố định) © Copyright Showeet.com 32