Giáo trình Đồ họa máy tính - Chương 2, Phần 1: Các đối tượng đồ họa cơ sở

CHÖÔNG 2

CAÙC ÑOÁI TÖÔÏNG ÑOÀ HOÏA CÔ SÔÛ

Baát kì moät aûnh moâ taû theá giôùi thöïc naøo bao giôø cuõng ñöôïc caáu truùc töø

taäp caùc ñoái töôïng ñôn giaûn hôn. Ví duï moät aûnh theå hieän baøi trí cuûa moät caên

phoøng seõ ñöôïc caáu truùc töø caùc ñoái töôïng nhö caây caûnh, tuû kính, baøn gheá,

töôøng, aùnh saùng ñeøn, … Vôùi caùc aûnh ñoà hoïa phaùt sinh baèng maùy tính, hình

daïng vaø maøu saéc cuûa moãi ñoái töôïng coù theå ñöôïc moâ taû rieâng bieät baèng

hai caùch : hoaëc laø baèng daõy caùc pixel töông öùng hoaëc laø baèng taäp caùc ñoái

töôïng hình hoïc cô sôû nhö ñoaïn thaúng hay vuøng toâ ña giaùc, … Sau ñoù, caùc aûnh

seõ ñöôïc hieån thò baèng caùch naïp caùc pixel vaøo vuøng ñeäm khung.

Hình 2.1 – AÛnh caùnh tay robot ñöôïc caáu taïo töø caùc ñoái töôïng ñoà hoïa cô sôû

Vôùi caùc aûnh ñöôïc moâ taû baèng caùc ñoái töôïng hình hoïc cô sôû, caàn phaûi coù

moät quaù trình chuyeån caùc ñoái töôïng naøy veà daïng ma traän caùc pixel tröôùc.

Quaù trình naøy coøn ñöôïc goïi laø quaù trình chuyeån ñoåi baèng doøng queùt (scan-

converting). Baát kì coâng cuï laäp trình ñoà hoïa naøo cuõng phaûi cung caáp caùc haøm

ñeå moâ taû moät aûnh döôùi daïng caùc ñoái töôïng hình hoïc cô sôû hay coøn goïi laø

caùc ñoái töôïng ñoà hoïa cô sôû (output primitives) vaø caùc haøm cho pheùp keát hôïp

taäp caùc ñoái töôïng cô sôû ñeå taïo thaønh ñoái töôïng coù caáu truùc phöùc taïp hôn.

Moãi ñoái töôïng ñoà hoïa cô sôû ñöôïc moâ taû thoâng qua döõ lieäu veà toïa ñoä vaø

caùc thuoäc tính cuûa noù, ñaây chính laø thoâng tin cho bieát kieåu caùch maø ñoái

töôïng ñöôïc hieån thò. Ñoái töôïng ñoà hoïa cô sôû ñôn giaûn nhaát laø ñieåm vaø ñoaïn

thaúng, ngoaøi ra coøn coù ñöôøng troøn, vaø caùc ñöôøng conics, maët baäc hai, caùc

maët vaø ñöôøng splines, caùc vuøng toâ ña giaùc, chuoãi kí töï, … cuõng ñöôïc xem laø

caùc ñoái töôïng ñoà hoïa cô sôû ñeå giuùp xaây döïng caùc aûnh phöùc taïp. Chöông

naøy seõ khaûo saùt caùc thuaät toaùn hieån thò caùc ñoái töôïng ñoà hoïa cô sôû cho

caùc thieát bò hieån thò daïng ñieåm.

Xeùt veà maët baûn chaát, caùc thuaät toaùn naøy thöïc hieän quaù trình chuyeån ñoåi

caùc ñoái töôïng ñoà hoïa cô sôû ñöôïc moâ taû trong heä toïa ñoä thöïc veà daõy caùc

pixel coù toïa ñoä nguyeân cuûa thieát bò hieån thò. Coù hai yeâu caàu ñaët ra cho caùc

thuaät toaùn naøy ñoù laø :

•

Ñoái töôïng ñöôïc moâ taû trong heä toïa ñoä thöïc laø ñoái töôïng lieân tuïc, coøn ñoái

töôïng trong heä toïa ñoä thieát bò laø ñoái töôïng rôøi raïc, do ñoù baûn chaát cuûa quaù

trình chuyeån ñoåi naøy chính laø söï rôøi raïc hoùa vaø nguyeân hoùa caùc ñoái töôïng

sao cho coù theå xaùc ñònh caùc ñieåm nguyeân xaáp xæ ñoái töôïng moät caùch toát nhaát,

thöïc nhaát. Nghóa laø ñoái töôïng hieån thò baèng löôùi nguyeân treân thieát bò hieån

thò phaûi coù hình daïng töông töï nhö ñoái töôïng trong löôùi toïa ñoä thöïc vaø “coù

