Bài giảng Đồ họa máy tính - Tuần 8: Phương pháp xén hình - Lý Quốc Ngọc

Download

Đồ họa máy tính

Tuần 8: Phương pháp XÉN HÌNH

Nội dung

8.1. Xén đoạn thẳng vào hình chữ nhật

8.2. Xén đa giác vào hình chữ nhật

8.3. Xén đa giác vào đa giác lồi

TS. Lý Quốc Ngọc

3/24/2014

8.1. Xén đoạn thẳng vào HCN

8.1.1. Phát biểu bài toán

Đặc tả miền trong của HCN là:

D 



(x, y)R²| xmin  x  xmax, ymin  y  ymax



Đoạn thẳng L qua (x1,y1), (x2,y2) có dạng:

x  x1 (x2 x1).t

y  y1 (y2 y1).t







t [0,1]

TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.1. Phát biểu bài toán

Phần giao DL là nghiệm của hệ phương trình:

xmin  x1 (x2 x1).t  xmax

y min  y1 (y2  y1).t  y max (1)

0  t 1











TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.1. Phát biểu bài toán

Gọi T là tập nghiệm của hệ phương trình (1),

DL  

T [t₁,t₂],

T  

T  

Nếu

thì





(x, y) R , x  x1 (x2 x1).t,









D  L 

y  y1 (y2  y1).t,

t₁ t  t₂









TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

- Xét vị trí tương quan giữa L và D:

x1, x2  xmin

x1, x2  xmax

y1, y2  y min

y1, y2  y max







(1)

L nằm ngoài D



TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

- Xét vị trí tương quan giữa L và D:

xmin  x1, x2  xmax

y min  y1, y2  y max









(2)

L nằm trong D

L cắt D nếu 2 đầu mút không thỏa (1) và (2)

TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

Để xét vị trí tương quan giữa L và D, Cohen-

Sutherland để xuất sử dụng mã vùng.

Mã vùng của một điểm P là Code(P) gồm 4

bits: Left(P), Right(P), Below(P), Above(P)

được xác định như sau:

TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

1 x  xmin

1 x  xmax



Left(P) 

Right(P) 









0 x  xmin

0 x  xmax

1 y  y min

1 y  y max



Below(P) 

Above(P) 









0 y  ymin

0 y  ymax

TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

Nếu L cắt D, giả sử

(A ở ngoài HCN).

Code(A)  0000

Ta thực hiện lặp quá trình sau cho đến khi đoạn thẳng

tạo sinh nằm ngoài hoặc nằm trong D.

- Nếu Left(A)=1: cập nhật A bởi nghiệm của hệ

phương trình

x  xmin







y_B y

y  y_A

^A(x  x_A)

x_B x_A





TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

- Nếu Right(A)=1: cập nhật A bởi nghiệm của hệ

phương trình

x  xmax







y_B y

y  y_A

^A(x  x_A)

x_B x_A





TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

- Nếu Below(A)=1: cập nhật A bởi nghiệm của hệ

phương trình

y  y min







x_B x_A

x  x_A

(y  y_A)



y_B y_A



TS. Lý Quốc Ngọc

8.1. Xén đoạn thẳng vào HCN

8.1.2. Phương pháp Cohen-Sutherland

- Nếu Above(A)=1: cập nhật A bởi nghiệm của hệ

phương trình

y  y max







x_B x_A

x  x_A

(y  y_A)



y_B y_A



TS. Lý Quốc Ngọc

8.2. Xén đa giác vào HCN

8.2.1. Phát biểu bài toán

Đặc tả miền trong của HCN là:

D 



(x, y)R²| xmin  x  xmax, ymin  y  ymax



Đa giác P có các đỉnh P₁(x₁,y₁),…, P_n(x_n,y_n) gồm

các đoạn thẳng có P_iP_i+1modndạng:

x  x  (x  x ).t







i1modn

t_i[0,1]; i[1,n]

y  y_i (y_i1modn y_i).t_i

