SOLUTION TUT 7

Câu I:
(left, right, bottom, top) = (30, 220, 50, 240)
Bảng outcode:
1. p1 = (40, 140), p2 = (100, 200)
//Compute Out Code
p1: outcode1 = 0000 p2: outcode2 = 0000
Bước 1: outcode1 | outcode2 = 0000
 Đoạn thẳng p1p2 thuộc vùng nhìn thấy.

2. p1 = (10, 270), p2 = (300, 0)
//Compute Out Code
p1: outcode1 = 1001 p2: outcode2 = 0110
Bước 1: outcode1 | outcode2 = 1111
Bước 2: outcode1 & outcode2 = 0000
 Giao một phần.
Bước 3: outcode1 & 1000 = 1000
Tính giao điểm:

x = x1 + (x2 – x1) * (top – y1) / (y2 – y1)
= 10 + (300-10) * (240 – 270) / (0 – 270) =42.22
y = top = 240
outcode của giao điểm: 0000
// Gán p1= p2(300,0) ; p2 = (x ,y)= (42.22 ,240)
// Lặp
p1: outcode1 = 0110 p2: outcode2 = 0000
Bước 1: outcode1 | outcode2 = 0110

//Compute Out Code
p1: outcode1 = 0101 p2: outcode2 = 0001
Bước 1: outcode1 | outcode2 = 0101
Bước 2: outcode1 & outcode2 = 0001
 Toàn bộ nằm ngoài khung nhìn. 4. p1 = (0, 0), p2 = (250, 250)
//Compute Out Code
p1: outcode1 = 0101 p2: outcode2 = 1010
Bước 1: outcode1 | outcode2 = 1111
Bước 2: outcode1 & outcode2 = 0000
 Giao một phần.
Bước 3: outcode1 & 1000 = 0000
outcode1 & 0100 = 0100
Tính giao điểm:

x = x1 + (x2 – x1) * (bottom – y1) / (y2 – y1);
= 0 + (250-0) * (50 – 0) / (250 – 0)
= 50
y = bottom = 50
outcode của giao điểm: 0000
// Gán p1= (x ,y)= (250 ,250) ; p2 =(50,50)
// Lặp
p1: outcode1 = 1010 p2: outcode2 = 0000
Bước 1: outcode1 | outcode2 = 1010
Bước 2: outcode1 & outcode2 = 0000
 Giao một phần.
Bước 3: outcode1 & 1000 = 1000
Tính giao điểm:

e = 2dx-dy = -4
e_inc = 2dx – 2dy = -10
x = 2
//lặp y từ 1 đến 7
// sau lần lặp đầu tiên
Chọn điểm ( 2, 1)
x = 2 ; e = -2
// sau lần lặp thứ 2: y= 2
Chọn điểm (2, 2)
x = 2 ; e = 0
// sau lần lặp thứ 3: y= 3
Chọn điểm (2, 3)
// e >= 0 nên x++; e = e + e_inc
x = 3 ; e = -10
// sau lần lặp thứ 4: y= 4
Chọn điểm (3, 4)
x = 3 ; e = -8
// sau lần lặp thứ 5: y= 5
Chọn điểm (3, 5)
x = 3 ; e = -6
// sau lần lặp thứ 6: y= 6
Chọn điểm (3 ,6)
x = 3 ; e = -4
// sau lần lặp thứ 7: y= 7
Chọn điểm (3, 7)
//kết thúc
b. (1, 1) và (7, 5).
dx = 6
dy = 4
// dx > dy
Câu III :
Cho đa giác ABCDEF có tọa độ các đỉnh như sau:
A = (2, 1); B = (6, 1); C = (7, 3); D = (6, 7); E = (4, 3); F = (2, 4)
Người ta dùng phương pháp đường quét để tô màu cho đa giác này
1) Hãy xây dựng bảng cạnh (Edge Table) cho đa giác này.
2) Hãy cho biết AEL (Active Edge List) tại các scan line y =1, y = 2, y = 3 và y = 4. 1) Edge table

Line 1 Line 2

Line 3

4
2
0

2
6
1/2



Line 4
Line 5
Line 6
Line 7
2) AEL (Active Edge List)

Scan line y =1
Scan line y =2

Scan line y = 3


1/2

4
2
0

2
7
1/2

4
2
0

4
4
-2

7
4
1/2

7
7
-1/4

4
2
0


flood_fill(x,y-1);
flood_fill(x,y+1);
}
}

Thứ tự cách pixel được tô:
(2, 2)  (3,2)  (2,1)  (1,1)  (2,3)  (1,3)

flood_fill (Eight-way)
flood_fill(int x, int y)
{
if (read_pixel(x,y) == WHITE)
{
write_pixel(x,y,BLACK);
flood_fill(x-1,y);
flood_fill(x+1,y);
flood_fill(x,y-1);
flood_fill(x,y+1);

flood_fill(x-1,y-1);
flood_fill(x+1,y-1);
flood_fill(x-1,y+1);
flood_fill(x+1,y+1);

}
}
Thứ tự cách pixel được tô:
(2, 2)  (3,2)  (2,1)  (1,1)  (2,3)  (1,3)