1
Câu 1. Đồ họa máy tính là gì? Cho biết các ứng dụng của đồ họa máy tính?
 Khái niệm ĐHMT
- Đồ họa máy tính là tất cả những gì liên quan đến việc sử dụng máy tính để phát sinh ra hình ảnh. Các
vấn đề liên quan tới công việc này bao gồm : tạo, lưu trữ, thao tác trên các mô hình (các mô tả hình học của
đối tượng) và các ảnh.
- Đồ họa máy tính bao gồm việc thiết kế phần cứng như thiết bị hiển thị, các thuật toán cần thiết để phát
sinh các đƣờng trên các thiết bị này, các phần mềm đƣợc sử dụng cho cả ngƣời lập trình hệ thống và người
lập trình ứng dụng đồ họa, và các chƣơng trình ứng dụng tạo ảnh bằng máy tính.
- Đồ họa máy tính tƣơng tác là một trong những phƣơng tiện mang lại thêm nhiều sự thuận
lợi cho ngƣời dùng trong việc phát sinh hình ảnh kể từ khi có phát minh của máy ảnh và truyền
hình.
 Các ứng dụng của đồ họa máy tính
 Hỗ trợ thiết kế (CAD/CAM)
CAD: Computer Aided Design, CAM: Computer Aided Manufacture
- Đồ họa máy tính đƣợc ứng dụng trong việc thiết kế các thành phần và hệ thống cơ khí, điện, các thiết
bị điện tử, xây dựng, hệ thống cáp quang, mạng điện thoại, thiết kế các mạch điện tử…Những phần liên
quan đến thiết kế và vẽ đƣợc thực hiện trực tiếp trên màn hình nhờ những công cụ trợ giúp đồ họa
 Xây dựng giao diện ngƣời dùng (User Interface)
- Mọi ứng dụng đều phải có giao diện giao tiếp với ngƣời dùng. Các ứng dụng dựa trên hệ điều hành MS
Windows là một minh họa rất trực quan của giao diện đồ họa. Các chức năng của các ứng dụng này đƣợc
thiết kế cho ngƣời dùng làm việc thông qua các biểu tƣợng mô tả chức năng đó.
- Các ứng dụng có giao diện đồ họa còn cho phép ngƣời dùng khả năng làm việc dễ dàng với nhiều cửa
sổ với nhiều dạng tài liệu khác nhau cùng một lúc.
 Biểu diễn thông tin
- Đây là các ứng dụng sử dụng đồ họa máy tính để phát sinh các biểu đồ, đồ thị,… dùng minh họa mối
quan hệ giữa nhiều đối tƣợng với nhau. Các ứng dụng này thƣờng đƣợc dùng để tóm lƣợc các dữ
liệu về tài chính, thống kê, kinh tế, khoa học, toán học, … giúp cho việc nghiên cứu, quản lí, … một cách
có hiệu quả.
 Tự động hoá văn phòng và chế bản điện tử
- Có thể tạo ra các văn bản điện tử và các văn bản sao chép cứng nhƣ tài liệu, biểu, các hình vẽ, hình

hình dung. Đồ họa máy tính cung cấp một công cụ tuyệt vời để thể hiện thông tin khoa học dƣới dạng dễ
tƣởng tƣợng và dễ nắm bắt nhất.
Câu 2: Trình bày hệ hiển thị thiết bị dạng Raster và Vecto?.
 Phương thức hiển thị Raster
- Tia điện tử quét ngang trên màn hình từ trái qua phải, khi quét hết một dòng ngang, tia điện tử đƣợc
dập tắt và lái hồi về đầu dòng tiếp.
3
- Mỗi điểm ảnh trên màn hình đƣợc gọi là pixel.
- Ảnh hiển thị theo công nghệ Raster là các đƣờng raster nằm ngang, mỗi đƣờng là một hàng gồm nhiều
pixel. Hệ hiển thị Raster lƣu trữ dƣới dạng ma trận các điểm ảnh biểu diễn toàn bộ màn hình.
- Sự bật tắt các điểm sáng trên màn hình phụ thuộc vào cƣờng độ của tia điện tử và đây chính là cơ sở
của việc tạo ra hình ảnh trên màn hình.
- Ưu điểm: Nguyên lý hoạt động tƣơng tự nhƣ tivi, hình ảnh tạo ra tƣơng đối tốt.
- Nhược điểm: xảy ra hiệu ứng bậc thang.
Phương pháp để tạo ra các pixel
- Phương pháp dùng phần mềm để vẽ trực tiếp từng pixel một.
- Dựa trên các lý thuyết mô phỏng để xây dựng nên hình ảnh mô phỏng của sự vật.
- Phương pháp rời rạc hoá (số hoá) hình ảnh thực của đối tượng.
- Có thể sửa đổi hoặc xử lý mảng các pixel thu được theo những phương pháp khác nhau để thu được
hình ảnh đặc trưng của đối tượng.
 Phương thức hiển thị vector
