Bài giảng Đồ họa máy tính - Chương 7: Đường và mặt cong tự do trong không gian ba chiều - Trần Thị Minh Hoàn

Nội dung text: Bài giảng Đồ họa máy tính - Chương 7: Đường và mặt cong tự do trong không gian ba chiều - Trần Thị Minh Hoàn

1. Chương VII: Đường và mặt cong tự do trong không gian ba chiều Mô hình hóa ba chiều  Nhiệm vụ  Biểu diễn các đối tượng rắn để hiển thị  Trong nhiều trường hợp có thể biểu diễn chính xác bề mặt đối tượng: khối hộp, hình trụ, hình cầu  Với khối rắn bất kỳ phải sử dụng phương pháp xấp xỉ và nội suy  Hai giải pháp chính  Xây dựng mô hình đường cong, mặt cong có dạng tự do để đạt độ trơn cao nhất  Xấp xỉ mặt cong bởi tập đa giác (khảm): chia bề mặt đối tượng thành nhiều đa giác con 1
2. Biểu diễn đường cong tự do  Lựa chọn cách biểu diễn 2
3. Biểu diễn đường cong tự do  Lựa chọn cách biểu diễn  Đường cong bất kỳ có thể biểu diễn bới ma trận điểm  Cần số lượng điểm vô cùng lớn để biểu diễn chính xác hình dạng  Sử dụng hàm đa thức để thể hiện hình dạng đường cong  Dạng tổng quát của hàm đa thức n n n 1 i p(x) an x an 1x a1x a0 ai x i 0 n – nguyên dương, a0, a1, , an là số thực  Đa thức thuận tiện cho tính toán bằng máy tính  Trong đồ họa đòi hỏi xác định tiếp tuyến, pháp tuyến cho đường cong. Đa thức cho khả năng dễ dàng tính vi phân. 3
4. Biểu diễn đường cong tự do  Dạng thông dụng biểu diễn đường cong trong mô hình hóa hình học: Dạng tham số  Đường cong được xấp xỉ bởi đường cong đa thức liên tục từng phần  Mỗi đoạn đường cong được xác định bởi ba hàm x, y và z x = x(t), y = y(t) và z = z(t)  Véctơ vị trí của các điểm trên đường cong sẽ là: p(t) = (x(t), y(t), z(t))  Hai phương pháp xấp xỉ thông dụng nhất trong các hệ thống CAD hiện nay là Bézier và B-spline 4
5. Đường cong Bézier  Pierre Bézier (1960, Renault), P. de Casteljau (Citroen)  Đường cong Bézier bậc n được xác định bởi n+1 điểm điều khiển là phương trình tham số có dạng sau: n P(t) V B (t), 0 t 1  k k ,n k 0 n n k k n! n k k Bk ,n (t) (1 t) t (1 t) t k k!(n k)! V0, V1 Vn - các điểm điều khiển Bk,n(t) – hàm liên kết trơn (là đa thức Bernstein, hàm trộn) Bk ,n (t) 0, vớivíi mọimäi k và 0 t 1 n  Bk ,n (t) 1 0 t 1 k 0 5
6. Đường cong Bézier n  Từ phương trình P(t) Vk Bk ,n (t), 0 t 1 k 0  Ta có hệ phương trình tham số n n n x(t)  xk Bk ,n (t) y(t)  yk Bk ,n (t) z(t)  zk Bk ,n (t) k 0 k 0 k 0  Đường cong Bézier tuyến tính (linear) có dạng P(t) = (1-t) V + t V 0 1  Đường cong Bézier bậc 2 (quadratic) có dạng 2 2 P(t) = (1-t) V0 + 2(1-t)tV1+t V2 6
7. Đường cong Bézier bậc 3 (cubic)  Đường cong Bézier bậc 3 được xác định bởi 4 điểm: Điểm bắt đầu (anchors) điểm kết thúc, hai điểm điều khiển (handles) Từ n P(t) Vk Bk ,n (t), 0 t 1 Ta có k 0 V1 V2 P(t)=V0B0,3+V1B1,3+V2B2,3+V3B3,3 3! V B t 0 (1 t)3 (1 t)3 0 0,3 0!3! 3! V B t1(1 t)2 3t(1 t)2 3 1,3 1!2! 3! 2 2 B2,3 t (1 t) 3t (1 t) 2!1! [(1-t)3]+[3t(1-t)2]+[3t2(1-t)]+t3=1 3! 3 0 3 B t (1 t) t P(t) = (1-t)3V + 3(1-t)2tV +3(1-t)t2P +t3V 3,3 3!0! 0 1 2 3 7
8. Dạng ma trận đường cong Bézier  Với đường cong bậc 3 V0 V P(t) (1 t)3 3t(1 t)2 3t 2 (1 t) t 3  1 V2 V3 V0 V P(t) (1 3t 3t 2 t 3 ) (3t 6t 2 3t 3 ) (3t 2 3t 3 ) t 3  1 V2 V3 1 3 3 1 V0 3 6 3 0 V P(t) t 3 t 2 t 1 1 3 3 0 0 V2 1 0 0 0 V3 P(t) = [t] [M]B [V]B 8
9. Thuật toán vẽ đường cong Bézier // n+1 số lượng các điểm điều khiển //Pi điểm điều khiển thứ i có các tọa độ x, y, z là (Pix, Piy, Piz) BesierCurve() begin n for i=0 to n do P(t) V B (t) Nhập điểm điều khiển P  k k ,n i k 0 next i n! for t=0. to 1. insteps of 0.05 do n k k Bk ,n (t) (1 t) t x=y=z=0. k!(n k)! for i=0 to n do B=Blend(i, n, t) x=x+P *B ix Blend (i, n, t) y=y+Piy*B z=z+Piz*B begin next i blend=GiaiThừa(n)/(GiaiThừa(i)*GiaiThừa(n-i)) if (x, y, z) là điểm bắt đầu blend=blend*(t)i*((1-t)n-i) then MoveTo (x, y, z) else LineTo(x, y, z) return (blend) endif end next t end 9
10. Thí dụ đường cong Bézier Cho hai đường cong Bézier P, Q xác định bởi trình tự các điểm sau: P: A(2, 3, 4), B(3, 1, 5), C(x, y, z), D(3, 4, 3) Q: D(3, 4, 3) , E(2, 6, 0), F(5, 7, 5), G(5, 2, 3) Hãy thiết lập điều kiện sao cho x, y, z bảo đảm tính liên tục C1.  P và Q là các đường cong bậc 3 3 2 2 3 Q(t)=(1-t) V0+3t(1-t) V1+3t (1-t)p2+t V3 V0 V 3 2 2 3 1 Q(t) (1 t) 3t(1 t) 3t (1 t) t  V2 V3  Véctơ tiếp tuyến (lấy đạo hàm theo t) 10
11. Thí dụ đường cong Bézier  Tìm véctơ tiếp tuyến (lấy đạo hàm theo t) V 0 V Q ' (t)  3(1 t)2 3(3t 2 4t 1) 3t(3t 2) 3t 2  1 V2 V 3  Phân đoạn thứ nhất tại cuối đường cong, với u=1, P’(u) và phân đoạn thứ 2 tại đầu đường cong, với t=0, Q’(0) A D B E P'( 1) 0 0 3 3 3(D C) Q'(0)  3 3 0 0 3(E D) C F D G  Để đảm bảo tính liên tục thì P’(u) tại u=1 phải bằng Q’(t) tại t=0 3(D-C)=3(E-D) x=4, y=2, z=6 11
12. Bài tập 1. Một đường cong Bézier bậc 3 có bốn điểm điều khiển (0, 0, 0), (4, 2, 2), (8, 6, 4), (12, 0, 0). Hãy xác định tiếp tuyến của đường cong tại t=1/4. 12
13. Biểu diễn mặt cong tự do  Phương pháp biểu diễn đường cong là công cụ hữu hiệu để biểu diễn đường cong như Hermite, Bézier, B-Spline  Đường cong  Cần 1 biến tham số (1 bậc tự do) để biểu diễn  Mặt cong P(t) = [x(t), y(t), z(t)] 0 t 1  Cần hai biến tham số P(s,t) = [x(s,t), y(s,t), z(s,t)] 0 t 1, 0 s 1
14. Mặt cong Bézier V0, V0,  Mặt cong Bézier được định nghĩa từ 2 3 V0, phương trình đường cong đơn giản 1 V1, 1 V3,  t Tích tensơ áp dụng cho hai hướng s và t 3 V1, V  Xác định các điểm trên mặt cong 0, 0 0 s V2, 0 V3, 0 n m P(s,t) Vi, j Bi,n (s)B j,m (t) 0 s, t 1 i 0 j 0 Vi,j - các điểm điều khiển, tổng số điểm điều khiển là (m+1)x(n+1); Bi,n(s) và Bj,m(t) - các hàm liên kết trơn Bernstein theo các hướng s và t.
15. Mặt cong Bézier  Tính chất  Mặt cong có dạng tổng quát theo điểm điều khiển  Nằm trong miền bao lồi của các điểm điều khiển  Các điểm góc mặt cong trùng với các điểm điều khiển tại góc  Biểu diễn dạng ma trận T T P(s,t) = [s][M]B[V]B [M]B [t] T  Ma trận chuyển vị [A] của ma trận [A]: T  Với mỗi phần tử aij của [A] thì phần tử tương ứng của [A] là aji.  Ma trận chuyển vị của ma trận hàng là ma trận cột -1 -1  [A] là ma trận nghịch đảo của [A]: [A][A] =I, (I là ma trận đơn vị)
16. Mặt cong Bézier  Biểu diễn dạng ma trận của mặt cong Bézier kép 1 3 3 1 V0,0 V0,1 V0,2 V0,3 3 6 3 0 V V V V P (s,t) s3 s2 s 1 1,0 1,1 1,2 1,3 3 3 0 0 V2,0 V2,1 V2,2 V2,3 1 0 0 0 V3,0 V3,1 V3,2 V3,3 1 3 3 1 t 3 2 3 6 3 0 t P (s,t) 3 3 0 0 t 1 0 0 0 1  Để biểu diễn mặt cong Bézier kép cần đến 16 điểm điều khiển
17. Thí dụ ứng dụng mặt cong Bézier  Yêu cầu Một kết cấu mái nhà dạng nửa hình trụ rỗng. Hãy tạo lưới điều khiển Bézier để xấp xỉ mặt cong này  Giải pháp  Xác định lưới điều khiển để tạo ra các điểm mặt cong dọc theo mặt cắt ngang nửa hình trụ.  Di chuyển các điểm này dọc theo trục z với khoảng cách đều nhau  Khảo sát mặt cắt tại z=0: chọn 5 điểm trên cung tròn sau: P0(20, 0), P1(102, 102), P2(0, 20), P3(-102, 102), P4(-20,0) y P2 P y z P3 1 100 t P4 x 20 P0 x
18. Thí dụ ứng dụng mặt cong Bézier  Để nội suy P0, ,P4 cần 5 điểm điều khiển Bézier: V0, V1, V2, V3, V4. 4 P(t)  B4,i (t)Vi i 0  Chọn ti cho t trong khoảng [0,1]: t0=0.0, t1=0.25, t2=0.5, t3=0.75, t4=1.0  Viết biểu thức dưới dạng đồng nhất B40 (t0 ) B41 (t0 ) B42 (t0 ) B43 (t0 ) B44 (t0 ) V0 B (t ) B (t ) . . . V 40 1 41 1 1 P5 x3 B5 x5 V 5x3 . . . . . V2 . . . . . V3 B40 (t4 ) . . . B44 (t4 ) V4 n n! 4! i n i i n i B (t ) t1 (1 t)4 1 4x0.25x(0.25)3 0.4218 Bni (t) t (1 t) t (1 t) 41 1 i i!(n i)! 1!(4 1)!
19. Thí dụ ứng dụng mặt cong Bézier  Tính cho mọi phần tử còn lại của [B] 1 0 0 0 0 0.3164 0.4218 0.2109 0.0469 0.0039 1 V 5 x3 B5 x5 P5 x3 B5x5 0.0625 0.25 0.375 0.25 0.0625 0.0039 0.0468 0.2812 0.4218 0.3164 0 0 0 0 1 -1 V0 1 0 0 0 0 20 0 1 20 0 1 V 0.3164 0.4218 0.2109 0.0469 0.0039 10 2 10 2 1 21.05 15.44 1 1 V2 0.0625 0.25 0.375 0.25 0.0625 0 20 1 - 0.1 32.61 1 V3 0.0039 0.0468 0.2812 0.4218 0.3164 10 2 10 2 1 - 21.05 15.44 1 V4 0 0 0 0 1 20 0 1 - 20 0 1
20. Thí dụ ứng dụng mặt cong Bézier  Bổ sung các điểm điều khiển đường cong trên lưới Bézier bằng cách thay đổi giá trị z từ 0 đến 100 với khoảng cách đều 20  Lưới điều khiển Bézier với 30 điểm sẽ là (20,0,0) (20,0,20) (20,0,40) . . (21.05,15.44,0) (21.05,15.44,20) . . . ( 0.1,32.61,0) . . . . . . . . . ( 20,0,0) ( 20,0,20) ( 20,0,40) . .
21. Khảm (Tessellation )  "tessellate" là xếp đặt hình vuông nhỏ theo mẫu khảm  Hai loại khảm  Sử dụng đa giác đều (tam giác, hình vuông, lục giác)  Sử dụng tam giác không đều (TIN – Triagulated Irregular Network Model)  TIN có khả năng biểu diễn bề mặt liên tục từ tập điểm dữ liệu rời rạc trong không gian.  Về mặt hình học, chúng là tập các đỉnh được nối với nhau thành các tam giác để hình thành bề mặt 3D.  Trong mỗi tam gác là mặt phẳng  Bề mặt thô cần nhiều điểm vào còn bề mặt trơn tru cần ít điểm vào hơn.
22. Thí dụ khảm (Tessellation ) Khỉ đầu chó Lưới tam giác Lưới TIN được raster 200x200 không đều tô màu
23. Kỹ thuật xây dựng TIN  Sơ đồ Voronoi  Thí dụ: Phân hoạch vùng cho các cột điện thoại trong thành phố  1850: Peter Lejeune-Dirichlet  1908: Voronoi công bố  Định nghĩa  Gọi P = {p1, p2, ,pn} là tập các điểm trong mặt phẳng Euclidean hai chiều. Gọi các điểm này là site. Hãy phân hoạch mặt phẳng này theo cách gán từng điểm của nó cho site gần nó nhất. Toàn bộ các điểm trong vùng được gán cho site hình thành vùng Voronoi V(pi). V(pi) bao gồm mọi điểm gần site pi hơn bất kỳ site nào khác. V ( pi ) x : pi x p j x , j i
24. Sơ đồ Voronoi  Sơ đồ Voronoi 2 vị trí p1, p2  x Gọi B(p1, p2) = B12 là đường phân giác vuông p1 góc với đoạn p1, p2.  Tính chất: Mọi điểm x trên B12 cách đều p1 và p2 B12 p2 hay |p1x | = | p2x |  Sơ đồ Voronoi của 3 vị trí B  Các vị trí p1, p2, p3 tạo thành tam giác 23  Tính chất: Sơ đồ chứa các đường phân giác p2 p vuông góc B12, B23 và B31. Theo Euclid thì 3 B chúng gặp nhau tại một điểm – đó là tâm của 12 B31 đường tròn duy nhất đi qua ba đỉnh tam giác. p1  Sơ đồ Voronoi của ba điểm là một điểm
25. Xây dựng TIN  Tam giác TIN thỏa mãn tiêu thức Delauney  Năm 1934 Delauney đã chứng minh  Nếu nối từng cặp site trong sơ đồ Voronoi có hai đa giác cùng chia sẻ một cạnh bởi đoạn thẳng thì ta có các tam giác của những site.  Các tam giác này thỏa mãn tiêu thức Delauney: vòng tròn ngoại tiếp của chúng không bao bất kỳ site nào khác.  Tính chất tam giác Delauney  Tồn tại duy nhất một sơ đồ Voronoi tương ứng với tập điểm cho trước  Nếu v là đỉnh Voronoi tại giao của các vùng V(p1), V(p2) và V(p3) thì v là tâm của vòng tròn C(v) xác định bởi p1, p2, p3 và bên trong vòng tròn này sẽ không chứa đỉnh nào khác.
26. Xây dựng TIN Hình thành TIN từ sơ đồ Voronoi