veû” lieân tuïc, lieàn neùt. Söï lieân tuïc treân löôùi nguyeân cuûa thieát bò hieån thò coù

ñöôïc do maét ngöôøi khoâng theå phaân bieät ñöôïc hai ñieåm quaù gaàn nhau.

•

Do caùc ñoái töôïng ñoà hoïa cô sôû laø thaønh phaàn chính caáu truùc caùc ñoái töôïng

phöùc taïp neân caùc thuaät toaùn hieån thò chuùng caàn phaûi ñöôïc toái öu hoùa veà

maët toác ñoä, ñaây chính laø ñieåm maáu choát cho vieäc ra ñôøi caùc thuaät toaùn

khaùc nhau.

Hình 2.2 – Quaù trình chuyeån ñoåi moät ñoaïn thaúng veà daõy caùc pixel töông öùng

1. CAÙC ÑOÁI TÖÔÏNG ÑOÀ HOÏA CÔ SÔÛ

1.1. Heä toïa ñoä theá giôùi thöïc vaø heä toïa ñoä thieát bò

1.1.1. Heä toïa ñoä theá giôùi thöïc

Heä toïa ñoä theá giôùi thöïc (hay heä toïa ñoä thöïc) laø heä toïa ñoä ñöôïc duøng moâ

taû caùc ñoái töôïng theá giôùi thöïc. Moät trong caùc heä toïa ñoä thöïc thöôøng ñöôïc

duøng nhaát ñoù laø heä toïa ñoä Descartes. Vôùi heä toïa ñoä naøy, baát kì moät ñieåm

naøo trong maët phaúng cuõng ñöôïc moâ taû baèng moät caëp toïa ñoä (x, y) trong ñoù

x, y  R. Goác toïa ñoä laø ñieåm O coù toïa ñoä (0, 0). Caùc truïc toïa ñoä coù chieàu

döông ñöôïc quy öôùc nhö hình 2.3; Ox, Oy laàn löôït ñöôïc goïi laø truïc hoaønh, truïc

tung; x laø khoaûng caùch töø ñieåm ñeán truïc hoaønh hay coøn ñöôïc goïi laø hoaønh

ñoä, y laø khoaûng caùch töø ñieåm ñeán truïc tung hay coøn ñöôïc goïi laø tung ñoä.

Caùc toïa ñoä theá giôùi thöïc cho pheùp ngöôøi duøng söû duïng baát kì moät thöù

nguyeân (dimension) quy öôùc nhö foot, cm, mm, km, inch, ... naøo vaø coù theå lôùn

nhoû tuøy yù.

1.1.2. Heä toïa ñoä thieát bò

Heä toïa ñoä thieát bò laø heä toïa ñoä ñöôïc duøng bôûi moät thieát bò xuaát cuï theå naøo ñoù nhö

maùy in, maøn hình, ... Ñaëc ñieåm chung cuûa caùc heä toïa ñoä thieát bò ñoù laø :

•

Caùc ñieåm trong heä toïa ñoä thieát bò cuõng ñöôïc moâ taû bôûi moät caëp toïa ñoä (x,

y), tuy nhieân ñieåm khaùc vôùi heä toïa ñoä thöïc laø x, y  N. Ñieàu naøy cho thaáy

caùc ñieåm trong heä toïa ñoä thöïc ñöôïc ñònh nghóa lieân tuïc, coøn caùc ñieåm trong

caùc heä toïa ñoä thieát bò laø rôøi raïc do tính chaát cuûa taäp caùc soá töï nhieân.

Caùc toïa ñoä x, y cuûa heä toïa ñoä thieát bò khoâng theå lôùn tuøy yù maø ñeàu bò giôùi

haïn trong moät khoaûng naøo ñoù. Moät soá thieát bò chæ cho x chaïy trong

ñoaïn[0,639], y chaïy trong ñoaïn [0,479]. Khoaûng giôùi haïn caùc toïa ñoä x, y laø

khaùc nhau ñoái vôùi töøng loaïi thieát bò khaùc nhau.

y

P_WC(x,y)

y_max

P_DC(x,y)

O

x

O

x_max

x

(a)

(b)

Hình 2.3 – Heä toïa ñoä thöïc (a) vaø heä toïa ñoä thieát bò (b)

Heä toïa ñoä vôùi caùc höôùng cuûa caùc truïc toïa ñoä nhö treân coøn ñöôïc goïi laø heä

toïa ñoä theo quy öôùc baøn tay phaûi.

Ngoaøi ra do caùch toå chöùc boä nhôù neân thoâng thöôøng caùc heä toïa ñoä thieát bò

thöôøng döïa treân heä toïa ñoä theo quy öôùc baøn tay traùi.

y

O

x

O

x

y

(a)

(b)

Hình 2.4 - Heä toïa ñoä theo quy öôùc baøn tay phaûi (a) vaø quy öôùc baøn tay traùi (b)

1.2. Ñieåm