- Quét vector theo tọa độ các điểm đầu và cuối vector. Ngƣời ta sử dụng các cuộn lái tia để quét thành
các đoạn thẳng và nhƣ thế để vẽ đƣợc một đối tƣợng đồ họa ngƣời ta phải phân tích đối tƣợng thành các
đoạn thẳng cơ sở và lần lƣợt vẽ chúng.
- Chỉ di chuyển một số lần cần thiết để tạo ra hình ảnh. Khi đang ở giữa hai điểm mút của đoạn thẳng
định vẽ thì chùm tia không bao giờ bị tắt.
- Ưu điểm:
+ Thích hợp cho việc hiển thị các đối tƣợng hình học
+ Không bị hiệu ứng bậc thang
+ Tốn ít bộ nhớ

- 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).
- Quá trình mô tả các đối tƣợng thực nhƣ sau:

Câu 4. Trình bày nguyên lý chung vẽ đoạn thẳng ?
 Nguyên lý chung
Đầu vào: cho 2 điểm đầu mút (x1,y1) (x2,y2), màu vẽ C.
Phương trình đƣờng thẳng đi qua 2 điểm đầu mút:
(x-x1)/(y-y1) = (x2-x1)/(y2-y1) => Y=(y2-y1)*(x-x1)/(x2-x1)+y1
Đặt m= (y2-y1)/(x2-x1)
b= y1-mx1
ta có phƣơng trình y=mx+b
m đƣợc gọi là độ dốc hay hệ số góc của đƣờng thẳng, b đƣợc gọi là đoạn chắn trên trục y.
- Từ phƣơng trình này chúng ta có thể xây dựng quá trình vẽ các đƣờng thẳng khi cho x biến thiên các
khoảng x và kết quả ta có thể thu đƣợc giá trị của y thay đổi với các khoảng y tƣơng ứng y=mx.
- Hoặc có thể làm ngƣợc lại cho y biến thiên từng khoảng y và kết quả ta có thể thu đƣợc giá trị của x
thay đổi các khoảng x tƣơng ứng x=y/m
- Đơn vị nhỏ nhất của màn hình là một điểm ảnh nên thông thƣờng chọn x= 1 (x= -1) hoặc y= 1
(y= -1).
- Nguyên lý chung là cho một thành phần tọa độ x hay nguyên biến đổi theo từng đơn vị và tính tọa độ
nguyên còn lại sao cho gần với tọa độ thực nhất.
Câu 5. Trình bày thuật toán DDA vẽ đoạn thẳng ?
- Để đơn giản hóa giải thuật, chúng ta chỉ xét các đƣờng thẳng có hệ số góc m trong khoảng [0,1] và
Dx>0. Mỗi bƣớc nhẩy của x trong mỗi lần tính tƣơng đƣơng một điểm ảnh.
6
Như vậy tại bước i+1: 

=

+ 1

Lúc này bằng cách cho x tăng một đơn vị tại mỗi bƣớc, ta sẽ tìm cách tính y để vẽ các pixel tƣơng ứng.
Giả sử ở bƣớc thứ k ta đã xác định các tọa độ nguyên (xk, yk) nhƣ vậy chúng ta cần xác định tọa độ
(

, 

) cho bƣớc kế tiếp
Theo công thức ta có: 

= 

+1
7
Giá trị của 

có thể đƣợc chọn bởi một trong 2 giá trị yk hoặc yk+1. Điểm đƣợc chọn là
điểm gần với y thực nhất.

Xét khoảng cách d
1
, d
2
từ y thực đến y
k
và đến y
k+1

