Clipping

ĐỒ HỌA MÁY TÍNH

Các thuật toán xén

điểm, đoạn thẳng

Dẫn nhập
? Thao tác loại bỏ các phần hình ảnh nằm ngoài một
vùng cho trước được gọi là xén hình.

? Vùng được dùng để xén hình gọi là cửa sổ xén (clip
window).

? Cho cửa sổ hình chữ nhật có tọa độ của các điểm
dưới bên trái và điểm trên bên phải lần lượt là
?xmin, ymin?? và ?xmax, ymax??.
? Một điểm P???y

được coi là nằm bên trong cửa sổ
?xmin? x ? xmax
?
nếu thỏa hệ bất phương trình : ??y
min
y y
? ?
max
.

? Bây giờ, ta sẽ xét bài toán xén đoạn thẳng được cho
bởi hai điểm P1?x1, y1?? và P2?x2, y2??vào cửa sổ hình
chữ nhật trên.

P7

P4





P3


P
1
P2

Window
P6
P8


P
1
P2

Window






P`5


P`6
(a)
P5
(b)



Dương Anh Đức, Lê Đình Duy



Các thuật toán xén hình 1/11

ĐỒ HỌA MÁY TÍNH

Vấn đề tối ưu hóa tốc độ

? Ý tưởng chung :

? Đối với các đoạn thẳng đặc biệt như nằm hoàn toàn
trong hoặc hoàn toàn bên ngoài cửa sổ (ví dụ như đoạn
P1P2 và P3P4 trong hình trên) : không cần phải tìm giao
điểm.

? Đối với các đoạn thẳng có khả năng cắt cửa sổ : cần phải
đưa ra cách tìm giao điểm nhanh.

? Nhận xét

? Các đoạn thẳng mà có cả hai điểm nằm hoàn toàn trong
cửa sổ thì cả đoạn thẳng nằm trong cửa sổ, đây cũng
chính là kết quả sau khi xén (ví dụ như đoạn thẳng
P1P2), mặt khác đối với các đoạn thẳng mà có hai điểm
nằm về cùng một phía của cửa sổ thì luôn nằm ngoài cửa
sổ và sẽ bị mất sau khi xén (ví dụ như đoạn thẳng P3P4).
? Với các đoạn thẳng có khả năng cắt cửa sổ (ví dụ như
đoạn thẳng P5P6và P7P8) để việc tìm giao điểm nhanh
cần rút gọn việc tìm giao điểm với những biên cửa sổ
không cần thiết để xác định phần giao nếu có của đoạn
thẳng và cửa sổ.

? Người ta thường sử dụng phương trình tham số của
đoạn thẳng trong việc tìm giao điểm giữa đoạn thẳng
với cửa sổ.
x ??x
1
y y
?
?
t x
?

2
?
x
1
?
?
?
x

1
?
tDx, Dx ??x

2
?
x
1
?
1
?
t y
2
?
y
1
?
y
1
?
tDy, Dy ? y
2
?
y
1
,
t
0 ? ??1

? Nếu giao điểm ứng với giá trị t nằm ngoài đoạn ???1
thì giao điểm đó sẽ không thuộc về cửa sổ.





Dương Anh Đức, Lê Đình Duy





Các thuật toán xén hình 2/11

ĐỒ HỌA MÁY TÍNH

Thuật toán Cohen - Sutherland

? Kéo dài các biên của cửa sổ, ta chia mặt phẳng
thành chín vùng gồm cửa sổ và tám vùng xung
quanh nó.



0101



0001



1001



0100



0000
Window

1000



0110



0010



1010



4 3 2 1






LEFT
RIGHT
TOP
BOTTOM






LEFT



TOP






BOTTOM






RIGHT


? Khái niệm mã vùng (area code)

? Một con số 4 bit nhị phân gọi là mã vùng sẽ được gán
cho mỗi vùng để mô tả vị trí tương đối của vùng đó so với
cửa sổ.

? Bằng cách đánh số từ 1 đến 4 theo thứ tự từ phải qua
trái, các bit của mã vùng được dùng theo quy ước sau để
chỉ một trong bốn vị trí tương đối của vùng so với cửa sổ
bao gồm : trái, phải, trên, dưới. Ví dụ :
Bit 1 : trái (LEFT)
Bit 2 : phải (RIGHT)
Bit 3 : trên (TOP)
Bit 4 : dưới (BOTTOM)

? Giá trị 1 tương ứng với vị trí bit nào trong mã vùng sẽ
chỉ ra rằng điểm đó ở vị trí ương ứng, ngược lại bit đó sẽ
được đặt bằng 0.

