Bài giảng Đồ họa Raster - Chương 2, Phần 1: Các thuật toán tô màu - Bùi Tiến Liên

Nội dung text: Bài giảng Đồ họa Raster - Chương 2, Phần 1: Các thuật toán tô màu - Bùi Tiến Liên

1. ĐỒ HỌA RASTER CÁC THUẬT TỐN TƠ MÀU Giảng viên : Bùi Tiến Lên
2. Bài tốn tơ màu Tơ màu là thao tác tìm các điểm sáng “nằm bên trong” một vùng khép kín. Input : Vùng S Output : {(x1, y1), (x2, y2) (xn, yn)} Trang 2
3. Các hướng tiếp cận Cĩ hai phương pháp - Tơ màu theo lân cận - Tơ màu theo dịng quét Trang 3
4. Tơ màu theo lân cận
5. Lân cận là gì ? Cĩ hai loại lân cận : lân cận 4 và lân cận 8. Lân cận 4 N4(x, y) = {(x-1, y), (x, y+1), (x+1, y), (x, y-1)} Lân cận 8 N8(x, y) = {(x-1, y), (x-1, y+1), (x, y+1), (x+1, y+1), (x+1, y), (x+1, y- 1), (x, y-1), (x-1, y-1)} trên trái y trái (x,y) phải y (x,y) dưới x x Trang 5
6. Thuật tốn đệ qui bước 1 Kẻ biên vùng cần tơ bước 2 Xác định một điểm (x, y) nằm bên trong vùng cần tơ bươc 3 Tơ điểm (x, y), sau đĩ tơ loang sang những điểm lân cận y x Trang 6
7. Cài đặt đệ qui // To loang void BoundaryFill(CDC *pDC, int x, int y, int fill_color, int boundary_color) { int color; color = pDC->GetPixel(x, y); if((color != fill_color) && (color != boundary_color)) { pDC->SetPixel(x, y, fill_color); BoundaryFill(pDC, x-1, y, fill_color, boundary_color); BoundaryFill(pDC, x, y+1, fill_color, boundary_color); BoundaryFill(pDC, x+1, y, fill_color, boundary_color); BoundaryFill(pDC, x, y-1, fill_color, boundary_color); } } Trang 7
8. Nhận xét thuật tốn đệ qui Ưu điểm Khuyết điểm Cĩ thể tơ vùng cĩ hình dạng bất Khơng thể dùng để tơ các vùng kỳ. cĩ kích thước lớn. kích thước ! Trang 8
9. Thuật tốn cải tiến bước 1 Cất điểm hạt giống đầu tiên vào kho. bước 2 Lặp nếu kho khơng rỗng - c1 Lấy điểm hạt giống. - c2 Tơ điểm hạt giống sau đĩ tơ loang sang trái và sang phải. - c3 Bổ sung những điểm hạt giống mới vào kho từ dịng trên và dịng dưới. Trang 9
10. Thuật tốn cải tiến hạt giống : điểm sáng kho : chứa các điểm hạt giống Trang 10
11. Thuật tốn cải tiến Minh họa tơ loang biên biên Trang 11
12. Thuật tốn cải tiến Tiêu chuẩn để là điểm hạt giống 1. Điểm này chưa được tơ và khơng phải điểm biên. 2. Điểm này thoả : - Điểm trái đầu tiên. - hoặc bên trái của nĩ là điểm biên (nếu nĩ khơng phải là điểm trái đầu tiên). Trang 12
13. Thuật tốn cải tiến Minh họa bổ sung những điểm hạt giống mới biên biên hạt giống biên biên biên Trang 13
14. Tơ theo lân cận - Một số vấn đề Sử dụng lân cận nào ? Trang 14
15. Tơ theo lân cận - Một số vấn đề Đường biên màu gì ? Trang 15
16. Tơ theo lân cận - Một số vấn đề Trang 16
17. Tơ màu theo dịng quét
18. Khái niệm dịng quét Dịng quét là dịng điểm sáng trên màn hình y Trang 18
19. Tơ hình chữ nhật l r y t y b Trang 19
20. Tơ hình tam giác Input (X1, Y1), (X2, Y2), (X3, Y3) Cách tơ bước 1 : Sắp xếp các đỉnh Y1 Y2 Y3 bước 2 : Phân trường hợp Theo tung độ Trang 20
21. Tơ hình tam giác Y1 = Y2 = Y3 Y1 < Y2 = Y3 2 3 1 3 2 1 Y1 = Y2 < Y3 Y1 < Y2 < Y3 3 3 2 2 1 1 Trang 21
22. Tơ hình tam giác 1 3 2 Y1 Xmin Xmax Tơ tam giác (Y1 = Y2 = Y3) 1. Tìm Xmin, Xmax 2. Tơ dịng Y1 bắt đầu tại cột Xmin, kết thúc tại cột Xmax Trang 22
23. Tơ hình tam giác 2 3 Tơ tam giác (Y1 < Y2 = Y3) Y2 Lặp y : Y1 Y2 1. Tìm hồnh độ giao điểm x , x giữa y l r dịng quét y với các cạnh trái và cạnh phải của tam giác. 2. Tơ dịng y bắt đầu tại cột xl, kết thúc y Y1 tại cột x . 1 r xl xr Trang 23
24. Tơ hình tam giác Ví dụ Các hồnh độ giao điểm của các dịng quét với cạnh (2, 2), (11, 6). 2 6 5 4 3 2 1 8 17 26 35 44 4 4 4 4 4 Trang 24
25. Tơ hình tam giác Cách tính hoành độ giao điểm x đầu là X1 2 xmoi = xcu + k với X − X k = 2 1 1 Y2 − Y1 Trang 25
26. Tơ hình tam giác 3 Y3 2 Y2 y Y 1 1 Trang 26
27. Tơ hình đa giác lồi p0 Cách tơ p3 1. Chia đa giác lồi cĩ n đỉnh {p0, p1, , pn-1} thành n-2 tam giác. - p p p p1 1 0 1 2 p2 - 2 p0p2p3 - p0 - i p0pipi+1 - p1 pn-1 - n-2 p0pn-2pn-1 p2 2. Tơ từng tam giác. pn-2 p3 Trang 27
28. Tơ hình đa giác Nguyên lý chia tam giác Mọi đa giác khơng tự cắt đều cĩ thể phân chia thành các tam giác. Trang 28
29. Thuật tốn tơ đa giác tổng quát
30. Thuật tốn y bước 1 Tìm ymin và ymax max y = min{y , (x , y ) P} I1 I2 I3 I4 min i i i y ymax = max{yi, (xi, yi) P} bước 2 Tơ từng dịng P Lặp y : ymin ymax c1 Tìm các giao điểm. y ymin c2 Sắp xếp các giao điểm. c3 Tơ các đoạn thẳng. Trang 30
31. Lưu ý Bỏ cạnh nằm ngang bỏ bỏ Trang 31
32. Lưu ý Dịng quét đi qua đỉnh b d a c e y I1 I2 I3 I4 Bình thường h f g Trang 32
33. Lưu ý Dịng quét đi qua đỉnh Lỗi b y d I1 I2 I3 I4 I5 a c e h f g Trang 33
34. Lưu ý Cắt bớt cạnh c theo trục y 1 đơn vị b 1 y d 1 I1 I2 I3 I4 a c e h f g Trang 34
35. Ví dụ {(1, 1) (2, 7) (4, 9) (7, 9) (9, 5) (9, 1) (7, 1) (5, 5) (4, 1)} c 9 b 8 d 7 6 5 a 4 3 e h g 2 1 i f 1 2 3 4 5 6 7 8 9 Trang 35
36. Tiền xử lý 1 c 9 b 8 d 7 6 Loại bỏ các cạnh 5 a {c, f, i} 4 3 e h g 2 1 i f 1 2 3 4 5 6 7 8 9 Trang 36
37. Tiền xử lý 2 9 b 8 d 7 6 5 Xử lý các cạnh a 4 {a, e} 3 e h g 2 1 1 2 3 4 5 6 7 8 9 Trang 37
38. Tơ 9 b 8 k=1 d 7 k=-3/4 6 5 a 4 k=1/6 3 k=1/4 k=-1/2 e h g k=0 2 1 1 2 3 4 5 6 7 8 9 Trang 38
39. Thơng tin cạnh đa giác cạnh ylower yupper xlower k a 1 7 1 1/6 b 7 9 2 1 d 5 9 9 -3/4 e 1 5 9 0 g 1 5 7 -1/2 h 1 5 4 1/4 Trang 39
40. Thơng tin các cạnh đa giác cạnh ylower yupper xlower k a 1 6 1 1/6 b 7 9 2 1 d 5 9 9 -3/4 e 1 4 9 0 g 1 5 7 -1/2 h 1 5 4 1/4 Trang 40
41. Phương trình đoạn thẳng F(x, y) = (Y2 – Y1)(x – X1) – (X2 – X1)(y – Y1) (X2,Y2) (X1,Y1) Trang 41
42. Xác định bên trong tam giác như thế nào ? (X3,Y3) (X2,Y2) (X1,Y1) Trang 42
43. Chiều các đỉnh của tam giác Tính diện tích tam giác x (y − y ) + x (y − y ) + x (y − y ) S = 1 2 3 2 3 1 3 1 2 2 (X2,Y2) (X2,Y2) (X3,Y3) (X3,Y3) S>0 (X1,Y1) (X1,Y1) S<0 Trang 43
44. Thuật tốn 1. Tìm xmin, xmax, ymin, ymax 2. Lặp y : ymin ymax, x : xmin xmax Nếu (x, y) nằm bên trong tam giác thì Tơ (x, y) ymax ymin xmin xmax Trang 44