›
›

Bài giảng Đồ họa Raster - Chương 3, Phần 3: Đường cong - Bùi Tiến Liên

ppt 76 trang cucquyet12 2600
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa Raster - Chương 3, Phần 3: Đường cong - Bùi Tiến Liên", để 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:

  • pptbai_giang_do_hoa_raster_chuong_3_phan_3_duong_cong_bui_tien.ppt

Nội dung text: Bài giảng Đồ họa Raster - Chương 3, Phần 3: Đường cong - Bùi Tiến Liên

  1. ĐỒ HỌA 2D ĐƯỜNG CONG Giảng viên : Bùi Tiến Lên
  2. Phân loại Quan điểm tốn học - Đường cong được biểu diễn bằng hàm số - Đường cong được biểu diễn bằng phương trình tham số Quan điểm thiết kế - Đường cong CAD (Computer Aided Design) Trang 2
  3. Đường cong được biểu diễn bằng hàm số
  4. Bài tốn Input Hàm số y = f(x) Miền đối số [xmin, xmax] Output Đồ thị hàm số y=f(x) xmin xmax Trang 4
  5. Thuật tốn Bước 1 : Chia miền đối số ra N đoạn bằng nhau x0 x1 x2 xN-1 xN xmin xmax Trang 5
  6. Thuật tốn Bước 2 : Tính y yN y 1 y2 yN-1 y0 x0 x1 x2 xN-1 xN xmin xmax Trang 6
  7. Thuật tốn Bước 3 : Kẻ đường gấp khúc đi qua N + 1 điểm. yN y 1 y2 yN-1 y0 x0 x1 x2 xN-1 xN xmin xmax Trang 7
  8. Cài đặt // Hàm vẽ đường cong hàm số void DrawCurve2D(CDC *pDC, TFunc2D f, double xmin, double xmax) { double x, x, y; x = (xmax – xmin)/N; x = xmin; y = f(x); pDC->MoveTo(ConvertWorldToScreen2D(x, y)); for(int i=1; i LineTo(ConvertWorldToScreen2D(x, y)); } } Trang 8
  9. Cài đặt // Lớp phương trình hàm class TFunc2D { virtual double operator () (double x) = 0; }; Trang 9
  10. Vấn đề phân đoạn Số phân đoạn N là bao nhiêu ? độ phân giải cột Trang 10
  11. Đồ thị đa thức bậc ba Cho y = ax3 + bx2 + cx + d x [xmin, xmax] y = 0.1x3 − 0.2x2 − 0.2x + 3 x − 4,4 Trang 11
  12. Vấn đề tính giá trị đa thức Cách tính thơng thường a*x*x*x + b*x*x + c*x + d; Cần 6 phép nhân và 3 phép cộng Cách tính Horner ((a*x + b)*x + c)*x + d Cần 3 phép nhân và 3 phép cộng Cách tính cải tiến ? Trang 12
  13. Vấn đề tính giá trị đa thức Đa thức bậc nhất y = ax + b Cách tính thông thường Cách tính cải tiến yi = axi + b y0 = ax0 + b yi+1 = yi + a x Tính Tính y0 = ax0 + b y0 = ax0 + b y1 = ax1 + b y1 = y0 + a x y2 = ax2 + b y2 = y1 + a x yi = axi + b yi = yi-1 + a x yi+1 = axi+1 + b yi+1 = yi + a x yN = axN+1 + b y0 = yi + a x Trang 13
  14. Vấn đề tính giá trị đa thức Đa thức bậc hai y = ax2 + bx + c Cách tính thông thường Cách tính cải tiến 2 2 yi = axi + bxi + c y0 = ax0 + bx0 + c 2 y0 = 2a xx0 + a x + b x yi+1 = yi + yi 2 yi+1 = yi + 2a x Trang 14
  15. Vấn đề tính giá trị đa thức Đa thức bậc ba y = ax3 + bx2 + cx + d Cách tính cải tiến 3 2 y0 = ax0 + bx0 + cx0 + d 2 2 3 2 y0 = 3a xx0 + (3a x + 2b x)x0 + a x + b x + c x 2 3 2 y0 = 6a x x0 + 6a x + 2b x yi+1 = yi + yi yi+1 = yi + yi 3 yi+1 = yi + 6a x Trang 15
  16. Đường cong được biểu diễn bằng Phương trình tham số
  17. Bài tốn Input: Phương trình tham số x(t) y(t) Miền tham số t [tmin, tmax] Output: x(t) = cos(5t)cos(t) y(t) = cos(5t)sin(t) t 0,2  Trang 17
  18. Thuật tốn Bước 1 : Chia miền tham số ra N đoạn bằng nhau Miền tham số to t1 t2 tN tmin tmax Trang 18
  19. Thuật tốn Bước 2 : Tính (x, y) ti tN t2 t1 to Trang 19
  20. Thuật tốn Bước 3 : Vẽ đường gấp khúc đi qua N + 1 điểm (xN, yN) (x2, y2) (x1, y1) (x0, y0) Trang 20
  21. Cài đặt // Hàm vẽ đường cong tham số void DrawCurve2D(CDC *pDC, TPara2D f, double tmin, double tmax) { double t, t; TPoint2D p; t = (tmax – tmin)/N; t = tmin; p = f(t); pDC->MoveTo(ConvertWorldToScreen2D(p)); for(int i=1; i LineTo(ConvertWorldToScreen2D(p)); } } Trang 21
  22. Cài đặt // Lớp phương trình tham số class TPara2D { virtual TPoint2D operator () (double t) = 0; } Trang 22
  23. Vấn đề phân đoạn x(t) = cos t y(t) = sint t 0,2  x(t) = t cos t y(t) = t sint t 0,8  Trang 23
  24. ĐƯỜNG CONG CAD
  25. ĐƯỜNG CONG BEZIER
  26. Định nghĩa đường cong Input n +1 điểm điều khiển {p0, p1, , pn} Output p1 p0 pn Trang 26
  27. Cơng thức xác định đường cong Ptts đường cong Bezier bậc n được tạo bởi n + 1 điểm điều khiển k=n n p(t) = B (t).p n n! n−k k  k k với B (t) = (1− t) t k=0 k k!(n − k)! t 0,1 hoặc k=n n x(t) = Bk (t).pkx k=0 k=n n y(t) = Bk (t).pky k=0 t 0,1 Trang 27
  28. Tính chất 1 Bảo tồn qua phép biến đổi affine. Trang 28
  29. Tính chất 2 Các điểm điểu khiển tạo thành bao lồi của đường cong Trang 29
  30. Đường cong Bezier bậc một p1 p(t) = (1 – t)p0 + tp1 t [0, 1] hoặc x(t) = (1 – t)p0x + tp1x y(t) = (1 – t)p0y + tp1y t [0, 1] p0 Trang 30
  31. Đường cong Bezier bậc hai p1 p2 2 2 p(t) = (1 – t) p0 + 2(1 – t)tp1 + t p2 t [0, 1] hoặc 2 2 x(t) = (1 – t) p0x + 2(1 – t)tp1x + t p2x 2 2 y(t) = (1 – t) p0y + 2(1 – t)tp1y + t p2y t [0, 1] p0 Trang 31
  32. Đường cong Bezier bậc ba p1 p2 p0 p3 3 2 2 3 p(t) = (1 – t) p0 + 3(1 – t) tp1 + 3(1 – t)t p2 + t p3 t [0, 1] hoặc 3 2 2 3 x(t) = (1 – t) p0x + 3(1 – t) tp1x + 3(1 – t)t p2x + t p3x 3 2 2 3 y(t) = (1 – t) p0y + 3(1 – t) tp1y + 3(1 – t)t p2y + t p3y t [0, 1] Trang 32
  33. Đạo hàm p’(0) = 3(p1 – p0) p’(1) = 3(p3 – p2) p”(0) = 6(p0 – 2p1 + p2) p”(1) = 6(p1 – 2p2 + p3) p1 p2 p3 p0 Trang 33
  34. Một số đường cong Bezier bậc ba Trang 34
  35. Độ thẳng của đường cong Bezier p 1 p2 p0 p3 p − p + p − p + p − p f = 0 1 1 2 2 3 p0 − p3 Trang 35
  36. Thuật tốn vẽ đệ qui Vẽ Bezier (p0, p1, p2, p3) Bắt đầu Nếu Thẳng (p0, p1, p2, p3) thì Vẽ đoạn thẳng p0p3 Ngược lại Chia {pi} thành {li} và {ri} Vẽ Bezier (l0, l1, l2, l3) Vẽ Bezier (r0, r1, r2, r3) Kết thúc Trang 36
  37. Thuật tốn vẽ đệ qui p1 p2 p3 p0 r l3 r0 1 l2 r2 l1 r3 l0 Trang 37
  38. Thuật tốn vẽ đệ qui p + 3p + 3p + p l = p r = 0 1 2 3 0 0 0 8 p + p p + 2p + p l = 0 1 r = 1 2 3 1 2 1 4 p + 2p + p p + p l = 0 1 2 r = 2 3 2 4 2 2 p + 3p + 3p + p l = 0 1 2 3 r = p 3 8 3 3 Trang 38
  39. ĐƯỜNG CONG HERMITE
  40. Định nghĩa đường cong Input 2 điểm {p0, p1} 2 vector {v0, v1} Ouput v0 v1 p0 p1 Trang 40
  41. Cơng thức xác định đường cong v0 v1 p0 p1 3 3 3 3 p(t) = H0 (t)p0 + H1 (t)p1 + H2 (t)v0 + H3 (t)v1 3 2 3 2 3 2 3 2 p(t) = (2t + 3t + 1)p0 + (-2t + 3t )p1 + (t – 2t + t)v0 + (t – t )v1 t [0, 1] hoặc 3 2 3 2 3 2 3 2 x(t) = (2t + 3t + 1)p0x + (-2t + 3t )p1x + (t – 2t + t)v0x + (t – t )v1x 3 2 3 2 3 2 3 2 y(t) = (2t + 3t + 1)p0y + (-2t + 3t )p1y + (t – 2t + t)v0y + (t – t )v1y t [0, 1] Trang 41
  42. Một số đường cong Hermite Trang 42
  43. Đường cong Bezier bậc ba & Hermite H B p0 = p0 H B p1 = p3 H B B v0 = 3(p1 − p0 ) H B B v1 = 3(p3 − p2 ) B B p1 p2 H B v 0 H p3 p1 H vH B p0 1 p0 Trang 43
  44. Dẫn nhập Bao nhiêu đường cong? Trang 44
  45. ĐƯỜNG CONG PHỨC
  46. Định nghĩa đường cong phức Đường cong phức là sự kết hợp của những đường cong cơ sở C = {C1, C2, , Cn} C2 C3 C4 C1 Trang 46
  47. Yêu cầu thiết kế đường cong phức Đối với người thiết kế 1. Dễ vẽ 2. Liên tục 3. Cục bộ Đối với người lập trình 1. Biểu diễn dễ dàng và hiệu quả 2. Tính tốn hiệu quả Trang 47
  48. Tính liên tục Liên tục bậc 0 Liên tục bậc 1 Liên tục bậc 2 Trang 48
  49. Phân loại 1. Đường cong Splines 2. Đường cong B-Splines 3. Đường cong Nurbs (NonUniform Rational B-Splines) Trang 49
  50. CÁC ĐƯỜNG CONG SPLINES
  51. Định nghĩa đường cong Splines Input n +1 điểm {P0, P1, , Pn} và một số thơng tin khác Output C = {C1, C2, , Cn} với Ci là các đường cong Hermite P1 Pn-1 C1 Cn C2 P0 Pn P2 Trang 51
  52. Cardinal Splines - Tham số tension t p0 = Pk Pk Pk+1 p1 = Pk+1 (1− t) v = (P − P ) 0 2 k+1 k−1 Pk-1 (1− t) v1 = (Pk+2 − Pk ) Pk+2 2 Trang 52
  53. Ảnh hưởng của tham số tension t t 0 Trang 53
  54. Catmull-Rom Splines ❖Là trường hợp đặc biệt của Cardinal Splines với t = 0 p0 = P1 P2 P1 P4 p1 = P2 P − P v = 2 0 0 2 P3 − P1 v1 = P3 2 P0 Trang 54
  55. Kochanek-Bartels Splines ❖Là trường hợp tổng quát của Cardinal Splines - Tham số tension t - Tham số bias b - Tham số continuity c p0 = Pk p1 = Pk+1 1 v = (1− t)(1+ b)(1− c)(P − P ) + (1− b)(1+ c)(P − P ) 0 2 k k−1 k+1 k 1 v = (1− t)(1+ b)(1+ c)(P − P ) + (1− b)(1− c)(P − P ) 1 2 k+1 k k+2 k+1 Trang 55
  56. Ảnh hưởng của tham số bias b b 0 Trang 56
  57. Natural Splines ❖Là đường cong liên tục C2 P1 v3 v0 v1 P3 P0 P2 v2 Trang 57
  58. Natural Splines P1 v3 v0 v1 P3 P0 P2 v2 Trang 58
  59. Natural Splines Trường hợp 1 : Biết các vector v0 và vn 1      v v 0 0 1 4 1    v1 3(P2 − P0 )  1 4 1   v 3(P − P ) 2 = 3 1            1 4 1 vn−1 3(Pn − Pn−2 )      1 vn vn Trang 59
  60. Natural Splines Trường hợp 2 : Đạo hàm bậc hai tại hai điểm P0 và Pn đều bằng 0 2 1     v 3(P − P ) 0 1 0 1 4 1    v1 3(P2 − P0 )  1 4 1   v 3(P − P ) 2 = 3 1            1 4 1 vn−1 3(Pn − Pn−2 )     1 2 vn 3(Pn − Pn−1) Trang 60
  61. Free Splines ❖Là đường cong liên tục C0 Trang 61
  62. ĐƯỜNG CONG B-SPLINES
  63. Định nghĩa Input n +1 điểm {P0, P1, , Pn}, Bậc k – 1, Tập hợp tham số knot {t0, t1, , tn+k} Output C = {C1, C2, , Cn-2} với Ci là các đường cong Bezier P1 P2 C1 P5 C2 C3 P0 P3 P4 Trang 63
  64. Cơng thức i=n k p(t) = Ni (t)Pi i=0 t 0,1 Với 1 1 nếu t ti,ti+1 Ni (t) = 0 khác k t − ti k−1 ti+k − t k−1 Ni (t) = Ni (t) + Ni+1 (t) ti+k−1 − ti ti+k − ti+1 Trang 64
  65. Cơng thức B-Splines bậc ba đều P1 p1 p2 P2 P0 + 4P1 + P2 p0 = P5 6 p p0 3 2P + P p = 1 2 1 3 P + 2P p = 1 2 2 3 P + 4P + P p = 1 2 3 3 6 P0 P3 P4 Trang 65
  66. Cơng thức B-Splines bậc hai đều p1 P1 P2 p 2 P1 − P0 p0 = P5 2 p1 = P1 p0 P − P p = 2 1 2 2 P0 P3 P4 Trang 66
  67. ĐƯỜNG CONG HỮU TỈ
  68. Định nghĩa ❖Là đường cong trong đĩ các hàm x(t) và y(t) là các hàm đa thức hữu tỉ Đường trịn Đường ellipse Trang 68
  69. Đường Conic Dạng chuẩn Ellipse x2 y2 + = 1 a, b 0 a2 b2 Hyperbola x2 y2 − = 1 a, b 0 a2 b2 Parabola y2 = 4ax a 0 Trang 69
  70. Đường Conic Dạng tham số Ellipse 1− t2 x(t) = a 2 1+ t t (− , ) 2t y(t) = b 1+ t2 Hyperbola 1+ t2 x(t) = a 2 1− t t (− , ) 2t y(t) = b 1− t2 Trang 70
  71. Đường Bezier hữu tỉ bậc hai Input p0(x0, y0) và trọng số w0 p1(x1, y1) và trọng số w1 p2(x2, y2) và trọng số w2 Output p1,w1 p0,w0 p2,w2 Trang 71
  72. Cơng thức Hệ tọa độ thuần nhất x(t) x0 x1 x2 2 2 2 y(t) = B0 (t) y0 + B1 (t) y1 + B2 (t) y2 w(t) w0 w1 w2 B2 (t)x + B2 (t)x + B2 (t)x 0 0 1 1 2 2 2 2 2 = B0 (t)y0 + B1 (t)y1 + B2 (t)y2 2 2 2 B0 (t)w0 + B1 (t)w1 + B2 (t)w2 Trang 72
  73. Cơng thức Hệ tọa độ đề các B2 (t)x + B2 (t)x + B2 (t)x 0 0 1 1 2 2 x(t) B2 (t)w + B2 (t)w + B2 (t)w = 0 0 1 1 2 2 2 2 2 y(t) B0 (t)y0 + B1 (t)y1 + B2 (t)y2 2 2 2 B0 (t)w0 + B1 (t)w1 + B2 (t)w2 2 x0 2 x1 2 x2 B0 (t) + B1 (t) + B2 (t) y0 y1 y2 = 2 2 2 B0 (t)w0 + B1 (t)w1 + B2 (t)w2 2 x0 2 x1 2 x2 B0 (t)w0 + B1 (t)w1 + B2 (t)w2 y0 y1 y2 = 2 2 2 B0 (t)w0 + B1 (t)w1 + B2 (t)w2 Trang 73
  74. Biểu diễn Conic bằng Bezier hữu tỉ Đường Ellipse a(1− t2 ) x(t) b(2t) = 2 y(t) 1+ t B2 (t)a + B2 (t)a + B2 (t)0 0 1 2 2 2 2 B0 (t)0 + B1 (t)b + B2 (t)2b = 2 2 2 B0 (t) + B1 (t) + B2 (t)2 2 a 2 a 2 0 B0 (t).1. + B1 (t).1. + B1 (t).2. 0 b b = 2 2 2 B0 (t).1+ B1 (t).1+ B2 (t).2 Trang 74
  75. ĐƯỜNG CONG NURBS
  76. Định nghĩa ❖Là đường cong phức C = {C1, C2, , Cn-2} với Ci là các đường cong Bezier hữu tỉ Trang 76