›
›

Giáo trình Đồ họa máy tính - Trường Đại học Hàng Hải

Download
BỘ GIAO THÔNG VẬN TẢI  
TRƢỜNG ĐẠI HỌC HÀNG HẢI  
BỘ MÔN: KHOA HỌC MÁY TÍNH  
KHOA: CÔNG NGHỆ THÔNG TIN  
BÀI GIẢNG  
ĐỒ HỌA MÁY TÍNH  
TÊN HỌC PHẦN  
: ĐỒ HỌA MÁY TÍNH  
: 17211  
MÃ HỌC PHẦN  
TRÌNH ĐỘ ĐÀO TẠO  
: ĐẠI HỌC CHÍNH QUY  
DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN  
HẢI PHÒNG - 2010  
MỤC LỤC  
NỘI DUNG  
STT  
TRANG  
CHƢƠNG 1  
GIỚI THIỆU ĐỒ HỌA MÁY TÍNH  
1
1
Giới thiệu về đồ họa máy tính  
1.1  
1.2  
1.2.1  
Tổng quan về một hệ đồ họa  
2
2
3
Hệ tọa độ thực, hệ tọa độ thiết bị và hệ tọa độ chuẩn  
Mô hình màu  
CÁC ĐỐI TƢỢNG ĐỒ HỌA CƠ BẢN  
Giới thiệu về các đối tượng đồ họa cơ sở  
Các đối tượng đồ họa cơ sở: điểm, đường, vùng tô, văn bản  
1.2.2  
CHƢƠNG 2  
4
4
2.1  
2.1.1  
2.1.2  
2.2  
2.2.1  
2.2.2  
2.3  
4
4
Các thuộc tính của các đối tượng đồ họa cơ sở  
Các thuật toán vẽ điểm, đường  
Vẽ đường thẳng  
4
4
Vẽ đường tròn, elip  
7
Các thuật toán tô màu  
10  
10  
12  
13  
Thuật toán tô màu dựa theo dòng quét đơn giản  
Thuật toán tô màu dựa theo đường biên  
Bài tập áp dụng  
CÁC PHÉP BIẾN ĐỔI ĐỒ HỌA 2 CHIỀU  
Các phép biến đổi cơ sở  
Giới thiệu về phép biến đổi  
Phép tịnh tiến  
2.3.1  
2.3.2  
2.4  
CHƢƠNG 3  
3.1  
14  
14  
14  
14  
14  
15  
15  
15  
15  
16  
16  
16  
16  
16  
16  
17  
18  
18  
19  
20  
21  
22  
23  
24  
25  
3.1.1  
3.1.2  
3.1.3  
3.1.4  
3.2  
3.2.1  
3.2.2  
3.2.3  
3.3  
3.3.1  
3.3.2  
3.3.3  
3.4  
Phép biến đổi tỉ lệ  
Phép quay  
Kết hợp các phép biến đổi  
Kết hợp các phép tịnh tiến  
Kết hợp các phép biến đổi tỉ lệ  
Kết hợp các phép quay  
Một số phép biến đổi khác  
Phép biến dạng  
Phép đối xứng  
Tính chất của phép biến đổi affine  
Phép biến đổi giữa các hệ tọa độ  
Bài tập áp dụng  
3.5  
CHƢƠNG 4  
PHÉP QUAN SÁT 2 CHIỀU  
Cửa sổ và vùng quan sát  
Phép biến đổi từ cửa sổ - đến – vùng quan sát  
Phép cắt xén hai chiều  
4.1  
4.2  
4.3  
4.3.1  
4.3.2  
4.3.3  
4.4  
Giải thuật Cohen – Sutherland  
Giải thuật chia tại trung điểm  
Giải thuật Liang – Barsky  
Bài tập áp dụng  
CHƢƠNG 5  
ĐỒ HỌA 3  
CHIỀU  
5.1  
5.1.1  
5.1.2  
5.2  
5.2.1  
5.2.2  
Tổng quan về đồ họa ba chiều  
Quy trình hiển thị đồ họa ba chiều  
Mô hình hóa đối tượng  
Biểu diễn đối tượng ba chiều  
Biểu diễn mặt đa giác  
Đường cong và mặt cong , đường cong và mặt cong Bezier, B-  
Spline  
25  
25  
25  
26  
27  
27  
Các phép biến đổi hình học ba chiều  
Phép biến đổi tỷ lệ  
Phép biến dạng  
Phép tịnh tiến  
Phép quay  
Bài tập áp dụng  
QUAN SÁT 3 CHIỀU  
Các phép chiếu  
Phép chiếu song song  
Phép chiếu phối cảnh  
Điểm tụ  
29  
30  
30  
31  
31  
31  
33  
33  
34  
37  
38  
39  
44  
5.3  
5.3.1  
5.3.2  
5.3.3  
5.3.4  
5.4  
CHƢƠNG 6  
6.1  
6.1.1  
6.1.2  
6.2  
6.3  
6.4  
Loại bỏ mặt khuất  
Bài tập áp dụng  
Tên học phần: Đồ họa máy tính  
Loại học phần: 4  
Khoa phụ trách: CNTT  
Tổng số TC: 4  
Đồ án môn học  
Bộ môn phụ trách giảng dạy: Khoa học Máy tính  
Mã học phần: 17211  
TS tiết Lý thuyết Thực hành/Xemina Tự học  
Bài tập lớn  
75  
45  
15  
0
15  
0
Điều kiện tiên quyết:  
Sinh viên phải học xong các học phần sau mới được đăng ký học phần này:  
Toán cao cấp, Toán rời rạc, Kỹ thuật lập trình, Tin học đại cương, Cấu trúc dữ liệu, Giải  
thuật  
Mục tiêu của học phần:  
Cung cấp cho sinh viên kiến thức và rèn luyện kỹ năng lập trình đồ họa máy tính đồ họa  
máy tính, các phương pháp dựng hình, xử lý hình ảnh cơ bản trong đồ họa.  
Nội dung chủ yếu  
- Những vấn đề cơ bản về đồ họa máy tính  
- Các thuật toán cơ bản trong đồ họa máy tính.  
- Đồ họa 2D/3D  
- Các phương pháp biến hình  
- Các phương pháp tạo bóng  
Nội dung chi tiết của học phần:  
PHÂN PHỐI SỐ TIẾT  
TÊN CHƢƠNG MỤC  
Chƣơng I : Giới thiệu đồ họa máy tính.  
1.1. Giới thiệu về đồ họa máy tính  
TS  
LT TH/Xemina  
BT  
KT  
3
3
0
1.2. Tổng quan về một hệ đồ họa  
16  
9
3
3
1
Chƣơng II : Các đối tƣợng đồ họa cơ bản  
2.1. Giới thiệu về các đối tượng đồ họa cơ sở  
2.1.1. Các đối tượng đồ họa cơ sở : điểm,  
PHÂN PHỐI SỐ TIẾT  
LT TH/Xemina BT  
TÊN CHƢƠNG MỤC  
đường, vùng tô, văn bản,...  
TS  
KT  
2.1.2. Các thuộc tính của các đối tượng đồ họa  
cơ sở  
2.2. Các thuật toán vẽ điểm, đường  
2.2.1. Vẽ đường thẳng  
2.2.2. Vẽ đường tròn, ellipse  
2.3. Các thuật toán tô màu  
2.3.1. Thuật toán tô màu dựa theo đường biên  
2.3.2. Thuật toán tô màu theo dòng quét  
2.4. Bài tập áp dụng  
10  
8
2
Chƣơng III: Các phép biến đổi đồ họa 2 chiều.  
3.1. Các phép biến đổi cơ sở  
3.1.1 Giới thiệu về phép biến đổi, biểu diễn  
ma trận của phép biến đổi, phép biến đổi affine  
3.1.2. Phép tịnh tiến  
3.1.3. Phép biến đổi tỉ lệ  
3.1.4. Phép quay quanh gốc tọa độ  
3.1.5. Biểu diễn ma trận của các phép biến  
đổi. Hệ tọa độ thuần nhất  
3.2. Kết hợp các phép biến đổi  
3.2.1. Kết hợp hai hay nhiều phép tịnh tiến,  
phép biến đổi tỉ lệ, phép quay.  
3.2.2. Phép biến đổi tỉ lệ với tâm tỉ lệ bất kì.  
3.2.3. Phép quay quanh tâm là một điểm bất  
kì.  
PHÂN PHỐI SỐ TIẾT  
TÊN CHƢƠNG MỤC  
3.3. Một số phép biến đổi khác  
TS  
LT TH/Xemina  
BT  
KT  
3.3.1. Phép biến dạng  
3.3.2. Phép đối xứng  
3.3.3. Tính chất của phép biến đổi affine  
3.4. Phép biến đổi giữa các hệ tọa độ  
3.5. Bài tập áp dụng  
12  
9
2
1
Chƣơng IV: Phép quan sát hai chiều  
4.1. Cửa sổ, Vùng quan sát  
4.2. Phép biến đổi từ cửa sổ - đến – vùng quan sát  
4.3. Phép cắt xén 2 chiều  
4.3.1 Giải thuật Cohen – Suntherland  
4.3.2 Giải thuật chia trung điểm  
4.3.3 Giải thuật Liang – Barsky  
4.4. Bài tập áp dụng  
22  
10  
5
6
1
Chƣơng V: Đồ họa ba chiều  
5.1. Tổng quan về đồ họa ba chiều  
5.1.1. Quy trình hiển thị đồ họa ba chiều  
5.1.2. Mô hình hóa đối tượng  
5.2. Biểu diễn đối tượng ba chiều  
5.2.1. Biểu diễn mặt đa giác  
5.2.2. Đường cong và mặt cong , đường cong và  
mặt cong Bezier, B-Spline  
5.3. Các phép biến đổi hình học ba chiều  
5.3.1. Phép tịnh tiến  
5.3.2. Phép quay quanh một trục  
PHÂN PHỐI SỐ TIẾT  
TÊN CHƢƠNG MỤC  
5.3.3. Phép biến đổi tỉ lệ  
TS  
LT TH/Xemina  
BT  
KT  
5.3.4. Kết hợp các phép biến đổi  
5.3.5. Các phép chuyển đổi giữa các hệ tọa độ  
5.4. Bài tập áp dụng  
15  
6
3
6
Chƣơng VI: Quan sát ba chiều  
6.1. Các phép chiếu  
6.2. Điểm tụ  
6.3. Loại bỏ mặt khuất  
6.4. Bài tập áp dụng  
Nhiệm vụ của sinh viên :  
Tham dự các buổi thuyết trình của giáo viên, tự học, tự làm bài tập do giáo viên giao, tham  
dự các bài kiểm tra định kỳ và cuối kỳ.  
Tài liệu học tập :  
Đặng Văn Đức. Kỹ thuật đồ họa máy tính. Viện Công nghệ thông tin. 2002.  
-
-
Donald Hearn, M. Pauline Baker, Computer Graphics, Prentice-Hall Inc., Englewood  
Cliffs, New Jersey, 1986.  
-
F.S.Hill, Computer graphics, 1990  
Hình thức và tiêu chuẩn đánh giá sinh viên:  
-
-
Hình thức thi cuối kỳ : Thi viết.  
Sinh viên phải đảm bảo các điều kiện theo Quy chế của Nhà trường và của Bộ  
Thang điểm: Thang điểm chữ A, B, C, D, F  
Điểm đánh giá học phần: Z = 0,4X + 0,6Y.  
Bài giảng này là tài liệu chính thức và thống nhất của Bộ môn Khoa học máy tính, Khoa Công  
nghệ thông tin và được dùng để giảng dạy cho sinh viên.  
Ngày phê duyệt:  
/
/2010  
Trưởng Bộ môn: (ký và ghi rõ họ tên)  
CHƢƠNG I GIỚI THIỆU ĐỒ HỌA MÁY TÍNH  
1.1 Giới thiệu về đồ họa máy tính  
Ngày nay, đồ họa máy tính được ứng dụng rộng rãi trong ngành công nghệ thông tin. Khó mà tìm  
được một ứng dụng thương mại của công nghệ thông tin không sử dụng một thành phần nào đó  
của hệ đồ họa máy tính. Đồ họa máy tính ở vị trí quan trọng trong lĩnh vực thiết kế và giao tiếp kỹ  
thuật. Nó là cơ sở để chuyển đổi các giải pháp tính toán số sang thể hiện hình ảnh tự nhiên cho  
thiết kế kỹ thuật hay muốn sáng tỏ một vấn đề phức tạp. Đồ họa máy tính biểu diễn được hình ảnh  
đối tượng, quan hệ, dữ liệu, vị trí … Đồ họa máy tính còn có chức năng mô tả kích thước của đối  
tượng, phân tích dữ liệu. Trong những thập niên cuối thế kỷ 20, sự phát triển mạnh của những hệ  
đồ họa như CAD/CAM đã trở thành chuẩn công nghiệp và trường học.  
1.2 Tổng quan về một hệ đồ họa  
Mục tiêu của đồ họa máy tính có chức năng tạo ra và thao tác các hình ảnh đồ họa, nên nó phải có  
khả năng tạo ra và hiệu chỉnh các hình ảnh bằng các tương tác và đáp ứng. Các ứng dụng đồ họa  
đưa ra các chỉ dẫn thuật ngữ theo yêu cầu đồ họa người dùng. Thư viện đồ họa thực hiện tương  
tác, làm cầu nối cho giao tiếp giữa người dùng và các thiết bị vật lý đơn giản đi.  
Hình 1.1 Hệ thống đồ họa  
Một trong các yêu cầu chính của một hệ thống đồ họa là các ứng dụng, áp dụng cho nhiều hệ thiết  
bị vật lý, phải được phát triển không phụ thuộc vào phần cúng. Để có được điều đó, phải có tiêu  
chuẩn hóa cho môi trường đồ họa ở mức chức năng, bằng việc cung cấp sự độc lập thiết bị và  
ngôn ngữ lập trình.  
Sự độc lập với thiết bị cho phép các chương trình ứng dụng đồ họa chạy trên các dạng phần cứng  
khác nhau. Nó được thực hiện thông qua thiết bị nhập xuất logic cung cấp cho phần mềm ứng  
dụng thông qua thư viện đồ họa và ánh xạ thiết bị vật lý cụ thể.  
Cho tới nay, có những tiêu chuẩn đồ họa đã được phát triển trong nhiều năm, bao gồm:  
GKS(Graphics Kernel System – 1985), được phát triển riêng cho các thiết bị nhập xuất 2 chiều.  
GKS-3D bổ sung thêm khả năng lập trình 3 chiều. PHIGS (Programmer’s Hierarchical Graphics  
System – 1984) hay PHIGS+ bao gồm khả năng lập trình không gian , tạo thành thao tác dữ liệu  
đồ họa phức tạp …  
Các tiêu chuẩn đồ họa thực tế là kết quả của việc chấp nhận trong công nghiệp các giao diện đặc  
trưng, được đề xuất bởi nhiều công ty và không nêu ra trong các tiêu chuẩn chính thức. Được  
nhắc đến trong số này là hệ X-Windows, cung cấp một loạt các chức năng nhập và thao tác đồ  
họa 2 chiều. Sự mở rộng được bắt đầu vào giữa những năm 80 là hệ X-Windows 3 chiều.  
Để đảm bảo sự linh hoạt, các tiêu chuẩn đồ họa thiết lập cho ứng dụng các thay đổi tối thiểu, cho  
1
phép nó định địa chỉ các thiết bị nhập xuất khác nhau. Khởi đầu, người lập trình tạo ra một hệ  
thống tọa độ mô hình, mô tả đối tượng gọi là hệ thống tọa độ thực. Tiếp theo, là hệ tọa độ tiêu  
chuẩn và hệ tọa độ thiết bị. Chương trình ứng dụng sẽ giao tiếp với hệ tọa độ chuẩn theo cách  
thức phù hợp, không quan tâm đến thiết bị xuất được dùng. Do đó, tạo ra sự độc lập với thiết bị  
trong việc tạo ra hình ảnh của đối tượng.  
1.2.1 Hệ tọa độ thực, hệ tọa độ thiết bị và hệ tọa độ chuẩn  
Trong lĩnh vực kỹ thuật đồ họa, chúng ta phải hiểu được rằng thực chất của đồ họa là làm thế nào  
để có thể mô tả và biến đổi được các đối tượng trong thế giới thực trên máy tính. Bởi vì, các  
đối tượng trong thế giới thực được mô tả bằng tọa độ thực. Trong khi đó, hệ tọa độ thiết bị lại sử  
dụng hệ tọa độ nguyên để hiển thị các hình ảnh. Đây chính là vấn đề cơ bản cần giải quyết.  
Ngoài ra, còn có một khó khăn khác là với các thiết bị khác nhau thì có các định nghĩa khác nhau.  
Do đó, cần có một phương pháp chuyển đổi tương ứng giữa các hệ tọa độ và đối tượng phải được  
định nghĩa bởi các thành phần đơn giản như thế nào để có thể mô tả gần đúng với hình ảnh thực  
bên ngoài.  
a.Hệ tọa độ thực:  
Một trong những hệ tọa độ thực thường được dùng để mô tả các đối tượng trong thế giới thực là hệ  
tọa độ Descartes. Với hệ tọa độ này, mỗi điểm P được biểu diễn bằng một cặp tọa độ (xp,yp) với  
xp, yp ∈R (xem hình 1.1).  
Hình 2.1 Hệ tọa độ thực  
. Ox : gọi là trục hoành; Oy  
: gọi là trục tung.  
. x : hoành độ điểm P; y  
p
p
: tung độ điểm P.  
b. Hệ tọa độ thiết bị:  
Hệ tọa độ thiết bị (device coordinates) được dùng cho một thiết bị xuất cụ thể nào đó, ví dụ như  
máy in, màn hình,.. Trong hệ tọa độ thiết bị thì các điểm cũng được mô tả bởi cặp tọa độ (x,y).  
Tuy nhiên, khác với hệ tọa độ thực là x, y ∈ N. Điều này có nghĩa là các điểm trong hệ tọa độ  
thực được định nghĩa liên tục, còn các điểm trong hệ tọa độ thiết bị là rời rạc. Ngoài ra, các tọa độ  
x, y của hệ tọa độ thiết bị chỉ biểu diễn được trong một giới hạn nào đó của N.  
c. Hệ tọa độ thiết bị chuẩn:  
Do cách định nghĩa các hệ tọa độ thiết bị khác nhau nên một hình ảnh hiển thị được trên thiết  
bị này là chính xác thì chưa chắc hiển thị chính xác trên thíết bị khác. Người ta xây dựng một hệ  
tọa độ thiết bị chuẩn đại diện chung cho tất cả các thiết bị để có thể mô tả các hình ảnh mà  
không phụ thuộc vào bất kỳ thiết bị nào. Trong hệ tọa độ chuẩn, các tọa độ x, y sẽ được gán các  
giá trị trong đoạn từ [0,1]. Như vậy, vùng không gian của hệ tọa độ chuẩn chính là hình vuông  
đơn vị có góc trái dưới (0, 0) và góc phải trên là (1, 1).  
2
1.2.2 Mô hình màu  
Màu sắc được sử dụng trong các ứng dụng đồ họa máy tính để giúp người dùng hiểu rõ về đối tượng  
hình học. Các màn hình đồ họa dựa sử dụng các màu sắc chromatic. Chúng dựa trên lý thuyết về bộ não  
người là màu sắc ánh sáng được tiếp nhận như sự phối hợp từ 3 màu là đỏ (red), xanh lá cây (green), và  
xanh dương (blue). Nói chung, màu được mô tả bằng 3 thuộc tính là màu sắc (hue), độ bão hòa  
(saturation), và độ sáng (brightness); chúng xác định vị trí trong quang phổ màu, độ tinh khiết và cường  
độ sáng. Có hàng loạt phương pháp được tạo các mô hình màu trong các ứng dụng đồ họa. Trong phần  
này chỉ đưa ra những mô hình màu tiêu biểu hơn cả, giúp tìm hiểu các ứng dụng đã lựa chọn màu sắc  
thích hợp như thế nào.  
a. RGB (Red - Green - Blue):  
Mô hình màu RGB mô tả màu  
sắc bằng 3 thành phần chính  
là Red - Green và Blue. Mô  
hình này được xem như một  
khối lập phương 3 chiều với  
màu red là trục x, màu Green  
là truc y, và màu Blue là trục  
z. Mỗi màu trong mô hình  
này được xác định bởi 3 thành  
phần R, G, B. Ứng với các tổ  
hợp khác nhau của 3 màu này  
sẽ cho ta một màu mới .  
Trong hình lập phương trên,  
mỗi màu gốc (R,G,B) có các  
gốc đối diện là các màu bù với nó. Hai màu được gọi là bù nhau khi kết hợp hai màu này lại với  
nhau ra màu trắng. Ví dụ : Green - Magenta, Red - Cyan, Blue - Yellow.  
b. CMY (Cyan - Magenta - Yellow):  
Tương tự như mô hình màu RGB nhưng 3 thành phần chính là Cyan - Magenta - Yellow. Do đó,  
tọa độ các màu trong mô hình CMY trái ngược với mô hình RGB. Ví dụ : màu White có các  
thành phần là (0,0,0), màu Black (1,1,1), màu Cyan (1,0,0),....  
c. HSV (Hue - Saturation - Value ):  
Thực chất của mô hình này là sự biến đổi của mô hình RGB. Mô hình HSV được mô tả bằng lệnh  
lập phương RGB quay trên đỉnh Black. H (Hue) là góc quay trục V (value) qua 2 đỉnh Black và  
White. Các giá trị biến thiên của H, S, V như sau: (Hue) chỉ sắc thái có giá trị từ 00 - 3600 . S  
(Saturation) chỉ độ bão hoà. V (Value) có giá trị từ 0 - 1. Các màu đạt giá trị bão hòa khi s = 1 và  
v = 1.  
3
CHƢƠNG II CÁC ĐỐI TƢỢNG ĐỒ HỌA CƠ BẢN  
2.1 Giới thiệu về các đối tƣợng đồ họa cơ sở  
Kỹ thuật đồ họa liên quan đến tin học và toán học bởi vì hầu hết các giải thuật vẽ, tô cùng các phép  
biến hình đều được xây dựng dựa trên nền tảng của hình học không gian hai chiều và ba chiều.  
Trong chương này, chúng ta giới thiệu các thuật toán vẽ và tô các đường cơ bản như đường thẳng,  
đa giác, đường tròn, ellipse. Các thuật toán này giúp cho sinh viên hiểu được quá trình vẽ và tô một  
đối tượng hình học cơ sở như thế nào.  
2.1.1 Các đối tượng đồ họa cơ sở  
- Điểm: điểm là thành phần cơ sở được định nghĩa trong một hệ tọa độ, đối với hệ tọa độ 2 chiều  
mỗi điểm được xác định bởi hoành độ và tung độ. Ngoài thông tin tọa độ, điểm còn có thông tin  
màu sắc.  
- Đoạn thẳng, đường thẳng: đường thẳng xác định qua 2 điểm, đoạn thẳng bị giới hạn bởi 2 điểm  
đầu và cuối. Phương trình đường thẳng được xác định qua 2 điểm P(x1, y1) và Q(x2, y2) như sau:  
x x1 x2 x1  
y y1 y2 y1  
Hay ở dạng phương trình đoạn chắn y = mx + b, trong đó: Dx = x2 –x1 , Dy = y2 –y1 ,  
Dy  
m   
Dx  
Hay ở dạng tổng quát: Ax + By + C = 0 , trong đó: A = y2- y1, B = x1 – x2, C = x2y1 – x1y2  
- Đường gấp khúc: là tập các đoạn thẳng nối với nhau một cách tuần tự, các đoạn không nhất thiết  
phải tạo thành hình khép kín và có thể cắt nhau. Giao của hai đoạn thẳng là đỉnh, đỉnh và đỉnh cuối  
của đa giác trùng nhau.  
- Vùng tô: bao gồm đường biên và vùng bên trong, đường biên là đường khép kín như đa giác  
lồi.  
- Ký tự, chuỗi ký tự: Ký tự cho phép hiển thị thông tin theo ngôn ngữ nào đó.  
2.1.2 Các thuộc tính của các đối tượng đồ họa cơ sở  
- Điểm có thuốc tính màu sắc.  
- Đoạn thẳng, đường thẳng có thuộc tính màu sắc, độ rộng, kiểu nét.  
- Vùng tô có thuộc tính của đường thẳng, và thuộc tính riêng là mầu tô và mẫu tô.  
- Ký tự có thuộc tính màu sắc, kiểu chữ, cỡ chữ, khoảng cách giữa các ký tự, hướng  
hiển thị ký tự...  
2.2 Các thuật toán vẽ điểm, đƣờng  
2.2.1 Thuật toán vẽ đường thẳng  
Xét đoạn thẳng có hệ số góc 0<m<=1 và Δx>0. Với các đoạn thẳng dạng này, nếu (xi, yi) là điểm  
đã được xác định ở bước thứ i thì điểm kế tiếp (xi+1, yi+1) ở bước thứ i+1 sẽ là một trong hai điểm  
sau:  
4
x x  
i1  
i
y
i
yi   
yi1  
Vấn đề đặt ra là chọn điểm vẽ như thế nào để đường thẳng được vẽ gần với đường thẳng muốn vẽ  
nhất và đạt được tối ưu hóa về mặt tốc độ ?  
Thuật toán DDA  
Là thuật toán tính toán các điểm vẽ dọc theo đường thẳng dựa vào hệ số góc của phương trình  
Δy  
đường thẳng y = mx+b. Trong đó: m   
,Δy yi1 yi ,Δx xi1 xi Nhận thấy tọa độ của  
Δx  
điểm x sẽ tăng 1 đơn vị trên mỗi điểm vẽ, còn việc quyết định chọn y  
là y +1 hay y sẽ phụ  
i i  
i +1  
thuộc vào giá trị sau khi làm tròn của tung độ y. Tuy nhiên, nếu tính trực tiếp giá trị thực của y ở  
mỗi bước từ phương trình y = mx+b thì cần một phép toán nhân và một phép toán cộng số thực: y  
i
= mx  
+ b = m(x + 1) + b = mx + b + m  
i i  
+1  
i +1  
Để cải thiện tốc độ, người ta khử phép nhân trên số thực. Ta có:  
yi = mxi + b ⇒ yi +1 = yi + m → int(yi +1)  
(2-1)  
Có 2 khả năng:  
0<m<=1: xi +1 = xi + 1, yi +1 = yi + m→ int(yi +1)  
(2-2)  
m>1:  
xi +1 = xi + 1/m → int(xi+1), yi +1 = yi + 1  
Hai trường hợp này dùng để vẽ một điểm bắt đầu từ bên trái đến điểm cuối cùng bên phải của  
đường thẳng (xem hình 1.1). Nếu điểm bắt đầu từ bên phải đến điểm cuối cùng bên trái thì xét  
ngược lại :  
0<m<=1: xi +1 = xi - 1, yi +1 = yi - m → int(yi +1)  
(2-3)  
m>1:  
xi +1 = xi - 1/m → int(xi+1), yi  
+1 = yi - 1  
Hình 2.1 Dạng đường thẳng tương ứng 2 khả  
năng của m.  
Tương tự, có thể tính toán các điểm vẽ cho  
trường hợp m<0: khi |m|<=1 hoặc |m|>1 (sinh viên tự tìm hiểu thêm).  
5
Thuật toán Bresenham  
Hình 2.2 Dạng đường thẳng  
nếu 0<m<=1  
Gọi (x +1,y  
) là điểm thuộc đoạn thẳng (xem hình 1.2). Ta có y = m(x +1) + b  
i +1 i  
i
Đặt  
d1 = y  
– y và d2 = (y +1) - y  
i +1  
i +1  
i
i
Việc chọn điểm (x  
, y  
) là P1 hay P2 phụ thuộc vào việc so sánh d1 và d2  
= y  
i +1 i +1  
Nếu d1- d2<0 : chọn điểm P1, tức là y  
i +1  
i
Nếu d1- d2 ≥0 : chọn điểm P2, tức là y  
= y +1  
i
i +1  
Ta có : d1 – d2 = 2yi+1 – 2yi – 1 = 2m(xi+1) + 2b – 2yi – 1  
(2-4)  
Δy  
x [ 2 (xi 1) 2b 2yi 1]  
Δx  
⇒ P = Δx (d1 – d2) = Δx[2m(x +1) + 2b - 2y - 1] =  
i
i
i
= 2Δy(xi+1) - 2Δx.yi + Δx(2b – 1) = 2Δy.xi - 2Δx.yi + 2Δy + Δx(2b - 1)  
Vậy C = 2Δy + Δx(2b - 1) = Const ⇒ Pi = 2Δy.xi - 2Δx.yi + C  
(2-5)  
Nhận xét rằng nếu tại bước thứ i ta xác định được dấu của Pi thì xem như ta xác định được điểm  
cần chọn ở bước (i+1). Ta có :  
Pi +1 - Pi = (2Δy.xi+1 - 2Δx.yi+1 + C) - (2Δy.xi - 2Δx.yi + C )  
⇔ Pi +1 = Pi + 2Δy - 2Δx ( yi+1 - yi )  
Nếu Pi < 0 : chọn điểm P1, tức là yi +1= yi và Pi +1 = Pi + 2Δy  
Nếu Pi ≥ 0 : chọn điểm P2, tức là yi +1= yi +1 và Pi +1 = Pi + 2Δy - 2Δx (2-6)  
Giá trị P0 được tính từ điểm vẽ đầu tiên (xo, yo) theo công thức: Po = 2Δy.xo - 2Δx.yo + C  
Δy  
Do (xo ,yo ) là điểm nguyên thuộc về đoạn thẳng nên ta có: yo mx o b   
xo b  
Δx  
6
Thay yo vào phương trình trên ta được: Po = 2Δy - Δx  
Nhận xét:  
Thuật toán Bresenham chỉ thao tác trên số nguyên và chỉ tính toán trên phép cộng và phép nhân 2.  
Điều này là một cải tiến làm tăng tốc độ đáng kể so với thuật toán DDA. Ý tưởng chính của thuật  
toán này là ở chổ xét dấu P để quyết định điểm kế tiếp, và sử dụng công thức truy hồi P  
-
i
i +1  
P
để tính P bằng các phép toán đơn giản trên số nguyên. Tuy nhiên, việc xây dựng trường hợp  
i
i
tổng quát cho thuật toán Bresenham có phức tạp hơn thuật toán DDA.  
2.2.2 Thuật toán vẽ đƣờng tròn, elip  
Trong hệ tọa độ Descartes, phương trình đường tròn bán kính R có dạng:  
tâm O(0,0) : x2 + y2 = R2 ;  
tâm C(xc,yc):  
(x - xc )2 + (y - yc )2 = R2  
(2-7)  
x x Rcosθ  
c
Trong hệ tọa độ cực :  
, θ[0, 2]  
y yc Rsinθ  
Do tính đối xứng của đường  
tròn C, nên ta chỉ cần vẽ 1/8  
cung tròn, sau đó lấy đối xứng  
qua 2 trục tọa độ và 2 đường  
phân giác thì ta vẽ được cả  
đường tròn.  
Hình 2.3 Đường tròn với các  
điểm đối xứng.  
Thuật toán xét trung điểm  
Do tính đối xứng của đường tròn nên ta chỉ cần vẽ 1/8 cung tròn, sau đó lấy đối xứng là vẽ được  
cả đường tròn. Thuật toán trung điểm đưa ra cách chọn y là y hay y -1 bằng cách so sánh  
i+1  
i
i
điểm Q(x ,y) với điểm giữa là trung điểm (Midpoint) của S1 và S2. Chọn điểm bắt đầu để vẽ  
i+1  
thứ i (xem hình 1.4), thì điểm (x  
,
là (0,R). Giả sử (x , y ) là điểm nguyên đã tìm được ở bước  
i+1  
i i  
) ở bước i+1 là sự lựa chọn giữa S1 và S2.  
y
i+1  
7
x
xi 1  
i1  
y 1  
i
yi1  
yi  
Hình 2.4 Đường tròn với  
điểm Q(x +1, y) và trung  
i
điểm.  
2
2
2
Đặt F(x,y) = x + y - R , ta có :  
F(x,y) < 0 , nếu điểm (x,y) nằm trong đường tròn.  
F(x,y) = 0 , nếu điểm (x,y) nằm trên đường tròn.  
F(x,y) > 0 , nếu điểm (x,y) nằm ngoài đường tròn.  
Xét P = F(MidPoint) = F(x +1, y - 1/2). Ta có :  
i
i
i
Nếu P < 0 : điểm MidPoint nằm trong đường tròn. Khi đó, điểm Q gần với điểm  
S1  
i
hơn nên ta chọn y  
= y .  
i
i+1  
Nếu P >= 0 : điểm MidPoint nằm ngoài đường tròn. Khi đó, điểm Q gần với điểm S2  
i
hơn nên ta chọn y  
= y - 1.  
i
i+1  
Mặt khác : P  
- P = F(x  
+1, y - 1/2) - F(x + 1, y - 1/2)  
i+1 i i  
i+1  
i
i+1  
2
2
2
2
2
2
= [(x  
+1) + (y  
- 1/2) - R ] - [(x +1) + (y - 1/2) - R ]  
i i  
i+1  
i+1  
2
2
= 2x + 3 + ((y ) - (y ) ) - (y  
i+1 i+1  
- y )  
i
i
i
Nếu P < 0 : chọn y  
i+1  
= y . Khi đó P  
= P + 2x +3  
(2-8)  
Vậy:  
i
i
i+1  
i
i
P >= 0 : chọn y  
= y - 1. Khi đó P  
= P + 2x - 2y +5  
i i i  
Nếu  
i
i+1  
i
i+1  
P ứng với điểm ban đầu (x , y ) = (0,R) là: P = F(x + 1, y - 1/2) = F(1, R - 1/2) = 5/4 -R  
i
o
o
o
o
o
Thuật toán Bresenham  
8
Tương tự thuật toán vẽ đường thẳng Bresenham, các vị trí ứng với các tọa độ nguyên nằm  
trên đường tròn có thể tính được bằng cách xác định một trong hai pixel gần nhất với đường tròn  
hơn trong mỗi bước.  
Hình 2.5 Đường tròn với  
khoảng cách d1 và d2.  
2
2
2
2
2
2
2
2
2
d1 = (y ) - y = (y ) - (R - (x + 1) ) và d2 = y - (y - 1) = (R - (x + 1) ) - (y -  
Ta có:  
1)  
i
i
i
i
i
i
2
Đặt Pi = d1 - d2 , do đó Pi+1 = Pi + 4xi + 6 + 2((yi+1)2 - (yi)2 ) - 2(yi+1 - yi)  
Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi + 4xi +6  
(2-9)  
Nếu P >= 0 : chọn y  
i+1  
P ứng với điểm ban đầu (x , y ) = (0,R) là: P = 3 - 2R.  
o
= y - 1. Khi đó P  
= P + 4(x - y ) + 10  
i i i  
i
i
i+1  
o
o
o
Thuật toán vẽ elip  
Tương tự thuật toán vẽ đường tròn, sử dụng thuật toán Bresenham để vẽ, ta chỉ cần vẽ 1/4 ellipse,  
sau đó lấy đối xứng qua các trục tọa độ sẽ vẽ được toàn bộ ellipse.  
x2 y2  
1  
Xét ellipse có tâm O, các bán kính là a và b, phương trình là:  
a2 b2  
Chọn tọa độ pixel đầu tiên cần hiển thị là (x ,y ) = (0,b). Cần xác định pixel tiếp theo là  
i
i
(x  
,y ). Ta có :  
i+1 i+1  
x
xi 1  
i1  
yi  
yi1  
2
2
2
2
; d1 = (y ) - y  
;
d2 = y - (y - 1)  
i
i
yi 1  
2b 2  
a2  
P P 2((yi1 )2 (yi )2 ) 2(yi1 yi )   
(2x i 3)  
i1  
i
Đặt Pi = d1- d2, có  
2b2  
a2  
Nếu P < 0 : chọn y  
= y ,  
i
(2-10)  
(2x i 3)  
P P   
i
i+1  
i1  
i
2b 2  
a2  
P P   
(2x i 3)  
i1  
i
9
Nếu P >= 0 : chọn y  
i+1  
= y – 1,  
i
i
2b2  
a2  
Po ứng với điểm ban đầu (xo, yo) = (0, b) là:  
Po   
2b 1  
2.3 Thuật toán tô màu  
Tô màu một vùng là thay đổi màu sắc của các điểm vẽ nằm trong vùng cần tô. Một vùng tô  
thường đựơc xác định bởi một đường khép kín nào đó gọi là đường biên. Dạng đường biên đơn  
Dạng đường biên đơn giản thường gặp là đa giác. Việc tô màu thường  
giản thường gặp là đa giác.  
chia làm 2 công đoạn :  
- Xác định vị trí các điểm cần tô màu.  
- Quyết định tô các điểm trên bằng màu nào. Công đoạn này sẽ trở nên phức tạp khi ta cần tô  
theo một mẫu tô nào đó chứ không phải tô thuần một màu.  
Có 3 cách tiếp cận chính để tô màu. Đó là : tô màu theo từng điểm (có thể gọi là tô đơn giản), tô  
màu theo dòng quét và tô màu dựa theo đường biên. Chúng ta sẽ giới thiệu 2 loại thuật toán tô mầu  
đơn giản và tô màu đường biên. Thuật toán tô màu theo dòng quét thì sinh viên tự tìm hiểu.  
.1 Tô đơn giản  
2.3  
Thuật toán này bắt đầu từ việc xác định một điểm có thuộc vùng cần tô hay không ? Nếu đúng là  
điểm thuộc vùng cần tô thì sẽ tô với màu muốn tô.  
a. Tô đường tròn  
Để tô đường tròn thì ta tìm hình vuông nhỏ nhất ngoại tiếp đường tròn bằng cách xác định điểm  
trên bên trái (xc – r, yc – r) và điểm dưới bên phải (xc + r, yc + r) của hình vuông .  
Giải thuật giả mã như sau:  
i chạy từ xc-r đến xc+r  
j chạy từ yc-r đến yc+r  
tìm khoảng cách d giữa hai điểm (i,j) và tâm (xc,yc)  
nếu d<r thì tô điểm (i,j) với màu muốn tô  
Hình 2.6  
đường  
tròn nội tiếp hình  
vuông.  
10  
b.Tô đa giác  
Trước tiên, chúng ta giải quyết  
bài toán tìm hình chữ nhật nhỏ  
nhất có các cạnh song song với  
hai trục tọa độ chứa đa giác cần  
tô dưa vào hai tọa độ (xmin,  
ymin), (xmax, ymax).  
Hình 2.7 đa giác nội tiếp hình  
chữ nhật.  
Trong đó, xmin, ymin là hoành
nhất của các đỉnh của đa giác.
ymax (hoặc ngược lại). Xét điểm
Thông thường một điểm nằm tr
cắt biên của đa giác phải là một
một giao điểm phải được tính
thường ta chọn tia qua phải.  
Hình 2.8 Xét đa giác gồm 13  
đỉnh là P , P , ....., P , P  
o
1
12 o  
Gọi tung độ của đỉnh Pi là Pi.y . Nếu :  
P .y < Min ( P .y, P .y) hay P .y > Max ( P .y, P .y) thì P là đỉnh cực trị (  
i
i+1 i-1 i+1 i-1  
i
i
cực tiểu hay cực đại ).  
P .y < P .y < P .y hay P  
> P .y > P .y thì P là đỉnh đơn điệu.  
i+1  
i-1 i+1  
i
i-1  
i
i
P = P  
và  
P .y < Min ( P .y, P .y) hay P > Max ( P .y, P .y) thì  
i+2 i-1 i+2 i-1  
i
i+1  
i
i
đoạn [P ,P ] là đoạn cực trị ( cực tiểu hay cực đại ).  
i i+1  
P = P  
và P .y < P .y < P .y  
i-1 i+2  
hay P  
> P .y > P .y thì đoạn  
i+2  
i
i+1  
i
i-1  
i
[P ,P ] là đoạn đơn điệu.  
i i+1  
Thuật toán kiểm tra điểm có nằm trong đa giác  
- Với mỗi đỉnh của đa giác ta đánh dấu là 0 hay 1 theo qui ước như sau: nếu là đỉnh cực trị hay  
đoạn cực trị thì đánh số 0. Nếu là đỉnh đơn điệu hay đoạn đơn điệu thì đánh dấu 1.  
- Xét số  
11  
giao điểm của tia nữa đường thẳng từ P là điểm cần xét với biên của đa giác. Nếu số giao điểm là  
chẳn thì kết luận điểm không thuộc đa giác. Ngược lại, số giao điểm là lẻ thì điểm thuộc đa giác.  
2.3.2 Tô màu  
đường biên  
Bài toán đặt ra : Cần tô màu một vùng nếu biết được màu của đường biên vùng tô và một điểm  
nằm bên trong vùng tô.  
Ý tưởng : Bắt đầu từ một điểm nằm bên trong vùng tô, kiểm tra các điểm lân cận của nó đã được  
tô với màu muốn tô, hay điểm lân cận có màu trùng với màu biên không ? Nếu cả hai trường hợp  
đều không phải thì ta sẽ tô điểm đó với màu muốn tô. Quá trình  
không còn tô được nữa thì dừng.  
này được lặp lại cho đến khi  
Có 2 quan điểm về cách tô này. Đó là dùng 4 điểm lân cận (có thể gọi là 4 liên thông) hay 8 điểm  
lân cận (8 liên thông)  
Cài đặt minh họa thuật toán 4 liên thông  
Boundary_fill ( x,y, mauto, maubien :integer);  
mau_ht : integer;  
begin  
mau_ht:= getpixel(x, y);  
If (mau_ht <> mauto) and (mau_ht <> maubien) then  
begin  
putpixel(x,y,color);  
Boundary_fill ( x+1,y, mauto, maubien );  
Boundary_fill ( x-1,y, mauto, maubien );  
Boundary_fill ( x,y+1, mauto, maubien );  
Boundary_fill ( x,y-1, mauto, maubien );  
end;  
end;  
Nhận xét :  
- Thuật toán có thể không chính xác khi có một số điểm nằm trong vùng tô có màu là màu cần tô  
của vùng.  
- Việc thực hiện gọi đệ qui làm thuật toán không thể sử dụng cho vùng tô lớn ( tràn stack).  
- Có thể khắc phục việc tràn stack bằng cách giảm số lần gọi đệ qui. Khởi đầu điểm (x,y) là điểm  
có vị trí đặc biệt trong vùng tô, sau đó, gọi đệ qui các điểm lân cận của  
(x,y).  
12  
2.4 Bài tập áp dụng  
Bài 1 Tại sao phải so sánh giá trị Pi với 0 trong các giải thuật Bresenham hay Midpoint. Bản chất  
của so sánh là gì?  
Gợi ý: giá trị Pi tạo ra không có phép chia nguyên, tính toán nhanh và chính xác hơn là tính trực  
tiếp.  
Bài 2 Cặt đặt các giải thuật Bresenham, MidPoint vẽ đoạn thẳng với hệ số góc trong khoảng [-1,  
1], đường tròn.  
Gợi ý: Vẽ đường thẳng, ta xét 3 trường hợp 0 < m < 1, -1 < m < 0, m= 0.  
Bài 3 Giải thích tại sao chỉ chọn cung 1/8 để vẽ rồi lấy đối xứng mà không mở rộng cho cung  
1/16 hay 1/32.  
Gợi ý: Nếu cung độ dài nhỏ hơn 1/8 thì giải thuật Midpoint không còn đúng nữa, vì không chính  
xác.  
Bài 4 Cài đặt giải thuật vẽ elip có tâm là gốc tọa độ, bán kính trục chính, trục phụ là a, b.  
Gợi ý: Dựa trên cơ sở giải thuật Midpoint cho vẽ đường tròn, nhưng vẽ cho cung ¼ rồi lấy đối  
xứng.  
Bài 5 Cài đặt thuật toán tô màu đường biên cho đối tượng hình tròn.  
Gợi ý: Sử dụng giả thuật tô mầu đường biên cải tiến, sử dụng giải thuật không đệ quy thì tốt hơn  
giải thuật đệ quy.  
13  
Tải về để xem bản đầy đủ
pdf 54 trang Thùy Anh 04/05/2022 5780
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Đồ họa máy tính - Trường Đại học Hàng Hải", để 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:

  • pdfgiao_trinh_do_hoa_may_tinh_truong_dai_hoc_hang_hai.pdf