Gọi (x
k+1
,y) là điểm thuộc đoạn thẳng, ta có y=m(x

>= d
2
=> y
k+1
= y
k
+1 d
1
- d
2
= 2m(x
k
+ 1) - 2y
k
+ 2b - 1
m=(y
2
-y
1
)/(x
2
-x
1
)
Nếu xác định đƣợc dấu của d
1
-d
2
thì sẽ biết đƣợc điểm ảnh nào gần với đoạn thẳng hơn. Xác
định tham số quyết định P

)[(2(y
2
-y
1
)(x
k
+1)+(x
2
-x
1
)(- 2y
k
+2b-1)]/(x
2
-x
1
) =2(y
2
-y
1
)x
k
-2(x
2
-x
1
)y
k
+c
Trong đó c là hằng số đối với đoạn thẳng và c=2(y

1
)(x
k
+1)-2(x
2
-x
1
)y
k
+c = P
k
+2(y
2
-y
1
)
+) P
k
>=0 d
1
>=d
2
chọn y
k+1
=y
k
+1
8
P
k+1

-y
1
)x
1
-2(x
2
-x
1
)y
1
+2(y
2
-y
1
)+(2b-1)(x
2
-x
1
)
Do (x
1
, y
1
) là điểm nguyên thuộc đoạn thẳng nên ta có y
1
=mx
1
+b = (Dy/Dx)*x
1
+ b.

A=y
2
-y
1
, B= -(x
2
-x
1
), C=x
2
y
1
-x
1
y
2

F(x,y)=0 với mọi điểm (x,y) thuộc đƣờng thẳng
F(x,y)>0 với các điểm (x,y) nằm phía dƣới đƣờng thẳng
F(x,y)<0 với các điểm (x,y) nằm phía trên đƣờng thẳng
9
Lúc này việc chọn các điểm S, P ở trên đƣợc đƣa về việc xét dấu của p
i
=2F(M)=2F(x
i
+1, y
i
+0.5)=
2A(x
i

+2D
y

+ Nếu p
i
>=0, điểm M nằm phía dƣới đoạn thẳng. Lúc này điểm thực Q nằm phía trên điểm M nên ta
chọn P tức là y
i+1
=y
i
+1
P
i+1
=2F(x
i+1
+1, y
i+1
+0.5)=2F(x
i
+2, y
i
+1.5)= 2A(x
i
+2)+2B(y
i
+1.5)+C = p
i
+2A+2B=p
i
+ 2D

+0.5)+C = 2(Ax
1
+By
1
+C)+ 2A+B =2A+B= 2D
y
-D
x

Câu 8. Trình bày nguyên lý chung vẽ đường tròn?
Trong hệ tọa độ Descartes, phƣơng trình đƣờng tròn bán kính R có dạng:
Với tâm O(0,0) : 

+

= 


Với tâm C(x
c
, y
c
): (x-x
c
)
2
+ (y-y
c
)
2

0
đến 90
0
. Cách này sẽ
khắc phục hạn chế đƣờng không liền nét của thuật toán trên, tuy nhiên điểm hạn chế chính của thuật
toán này đó là chọn bƣớc nhảy cho θ nhƣ thế nào cho phù hợp khi bán kính thay đổi.
Câu 9. Thuật toán trung điểm (MidPoint) vẽ đƣờng tròn
Xét đƣờng tròn tâm tại gốc tọa độ, bán kính R. Xét cung 1/8 đƣờng tròn C(
1/8
), sau đó lấy đối
xứng.

Nhƣ vậy nếu có (x, y) thuộc (C
1/8
) thì các điểm : (y, x), (y,-x), (x,-y), (-x,-y), (y,-x), (-y,x), (-x,y) sẽ
thuộc (C).
Chọn điểm bắt đầu để vẽ là điểm (0,R). Dựa vào hình vẽ, nếu (x
i
, y
i
) là điểm nguyên đã tìm đƣợc ở
bƣớc thứ i, thì (x
i+1
, y
i+1
) ở bƣớc thứ (i+1) là sự lựa chọn giữa S và P. Nhƣ vậy:
x
i+1
=xi+1 y
i+1

i
-0.5)
2
-R
2

11
p
i+1
=F(x
i+1
+1, y
i+1
-0.5)= (x
i+1
+1)
2
+ (y
i+1
-0.5)
2
- R
2