Ñieåm laø thaønh phaàn cô sôû ñöôïc ñònh nghóa trong moät heä toïa ñoä. Ñoái vôùi heä

toïa ñoä hai chieàu moãi ñieåm ñöôïc xaùc ñònh bôûi caëp toïa ñoä (x, y).

Ngoaøi thoâng tin veà toïa ñoä, ñieåm coøn coù thuoäc tính laø maøu saéc.

1.3. Ñoaïn thaúng, ñöôøng gaáp khuùc

Moät ñöôøng thaúng coù theå xaùc ñònh neáu bieát hai ñieåm thuoäc noù. Phöông trình

ñöôøng thaúng ñi qua hai ñieåm (x₁, y₁) vaø (x₂, y₂) coù daïng sau :

x  x₁

y  y₁

x₂ x₁

y₂ y₁



hay ôû daïng töông ñöông :



x  x₁y₂ y₁





y  y₁x₂ x₁

 

Khai trieån ta coù daïng : y  mx  b, trong ñoù :

Dy

m 

, Dy  y₂ y₁, Dx  x₂ x₁

Dx

b  y₁ mx₁

Ñaây coøn ñöôïc goïi laø phöông trình ñoaïn chaén cuûa ñöôøng thaúng.

Neáu khai trieån döôùi daïng :



y₂ y₁



x 



x₂ x₁



y  x₁y₂ x₂y₁ 0

vaø ñaët A  y₂ y₁, B  



x₂ x₁,C  x₂y₁ x₁y₂thì phöông trình ñöôøng thaúng seõ coù



daïng Ax  By  C  0, daïng naøy ñöôïc goïi laø phöông trình toång quaùt cuûa ñöôøng thaúng.

Phöông trình tham soá cuûa ñöôøng thaúng coù daïng caùc toïa ñoä x, y ñöôïc moâ taû

qua moät thaønh phaàn thöù ba laø t. Daïng naøy raát thuaän tieän khi khaûo saùt caùc

ñoaïn thaúng.

x 

y 



1 t



1 t



x₁ tx₂









y₁ ty₂

Neáu t

vaø (x₂, y₂), neáu t



0,1



, ta coù caùc ñieåm (x,y) thuoäc veà ñoaïn thaúng giôùi haïn bôûi hai ñieåm (x₁, y₁)

, , ta seõ coù toaøn boä ñöôøng thaúng.





Moät ñoaïn thaúng laø moät ñöôøng thaúng bò giôùi haïn bôûi hai ñieåm ñaàu, cuoái.

(x₂, y₂)

t>1

t=1

(x₁, y₁)

t=0

t<0

Hình 2.5 – Daïng tham soá cuûa phöông trình ñöôøng thaúng

Ñöôøng gaáp khuùc laø taäp caùc ñoaïn thaúng noái vôùi nhau moät caùch tuaàn töï.

Caùc ñoaïn thaúng naøy khoâng nhaát thieát phaûi taïo thaønh moät hình kheùp kín vaø

caùc ñoaïn coù theå caét laãn nhau. Ñieåm giao cuûa hai ñoaïn thaúng ñöôïc goïi laø

ñænh. Caùc ñöôøng gaáp khuùc ñöôïc xaùc ñònh qua danh saùch caùc ñænh, moãi ñænh

ñöôïc cho bôûi caùc caëp toïa ñoä



x_i, y_i.



Moät ña giaùc laø moät ñöôøng gaáp khuùc coù ñieåm ñaàu vaø ñieåm cuoái truøng

nhau.

(a)

(b)

Hình 2.6 – Ñöôøng gaáp khuùc (a) vaø ña giaùc (b)

Caùc thuoäc tính cuûa ñoaïn thaúng bao goàm :

•

Maøu saéc

Ñoä roäng cuûa neùt veõ.

•

Kieåu neùt veõ cuûa ñoaïn thaúng : coù theå laø moät trong caùc daïng nhö hình 2.7.

Haàu heát caùc coâng cuï ñoà hoïa ñeàu ñònh nghóa taäp caùc kieåu neùt veõ ñoaïn thaúng

coù theå duøng vaø cho pheùp ngöôøi duøng ñònh nghóa kieåu ñoaïn thaúng cuûa mình

thoâng qua moät maãu (pattern) goàm caùc soá 0, 1.

Ñoái vôùi ñöôøng gaáp khuùc, caùc ñoaïn thaúng trong cuøng moät ñöôøng gaáp khuùc

thì coù cuøng moät thuoäc tính.

Hình 2.7 – Moät soá kieåu neùt veõ cuûa ñoaïn thaúng

1.4. Vuøng toâ

Moät vuøng toâ bao goàm ñöôøng bieân vaø vuøng beân trong. Ñöôøng bieân laø

moät ñöôøng kheùp kín ví duï nhö ña giaùc.

Caùc thuoäc tính cuûa vuøng toâ bao goàm:

•

