›
›

Bài giảng Đồ họa máy tính - Đường và mặt cong - Ngô Quốc Việt

pdf 43 trang Gia Huy 16/05/2022 3830
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa máy tính - Đường và mặt cong - Ngô Quốc Việt", để 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:

  • pdfbai_giang_do_hoa_may_tinh_duong_va_mat_cong_ngo_quoc_viet.pdf

Nội dung text: Bài giảng Đồ họa máy tính - Đường và mặt cong - Ngô Quốc Việt

  1. ĐƯỜNG VÀ MẶT CONG NGÔ QUỐC VIỆT 2009
  2. Đường cong Bezier . Thuật giải Casteljau. . Đa thức Bernstein. Đường bậc 3, B-splines. Mặt cong. Hỏi đ|p B{i tập 2
  3. Mục tiêu: x}y dựng đường cong thông qua c|c điểm điều khiển. Do Pierre Bezier x}y dựng (trong thời gian l{m việc ở Renault). Tương tự đường Hermit nhưng trực quan hơn 3
  4. p1 = x1,y1 p2 = x2,y2 p(t) = Si=0 3 Bi(t) pi 3 i 3-i Bi(t) = ( i) t (1-t) p = x ,y 0 0 0 p3 = x3,y3 3 2 2 3 p(t) = (1-t) p0 + 3(1-t) tp1 + 3(1-t)t p2 + t p3 3 2 2 3 x(t) = (1-t) x0 + 3(1-t) tx1 + 3(1-t)t x2 + t x3 3 2 2 3 y(t) = (1-t) y0 + 3(1-t) ty1 + 3(1-t)t y2 + t y3 4
  5. • Đường Bezier có bậc bất kỳ • Bậc đường Bezier=số điểm điều khiển – 1 • Ví dụ: – Bậc 2 (quadratic): 3 CPs – Bậc 3 (cubic): 4 CPs – Bậc 4 (quadratic): 5 CPs • C}u hỏi: – L{m c|c n{o thêm điểm điều khiển v{o đường Bezier x|c định? – L{m c|ch n{o chia đường cong Bezier th{nh hai đoạn cong Bezier? 5
  6. • X}y dựng điểm trên đường cong. p1 p01 = (1-t) p0 + t p1 p12 p12 = (1-t) p1 + t p2 p p = (1-t) p + t p p012 2 23 2 3 1-t p012 = (1-t) p01 + t p12 p123 p p = (1-t) p + t p 0123 123 12 23 p01 p0123 = (1-t) p012 + t p123 t p23 • Chia đường cong tại p0123 – p0 p01 p012 p0123 p0 – p0123 p123 p23 p3 p3 • Lặp lại với c|c gi| trị t để có đường Bezier. 6
  7. • Dùng để tăng điều khiển • Bắt đầu với S p (n ) ti (1-t)n-i = S q (n + 1) ti (1-t)n+1-i i i i i p • X|c định q 1 1/2 i q2 1/2 (t+(1-t)) S p (n ) ti (1-t)n-i 1/4 i i p2 n i n+1-i i+1 n-i = S pi ( i) (t (1-t) + t (1-t) ) q1 1/4 • So s|nh c|c hệ số q3 n + 1 n n 3/4 qi( i ) = pi( i) + pi-1( i-1) 3/4 qi = (i/(n+1))pi-1 + (n+1-i/(n+1))pi p0=q0 p3=q4 7
  8. • Dạng tổng qu|t với • Công thức trên x|c định lớp c|c đường cong Bezier. 8
  9. Hệ số của c|c điểm điều khiển l{ tập c|c h{m được gọi l{ Bernstein polynomials. Ở bậc 3 (4 điểm điều khiển), ta có: 9
  10. 3 3 B0 (t) B3 (t) • Bậc bất kỳ 1 n n i n-i Bi (t) = ( i) t (1-t) B 3(t) B 3(t) n n - 1 n - 1 1 2 ( i) = n!/(i!(n – i)!) = ( i ) + ( i - 1) • Ph}n hoạch đơn vị – Tổng bằng 1 với mọi t trong [0,1] n 0 Si=0 n Bi (t) = 1 0 1/3 2/3 1 • Đa thức bậc cao được x}y dựng từ c|c b đa thức bậc thấp hơn d n n i n-i Bi (t) = ( i) t (1-t) n - 1 i n-i n - 1 i n-i = ( i ) t (1-t) + ( i - 1) t (1-t) a n-1 n - 1 = (1-t)Bi (t) + tBi - 1 (t) c 3 3 3 3 p(t)=aB0 (t)+bB1 (t)+cB2 (t)+dB3 (t) 10
  11. n n-1 n - 1 Bi (t) = (1-t)Bi (t) + tBi - 1 (t) = 2 1 B0 (t) = (1-t) B0 (t) = + 2 1 1 B1 (t) = (1-t) B1 (t) + t B0 (t) = 2 1 B2 (t) = t B1 (t) 11
  12. f(0,0,1) f(0,t,1) f(0,t,t) f(0,1,1) f(t,t,t) f(t,t,1) f(0,0,t) p(t) = f(t,t,t) f(t,1,1) f(0,0,0) f(1,1,1) p(t) = f(t,t,t) = (1-t) f(t,t,0) + t f(t,t,1) = (1-t)[(1-t) f(t,0,0) + t f(t,0,1)] + t [(1-t) f(t,0,1) + t f(t,1,1)] = (1-t)2 f(t,0,0) + 2 (1-t) t f(t,0,1) + t2 f(t,1,1) = (1-t)3 f(0,0,0) + 3 (1-t)2 t f(0,0,1) + 3 (1-t) t2 f(0,1,1) + t3 f(1,1,1) 12
  13. n n p(t)  Bi (t) pi i 0 Bn (t) 0 p(t) p0  pn  n Bn (t) 13
  14. n n p(t)  Bi (t) pi i 0 m  m 1 00 0n p(t) p0  pn     n 1 mn0  mnn t j i n j mij ( 1) j i 14
  15. n n p(t)  Bi (t) pi i 0 m  m 1 00 0n p(t) p0  pn     n 1 mn0  mnn t 1 3 3 1 0 3 6 3 M 0 0 3 3 0 0 0 1 15
  16. Hầu hết phần cứng đồ họa chỉ hiển thị đường thẳng hay đa gi|c. Vậy hiển thị đường Bezier ra sao? Cần thuật giải thích nghi, trong đó xét tính phẳng vẽ đoạn thẳng nối giữa hai điểm đầu cuối thay vì vẽ đa gi|c. DisplayBezier (vo,v1,v2,v3) if (FlatEnough(v0,v1,v2,v3)) Line(v0,v3) else do something smart 16
  17. • So s|nh tổng độ d{i của đa gi|c điều khiển với độ d{i của hai điểm điều khiển đầu v{ cuối: 18
  18. B-splines điểu khiển từng vertex (tính cục bộ) cho từng đoạn cong. Tính liên tục của đường B-spline luôn được duy trì. Nhiều kiểu B-splines: bậc có thể kh|c nhau (linear, quadratic, cubic, ), theo dạng đồng nhất hay không đồng nhất. Với uniform B-splines, tính liên tục luôn có bậc thấp hơn một so với bậc của đoạn cong. . Linear B-splines liên tục trong C0, cubic liên tục trong C2, v.v. 19
  19. Định nghĩa tương tự như đường Bezier nhưng ho{n to{n dựa trên tập h{m cơ sở (blendding) kh|c. Không đi qua c|c điểm điều khiển (ngoại trừ hai điểm đầu cuối). 20
  20. Tập h{m cơ sở của đường B-Splines với 4 điểm điều khiển (còn gọi l{ cubic bspline). 3 x(t)  Pi Bi,4 (t) i 0 1 1 1 1 P 1 3t 3t 2 t 3 P 4 6t 2 3t 3 P 1 3t 3t 2 3t 3 P t 3 0 6 1 6 2 6 3 6 21
  21. • Đường cong có nội suy 0,7 (interpolate) c|c điểm đầu mút không? 0,6 B1,4 B2,4 • Đường B-splines có nằm trong 0,5 bao đóng? 0,4 1 x(t) P 1 3t 3t 2 t 3 0,3 0 6 0,2 1 2 3 B0,4 B3,4 P 4 6t 3t 0,1 61 1 0 P 1 3t 3t 2 3t 3 2 6 t 1 P t 3 3 6 22
  22. Tổng c|c gi| trị h{m trông (tại mọi t) luôn bằng 1. . Đường B-Spline nằm trong bao đóng Đường B-Splines không nội suy c|c điểm đầu cuối . Vì vậy cần đường non-uniform B-splines Dạng ma trận của cubic B-spline. 1 3 3 1 t3 2 1 3 6 0 4 t x(t) P P P P  6 0 1 2 3 3 3 3 1 t 1 0 0 0 1 23
  23. n X t  Pk Bk, d t Dạng tổng qu|t: k 0 . n l{ số điểm điều khiển. . d l{ bậc của đường cong, 2 d n+1, d thường bằng 3 hay 4 . Bk,d l{ h{m cơ sở B-spline uniform B-spline có bậc d-1. . Pk l{ c|c điểm điều khiển . Mỗi Bk,d kh|c zero trong một miền nhỏ c|c gi| trị t, vì vậy có tính cục bộ. 24
  24. B B B B B B B 0,7 0,4 1,4 2,4 3,4 4,4 5,4 6,4 0,6 0,5 0,4 0,3 0,2 0,1 0 -3 -2,5 -2 -1,5 -1 -0,5 0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 t 25
  25. n X t  Pk Bk,4 t 0,25 k 0 0,2 0,15 P1B1,4 P4B4,4 P0B0,4 P2B2,4 0,1 P6B6,4 P3B3,4 0,05 P5B5,4 0 3 0 3 - 2,4 1,5 0,6 2,7 2,1 1,8 1,2 0,9 0,3 0,3 1,2 2,1 3,9 4,8 0,6 0,9 1,5 1,8 2,4 2,7 3,3 3,6 4,2 4,5 - - - - - - - - - t 26
  26. Tại gi| trị t trên đường uniform cubic B-spline, có 4 h{m cơ sở kh|c zero. Mỗi h{m cơ sở l{ tịnh tiến của of B0,4 Xét khoảng 0 t<1 . Chúng ta chọn phần thứ tư của B0,4 . Chúng ta chọn phần thứ ba của B1,4 . Chúng ta chọn phần thứ hai của B2,4 . Chúng ta chọn phần thứ nhất của B3,4 27
  27. • Khoảng gi| trị tham số nguyên từ i đến i+1 cũng tương tự như khoảng từ 0 đến1. – Gi| trị tham số được dời đi một khoảng i – Tập c|c điểm điều khiển kh|c cần được x|c định. • Để x|c định cubic B-spline tại gi| trị t bất kỳ: – Tìm số nguyên lớn nhất mả nhỏ hơn hay bằng t: i = floor(t) – X|c định: 3 X t  Pi k Bk,4 t i k 0 • Miền x|c định hợp lệ của t: 0 t <n-3, với n l{ số điểm điều khiển. 28
  28. • Để lặp lại đường B-Spline, sử dụng c|c điểm điều khiển ở phần đầu đường cong để tính to|n c|c gi| trị tại tại cuối đường cong: 3 X t P(i k ) modn Bk,4 t i k 0 • C|c gi| trị tham số l{ hợp lệ 29
  29. • Uniform B-splines không nội suy c|c điểm điều khiển, ngoại trừ: – Lặp lại một điểm điều khiểm 3 lần – Tất cả đạo h{m triệt tiêu tại điểm điều khiển đó. – Để nội suy những điểm có đạo h{m kh|c zero, chúng ta cần sử dụng non-uniform B-splines với c|c điểm nút lặp lại. • Uniform B-splines thuộc C2 – Tất cả c|c h{m blending l{ C2, tổng c|c h{m blending l{ C2 30
  30. • C|ch thực hiện tương tự như đường Bezier – Ước lượng tập c|c gi| trị tham số t v{ nối c|c đoạn thẳng • Tuy nhiên, khó x|c định c|c ước lượng (về số lượng, gi| trị). – Dùng nguyên tắc chia để t|ch đường cong th{nh c|c đoạn ngắn, sau đó nối c|c điểm điều khiển. • Nguyên tắc subdivision cho B-splines như thế n{o? • Thay vì subdivision, h~y xem qu| trình t|ch l{ qu| trình tinh chỉnh: – Thêm c|c điểm điều khiển, v{ knots, giữa c|c điểm sẵn có. – Sử dụng thuật giải Oslo để vẽ đường B-Spline. 31
  31. • Ý tưởng chính: ph|t sinh 2n-3 điểm điều khiển mới: – Thêm điểm điều khiển mới v{o giữa từng đoạn cong: P’0,1, P’1,2, P’2,3 , , P’n-2,n-1 – Thay đổi c|c điểm điều khiển hiện h{nh: P’1, P’2, , P’n-2 • Bỏ điểm điều khiển đầu v{ cuối. 1 1 • Rules: P P P , P' P 6P P i, j 2 i j i 8 i 1 i i 1 • Nếu đường cong có chu trình, thì ph|t sinh 2n điểm điều khiển mới bằng c|ch tính c|c tọa độ trung bình . 32
  32. • Cả đường B-spline v{ Bezier l{ dạng đường cubic, vì vậy có thể biến đổi qua lại. • Nhắc lại, một điểm trên đường cong có thể biểu diễn bởi ma trận: x(t) PT MT – P l{ vector c|c điểm điều khiển. – M l{ ma trận hoặc MB-spline hay MBezier – T l{ vector cột chứa : t3, t2, t, 1 • Dễ d{ng x|c định được ma trận MB-spline->Bezier nhằm biến đổi c|c điểm điều khiển B-spline th{nh c|c điểm điều khiển Bezier 33
  33. 1 4 1 0 1 0 4 2 0 M B spline Bezier 6 0 2 4 0 0 1 4 1 P0,Bezier 1 4 1 0 P0,B spline P1,Bezier 1 0 4 2 0 P1,B spline P2,Bezier 6 0 2 4 0 P2,B spline P3,Bezier 0 1 4 1 P3,B spline 34
  34. • Uniform B-splines l{ trường hợp đặc biệt của B- splines • Mỗi h{m blending giống nhau • C|c h{m blending starts với t=-3, t=-2, t=-1, • Mỗi h{m blending kh|c zero for 4 units of the parameter • Non-uniform B-splines có c|c h{m blending starting v{ stopping ở c|c gi| trị kh|c nhau, v{ h{m blending cũng không giống nhau. 35
  35. • Knots: x|c định d~y c|c gi| trị tham số m{ tại đó c|c h{m blending sẽ được bật hay tắt. • Gi| trị Knot luôn tăng, v{ có n+d+1 trong tập đó tạo nên một knot vector: (t0,t1, ,tn+d) với t0 t1 tn+d • Một đường cong chỉ được x|c định cho những gi| trị tham số giữa td-1 v{ tn+1 • C|c gi| trị tham số n{y ứng với vị trí c|c đoạn của đường cong giao nhau. • Có một điểm điều khiển cho từng gi| trị trong knot vector • C|c h{m blending được định nghĩa đệ quy theo dạng the knots v{ bậc của đường cong. 36
  36. 1 tk t tk 1 t tk B t Bk,d t Bk,d 1 t k,1 t t 0 otherwise k d 1 k t t k d Bk 1,d 1 t tk d tk 1 • Quan hệ đệ quy bắt đầu với B-splines bậc 1, v{ x}y dựng dần cho c|c bậc cao hơn. • SỬ dụng thuật giải Cox - de Boor. 37
  37. • Uniform cubic B-splines được tạo với knot vector có dạng (-3,-2,-1,0,1, ,n+1) • Mỗi h{m blending l{ kh|c zero trên khoảng tham số có độ d{i 4. • Tất cả h{m l{ sự dịch chuyển lẫn nhau. – Mỗi h{m l{ được tạo ra do dời một đơn vị từ h{m trước đó. – Bk,d(t)=Bk+1,d(t+1) • C|c h{m blending l{ kết quả của phép to|n convolving với chính nó d lần. 38
  38. B 0,1 B 1,1 1,2 1,2 1 1 0,8 0,8 B1,1(t) 0,6 B0,1(t) 0,6 0,4 0,2 0,4 0 0,2 0 3 0 - 2,7 2,4 2,1 1,8 1,5 1,2 0,9 0,6 0,3 0,3 0,6 0,9 - - - - - - - - - t t B 2,1 B 3,1 1,2 1,2 1 1 0,8 0,8 B3,1(t) B2,1(t) 0,6 0,6 0,4 0,4 0,2 0,2 0 0 t t 39
  39. B0,2(t) B2,2(t) 0,2 0,4 0,6 0,8 1,2 0,2 0,4 0,6 0,8 1,2 0 1 0 1 -3 -3 -2,75 -2,5 -2,65 -2,25 -2,3 -2 -1,95 -1,75 -1,5 -1,6 B 2,2B -1,25 B0,2 -1,25 t -1 t -0,75 -0,9 -0,5 -0,55 -0,25 0 -0,2 0,25 0,15 0,5 0,75 0,5 B1,2(t) 1 0,85 0,2 0,4 0,6 0,8 1,2 B 0 1 0 -3 , 2 -2,75 ( t -2,5 ) -2,25 -2 t -1,75 1 -1,5 3 B B 1,2 -1,25 t t -1 -0,75 -0,5 2 3 -0,25 0 t t 0,25 0,5 2 1 0,75 1 40
  40. B 0,3 B 1,3 0,8 0,8 0,7 0,7 0,6 0,6 0,5 0,5 B1,3(t) 0,4 B0,3(t) 0,4 0,3 0,3 0,2 0,2 0,1 0,1 0 0 1 3 1 2 - - 0 - 0,5 1,5 2,5 0,5 - - - 0,75 0,25 2,25 1,75 0,75 0,25 2,75 1,25 - - - - - - 0 1 2 1 3 - - - 0,5 1,5 0,5 2,5 - - - 0,25 0,75 2,25 1,75 1,25 0,75 0,25 2,75 - - - - - - t t t 3 2 3 t 2 1 2 B0,3(t) 2t 6t 3 2 t 1 2 2 t 1 t 0 41
  41. B0,4(t) 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0 -3 -2,8 -2,6 -2,4 -2,2 -2 -1,8 -1,6 -1,4 B 0,4 -1,2 t -1 -0,8 -0,6 -0,4 -0,2 0 0,2 0,4 0,6 0,8 1 42
  42. t 3 3 3 t 2 1 3t3 15t2 21t 5 2 t 1 B (t) 0,4 3 2 6 3t 3t 3t 1 1 t 0 3 1 t 0 t 1 43