ĐỒ HỌA 2D
ĐỒ HỌA 2D
CÁC THUẬT TOÁN XÉN HÌNH
CÁC THUẬT TOÁN XÉN HÌNH
Giảng viên : Bùi Tiến Lên
Trang 2
Xén hình là gì (Clipping) ?
Xén hình là gì (Clipping) ?
Là thao tác loại bỏ phần hình ảnh của thế giới thực nằm
bên ngoài một cửa sổ quan sát.
Trang 3
Các loại xén hình
Các loại xén hình
- Xén điểm
- Xén đoạn thẳng
- Xén đa giác
- Xén đối tượng
Xeùn ñieåm
Xeùn ñieåm
Trang 5
Cách xén
Cách xén
Input
Điểm P
Output
P thuộc cửa sổ W ?
l r
b
t
P(x, y)


P
2
P
1
P
2
Q
1
Q
2
Trang 8
Phân vùng
Phân vùng
Mặt phẳng được chia thành làm 5 vùng.
bên trong
Trang 9
Phaõn vuứng
Phaõn vuứng
beõn traựi beõn phaỷi
Trang 10
Phaân vuøng
Phaân vuøng
beân treân
beân döôùi
Trang 11
Maừ vuứng Caựch tớnh
Maừ vuứng Caựch tớnh
( )
tbrlC
WPC

Trang 13
Thuật toán
Thuật toán
Lặp
bước 1 : Tính mã vùng
C
1
là mã vùng của P
1
C
2
là mã vùng của P
2
bước 2 : Xét mã vùng
th1 : Đoạn thẳng nằm vùng bên trong
th2 : Đoạn thẳng thuộc các vùng bên ngoài
th3 : Còn lại
Trang 14
Trường hợp 1
Trường hợp 1
P
1
P
2
Dừng
PQ
PQ
Thì
0000C
0000C

dưới bên vùngthuộc PP
?1??C
?1??C
phải bên vùngthuộc PP
??1?C
??1?C
trái bên vùngthuộc PP
???1C
???1C
vùngmã Nếu
21
2
1
21
2
1
21
2
1
21
2
1
Trang 17
Trường hợp 3
Trường hợp 3
P
2
P
1
1moi2

=
∩=
Trang 19
Tóm tắt
Tóm tắt
Tính
mã vùng
Xét
Hết
Begin
End
P
1
, P
2
Q
1
, Q
2
P
1moi
,
P
2moi
th1 th2th3
Xeựn ủoaùn thaỳng
Xeựn ủoaùn thaỳng
Thuaọt toaựn Liang-Barsky
Thuaọt toaựn Liang-Barsky
Trang 21

Trang 22
Vớ duù
Vớ duù
( ) ( )



+=
+=
t3y
t24x
: thaỳng ủửụứng soỏ tham trỡnh Phửụng .6,4B ,4,3A ủieồm 2 Cho
1 2 3 4 5 6 7 8 9
1
2
3
4
5
6
10
(
4
,
3
)
(
6
,
4
)

Trang 24
Böôùc 1
Böôùc 1
( )
( )
[ ]
1,0t
WtPPPW
WtPPPW
ty1y2y1b
rx1x2x1l
∈
≤−+≤
≤−+≤
P
1
P
2
t
0
1
Trang 25
Böôùc 2
Böôùc 2
( )
( )
[ ]
1,0t
qtp
qtp