Thuoäc tính cuûa ñöôøng bieân : chính laø caùc thuoäc tính nhö thuoäc tính cuûa

ñoaïn thaúng.

Thuoäc tính cuûa vuøng beân trong : bao goàm maøu toâ vaø maãu toâ.

Hình 2.8 – Vuøng toâ vôùi caùc daïng ñöôøng bieân vaø maãu toâ khaùc nhau

1.5. Kí töï, chuoãi kí töï

Caùc chuoãi kí töï giuùp hieån thò noäi dung caùc thoâng ñieäp theo moät ngoân ngöõ

naøo ñoù.

Caùc thuoäc tính cuûa kí töï bao goàm :

•

Maøu saéc cuûa caùc kí töï.

Font chöõ : boä kí töï duøng hieån thò; Noù ñònh nghóa kieåu, kích thöôùc cuûa kí töï

hieån thò. Hình daïng cuûa moãi kí töï coù theå ñöôïc xaùc ñònh bôûi moät taäp caùc

ñöôøng gaáp khuùc (tröôøng hôïp font vector) hay laø maãu caùc pixel (font

bitmap). Coù nhieàu loaïi font khaùc nhau nhö font bitmap, font truetype, font

CHR, ...

•

Kích thöôùc : chieàu cao vaø chieàu roäng cuûa kí töï. Caùc kí töï ñònh nghóa baèng

ñöôøng gaáp khuùc coù theå deã daøng thay ñoåi kích thöôùc hôn laø caùc kí töï ñònh

nghóa baèng maãu caùc pixel.

Khoaûng caùch giöõa caùc kí töï.

•

Söï canh chænh (gioùng leà) : canh traùi (left text), canh phaûi (right text), canh

giöõa (center text), canh ñeàu nhau (justify text).

Caùch hieån thò tuaàn töï cuûa caùc kí töï : coù theå laø phaûi sang traùi, töø treân xuoáng

döôùi, töø traùi sang phaûi, töø döôùi leân treân.

Höôùng cuûa kí töï.

Hình 2.9 – Daïng bitmap vaø vector cuûa font kí töï B

2. CAÙC THUAÄT TOAÙN VEÕ ÑÖÔØNG

Giaû söû toïa ñoä caùc ñieåm nguyeân sau khi xaáp xæ ñoái töôïng thöïc laàn löôït laø



x_i, y_i

Baøi toaùn ñaët ra laø neáu bieát ñöôïc

nguyeân tieáp theo _i1, y_i1seõ ñöôïc xaùc ñònh nhö theá naøo.

Nhaän xeùt raèng ñeå ñoái töôïng hieån thò treân löôùi nguyeân ñöôïc lieàn neùt, caùc ñieåm maø



,i  0,.... Ñaây laø caùc ñieåm nguyeân seõ ñöôïc hieån thò treân maøn hình.



x_i, y_ilaø toïa ñoä nguyeân xaùc ñònh ôû böôùc thöù i, ñieåm





x





x

_i1, y_i1coù theå choïn chæ laø moät trong taùm ñieåm ñöôïc ñaùnh soá töø 1 ñeán 8 trong hình 2.10



(ñieåm ñen chính laø x_i, y_i).Hay noùi caùch khaùc : _i1, y_i1x_i 1, y_i 1







x









.

Daùng ñieäu cuûa ñöôøng seõ cho ta gôïi yù khi choïn moät trong taùm ñieåm treân.

Caùch choïn caùc ñieåm nhö theá naøo seõ tuøy thuoäc vaøo töøng thuaät toaùn treân cô

sôû xem xeùt tôùi vaán ñeà toái öu toác ñoä.

4

5

6

3

7

2

1

8

Hình 2.10 – Caùc ñieåm



x

_i1, y_i1coù theå choïn ôû böôùc (i+1)



2.1. Thuaät toaùn veõ ñoaïn thaúng

Xeùt ñoaïn thaúng coù heä soá goùc 0  m  1vaø Dx  0

Vôùi caùc ñoaïn thaúng daïng naøy, neáu x_i, y_ilaø ñieåm ñaõ xaùc ñònh ñöôïc ôû böôùc thöù i

_i1, y_i1ôû böôùc thöù (i+1) seõ laø moät trong hai tröôøng

.





(ñieåm maøu ñen) thì ñieåm caàn choïn

hôïp nhö hình veõ sau :



x



Hình 2.11 – Caùc ñieåm



x

_i1, y_i1choïn ôû böôùc (i+1) cho tröôøng hôïp



(x_i+1, y_i+1)

2

y_i

(x_i+1, y_i)

1

x_i

ñoaïn thaúng coù heä soá goùc 0<m<1

x

y_i1

 x_i 1







i1

Nhö vaäy :





y_i, y_i 1



Vaán ñeà coøn laïi laø caùch choïn moät trong hai ñieåm treân nhö theá naøo ñeå coù

theå toái öu veà maët toác ñoä.

