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

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

1. Thuật toán cải tiến Minh họa tô loang biên biên Trang 11
2. Thuật toá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
3. Thuật toá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
4. Tô theo lân cận - Một số vấn đề Sử dụng lân cận nào ? Trang 14
5. Tô theo lân cận - Một số vấn đề Đường biên màu gì ? Trang 15
6. Tô theo lân cận - Một số vấn đề Trang 16
7. Tô màu theo dòng quét
8. 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
9. Tô hình chữ nhật l r y t y b Trang 19
10. 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
11. 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
12. 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
13. Tô hình tam giác 2 3 Tô tam giác (Y1 < Y2 = Y3) Y2 Lặp y : Y1 Y2 1. Tìm hoà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
14. Tô hình tam giác Ví dụ Các hoà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
15. Tô hình tam giác Caùch tính hoaønh ñoä giao ñieåm x ñaàu laø X1 2 xmoi = xcu + k vôùi X − X k = 2 1 1 Y2 − Y1 Trang 25
16. Tô hình tam giác 3 Y3 2 Y2 y Y 1 1 Trang 26
17. 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
18. 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
19. Thuật toán tô đa giác tổng quát
20. Thuật toá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
21. Lưu ý Bỏ cạnh nằm ngang bỏ bỏ Trang 31
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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
28. 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
29. Thông tin cạnh đa giác caï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
30. Thông tin các cạnh đa giác caï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
31. 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
32. Xác định bên trong tam giác như thế nào ? (X3,Y3) (X2,Y2) (X1,Y1) Trang 42
33. 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
34. Thuật toá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