? Các giá trị bit trong mã vùng được tính bằng cách xác
định tọa độ của điểm ???x, thuộc vùng đó với các biêny
của cửa sổ. Bit 1 được đặt là 1 nếu
được tính tương tự.
x ??xmin, các bit khác

Dương Anh Đức, Lê Đình Duy

Các thuật toán xén hình 3/11



Thuật toán

ĐỒ HỌA MÁY TÍNH

? Gán mã vùng tương ứng cho các điểm đầu cuối
P1, P2của đoạn thẳng cần xén lần lượt là
có nhận xét :
c1, c2. Ta

? Các đoạn thẳng nằm hoàn toàn bên trong cửa sổ sẽ có
c1??c2??0000
, ứng với các đoạn này, kết quả sau khi
xén là chính nó.

? Nếu tồn tại

k ??1,..4 , sao cho với bit thứ k của
c1, c2 đều
có giá trị 1, lúc này đoạn thẳng sẽ nằm về cùng phía ứng
với bit k so với cửa sổ, do đó nằm hoàn toàn ngoài cửa
sổ. Đoạn này sẽ bị loại bỏ sau khi xén. Để xác định tính
chất này, đơn giản chỉ cần thực hiện phép toán logic
AND trên
c1, c2. Nếu kết quả khác 0000, đoạn thẳng sẽ
nằm hoàn toàn ngoài cửa sổ.

? Nếu
c1, c2

không thuộc về hai trường hợp trên, đoạn
thẳng có thể hoặc không cắt ngang cửa sổ, chắc chắn sẽ
tồn tại một điểm nằm ngoài cửa sổ, không mất tính tổng
quát giả sử điểm đó là P1. Bằng cách xét mã vùng của
P1là c1
ta có thể xác định được các biên mà đoạn
thẳng có thể cắt để từ đó chọn một biên và tiến hành
tìm giao điểm P1` của đoạn thẳng với biên đó. Lúc này,
đoạn thẳng ban đầu được xén thành
P1P1` . Sau đó chúng
ta lại lặp lại thao tác đã xét cho đoạn thẳng mới
P1P1`
cho tới khi xác định được phần nằm trong hoặc loại bỏ
toàn bộ đoạn thẳng.

? Các điểm giao với các biên cửa sổ của đoạn thẳng có thể
được tính từ phương trình tham số. Ví dụ : tung độ y của
điểm giao đoạn thẳng với biên đứng của cửa sổ có thể
? 1?
tính từ công thức y ? y1??m x ??x , trong đó x có thể là
xmin hay xmax.


Dương Anh Đức, Lê Đình Duy


Các thuật toán xén hình 4/11

ĐỒ HỌA MÁY TÍNH

Lưu đồ thuật toán Cohen - Sutherland


Begin



EnCode(P1,c1);
EnCode(P2,c2)



(c1!=0000) || (c2!=0000)


Yes


(c1&c2 == 0000)


Yes

Xác định giao điểm của đoạn
thẳng với biên của cửa sổ
bằng cách xét mã vùng của
điểm nằm ngoài cửa sổ





End

// Đoạn CT tính mã vùng

void EnCode(POINT p, CODE &c, RECT rWin)
{
c = 0;
if(p.x < rWin.Left)
c |= LEFT;
if(p.x > rWin.Right)
c |= RIGHT;
if(p.y > rWin.Top)
c |= TOP;
if(p.y < rWin.Bottom)
c |= BOTTOM;
}



No





No


Dương Anh Đức, Lê Đình Duy


Các thuật toán xén hình 5/11

ĐỒ HỌA MÁY TÍNH

Thuật toán Liang - Barsky

? Thuật toán Liang-Barsky được phát triển dựa vào
việc phân tích dạng tham số của phương trình đoạn
thẳng.

x ??x

1

?
?
t x

2

?

x

1
?

?

x

1

?

tDx, Dx ??x

2

?

x
1
y ??y
1
?
?
t y
2
?
y
1
?
?
y
1
?
tDy, Dy ? y
2
?
y
1
,
t
0 ? ??1

? Ứng với mỗi giá trị t, ta sẽ có một điểm P tương ứng
thuộc đường thẳng.

? Các điểm ứng với

? Các điểm ứng với

? Các điểm ứng với
t ??1 sẽ thuộc về tia P2x.
t ??0 sẽ thuộc về tia P2x`.
0 1
??t ? sẽ thuộc về đoạn thẳng

x







P1P2.