2.1.1. Thuaät toaùn DDA (Digital Differential Analyzer)

Vôùi thuaät toaùn DDA, vieäc quyeát ñònh choïn y_i1laø y_ihay y_i 1, döïa vaøo phöông

trình cuûa ñoaïn thaúng y  mx  b. Nghóa laø, ta seõ tính toïa ñoä cuûa ñieåm



x_i 1, y thuoäc veà



ñoaïn thaúng thöïc. Tieáp ñoù, y_i1seõ laø giaù trò sau khi laøm troøn giaù trò tung ñoä y.

y  m

y_i1 Round



x_i 1  b



Nhö vaäy :

y

 

(x_i+1, Round(y))

(x_i+1, y)

(x_i, y_i)

Hình 2.12 – Minh hoïa thuaät toaùn DDA

Neáu tính tröïc tieáp giaù trò thöïc y ôû moãi böôùc töø phöông trình y  mx  bthì phaûi caàn

moät pheùp toaùn nhaân vaø moät pheùp toaùn coäng soá thöïc. Ñeå caûi thieän toác ñoä, ngöôøi ta tính giaù

trò thöïc cuûa y ôû moãi böôùc theo caùch sau ñeå khöû pheùp tính nhaân treân soá thöïc :

Nhaän xeùt raèng : y_sau mx_i1 b  m



x_i 1  b



y_tröôùc mx_i b

 y_sau y_tröôùc m

Löu ñoà thuaät toaùn DDA veõ ñoaïn thaúng qua hai ñieåm (x₁, y₁) vaø (x₂,y₂)

Begin

m=Dy/Dx;

x=x1;

y=y1;

putpixel(x, Round(y), c);

No

x<x2

Yes

x=x+1;

y=y+m;

putpixel(x, Round(y),c);

End

Caøi ñaët minh hoïa thuaät toaùn DDA

#define Round(a) int(a+0.5)

int Color = GREEN;

void LineDDA (int x1, int y1, int x2, int y2)

{

int x = x1;

float y = y1;

float m = float(y2-y1)/(x2-x1);

putpixel(x, Round(y), Color);

for(int i=x1; i<x2; i++)

{

x++;

y +=m;

putpixel(x, Round(y), Color);

}

} // LineDDA

Nhaän xeùt

•

Vieäc söû duïng coâng thöùc y_sau y_tröôùc m ñeå tính giaù trò y taïi moãi böôùc ñaõ

giuùp cho thuaät toaùn DDA nhanh hôn haún so vôùi caùch tính y töø phöông

trình y  mx  b do khöû ñöôïc pheùp nhaân treân soá thöïc. Tuy nhieân, vieäc

coäng doàn giaù trò thöïc m vaøo y coù theå seõ tích luõy sai soá laøm cho haøm laøm

troøn coù keát quaû sai daãn tôùi vieäc xaùc ñònh vò trí cuûa ñieåm veõ ra bò cheäch

höôùng so vôùi ñöôøng thaúng thöïc. Ñieàu naøy chæ xaûy ra khi veõ ñoaïn thaúng khaù

daøi.

Tuy ñaõ khöû ñöôïc pheùp nhaân soá thöïc nhöng thuaät toaùn DDA vaãn coøn bò haïn

cheá veà maët toác ñoä do vaãn coøn pheùp toaùn coäng soá thöïc vaø laøm troøn. Coù theå

khaéc phuïc thao taùc coäng soá thöïc m vaø laøm troøn trong thuaät toaùn baèng caùch

Dy

nhaän xeùt m 

vôùi Dy, Dx laø caùc soá nguyeân.

Dx

2.1.2. Thuaät toaùn Bresenham

Thuaät toaùn Bresenham ñöa ra caùch choïn y_i1laø y_ihay y_i 1 theo moät höôùng khaùc

sao cho coù theå toái öu hoùa veà maët toác ñoä so vôùi thuaät toaùn DDA. Vaán ñeà maáu choát ôû ñaây laø

laøm theá naøo ñeå haïn cheá toái ña caùc pheùp toaùn treân soá thöïc trong thuaät toaùn.

(x_i+1, y)

P

y_i+1

y

d₂

d₁

S

y_i

x_i

x_i+1

Hình 2.13 – Minh hoïa thuaät toaùn Bresenham

Goïi

Ñaët



x_i 1, y

d₁ y  y_i

d₂ y_i 1  y



laø ñieåm thuoäc ñoaïn thaúng. Ta coù: y  m



x_i 1  b.







Xeùt taát caû caùc vò trí töông ñoái cuûa y so vôùi y_ivaø y_i 1, vieäc choïn ñieåm

S hay P phuï thuoäc vaøo vieäc so saùnh d₁vaø d₂hay daáu cuûa d₁ d₂:



x

_i1, y_i1



laø

•

Neáu d₁ d₂ 0 , ta seõ choïn ñieåm S, töùc laø y_i1 y_i

