Nhóm biên soạn: Nhóm #05
#8521006
Người đại diện: Cao Văn Tú
[email protected]

Mã Ticket tài liệu:
Skype: caotu_95 – Yahoo: bigme_caotu – Email:

ĐỀ CƯƠNG ÔN TẬP MÔN ĐỒ HỌA MÁY TÍNH
I. CẤU TRÚC ĐỀ THI.
Đề thi giữa kỳ gồm 02 câu. Trong đó:
+ 01 câu lý thuyết (Ôn theo mục II) – gồm 10 câu hỏi.
+ 01 câu bài tập (Ôn theo mục III)
 Thuật toán DDA.
 Thuật toán Bresanham.
 Thuật toán Midpoint.
II. PHẦN LÝ THUYẾT.
Câu 1: Hệ toạ độ thế giới thực? Hệ tọa độ thiết bị? Hệ tọa độ chuẩn?
Hướng dẫn
 Hệ toạ độ thế giới thực (WCS: World Coordinate System)
+) Hệ tọa độ thế giới thực (hay hệ tọa độ thực) là hệ tọa độ được dùng mô tả các đối
tượng thế giới thực.
+) Một trong các hệ tọa độ thực thường được dùng nhất đó là hệ tọa độ Descartes.
+) Với hệ tọa độ này, bất kì một điểm nào trong mặt phẳng cũng được mô tả bằng
một cặp tọa độ (x, y) trong đó x, y ∈ R. Gốc tọa độ là điểm O có tọa độ (0, 0). Ox, Oy
lần lượt được gọi là trục hoành, trục tung; x là khoảng cách từ điểm đến trục hoành hay
còn được gọi là hoành độ, y là khoảng cách từ điểm đến trục tung hay còn được gọi là
tung độ.
+) Các tọa độ thế giới thực cho phép người dùng sử dụng bất kì một thứ nguyên
(dimension) quy ước như foot, cm, mm, km, inch, ... nào và có thể lớn nhỏ tùy ý.
 Hệ toạ độ thiết bị (DCS: Device Coordinate System)

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

Hình 1: Hệ tọa độ chuẩn
Câu 2: Nguyên lý chung vẽ đoạn thẳng.
Hướng dẫn
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.
Việc quyết định chọn x hay y biến đổi phụ thuộc vào dáng điệu của đoạn thẳng để ta
có thể thu được đoạn thẳng xấp xỉ tốt nhất của đoạn thẳng thực tế.
Website: www.bigme.vn |
[email protected]

2

BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05
Mã Ticket tài liệu:
#8521006
Người đại diện: Cao Văn Tú
Skype: caotu_95 – Yahoo: bigme_caotu – Email:
[email protected]

+ 1, y)

thuộc về đoạn thẳng

sẽ là giá trị sau khi làm tròn giá trị tung độ y.

y = m( x i + 1) + b

Như vậy :

yi+1 = Round( y)

Nếu tính trực tiếp giá trị thực y ở mỗi bước từ phương trình

y = mx + b thì

phải cần một

phép toán nhân và một phép toán cộng số thực. Để cải thiện tốc độ, người ta tính giá trị thực
của y ở mỗi bước theo cách sau để khử phép tính nhân trên số thực :
Nhận xét rằng :

y sau = mx i +1 + b = m( x i + 1) + b
y tröôùc = mx i + b
⇒ y sau = y tröôùc + m

Nhận xét:
+) Việc sử dụng công thức

y sau = y tröôùc + m


Dy
Dx

m=

với Dy, Dx là các số

nguyên
Câu 4. Thuật toán Breshenham vẽ đoạn thẳng
Hướng dẫn
Thuật toán Bresenham đưa ra cách chọn

y i +1

là

yi

hay

yi + 1

theo một hướng khác

sao cho có thể tối ưu hóa về mặt tốc độ so với thuật toán DDA. Vấn đề mấu chốt ở đây là
làm thế nào để hạn chế tối đa các phép toán trên số thực trong thuật toán.
Gọi ( xi

+ 1, y)

d1 − d2 ≥ 0 ,

yi + 1 ,

d1 − d2

việc chọn điểm ( xi+1 , yi+1 ) là S

:

yi +1 = yi .

ta sẽ chọn điểm P, tức là

y i +1 = y i + 1 .

pi = Dx ( d1 − d2 ) = Dx ( 2 y − 2 yi − 1)

⇒ pi = Dx[ 2( m( x i + 1) + b) − 2 yi − 1]

Thay

m=

Dy
Dx

vào phương trình trên ta được :

pi = 2 Dyx i − 2 Dxy i + c ,