TS. Lý Quốc Ngọc

8.2. Xén đa giác vào HCN

8.2.1. Phát biểu bài toán

DP

Phần giao

là miền trong được tạo bởi tập các

đỉnh của D thuộc đa giác P và tập điểm là nghiệm của

các hệ phương trình sau

xmin  x  (x  x ).t  xmax







i1modn

y min  y  (y  y ).t  y max i[1,n]

i1mod



0  t_i1



TS. Lý Quốc Ngọc

8.2. Xén đa giác vào HCN

8.2.2. Phương pháp Sutherland-Hodgeman

Giai đoạn 1. Xác định tập điểm ứng viên tạo nên

DP

phần giao

-Nếu tất cả các đỉnh của P đều nằm trên D (hoặc trong D)

thì kết quả chính là đa giác.

-Nếu ngược lại (tồn tại ít nhất 1 điểm của P nằm ngoài D)

. Duyệt lần lượt các cạnh của P khởi đầu từ đỉnh (x₁,y₁).

. Với mỗi cạnh của P, ta có các trường hợp sau:

. Nếu cả 2 đỉnh đều nằm ngoài HCN thì

. Nếu cạnh nằm ngoài HCN thì không lưu đỉnh.

. Nếu cạnh cắt HCN thì lưu 2 giao điểm.

TS. Lý Quốc Ngọc

8.2. Xén đa giác vào HCN

8.2.2. Phương pháp Sutherland-Hodgeman

. Với mỗi cạnh của P, ta có các trường hợp sau:

. Nếu P_inằm ngoài, P_i+1modnnằm trong: lưu giao điểm I

và P_i+1modn

. Cả hai đỉnh nằm trong D: lưu P_ivà P_i+1modn

. Nếu P_inằm trong, P_i+1modnnằm ngoài: lưu P_ivà I

TS. Lý Quốc Ngọc

8.2. Xén đa giác vào HCN

8.2.2. Phương pháp Sutherland-Hodgeman

Giai đoạn 2. Bổ sung tập điểm ứng viên tạo nên

phần giao

DP

Sau khi duyệt qua tất cả các cạnh của P, ta có một dãy

các đỉnh mới phát sinh {Q}, (giải sử {Q} )

 

i[1,m]

Nếu trong dãy các đỉnh mới này, có hai đỉnh liên tiếp

không nằm trên cùng một cạnh của D. giả sử là Q_i

và Q_i+1. Đi dọc theo các cạnh của D từ Q_iđến Q_i+1

để tìm tất cả các đỉnh của D nằm trong P rồi bổ

sung chúng vào giữa Q_ivà Q_{i+1 .}

TS. Lý Quốc Ngọc

8.2. Xén đa giác vào HCN

8.2.2. Phương pháp Sutherland-Hodgeman

Giai đoạn 2. Bổ sung tập điểm ứng viên tạo nên phần

giao

DP

Tập điểm được bổ sung cấu thành nên phần giao

DP

Nếu tậo điểm này rỗng:

. Nếu tồn tại một đỉnh D nằm trong P thì kết quả D.

. Ngược lại kết quả là rỗng

TS. Lý Quốc Ngọc

8.3. Xén đa giác vào đa giác lồi

8.3.1. Phát biểu bài toán

Cho trước đa giác lồi Pconvex.

Đa giác bị cắt P có các đỉnh P₁(x₁,y₁),…, P_n(x_n,y_n)

gồm các đoạn thẳng có P_iP_i+1modndạng:

x  x  (x  x ).t







i1modn

t_i[0,1]; i[1,n]

y  y_i (y_i1modn y_i).t_i

TS. Lý Quốc Ngọc

Tải về để xem bản đầy đủ

24 trang Thùy Anh 27/04/2022 6020

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa máy tính - Tuần 8: Phương pháp xén hình - Lý Quốc Ngọc", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

bai_giang_do_hoa_may_tinh_tuan_8_phuong_phap_xen_hinh_ly_quo.pdf