Ngöôïc laïi, neáu d₁ d₂ 0 , ta seõ choïn ñieåm P, töùc laø y_i1 y_i 1 .

d₁ d₂ Dx 2y  2y_i 1

x_i 1  b  2y_i 1

.

Xeùt p_i Dx

 p_i Dx











2



m







Dy

Dx

Dx.

Thay m 

c  2Dy  2b 1

Nhaän xeùt raèng do Dx  0 neân daáu cuûa bieåu thöùc d₁ d₂cuõng chính laø daáu cuûa p_i

vaøo phöông trình treân ta ñöôïc : p_i 2Dyx_i 2Dxy_i c , vôùi





.

Hay noùi moät caùch khaùc, neáu taïi böôùc thöù i ta xaùc ñònh ñöôïc daáu cuûa p_ithì xem nhö ta xaùc

ñònh ñöôïc ñieåm caàn choïn ôû böôùc (i+1). Vaán ñeà coøn laïi laø laøm theá naøo ñeå tính ñöôïc p_itaïi

moãi böôùc thaät nhanh.

Ta coù :

p_i1 p_i

 p_i1 p_i 2Dy

 p_i1 p_i 2Dy  2Dx



2Dyx_i1 2Dxy_i1 c

x_i1 x_i 2Dx

y_i1 y_i







2Dyx_i 2Dxy_i c

y_i1 y_i

, do x_i1 x_i 1















Töø ñaây ta coù theå suy ra caùch tính p_i1töø p_inhö sau :

•

Neáu p_i 0 thì p_i1 p_i 2Dy do ta choïn y_i1 y_i

.

•

Ngöôïc laïi, neáu p_i 0, thì p_i1 p_i 2Dy  2Dx, do ta choïn y_i1 y_i 1 .

Giaù trò p₀ñöôïc tính töø ñieåm veõ ñaàu tieân

p₀ 2Dyx₀ 2Dxy₀ c  2Dyx₀ 2Dxy₀ 2Dy  2b 1 Dx



x₀, y₀



theo coâng thöùc

:

.





Dy

Do



x₀, y₀



laø ñieåm nguyeân thuoäc veà ñoaïn thaúng neân ta coù y₀ mx₀ b 

x₀ b

Dx

Theá vaøo phöông trình treân ta suy ra : p₀ 2Dy  Dx.

Löu ñoà thuaät toaùn Bresenham

Begin

p=2Dy-Dx;

Const1=2Dy;

Const2=2(Dy-Dx);

x=x1;

y=y1;

putpixel(x, y, c);

No

x<x2

Yes

No

p<0

Yes

p=p+Const1;

p=p+Const2;

y=y+1

x=x+1;

putpixel(x,y,c);

End

Caøi ñaët minh hoïa thuaät toaùn Bresenham

void LineBres (int x1, int y1, int x2, int y2)

{

int Dx, Dy, p, Const1, Const2;

int x, y;

Dx

Dy

p

= x2 - x1;

= y2 - y1;

= 2*Dy - Dx; // Dy <<1 - Dx

Const1 = 2*Dy; // Dy <<1

Const2 = 2*(Dy-Dx); // (Dy-Dx) <<1

x = x1;

y = y1;

putpixel(x, y, Color);

for(i=x1; i<x2; i++)

{

if (p<0)

p += Const1;

else

{

p += Const2;

y++;

}

x++;

putpixel(x, y, Color);

}

} // LineBres

Nhaän xeùt

•

Thuaät toaùn Bresenham chæ laøm vieäc treân soá nguyeân vaø caùc thao taùc treân soá

nguyeân chæ laø pheùp coäng vaø pheùp dòch bit (pheùp nhaân 2) ñieàu naøy laø moät

caûi tieán laøm taêng toác ñoä ñaùng keå so vôùi thuaät toaùn DDA. YÙ töôûng chính cuûa

thuaät toaùn naèm ôû choã xeùt daáu p_iñeå quyeát ñònh ñieåm keá tieáp, vaø söû duïng

coâng thöùc truy hoài p_i1 p_iñeå tính p_ibaèng caùc pheùp toaùn ñôn giaûn treân

soá nguyeân.

Thuaät toaùn naøy cho keát quaû töông töï nhö thuaät toaùn DDA.

2.1.3. Thuaät toaùn MidPoint

Thuaät toaùn MidPoint ñöa ra caùch choïn y_i1laø y_ihay y_i 1 baèng caùch so saùnh

ñieåm thöïc Q



x_i 1, y vôùi ñieåm MidPoint laø trung ñieåm cuûa S vaø P. Ta coù :



•

Neáu ñieåm Q naèm döôùi ñieåm MidPoint, ta choïn S.

•

Ngöôïc laïi neáu ñieåm Q naèm treân ñieåm MidPoint ta choïn P.

Q(x_i+1, y)

P

y_i+1

y_i

MidPoint

S

x_i