bước thật nhanh.
Website: www.bigme.vn |
[email protected]

4

BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05
#8521006
Người đại diện: Cao Văn Tú
[email protected]
Ta có :

Mã Ticket tài liệu:
Skype: caotu_95 – Yahoo: bigme_caotu – Email:

pi+1 − pi = ( 2 Dyx i+1 − 2 Dxy i+1 + c) − ( 2 Dyx i − 2 Dxy i + c)
⇔ pi +1 − pi = 2 Dy( x i +1 − x i ) − 2 Dx ( yi+1 − yi )
⇔ pi +1 − pi = 2 Dy − 2 Dx ( y i+1 − yi ), do x i+1 = x i + 1

Từ đây ta có thể suy ra cách tính
pi < 0

pi+1 = pi + 2 Dy

•

do ta chọn

y i +1 = y i + 1 .

được tính từ điểm vẽ đầu tiên ( x 0 , y0 ) theo công thức :

p0 = 2 Dyx 0 − 2 Dxy 0 + c = 2 Dyx 0 − 2 Dxy 0 + 2 Dy − ( 2b − 1) Dx

Do ( x 0 , y0 ) là điểm nguyên thuộc về đoạn thẳng nên ta có
vào phương trình trên ta suy ra :

y0 = mx 0 + b =

Dy
x0 + b
Dx
.

Thế

p0 = 2 Dy − Dx .

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 (phép dịch bit). Đ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 Pi để quyết định điểm
kế tiếp, và sử dụng công thức truy hồi Pi +1 - Pi để tính Pi 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 tổng quát cho thuật toán Bresenham có
phức tạp hơn thuật toán DDA.
+) Thuật toán này cho kết quả tương tự như thuật toán DDA.

Nhóm biên soạn: Nhóm #05
Mã Ticket tài liệu:
#8521006
Người đại diện: Cao Văn Tú
Skype: caotu_95 – Yahoo: bigme_caotu – Email:
[email protected]
• Nếu điểm Q nằm dưới điểm MidPoint, ta chọn S.
Ngược lại nếu điểm Q nằm trên điểm MidPoint ta chọn P.

•

Ta có dạng tổng qt của phương trình đường thẳng :
Ax + By + C = 0

với
Đặt

F ( x, y) = Ax + By + C ,

A = y2 − y1 , B = −( x 2 − x1 ) , C = x 2 y1 − x1 y 2

ta có nhận xét :

< 0, nếu ( x, y ) nằm phía trê n đườ ng thẳ ng

F ( x, y) = 0, nế u ( x, y ) thuộc về đườ ng thẳ ng
> 0, nế u ( x, y ) nằ m phía dướ i đườ ng thẳ ng.


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

Mặt khác :
1
1


pi+1 − pi = 2 F  x i+1 + 1, yi+1 +  − 2 F  x i + 1, yi + 
2
2







1
1


⇔ pi+1 − pi = 2 A( xi+1 + 1) + B yi +1 +  + C  − 2 A( xi + 1) + B yi +  + C 
2
2






⇔ pi +1 − pi = 2 A + 2 B( yi +1 − yi ) = 2 Dy − 2 Dx ( yi +1 − y i )


đầu


Nhóm biên soạn: Nhóm #05
Mã Ticket tài liệu:
#8521006
Người đại diện: Cao Văn Tú
Skype: caotu_95 – Yahoo: bigme_caotu – Email:
[email protected]
Ta tính giá trị p0 ứng với điểm ban đầu ( x 0 , y0 ) , với nhận xét rằng ( x 0 , y0 ) là điểm
thuộc về đoạn thẳng, tức là có : Ax 0 + By 0 + C = 0


1
1


p0 = 2 F  x 0 + 1, y0 +  = 2 A( x 0 + 1) + B y0 +  + C 
2
2




⇒ p0 = 2( Ax 0 + By 0 + C ) + 2 A + B = 2 A + B = 2 Dy − Dx

Nhận xét rằng thuật toán MidPoint cho kết quả tương tự như thuật toán Bresenham.
Câu 6. Trình bày nguyên lý chung vẽ đường tròn?
Hướng dẫn
+) Trong hệ tọa độ Descartes, phương trình đường tròn bán kính R có dạng:

đ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 7. Trình bày thuật toán MidPoint vẽ đường tròn?
Hướng dẫn
+) Do tính đối xứng của đường tròn (C) nên ta chỉ cần vẽ cung (C1/8) là cung 1/8
đường tròn, sau đó lấy đối xứng.
(-x,y)

(x,y)
(y,x)

(-y,x)
R

(-y,-x)

2

(-x,-y)