x`






P1(x1, y1)


t=0
t<0

P2(x2, y2)


t=1


t>1

? Tập hợp các điểm thuộc về phần giao của đoạn thẳng
và cửa sổ ứng với các giá trị t thỏa hệ bất phương
??xmin??x1??tDx ??x
max
?
y
? y tDy y
?
?
?
trình : ?
0
?
min
t
? ?
1
1
max






Dương Anh Đức, Lê Đình Duy






Các thuật toán xén hình 6/11



p




1



???



Dx, q
1

ĐỒ HỌA MÁY TÍNH
x1??xmin
?
p2??Dx,
q2??xmax??x1
? Đặt
p
3
???
Dy, q
3
?
y
1
?
y
min
p4??Dy,
q4? ymax??y1

? Lúc này ta viết hệ phương trình trên dưới dạng :

?

pkt ??qk, k

?

1,2,3,4
??0 ??t ??1
? Như vậy việc tìm đoạn giao thực chất là tìm nghiệm
của hệ bất phương trình này. Có hai khả năng xảy
ra đó là :

? Hệ bất phương trình vô nghiệm, nghĩa là đường thẳng
không có phần giao với cửa sổ nên sẽ bị loại bỏ.

? Hệ bất phương trình có nghiệm, lúc này tập nghiệm sẽ
là các giá trị t thỏa t ???t1, t2?????0,1 .
? Ta xét các trường hợp :

? Nếu

k
? ?
?1
?
,2,3,4 : (

p
k

q
0) (
? ?k

?

0)

thì rõ ràng bất
phương trình ứng với k trên là vô nghiệm, do đó hệ vô
nghiệm.

? Nếu
k
? ?
?1
?
,2,3,4 : (
p
k

0) (
? ?
q
k

?

0) thì với các bất
phương trình mà ứng với pk= 0 là các bất phương trình
hiển nhiên, lúc này hệ bất phương trình cần giải tương
đương với hệ bất phương trình có pk? 0.

? Với các bất phương trình
t ??qk/ pk.

? Với các bất phương trình
t ??qk/ pk.
pkt ??qkmà



pkt ??qkmà
pk??0 , ta có



pk??0 , ta có





Dương Anh Đức, Lê Đình Duy





Các thuật toán xén hình 7/11

ĐỒ HỌA MÁY TÍNH
? Vậy nghiệm của hệ bất phương trình là ?t1, t2?? với :

?
?t
1

??q
??max(?


k,p
k

?
??0?


U


???)
?
??
t
??2?
?
??pk
??q
min(?k, p
??pk



k


?
?
?
0
??U
?


???
)
?
t
??t
??1
?
2

? Nếu hệ trên có nghiệm thì đoạn giao

Q1Q2sẽ là
(x
t Dx y
t
x
t Dx y
t Dy
Q11
?
1
,
1
?
1
Dy), (
Q21
?
2
,
1
?
2
) .

? Nếu xét thuật toán này ở khía cạnh hình học ta có :

? Trường hợp
k
? ?
?1
?
,2,3,4 : (
p

k

?
0) ??(
q
k

?
0)

tương ứng
với trường hợp đoạn thẳng cần xét song song với một
trong các biên của cửa sổ ( pk??0 ) và nằm ngoài cửa sổ
( qk??0 ) nên sẽ bị loại bỏ sau khi xén.

? Với

pk??0 , giá trị t ??r
k

?

q


k

/ p


k

sẽ tương ứng với
giao điểm của đoạn thẳng với biên k kéo dài của cửa sổ.
Trường hợp
pk??0 , kéo dài các biên cửa sổ và đoạn
thẳng về vô cực, ta có đường thẳng đang xét sẽ có hướng
đi từ bên ngoài vào bên trong cửa sổ. Nếu
pk??0 , đường
thẳng sẽ có hướng đi từ bên trong cửa sổ đi ra. Do đó hai
đầu mút của đoạn giao sẽ ứng với các giá trị t1, t2được
tính như sau : Giá trị t1 chính là giá trị lớn nhất của các
r
k
/
??qkp
k
mà
pk??0
(đường thẳng đi từ ngoài vào
trong cửa sổ) và 0; giá trị t2chính là giá trị nhỏ nhất
của các
r
k
?
qk/ p
k mà
pk??0 (đường thẳng đi từ trong
cửa sổ đi ra) và 1.







Dương Anh Đức, Lê Đình Duy









Các thuật toán xén hình 8/11

ĐỒ HỌA MÁY TÍNH

Thuật toán xén đa giác

Sutherland - Hodgemand

Dẫn nhập