Báo cáo Kỹ thuật đồ họa đề tài "Dùng tool và ngôn ngữ lập trình viết một ứng dụng liên quan đến xén tỉa 2D và 3D"

lOMoARcPSD| 36067889 MỤC LỤC LỜI NÓI ĐẦU 3
A.PHÂN TÍCH BÀI TOÁN 4 1.XÉN TỈA LÀ GÌ? 4
2.CÁC LOẠI XÉN TỈA 4 2.1 Xén tỉa điểm 4
2.2 Xén tỉa đoạn thẳng 4 2.3 Xén tỉa đa giác 5
3. CÁC GIẢI THUẬT XÉN TỈA 6
3.1 Xén tỉa đoạn thẳng bằng thuật toán Cohen-Sutherland 6
3.2 Xén tỉa đoạn thẳng bằng thuật toán Lyangbarsky 11
3.3 Xén tỉa đa giác bằng thuật toán Sutherland-Hogman 13
B.PHÂN TÍCH THIẾT KẾ VÀ DEMO 20
1.THIẾT KẾ GIAO DIỆN HIỂN THỊ 20 1.1 Giao diện thanh chọn 20
1.2 Giao diện bảng vẽ 20
1.3 Hướng dẫn sử dụng demo 21
2.CÀI ĐẶT THUẬT TOÁN 21
2.1 Thuật toán Cohen-Sutherland 21 2.2 Thuật toán Lyangbarsky 24
2.3 Thuật toán Sutherland-Hodgman 28 3.DEMO 29
TÀI LIỆU THAM KHẢO 32 LỜI NÓI ĐẦU
Như chúng ta đã thấy trong những năm gần đây sự phát triển vượt
bậc về công nghệ đồ họa đã mang lại cho con người chúng ta vô vàn sự tiện
nghi, những trải nghiệm mới mẻ, chân thực.
Kỹ thuật đồ họa góp phần quan trọng làm cho giao tiếp giữa con
người và máy tính trở nên thân thiện hơn. Trong kỹ thuật đồ họa có nhiều
thuật toán khác nhau. Xong mỗi thuật toán lại tỏ ra có những ưu việt và hạn
chế riêng đối với từng bài toán cụ thể. lOMoARcPSD| 36067889
Là sinh viên khoa Công nghệ thông tin trường Học viện Công nghệ
Bưu Chính Viễn Thông. Chúng em cũng được tiếp xúc với môn học Kỹ
thuật đồ họa. Với những kiến thức em đã học và được sự hướng dẫn của cô
Nguyễn Thị Thanh Tâm chúng em đã thực hiện đề tài “ Dùng tool và ngôn
ngữ lập trình viết một ứng dụng liên quan đến xén tỉa trong 2D và 3D”.
Có lẽ rằng chương trình và báo cáo của chúng em chưa được chuyên
nghiệp, hoàn chỉnh nhất, còn có những thiếu sót. Vì thế em rất mong cô và
các bạn có thể góp ý để nhóm em xây dựng đề đạt kết quả tốt nhất có thể.
A.PHÂN TÍCH BÀI TOÁN 1. XÉN TỈA LÀ GÌ?
Xén tỉa là tiến trình xác định các điểm của một đối tượng nằm trong
hay ngoài cửa sổ hiển thị. Nằm trong được hiển thị, nằm ngoài loại bỏ.
Việc loại từng điểm ảnh của đối tượng thường chậm nhất là khi đối
tượng mà phần lớn nằm ngoài cửa sổ hiển thị.
2. CÁC LOẠI XÉN TỈA 2.1 Xén tỉa điểm
Giả sử (x,y) là tọa độ của một điểm, vậy điểm đó được hiển thị khi thoả mãn: Xmin <= x <= Xmax Ymin <= y <= Ymax
2.2 Xén tỉa đoạn thẳng
Các thuật toán xén tỉa đoạn thẳng đều tập trung giải quyết hai vấn đề
chính nhằm tối ưu tốc độ thuật toán đó là: loại bỏ việc tìm giao điểm đối
với các đoạn thẳng chắc chắn không cắt cửa sổ (như nằm hoàn toàn
trong, nằm hoàn toàn ngoài), và với đoạn thẳng có khả năng cắt cửa sổ,
cần phải tìm cách hạn chế số lần tìm giao điểm với các biên không cần thiết.
Tiến trình, giải thuật kiểm tra chấp nhận các đoạn thẳng nằm trong
và loại bỏ các đoạn thẳng nằm ngoài dựa trên 2 điểm đầu cuối. Lý do:
– Không kiểm tra mọi điểm trên đoạn thẳng. lOMoARcPSD| 36067889
– Hầu hết các đoạn thẳng với 1 màn hình hiển thị đều được chấp nhậnhoặc loại bỏ.
– Rất ít các đoạn thẳng cắt cửa sổ hiển thị. 2.3 Xén tỉa đa giác
Hình 2.3.1 Các loại đa giác
Đa giác lồi: là đa giác có đường thẳng nối bất ký 2 điểm bên trong
nào của đa giác đều nằm trọn trong đa giác. Đa giác không lồi là đa giác lõm.
Theo quy ước: một đa giác với các đỉnh P1, .....,Pn (các cạnh là Pi-
1Pi và PnP1) được gọi là theo hướng dương nếu các hình theo thứ tự đã
cho tạo thành một mạch ngược chiều kim đồng hồ.
Nếu bàn tay trái của một người dọc theo bất kỳ cạnh Pi-1Pi hoặc
PNP1 cũng chỉ về bên trong đa giác.
Hình 2.3.2 Quy tắc tìm hướng dương của một đa giác hướng Khảo sát
một điểm so với một đường thẳng:
Có điểm A(x1,y1), B(x2,y2) và P(x,y) lOMoARcPSD| 36067889
Theo định nghĩa thì tích của hai vectơ (ABxAP) chỉ theo hướng của
vectơ K⊥ với mặt phẳng (XoY). Có: AB=(x2-x1)i + (y2-y1)j AP=(x-x1)i + (y-y1)j
Vậy ABxAP=[ (x2-x1).(y-y1) – (y2-y1).(x-x1) ].K Do
đó hướng được xác định như sau:
C = (x2 - x1)(y - y1) - (y2 - y1)(x - x1)
Nếu C dương thì P nằm bên trái AB. Nếu C
âm thì P nằm bên phải AB.
3. CÁC GIẢI THUẬT XÉN TỈA
3.1 Xén tỉa đoạn thẳng bằng thuật toán Cohen-Sutherland Cho đoạn thẳng P
thuật toán cần tìm ra đoạn thẳng giao giữa 1P2,
P1P2 và cửa sổ Window được hiển thị như hình vẽ (Input: Đoạn thẳng
P1P2; Output: P1P2 giao W(Wl ,Wr ,Wb ,Wt )).
Mặt phẳng được chia làm 5 vùng: lOMoARcPSD| 36067889 lOMoARcPSD| 36067889 Lúc này, ta có:
+ Input: Đoạn thẳng P1P2
+ Output: P1P2 giao W(Wl ,Wr ,Wb ,Wt )
Bước 1: gán mã vùng 4 bit cho mỗi điểm cuối của đoạn thẳng. C1 là mã vùng của P1 lOMoARcPSD| 36067889 C2 là mã vùng của P2
Bước 2: quá trình kiểm tra vị trí của đoạn thẳng so với cửa sổ.
Trường hợp 1 : Đoạn thẳng nằm ở vùng bên trong lOMoARcPSD| 36067889
Trường hợp 2 : Đoạn thẳng thuộc các vùng bên ngoài
Trường hợp 3 : Đoạn thẳng cắt cửa sổ lOMoARcPSD| 36067889
3.2 Xén tỉa đoạn thẳng bằng thuật toán Lyangbarsky
Thuật toán xén tỉa đoạn thẳng LyaBarsky tập trung giải quyết
hai vấn đề chính nhằm tối ưu tốc độ thuật toán đó là: loại bỏ việc
tìm giao điểm đối với các đoạn thẳng chắc chắn không cắt cửa sổ
(như nằm hoàn toàn trong, nằm hoàn toàn ngoài), và với đoạn thẳng
có khả năng cắt cửa sổ, cần phải tìm cách hạn chế số lần tìm giao
điểm với các biên không cần thiết
Thuật toán LyaBarsky thì tuy dựa vào phương trình tham số
của đoạn thẳng để lập luận nhưng thực chất là dựa trên việc xét các
giao điểm có thể có giữa đoạn thẳng kéo dài với các biên của cửa sổ lOMoARcPSD| 36067889
(cũng được kéo dài). Các giao điểm này tương ứng với các giá trị rk
= qk/pk. Cả hai thuật toán này đều có thể được mở rộng cho việc
xén hình trong đồ hoạ 3D.
Bước 1 : Xác định tọa tộ 2 điểm đầu và cuối của đoạn thẳng đang xét (x1; y1), (x2; y2) Bước 2: Tính x = x2-x1 • y = y2- y1
• p1 = - x, p2 = x, p3 = - y, p4 = y
• q1 = x1 – xmin, q2 = xmax – x1, q3 = y-ymin, q4 = ymax-y Bước 3: Xét :
• Nếu Pk = 0: điều đó tương đương với việc đoạn thẳng đang xét
song song với cạnh thứ k của hình chữ nhật clipping.
a. Nếu qk < 0 đoạn thẳng nằm ngoài cửa sổ (hệ bất phươngtrình trên vô nghiệm)
b. Nếu qk >= 0 thì đoạn thẳng nằm trong hoặc nằm trên cạnhcủa cửa sổ clipping.
• Nếu Pk 0: đoạn thẳng đang xét sẽ cắt cạnh k tương ứng của cửa
sổ clipping tại vị trí trên đoạn thẳng uk = qk/Pk (k = 1,2,3,4) a. Pk
< 0 => Tìm u0 = max({0} {uk : uk = qk/pk, pk<0})
b. Pk > 0 => Tìm u1 = min({1} {uk : uk = qk/pk, pk>0})
Nếu u0 > u1 => Đoạn thẳng nằm ngoài cửa sổ
Nếu u0 < u1 => đọa thẳng nằm trong cửa sổ
Thay tọa đồ u0, u1 vào phương trình để tìm tọa độ mới :
a. Với điểm đầu : x = x1 + x*u0, y = y1 + x*u0
b. Với điểm cuối : x = x1 + x*u1, y = y1 + x*u1
3.3 Xén tỉa đa giác bằng thuật toán Sutherland-Hogman
Cho đa giác P bất kì có n cạnh, thuật toán cần tìm ra đa giác P
giao với cửa sổ Window (input: Đa giác P; output: P giao Window) lOMoARcPSD| 36067889
Mỗi cạnh mặt phẳng chia làm 2 phần: nửa mặt phẳng trong và nửa mặt phẳng ngoài.
Cửa sổ quan sát là giao của các nửa mặt phẳng trong của các cạnh. lOMoARcPSD| 36067889
Dùng từng cạnh của cửa sổ lần lượt xén đa giác ● Bước 1: Xén trái ● Bước 2: Xén phải
● Bước 3: Xén dưới ● Bước 4: Xén trên Lúc này ta có,
+ input: Đa giác IN = {P0, P1,.., Pn-1}
+ output: Đa giác OUT = IN giao W{Wl, Wr, Wb, Wt} lOMoARcPSD| 36067889 Bước 1: OUT = {} Bước 2: Lặp P: P0 … Pn-1
S là đỉnh kề trước của P
Trường hợp 1, P bên trong S bên trong
Trường hợp 2: P bên ngoài, S bên trong lOMoARcPSD| 36067889
Trường hợp 3: P bên ngoài, S bên ngoài
Trường hợp 4: P bên trong, S bên ngoài lOMoARcPSD| 36067889
Ta xét ví dụ minh họa sau để hiểu rõ thuật toán hơn.
VD: Xén đa giác ABCDEF vào vùng cửa sổ như hình: lOMoARcPSD| 36067889 lOMoARcPSD| 36067889
B. PHÂN TÍCH THIẾT KẾ VÀ DEMO
1. THIẾT KẾ GIAO DIỆN HIỂN THỊ 1.1Giao diện thanh chọn
Bao gồm 4 nút chọn (button) với các chức năng:
+ Nút Line : vẽ 1 đường thẳng với 2 điểm cho trước
+ Nút ViewPoint : vẽ một hình chữ nhật với 2 điểm cho trước
+ Nút Cut : Thực hiện xén tỉa hình vẽ
+ Nút Delete: Xóa các đối tượng có trong giao diện 1.2 Giao diện bảng vẽ
Là một khu vực hình vuông, nền đen với kích thước 400 x 400 lOMoARcPSD| 36067889
1.3Hướng dẫn sử dụng demo
- Để vẽ hình: ta chọn nút Line sau đó di chuyển chuột vào vùng giao
diện bảng vẽ, click chọn 2 điểm bất kỳ để vẽ 1 đường thẳng
- Tương tự như vậy ta cũng chọn sang nút ViewPoint và click chọn 2
điểm (điểm phải trên và điểm trái dưới hoặc điểm trái trên và điểm
phải dưới) ở trong vùng giao diện bản vẽ để vẽ ViewPoint.
- Để thực hiện thuật toán: chọn nút Cut để xén tỉa hình đã vẽ Chú ý:
Nếu như chưa vẽ ViewPoint mà thực hiện xén tỉa thì sẽ không hợp lệ,
hộp thông báo chưa vẽ ViewPoint sẽ hiển thị để nhắc nhở
- Chọn nút Delete để xóa và làm mới bảng vẽ.
2. CÀI ĐẶT THUẬT TOÁN
2.1Thuật toán Cohen-Sutherland lOMoARcPSD| 36067889 lOMoARcPSD| 36067889 lOMoARcPSD| 36067889 2.2Thuật toán Lyangbarsky lOMoARcPSD| 36067889 lOMoARcPSD| 36067889 lOMoARcPSD| 36067889
2.3Thuật toán Sutherland-Hodgman lOMoARcPSD| 36067889 3. DEMO
❖ Xén tỉa đoạn thẳng ⮚ Kết quả: lOMoARcPSD| 36067889 ❖ Xén tỉa đa giác ⮚ Kết quả lOMoARcPSD| 36067889 lOMoARcPSD| 36067889
TÀI LIỆU THAM KHẢO [1]
Hoàng Kiếm, Dương Anh Đức, Lê Đình Duy, Vũ Hải Quân. Giáo trình cơ sở Đồ hoạ
Máytính, NXB Giáo dục, 2000. [2]
Lê Tấn Hùng, Huỳnh Quyết Thắng. Kỹ thuật đồ hoạ máy tính, NXB khoa học và kỹ thuật,2002. [3]
Trịnh Thị Vân Anh. Bài giảng Kỹ thuật đồ họa, Học viện Công nghệ Bưu chính Viễnthông, 2020.