(y,-x)

(x,-y)

xám trong hình vẽ) :

+) Cung (C1/8) được mô tả như sau (cung của phần tô


2

ngun đã tìm được ở bước thứ i, thì điểm ( x i+1 , yi+1 ) ở bước thứ (i+1) là sự lựa chọn giữa S
và P.
 x i +1 = x i + 1

y ∈ { yi , yi − 1}
Như vậy :  i+1

+) Tương tự như thuật tốn MidPoint vẽ đoạn thẳng, việc quyết định chọn một trong
hai điểm S và P sẽ được thực hiện thơng qua việc xét dấu của một hàm nào đó tại điểm
MidPoint là điểm nằm giữa chúng.
+) Đặt

F ( x, y) = x 2 + y 2 − R 2

, ta có :

< 0, nế u ( x, y ) nằ m trong đườ ng trò n

F ( x, y) = 0, nế u ( x, y ) nằ m trê n đườ ng trò n
> 0, nế u ( x, y ) nằ m ngoà i đườ ng trò n.


Xét

1

pi = F ( MidPoint ) = F  x i + 1, yi − 
2

.


pi+1 − pi = F  x i+1 + 1, y i+1 −  − F  x i + 1, yi − 
2
2




⇔ pi +1

2
2

 

1
1


2
2
2
− pi = ( xi+1 + 1) +  yi+1 −  − R  − ( xi + 1) +  yi −  − R2 
2
2



 


Website: www.bigme.vn |
[email protected]

9

BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05
#8521006
Người đại diện: Cao Văn Tú
[email protected]
Vậy :

Mã Ticket tài liệu:
Skype: caotu_95 – Yahoo: bigme_caotu – Email:

•

p i +1 = p i + 2 x i + 3 ,

•

p i +1 = p i + 2 x i − 2 y i + 5 ,

Ta tính giá trị

p0


Nguyên lý chung:
+) Cho elip tâm (h, k), độ dài trục chính là a, độ dài trục phụ là b
+) Phương trình đường elip được xác định như sau : (x-h)2/a2+(y-k)2/b2=1.
+) Phưuơng trình elip với tâm tại gốc tọa độ: x2/b2+y2/b2=1
+) Elip được chia thành 4 phần đối xứng qua 2 trục tọa độ, do vậy ta chỉ cần vẽ cung ¼
elip sau đó thực hiện lấy đối xứng để thu được các phần còn lại.
+) Để 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)=b2x2+a2y2−a2b2=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.

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=2b2x.i+2a2y.j
Website: www.bigme.vn |
[email protected]

10

BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05
Mã Ticket tài liệu:

+) Tại bước j ta có điểm (xj,yj).
+) Pixel ở bước kế tiếp j+1 có thể là: C(xj,yj-1) hoặc D(xj+1, yj-1).
+) Chúng ta sẽ lựa chọn điểm gần với đường elip nhất. Để quyết định chọn điểm nào
chúng ta có thể dựa vào dấu của hàm F tại trung điểm M của đoạn CD .
Tham số quyết định: (Tương tự như trên)
Website: www.bigme.vn |
[email protected]

11

BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05
Mã Ticket tài liệu:
#8521006
Người đại diện: Cao Văn Tú
Skype: caotu_95 – Yahoo: bigme_caotu – Email:
[email protected]
Câu 9. Trình bày các mô hình màu RGB, CMY, CMYK?
Hướng dẫn
Mô hình màu RGB (Red, Green, Blue - đỏ, lục, lam):
+) Mô hình màu thể hiện trong màn hình CRT xác định bằng những đặc tính của hiện
tượng phát quang các chất phốt pho trong màn hình CRT. Mô hình không gian màu RGB
được sắp xếp theo khối lập phương đơn vị. Đường chéo chính của khối lập phương với sự
cân bằng về số lượng từng màu gốc tương ứng với các mức độ xám với đen là (0,0,0) và
trắng (1,1,1).
+) Đây là mô hình màu cộng tính.
+) C = rR + gG + bB