x_i+1

Hình 2.14 – Minh hoïa thuaät toaùn MidPoint

Ta coù daïng toång quaùt cuûa phöông trình ñöôøng thaúng :

Ax  By  C  0

vôùi A  y₂ y₁, B  



x₂ x₁,C  x₂y₁ x₁y₂



Ñaët

F



x, y



 Ax  By  C, ta coù nhaän xeùt :

 0,neáu



x,y



naèm phía treân ñöôøng thaúng

thuoäc veàñöôøng thaúng

naèm phía döôùi ñöôøng thaúng.



F



x, y



 0,neáu

 0,neáu



x,y









Luùc naøy vieäc choïn caùc ñieåm S, P ôû treân ñöôïc ñöa veà vieäc xeùt daáu cuûa

1

2





p_i 2F



MidPoint



 2F x  1, y 

.





i





•

Neáu p_i 0, ñieåm MidPoint naèm phía treân ñoaïn thaúng. Luùc naøy ñieåm thöïc

Q naèm döôùi ñieåm MidPoint neân ta choïn S, töùc laø y_i1 y_i

.

•

Ngöôïc laïi, neáu p_i 0, ñieåm MidPoint naèm phía döôùi ñoaïn thaúng. Luùc naøy

ñieåm thöïc Q naèm treân ñieåm MidPoint neân ta choïn P, töùc laø y_i1 y_i 1 .

Maët khaùc :

1

2

1

2













p_i1 p  2F x  1, y_i1



 2F x  1, y 



i

i1

i

















1

2

1

2











 p_i1 p  2 A



x

_i1 1



 B y_i1

 C  2 A



x_i 1



 B y 

 C









i





















 p_i1 p_i 2A  2B

Vaäy :



y_i1 y_i



 2Dy  2Dx



y_i1 y_i



•

p_i1 p_i 2Dy, neáu p_i 0 do ta choïn y_i1 y_i

.

p_i1 p_i 2Dy  2Dx, neáu p_i 0 do ta choïn y_i1 y_i 1 .

x₀, y₀

Ta tính giaù trò p₀öùng vôùi ñieåm ban ñaàu





, vôùi nhaän xeùt raèng



x₀, y₀laø



ñieåm thuoäc veà ñoaïn thaúng, töùc laø coù : Ax₀ By₀ C  0





1

2

1

2













p  2F x  1, y 

 2 A



x₀ 1



 B y 

 C



0

















 p₀ 2



Ax₀ By₀ C  2A  B  2A  B  2Dy  Dx



Nhaän xeùt raèng thuaät toaùn MidPoint cho keát quaû töông töï nhö thuaät toaùn

Bresenham.

2.2. Thuaät toaùn veõ ñöôøng troøn

Phöông trình ñöôøng troøn coù taâm laø goác toïa ñoä, baùn kính R laø : x² y² R²

Töø phöông trình naøy ta coù theå ñöa veà daïng y   R² x². Ñeå veõ caùc ñöôøng

troøn coù taâm baát kì, ñôn giaûn chæ caàn tònh tieán caùc ñieåm sau khi veõ

xong ñöôøng troøn coù taâm laø goác toïa ñoä theo vector tònh tieán

.



x_C, y_C





x_C, y_C.



2.2.1. Moät soá caùch tieáp caän veõ ñöôøng troøn

Do tính ñoái xöùng neân ñeå veõ toaøn boä ñöôøng troøn, ta chæ caàn veõ cung ¼

ñöôøng troøn sau ñoù laáy ñoái xöùng ñeå xaùc ñònh caùc ñieåm coøn laïi.

Moät trong nhöõng caùch ñôn giaûn nhaát laø cho x chaïy töø 0 ñeán R, sau ñoù tính y töø coâng

thöùc treân (chæ laáy giaù trò döông) roài laøm troøn ñeå xaùc ñònh giaù trò nguyeân töông öùng. Caùch

laøm naøy khoâng hieäu quaû do gaëp phaûi caùc pheùp toaùn nhaân vaø laáy caên laøm haïn cheá toác ñoä,

ngoaøi ra ñöôøng troøn veõ ra theo caùch naøy coù theå khoâng lieàn neùt (tröø tröôøng hôïp R lôùn) khi

x gaàn R (do chæ coù moät giaù trò y duy nhaát cho moät giaù trò x). Chuùng ta coù theå khaéc phuïc

ñieàu naøy baèng caùch ñieàu chænh ñoái töôïng thay ñoåi laø x (roài tính y theo x) hay y (roài tính x

theo y) tuøy vaøo giaù trò tuyeät ñoái cuûa heä soá goùc ñöôøng troøn laø lôùn hôn hay nhoû hôn 1,

nhöng caùch laøm naøy ñoøi hoûi theâm caùc pheùp tính toaùn vaø kieåm tra neân laøm cho thuaät toaùn

phöùc taïp theâm. (Xem hình 2.15)

