intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

ĐỒ HỌA MÁY TÍNH - XÉN HÌNH, TÔ MÀU

Chia sẻ: Nguyễn Văn Quang | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST
Báo xấu
624
lượt xem 95
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Xén hình 1. Xén đoạn thẳng vào hình chữ nhật Cohen–Sutherland, Thuật toán Chia nhị phân, Liang–Barsky 2. Xén đoạn thẳng vào hình tròn 3. Xén đường tròn vào hình chữ nhật 4. Xén đa giác vào hình chữ nhật 5. Xén đa giác vào đa giác

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: ĐỒ HỌA MÁY TÍNH - XÉN HÌNH, TÔ MÀU

  1. 4/4/2011 CH 2. XÉN HÌNH, TÔ MÀU Trương Văn Quốc Nhật 1 Nội dung  Xén hình 1. Xén đoạn thẳng vào hình chữ nhật Cohen–Sutherland, Thuật toán Chia nhị phân, Liang–Barsky 2. Xén đoạn thẳng vào hình tròn 3. Xén đường tròn vào hình chữ nhật 4. Xén đa giác vào hình chữ nhật 5. Xén đa giác vào đa giác  Tô màu 1. Thuật toán Loang 2. Thuật toán Dòng quét (Scan-line)  Bài tập 2 1
  2. 4/4/2011 Xén (clipping) 3 1. Xén đoạn thẳng vào hình chữ nhật 4 6 2 1 3 5 • Thuật toán Chia nhị phân • Cohen–Sutherland • Liang–Barsky 4 2
  3. 4/4/2011 Thuật toán Cohen–Sutherland • A = B = 0000  AB D  ClipD F AB 4 6 2 • A & B ≠ 0000  AB D  ClipD F D B • A & B = 0000 và A | B ≠ 0000: Xét A (giả sử A nằm ngoài): 1  Thay A bởi giao của AB 3 với cạnh trái nối dài A  Thay A bởi giao của AB với cạnh phải nối dài  Thay A bởi giao của AB với cạnh dưới nối dài 5  Thay A bởi giao của AB với cạnh trên nối dài 5 Bit: 3 2 1 0 Thuật toán Chia nhị phân 4 6 2 D 1 3 5 6 Bit: 3 2 1 0 3
  4. 4/4/2011 Thuật toán Liang-Barsky Ptrình tham số: x x A t xB xA y y A t yB yA 2 xm in x A t xB xA xm ax 1 3 D ym in y A t yB yA ym ax 2 0t1 Đặt: x xB x A , y yB y A p1 x , q1 x A xmin (trái) x , q2 xm ax x A (phải) p2 2 3 p3 y , q3 y A ym in (dưới) 4 1 y , q4 ymax y A (trên) p4 1  pk t qk , k 1,4 Cohen- : Cập nhật y 1  Liang- : Cập nhật t 0t1 3 2 1 0 Bit: 0 : AB // 1 cạnh CÝ: pk 0 : ngoài  trong pk Thứ tự cắt: 7 0 : trong  ngoài pk tráiphảitrêndưới Kiểm tra… Đặt: x xB x A , y yB y A x , q1 x A xmin (trái) p1 0 : AB // 1 cạnh pk x , q2 xm ax x A (phải) p2 0 : ngoài  trong pk p3 y , q3 y A ym in (dưới) 0 : trong  ngoài pk y , q4 ymax y A (trên) p4 ymax D Cạnh trái - - + + p1 x A xB Cạnh phải - - + + p2 x B x A ymin Cạnh dưới - - + + p3 yA yB xmax xmin Cạnh trên - - + + p4 y B y A 8 4
  5. 4/4/2011 Thuật toán Liang-Barsky t0=0; dx=xB-xA; t1=1; dy=yB-yB; for (canh=14){ //duyệt lần lượt các cạnh switch (canh){ //0.tính p,q,r 1: p=-dx; q=xA-xmin; 2: p=dx; q=xA-xmin; 3: p=-dy; q=xA-xmin; 4: p=dy; q=xA-xmin; } r=q/p; //1.cạnh song song  ko vẽ if (p=0 && qt0) t0=r; } else if (p>0) { //3.trong  ngoài //nằm ngoài ko vẽ if (rt1) t1=r; } } x0=xA+t0*dx; y0=yA+t0*dy; x1=xA+t1*dx; y1=yA+t1*dy; return đoạn:(x0,y0)(x1,y1); 11 Xén đoạn thẳng vào HCN xiên xoay -α α cắt xoay α α 12 5
  6. 4/4/2011 Xén đa giác vào hình chữ nhật 13 Ý tưởng Sutherland-Hodgeman trên phải trái dưới 14 6
  7. 4/4/2011 Cắt dọc theo cạnh trên U Un D 9 10 2 3 8 7 6 d 5 C D A B 4 C B 1 1 U1 A A=10; 9 for (B=110){ 8 if (B trong){ 4 if (A ngoài) Thêm(AB∩d); 5 Thêm(B); } else { if (A trong) Thêm(AB∩d); } A=B; } 7 6 15 Thuật toán Sutherland-Hodgeman U = danh_sách_đỉnh_đa_giác; for (cạnh = trênphảidướitrái){ Vn VU; //lúc này: V đầy, U rỗng //cý: sau mỗi lần cắt, n có thể thay đổi A=Vn; for (B = V1Vn){ if (B trong){ if (A ngoài) ném(AB∩cạnh); ném(B); } else { if (A trong) ném(AB∩cạnh); V1 } U V A=B; } } 17 7
  8. 4/4/2011 Cắt đôi? Cắt thành 2 cái luôn à? 6 3 4 5 2 1 18 Xén đa giác vào đa giác 19 8
  9. 4/4/2011 Ui chao, dễ Xác định “trong”, “ngoài”? òm! 0trên B(7,9) n2 n1 yB yA , xB xA - n2 yB yA , xB xA n1 ngoài Giả sử: AP x, y AP n AP n cos AP P AP n x yB y A y xB xA A (5,3) α (2,3) + 0 : trong cos n 0 : trên cos 20 0 : ngoài cos trong Xác định mã xP xmin xmax yP ymin ymax ymax D P = 0; if (xP < xmin) P = P|1; //trái P if (xP > xmax) P = P|2; //phải ymin if (yP < ymin) P = P|4; //dưới xmax if (yP > ymax) P = P|8; //trên xmin Tính mã P Bit: 3 2 1 0 21 9
  10. 4/4/2011 Nội dung  Xén hình 1. Xén đoạn thẳng vào hình chữ nhật Cohen–Sutherland, Thuật toán Chia nhị phân, Liang–Barsky 2. Xén đoạn thẳng vào hình tròn 3. Xén đường tròn vào hình chữ nhật 4. Xén đa giác vào hình chữ nhật 5. Xén đa giác vào đa giác  Tô màu 1. Thuật toán Scanline 2. Thuật toán Loang  Bài tập 22 Thuật toán Loang – Ý tưởng 1 4 p 2 3 x 42 26 x 28 14 27 41 16 6 15 29 40 23 8 2 7 17 30 39 25 13 5 1 3 9 18 31 38 24 12 4 10 19 32 37 22 11 20 33 36 21 34 35 • Đệ quy • Khử đệ quy 23 10
  11. 4/4/2011 Thuật toán Loang – Đệ quy Stack Loang(4,4) Loang(5,5) Loang(6,4) x 5 6 7 0 Loang(5,3) Loang(5,4) Loang(6,5) x x 3 Loang(x,y,mau) Loang(7,4) Loang(6,3) { Loang(5,5) 6 5 x S && ChưaTô(x,y)] 4 if [(x,y) Loang(6,6) { Loang(7,5) Tô(x,y); 7 4 17 Loang(6,4) 5 Loang(5,6) Loang(x,y-1,mau); Loang(6,7) Loang(x+1,y,mau); 8 3 16 6 Loang(7,6) Loang(x,y+1,mau); Loang(6,5) Loang(5,7) Loang(x-1,y,mau); 9 2 15 7 Loang(6,8) } Loang(7,7) } Loang(6,6) 10 1 14 8 Loang(5,8) Gọi: Loang(6,8,đỏ) Loang(7,9) 11 12 13 9 Loang(7,8) Loang(6,7) y Loang(6,8) 24 Thuật toán Loang – Khử đệ quy (1,5) Queue (2,6) (3,7) (4,8) (5,7) Vào: x0,y0,mau (6,6) (7,5) Tô(x0,y0); Q = {(x0,y0)}; (2,4) (6,4) x while (Q ≠ Ф) 0 1 2 3 4 5 6 7 8 (3,3) { (5,3) 0 (4,2) Pop(p);//lấy p từ Q x 1 (2,5) for ( v = Kề(p)) (3,6) x 14 x 2 if [v S && ChưaTô(v)] (4,7) x 16 6 15 x 3 { (5,6) Tô(v); (6,5) x 18 8 2 7 17 x 4 (3,4) Push(v);//đưa v vào Q x 25 13 5 1 3 9 19 x 5 (5,4) } (4,3) x 24 12 4 10 20 x } 6 (3,5) x 23 11 21 x 7 (4,6) (5,5) x 22 x 8 Ví dụ: (x0,y0)=(4,5) (4,4) x 9 (4,5) 25 y 11
  12. 4/4/2011 Thuật toán Loang – Khử đệ quy Vào: x0,y0,mau Tô(x0,y0); Tô(x0,y0); dau=cuoi=0; Q = {(x0,y0)}; Qx[0]=x0; Qy[0]= y0; while (Q ≠ Ф) while (dau ≤ cuoi) { { Px=Qx[dau]; Pop(p);//lấy p từ Q Py=Qy[dau]; dau++; //lấy p từ Q for ( (vx,vy) Kề(px,py)) for ( v Kề(p)) if [v S && ChưaTô(v)] if [(vx,vy) S && ChưaTô(vx,vy)] { { Tô(vx,vy); cuoi++; Tô(v); Qx[cuoi]=vx; Push(v);//đưa v vào Q Qy[cuoi]=vy;//đưa v vào Q } } } } 26 27 12
  13. 4/4/2011 Thuật toán Dòng quét (Scan-line) x1 x2 x3 x4 x3 x4 x1 x2 x3 x4 x1 x2 x3 x2 x1 x2 x1 x1,x2,x3,x4,x5,x6 (x1,x2), (x3,x4 ), ( x5,x6) - Dòng quét cắt đứt 2 cạnh liên tiếp  bỏ xi+1 xi xi+1 - Dòng quét xẹt qua 2 cạnh liên tiếp  giữ xi+1 28 Bài tập 1. Bắt buộc (2 tuần): Xây dựng (nếu có) & Cài đặt các thuật toán :  Xén đoạn thẳng vào hình chữ nhật (Cohen–Sutherland, Liang-Barsky)  Xén đa giác vào hình chữ nhật (Sutherland-Hodgeman)  Tô màu Loang (đệ quy, khử đệ quy) Mỗi thuật toán vẽ là 1 phương thức, gộp vào 1 file mã nguồn (đuôi là cs). 2. Không bắt buộc (thoải mái): Xây dựng (nếu có) & Cài đặt các thuật toán:  Xén đoạn thẳng vào HCN xiên  Xén đa giác vào đa giác (Sutherland-Hodgeman)  Tô màu dòng quét 29 13
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2