Skype: caotu_95 – Yahoo: bigme_caotu – Email:
[email protected]
+) Mô hình này có ba 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
+) Ta có Red +Cyan = Black ; Green +Magenta = Black ; Blue + Yellow = Black
+) Đây là mô hình màu trừ tính.
Mô hình màu CMY- K
+) Mô hình mở rộng của CMY ứng dụng trong máy in màu. Giá trị đen bổ xung vào
thay thế cho hàm lượng màu bằng nhau của 3 màu cơ bản.
+) Công thức chuyển đổi:
K = min(C, M, Y) ; C = C - K ; M = M - K; Y = Y - K ;
C-Cyan, M-Magenta, Y-Yellow; K-blacK
Câu 10. Trình bày các mô hình màu HSV, HSL?
Hướng dẫn
Mô hình màu HSV.
Các yếu tố xác định màu sắc trong mô hình này gồm:
-Hue - sắc màu: dùng để phân biệt sự khác nhau giữa các màu như xanh, đỏ, vàng...
- Saturation - độ bão hoà: chỉ ra mức độ thuần của một màu hay khoảng cách của màu
tới điểm có cường độ cân bằng(màu xám)
- Lightness - độ sáng: hiện thân về mô tả cường độ sáng từ ánh sáng phản xạ nhận
được từ đối tượng.
-Vualue(Brightness) - độ phát sáng: cường độ ánh sáng mà tự đối tượng phát ra chứ
không phải do phản xạ từ các nguồn sáng khác.
Website: www.bigme.vn |
[email protected]

+ 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 .
Một số bất lợi:
+ Cần có các phép hiệu chỉnh gamma.
Mô hình màu HSL (Hue, Lightness, Saturation Model) – không gian màu trực quan
+) Mô hình màu HLS là không gian màu trực quan. Mô hình này thường được dùng
trong kỹ thuật đồ hoạ.
+) Ưu điểm là rất trực giác

Website: www.bigme.vn |
[email protected]

14

BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05
Mã Ticket tài liệu:
#8521006
Người đại diện: Cao Văn Tú
Skype: caotu_95 – Yahoo: bigme_caotu – Email:
[email protected]
+) 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 giống
nhau
+) Độ 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:

Dạng 1: Thuật toán DDA (Digital Differential Analyzer)
 Cơ sở lý thuyết
+ Thuật toán DDA là một 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 đường thẳng y = mx + b.
+ Lưu đồ thuật toán DDA.
Bắt đầu

Dy
; x = x1 ; y = y1 ;
Dx
Putpixel ( x, Round ( y ), c );

m=

x < x2

No

Yes

x = x + 1; y = y + m;
Putpixel ( x, Round ( y ), c );

Kết thúc
 Lưu ý một số công thức của đường thẳng.

Website: www.bigme.vn |
[email protected]

16


m=

Dy 3
= = 0, 75
Dx 4
(Thuộc vào trường hợp 0 < m < 1)

 x0 = 3

y =4
 Xác định điểm đầu tiên:  0

⇒

Vẽ điểm (3, 4).

 Xác định những điểm tiếp theo:
x = 3
y1 = y0 + m = 4 + 0, 75 = 4, 75 ⇒  1
 y1 = 4
+)

⇒

Vẽ điểm (3, 5).

 x1 = 4
y2 = y1 + m = 4, 75 + 0, 75 = 5,5 ⇒ 
 y1 = 5

[email protected]

17

Vẽ điểm (6, 7).

Vẽ điểm (7, 8).
BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05
#8521006
Người đại diện: Cao Văn Tú
[email protected]

Mã Ticket tài liệu:
Skype: caotu_95 – Yahoo: bigme_caotu – Email:

x = 8
y6 = y5 + m = 7, 75 + 0, 75 = 8,5 ⇒  1
 y1 = 8
+)

⇒

x = 9
y7 = y7 + m = 8,5 + 0, 75 = 9, 25 ⇒  1
 y1 = 9
+)

2
1
+)
1
+)

m=

Dy 5
= =1
Dx 5
(Thuộc vào trường hợp m > 1)

 x0 = 5

y = 10
 Xác định điểm đầu tiên:  0

⇒

Vẽ điểm (5, 10).

 Xác định những điểm tiếp theo:

+)

+)

x1 = x0 +


= 8 +1 = 9 ⇒ 
m
 y1 = 14

⇒

+)

+)

x4 = x3 +

Website: www.bigme.vn |
[email protected]

Vẽ điểm (6, 11).

Vẽ điểm (7, 12).

Vẽ điểm (8, 13).

Vẽ điểm (9, 14).

18

BIGME.VN – Siêu thị trực tuyến hàng
đầu


Nhóm biên soạn: Nhóm #05

đầu toán Bresenham
 Cơ sở lý thuyết
+ Gọi (xi+1,y) là điểm thuộc đoạn thẳng thực.
Dx+=b.x2 −(0x1
Mã Ticket tài liệu:
Skype: caotu_95 – Yahoo: bigme_caotu – Email:

x < x2

No

 Các bước vẽ thuật toán Bresanham
+) Bước 1: Nhập các điểm đầu mút. Điểm đầu mút bên trái chứa tọa độ (x1,y1), điểm đầu
mút bên phải chứa tọa độ (x2,y2).
+) Bước 2: Tính các đại lượng:
Dx = x2 − x1 ; Dy = y2 − y1 ;