Moät caùch tieáp caän khaùc laø veõ caùc ñieåm

ñeán 90⁰. Caùch naøy seõ khaéc phuïc haïn cheá ñöôøng khoâng lieàn neùt cuûa thuaät

toaùn treân, tuy nhieân ñieåm haïn cheá chính cuûa thuaät toaùn naøy ñoù laø choïn



Rcos







, Rsin



 , vôùi 

chaïy töø 0⁰



böôùc nhaûy cho

 nhö theá naøo cho phuø hôïp khi baùn kính thay ñoåi.

(0,17)

(17,0)

Hình 2.15 – Ñöôøng troøn veõ ra khoâng lieàn neùt theo caùch veõ treân

2.2.2. Thuaät toaùn MidPoint

Do tính ñoái xöùng cuûa ñöôøng troøn (C) neân ta chæ caàn veõ cung (C^1/8) laø cung 1/8

ñöôøng troøn, sau ñoù laáy ñoái xöùng. Cung (C^1/8) ñöôïc moâ taû nhö sau (cung cuûa

phaàn toâ xaùm trong hình veõ) :



2

0  x  R





2



R

 y  R





2

(-x,y)

(x,y)

(-y,x)

(y,x)

R

2

(-y,-x)

(y,-x)

(-x,-y)

(x,-y)

Hình 2.16 – Caùc vò trí ñoái xöùng treân ñöôøng troøn (C) töông öùng vôùi (x,y)

Nhö vaäy neáu coù (x, y)  (C^1/8) thì caùc ñieåm : (y, x), (y,-x), (x,-y), (-x,-y), (-y,-x), (-

y,x), (-x,y) seõ thuoäc (C).

Choïn ñieåm baét ñaàu ñeå veõ laø ñieåm (0,R). Döïa vaøo hình veõ, neáu



x_i, y_i



laø

ñieåm nguyeân ñaõ tìm ñöôïc ôû böôùc thöù i, thì ñieåm

laø söï löïa choïn giöõa S vaø P.



x

_i1, y_i1



ôû böôùc thöù (i+1)

x

y_i1

 x_i 1







i1

Nhö vaäy :





y_i, y_i 1



Töông töï nhö thuaät toaùn MidPoint veõ ñoaïn thaúng, vieäc quyeát ñònh choïn moät

trong hai ñieåm S vaø P seõ ñöôïc thöïc hieän thoâng qua vieäc xeùt daáu cuûa moät

haøm naøo ñoù taïi ñieåm MidPoint laø ñieåm naèm giöõa chuùng.

Q(x_i+1, y)

S

P

y_i

MidPoint

y_i-1

x_i

x_i+1

Hình 2.17 – Thuaät toaùn MidPoint veõ ñöôøng troøn

Ñaët

F



x, y

 x² y² R², ta coù :



 0,neáu



x,y



naèm trong ñöôøng troøn

naèm treân ñöôøng troøn

naèm ngoaøi ñöôøng troøn.



F



x, y



 0,neáu

 0,neáu









1

2





Xeùt p_i F



MidPoint



 F x  1, y  . Ta coù :





i





•

Neáu p_i 0, ñieåm MidPoint naèm trong ñöôøng troøn. Luùc naøy ñieåm thöïc Q

gaàn S hôn neân ta choïn S, töùc laø y_i1 y_i

.

•

Ngöôïc laïi, neáu p_i 0, ñieåm MidPoint naèm ngoaøi ñöôøng troøn. Luùc naøy

ñieåm thöïc Q gaàn P hôn neân ta choïn P, töùc laø y_i1 y_i 1.

Maët khaùc :

1

2

1

2













p_i1 p  F x  1, y_i1



 F x  1, y 



i i



i

i1











2













1

2

1

2









 p  p 



x

 1 ²



 y



 R²







x  1 ²



 y 

 R²













i1

i

i1

i























2





1

2

1













 p  p 



x  2 ²



 y



 R²





x  1 ²



 y 

 R²













i1

i

i1

i

2

























 p_i1 p  2x  3

Vaäy :



y_i²_1 y_i²







y_i1 y_i

i

•

p_i1 p_i 2x_i 3, neáu p_i 0 do ta choïn y_i1 y_i

p_i1 p_i 2x_i 2y_i 5, neáu p_i 0 do ta choïn y_i1 y_i 1.

x₀, y₀0, R

.

Ta tính giaù trò p₀öùng vôùi ñieåm ban ñaàu











.

1

2

1

2

5

4













p  F x  1, y 

 F 1, R 



 R



0









Löu ñoà thuaät toaùn MidPoint veõ ñöôøng troøn

Begin

p=5/4-R;

x=0;

y=R;

Put8Pixel(x, y, c);

No

x<y

Yes

No

p<0

Yes

p=p+2*x+3;

p=p+2(x-y)+5;

y=y-1

x=x+1;

Put8Pixel(x,y,c);

End