Bài giảng Đồ họa 2D - Chương 3c: Đường cong - Bùi Tiến Lên

Nội dung text: Bài giảng Đồ họa 2D - Chương 3c: Đường cong - Bùi Tiến Lên

1. Đồ 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
2. 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
3. Vấn đề tính giá trị đa thức Ña thöùc baäc nhaát y = ax + b Caùch tính thoâng thöôøng Caùch tính caûi tieá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
4. Vấn đề tính giá trị đa thức Ña thöùc baäc hai y = ax2 + bx + c Caùch tính thoâng thöôøng Caùch tính caûi tieá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
5. Vấn đề tính giá trị đa thức Ña thöùc baäc ba y = ax3 + bx2 + cx + d Caùch tính caûi tieá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
6. Đường cong được biểu diễn bằng Phương trình tham số
7. Bài toá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
8. Thuật toá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
9. Thuật toán Bước 2 : Tính (x, y) ti tN t2 t1 to Trang 19
10. Thuật toá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
11. 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
12. Cài đặt // Lớp phương trình tham số class TPara2D { virtual TPoint2D operator () (double t) = 0; } Trang 22
13. 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
14. ĐƯỜNG CONG CAD
15. ĐƯỜNG CONG BEZIER
16. Định nghĩa đường cong Input n +1 điểm điều khiển {p0, p1, , pn} Output p1 p0 pn Trang 26
17. Công thức xác định đường cong Ptts ñöôøng cong Bezier baäc n ñöôïc taïo bôûi n + 1 ñieåm ñieàu khieå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 hoaë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
18. Tính chất 1 Bảo toàn qua phép biến đổi affine. Trang 28
19. 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
20. Đườ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
21. Đườ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
22. Đườ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
23. Đạ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
24. Một số đường cong Bezier bậc ba Trang 34
25. Độ 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
26. Thuật toá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
27. Thuật toán vẽ đệ qui p1 p2 p3 p0 r l3 r0 1 l2 r2 l1 r3 l0 Trang 37
28. Thuật toá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
29. ĐƯỜNG CONG HERMITE
30. Định nghĩa đường cong Input 2 điểm {p0, p1} 2 vector {v0, v1} Ouput v0 v1 p0 p1 Trang 40
31. 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
32. Một số đường cong Hermite Trang 42
33. Đườ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
34. Dẫn nhập Bao nhieâu ñöôøng cong? Trang 44
35. ĐƯỜNG CONG PHỨC
36. Đị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
37. 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 toán hiệu quả Trang 47
38. 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
39. Phân loại 1. Đường cong Splines 2. Đường cong B-Splines 3. Đường cong Nurbs (NonUniform Rational B-Splines) Trang 49
40. CÁC ĐƯỜNG CONG SPLINES
41. Đị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
42. 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
43. Ảnh hưởng của tham số tension t t 0 Trang 53
44. 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
45. 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
46. Ảnh hưởng của tham số bias b b 0 Trang 56
47. Natural Splines ❖Là đường cong liên tục C2 P1 v3 v0 v1 P3 P0 P2 v2 Trang 57
48. Natural Splines P1 v3 v0 v1 P3 P0 P2 v2 Trang 58
49. 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
50. 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
51. Free Splines ❖Là đường cong liên tục C0 Trang 61
52. ĐƯỜNG CONG B-SPLINES
53. Đị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
54. Công thức i=n k p(t) = Ni (t)Pi i=0 t 0,1 Vôùi 1 1 neáu t ti,ti+1 Ni (t) = 0 khaù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
55. 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
56. 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
57. ĐƯỜNG CONG HỮU TỈ
58. Đị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
59. Đườ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
60. Đườ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
61. Đườ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
62. 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
63. 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
64. 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
65. ĐƯỜNG CONG NURBS
66. Đị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