(
1
2
•
• Chọn điểm xuất phát (x, y) = (x1, y1)
• Vẽ điểm (x1, y1).

P = 2 Dy − Dx; c = 2 Dy; c = 2 Dy − Dx ) ;

+) Bước 3: Nếu x < x2 thì x = x + 1

• Nếu P < 0 : P = P + 2 Dy = P + c1

(
)
• Ngược lại:
• Vẽ điểm (x, y) mới.

c1 = 2 Dy = 2.1 = 2; c2 = 2 ( Dy − Dx ) = 2 ( 1 − 5 ) = −8

 x0 = 4

y =5
 Xác định điểm đầu tiên:  0

.

⇒

Vẽ điểm (4, 5).

 Xác định những điểm tiếp theo:

+)

P0 = −3 < 0

 x1 = 5
⇒
 y1 = 5

⇒

Vẽ điểm (5, 5).

⇒ P1 = P0 + 2 Dy = P0 + c1 = − 3 + 2 = −1

+)


 x4 = 8
⇒
 y4 = 6

⇒

Vẽ điểm (8, 6).

⇒ P4 = P3 + c1 = − 5

+)

P4 = −5 < 0

 x5 = 9
⇒
 y5 = 6

⇒

Vẽ điểm (9, 6).

Điểm (9, 6) có x = x2 nên thuật toán dừng.
Website: www.bigme.vn |
[email protected]

21

BIGME.VN – Siêu thị trực tuyến hàng



 Cơ sở lý thuyết của thuật toán Midpoint vẽ đường tròn.
+) Do tính đối xứng của đường tròn (C) nên ta chỉ cần vẽ cung (C1/8) là cung 1/8 đường
tròn, sau đó lấy đối xứng. Cung (C1/8) được mô tả như sau (cung của phần tô xám trong

hình vẽ) :


2
0 ≤ x ≤ R

2

2

R
≤ y≤R

 2

+) Như vậy nếu có (x, y) ∈ (C1/8) thì các điểm : (y, x), (y,-x), (x,-y), (-x,-y), (-y,-x), (No
Website: www.bigme.vn |
[email protected]

22

BIGME.VN – Siêu thị trực tuyến hàng
đầu


2

Xét
. Ta có :
•

•

Nếu pi < 0 , điểm MidPoint nằm trong đường tròn. Lúc này điểm thực Q gần S hơn nên
ta chọn S, tức là yi+1 = yi .
Ngược lại, nếu pi ≥ 0 , điểm MidPoint nằm ngồi đường tròn. Lúc này điểm thực Q gần
P hơn nên ta chọn P, tức là yi+1 = yi − 1 .
Mặt khác :
1
1


pi+1 − pi = F  x i+1 + 1, y i+1 −  − F  x i + 1, yi − 
2
2


2
2

 

1
1




 


(

)

⇔ pi +1 − pi = 2 xi + 3 + yi2+1 − yi2 − ( yi +1 − yi )

Vậy :
•

p i +1 = p i + 2 x i + 3 ,

•

p i +1 = p i + 2 x i − 2 y i + 5 ,

+) Ta tính giá trị
Website: www.bigme.vn |
[email protected]

nếu
p0

pi < 0

do ta chọn




+ Lưu đồ thuật toán MidPoint.
Bắt đầu

5
− R; x = 0; y = R;
4
Put 8Pixel ( x, y, c);
P=

x
x = 0
⇒

+) Ta có:  y = R = 10
Vẽ điểm (0, 10).
P0 =

 x1 = 1

y = 10
P
=
−
8,
75


⇒
 y6 = 8

+)

Vẽ điểm (6, 8).

P6 = P5 + 2 ( x5 − y5 ) + 5 = 8, 25 + 2 ( 5 − 9 ) + 5 = 5, 25
 x7 = 7
P6 = 9, 25 > 0. 
 y7 = 7
+)

⇒

Vẽ điểm (7, 7).

P7 = P6 + 2 ( x6 − y6 ) + 5 = 5, 25 + 2 ( 6 − 8 ) + 5 = 6, 25

Thuật toán dừng vì x < y.
 Hình vẽ minh họa. (Bạn đọc tự vẽ)
 Ghi nhớ:
o Đối với thuật toán MidPoint thì tọa độ của x luôn luôn tăng nên 1 đơn vị (x = x + 1).

Website: www.bigme.vn |
[email protected]

25

BIGME.VN – Siêu thị trực tuyến hàng