Ta có :
+ Nếu p
i

i+1
=y
i
-1
p
i+1
=F(x
i
+2, y
i
- 1.5)= (x
i
+2)
2
+ (y
i
-1.5)
2
-R
2
= p
i
+ 2x
i
-2y
i
+5
Tính giá trị p
1
ứng với điểm ban đầu (x

Để vẽ elip tâm (h,k) ta có thể thực hiện vẽ elip tâm tại gốc tọa độ sau đó tịnh tiến theo véc tơ (h,k).
Tại mỗi bƣớc ta cho x tăng từ 0 đến a sau đó tính giá trị y tƣơng ứng qua biểu thức trên, sau đó lấy giá
trị nguyên gần với giá trị y thực nhất.
 Thuật toán trung điểm (MidPoint) vẽ elip
Xét elip tâm tại gốc tọa độ. Phƣơng trình đƣờng elip:
F(x,y)=b
2
x
2
+a
2
y
2
−a
2
b
2
=0
Xét vẽ cung ¼ elip, sau đó lấy đối xứng để thu đƣợc các phần còn lại
0<=x<=a
0<=y<=b
12
Chia cung ¼ elip này thành 2 vùng với điểm chia P là tiếp điểm của tiếp tuyến có hệ số góc là -1.
Véc tơ gradient vuông góc với tiếp tuyến tại tiếp điểm đƣợc xác định nhƣ sau:
GradF(x,y) = (∂F/∂x)i+(∂F/∂y)j=2b
2
x.i+2a
2
y.j
Ta có tiếp tuyến với cung tròn (độ dốc) = -1

i
=F(M)= F(x
i
+1,y
i
-1/2) = b
2
(x
i
+1)
2
+ a
2
(y
i
-1/2)
2
-a
2
b
2
pi+1 = F(xi+1+1,yi+1-1/2) = b
2
(x
i+1
+1)
2
+ a
2
(y

i
+2)
2
+ a
2
(y
i
-1/2)
2
-a
2
b
2

= p
i
+ b
2
(2x
i
+3)
- Nếu p
i
>=0 chọn B: xi+1=xi+1 yi+1=yi -1
p
i+1
= b
2
(x
i

(b-1/2)
2
-a
2
b
2
= b
2
- a
2
b +a
2
/4
+ Xét trên phần 2:
Ta lấy toạ độ của Pixel sau cùng trong phần 1 của đƣờng cong để tính giá trị ban đầu cho phần 2.
Tại mỗi bƣớc y giảm từng đơn vị, x biến đổi theo y.
Tại bƣớc j ta có điểm (x
j
,y
j
).
Pixel ở bƣớc kế tiếp j+1 có thể là: C(x
j
,y
j
-1) hoặc D(x
j
+1, y
j
-1

2
(x
j+1
+1/2)
2
+ a
2
(y
j+1
-1)
2
-a
2
b
2

- Nếu q
j
<0 chọn D: y
j+1
=yj-1, x
j+1
= x
j
+1
qj+1 b
2
(x
j+1
+1/2)

2
(2x
j
+2) +a
2
(-2y
j
+3)
- Nếu q
j
>=0 chọn C: y
j+1
=yj-1, x
j+1
= x
j

qj+1 = b
2
(x
j+1
+1/2)
2
+ a
2
(y
j+1
-1)
2
-a

= f(x
p
+1/2,y
p
-1) = b
2
(x
p
+1/2)
2
+ a
2
(y
p
-1)
2
-a
2
b
2

Câu 11. Định nghĩa đa giác, cho biết cách vẽ một đa giác?
 Khái niệm đa giác
Đa giác là thành phần cơ bản nhất của bề mặt. Việc biểu diễn đa giác có thể thông qua tập các đƣờng
thẳng hay tập các điểm thuộc đa giác. Một đa giác là một đƣờng gấp khúc có điểm đầu và điểm cuối trùng
nhau.
 Xây dựng cấu trúc dữ liệu để vẽ đa giác Type
d_dinh = record x,y: longint; end;
dinh = array[0 10] of d_dinh; var d: dinh;
Với cách xây dựng cấu trúc dữ liệu nhƣ thế này thì chúng ta chỉ cần nhập vào tọa độ các đỉnh và

i
,
y
i
)ϵP}
- Ứng với mỗi dòng quét y=k, với k thay đổi từ y
bottom
đến y
top
lặp :
+ Tìm tất cả các hoành độ giao điểm của dòng quét y=k với các cạnh của đa giác.
+ Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x
0
, x
1
, …
+ Tô màu các đoạn thẳng trên đƣờng thẳng y=k lần lƣợt đƣợc giới hạn bởi các cặp
(x
0
,x
1
), (x
2
, x
3
), ….
Nếu chỉ dừng ở mức này và chuyển sang cài đặt, chúng ta sẽ gặp một số vấn đề sau :
+ Nhận xét rằng, ứng với mỗi dòng quét, không phải lúc nào tất cả các cạnh của đa giác cũng tham
gia cắt dòng quét.
+ Việc tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ gặp các phép toán phức tạp nhƣ nhân,

C = rR + gG + bB
Trong đó C = màu hoặc ánh sáng kết quả. (r,g,b) = toạ độ màu trong miền [0 1], (R,G,B) = các màu cơ
bản đỏ, lục và lam.

Nếu hai màu tạo ra cùng một giá trị kích thích thì chúng ta không thể phân biệt đƣợc hai màu.
Không gian màu RGB dựa theo chuẩn ITU-R BT.709, với gama = 2.2 và điểm trắng của mô hình là
6500 degrees K.
Một số thuận lợi khi dùng không gian RGB :
+ Không gian RGB là chuẩn công nghiệp cho các thao tác đồ họa máy tính.
16
+ Có thể chuyển đổi qua lại giữa không gian RGB với các không gian màu khác nhƣ CIE, CMY, HSL,
HSV,
+ Các thao tác tính toán trên không gian RGB thƣờng đơn giản hơn.
Một số bất lợi :
+ Các giá trị RGB của một màu là khác nhau đối với các màn hình khác nhau : các giá trị RGB của
màu tim trên màn hình màu này sẽ không sinh ra đúng màu đó trên một màn hình khác.
+ Sự mô tả các màu trong thế giới thực đối với không gian RGB còn nhiều hạn chế bởi vì không
gian RGB không hoàn toàn phù hợp với sự cảm nhận màu sắc của con ngƣời.
 Mô hình màu CMY (Cyan, Magenta, Yellow - xanh tím, Đỏ tƣơi, vàng)
3 màu cơ sở là Cyan, Magenta, Yellow đây là 3 màu bù của 3 màu Red, Green, Blue.
Đây là mô hình màu bù (Subtractive color models) hiển thị ánh sáng và màu sắc phản xạ từ mực in. Bổ
xung thêm mực đồng nghĩa với ánh sáng phản xạ càng ít.
Khi bề mặt không phủ mực thì ánh sáng phản xạ là ánh sáng trắng - white.
Khi 3 màu có cùng giá trị cho ra màu xám. Khi các giá trị đạt max cho màu đen.
Color = cC + mM + yY

Đây là mô hình màu trừ tính.
- Hệ màu CMY được dùng cho các thiết bị in màu/giấy, chẳng hạn như máy in tĩnh điện hoặc máy in
phun.
Ta có Red +Cyan = Black ; Green +Magenta = Black ; Blue + Yellow = Black

Saturation: Độ bão hoà 0-1, giá trị của S là tập các giá trị từ 0 trên đƣờng trục tâm (trục V) đến 1 trên
các mặt bên tại đỉnh của chóp 6 cạnh.
18

 Một số thuận lợi của không gian HSV :
+ Không gian HSV dễ dàng đáp ứng các màu sắc của các chƣơng trình đồ họa do đƣợc xây dựng
dựa trên sự bắt chƣớc luật trộn màu của ngƣời họa sĩ.
+ Do không cần sử dụng các phép biến đổi lƣợng giác khi muốn chuyển sang không gian RGB nên
không gian HSV có nhiều thuận lợi về mặt tính toán hơn so với không gian HSL.
 Một số bất lợi :
+ Cần có các phép hiệu chỉnh gamma.
 Mô hình màu HLS (Hue, Lightness, Saturation Model) – không gian màu trực quan
Mô hình thƣờng đƣợc sử dụng trong kỹ thuật đồ hoạ.
Ưu điểm là rất trực giác ví dụ ta có thể chọn màu, thay đổi độ sáng và thay đổi độ bão hoà.
Nhược điểm là khi chuyển đổi với không gian màu RGB sẽ có sai số (cube stood on end) thay đổi
trên các loại màn hình khác nhau, rõ ràng không cảm nhận đều các màu.

19
Có thể coi mô hình HLS nhƣ một sự biến dạng của mô hình HLS mà trong đó mô hình này màu
trắng đƣợc kéo hƣớng lên hình chóp sáu cạnh phía trên từ mặt V=1.
Độ sáng (Lightness)=0 cho màu đen (tại điểm mút thấp nhất của hình chóp sáu cạnh đôi) và bằng 1 cho
màu trắng (tại đầu mút cao nhất).
 Một số thuận lợi của không gian HSL :
+ Không gian HSL gần với sự cảm nhận các thuộc tính màu sắc của con ngƣời hơn không gian
RGB. Các màu đƣợc xác định dễ dàng hơn.
+ Việc kiểm soát các màu cơ sở HSL dễ hơn cho những ngƣời mới làm quen với các chƣơng trình đồ
họa.
 Một số bất lợi :
+ Việc thêm vào một vector không thể thực hiện đơn giản nhƣ không gian RGB (chỉ thêm vào các
thành phần màu). Các thao tác lƣợng giác khi biến đổi sẽ ảnh hƣởng đáng kể đến tốc độ của chƣơng

thẳng sẽ đƣợc hiển thị toàn bộ trong vùng dữ liệu hiển thị.
 Trƣờng hợp 2: Không nhìn thấy
Đoạn thẳng nằm hoàn toàn về một phía ngoài của cửa sổ. 2 đầu mút của đoạn thẳng nằm hoàn toàn
về một phía ngoài của cửa sổ thỏa mãn một trong 4 bất đẳng thức sau:
x1, x2> xmax x1, x2<
xmin y1,y2>ymax y1,
y2<ymin
Đoạn thẳng bị loại bỏ khỏi vùng dữ liệu hiển thị.
 Trƣờng hợp 3: đoạn thẳng đƣợc cắt.
Đoạn thẳng không thuộc trƣờng hợp một hoặc trƣờng hợp hai. Khi đó đoạn thẳng có thể cắt hoặc không
cắt cửa sổ.
 Cách xác định giao điểm trong trường hợp đoạn thẳng cắt cửa sổ
- Đoạn thẳng cắt cửa sổ hình chữ nhật tại các giao điểm, ta quy về trường hợp đoạn thẳng cắt đoạn
thẳng.
Xét 2 đoạn thẳng AB, CD có các tọa độ đầu mút nhƣ sau: A(x
a
, y
a
), B(x
b
, y
b
),
C(x
c
, y
c
), D(x
d
, y

d
-y
c
) v 0<=v<= 1
Xét 2 đƣờng thẳng chứa 2 đoạn thẳng AB và CD tƣơng ứng (t, v ϵR)
Nếu 2 đƣờng thẳng này giao nhau với giá trị tham số t, v tƣơng ứng nằm trong khoảng [0,1] giao
điểm này sẽ nằm trong đoạn thẳng AB và CD. Nếu giá trị tham số nằm ngoài khoảng [0,1] thì hai
đoạn thẳng này không giao nhau.
Câu 17. Trình bày thuật toán xén đoạn thẳng Cohen-Sutherland?
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.
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í tƣơng ứng,
ngƣợc lại bit đó sẽ đƣợc đặt bằng 0. Ví dụ một vùng có mã là 1001, thì nó sẽ nằm phía dƣới (bit 4
bằng 1), bên trái (bit 1 bằng 1) so với cửa sổ, vùng có mã là 0000 chính là cửa sổ.

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 thuộc vùng đó với các
biên của cửa sổ. Bit 1 đƣợc đặt là 1 nếu x< x
min
, các bit khác đƣợc tính tƣơng tự.
Thuật toán
22
Gán mã vùng tƣơng ứng cho các điểm đầu cuối P
1
P

1
là c
1
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 P
1
’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 P
1
P
1
’. Tới đây chúng ta lại lặp
lại thao tác đã xét cho đoạn thẳng mới P
1
P
1
’ 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ố. Tung
độ y của điểm giao đoạn thẳng với biên đứng của cửa sổ có thể tính từ công thức y=y
1
+m(x-x
1
), trong
đó x có thể x
min
hay x
max
. Tƣơng tự, hoành độ x của điểm giao đoạn thẳng với biên ngang của cửa sổ
có thể tính từ công thức : x=x

)= y
1
+tDy, Dy=y
2
-y
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 t>=1 sẽ thuộc về tia P
2
x.
+ Các điểm ứng với t<=0 sẽ thuộc về tia P
2
x’.
+ Các điểm ứng với 0<=t<=1 sẽ thuộc về đoạn thẳng P
1
P
2
.

23
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 trình :

Đặt:
P
1
=-Dx, q
1
=x


Lúc này ta viết hệ phƣơng trình trên dƣới dạng :

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 mãn:

Ta xét các trƣờng hợp :
+ Nếu tồn tại k ϵ {1, 2,3,4}: (p
k
=0) ˄ (q
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 với mọi 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 p
k
= 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 p
k
t <=q
k
mà p

(x
1
+t
1
Dx, y
1
+t
1
Dy), Q
2
(x
1
+t
2
Dx, y
1
+t
2
Dy)
Thông thƣờng, thuật toán Liang-Barsky cho tốc độ tốt hơn thuật toán CohenSutherland vì rút gọn
đƣợc số giao điểm cần tính.
Câu 19. Trình bày thuật toán cắt đa giác Sutherland-Hodgman?
Cho P
1
, ,P
N
là danh sách các đỉnh của đa giác đã bị cắt tỉa P. Cho cạnh AB (điểm A,B) là cạnh
bất kỳ của đa giác cắt tỉa Q lồi duyệt theo hƣớng dƣơng. Với mỗi cạnh của đa giác Q ta sẽ cắt mỗi
cạnh của đa giác P và tạo nên một đa giác mới với các đỉnh đƣợc xác định nhƣ sau:
Xét cạnh P

i-1
nằm bên phải và P
i
nằm bên trái thì cả giao điểm I và P
i
đều đƣợc lƣu lại.
Quá trình thực hiện thuật toán bằng cách duyệt lần lƣợt tƣng cạnh của đa giác cắt. Với mỗi cạnh
của đa giác cắt lại duyệt lần lƣợt từng cạnh của đa giác bị cắt mới thu đƣợc.
Thuật toán Sutherland-Hodgeman cho kết quả rất chính xác khi làm việc với các đa giác lồi, tuy
nhiên với các đa giác lõm kết quả hiển thị có thể sẽ có đoạn thừa.
25
Câu 20. Cho biết các tính chất của phép biến đổi affine?
 Phép biến đổi affine bảo toàn đường thẳng
Ảnh của đƣờng thẳng qua phép biến đổi affine là đƣờng thẳng.
Từ kết quả trên, để biến đổi một đoạn thẳng đi qua hai điểm A và B, ta chỉ cần áp dụng phép biến đổi
cho hai điểm A, B rồi vẽ lại đoạn thẳng qua hai điểm mới.
 Tính song song của các đường thẳng được bảo toàn
Ảnh của hai đƣờng thẳng song song là hai đƣờng song song.
Một hệ quả quan trọng của tính chất này đó là ảnh của các hình bình hành sau phép biến đổi là các hình
bình hành.
 Tính tỉ lệ về khoảng cách được bảo toàn
Giả sử C là điểm chia đoạn AB theo tỉ số t. Nếu A’, B’, C’ lần lƣợt là ảnh A, B, C qua phép biến đổi
thì C’ cũng sẽ chia A’B’ theo tỉ số t.
Trong trƣờng hợp đặc biệt, nếu C là trung điểm của AB thì C’ cũng là trung điểm của A’B’, từ đó ta có
thể suy ra một số tính chất sau :
+ Trong hình vuông, các đƣờng chéo cắt nhau tại trung điểm của mỗi đƣờng nên các đƣờng chéo
của bất cứ hình bình hành nào cũng cắt nhau tại trung điểm của mỗi đƣờng.
+ Trong tam giác đều, giao điểm của ba đƣờng trung tuyến chia mỗi đƣờng theo tỉ số 1:2. Mặt
khác, một tam giác bất kì là ảnh của tam giác đều qua phép biến đổi affine, nên giao điểm của các
đƣờng trung tuyến của nó cũng sẽ chia chúng theo tỉ lệ 1:2.